We all know that cryptographic primitives should not be implemented independently. We also know that even if we slyly reverse the order of letters in all the words of a message, move each letter alphabetically by 5 positions and dilute the text with random phrases to knock the attackers out of the way, our wonderful cipher will most likely reveal any more or less familiar a person with cryptography (and in this case a smart 12-year-old teenager will cope with the task).

However, the introduction of well-known and robust algorithms is not a panacea. Even if you take a ready-made implementation of this algorithm, generate secret keys according to all requirements and the like, anyway, you will remain potentially subject to some very effective attacks. An experienced attacker is tiny enough, it would seem, completely unrelated to the cryptosystem of information to bypass encryption.

My message is not to convince you to abandon the use of cryptographic tools on your own or to go and hire a consultant with a salary of $ 1,000 per hour whenever you think about encryption.
In part, I mean that you should never relax, you should always be alert, looking for ways that an attacker can use to get additional information about your system, and in part to the fact that Padding Oracle Attack is a cool demonstration of all this. So, let's begin.

CBC mode

CBC, or the ciphertext block chaining mode, is one of the symmetric block encryption modes using a feedback mechanism. This means that during encryption, the next plaintext block passes through the block encryption algorithm, and also additionally changes using the result of encrypting the previous block.
So, if we encrypt the sentence:

Carefully chosen length.

we get the encryption result for each block of 16 bytes, and the last block of plaintext will be supplemented in a special way (but more on that later).
In CBC, each plaintext block is added modularly two bits (xor) to the previous ciphertext block before being input to the encryption algorithm. This interdependence of blocks means that each block of ciphertext depends on each block of plaintext that has been processed so far. Moreover, a change in any byte of plaintext will lead to a change in all subsequent bytes of ciphertext (avalanche effect, aha). According to Wikipedia, CBC is "one of two symmetric block encryption modes recommended by Neil Ferguson and Bruce Schneier."
')

How block addition works (important!)

The preferred method of complementing ciphertext blocks is PKCS7. In it, the value of each byte to be padded is set equal to the number of padded bytes. So if we have a block of 12 characters, it will be supplemented by four bytes [04, 04, 04, 04] to the standard block size of 16 bytes. If the block is 15 bytes in size, it will be supplemented with one byte [01]. If the block is exactly 16 bytes in size, we add a new block consisting of [16] * 16 . (for more information, https://en.wikipedia.org/wiki/Padding_(cryptography ) #PKCS7 )

According to this method, the last block of decoded plaintext cannot end, for example, with [..., 13, 06, 05] . This means that the original ciphertext is incorrect, because there are no valid plaintext that could be converted to such a ciphertext.

The Padding Oracle Attack

It turns out that knowing the fact whether a clear text is obtained by decrypting a ciphertext with the correct addition is enough for an attacker to carry out a successful attack on encryption in CBC mode. If we can provide ciphertexts to some service, and it will return information to us whether the addition is correct, we will be able to open ANY ciphertext.

So an error that is enough to break your encryption may be some API that will return code 200 if the ciphertext we submitted is decrypted into something with the correct complement, and code 500 if not.
This is not an unlikely situation. For example, Ruby OpenSSL is subject to this problem. It is enough to use the sample code from the official documentation ( http://www.ruby-doc.org/stdlib-1.9.3/libdoc/openssl/rdoc/OpenSSL/Cipher.html#documentation ):

decipher = OpenSSL::Cipher::AES.new(128, :CBC) decipher.decrypt decipher.key = "the most secret!" decipher.iv = "also very secret" plain = decipher.update("thewrongpadding!") + decipher.final 

This code gives OpenSSL :: Cipher :: CipherError: bad decrypt , which, if not intercepted, will return a response with error 500 .

Suppose we stole ciphertext. If we can send ciphertexts and determine whether they are decrypted into messages with the correct complement, how can we use this to completely decrypt the stolen ciphertext?

Intermediate state (intermediate state)

Repeat one more time - in the CBC mode, each plaintext block is modulated by two bits (XOR) with the previous ciphertext block before going into the cipher entry. When decrypted, each ciphertext passes through the decoder and then XOR'its with the previous ciphertext block to produce plaintext.

The attack works by calculating the “intermediate state” of the decryption procedure (see the diagram) for each block of ciphertext. This is the state of the ciphertext block after decryption by the block algorithm, but BEFORE the XOR procedure with the previous ciphertext block. We will find this state, rising from the bottom of the plaintext, instead of going down through the block cipher. Also, we will not worry at all about the encryption key or block encryption algorithm.

Why is this intermediate state so important? Note:

 I2 = C1 ^ P2  P2 = C1 ^ I2 

We already know C1 because this is part of the ciphertext we have. So if we find I2, we can easily find P2 and decrypt the message.

Ciphertexts manipulation

Recall that we can feed any ciphertext to the input of the system, and the server will answer us if the correct addition is obtained after decryption. We use this fact by inputting C1 '+ C2 to the input, where C1' is a ciphertext block formed by us in a special way, and C2 is the block that we want to decrypt. By the designation C1 '+ C2, we mean simple concatenation (that is, “gluing” blocks). Denote the result of decryption as P'2 .

To begin with, we fill C1 '[1..15] with random bytes, and C1' [16] fill it with zero ( 0x00 ). Now give C1 '+ C2 server. If the server responds that the addition turned out to be correct, then we can be sure (with high probability) that P2 '[16] is 0x01 (since the addition is correct). If the server responds with an error, send a message with C1 '[16] , set to 0x01 , then to 0x02 , etc. until we get the answer we need.

(translator's note. Of course, it is possible that we get two correct answers:
1) for addition 01
2) to add 02.02 or 03.03.03…

If such a situation occurs, simply change the penultimate byte C1 'and repeat the operation again.
At the very least, we will need three attempts, but this is unlikely.
)

Now we assume that the server returned the answer 200 when C1 '[16] = 94 .

 I2 = C1' ^ P2' I2[16] = C1'[16] ^ P2'[16] = 94 ^ 01 = 95 

Hooray! We received the final byte of the intermediate state. Since C2 is taken from real ciphertext, then I2 is also identical to real one. Therefore, we can decipher the last byte of this plaintext:

 P2[16] = C1[16] ^ I2[16] = C1[16] ^ 95 

We input C1 '[16] = C1 [16] and get the last byte of the real plaintext. At this stage, we found only a placeholder, so we have to do a few more iterations of this process until we find something interesting.

We continue

We found the last byte by scrolling C1 ' until the correct complement was obtained. In this case, we can conclude that the last byte of P'2 is 0x01 . Then using P2 '[16] and C1' [16] , we find I2 [16] . Continuing this process, we find the remaining bytes of I2 and decrypt the entire block of ciphertext.

Fill C1 '[1..14] with random bytes, set C1' [15] to 0x00 , and C1 '[16] to get P2' [16] == 0x02 :

 C'1[16] = P'2[16] ^ I2[16] = 02 ^ 95 = 93 

Now we can be sure that P2 ' will end at 0x02, and therefore the only option where P2' will have the correct complement is if P2 [16] == 0x02 . We will scroll through C1 '[15] until the server gives us the code 200 . Suppose that this happened at C1 '[15] == 106 . We do again what we already know:

 I2 = C1' ^ P2' I2[15] = C1'[15] ^ P2'[15] = 106 ^ 02 = 104 

And voila! We know the penultimate byte of I2 . Therefore, we can find the penultimate byte of P2 , as we have done before:

 P2[15] = C1[15] ^ I2[15] = C1[15] ^ 104 

And so on for all 16 bytes of C2 .

Remaining blocks

The form of ciphertext blocks depends only on them and the preceding blocks. So we can apply the above algorithm to each block of ciphertext (separately from the first). The first block will be encrypted using the initialization vector ( IV ), and the IV itself is chosen randomly during the encryption procedure. Until we recognize IV , we will not be able to decipher the first block, and there is nothing that can be invented here, besides the stupid search of obvious values [0,0,0, ...] for IV and see if it turns out anyone reasonable plaintext. And to do so in the hope that the first 16 bytes will be something like " Dear Eugene! ".

This is the Padding Oracle Attack .

That's why everything related to cryptography is scary.

We know that we should not independently implement cryptographic primitives, and that we build the system on something already invented. It is easy to feel relaxed when we hide behind a strong cipher developed by experts. And as long as we keep our keys secret and do not store open texts anywhere, we feel invulnerable.

But, as you just saw, just the smallest third-party channel, a drop of information, is enough to make the system completely vulnerable. Our imaginary developer used a robust algorithm from an existing library, generated keys of the required length, and did not do anything stupid, like reusing temporary values ​​( nonce ). His only mistake was not to intercept the non-obvious exception, which led us to the possibility of understanding whether our ciphertext is decrypted into something correct.

Of course, this particular attack can be prevented by intercepting exceptions, limiting the number of requests from one IP address and monitoring suspicious requests, but this is not the point. The attackers are always sophisticated and will use even the slightest imperfection of implementation. Be careful with your cryptography, even if it is taken from a reliable source.

Thank.

The Matasano Crypto Challenges ( http://matasano.com/articles/crypto-challenges/ ), thanks to which I became interested in cryptography. Highly recommend!

_____

The translation was made with the permission of the author of the article Robert Heaton.
Source: http://robertheaton.com/2013/07/29/padding-oracle-attack/
More interesting related links:
https://class.coursera.org/crypto-preview/lecture/38