DOWN-THE-STREAM-2
Challenge
The author tried to be a bit more clever and this time, parts of the cipher are redacted. However, you were able to intercept a plaintext-ciphertext pair generated from the algorithm. Does this compensate for the redacted algorithm?
The initialization vector this time (IV) is the palindrome generated from the previous IV. e.g. if the previous IV was 2a, then the palindrome generated is 2aa2
Files given: chall.py, intercepted.txt, output.txt
Understanding the cipher
Same shape as down-the-stream-1, upgraded to a 16-bit register, but the feedback function is imported from a module we don't have:
from unknown_funcs import generate_feedback
def next_register(register: int) -> int:
for _ in range(16):
feedback = generate_feedback(register)
register = ((register << 1) | feedback) & 0xffff
return register
Two things save this: the IV isn't fully unknown (it's the palindrome of down-the-stream-1's IV, 0x8e becomes 0x8ee8), and output.txt hands us a known 12-byte plaintext/ciphertext pair, "Hello, world", encrypted under that same IV. That's enough to reverse-engineer generate_feedback itself.
Recovering the register sequence
The cipher XORs each plaintext byte pair with the current 16-bit register, then clocks the register once (16 internal micro-steps) before the next pair. Since ct = pt ⊕ register, every register value along the way is just ct ⊕ pt at that position. No guessing required.
pt = b"Hello, world"
ct = bytes.fromhex("c68d2a7ec13c03eb380395cf")
recovered_iv = ((ct[0] ^ pt[0]) << 8) | (ct[1] ^ pt[1])
assert recovered_iv == IV # sanity check: first pair uses the raw IV, unclocked
regs = [IV]
for i in range(2, len(pt), 2):
r = ((ct[i] ^ pt[i]) << 8) | (ct[i + 1] ^ pt[i + 1])
regs.append(r) # regs[k] = register after k applications of next_register
Recovering the feedback mask
The redacted generate_feedback almost certainly has the same shape as down-the-stream-1's: parity of some fixed AND mask against the register, just with an unknown 16-bit mask and one clock per bit instead of a fixed offset set. Rather than solve for it by hand, it's cheap to just brute force. Only 65536 possible masks, and every consecutive (regs[i], regs[i+1]) pair recovered above has to agree on the same one.
def next_register(register, mask):
for _ in range(16):
feedback = bin(register & mask).count("1") % 2
register = ((register << 1) | feedback) & 0xffff
return register
for mask in range(1, 0x10000):
if all(next_register(regs[i], mask) == regs[i + 1] for i in range(len(regs) - 1)):
print(f"recovered mask: 0x{mask:04x}")
break
This converges on a single mask instantly. Five independent transitions is far more constraint than one 16-bit unknown needs.
Decrypting the flag
With the mask recovered, replay the same keystream generator from the known IV against intercepted.txt, which is the actual flag ciphertext. This is the same next-register loop from down-the-stream-1, just with the mask filled in instead of hardcoded taps:
def next_register(register):
for _ in range(16):
register = ((register << 1) | bin(register & 0xba40).count('1') % 2) & 0xffff
return register
ct = bytes.fromhex("e989357ec7774be81425bfd007aaf6f30b5342ce52a66776f8b326449b85ed186f1641603546b068dd89ba6b3145")
IV = 0x8ee8
pt = bytearray()
pt.append(ct[0] ^ (IV >> 8))
pt.append(ct[1] ^ (IV & 0x00ff))
for i in range(2, len(ct), 2):
IV = next_register(IV)
pt.append(ct[i] ^ (IV >> 8))
pt.append(ct[i+1] ^ (IV & 0x00ff))
print(pt.decode())