Set 2: block crypto
Set 2 is concerned with the "bread and butter" of block ciphers.
Challenge 9: PCKS#7 padding
Block ciphers are defined so that they can encrypt blocks of fixed size, usually 8 or 16 bytes. What happens if the size of the plaintext is not a multiple of the block size of the cipher? We need to pad the last bytes so that they can make a complete block.
A popular padding scheme is PCKS#7. According to this scheme, if we need to add 4 bytes at the end of the plaintext to make it even, we add 4 bytes '\x04'. You get the picture :)
In this challenge you need to implement this padding scheme. Not really challenging so I won't spend more time on this :)
Challenge 10: CBC mode
CBC mode tries to solve the predictability issue of ECB.
Let's say we have a padded plaintext to encrypt. Before encrypting, each block is XORed with the previous block of ciphertext. The first block of plaintext is encrypted with a "fake" block called the initialization vector, or IV.
When decrypting, we do the reverse; we pass the ciphertext through the decryption algorithm, and then we XOR the result with the previous ciphertext block to get back the original plaintext. The same IV should be used as a 0th block.
This means that the encryption and decryption agents need to know the same IV. Two ways are common:
- agree on a predefined IV; for instance, the challenge says to use an all-zero block.
- after encrypting a message, we append the IV at the end. The decryption algorithm will then retrieve this block.
Challenge 11: recognize ECB from CBC
Implement an encryption oracle that randomly uses ECB or CBC mode, with 0.5 probability, every time it is invoked. Before encrypting, the oracle also prepends and appends random bytes to the input text. Then, recognize which mode has been used.
We control the plaintext that is passed to the oracle; we can produce long plaintexts that are guaranteed to have at least two identical blocks, even accounting for the random bytes added by the oracle. Then, we count how many blocks are repeated more than once in the ciphertext; if there is at least one repeated block, ECB was used, otherwise, CBC was used.
In a general case in which we do not control the plaintext, this algorithm does not always work; in particular, not finding repeated blocks in the ciphertext does not give you any information on which mode was used. The encryption key is supposed to be unknown, i.e. the oracle generates it internally; so we cannot try a decryption under both modes and verify which one produces valid English text.
If the IV is appended to the ciphertext we can recognize CBC by checking whether the ciphertext is longer than its plaintext by one block. This however only works if the oracle appends the IV to the ciphertext, which is not always the case.
Challenge 12: ECB decryption (simple)
The setup: you have a function that takes a plaintext, appends a fixed text (provided in base64 encoding so you can't cheat ;)), and encrypts the result with AES ECB. The encryption key is always the same, it is generated once at the beginning.
Goal: exploit the weakness of ECB to decrypt the unknown plaintext appended at the end.
This solution proceeds in steps:
Detect the block size used by AES. Remember that when a plaintext length is not a multiple of the block size, padding must be added at the end. It follows that the ciphertext length is always the "next" multiple of the block size.
So we start by encrypting a plaintext of length 0 and storing the ciphertext length. We then encrypt progressively longer plaintexts (1 character, 2 characters, etc...) until the ciphertext length will increase. This means that we have just started a new block of the plaintext. Since we don't know the total length of the plaintext, we need to repeat this another time, i.e. add characters until the ciphertext length increases again. The difference between this ciphertext length and the first one we found is the size of a single block.
Detect that we are using ECB. Already done for a previous challenge. In a nutshell, now that we know the block size, we encrypt two identical blocks and check that the corresponding ciphertext blocks are also the same. The unknown text is added at the end, so it can be ignored.
Break it!
First acquire the number of blocks occupied by the secret string, by encrypting an empty plaintext.
Now as the title suggest we decode the secret string one byte at a time. We start by encrypting a plaintext formed by (block_size - 1) characters. Let's say block_size is 8 and we always use the 'X' character for the part of the plaintext we control.
The last byte will be occupied by the first byte of the secret string. At this point we generate all possible plaintext blocks by iterating over all possibilities for the last byte. Example: 'XXXXXXXA', 'XXXXXXXB', etc. I iterated on a list of all bytes that correspond to readable characters in ASCII.
We encrypt these blocks, until we find which one produces the same ciphertext as the "real" plaintext. We have just found the value of the first byte of the secret string!
We continue by encrypting a plaintext formed by (block size - 2) characters. We add the byte we just cracked as second to last, and then we repeat the same process with the last byte. We discover the second byte of the secret. Once we have decrypted one whole block, we repeat the same with the following blocks of the secret, since we already know the plaintext that comes before that.
Keep in mind that if there is any padding at the end, you will also "crack" that part. I added all cracked bytes to a list and then rounded it to the nearest block length to eliminate the padding.
Challenge 13: ECB cut-and-paste
Note: this is going to be extremely fun!
The setup: you have a function which creates an encrypted user profile. The profile is composed by an email address, given by the user, a numerical ID, and the role, which is always set to 'user'. This is then represented as a string and encrypted using AES in ECB mode.
Another function takes the encrypted profile and decrypts it, returning it as an object (in my code, a Python dictionary).
The goal is to use the cut-and-paste vulnerability of ECB and modify the ciphertext so that, when decrypted, the profile role is changed from 'user' to 'admin'. This is possible because in ECB each ciphertext block depends only on the corresponding plaintext block. We can "cut out" a ciphertext block and replace it with another one we produced independently.
First, we create the profile we want to escalate the privileges for. The email address is chosen so that the length of the encrypted profile is 36 bytes: the last 4 bytes, i.e. the word 'user', will then lay at the beginning of the last block. This of course assumes we know how the profile is encoded before encryption; at the very least we need to know where 'user' is written. The total size can be discovered easily.
We then create a second profile with the word 'admin' in the email address; again the size is chosen so that 'admin' lays at the beginning of a block. In this case it won't be the last block, since the rest of the email address and of the encoded profile is appended. That does not matter.
From this second profile, we take the ciphertext block with (encrypted) 'admin' in it. We replace the last ciphertext block of the first profile with this one. When we decrypt this ciphertext, we get an admin role!
enc = aes_lib.AESCipher()
p1 = CreateEncryptedProfile('[email protected]', enc)
address = 'XXXXXXXXXXadmin'
# Here we add PKCS7 padding to the rest of our fake block so it's removed when decrypting.
address += chr(11) * 11
# You can add whatever else makes sense here. Let's say the server
# does basic email validation, we want to pass a valid string.
address += '@bar.it'
p2 = CreateEncryptedProfile(address, enc)
encrypted_admin_block = p2[16:32]
fake_admin = p1[:32]
fake_admin += encrypted_admin_block
print(DecryptRole(fake_admin, enc))
Challenge 14: ECB decryption (hard)
This is similar to challenge #12, with a small addition: the oracle prepends a random count of random bytes to every plaintext before encryption. Let's see how this forces our solution to change:
Detect the block size: this is the same as before.
Detect that we are using ECB: 2 blocks with the same plaintext are not enough to guarantee 2 identical blocks of ciphertext when ECB is used: the first block may actually contain a part of the random prefix. So we generate 3 blocks: now we are sure that the last two will generate two identical blocks of ciphertext, and we can derive the block size from that.
Find the length of the prefix: this is similar to detecting the encryption mode. We start from 2 blocks of identical plaintext, and we append one byte until we get two blocks of identical ciphertext. At this point, the block size - the number of bytes we appended before succeeding is the length of the prefix. However, the resulting length is modulo 16, meaning that for a prefix of length 17 we would return 1. We account for this ambiguity later on.
Break it! This is very similar to challenge #12, with two differences:
- we pad the prefix so that its length becomes a multiple of the block size, and we ignore such bytes.
- due to the ambiguity in discovering the prefix length, if we don't succeed with length X, we try X + block size, and then X + block size * 2, etc... until we succeed in decrypting a whole set of readable characters. In a realistic scenario, the prefix length is not so huge that this becomes prohibitive.
Challenge 15: PKCS#7 padding validation
Implement a function that takes a plaintext, determines if it has valid PKCS#7 padding, and then strips it off. If the padding is not valid, an exception is thrown.
This is a preparatory step for later, so it has no intrinsic difficulty.
Challenge 16: CBC bitflipping
The idea behind the challenge is that we have to insert the 'admin=true' string in a plaintext that looks like a set of URL parameters. The final string is encrypted with AES CBC and a secret key and passed to a verifier, which decrypts it and allows us access if it finds the admin=true string.
However, non-admin users are not allowed to pass this string, because the '=' characters are quoted out (or because some application is preventing them in the first place :)). So we insert something else, say 'adminXtrue', and then do a bitflipping attack to change 'X' into '='. We achieve this by manipulating the ciphertext only.
Let's recap how ciphertext blocks are decrypted with CBC mode. We take a ciphertext block and we decrypt it through AES, then we XOR the result with the previous ciphertext block. This is applied byte-by-byte to the blocks.
Therefore, bitflipping is done by changing the ciphertext block precending the block of the character we want to change. That block is scrambled, i.e. it decrypts to something completely different than the original plaintext. So you need to ensure you can "lose" that block: in this challenge, since you control part of the string, you can simply use the prefix, or supply a long enough string to completely fill the previous block with data you can lose. This all relies on the fact that the verifier is pretty dumb: it only looks for the existence of 'admin=true', and perhaps for the correctness of the fixed prefix and suffix, but nothing else.
We have that the current value of plaintext block 2 (pt2) is given by the decryption of ciphertext block 2 (let's call it pre-pt2) XOR the ciphertext block 1 (ct1).
pt2 = pre-pt2 XOR ct1
If we focus on the single bytes we want to change:
'X' = pre-pt2 XOR ct1
Now we change ct1 into new-ct1 (which is the unknown). We obtain that:
new-pt2 = pre-pt2 XOR new-ct1
or
'=' = pre-pt2 XOR new-ct1
The quantity pre-pt2 remains unchanged, since it is the result of the decryption of the unchanged second ciphertext block. We change both equations to have pre-pt2 on the left-hand side.
pre-pt2 = 'X' XOR ct1
pre-pt2 = '=' XOR new-ct1
At this point we take the two right-hand sides:
'X' xor ct1 = '=' XOR new-ct1
and we solve for new-ct1:
new-ct1 = 'X' XOR '=' XOR ct1
So the new value of the ciphertext byte is given by the XOR of the old value, the current plaintext byte, and the "target" byte. Having computed this byte, we replace it in the right position of the ciphertext block (same offset as the byte we want to change in the plaintext) and pass the modified ciphertext to the verifier. The decryption will now contain 'admin=true' instead of 'adminXtrue' and pass the validation.