shift registers, Small Trouble, Timestamped Secrets
Задачи picoCTF
shift registers
Начальные данные
Нам даются файлы:
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
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
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))
Ответ
