ROBOT: Bleichenbacher returns
“Those who do not remember the past are condemned to repeat it” (George Santayana)
Some days ago, a new vulnerability known as ROBOT and affecting some SSL/TLS implementations has been published. This acronym refers to “Return Of Bleichenbacher’s Oracle Thread”. In this post, we attempt to explain this vulnerability.
Of course, if this is about the return of Bleichenbacher’s oracle the first question is… what is this oracle and how can it be used to attack SSL/TLS?
Last year we published a post about DROWN (https://www.s21sec.com/es/blog/2016/04/drown-a-fondo-un-nuevo-ataque-al-ssl-parte-i/ , in Spanish) where we stated that during SSL/TLS connection both peers negotiate a series of symmetric keys that will be used to encrypt the data being transmitted between them. There are several methods to negotiate these keys. One of them is RSA, which is the method attacked both by DROWN and by Bleichenbacher’s oracle. The message exchange process can be seen in the following diagram:
Summarizing (a complete explanation of the process can be seen in Spanish in the first part of the DROWN post), the security of the process lies on a certain message (ClientKeyExchange) sent by the client to the server. This message contains a value known as “pre-master-secret” encrypted with the public RSA key of the server, and thus it should be decryptable only by the server. If an attacker manages to deduce the value of this “pre-master-secret” he will be able to decrypt the whole communication.
The critical point is that the size of the “pre-master-secret” is smaller than the size of the server’s public key (something that is normal in RSA encryption). Even though it is mathematically possible to encrypt a value much smaller than the RSA key, it is a bad security practice, and so padding is added before encryption in order to have a value with a size more or less of the same order as the key size. This padding must comply with the PKCS#1 v1.5 format, and so the data that is encrypted and sent to the server must have this structure:
Where red cells have a fixed value, green cells have random non-zero values and blue cells contain the “pre-master-secret”.
So, when the server receives the ClientKeyExchange, the first step is decrypting it and checking if it complies with this format. If the first two bytes are not 0x00 0x02 (allow with other less-important conditions), this condition is identified as an error and that the connection will not be established. In this case, the first SSL/TLS implementations sent an alert to the client and closed the connection.
This is the point where Bleichenbacher’s oracle performs its magic. In this context, an oracle is a mechanism that can be used to extract information that shouldn’t be known. For instance, an attacker tries to establish a connection by sending an arbitrary (random) value in the ClientKeyExchange message instead of the encrypted pre-master-secret. If the server continues with the negotiation, it means that the first two bytes of the decrypted data are 0x00 0x02. If the server sends an alert, they were not.
It is also true that the server can perform additional checks leading to rejected values even though the first two decrypted bytes are 0x00 0x02. For instance, the server can check that the P values are non-zero and that the value between P and M is exactly 0. Depending on the behavior of the server on the result of these checks, the attack is easier or harder and the oracle is of higher or lower “quality”.
Swiss cryptographer Daniel Bleichenbacher discovered in 1998 that this behavior can be used to infer the value of the pre-master-secret. The following diagram shows the behavior:
In this case, the values C and C’ indicate the content that is sent as encrypted pre-master-secret within the ClientKeyExchange packet, while the values below are the result of RSA decrypting those values (thus, they represent the padded pre-master-secret). For C, after decryption the first two values are 0x00 0x02 (the value of the rest is mostly unimportant), so the server identifies it as a valid pre-master-secret and sends its corresponding next message, which is ChangeCipherSpec. For C’, after decryption the first two bytes are 0xF2 0x13. So, the server flags it as an error and generates an alert. This means that, for an arbitrary cyphered block of data, we can know if the first two bytes of the decrypted data are 0x00 0x02.
To understand the next step of the attack, it must be taken into account that the RSA algorithm is partially homomorphic (the explanation can be seen in Spanish, in the web page https://www.s21sec.com/es/blog/2016/04/drown-a-fondo-un-nuevo-ataque-al-ssl-parte-ii/). This means that if we have a given text encrypted using RSA and we apply a series of transformations, we obtain a different encrypted text whose corresponding decrypted text has a known relationship to the original one. This is like being able to apply a transformation to a cyphered text that converts all the decrypted text to uppercase, even without knowing which is the original text (this is impossible in RSA, but it’s a good metaphor).
So, the attack implies generating new values to be sent in ClientKeyExchange (using a simple algorithm that takes as input a parameter “s” that the attacker modifies) and check if the first two bytes of the decrypted data are 0x00 0x02. And how can we check this condition without having the private key? Quite easy: we use the oracle we saw before.
Most of the attempts are rejected and the server sends and alert, as the attacker has to work without knowing the decrypted values. But once in a while, the server accepts one of the modified ClientKeyExchange messages, meaning its first two decrypted bytes are 0x00 0x02.
As the attacker knows the relationship between the accepted ClientKeyExchange and the original one (he knows the value of “s” used to generate it), this provides the attacker with a little bit of information about the original ClientKeyExchange data, allowing him to close in the possible values of the “pre-master-secret” of the legitimate connection (this mechanism provides both lower and upper bounds of the “pre-master-secret” value). Eventually, after finding a high enough number of “s” values generating acceptable ClientKeyExchange messages, the attacker obtains the exact value of the original “pre-master-secret”, or a range small enough to be brute-forced.
To have an idea of the amount of required work, Bleichenbacher’s oracle is also known as the “million messages attack” because it was estimated that a successful attack would require that number of fake ClientKeyExchange messages until the value of the “pre-master-secret” of the original connection is obtained. In practice this value varies greatly depending on the “quality” of the oracle.
To neutralize Bleichenbacher’s oracle, if a server detects a malformed ClientKeyExchange (meaning that the result after decryption does not comply with the expected padding format), it generates a random value and proceeds as if the client had provided that value. The attack in this case results in:
With this mechanism, the attacker is unable to distinguish correct and incorrect values, as the server behaves as if every ClientKeyExchange was valid, so the oracle is neutralized and the attack is not possible. As this mechanism has been included within the TLS standard in recent versions, all implementations include it and we can forget about this problem.
Almost 20 years later, the authors of the study in which ROBOT is based decided to check if this protection Works in an adequate way in a series of implementations, and so if Bleichenbacher’s Oracle is usable or not. The result, unfortunately, has not been good. Some of the most serious cases return an alert or simply close the TCP connection as soon as an invalid ClientKeyExchange is received, meaning that they do not implement the protections.
Another surprising case are implementations that correctly implement the protections, generate a random value to be used as pre-master-secret, send the corresponding server-side ChangeCipherSpec and Finished messages… and then unexpectedly close the connection without waiting for the client-side ChangeCipherSpec and Finished messages. So, the attacker only has to wait a bit. If the server unexpectedly closes the connection, the ClientKeyExchange value was invalid, whereas if the server waits undefinitely (or until timeout), then the ClientKeyExchange value was correct.
Summarizing, even after 20 years, Bleichenbacher’s oracle is a pain for some implementations. This, coupled with the lack of perfect forward secrecy in RSA secret exchange justifies the decision to eliminate it in TLS 1.3.
On the other hand, the amount of different incorrect implementations reminds us that implementing cryptographic libraries is not something to be taken lightly, and that it’s much better to use established, tested and audited libraries instead of starting to implement our own code from scratch.
To better analyze this problem, you can refer to the original paper, that can be found at https://eprint.iacr.org/2017/1189.pdf