Last night, researchers from Google released details of a new attack that they have called the Padding Oracle On Downgrade Legacy Encryption (POODLE) attack which has been assigned CVE-2014-3566.
The summary is, essentially, that SSLv3 uses a MAC-then-encrypt construction, which doesn’t authenticate the padding as it is applied on the plaintext message before padding or encryption are applied. This gives rise to a padding oracle bug, which is how BEAST worked too.
Block ciphers require plain-texts to be of a length divisible into fixed-size blocks, e.g. 128 bits in the case of AES. As normal messages don’t adhere to this (i.e. can be arbitrary in size) we use padding to ensure that the message is expanded to fit that requirement. Padding usually adds a minimum of 1 byte, and a maximum of one entire block. Its value is usually tied to the length of the padding, for example in PKCS#7 padding we would add 01 01 for two bytes, 02 02 02 for 3 bytes, 03 03 03 03 for 4 bytes, etc. However, instead of checking that all the bytes match, the SSLv3 specification states that only the last byte is to be validated. In some cases, in fact, client libraries mistakenly set the first padding bytes improperly – Oracle’s implementation has, in the past, used zeroes for all bytes but the last.
Another requirement that block ciphers don’t provide on their own is securely encrypting more than a single block with the same key. This is important, because simply transforming each block independently with a cipher (this is known as Electronic Codebook, or ECB mode) results in equal blocks encrypting to equal cipher-texts, which is bad news because this leaks information! Instead, we use different constructions to ensure safety when encrypting multiple blocks – Cipher Block Chaining (CBC) is a very common one.
In CBC, we take each previous cipher-text block and xor it with the current plaintext block before encryption. So for block 4, you take the encrypted block 3, xor it with the block 4 plaintext, then encrypt that value. The first block (block 0) has no previous cipher-text block, so we use an Initialisation Vector (IV). The IV is important, because it allows us to securely send the same full messages with the same key without their entire resulting cipher-texts being equal, as long as we don’t ever re-use an IV with the same key. Anyway, that detail isn’t important for this bug.
To decrypt a CBC message, we decrypt a block, then xor the output with the previous block’s cipher-text, i.e:
Mn = Dk(Cn) ⊕ Cn-1, where M is the message, Dk is a block decryption with a key k, C is the ciphertext, and ⊕ denotes an xor.
It turns out that this construction is malleable, meaning that an attacker can modify the cipher-text in a way that causes meaningful things to happen to the plaintext when it gets decrypted. This has been known about for a long time, and underpins many modern SSL/TLS bugs, as well as bugs in other crypto-systems.
Essentially, if you modify a block by xor’ing it with some value, the next block’s plaintext gets xor’ed with that value at the cost of the tweaked block being completely garbled. So if we want to attack block 4, we’d xor C3 with a value t, so that the decryption becomes:
Dk(C4) ⊕ (C3 ⊕ t) = M4 ⊕ t
This is really useful if you know any of the values of M4, because you can use xor to arbitrarily alter any value you know. This has a side-effect, though. Because C3 is now C3 ⊕ t, when decrypting C3 it gets utterly garbled, destroying it entirely. This is fine in some cases, for example if your target application doesn’t check block authenticity and doesn’t read (or doesn’t care about) the data in the garbled block. Another trick in this avenue is to change the IV instead, so that:
M0 = Dk(C0) ⊕ IV
becomes
Dk(C0) ⊕ (IV ⊕ t) = M0 ⊕ t
This doesn’t have the block-garbling side effect, but you can only do it on the first block. This is particularly useful in systems where cipher-text blocks are authenticated but the IV isn’t.
Anyway, you’re probably wondering what this has to do with POODLE. Remember all that padding stuff? Turns out that you can use that to work out the values of cookies.
An attacker gets the victim to visit a page controlled by them. That page includes JavaScript that repeatedly requests a target site for which we want to steal cookies from. The request body will look something like this:
POST /url\r\nCookie: name=value\r\n ... \r\n\r\nbody
Which after padding and MAC looks like this:
POST /url\r\nCookie: name=value\r\n ... \r\n\r\nbody{20-byte MAC}{pad}
The attacker controls the URL and the request body. This allows them to force the cookie into a particular position in the request. Specifically, the attacker sends requests with different length URLs and body data until the observed encrypted message grows by one block, with an earlier block having its last byte as one unknown byte of cookie. This sounds hard, but it’s as simple as knowing that the Cookie header is in a certain position and tweaking the URL to block-align it, then sending a maximum of 16 requests with incrementing POST body sizes until the output grows by one block.
The attacker knows that the final byte in the padding block will have a decimal value of 15 (i.e. 0x0F) because of the known padding size. He can then utilise the CBC malleability issue discussed above to replace the padding block with the target block (containing 1 byte of cookie at the end). Most of the time this will be rejected as invalid padding, but 1 in 256 times (on average) this will be accepted because the decrypted last byte will happen to be 15. This probability is due to the different key / IV used each time, so the cipher-text will be different (randomly) each time, so when the last block is decrypted it xors with the previous cipher-text block and has a chance of randomly producing 15 as the last byte.
That’s a bit of a challenge to follow, so let’s look at it specifically in terms of the decryption:
Mn = Dk(Cn) ⊕ Cn-1
where Cn, the final block, containing padding, is replaced with Ci:
Mn = Dk(Ci) ⊕ Cn-1
Because Ci wasn’t intended to be xor’ed with Cn-1 the output is garbage. However, because Cn-1 is random, in roughly 1/256 cases the last byte of output will be 15, leading the padding to be falsely accepted as valid. When this occurs, the attacker can deduce that:
Dk(Ci)[15] ⊕ Cn-1[15] = 15
Which, by doing a bit of bitwise algebra, gets us some plaintext:
Mi[15] = 15 ⊕ Cn-1[15] ⊕ Ci-1[15]
The above arises because Ci was xor’ed with Ci-1 when the CBC encryption occurred.
The Cn-1 and Ci-1 values are known to the attacker, so they just decrypted a single byte of the message, without knowing the key!
The attack requirements are:
- Attacker can get the client to send HTTPS requests (easy via JS)
- Attacker is in a position to modify client traffic (“Man-In-The-Middle”)
- Connection uses a block cipher suite from SSLv3
Now that last one is interesting. SSLv3 is still very widely supported by servers, but TLS is usually there too and clients should prefer it. However, due to all sorts of issues with client/server compatibility, it turns out that if a connection fails to properly negotiate TLS then in many clients it’ll downgrade to SSLv3. All an attacker needs to do, is sit in the middle and interfere with the handshake such that the client assumes there’s an incompatibility and renegotiates down to SSLv3.
There are two fixes. The first is to just turn off SSLv3, or at least disable CBC cipher suites in SSLv3 (but that leads to other problems so isn’t recommended). There is also a client-side fix for the downgrade, which is to enable the TLS_FALLBACK_SCSV flag in the client hello – this is recommended within the original Google article. However, organisations should not rely upon all clients having this patch, or that some clients will not downgrade to SSLv3 for other reasons.
Our SSL Good Practice Guide has been recommending that SSLv3 be disabled for some time now, which prevents this attack. We’ve also updated the SSL cipher suite enum tool to include a check for POODLE, so you can test your configuration.