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,
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.)
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
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".
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).
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.