infosecfamily
← В каталог
CyLab (picoCTF)  /  Medium

shift registers, Small Trouble, Timestamped Secrets

Задачи picoCTF

shift registers ↗Small Trouble ↗Timestamped Secrets ↗

shift registers

Задача: I learned about lfsr today in school so i decided to implement it in my program. It must be safe right? 

chall.py  output.txt

Начальные данные

Нам даются файлы:

chall.py:

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes

key = bytes_to_long(get_random_bytes(126))

def steplfsr(lfsr):
    b7 = (lfsr >> 7) & 1
    b5 = (lfsr >> 5) & 1
    b4 = (lfsr >> 4) & 1
    b3 = (lfsr >> 3) & 1

    feedback = b7 ^ b5 ^ b4 ^ b3
    lfsr = (feedback << 7) | (lfsr >> 1)
    return lfsr

def encrypt_lfsr(pt_bytes):
    output = bytearray()
    lfsr = key & 0xFF
    for p in pt_bytes:
        lfsr = steplfsr(lfsr)
        ks = lfsr
        output.append(p ^ ks)
    return bytes_to_long(bytes(output))

pt = b"[redacted]"
ct = encrypt_lfsr(pt)

print(long_to_bytes(ct).hex())

output.txt:

21c1b705764e4bfdafd01e0bfdbc38d5eadf92991cdd347064e37444e517d661cea9

Криптоанализ

Анализируя файл chall.py, можно заметить две функции: 1. steplfsr 2. encrypt_lfsr

Ф-ция 1. реализует восьмибитный сдвиг регистра с обратной связью. Сама функция обратима, но перебор 256 значений решает эту проблему мгновенно.

В ф-ции 2. происходит само шифрование с помощью ф-ции 1.. Ключ генерируется путем строчки в начале: key = bytes_to_long(get_random_bytes(126)), однако в самой функции есть строка lfsr = key & 0xFF, что оставляет всего 256 вариантов изначального состояния lfsr, поэтому ключ фиктивен - его можно не подбирать.

Сама гамма не зависит от исходного текста - это просто xor байтов текста с байтами гаммы.

Также нам известно начало исходной строки: picoCTF{ - следовательно, можно применить known plaintext attack.

Решение

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes

key = bytes_to_long(get_random_bytes(126))

def steplfsr(lfsr):
    b7 = (lfsr >> 7) & 1
    b5 = (lfsr >> 5) & 1
    b4 = (lfsr >> 4) & 1
    b3 = (lfsr >> 3) & 1

    feedback = b7 ^ b5 ^ b4 ^ b3
    lfsr = (feedback << 7) | (lfsr >> 1)
    return lfsr

ct_hex = "21c1b705764e4bfdafd01e0bfdbc38d5eadf92991cdd347064e37444e517d661cea9"
ct = bytes.fromhex(ct_hex)

for key_byte in range(256):
    lfsr = key_byte
    pt = bytearray()
    for c in ct:
        lfsr = steplfsr(lfsr)   # шаг LFSR
        ks = lfsr               # гамма — новое состояние
        pt.append(c ^ ks)
    # Проверяем, похоже ли на флаг (все байты печатные или начало с 'picoCTF')
    try:
        text = pt.decode('ascii')
        if text.startswith('picoCTF{'):
            print(f"key_byte=0x{key_byte:02x}: {text}")
    except UnicodeDecodeError:
        continue

Ответ

Small Trouble

Задача: Everything seems secure; strong numbers, familiar parameters but something small might ruin it all. Can you recover the message?

Download the message. And source code

Начальные данные

Нам даются файлы:

encryption.py:

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random

# Generate two large primes (1048 bits each)
p = getPrime(1048)
q = getPrime(1048)
n = p * q
phi = (p - 1) * (q - 1)

# compute d
d = getPrime(256)

# Compute the public exponent
e = inverse(d, phi)

# Encrypt a flag
flag = b'picoCTF{...}'
m = bytes_to_long(flag)
c = pow(m, e, n)

# Output for the challenge
with open("message.txt", "w") as f:
    f.write(f"n = {n}\n")
    f.write(f"e = {e}\n")
    f.write(f"c = {c}\n")

message.txt:

n = 3980993015101017140353277804369745949706344223334890812840413257071044175973139291856038905399468319530362030870405443017903655374929929825011733964330181337551061274726015170805648591339935699566483704533804413902772334194671185814032757795167276567492610548489766891166023546451221494011601527912413323143640008533569546329046772124896140545774468831882189458647605131344071766512469603284171712833770168967153998797122819825938323489525196597407482515674210085730485950171311356595462370875129472210846138025654237220573246971086221110031195278019873474587710322597773432501095235059971088078096926751790014797097704337356321889
e = 3336497038614663222541921459680551835187913731404732354361770350895041393777650313575506088859422849385970294213215931070595265411244105028409623278013975724125500479919877564207207562572189315593170541926598007670763000263224010236185517132229343161667668429997117301579363090706170019283552359847390040311521617091884426220652237247589452213130475528794167610900761281292390567153221748933849959961895636324991675428047481887984343193310278137379109243220192216924968789976201537337617841164156347418356710488273730184036786730194843318185762453423678066812440979743181541976510807538521163968859836855958692325875567630213728207
c = 1826031079095822845536526213992736069835634421976077836267143793181964583083024760950942723002771287666852728279522910274806690415793596687180742873080830698626932982997385432329275546871401690500831953978994557961462780510004840010773264058566952483483889805568428664825400505121671890223584721114411827697594512296341594773601537519080793749568472726239590091904052247534142381322885597999201255135897334420626115847929127670295300664641023915921412100348810694368790829410468324587518896440574662249893060377916803644769267529820246473511018540449718324002956264174312180181563530270721168751856698020681743829723342459520727632

Криптоанализ

Это RSA. N имеет размер len(p) + len(q) = 4096. d - всего 256 бит - примерно в 2**1840 меньше n - следовательно, можно применить Атаку Винера.

Решение:

С помощью RsaCtfTool версии commit 9581ede69f5d59059282efd4c505e5b6eb7eff38

python3 ~/RsaCtfTool/RsaCtfTool.py -n 3980993015101017140353277804369745949706344223334890812840413257071044175973139291856038905399468319530362030870405443017903655374929929825011733964330181337551061274726015170805648591339935699566483704533804413902772334194671185814032757795167276567492610548489766891166023546451221494011601527912413323143640008533569546329046772124896140545774468831882189458647605131344071766512469603284171712833770168967153998797122819825938323489525196597407482515674210085730485950171311356595462370875129472210846138025654237220573246971086221110031195278019873474587710322597773432501095235059971088078096926751790014797097704337356321889 -e 3336497038614663222541921459680551835187913731404732354361770350895041393777650313575506088859422849385970294213215931070595265411244105028409623278013975724125500479919877564207207562572189315593170541926598007670763000263224010236185517132229343161667668429997117301579363090706170019283552359847390040311521617091884426220652237247589452213130475528794167610900761281292390567153221748933849959961895636324991675428047481887984343193310278137379109243220192216924968789976201537337617841164156347418356710488273730184036786730194843318185762453423678066812440979743181541976510807538521163968859836855958692325875567630213728207 --decrypt 1826031079095822845536526213992736069835634421976077836267143793181964583083024760950942723002771287666852728279522910274806690415793596687180742873080830698626932982997385432329275546871401690500831953978994557961462780510004840010773264058566952483483889805568428664825400505121671890223584721114411827697594512296341594773601537519080793749568472726239590091904052247534142381322885597999201255135897334420626115847929127670295300664641023915921412100348810694368790829410468324587518896440574662249893060377916803644769267529820246473511018540449718324002956264174312180181563530270721168751856698020681743829723342459520727632 --attack wiener

Ответ

Timestamped Secrets

Задача: Someone encrypted a message using AES in ECB mode but they weren’t very careful with their key. Turns out it’s derived from something as simple as the current time! Can you uncover the key and decrypt the flag?

Download the encrypted message: message
You may also find the encryption script helpful: code

Начальные данные

Нам даются файлы:

encryption.py:

from hashlib import sha256
import time
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

def encrypt(plaintext: str, timestamp: int) -> str:
    timestamp = int(time.time())
    key = sha256(str(timestamp).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    padded = pad(plaintext.encode(), AES.block_size)
    ciphertext = cipher.encrypt(padded)
    return ciphertext.hex()


if __name__ == "__main__":
    plaintext = "picoCTF{...}"
    result = encrypt(plaintext, key)
    print(f"Hint: The encryption was done around {timestamp} UTC\n")
    print(f"Ciphertext (hex): {ciphertext.hex()}\n")

message.txt

Hint: The encryption was done around 1770242601 UTC
Ciphertext (hex): 2849cce932845f9864c369cf519473dd9b54ce1105c02305886bdc8690134711

Криптоанализ

Нам прямым текстом в main дается ключ - получить мы его можем примерно таким образом:

timestamp = 1770242601
key = sha256(str(timestamp).encode()).digest()[:16]

Далее нам достаточно просто дописать функцию расшифровки и unpad-ить текст.

Решение

from hashlib import sha256
import time
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

def decrypt(ciphertext: str) -> str:

    timestamp = 1770242601
    key = sha256(str(timestamp).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    ciphertext = bytes.fromhex(ciphertext)
    plaintext = cipher.decrypt(ciphertext)
    return unpad(plaintext, AES.block_size).decode()


if __name__ == "__main__":
    ciphertext = '2849cce932845f9864c369cf519473dd9b54ce1105c02305886bdc8690134711'
    print(decrypt(ciphertext))

Ответ