public
Created

CipherSaber code golf

  • Download Gist
gistfile1.mkd
Markdown

Find the shortest way to write CipherSaber. There are several parts to this puzzle:

RC4/Arcfour

Arcfour is fully specified elsewhere, but for completeness, I'll describe it here.

Key setup

Set up two arrays, S and S2, both of length 256, where k_1 is the first byte of the key, and k_n is the last.

S = [0, ..., 255]
S2 = [k_1, ..., k_n, k_1, ...]

(S2 is filled with the bytes of the key, again and again, until all 256 bytes are filled up.)

Then, initialise j to 0, and shuffle 256 times:

j = 0
for i in (0 .. 255)
    j = (j + S[i] + S2[i]) mod 256
    swap S[i], S[j]
end

This completes key setup. The S2 array is no longer used here, and can be scrubbed.

Cipher stream generation

Initialise i and j to 0, then generate the key stream as follows:

i = 0
j = 0
while true
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap S[i], S[j]
    k = (S[i] + S[j]) mod 256
    yield S[k]
end

Encrypting/decrypting data

  • To encrypt, XOR the keystream output with the plaintext
  • To decrypt, XOR the keystream output with the ciphertext

CipherSaber

CipherSaber (which is what we're solving in this question) is a variation of RC4/Arcfour in two ways:

10-byte IV/nonce

When encrypting a message, 10 random bytes should be obtained, such as via /dev/urandom, and be written into the first 10 bytes of the encrypted output. When decrypting a message, the first 10 bytes of the input is the IV used to encrypt it.

The RC4/Arcfour key setup stage is run with passphrase || IV as the key, where passphrase is the user-specified passphrase, IV is as described above, and || is concatenation. So, a passphrase of "Hello, world!" and an IV of "supercalif" (however unlikely that is :-P) would result in a key of "Hello, world!supercalif".

Multiple iterations of key setup

In order to help prevent the vulnerability that made WEP encryption completely broken, the key setup stage of RC4 is run a user-specified number of times. The value of j should be retained between iterations.

Because of this variation on the key setup, using your system's RC4 is unlikely to work (although kudos to you if you pull it off :-D).

Test vectors

Here are some test vectors you can use to test your programs. I can post some more if people want more data to test with.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.