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.
