Bleichenbacher Attack
This attack is applicable when key-exchange take place using RSA algorithm and the padding used is PKCS#1 v1.5. I explained how about RSA & padding in my earlier article.
How the Attack works:
Note that during TLS session setup with RSA key exchange, client choose a random 48 bit number(2 bytes of protocol version and 46 random bytes), pad as per PKCS encoding scheme to make of same order of modulo n. The whole thing is then raised to public exponent e modulo n. On the receiver side, after decryption, the data is verified to align properly otherwise the packet is discarded.After decryption, receiver check if the plain text data starts with 0x00 02 , if not it is discarded, then all the bytes are skipped until 0x00 is found.
Note that for public key operation, PKCS padded data must always starts with 0x00 0x02.Also we know for RSA that it has homomorphic property of multiplication.That means when a encrypted text is multiplied with another encrypted text , decryption of resulting value will yield something meaningful. Let’s see with an example.
Suppose an attacker get the cipher text C which is essentially [Mᵉ mod n], attacker doesn’t know about M(which is PKCS padded)but he know about public key (e, n).
C = Mᵉ mod n
Attacker then multiplies this cipher value with a chosen s. For all failure cases, server must respond something like ‘Bad data’.Attacker keep changing value of s and wait until accepted by server.
C` = C * sᵉ mod n which is essentially encryption of (M *s) .
When server accept this C` that mean C`after decryption start with 0x00 0x02 and C` is a valid encryption for M*s with PKCS padding.
C` = M *s and hence M = C` ÷ s or M = C` s⁻¹ mod n
Technical Details from paper
B = 2^8(k−2). k is key size in bytes, like in RSA we say 2048 bit (256 bytes).
Since first 2 bytes are 0x00 0x02 , we are subtracting that.
2⁸ is done to show the message in bit representation.
When the message is accepted by server, that means.
2 B ≤ ms mod n < 3B
2 B means 0010 ……k-2 bytes
3B means 0010 …….k-2 bytes
Since we know that if message is accepted first 2 bytes are 0x00 02 and hence the message ms mod n is strictly less than when first 2 bytes are 0x00 03. And like that attacker further reduces the boundary by doing binary search until a single value is found.
Mitigation:
* Do not use RSA for key exchange.Instead use DH or ECDH which additionally provide property of Perfect Forward Secrecy.
* For padding, use OAEP instead of PKCS.
* Do not inform the client about failure when Pre-Master decryption failed, instead inform at Finished stage.As per RFC 5246 page 60.
“In any case, a TLS server MUST NOT generate an alert if processing an
RSA-encrypted premaster secret message fails, or the version number
is not as expected. Instead, it MUST continue the handshake with a
randomly generated premaster secret. It may be useful to log the
real cause of failure for troubleshooting purposes; however, care
must be taken to avoid leaking the information to an attacker”
Reference:
Return Of Bleichenbacher’s Oracle Threat (ROBOT)
20 years later, this attack was discovered by Hanno Bock and others.
It seems the mitigation techniques suggested were too complex and hence not implemented properly. Bleichenbacher attack is always possible if the attackers is able to distinguish between valid and invalid padded message.
ROBOT attack suggest 5 test vector and then try these on any server to see if we get different alert, if yes that means the server is vulnerable to Bleichenbacher attack.
M1: Correctly formatted PKCS#1 v1.5 packet
M2: Incorrect PKCS #1 v1.5 padding , like we know that before doing public key encryption , message is padded and it must start with 0x00 02. In this test scenario, we test with invalid start bytes.
M3: Remember that random bytes are non-zero bytes and must end with 00, message is a valid PKCS#1 v1.5 format but 00 bytes is misplaced to some other position.
M4: Don’t add 00 bytes after the random padding bytes.
M5: Pre-master secret is 2 bytes of protocol version and 46 random bytes, in this test vector, attacker can change the TLS version and observe server response.
So researchers did server scan with above test vector and observer what server respond, it attackers is able to distinguish valid from invalid message that means we have an oracle.
Signature forging: Another interesting thing was reported in ROBOT attack was, attacker would be able to create a valid signature without leaking private key. Let’s see how this works:
In RSA a signature is generated by raising the message M to private exponent d.
S = Tᵈ mod n
Before that message M is padded as per PKCS#1 v1.5
T = 0x00 0x01 || pad() || 0x00 || ASN.1(hash(M)) If we multiply this T with sᵉ mod n and server is able to properly decrypt this means PKCS encoding is proper.
(T * sᵉ )mod n
We raised Tᵈᵉ , remember RSA equation d.e = 1 mod n
C` =(Tᵈ * s)ᵉ mod n where Tᵈ is signature.
Tᵈ = C`s⁻¹ mod n and that’s how we can get the signature of T.
Reference:
The 9 Lives of Bleichenbacher’s CAT
In order to understand this attack one need to understand following
Cache Timing Attack.
FLUSH-RELOAD Attack
A spy which runs on same machine as victim and has access to cache.Spy also knew the algorithm which uses secret key, for example, here e is secret.
Attacker can then FLUSH the cache address of instruction x =x`
Victim process when execute will then have to reload x` only when eᵢ is 1. Attacker will then try to reload x and if it get access faster that means it is cache and that indirectly means eᵢ is 1. And so on attacker can retrieve bits of secret key.
PRIME-PROBE Attack
A spy which runs on same machine as victim and has access to cache, first fills up the entire cache with spy data.When the victim process run, it will obvious use some of the cache(which is now filled with spy data) and use some policy(LRU etc)to evict some cache line. So whatever cache line is access, attacker can retrieve some partial information about secrecy.For example, in this toy example
If Key =0xAA and CT(cipher text, known to attacker), Lookup[0x55] will be accessed and attacker observe this on cache line and can know about key.
- MiTM downgrades the attack to use RSA key exchange and also use BEAST kind of attack to parallelize it. Further to speed-up they use multiple server’s which share same public key certificate. This is possible since many service have mirrors for different geographical region bt end up using same server certificate on all mirrors.
- For padding oracle they use Manger’s Oracle.
Attack is also applicable to TLS 1.3 where the connection is downgraded to TLS 1.2. MiTM strip of the “warning bytes” of “DWNGRAD” in server_random.Further certificate_verify message, which is essentially a signature, can also be forged using Bleichenbacher’s attack as explained above.
Research paper mentions following test cases and then evaluates them.
- The first check corresponds to the test for a zero byte somewhere after the first ten bytes of the plaintext.
- The second check verifies that there are no zero bytes in the padding string PS00 .
- The third check verifies the plaintext length against some specific value (48 byte for a TLS premaster secret in our case).
- Finally, the fourth check is payload-aware and TLS-specific: it verifies the first two bytes of the payload; these bytes are set to the client’s protocol version as defined in RFC5246.
Mitigation
- Use ECDH for key exchange but may be not possible for compatibility with older version.
- Use constant time code and for both success and failure case execution time remain same.
- Use different key pair for signing and decryption.2048 bits or higher key length make Bleichenbacher/Manger attack less practical.
- Shorter handshake timeout, dedicated crypot hardware.