Challenge 18: Implement CTR, the stream cipher mode

The string:

L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==

... decrypts to something approximating English in CTR mode, which is an AES block cipher mode that turns AES into a stream cipher, with the following parameters:

  key=YELLOW SUBMARINE
  nonce=0
  format=64 bit unsigned little endian nonce,
         64 bit little endian block count (byte count / 16)

CTR mode is very simple.

Instead of encrypting the plaintext, CTR mode encrypts a running counter, producing a 16 byte block of keystream, which is XOR'd against the plaintext.

For instance, for the first 16 bytes of a message with these parameters:

keystream = AES("YELLOW SUBMARINE",
                "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00")

... for the next 16 bytes:

keystream = AES("YELLOW SUBMARINE",
                "\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00")

... and then:

keystream = AES("YELLOW SUBMARINE",
                "\x00\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00")

CTR mode does not require padding; when you run out of plaintext, you just stop XOR'ing keystream and stop generating keystream.

Decryption is identical to encryption. Generate the same keystream, XOR, and recover the plaintext.

Decrypt the string at the top of this function, then use your CTR function to encrypt and decrypt other things.

This is the only block cipher mode that matters in good code. Most modern cryptography relies on CTR mode to adapt block ciphers into stream ciphers, because most of what we want to encrypt is better described as a stream than as a sequence of blocks. Daniel Bernstein once quipped to Phil Rogaway that good cryptosystems don't need the "decrypt" transforms. Constructions like CTR are what he was talking about.

from base64 import b64decode

from libmatasano import encrypt_aes_128_block, bxor

For people that never saw the flow chart for CTR mode:

def aes_128_ctr_keystream_generator(key, nonce):
    counter = 0
    while True:
        to_encrypt = (nonce.to_bytes(length=8, byteorder='little')
                     +counter.to_bytes(length=8, byteorder='little'))
        keystream_block = encrypt_aes_128_block(to_encrypt, key)
        # equivalent to "for byte in keystream_block: yield byte"
        # for the "yield" keyword in Python,
        # see https://docs.python.org/3/tutorial/classes.html#generators
        yield from keystream_block

        counter += 1

def aes_128_ctr_transform(msg, key, nonce):
    '''does both encryption (msg is plaintext)
    and decryption (msg is ciphertext)'''

    keystream = aes_128_ctr_keystream_generator(key, nonce)
    # by default our 'bxor' function uses the longest string,
    # but here the keystream is of unlimited size
    # (bytes are generated on-the-fly)
    # so I added a parameter to be able to switch to
    # "take the shortest string"
    return bxor(msg, keystream, longest=False)

ctxt = b64decode('L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==')
aes_128_ctr_transform(ctxt, key=b'YELLOW SUBMARINE', nonce=0)

b"Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby "

Note: the comment about CTR mode being the only block cipher mode that matters in good code is a bit outdated nowadays as new modes are being used, in particular what we call authenticated encryption modes (see Wikipedia:Authenticated encryption). However one of the most used such modes is GCM wich is very close to CTR.

But another authenticated encryption mechanism is what we call encrypt-then-mac and it allows to use even CBC mode without the issues we saw in challenge 17.