6.857: Computer and Network Security

Successful Teams (in chronological order)

Source code

Here's our implementation of the Advanced Bit-Diddling Standard. The server will accept any key that encrypts 100 random plaintexts to the same ciphertexts as the secret key.

def xor(s1, s2):
    """Return s1 XOR s2. Truncates the longer input."""
    return ''.join(chr(ord(a) ^ ord(b)) for (a, b) in zip(s1, s2))

def permutebits(m, p):
    """Permute each bit in m according to the string p, which encodes an
    8*len(m)-long permutation."""
    out = ""
    for byte in xrange(len(m)):
        v = 0
        for bit in xrange(8):
            # Fetch the appropriate index from the permutation.
            i = ord(p[8 * byte + bit])
            # Find the message byte and shift it down to extract the bit
            # we want.
            b = (ord(m[i / 8]) >> (7 - (i % 8))) & 1
            # Add this as the next bit to v.
            v = (v << 1) + b
        out += chr(v)
    return out

def diddle_bits(data, p, S, rounds):
        l = data[0:8]
        r = data[8:16]
        for i in xrange(rounds):
            rp = permutebits(r, p)
            rS = ''.join(S[ord(b)] for b in rp)
            (l, r) = (r, xor(l, rS))
        return l + r

Interface

This web server exposes the following interface. You can access it with either GET or POST; GET will be demonstrated for simplicity.

Don't forget that there's a Python client library on the class website, which takes care of all of the below for you.

Key Generation

Each key in the database is associated with a team label and a number of rounds. Make a call to /ps2/genkey with parameters team and rounds (for the problem set, the number of rounds should be 2 or more). For instance, if team 0 wanted to attempt cracking 3 rounds, they would access http://6.857.scripts.mit.edu/ps2/genkey?team=0&rounds=3.

The output is of the form Key <b>100</b> generated.

Encryption

All data is encoded in uppercase hexadecimal. For instance, to transmit the binary string 0001001000111111, you would encode it as 123F. (This is the encoding of Python's base64.b16encode and base64.b16decode, for instance.) Bits and bytes are big-endian, i.e., the first bit is the highest-order bit (0 in this example), and the first byte is the highest-order byte (0x12).

Send a request to /ps2/encrypt with parameters key, the key ID you specified in the previous round, and data, the block you want encrypted. Each block should be 128 bits, so therefore a properly-encoded bock is 32 hexadecimal digits.

For instance, to encrypt the zero block with the key that team 0 previously generated, access http://6.857.scripts.mit.edu/ps2/encrypt?key=100&data=00000000000000000000000000000000.

The output will just be the encrypted block, in the same hexademical encoding.

You can only encode 1000 plaintexts with the same key. After this point you will need to generate a new key.

Guessing the key

Encode your p and S arrays with one byte per cell and encode them in the same manner as above (so if p = [15, 3, 5...], you'd use 0F0305...). Pass the parameters p and S (note that S is upper-case), along with key to /ps2/guess.

If you guess wrong, the key will no longer be valid for encryption.