CRACK Solution

Shift Register

CRACK LFSR keystream compare

In-game screenshot of Shift Register
In-game view
FamilyCRACK Graph0.902 DifficultyHard Ring05 IDz6_lfsr_stream

Prerequisites

SPLIT DECAY

Unlocks

ECHO CANCEL

Accepted input SIGNAL
TechniqueLFSR keystream compare Rulenonzero SampleSIGNAL

Walkthrough

The keystream here is no counter. A linear feedback shift register clocks out one byte per character, shifting and tapping as it goes. Clone the register, replay its output, and the stream lifts off.

An 8-bit Galois LFSR (seed 0x9C, taps 0xB8) supplies the XOR keystream. Reproduce the shift-and-tap sequence to get each keystream byte, then XOR it out of the target.

Hints

  • HINT 1: Length is fixed at 6. The state starts at 0x9C and changes after every character; the first keystream byte is the seed itself.
  • HINT 2: To advance: read the low bit, shift the state right by one, and XOR with 0xB8 only when that low bit was 1.
  • HINT 3: The six keystream bytes are 0x9C 0x4E 0x27 0xAB 0xED 0xCE. XOR them into the targets to spell SIGNAL.

Reject Samples

  • SIGNAM
  • signal
  • SIGNA
  • SIGNALL
  • STREAM
Verifier Listing 
; z6_lfsr_stream: "Shift Register". The keystream is not a counter and not an
; LCG; it comes from an 8-bit Galois LFSR. Starting from seed 0x9C, each step
; emits the current state as the keystream byte, then advances: pull the low bit
; off, shift the state right by one, and if that low bit was set, XOR the state
; with the tap mask 0xB8. The keystream byte is XOR'd into the matching input byte
; and compared to a stored target, position by position. To crack it, run the same
; LFSR to regenerate the six keystream bytes, then XOR them back out of the
; targets. Technique: LFSR keystream compare. r0 = 1 on accept; rule: nonzero.
;
; keystream from seed 0x9C, taps 0xB8: 0x9C 0x4E 0x27 0xAB 0xED 0xCE
; ct = ks ^ c of "SIGNAL": 0xCF 0x07 0x60 0xE5 0xAC 0x82

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

        mov   r3, 0x9C      ; r3 = LFSR state (seed)
        mov   r7, 0         ; r7 = position index
loop:   cmp   r7, 6
        jge   ok

        ldb   r0, [r7]
        xor   r0, r3        ; mix in this step's keystream byte (the state)

        ; --- 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, 0x82      ; position 5
        jmp   chk
t0:     mov   r1, 0xCF
        jmp   chk
t1:     mov   r1, 0x07
        jmp   chk
t2:     mov   r1, 0x60
        jmp   chk
t3:     mov   r1, 0xE5
        jmp   chk
t4:     mov   r1, 0xAC
chk:    cmp   r0, r1
        jnz   bad

        ; --- advance the Galois LFSR one step --------------------------
        mov   r4, r3
        and   r4, 1         ; r4 = low (output) bit
        shr   r3, 1         ; shift the state right
        cmp   r4, 0
        jz    nostep
        xor   r3, 0xB8      ; tapped feedback
nostep: inc   r7
        jmp   loop

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