AES busting
AES is a symmetric key, block cipher algorithm. It is used in many common Internet protocols and operating system services, including TLS, IPSec, and file-level or full-disk encryption. Given its ubiquity, it is an important cipher to know how to use, and the principles of (in)correct use of AES transfer easily to (in)correct use of other ciphers.
Even though AES is a block cipher, it (like many other block ciphers) can be used in a way that makes it behave like a stream cipher.
AES processes blocks of 128 bits using a secret key of 128, 192, or 256 bits, with the 128-bit key being the most common because it makes encryption slightly faster and because the difference between 128- and 256-bit security is meaningless for most applications.
AES modes
| Mode | Notes |
|---|---|
| Electronic Code Book (AES-ECB) | Each 16-byte block of plaintext is encrypted independently. |
| Cipher Block Chaining (AES-CBC) | Each plaintext block gets XOR-ed with the previous ciphertext block prior to encryption. An initialization vector is used to make sure each encryption has a different ciphertext result. |
| Cipher FeedBack (AES-CFB) | The keystream is obtained by encrypting the last ciphertext produced with the block cipher. |
| Output FeedBack (AES-OFB) | The keystream is obtained by recursively encrypting the Initialization Vector. |
| Counter (AES-CTR) | The keystream is generated by encrypting a sequence of counter blocks with ECB. |
| Galois Counter Mode (AES-GCM) | A combination of Counter mode (CTR) and Authentication. Uses a Message Authentication Code (MAC) for authentication. |
| Encrypt-then-authenticate- then-translate (AEX) |
Another method for Authenticated Encryption with AES. |
Pros and cons
TL;DR: Use GCM mode for maximum security.
| Name | Pros | Cons |
|---|---|---|
| ECB | Simplest. | Weakest cipher Padding needed. |
| CBC | Each ciphertext is different => It is not possible to know if two hashed data strings originate from the same plaintext. |
Padding needed. An error in one plain text block will affect all the following blocks. Vulnerable to attacks like padding oracle attacks, chosen-plaintext attacks, and chosen-ciphertext attacks if the initialization vector isn’t changed for every encryption. The previous block must be known to encrypt the next block => No parallelisation of operations => Slow. |
| CFB | A stream cipher accepts data of any length => padding not needed. |
Each ciphertext relies on the other to be decrypted => Corrupted data cannot be recovered. No parallelisation of operations. => Slow. |
| OFB | A stream cipher accepts data of any length => padding not needed. |
The correct IV is needed to decrypt the whole thing => Corrupted data cannot be recovered. No parallelisation of operations => Slow. |
| CTR | A stream cipher accepts data of any length => padding not needed. Each counter block can be encrypted separately =>Parallelisation possible => Faster. |
Corrupted data cannot be recovered. Needs a different IV for each message to be truly secure. |
| GCM | Guarantees integrity. Pipelines and parallelisation of operations possible. Minimal computational footprint. |
Complex implementation. |
| AEX | Detects unauthorised modifications. Simpler than GCM to implement. |
Slower than GCM. |
ECB
The most basic encryption mode is the electronic codebook (ECB) mode. The message is divided into blocks and each block is encrypted separately. The problem is that if you submit the same plain text more than once, you always get the same ciphertext. This gives attackers a place to begin analysing the cipher to attempt to derive the key. ECB is using the cipher exactly as it is described without improving its security.
There is no good reason to use ECB over CBC, if both ends of the communication can support CBC. Cipher block chaining is a strong deterrent to known plain text attacks.
CBC
When using cipher block chaining (CBC) mode, each block of plaintext is XOR’d with the previous ciphertext block before being encrypted. This means there is more randomness in the final ciphertext. This is much more secure than electronic codebook mode and is the most common mode.
The only issue with CBC is the first block. There is no preceding block of ciphertext to XOR the first plaintext block with. It is common to add an initialization vector (IV) to the first block so that it has something to be XOR’d with. The initialization vector is a pseudorandom number, much like the cipher key. Usually, an IV is only used once, a \(nonce\) (Number Only used Once).
The decryption process in CBC mode is done as:
where \(nb\) is the number of blocks.
Bit-flipping attack
If you know the position of the target byte, then you can modify the corresponding ciphertext position in the previous ciphertext block. For example, if you modify a byte in the ciphertext \(C_{i-1}\), then \(P_i\) will be changed by one block since \(C_{i-1}\) only affects the plaintext \(P_i\) by \(\oplus\).
A ciphertext byte of \(C_2\) is modified: This affects the corresponding byte in the next plaintext block \(P_3\) and in the corresponding full plaintext block \(P_2\) which has the same index as the modified ciphertext which is garbage. There is an error.
An \(\text{IV}\) byte is modified: This affects only the corresponding byte in the first plaintext \(P_1\). If the target plaintext is in the first block, this will not leave a trace.
Padding oracle attack
A padding oracle is a system that behaves differently depending on whether the padding in a CBC-encrypted ciphertext is valid. You can see it as a black box or an API that returns either a success or an error value. A padding oracle can be found in a service on a remote host sending error messages when it receives malformed ciphertexts. The preferred method of padding block ciphertexts is PKCS7. In PKSC7, the value of each padded byte is the same as the number of bytes being added.
Given a padding oracle, padding oracle attacks record which inputs have a valid padding and which do not, and exploit this information to decrypt chosen ciphertext values.
Assume having intercepted a CBC encrypted ciphertext, and being able to connect with a server to pass in any ciphertext, and the server will tell us whether it decrypts to plaintext with valid padding or not. The server is used as oracle.
In CBC decryption, each ciphertext is passed through the cipher, then XORed with the previous ciphertext block to give the plaintext. The attack works by calculating the “intermediate state” of the decryption for each ciphertext. This is the state of a ciphertext block after being decrypted by the block cipher but before being XORed with the previous ciphertext block.
\(C_1\) is known already, as it is just part of the intercepted ciphertext, so if we find \(I_2\) then we can trivially find \(P_2\) and decrypt the ciphertext.
Pick a random block \(C_1\) and vary its last byte until the padding oracle accepts the ciphertext as valid. Usually, in a valid ciphertext, \(C_1[15] ⊕ X[15]\) = 01, so you’ll find \(X[15]\) after trying around 128 values of \(C1[15]\).
Find the value \(X[14]\) by setting \(C_1[15]\) to \(X[15] ⊕ 02\) and searching for the \(C_1[14]\) that gives correct padding. When the oracle accepts the ciphertext as valid, it means you have found \(C_1[14]\) such that \(C_1[14] ⊕ X[14] = 02\).
Repeat steps 1 and 2 for all 16 bytes.
In the wilderness (real digital world), implementing a padding oracle attack is a bit more complicated than that, because one has to deal with wrong guesses at step 1. A ciphertext may have valid padding not because \(P_2\) ends with a single 01 but because it ends with two 02 bytes or three 03 bytes. But that’s easily managed by testing the validity of ciphertexts where more bytes are modified.
CTR
In CTR mode, encryption XORs the plaintext and the stream taken from “encrypting” the nonce, N, and counter, Ctr. Decryption is the same, so you only need the encryption algorithm for both
encryption and decryption.
RootMe challenges
Security
Never reuse key and IV pairs. Reusing a key and IV pair in CBC produces predictable output for predictable headers. Parts of the messages that you might be inclined not to think about at all, because they are boilerplate or contain hidden structure, will become a liability; adversaries can use predictable ciphertext to learn about your keys. Reusing a key and IV in counter mode is even worse. If and adversary happens to know the plaintext, they can recover the key. Cipher block chaining mode is different because a change to a single byte of ciphertext will affect all subsequent blocks.
Keys must be drawn from good sources of randomness. The random package is a pseudo-random number generator and not even a good one at that. Pseudo-random generators are deterministic, generating numbers that appear random to humans, but are always the same given a known seed value.
Gaze into padding and its attacks. Choose a cipher mode like AES-GCM or AEX.