3
$\begingroup$

I am trying to understand how the POODLE attack would actually be implemented. In the original security advisory from Möller, Duong and Kotowicz [POODLE 14] the following example is presented:

Assume that each block $C$ has 16 bytes, {..}. The MAC size in SSL 3.0 CBC cipher suites is typically 20 bytes, so below the CBC layer, an encrypted POST request will look as follows:

POST /path Cookie: name=value... \r\n\r\nbody || 20-byte MAC || padding

Then the authors go on explaining how one can decrypt a previously unknown byte of the cookie:

The attacker then replaces $C_n$ by $C_i$ and forwards this modified SSL record to the server.

I understand it so far. The only problem I have is this, since the padding is 1 to L bytes long (where L is our block size in bytes, 16 in our example) we only can decrypt bytes with values between 1 and L right ? Let's say the last byte in the block $C_i$ equals to 0x0020, how would I decrypt it ?

$\endgroup$
2
$\begingroup$

For a CBC mode cipher, which is what POODLE applies to, you don't encrypt or decrypt individual bytes, but rather blocks, formed by adding padding to the actual data bytes. For encryption in general every byte can be any value 0 to 255, and the SSL spec allows the padding_length byte to be almost any value, but most if not all implementations only use 0 to L-1. (Not 1 to L; a different common padding scheme, PKCS#5/7, does use 1 to L.) SSL/TLS uses MAC-then-encrypt (see a hundred other questions why this turned out to be not the best choice) so actually user-data plus HMAC is padded and then CBC-encrypted, as shown by the line you posted: user data consisting of POST /path cookies etc, then (20-byte) MAC, then padding.

CBC mode encrypts a block at a time after XORing the plaintext block with the previous ciphertext block, or for the first block with the IV. Similarly when decrypting it XORs the decrypted block with the previous ciphertext block or IV to produce the plaintext. The diagram in Wikipedia shows this in detail.

HOW POODLE BITES. You omitted most of the paper's explanation:

The attacker controls both the request path and the request body, and thus can induce requests such that the following two conditions hold:
● The padding fills an entire block (encrypted into Cn).
● The cookies’ first as-of-yet unknown byte appears as the final byte in an earlier block (encrypted into Ci).
The attacker then replaces Cn by Ci and forwards this modified SSL record to the server. Usually, the server will reject this record, and the attacker will simply try again with a new request. Occasionally (on average, once in 256 requests), the server will accept the modified record, and the attacker will conclude that DK(Ci)[15] ⊕ Cn-1 [15] = 15, and thus that Pi[15] = 15 ⊕ Cn-1 [15] ⊕ Ci-1 [15]. This reveals the cookies’ first previously unknown byte. The attacker proceeds to the next byte by changing the sizes of request path and body simultaneously such that the request size stays the same but the position of the headers is shifted , continuing until it has decrypted as much of the cookies as desired. The expected overall effort is 256 SSL 3.0 requests per byte.

When Cn is replaced by Ci satisfying the two stated conditions, the receiver first decrypts, and unpads, the received message. There are two possibilities:

  • If the result of CBC decryption has anything other than 15 in the last byte, the unpadding either fails entirely or yields a result that fails MAC verification (with overwhelming probability), producing an error alert that the attacker can observe.
  • If the result of CBC decryption does have 15 in the last byte, the receiver doesn't detect any error and continues with the session. The attacker now knows that the last byte from the previous ciphertext block (Cn-1[15]) XORed with byte 15 of the block that was encrypted to form Pi (Dk(Ci)[15]) is 15 and also knows that Dk(Ci)[15] was computed as Pi[15] XOR Ci-1[15]. Combining these allows the attacker to compute Pi[15] with the formula shown.

Replace 16 and 15 by 8 and 7 for an 8-byte block cipher, which for SSLv3 was triple-DES, DES, RC2 or IDEA. But almost nobody implemented IDEA and RC2, and DES has been insecure and deprecated or prohibited for over a decade.

The attacker now knows a cookie byte (or bite?); rinse and repeat, or as a classic snack advertisement had it, "munch all you want, we'll make more". EDIT: Specifically, to get the second cookie byte, the attacker adjusts the URL path that it causes the browser to request, so that the second cookie byte now falls at Pi[15], satisfying the second assumption. It repeatedly requests this URL until it gets the Pn'[15]=15 case for the second cookie byte. Then it adjusts the path so that the third cookie byte falls at Pi[15] and is recovered, then the fourth, and so on. Remember the browser sends the same cookie(s) on all requests to the same origin across multiple connections, until directed to change it(them), typically when the user logs-out or after a long period of time like an hour; this attack likely takes less than 50*128*0.1sec = 10 minutes. This does assume that the other data in the request headers like user-agent: and accept-language: etc don't vary in length (or vary only by a multiple of the blocksize 16, less likely); in practice on most browsers these are fixed except for Host: and that is fixed by the attack. It doesn't matter the key (and IV) changes on each connection, because we don't try to recover any of those keys, only an unchanging part of the plaintexts.

$\endgroup$
  • $\begingroup$ Thank you for the explanation, but you missed what I was trying to ask a little bit, maybe I wasn't clear enough. What I didn't understand was how "rinse and repeat" would help, since I assumed the encrypted ciphertext would stay the same, but since the connection would be closed due to the padding error we will get different IVs and different keys for the next connection. If you could mention this in your answer I would gladly accept it. $\endgroup$ – rtur Nov 21 '15 at 8:47
  • $\begingroup$ @rtur done (but comment too short) $\endgroup$ – dave_thompson_085 Nov 21 '15 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.