GCHQ _Can you crack it?
blindcyclistsunion at gmail.com
Thu Dec 15 17:04:38 GMT 2011
On 12 Dec 2011, at 06:34, James Firth wrote:
> The competition, reportedly a recruitment drive, at canyoucrackit.co.uk was
> meant to close at midnight last night.
> Did anyone try solve it? Turns out not crypto knowledge required - but a
> lot of computer science/software engineering is involved:
<delurk, with apols for O/T>
Tried, and indeed succeeded. And what fun it was! However, as I come
to write bits of it up, I'm looking at a bit of the disassembly listing
from the first stage, which for the most part looks exactly like an RC4
stream cipher implementation, but for just one thing :
80480c3: inc al ;; i = ( i+1 )
80480c5: add bl,BYTE PTR [esi+eax*1] ;; j = ( j + S[i] )
80480c8: mov dl,BYTE PTR [esi+eax*1] ;;
80480cb: mov dh,BYTE PTR [esi+ebx*1] ;; swap S[i] and S[j]
80480ce: mov BYTE PTR [esi+eax*1],dh ;;
80480d1: mov BYTE PTR [esi+ebx*1],dl ;;
80480d4: add dl,dh ;; t = (S[i]+S[j])
80480d6: xor dh,dh
80480d8: mov bl,BYTE PTR [esi+edx*1] ;; Should be : K = S[t]
;; Actually : j = S[t]
;; Since S[t] is stored
;; in bl which is used
;; as j above.
80480db: mov dl,BYTE PTR [edi]
80480dd: xor dl,bl ;; xor to get plain
80480df: mov BYTE PTR [edi],dl ;; write plain text byte
80480e1: inc edi
80480e2: dec ecx
80480e3: jne 80480c3 <main+0x6b>
( also at https://gist.github.com/1481580)
Key scheduling is per the description given in Applied Cryptography, but in the
actual stream part, j seems to be set equal to K at the end of each iteration.
Most likely, this program was hand coded in assembler, so it may well be a mistake.
Unfortunately, my 'mad crypto skillz' don't quite yet stretch to working out what,
if any, deleterious effect this will have on the resulting stream, other than to
render it different to reference implementations of RC4. Certainly once we have
run through a single iteration, we then know what j is at the top of the algo,
but past they I am, as yet, a bit stumped.
Certainly appreciate any comments from crypto boffins, even (perhaps especially)
if it's just : "it's just broken, now stop playing with it and do something useful".
BTW, on the off chance that this does introduce a weakness, I'd appreciate it if no
one tells me what it actually is, rather spoils the fun :-)
More information about the ukcrypto