In previous chapter of the Crypto Series we learned some basics about XOR operation which helped us to solve first few Cryptopals challenges. Today we are going to look at AES – Advanced Encryption Standard algorithm and the simplest mode of operation – ECB. We will learn some basic theory and then apply the knowledge to solve more challenges, starting at task 1.7.
AES
AES is commonly used symmetric algorithm. Symmetric means that same key is used for both encryption and decryption. It operates on blocks of fixed size – 128 bits (or 16 bytes). Key also has defined length – it is either 128, 192 or 256 bits.
Something called the SP network is the foundation of the algorithm it takes 16 bytes of data, given key and spits out some 16B output. The inner working is quite complicated and boring, but I have some good news – we can happily ignore that! The way the network is used is much more important. In this chapter we will talk about ECB. But first something about padding…
PKCS#7 padding
What if the data are not aligned to 16B blocks? Some stuffing is needed. PKCS#7 is a common standard for such thing. First it counts how many bytes are missing from the incomplete block and then it uses bytes of that value for stuffing. If the block is properly aligned from the beginning, an entire block of padding is appended. Like this:
Raw: ninja_warrior Pad: ninja_warrior\x03\x03\x03 Raw: ABC Pad: ABC\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d Raw: YELLOW SUBMARINE Pad: YELLOW SUBMARINE\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10
If the padding is incorrect after deciphering, the message has been damaged and should be discarded. However, the reason (that padding is invalid) should not be presented to the user, because it can (at least in CBC mode) present new vulnerabilities.
ECB mode
ECB (Electronic Codebook) mode is the most basic mode. Each block of data is treated independently. See encryption and decryption diagrams below:
The block independency in ECB mode is very insecure. It essentialy means that 2 equivalent plaintext blocks are encrypted into 2 equivalent ciphertext blocks. Why is this a problem? Check this famous “securely” encrypted image!
ECB detection
ECB ciphertext will be aligned to block (16 bytes) boundary. If you have control over the plaintext and are able to observe the resulting ciphertext, submit a long string of identical characters and look for repeating 16B sequence. You can detect this phenomenon passively, if you are lucky. This is what task 1.8 is all about.
ECB chosen-plaintext attack
If you control a portion of plaintext and have access to the resulting ciphertext, you can decrypt everything after that. Consider following blocks of plaintext:
|?????????????con|trolled-plainte|xt??????????????|...
First you must discover the block alignment. This can be done by submitting a long string of identical characters and computing the offset for the repeating block. Then you align the message so one block will have exactly one unknown byte:
|?????????????AAA|AAAAAAAAAAAAAA?|????????????????|...
After encryption that block will have some specific value. Now you bruteforce the unknown byte – you are looking for the same resulting ciphertext. Use the correct byte (e.g. ‘H’) in the padding and continue in the same manner.
|?????????????AAA|AAAAAAAAAAAAAH?|????????????????|...
This is expected in tasks 2.12 and 2.14.
ECB cut-and-paste attack
Because individual blocks in ECB mode are completely independent, nothing stops you from reordering, duplicating or ommiting some of them if needed. This is what happens later in task 2.13.
I can imagine some Single Sign-On service that, upon login with your email, provides you an identifier that is created by encrypting your email and other information with AES in ECB mode. You then use the identifier for access to other services (they decrypt the data and validate the identity). The key is unknown to you, so no one should be able to craft fake valid ciphertext, right?
Consider the following cookie before encryption:
email=foo@bar.com&uid=10&role=user
where email is controlled by where email is controlled by the attacker and special characters (=, &) are properly sanitized. The attacker would obviously like very much to become the admin. If ECB mode is used, this is possible. Here are the data aligned into 16B blocks:
|email=foo@bar.co|m&uid=10&role=us|er..............|
First the cookie must be properly aligned, something like this:
|email=AAAAAAAAAA|AAA&uid=10&role=|user............|
Then the attacker creates fake block that will hold the desired value (the second block in the following diagram). The block must also have valid padding if it is designed to go to the end.
|email=AAAAAAAAAA|admin-----------|AAA&uid=10&role=|user............|
Finally, after encryption, the last block can be dropped and the crafted block is put at the end – the ECB mode allows that. The server will decrypt the payload as:
|email=AAAAAAAAAA|AAA&uid=10&role=|admin-----------|
Let’s go practical now.
1.7 – AES in ECB mode
Here we basically test the implementation works.
wget -qO- https://cryptopals.com/static/challenge-data/7.txt | base64 -d > /tmp/a
*** c = file:/tmp/a [.] c = \x120\xaa\xde>\xb30\xdb...xbb\xce\x1f\xff\x8c-\x87 *** k = 'YELLOW SUBMARINE' [.] k = YELLOW SUBMARINE *** aes = AES mode=ecb key=k ciphertext=c *** p = decrypt aes *** hd p 00000000 4927 6d20 6261 636b 2061 6e64 2049 276d |I'm back and I'm| 00000010 2072 696e 6769 6e27 2074 6865 2062 656c | ringin' the bel| 00000020 6c20 0a41 2072 6f63 6b69 6e27 206f 6e20 |l .A rockin' on | 00000030 7468 6520 6d69 6b65 2077 6869 6c65 2074 |the mike while t| ...
Just to make sure we can encrypt as well:
*** aes2 = AES mode=ecb key=k plaintext=p *** c2 = encrypt aes2 *** checksum c c2 c 448a2d178e78089da815d2fe92d240e0 c2 448a2d178e78089da815d2fe92d240e0
1.8 – Detect AES in ECB mode
wget -O /tmp/a https://cryptopals.com/static/challenge-data/8.txt
As I mentioned, same plaintext blocks will under ECB mode result into same ciphertext blocks. We can see whether it is the case in this task. Langdon has analyze command, that is designed to show basic stuff you might be interested in (e.g. length, entropy) and in the future it should support algorithm-specific analysis. If not specified, analysis is done on all variables.
*** multiline /tmp/a sample *** analyze ... [.] Analysis for sample_132: [.] Value: 0xd880619740a8a19b7840a8...33f2c123c58386b06fba186a [.] Length (B): 160 [.] Unique byte count: 84 [.] Entropy: 0.7550318303133909 [.] IOC: 0.014937106918238994 [!] Repeating patterns of blocksize=2 found, this could be XOR ciphertext with keysize=2. [!] Repeating patterns of blocksize=16 found, this could be XOR ciphertext with keysize=16. [!] Repeating patterns of blocksize=16 found, this could be AES-ECB ciphertext. ...
2.9 – Implement PKCS#7 padding
DONE! NEXT!
2.12 – Byte-at-a-time ECB decryption
Let’s skip following CBC challenges for now and finish the ECB stuff.
This task is finally about practical attack, the ECB chosen-plaintext attack. But before we solve this particular challenge, I should explain the concept of oracles.
Oracle
The problem in task 2.12 can be separated into two logical parts:
- exact instructions of the challenge – unique for this case,
- the principles of the attack (padding length detection, byte bruteforce etc.) – universal for all cases.
It does not make sense to re-implement the second part over and over for each use case. For this reason Langdon has those parts implemented independently.
The code unique for every case is called oracle and – specifically for Langdon – is written as a Python module, which can be imported upon request using oracle command. Some functions, for example ecb-chosen-plaintext relevant for this challenge, take oracle(s) as arguments and carry the entire attack. You can also run the oracle manually, using run command. This is how it could be done:
# sample oracle just reverses given data *** p = 'Hello World!' [.] p = Hello World! *** o = oracle oracles/reverse.py *** c = run o p *** c~Raw Raw: b'!dlroW olleH'
If you aim to run oracles manually, they can do basically anything, just make sure they return something. For attacks that require oracles the meaning is given and you must follow the principle. I will mention it in every case we come across.
Initially Langdon has been designed to treat oracles as completely independent programs (possibly implemented in any language), but that brought considerable performance issues. Because of that oracles are now imported directly as Python modules.
Back to the problem
According to the task, we input some string to an oracle. The oracle will append some secret data and encrypt the whole thing. Even though we do not know the encryption key, due to the fact that we have control of some portion of the data (chosen-plaintext) and it is working in ECB mode. We can break the secret.
The oracle for chosen-plaintext attack must take some payload (preferably as string of bytes, but it does not really matter) and return ciphertext as string of bytes. If these conditions are satisfied, Langdon can work with it on any real-world application.
Unfortunately, for maximum efficiency oracle codes are not quite trivial. To implement your own oracle, consider using oracle/sample.py as a starting point. Let’s see how the oracle for this challenge looks like:
self.params['secret'] = Variable(
'base64:Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK', constant=True)
self.params['key'] = Variable('YELLOW SUBMARINE', constant=True)
In OracleThread constructor, which run only once, constants should be defined. On lines 82-83 we define the secret to be appended. Variable class is not in native Python – it is implemented in Langdon and automatically deals with different data formats (like base64 in this case). You are not obliged to use it, but I find it a significant time-saver. Line 84 shows the secret key, imagine it is really unknown (in practice the oracle would probably send the data to a server and return the answer).
payload = Variable(payload)
payload = Variable(payload.as_raw() +
self.params['secret'].as_raw())
key = self.params['key']
aes = AES(mode='ecb', plaintext=payload, key=key)
aes.encrypt()
output = aes.params['ciphertext'].as_raw()
On lines 100 – 106 in OracleThread’s run method (which is expected to be called repeatedly) the secret is appended to data and the whole thing is encrypted. Finally the result is returned. The code you saw so far is the only code that needs to be re-implemented for each case, everything else is universal and contained in the Langdon itself. And how to run the whole thing?
*** o = oracle oracles/cp_12.py *** ecb-chosen-plaintext o [.] Looking for starting offset and block size... [.] Found repeating patterns. [.] Block size: 16 [.] Starting offset: 0 [.] Decryption will start at block 0. [.] Using block offset 15 [.] Plaintext: b'R' [.] Using block offset 14 [.] Plaintext: b'Ro' [.] Using block offset 13 [.] Plaintext: b'Rol' [.] Using block offset 12 [.] Plaintext: b'Roll' ... [.] Dealing with new block. [.] Using block offset 15 [.] Oracles failed to find single answer, trying next block. [.] Dealing with new block. [.] Using block offset 15 [.] No reference, this is the end. 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
2.13 – ECB cut-and-paste
For this task we will need 2 oracles – one for encryption, one for decryption. Encryption oracle takes given payload (any format), does the sanitization and data formatting and encrypts it using the unknown key, returning the ciphertext in raw format. Decryption oracle will take ciphertext (any format) and return plaintext as raw data. Oracles are feeded into ecb-cut-paste command, together with string to replace (‘user’ in this case) and desired string (‘admin’).
*** enc = oracle oracles/cp_13_e.py *** dec = oracle oracles/cp_13_d.py *** expected = 'user' [.] expected = user *** desired = 'admin' [.] desired = admin *** x = ecb-cut-paste enc dec expected desired [.] Determined blocksize: 16 [.] Determining payload offset... [.] Payload offset: 6 [.] Determining size of data between payload and expected... [.] Found difference: 13. [.] You must use payload of length 13 (or + n * 16) [.] Using b'XXXXXXXXXXXXX' as payload, len: 13 [.] Decrypted message: b'email=XXXXXXXXXXXXX&uid=10&role=user' [.] Decrypted chunks: [b'email=XXXXXXXXXX', b'XXX&uid=10&role=', b'user'] [.] Using b'XXXXXXXXXXadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0bXXX' as final payload, len: 29 [.] Decrypted message: b'email=XXXXXXXXXXXXX&uid=10&role=admin' [.] Decrypted chunks: [b'email=XXXXXXXXXX', b'XXX&uid=10&role=', b'admin'] *** run dec x email=XXXXXXXXXXXXX&uid=10&role=admin
Final ciphertext is the result of the command. If you want to validate it, you may manually execute the decryption routine. You also probably want to use email of your choice, this can be specified as last argument to the command (notice how Langdon computes proper length for you in the output above).
*** payload = 'abc@gmail.com' [.] payload = abc@gmail.com *** x = ecb-cut-paste enc dec expected desired payload [.] Determined blocksize: 16 [.] Determining payload offset... [.] Payload offset: 6 [.] Determining size of data between payload and expected... [.] Found difference: 13. [.] You must use payload of length 13 (or + n * 16) [.] Using b'abc@gmail.com' as payload, len: 13 [.] Decrypted message: b'email=abc@gmail.com&uid=10&role=user' [.] Decrypted chunks: [b'email=abc@gmail.', b'com&uid=10&role=', b'user'] [.] Using b'abc@gmail.admin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0bcom' as final payload, len: 29 [.] Decrypted message: b'email=abc@gmail.com&uid=10&role=admin' [.] Decrypted chunks: [b'email=abc@gmail.', b'com&uid=10&role=', b'admin'] *** run dec x email=abc@gmail.com&uid=10&role=admin
2.14 – Byte-at-a-time ECB decryption (harder)
This is very similar to task 2.12, but the oracle also prepends some random data. Langdon expects that and therefore the usage is the same.
*** o = oracle oracles/cp_14.py *** ecb-chosen-plaintext o [.] Looking for starting offset and block size... [.] Found repeating patterns. [.] Block size: 16 [.] Starting offset: 9 [.] Decryption will start at block 1. [.] Using block offset 15 ... 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
2.15 – PKCS#7 padding validation
In one particular type of attack, we would want to know whether the PKCS#7 padding of a plaintext is correct or not. This is natively implemented in Langdon.
Conclusion
Today we finally did some practical attacks on current cryptography. We know that ECB mode is quite insecure and we can:
- detect ECB by searching for equal 16B blocks,
- decrypt plaintext after our data if we submit data for decryption,
- re-order, add and ommit individual ECB blocks.
In the next chapter we will continue with AES and introduce CBC mode of operation.