CipherSaber encryption

Question

Implement a CipherSaber encryption program, as described below. Guidelines:

• The smallest entry, in bytes, wins.
  • However, in a departure from code-golf norms, you are welcome to post interesting entries, even if they aren't serious golf entries.
• An entry would typically be a program that takes the plaintext from standard input, and writes the ciphertext to standard output, with the key specified (by the user) in some way you prefer.
  • However, if you wish to implement this as a procedure, that is fine too.
• The IV must come from a cryptographically secure pseudorandom number generator. If your language doesn't support that, choose a different one. ;-)
• Please do not use any crypto-specific libraries, system calls, or instructions (other than the PRNG, as stipulated above). Of course, generic low-level bitwise operations are okay.

CipherSaber is a variant of RC4/Arcfour, so I'll start by describing the latter, then the changes CipherSaber makes thereto.

0. RC4/Arcfour

Arcfour is fully specified elsewhere, but for completeness, I'll describe it here. (In case of any discrepancies between the Internet-draft and this description, the former is normative.)

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

1. CipherSaber

CipherSaber (which is what we're implementing 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 shuffling loop of the key setup stage of RC4 is run a user-specified number of times. The value of j should be retained between iterations.

2. Test vectors

Here are some test vectors you can use to test your programs. Furthermore, squeamish ossifrage created a CipherSaber encryption & decryption tool that you can use to validate your results.

You only need to implement the encryption program. You do not need to supply the decryption program, but your encryption program's output must roundtrip correctly to the original input when processed with a correctly-implemented decryption program using the correct key.

Answer 1

Pyth, 100 bytes

$import os$KsM$os.urandom(10)$JuuXN@LN,T=+Z+@NT@+CMzKT)bGQU=b256=Z0sCM+K.exCb@=XJ=N@LJ,hk=+Z@Jhk)sNw

This script uses the $ command, which allows executing Python code. To prevent executing malicious code on the server, the this command is disabled in the online compiler. You have to run it with the off-line compiler which you can find here.

The input is in the format:

secret key
5 (number of repeats)
secret message

The program outputs the encrypted string, which might contain unprintable chars. If you want to verify it using the CipherSaber Encryption & Decryption Tool, you can use the following code, which converts the string to a series of hexadecimal digits.

$import os$KsM$os.urandom(10)$JuuXN@LN,T=+Z+@NT@+CMzKT)bGQU=b256=Z0         
jdm.[2.HCd`0
sCM+K.exCb@=XJ=N@LJ,hk=+Z@Jhk)sNw

Pyth doesn't support cryptographically secure pseudorandom numbers and importing them from Python costs 25 bytes. A shorter code, which uses Pyth's/Python's normar pseudorandom-number generator and also works in the online compiler is:

KmO=b256TJuuXN@LN,T=+Z+@NT@+CMzKT)bGQUb=Z0sCM+K.exCb@=XJ=N@LJ,hk=+Z@Jhk)sNw

Try it online: returning a string or a series of hexadecimal digits

The code is nothing special. Just a lot of dirty assignments and immediate reuses of computed results and applying twice the list-swap trick.

Explanation:

                                  implicit: z = 1st input (= key string)
                                  Q = 2nd input (number of repetitions)
$import os$KsM$os.urandom(10)$
$import os$                       import Python's os module
              $os.urandom(10)$    create 10 cryptographically secure 
                                  pseudo-random bytes
            sM                    convert them to ints
           K                      store them in K

JuuXN@LN,T=+Z+@NT@+CMzKT)bGQU=b256
                             =b256assign b with 256
 u                         QUb    start with G = [0, 1, ..., 255], 
                                  evaluate the following expression Q times and
                                  update G with the result each time:
  u                      bG         start with N = G, 
                                    for each T in [0, 1, ..., 255] evaluate the
                                    following expression and update N each time:
                   CMz                convert key to list of ints
                  +   K               extend it with K
                 @     T              take the Tth element (modulo length)
              @NT                     take the Tth element of N
             +                        add these two values
           +Z                         add Z (with is initially 0)
          =                           and update Z with the result
        ,T  Z                         make the pair of indices [T, Z] 
     @LN                              look-up their values in N
   XN                   )             and switch these two values in N
J                                 assign the result (the key setup) to J

=Z0                               set Z to 0

sCM+K.exCb@=XJ=N@LJ,hk=+Z@Jhk)sNw 
                                w read a string from input (message)
     .e                           map each index k, char b in message to:
                         @Jhk       look-up the (k+1)th element in J
                      =+Z           add it to Z and update Z
                   ,hk  Z           make the pair of indices [k+1,Z]
                @LJ                 look-up their values in J
              =N                    assign the result to N
            XJ N             )      swap these values in J
           =                        and update J with the result
          @  J                sN    take the sum(N)th element of J
        Cb                          convert b to int
       x                            bitwise xor of these two elements
   +K                             insert K at the beginning
 CM                               convert each element to char
s                                 sum them (generate a string)
                                  implicitly print

Answer 2

Python 2 - 373 350 326 317 bytes

Pyth possibly coming later. Defines one function, c(p,d,r,m) which takes byte lists for passphrase and data, and int for repetitions and mode which encrypts when 1 and decrypts when 0. This is because the only difference in them is dealing with the IV. Returns byte list.

import os
B=256
def c(p,d,r,m):
    if m:v=map(ord,os.urandom(10))
    else:v,d=d[:10],d[10:]
    p+=v;S=range(B);T=(p*B)[:B];j=0;exec"for i in range(B):j=(j+S[i]+T[i])%B;S[i],S[j]=S[j],S[i]\n"*r;o=[];i=j=0
    for b in d:i=-~i%B;j=(j+S[i])%B;S[i],S[j]=S[j],S[i];k=(S[i]+S[j])%B;o+=[S[k]^b]
    return v+o if m else o

Here is some test code / Helper functions:

phrase = "hello"
text = "Mary had a little lamb, little lamb, little lamb"
N = 5

def make_bytes(string):
    return map(ord, string)

def make_string(bytes):
    return "".join(map(chr, bytes))

def make_hex(bytes):
    return " ".join("%02x" % i for i in bytes)

def from_hex(hex_str):
    return [int(i, 16) for i in hex_str.split()]

cipher = c(make_bytes(phrase), make_bytes(text), N, 1)
print make_hex(cipher)
plain = c(make_bytes(phrase), cipher, N, 0)
print make_string(plain)

Answer 3

Ruby - 263 chars

This is my Ruby answer to the original question on stackoverflow back in 2010! It is a encoder and decoder all in one program

Parameters are:
e or d (for encode or decode)
key
number of times

$ ruby saber.rb e gnibbler 10 < in.txt | ruby saber.rb d gnibbler 10

o,k,l=ARGV;print o<'e'?(v=STDIN.read(10))*0:v=(0..9).map{rand(256).chr}.join;j=0;E=255
S=Array 0..255;(S*l.to_i).each{|i|j=j+S[i]+((k+v)*E)[i].ord&E;S[i],S[j]=S[j],S[i]};i=j=0
STDIN.each_byte{|c|i=i+1&E;j=j+S[i]&E;S[i],S[j]=S[j],S[i];print (c^S[S[i]+S[j]&E]).chr}

Answer 4

C, 312 bytes

Accepts a key and key mixing iteration count on the command line, then encrypts everything on stdin to stdout. This uses the BSD/Darwin library function arc4random(), which is a PRNG based on RC4. It automatically seeds itself, so the results will be different every time.

unsigned char n,i,j,q,x,t,s[256],k[256];main(int c,char**v){for(strcpy(k,v[1]),n=strlen(k);x<10;x++)putchar(k[n++]=arc4random());do{s[i]=i;}while(++i);for(x=atoi(v[2]);x--;)do{t=s[i];s[i]=s[j+=s[i]+k[i%n]];s[j]=t;}while(++i);for(;(c=getchar())>0;){q+=s[++i];t=s[i];s[i]=s[q];s[q]=t;t=s[i]+s[q];putchar(c^s[t]);}}

Tidier version:

unsigned char n,i,j,q,x,t,s[256],k[256];
main(int c,char**v) {
  for (strcpy(k,v[1]),n=strlen(k);x<10;x++) putchar(k[n++]=arc4random());
  do {
    s[i]=i;
  }
  while(++i);
  for (x=atoi(v[2]);x--;) do {
    t=s[i];
    s[i]=s[j+=s[i]+k[i%n]];
    s[j]=t;
  }
  while (++i);
  for (;(c=getchar())>0;) {
    q+=s[++i];
    t=s[i];
    s[i]=s[q];
    s[q]=t;
    t=s[i]+s[q];
    putchar(c^s[t]);
  }
}

Example:

$ echo -n 'Ciphersaber' | ./csgolf 'hello' 20 | xxd -p
0f6257c330e5e01c3eab07bc9cb4ee4c3eaa514a85

Answer 5

Python - 266 chars

This is my Python answer to the original question on stackoverflow back in 2010! It is a encoder and decoder all in one program

Parameters are:
e or d (for encode or decode)
key
number of times

$ python saber.py e gnibbler 10 < in.txt | python saber.py d gnibbler 10

This version attempts to merge the 2 loops of the rc4 into one (saves 11 bytes so far...)

import os,sys;X,Y=sys.stdin.read,os.write;_,o,k,l=sys.argv;p='d'<o
V=(X,os.urandom)[p](10);Y(1,V*p);E,S=255,range(256)
for q in S*int(l),X():
 t=q<'';j=0;i=-t
 for c in q:i=i+1&E;j=j+S[i]+t*ord(((k+V)*E)[i])&E;S[i],S[j]=S[j],S[i];t or Y(1,chr(ord(c)^S[S[i]+S[j]&E]))