CRACK Solution

Golden Stream

CRACK Fibonacci additive keystream cipher

FamilyCRACK Graph0.912 DifficultyHard Ring05 IDz6_fib

Prerequisites

TENS AND UNITS Square Deal

Unlocks

SCALE PAIR

Accepted input PHOTON

TechniqueFibonacci additive keystream cipher Rulenonzero SamplePHOTON

Walkthrough

This stream cipher does not count and does not XOR. Its keystream grows like Fibonacci, each byte the sum of the last two, and it is added onto the text. Roll the sequence forward and subtract your way back in.

Keystream is a Fibonacci recurrence seeded 0x1F, 0x2D; each next byte is the sum of the previous two, and the cipher adds it to the plaintext. Regenerate the bytes and subtract them from the targets.

Hints

HINT 1: Length is fixed at 6. The first two keystream bytes are the seeds; after that each is the sum of the two before it.
HINT 2: The byte is ADDED, not XOR'd. To undo a position, subtract its keystream byte from the target (mod 256).
HINT 3: The keystream is 0x1F 0x2D 0x4C 0x79 0xC5 0x3E. Subtracting from the targets spells PHOTON.

Reject Samples

PHOTOM
photon
PHOTO
PHOTONN
PROTON

Verifier Listing

; z6_fib: "Golden Stream". An additive keystream cipher, but the keystream is a
; Fibonacci recurrence rather than a counter or an LCG, and it is ADDED to the
; plaintext rather than XOR'd. The state is a pair of bytes seeded 0x1F, 0x2D; each
; new keystream byte is the sum of the previous two (mod 256). For every position,
; target = (input byte + keystream byte) mod 256, compared to a stored value. To
; crack it, roll the Fibonacci pair forward to get the six keystream bytes, then
; SUBTRACT each from its target to recover the password. Technique: Fibonacci
; additive keystream cipher. r0 = 1 on accept; rule: nonzero.
;
; keystream (k0=0x1F, k1=0x2D, then sum the previous two): 0x1F 0x2D 0x4C 0x79 0xC5 0x3E
; ct = (c + k) mod 256 of "PHOTON": 0x6F 0x75 0x9B 0xCD 0x14 0x8C

        len   r2
        cmp   r2, 6
        jnz   bad           ; fixed length 6

        mov   r5, 0x1F      ; r5 = previous-previous keystream byte
        mov   r6, 0x2D      ; r6 = previous keystream byte
        mov   r7, 0         ; r7 = position index
loop:   cmp   r7, 6
        jge   ok

        ; --- compute this step's keystream byte in r3 ------------------
        cmp   r7, 0
        jz    k0
        cmp   r7, 1
        jz    k1
        ; r3 = r5 + r6, then roll the pair forward
        mov   r3, r5
        add   r3, r6
        mov   r5, r6
        mov   r6, r3
        jmp   apply
k0:     mov   r3, 0x1F      ; first keystream byte is the first seed
        jmp   apply
k1:     mov   r3, 0x2D      ; second keystream byte is the second seed
apply:  ldb   r0, [r7]
        add   r0, r3        ; additive cipher

        ; --- select this position's target byte ------------------------
        cmp   r7, 0
        jz    t0
        cmp   r7, 1
        jz    t1
        cmp   r7, 2
        jz    t2
        cmp   r7, 3
        jz    t3
        cmp   r7, 4
        jz    t4
        mov   r1, 0x8C      ; position 5
        jmp   chk
t0:     mov   r1, 0x6F
        jmp   chk
t1:     mov   r1, 0x75
        jmp   chk
t2:     mov   r1, 0x9B
        jmp   chk
t3:     mov   r1, 0xCD
        jmp   chk
t4:     mov   r1, 0x14
chk:    cmp   r0, r1
        jnz   bad
        inc   r7
        jmp   loop

ok:     mov   r0, 1
        ret
bad:    mov   r0, 0
        ret