Find the shortest way to write CipherSaber. There are several parts to this puzzle:
Arcfour is fully specified elsewhere, but for completeness, I'll describe it here.
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.
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
- To encrypt, XOR the keystream output with the plaintext
- To decrypt, XOR the keystream output with the ciphertext
CipherSaber (which is what we're solving in this question) is a variation of RC4/Arcfour in two ways:
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".
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).
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.