• gistfile1.mkd

Find the shortest way to write [CipherSaber](http://en.wikipedia.org/wiki/CipherSaber). There are several parts to this puzzle:

## RC4/Arcfour

[Arcfour is fully specified elsewhere](http://www.mozilla.org/projects/security/pki/nss/draft-kaukonen-cipher-arcfour-03.txt), 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](http://www.cypherspace.org/adam/csvec/) you can use to test your programs. I can post some more if people want more data to test with.