# signature with Bleichenbacher’s attack

I understood Bleichenbacher & ROBOTO attack, however I have some trouble understanding Section 3.5 of ROBOT attack which discusses retrieving private keys. https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-bock.pdf

In order to create a signature with the server’s private key, the attacker first uses a proper hash function and encoding to process the message. For example, when creating a PKCS #1 v1.5 signature for message M, the encoded result will have the following format [29]:

EM = 0x0001 || 0xFF...FF || 0x00 || ASN.1(hash(M))

hash() denotes a cryptographic hash function.

What message M is the author talking about? Is this TLS session establishment? Can someone shed more light on this section 3.5

• That section isn't talking about TLS. M is the thing to be encrypted. – schroeder Sep 23 '18 at 19:55

What message M is the author talking about? Is this TLS session establishment? Can someone shed more light on this section 3.5

First of all, you need to understand what the Bleichenbacher attack is (by the description in your answer, you don't).

What it is is a way of, given a value $$EM$$, computing $$EM^d \bmod N$$, given an Oracle that will, given a value $$EM'$$, telling you whether $$EM'^d \bmod N$$ has value PKCS #1.5 encryption padding (which is different from the signature padding). The attacker can often find an Oracle by using a protocol where he sends an encrypted value to the system under attack, and observing how the system reacts (whether he acts as if the decryption failed, or whether he acts like he got some valid value).

When the attack was first published 20 years ago, it would require a huge number (circa a million) different $$EM'$$ values to actually work; later refinements significantly reduced that number, to circa 10,000 messages IIRC.

Now, on to TLS and your actual question, and while the paper does look at protocols beyond TLS, I'll focus on TLS.

When the TLS server establishes a connection, it sends both its certificate (showing that it owns a public key), and something signed with that public key. If the signature doesn't verify, the client rejects the connection.

So, in order to masquerade as the server, you'd need to do the same thing; you need to send a certificate (which this attack reuses the valid server's certificate), and then the signature of something; that something is the message M.

Now, if you look into the TLS protocol, this $$M$$ is the transcript of the TLS negotiation up to that point; the details aren't actually relevant to the attack, except that they aren't known until the negotiation actually happens (as it includes unpredictable values chosen by the client).

So, what the paper proposes we do is masquerade as the server up until the point where it actually has to generate the signature. It knows $$M$$, and so we able to compute $$EM$$. Then, by quickly performing the Bleichenbacher attack against the real server, it recovers $$EM^d \bmod N$$ before the client times out. This $$EM^d \bmod N$$ value is the correct signature for $$M$$, and so the attacker can present that to the client, and the attack succeeds.

• Thanks, regarding ROBOT attack , they conducted a CTF and here is one writeup s21sec.com/en/blog/2018/02/solving-the-robot-ctf I am still trying to co-relate if this is same as suggested by you. – Chits Oct 1 '18 at 16:47
• @Chits: the biggest difference in the blog post is that they're attempting a public key decryption, not a signature generation. These are the same basic problem; however, at least in the TLS case discussed in the paper, the protocol gives a strict time limit for how much time you can take to generate the signature; in the public key decryption case done in the CTF scenario, you can take as much time as you as need – poncho Oct 1 '18 at 18:12
• Thanks, I will re-read ROBOT attack and CTF writeup, mainly signature part that how can they generate a message signed by server's private key. Do you some other links for understanding of Bleichenbacher attack and ROBOT? – Chits Oct 1 '18 at 18:38
• Nit: for SSL3 & TLS1.0-1.2 using RSA-signed keyexchange (DHE_RSA or ECDHE_RSA) server signs only the body of ServerKeyExchange, while client signs transcript IF client auth is used (optional). TLS 1.3 changes server signature to transcript -- but doesn't use RSA encryption at all, so Bleichenbacher/ROBOT doesn't apply. However the demo signature in the ROBOT paper is not for (any) TLS protocol just an arbitrary string. – dave_thompson_085 Dec 18 '18 at 23:13

After reading the paper few time, I think I got how an attacker can get a message signature signed by server's private key.

Requirement for Bleichenbacher’s attack is a ciphertext and oracle. But in this case a ciphertext of message has to found first before Bleichenbacher’s attack can be performed.

• To create a signature , an attacker first generated EM = 0x0001 || 0xFF...FF || 0x00 || ASN.1(hash(M)) , here M can be any test message.

• Next we have to create such a ciphertext which can be decrypted correctly by server, in order to do so we keep iterating EM * pow( s, e, N) mod n, where s starts 1 and keep incrementing, (e, N) is public key and feed this to oracle to see if this can be decrypted ?

• After too many invocation of oracle, once can get a value of s, which created such an encrypted string that can be decrypted by server.

• After this Bleichenbacher attack , which gives us a decrypted text, which is actually message signed by server' private key.

• To get actual signed message, we have to perform inverse operation of 's' , because remember that encrypted message above is EM * s.

• One can verify using public key that this signed message received is correct.

Main point to note is decryption and signing is same thing from RSA point of view, both need private key.
Authors of ROBOT shows this in a smart way by retrieving a signed message with facebook's private key !! and then verifying it (check the paper).
Note that in all the process actual private key is not revealed to attacker, just the message signed by private key.