Yes, the title is a clickbait. In last chapter we talked about AES algorithm in its simplest mode ECB. Today we will look at another mode, namely CBC. As usual, we will apply the newly acquired knowledge in action to solve more Cryptopals challenges (starting at task 2.10).
CBC mode
In Cipher Block Chaining (CBC) mode the biggest problem of ECB, block independency, is cancelled. How does it work? When encrypting, a plaintext block is XORed with previous ciphertext block before actual AES encryption. Naturally, when decrypting, the process is reversed. See diagrams below:
For the first block, an Initialization Vector, or IV, is used. IV should be different for every message sent and in CBC mode it also must be unpredictable at encryption time (no last ciphertext block of previous message as new IV, that is prohibidado!), but after encryption it can be made public (often prepended to the final ciptertext).
You can also use CBC mode to create a fixed-length authentication code – last ciphertext block is resulting MAC (and IV can be zero).
CBC detection
Like with ECB, the length of a CBC mode ciphertext will be divisible by 16. Change of one bit in plaintext will change current and all following blocks in ciphertext. Change in ciphertext will after decryption affect the entire current block and corresponding bits of the following block, which is abused in CBC bitflipping attack.
CBC bitflipping attack
You should see the first problem with CBC if you realize two things:
- With XOR we can transform any data into arbitrary data if we control the third operand. In other words, in C = A ^ B, where we have full control over B, we can get arbitrary C for any A.
- In CBC decryption you XOR original ciphertext C1 (known) with decryption of C2 (I2 in the diagram, unknown) in order to get plaintext P2 (sometimes known).
For example, string some_garbage=XXXXXXXXXXX&admin=0 is padded and encrypted with key YELLOW SUBMARINE and IV 0xf370d32fcca1e9ac9c36605b1e4e0408 like this:
P |s o m e _ g a r b a g e = X X X |X X X X X X X X & a d m i n = 0 |10101010101010101010101010101010| C |e2fcbc5c59b705f2e428363b1b0189c7|e99e062faa57cd4624a685252a3cb4b9|84c255aa22532a4ce484e1babb5ded69|
This ciphertext is then used as a cookie. You can manually flip the last bit in the first ciphertext block. After decryption the first block will be destroyed, but the second block will have the last bit flipped. Following blocks (padding in this case) will not be affected.
C' |e2fcbc5c59b705f2e428363b1b0189c6|e99e062faa57cd4624a685252a3cb4b9|84c255aa22532a4ce484e1babb5ded69|
^^
P' |c9429c2a0bae8b9b83d30b4bf26a3f1b|X X X X X X X X & a d m i n = 1 |10101010101010101010101010101010|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^
This attack will be used in task 2.16. How to counter that? You could as server MAC the final ciphertext (compute hash of data and secret key) before sending to user. Later, if the MAC does not match, somebody altered the ciphertext.
Do not swap the encryption and MAC operations, always follow Encrypt-then-MAC rule! If you do not believe me, check Moxie Marlinspike’s post about The Cryptographic Doom Principle.
CBC padding oracle attack
As we mentioned, AES uses PKCS#7 padding to ensure that all blocks have fixed length of 16 bytes. When the padding is incorrect after deciphering, the message is damaged and should not be used as legitimate. However, the reason (that padding is invalid) should not be presented to the user. If you fail to follow this advice, bad things happen.
The CBC padding oracle attack allows the attacker to fully decrypt an encrypted message if he can use oracle to determine whether submitted ciphertext has valid padding. The plaintext will be revealed in reverse order – from the last byte of the last block.
Decryption formula for second block is P2 = AES(C2, key) ^ C1, or simply P2 = I2 ^ C1. The goal is to reveal I2 – the value right after AES decryption (referred to as Intermediate state). If I2 is known, the plaintext can be easily revealed by XORing the value with previous block of ciptertext C1 (which is known). Also, as shown in the CBC bitflipping attack, we can directly manipulate resulting plaintext bits P2 with previous ciphertext block C1.
Consider following schema of 2 successive blocks (key = ‘YELLOW SUBMARINE’, IV = 0):
P2[15] -,
P: |L o r e m i p s u m d o l o |r s i t a m e t . 0505050505| (unknown)
C: |eadcc5aa4800dff175a49cf3a0f2041d|f476548f1806681d6b265735ead1458f|
^- C1[15]
We now want to alter the C1 block to give new plaintext: ‘Lorem ipsum dolor sit amet\x05\x05\x05\x05\x01‘. The padding will now be only the last byte, \x01. This last byte is, unlike original padding, known to the attacker. Let’s call the altered C1 block C1′ and the plaintext block with altered padding P2′. The C1′ block will consist of 15 bytes of any value and the last important byte C1′[15]. This byte will be bruteforced – sent to oracle waiting for ‘No padding error’. Sometimes two valid C1′[15]s may be found, corresponding to two possible valid padding bytes (in this case \x01 and original \x05). We use the one that differs from the original ciphertext, because we do not know the corresponding original plaintext byte P2[15].
Upon discovering the byte, we can use those last bytes C1′[15] and P2′[15] to compute the last byte of the Intermediate state I2[15]:
I2[15] = C1'[15] ^ P2'[15]
In our example, correct C1′[15] value will be \x19, found by bruteforce (along with \x1d, but that is ignored, because it is in the original ciphertext). I2[15] will therefore be \x19 ^ \x01 = \x18.
Now we can finally reveal the original plaintext byte: P2[15] = C1[15] ^ I2[15]. In our example it would be \x1d ^ \x18 = \x05 – the last byte in the (padded) original plaintext.
Next byte is computed in similar way, just P2′ will end with \x02\x02 and C1′ with \x??\x1a. Why \x1a? Already known I2[15] xor new expected padding byte P2′[15]: \x18 ^ \x02.
The first block can be decrypted only if the IV is known (or can be guessed).
CBC chosen-ciphertext attack
You may think: If both key and IV must be known for both parties, why not use same value for both (and keep it secret)? Bad idea. If the attacker is able to forge a ciphertext and get it decrypted, they can reveal the IV value. Three consecutive blocks are needed. Equations (derived from the diagrams above) are:
C1 = AES(P1 ^ IV, key) C2 = AES(P2 ^ C1, key) C3 = AES(P3 ^ C2, key) P1 = AES(C1, key) ^ IV P2 = AES(C2, key) ^ C1 P3 = AES(C3, key) ^ C2
Attacker can replace blocks (C1, C2, C3) with (C1, 0, C1). This is what happens:
P1 = AES(C1, key) ^ IV P2 = AES(0, key) ^ C1 P3 = AES(C1, key) ^ 0 = AES(C1, key) P1 = P3 ^ IV IV = P1 ^ P3
Let’s go practical now.
2.10 – Implement CBC mode
wget -qO- /tmp/a https://cryptopals.com/static/challenge-data/10.txt | base64 -d > /tmp/a
Again, let’s see the implementation is working.
*** c = file:/tmp/a [.] c = \x120\xaa\xde>\xb30\xdb...V\x01|\xcb\xb1\x9et\x8da *** k = 'YELLOW SUBMARINE' [.] k = YELLOW SUBMARINE *** iv = zeros 16 *** aes = AES mode=cbc key=k iv=iv ciphertext=c *** p = decrypt aes *** p~Raw Raw: b"I'm back and I'm ringin' the bell \nA rockin' on the mike while the fly girls yell... *** aes = AES mode=cbc key=k iv=iv plaintext=p *** c2 = encrypt aes *** checksum c c2 c c56d103dd54a57bcd6378fabb960e484 c2 c56d103dd54a57bcd6378fabb960e484
2.11 – ECB/CBC detection oracle
In this task we are supposed to distinguish between ECB and CBC ciphertext. Random data of random length are both prepended and appended to provided payload. We will use the same trick as in 1.8 and take advantage of the fact that in ECB blocks of same plaintext turn into same ciphertext blocks.
*** plaintext = zeros 64
*** key = random 0 255 16
*** iv = random 0 255 16
***
*** # random paddings of random lengths
*** left_len = random 5 10
*** left_padding = random 0 255 left_len
*** right_len = random 5 10
*** right_padding = random 0 255 right_len
*** p = concat left_padding plaintext right_padding
***
*** # do the magic
*** ecb = AES mode=ecb key=key plaintext=p
*** cbc = AES mode=cbc key=key iv=iv plaintext=p
*** c1 = encrypt ecb
*** c2 = encrypt cbc
*** analyze c1
[.] Analysis for c1:
[.] Value: #\xb4&\xe6~\x06?\xabYv@\...\xca\xcb\xee\xd2\x87\xde
[.] Length (B): 96
[.] Unique byte count: 56
[.] Entropy: 0.694301363362425
[.] IOC: 0.015131578947368421
[!] 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.
*** analyze c2
[.] Analysis for c2:
[.] Value: \l1
\x05 \x9e\xf4@,\x9dH...x10
\x91i\xbby\xfd@!\x1a
[.] Length (B): 96
[.] Unique byte count: 84
[.] Entropy: 0.7889215332848191
[.] IOC: 0.0037280701754385964
2.16 – CBC bitflipping attack
For CBC bitflipping attack we need two oracles. First one takes provided user data (any format) and returns ciphertext as raw bytestring. For the purpose of the task data will be sanitized (; and =) and placed in the middle of formatted string before encryption. The second oracle will simply decrypts given ciphertext (any format) and return raw bytestring.
First the oracles are tested so we can see how the message will look.
*** e_oracle = oracle oracles/cp_16_e.py *** d_oracle = oracle oracles/cp_16_d.py *** # you need block index to alter => *** input = 'thisishalloween' [.] input = thisishalloween *** c = run e_oracle input *** p = run d_oracle c *** hexdump p 00000000 636f 6f6b 696e 6725 3230 4d43 733b 7573 |cooking%20MCs;us| 00000010 6572 6461 7461 3d74 6869 7369 7368 616c |erdata=thisishal| 00000020 6c6f 7765 656e 3b63 6f6d 6d65 6e74 323d |loween;comment2=| 00000030 2532 306c 696b 6525 3230 6125 3230 706f |%20like%20a%20po| 00000040 756e 6425 3230 6f66 2532 3062 6163 6f6e |und%20of%20bacon|
In the hexdump we can see our data starts at block #1 (counting from 0 of course) and we have complete control from block 2 onwards. We will attempt to inject malicious payload (;admin=true;) into block #3, expecting block #2 to get broken. The cbc-bitflipping command does the magic, provided encryption oracle, decryption oracle, target block and expected payload.
*** target_block = 3
[.] target_block = 3
*** payload = ';admin=true;a='
[.] payload = ;admin=true;a=
*** x = cbc-bitflipping e_oracle d_oracle target_block payload
[.] Determined blocksize: 16
[.] Trying sample payload.
[.] Payload: b'thisishalloween'
[.] Encrypted blocks: [b'\xe0T\x02\xa8\x95\x1b\xe4\x16\xb6Q\x7fC\xfe;:!', b'5\xe5\x1bn\xa9\xf5}*.\xa1\xff\x15^\x01_\xa5', b'\x83\xf7\x10\xa2\xe9"!\xe5\xben\xd5\x14\x84\xe8!Z', b'BR\xad\xfc\xeb\xe4\xc53\x9b\x11\xb5\x10lD\xeb\xff', b'xz$t\x91\xdc\xd0l\x9a"PO\xe0\xc8\x1f0', b'\xb9\xc4\x95L\r\xf3\xf3\xd8\x0f\xf2\xf2[\xfc\x18{\xe4']
[.] Decrypted: b'cooking%20MCs;userdata=thisishalloween;comment2=%20like%20a%20pound%20of%20bacon'
[.] Decrypted blocks: [b'cooking%20MCs;us', b'erdata=thisishal', b'loween;comment2=', b'%20like%20a%20po', b'und%20of%20bacon']
[.] New blocks: [b'\xe0T\x02\xa8\x95\x1b\xe4\x16\xb6Q\x7fC\xfe;:!', b'5\xe5\x1bn\xa9\xf5}*.\xa1\xff\x15^\x01_\xa5', b"\x9d\xa4D\xa3\xe9'y\xb4\xfe+\xd1\n\xd7\xe5jT", b'BR\xad\xfc\xeb\xe4\xc53\x9b\x11\xb5\x10lD\xeb\xff', b'xz$t\x91\xdc\xd0l\x9a"PO\xe0\xc8\x1f0', b'\xb9\xc4\x95L\r\xf3\xf3\xd8\x0f\xf2\xf2[\xfc\x18{\xe4']
*** hd x
00000000 636f 6f6b 696e 6725 3230 4d43 733b 7573 |cooking%20MCs;us|
00000010 6572 6461 7461 3d74 6869 7369 7368 616c |erdata=thisishal|
00000020 bb3f 6a25 a4db 810b 2671 e106 8f84 8700 |.?j%....&q......|
00000030 3b61 646d 696e 3d74 7275 653b 613d 3b61 |;admin=true;a=;a|
00000040 756e 6425 3230 6f66 2532 3062 6163 6f6e |und%20of%20bacon|
3.17 – CBC padding oracle
First select one of the following strings at random and encrypt it:
cat << EOF | shuf -n 1 | base64 -d > /tmp/a MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc= MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic= MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw== MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg== MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA== MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw== MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8= MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g= MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93 EOF # create ciphertext cat << EOF | ./langdon key = random 0 255 16 iv = random 0 255 16 a = file:/tmp/a export key /tmp/key export iv /tmp/iv aes = AES mode=cbc key=key iv=iv plaintext=a c = encrypt aes export c /tmp/c EOF
Now we need an oracle that takes ciphertext (any format), attempts to decrypt it and returns whether the decryption has been successful. The cbc-padding command used for the attack converts the oracle output to boolean, therefore it is up to you what the oracle exactly returns. In implementation for this specific task, oracle returns correctly decrypted data (as bytestring) or empty bytestring.
*** c = file:/tmp/c [.] c = (*G\xcdC\xdf\x86q\xf2\x9...\xdc\x84\xbd;zP\xb6v\xae *** #o = cbc/cryptopals_17.sh *** o = oracle oracles/cp_17.py *** p = cbc-padding c o [.] Previous block: 02 6b 14 f1 de a4 83 e3 8b da 11 dc 28 64 b2 fd [.] Actual block: 1a 0c 80 0d 06 f3 5a dc 84 bd 3b 7a 50 b6 76 ae [.] Dealing with byte #15 (ae) [.] Found valid padding byte: 249 [.] New block plaintext: b'\x05' [.] Dealing with byte #14 (76) [.] Found valid padding byte: 181 [.] New block plaintext: b'\x05\x05' ... *** p~Raw Raw: b'\xd4"\xad\xf4fC\x969\x03\xcd\x8a\x80c\x00\xfd2 hat with a souped up tempo'
The attack was partially successful, we have some data. First block is broken though, and this is because of unknown IV (0 is used by default). If you know the IV used, you can specify it manually:
*** iv = file:/tmp/iv
[.] iv = \xe4\x12\x9d\xc4Vu\xd7Wg\xed\xeb\xa0
i\x9aZ
*** #o = cbc/cryptopals_17.sh
*** o = oracle oracles/cp_17.py
*** p = cbc-padding c o 16 iv
[.] Previous block: 02 6b 14 f1 de a4 83 e3 8b da 11 dc 28 64 b2 fd
[.] Actual block: 1a 0c 80 0d 06 f3 5a dc 84 bd 3b 7a 50 b6 76 ae
[.] Dealing with byte #15 (ae)
[.] Found valid padding byte: 249
[.] New block plaintext: b'\x05'
...
*** p~Raw
Raw: b'000006And a high hat with a souped up tempo'
4.27 – Key=IV key recovery
Next CBC task is far away in Set 4. We will need an oracle now, this time taking ciphertext (any format) and returning corresponding plaintext as raw bytestring. First let’s create a ciphertext with an ‘unknown’ key.
*** p = ‘Illuminati, you’ve come to take control. You can take my heartbeat, but you can’t break my soul. We all shall be free.’
[.] p = b”Illuminati, you’ve com…. We all shall be free.”
*** key = ‘YELLOW SUBMARINE’
[.] key = YELLOW SUBMARINE
*** iv = key
*** aes = AES mode=cbc key=key iv=iv plaintext=p
*** c = encrypt aes
Can we somehow get the value ‘YELLOW SUBMARINE’ from the ciphertext and oracle?
*** o = oracle oracles/cp_27.py *** revealed_key = cbc-chosen-ciphertext o c [.] Decrypted: b"Illuminati, you've come to take control. You can take my heartbeat, but you can't break my soul. We all shall be free.\n\n\n\n\n\n\n\n\n\n" [.] Fake: b'\x9b\xf4\xe0\xc9\xee\xae\x84\x80M\x80\x15\x05~Xd\x07\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x9b\xf4\xe0\xc9\xee\xae\x84\x80M\x80\x15\x05~Xd\x07' [.] Decrypted: [b"Illuminati, you'", b'\xf6\x04\x87mo\xda\xfd,\xe23?T\x9fV\xa0E', b'\x10) 9">N2!+aa+&;b'] *** hexdump revealed_key 00000000 5945 4c4c 4f57 2053 5542 4d41 5249 4e45 |YELLOW SUBMARINE|
Conclusion
We are now familiar with AES CBC mode; safer than ECB, but far from perfect. We demonstrated three practical attacks on CBC mode and now you know that:
- a block can be sacrificed in order to alter the following block, use Encrypt-then-MAC approach to counter it,
- do not tell anyone that padding is invalid,
- the IV should not be same as the key or predictable.
In the next chapter we will take a look at AES in CTR mode.