Set 2: Block crypto

This is the first of several sets on block cipher cryptography. This is bread-and-butter crypto, the kind you'll see implemented in most web software that does crypto.

This set is relatively easy. People that clear set 1 tend to clear set 2 somewhat quickly.

Three of the challenges in this set are extremely valuable in breaking real-world crypto; one allows you to decrypt messages encrypted in the default mode of AES, and the other two allow you to rewrite messages encrypted in the most popular modes of AES.

• Preliminaries
• Challenge 9: Implement PKCS#7 padding
• Challenge 10: Implement CBC mode
• Challenge 11: An ECB/CBC detection oracle
• Challenge 12. Byte-at-a-time ECB decryption (Simple)
• Challenge 13: ECB cut-and-paste
• Challenge 14: Byte-at-a-time ECB decryption (Harder)
• Challenge 15: PKCS#7 padding validation
• Challenge 16: CBC bitflipping attacks

Preliminaries

import base64
from random import randbytes, random, randint

# From pyca/cryptography
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

def xor(x, y):
    return bytes(xb^yb for xb, yb in zip(x, y))

def A(n):
    return b"A"*n

Challenge 9: Implement PKCS#7 padding

A block cipher transforms a fixed-sized block (usually 8 or 16 bytes) of plaintext into ciphertext. But we almost never want to transform a single block; we encrypt irregularly-sized messages.

One way we account for irregularly-sized messages is by padding, creating a plaintext that is an even multiple of the blocksize. The most popular padding scheme is called PKCS#7.

So: pad any block to a specific block length, by appending the number of bytes of padding to the end of the block. For instance,

YELLOW SUBMARINE

... padded to 20 bytes would be:

YELLOW SUBMARINE\x04\x04\x04\x04

---

PKCS#7 padding is defined in RFC 2315 §10.3 and is implemented, as we saw in set 1, by cryptography.hazmat.primitives.padding.PKCS7. But here's our implementation. Notice that the function always adds some padding; it's never idempotent. As a result it is unambiguously reversible.

def pad_pkcs7(text, blocksize):
    n = blocksize - len(text)%blocksize
    return text + bytes([n]*n)

print(pad_pkcs7(b"YELLOW SUBMARINE", 20))

b'YELLOW SUBMARINE\x04\x04\x04\x04'

And to remove padding:

def unpad_pkcs7(text):
    assert len(text) > 0, "invalid padding"
    n = text[-1]
    assert n > 0 and len(text) >= n and all(text[-i] == n for i in range(1, n+1)), (
        "invalid padding"
    )
    return text[:-n]

print(unpad_pkcs7(pad_pkcs7(b"YELLOW SUBMARINE", 20)))

b'YELLOW SUBMARINE'

Challenge 10: Implement CBC mode

CBC mode is a block cipher mode that allows us to encrypt irregularly-sized messages, despite the fact that a block cipher natively only transforms individual blocks.

In CBC mode, each ciphertext block is added to the next plaintext block before the next call to the cipher core.

The first plaintext block, which has no associated previous ciphertext block, is added to a "fake 0th ciphertext block" called the initialization vector, or IV.

Implement CBC mode by hand by taking the ECB function you wrote earlier, making it encrypt instead of decrypt (verify this by decrypting whatever you encrypt to test), and using your XOR function from the previous exercise to combine them.

The file here is intelligible (somewhat) when CBC decrypted against "YELLOW SUBMARINE" with an IV of all ASCII 0 (\x00\x00\x00 &c).

---

We test our implementation by decrypting the given file using OpenSSL, then re-encrypting it with our own algorithm and checking that the result matches the original.

def aes_128_ecb_encrypt(ptext, key, pad=True):
    if pad:
        ptext = pad_pkcs7(ptext, 16)
    encryptor = Cipher(algorithms.AES128(key), modes.ECB()).encryptor()
    return encryptor.update(ptext) + encryptor.finalize()

def aes_128_cbc_encrypt(ptext, key, iv=bytes(16)):
    ptext = pad_pkcs7(ptext, 16)
    ctext = bytearray()
    block = iv
    for i in range(0, len(ptext), 16):
        block = aes_128_ecb_encrypt(xor(block, ptext[i:i+16]), key, pad=False)
        ctext.extend(block)
    return bytes(ctext)

key = b"YELLOW SUBMARINE"
decryptor = Cipher(algorithms.AES128(key), modes.CBC(bytes(16))).decryptor()
ciphertext = base64.b64decode(open("10.in").read())
plaintext = unpad_pkcs7(decryptor.update(ciphertext) + decryptor.finalize())

print(aes_128_cbc_encrypt(plaintext, key) == ciphertext)

True

For good measure we implement the corresponding decryption functions.

def aes_128_ecb_decrypt(ctext, key, unpad=True):
    decryptor = Cipher(algorithms.AES128(key), modes.ECB()).decryptor()
    ptext = decryptor.update(ctext) + decryptor.finalize()
    if unpad:
        ptext = unpad_pkcs7(ptext)
    return ptext

def aes_128_cbc_decrypt(ctext, key, iv=bytes(16)):
    ptext = bytearray()
    prev_block = iv
    for i in range(0, len(ctext), 16):
        ptext.extend(xor(prev_block, aes_128_ecb_decrypt(ctext[i:i+16], key, unpad=False)))
        prev_block = ctext[i:i+16]
    return unpad_pkcs7(bytes(ptext))

# Verify that implementation matches OpenSSL
print(aes_128_cbc_decrypt(ciphertext, key) == plaintext)

True

Challenge 11: An ECB/CBC detection oracle

Now that you have ECB and CBC working:

Write a function to generate a random AES key; that's just 16 random bytes.

Write a function that encrypts data under an unknown key --- that is, a function that generates a random key and encrypts under it.

The function should look like:

encryption_oracle(your-input)
=> [MEANINGLESS JIBBER JABBER]

Under the hood, have the function append 5-10 bytes (count chosen randomly) before the plaintext and 5-10 bytes after the plaintext.

Now, have the function choose to encrypt under ECB 1/2 the time, and under CBC the other half (just use random IVs each time for CBC). Use rand(2) to decide which to use.

Detect the block cipher mode the function is using each time. You should end up with a piece of code that, pointed at a block box that might be encrypting ECB or CBC, tells you which one is happening.

---

If we pass in 3 arbitrary but identical 16-byte input blocks, then output blocks 1 and 2 will be identical iff ECB mode was used as illustrated below:

       +-----------------+-----------------+-----------------+
       |  input block 0  |  input block 1  |  input block 2  |
-------v-----------------v-----------------v-----------------v-----------
 random AAAAAAAAAA AAAAAA AAAAAAAAAA AAAAAA AAAAAAAAAA AAAAAA random pad
^-----------------^-----------------^-----------------^-----------------^
|  output block 0 |  output block 1 |  output block 2 |  output block 3 |
+-----------------+-----------------+-----------------+-----------------+

def encryption_oracle(ptext):
    input = randbytes(randint(5, 10)) + ptext + randbytes(randint(5, 10))
    if random() < .5:
        return {"mode": "ECB", "ciphertext": aes_128_ecb_encrypt(input, randbytes(16))}
    else:
        return {"mode": "CBC", "ciphertext": aes_128_cbc_encrypt(input, randbytes(16), randbytes(16))}

def cipher_mode_detection_test():
    # Return True if mode is correctly detected
    r = encryption_oracle(A(48))
    return (r["mode"] == "ECB") ^ (r["ciphertext"][16:32] == r["ciphertext"][32:48]) == 0

print(all(cipher_mode_detection_test() for _ in range(100)))

True

Challenge 12: Byte-at-a-time ECB decryption (Simple)

Copy your oracle function to a new function that encrypts buffers under ECB mode using a consistent but unknown key (for instance, assign a single random key, once, to a global variable).

Now take that same function and have it append to the plaintext, BEFORE ENCRYPTING, the following string:

Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK

Base64 decode the string before appending it. Do not base64 decode the string by hand; make your code do it. The point is that you don't know its contents.

What you have now is a function that produces:

AES-128-ECB(your-string || unknown-string, random-key)

It turns out: you can decrypt "unknown-string" with repeated calls to the oracle function!

Here's roughly how:

1. Feed identical bytes of your-string to the function 1 at a time --- start with 1 byte ("A"), then "AA", then "AAA" and so on. Discover the block size of the cipher. You know it, but do this step anyway.

2. Detect that the function is using ECB. You already know, but do this step anyways.

3. Knowing the block size, craft an input block that is exactly 1 byte short (for instance, if the block size is 8 bytes, make "AAAAAAA"). Think about what the oracle function is going to put in that last byte position.

4. Make a dictionary of every possible last byte by feeding different strings to the oracle; for instance, "AAAAAAAA", "AAAAAAAB", "AAAAAAAC", remembering the first block of each invocation.

5. Match the output of the one-byte-short input to one of the entries in your dictionary. You've now discovered the first byte of unknown-string.

6. Repeat for the next byte.

---

This might be called an incremental dictionary attack. To illustrate, imagine the block size is 3 and the unknown string is mnopqr. Then the procedure outlined above would proceed like so:

input string	lookup prefix	cipher input	ciphertext block examined	byte discovered
AA	AA_	AAmnopqr	0	m
A	Am_	Amnopqr	0	n
	mn_	mnopqr	0	o
AA	no_	AAmnopqr	1	p
A	op_	Amnopqr	1	q
	pq_	mnopqr	1	r

The length of the unknown string is obscured by the blockiness of the cipher, but we detect it by counting how many input bytes can be supplied before the returned ciphertext size increases by another block. (Though we do not check it here, the step increase in the size of the ciphertext would reveal the block size.)

The code below anticipates Challenge 14, in which a random prefix is placed before the input string. The rpl argument is the length of the random prefix and fl is the number of bytes needed to pad (or "fill") the prefix to the next block boundary; both are zero for this challenge.

detect_unknown_string_length begins in this state:

|<-                                         l ->|
|<-    rpl ->|<- fl ->|
----------------------+--------------------------
random-prefix AAAAAAA | unknown-string pad.......
----------------------+--------------------------
                      | sb (starting block)

And ends in this state:

|<-                                         l ->|
|<-    rpl ->|<- fl ->|<- isl ->|
----------------------+-------------------------+----------------
random-prefix AAAAAAA | AAAAAAAA unknown-string | new 16-byte pad
----------------------+-------------------------+----------------
                      | sb (starting block)

random_key = randbytes(16)

unknown_string = base64.b64decode("""
Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK""")

# We will discover the value of `unknown_string` without looking at
# the variable other than to use it for encryption below.

def mystery_encrypt(ptext):
    return aes_128_ecb_encrypt(ptext + unknown_string, random_key)

def detect_unknown_string_length(rpl=0):
    fl = (-rpl)%16  # fill length
    l = len(mystery_encrypt(A(fl)))
    for isl in range(1, 16):
        if len(mystery_encrypt(A(fl+isl))) > l:
            return l-rpl-fl-isl
    return l-rpl-fl-16

def solve_mystery(rpl=0):
    discovered = bytearray()
    fl = (-rpl)%16  # fill length
    sb = (rpl+fl)//16  # starting block
    isl = 15  # input string length
    bn = sb  # block number
    for _ in range(detect_unknown_string_length(rpl)):
        input_string = A(isl)
        lookup_prefix = (input_string + discovered)[-15:]
        lookup_dict = {
            mystery_encrypt(A(fl) + lookup_prefix + bytes([b]))[sb*16:(sb+1)*16] : b
            for b in range(256)
        }
        block = mystery_encrypt(A(fl) + input_string)[bn*16:(bn+1)*16]
        discovered.append(lookup_dict[block])
        isl -= 1
        if isl < 0:
            isl = 15
            bn += 1
    return bytes(discovered)

print(solve_mystery().decode("ASCII").strip())

Rollin' in my 5.0
With my rag-top down so my hair can blow
The girlies on standby waving just to say hi
Did you stop? No, I just drove by

And for further confirmation:

print(solve_mystery() == unknown_string)

True

Challenge 13: ECB cut-and-paste

Write a k=v parsing routine, as if for a structured cookie. The routine should take:

foo=bar&baz=qux&zap=zazzle

... and produce:

{
  foo: 'bar',
  baz: 'qux',
  zap: 'zazzle'
}

(you know, the object; I don't care if you convert it to JSON).

Now write a function that encodes a user profile in that format, given an email address. You should have something like:

profile_for("foo@bar.com")

... and it should produce:

{
  email: 'foo@bar.com',
  uid: 10,
  role: 'user'
}

... encoded as:

email=foo@bar.com&uid=10&role=user

Your "profile_for" function should not allow encoding metacharacters (& and =). Eat them, quote them, whatever you want to do, but don't let people set their email address to "foo@bar.com&role=admin".

Now, two more easy functions. Generate a random AES key, then:

1. Encrypt the encoded user profile under the key; "provide" that to the "attacker".
2. Decrypt the encoded user profile and parse it.

Using only the user input to profile_for() (as an oracle to generate "valid" ciphertexts) and the ciphertexts themselves, make a role=admin profile.

def encode_dict(d):
    return "&".join(f"{k}={v}" for k, v in d.items())

def decode_dict(s):
    return {p.split("=")[0]: p.split("=")[1] for p in s.split("&")}

def profile_for(address, role="user"):
    assert "&" not in address and "=" not in address, "invalid character in address"
    return {"email": address, "uid": "10", "role": role}

def encrypt_profile(p):
    return aes_128_ecb_encrypt(bytes(encode_dict(p), encoding="ASCII"), random_key)

def decrypt_profile(text):
    return decode_dict(aes_128_ecb_decrypt(text, random_key).decode("ASCII"))

admin_profile = encrypt_profile(profile_for("gregjanee@gmail.com", role="admin"))
decrypt_profile(admin_profile)

{'email': 'gregjanee@gmail.com', 'uid': '10', 'role': 'admin'}

Challenge 14: Byte-at-a-time ECB decryption (Harder)

Take your oracle function from #12. Now generate a random count of random bytes and prepend this string to every plaintext. You are now doing:

AES-128-ECB(random-prefix || attacker-controlled || target-bytes, random-key)

Same goal: decrypt the target-bytes.

Stop and think for a second.

What's harder than challenge #12 about doing this? How would you overcome that obstacle? The hint is: you're using all the tools you already have; no crazy math is required.

Think "STIMULUS" and "RESPONSE".

---

Like the random key, we assume that the random prefix is consistent. Following the cue from Challenge 11, we supply an increasing number of arbitrary, but identical bytes until we observe two identical ciphertext blocks in succession. This will require 32 bytes (for the two blocks) plus an additional 0-15 bytes to pad the remainder of the preceding random prefix:

                |<-                                      n ->|
-----------------------+------------------+------------------+----------------
...random-prefix AAAAA | AAAAAAAAAAAAAAAA | AAAAAAAAAAAAAAAA | target-bytes...
-----------------------+------------------+------------------+----------------
                         i

At which point we will have identified a clean block boundary and can proceed with the approach given in Challenge 12. (Challenge 12 asked us to check that the oracle is using ECB mode. That this approach works is evidence of that.)

random_prefix = randbytes(randint(1, 40))

def mystery_encrypt(ptext):
    # Revised definition
    return aes_128_ecb_encrypt(random_prefix + ptext + unknown_string, random_key)

def detect_random_prefix_length():
    for n in range(32, 48):
        ctext = mystery_encrypt(A(n))
        for i in range(0, len(ctext)-16, 16):
            if ctext[i:i+16] == ctext[i+16:i+32]:
                return i-(n-32)

print(solve_mystery(detect_random_prefix_length()).decode("ASCII").strip())

Rollin' in my 5.0
With my rag-top down so my hair can blow
The girlies on standby waving just to say hi
Did you stop? No, I just drove by

Challenge 15: PKCS#7 padding validation

Write a function that takes a plaintext, determines if it has valid PKCS#7 padding, and strips the padding off.

The string:

"ICE ICE BABY\x04\x04\x04\x04"

... has valid padding, and produces the result "ICE ICE BABY".

The string:

"ICE ICE BABY\x05\x05\x05\x05"

... does not have valid padding, nor does:

"ICE ICE BABY\x01\x02\x03\x04"

If you are writing in a language with exceptions, like Python or Ruby, make your function throw an exception on bad padding.

Crypto nerds know where we're going with this. Bear with us.

---

Implemented under Challenge 9 above.

Challenge 16: CBC bitflipping attacks

Generate a random AES key.

Combine your padding code and CBC code to write two functions.

The first function should take an arbitrary input string, prepend the string:

"comment1=cooking%20MCs;userdata="

... and append the string:

";comment2=%20like%20a%20pound%20of%20bacon"

The function should quote out the ";" and "=" characters.

The function should then pad out the input to the 16-byte AES block length and encrypt it under the random AES key.

The second function should decrypt the string and look for the characters ";admin=true;" (or, equivalently, decrypt, split the string on ";", convert each resulting string into 2-tuples, and look for the "admin" tuple).

Return true or false based on whether the string exists.

If you've written the first function properly, it should not be possible to provide user input to it that will generate the string the second function is looking for. We'll have to break the crypto to do that.

Instead, modify the ciphertext (without knowledge of the AES key) to accomplish this.

You're relying on the fact that in CBC mode, a 1-bit error in a ciphertext block:

• Completely scrambles the block the error occurs in
• Produces the identical 1-bit error(/edit) in the next ciphertext block.

Stop and think for a second.

Before you implement this attack, answer this question: why does CBC mode have this property?

---

The diagram below illustrates how an error (or intentional edit!) in a ciphertext block affects the subsequent decrypted plaintext block in the corresponding position by simple XOR.

So the strategy is this. If we know that a particular string appears in the plaintext, and at what position, we can exploit this knowledge by XOR-ing the string with the desired replacement string (";admin=true;" in this case) to compute a kind of delta, and then XOR the delta with the corresponding ciphertext in the preceding block to effect that change.

def fun1(userdata):
    return aes_128_cbc_encrypt(
        (
            b"comment1=cooking%20MCs;userdata="
            + userdata.replace(b";", b"%3B").replace(b"=", b"%3D")
            + b";comment2=%20like%20a%20pound%20of%20bacon"
        ),
        random_key
    )

def fun2(ctext):
    return b";admin=true;" in aes_128_cbc_decrypt(ctext, random_key)

ciphertext = fun1(b"the ;admin=true; in this string will be quoted away")

print(fun2(ciphertext))

False

The plaintext that we know appears and that we exploit is comment1=cooking%20MCs;userdata=, specifically the 12 bytes that start block 2 (%20MCs;userd).

replacement_text = b";admin=true;"
n = len(replacement_text)
target_text = b"comment1=cooking%20MCs;userdata="[16:16+n]
delta = xor(target_text, replacement_text)
new_ciphertext = xor(ciphertext[:n], delta) + ciphertext[n:]
print(fun2(new_ciphertext))

True

This is an interesting attack because the attacker does not know the key and does know the plaintext, yet can modify the plaintext in a knowing and significant way. One can imagine a webserver sending an encrypted cookie to a client, and trusting that the returned coookie must be valid because, after all, it's encrypted, right? Oops, no. Incorporating a message authentication code (MAC) would protect against this attack.