5
$\begingroup$

I have been reading about “Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension” by Wing H. Wong. I was wondering if this attack is feasible while signing with RSA and, if yes, how?

Also, how this kind of attack is applied with DH?

Talking about timing attacks in general, in which way AES is affected and how to solve it? (I mean, with RSA the "problem" is at multiplication level, while for AES where is the problem that makes the cipher implementation key or data dependent?)

$\endgroup$
  • $\begingroup$ It would be good to split this question. The answer below at least partially handles the question about AES, but the RSA signing and DH parts remain unanswered. $\endgroup$ – otus Dec 5 '17 at 14:32
  • $\begingroup$ Link is 404 now? $\endgroup$ – Squeamish Ossifrage Dec 5 '17 at 15:05
5
$\begingroup$

The seminal paper on timing attacks is Paul C. Kocher, ‘Timing Attacks on Implementations of Diffie–Hellman, RSA, DSS, and Other Systems’, CRYPTO 1996, Springer LNCS 1109, 1996 (alternate link in case you hit a paywall). This is also the standard reference, and it's quite approachable—I recommend reading it. Here's a coarse high-level overview.

The basic idea for RSA and DH is to measure how long modular exponentiation takes as a function of a secret exponent.

How do you do this with RSA encryption? Find an automated system that decrypts and sends an answer back to you, and send it a long sequence of messages, and measure how long it takes to decrypt each one. Any timing variation in the crypto computation itself—once you've isolated noise from the network and other sources—is likely to be dominated by the timing variation in modular exponentiation to compute $m = c^d \pmod n$ for secret $d$, in naive RSA implementations. (Here $n$ is the public key, $c$ is the ciphertext representative, and $m$ is the padded plaintext representative for (say) RSAES-OAEP, or secret key seed for RSA-KEM.)

How do you do this with RSA signature? Find an automated system that signs and sends a signature back to you—not a signature on any document you want, only a signature on documents that the legitimate signer wants to sign. For example, an HTTPS certification authority like Let's Encrypt will do this. Send it a long sequence of requests to sign, and measure how long it takes to sign them. Again, the timing variation is likely to be dominated by timing variation in modular exponentiation to compute $s = h^d \pmod n$ for secret $d$, in naive RSA implementations. (Here $h$ is the message hash, and $s$ is the signature.)

How do you do this with Diffie–Hellman? Find an automated system that performs DH key agreement with a static key, and ask it to do a long sequence of key agreements with public keys of your choice. Once again, the timing variation is likely to be dominated by timing variation in modular exponentiation to compute $k = B^a \pmod p$ where $a$ is the static secret and $B$ is the attacker's ephemeral public key.

How do you do this with AES? It's a little different, and the Kocher paper doesn't go into much detail beyond a casual mention. The standard reference here is Daniel J. Bernstein, ‘Cache-timing attacks on AES’, Document ID: cd9faae9bd5308c440df50fc26a517b4, 2005-04-14. It is also fairly approachable. The coarse high-level overview is that the time it takes the CPU to load an element of an array depends on whether that position in memory is already cached. By studying which elements of the S-box are typically not cached at some point in the computation yielding $S[k_i \oplus p_i]$, and studying which plaintext bytes $p_i$ cause the computation to take the most time, we can deduce the key byte $k_i$, and repeat for all the others.

There are also side channel attacks on other parts of RSA-based cryptosystems than modular exponentiation, such as Bleichenbacher's attack on PKCS#1 v1.5, which exploits side channels for the bytes that make up valid padding of a secret message representative to enable an adversary to decrypt or sign messages without the private key. This side channel may manifest as a different error message, or as variation in the time it takes to respond, which extended the idea to RSAES-OAEP (paywall-free preprint), the successor to PKCS#1 v1.5 encryption. Attacks in this class of side channels, padding oracle attacks, apply in other contexts as well, such as the Lucky Thirteen attack on CBC modes of block ciphers in TLS.

And there are, of course, other variations on the theme of timing attacks: e.g. exploiting cache-sharing in hyperthreading to recover keys from one hyperthread in another on Intel CPUs via the L2 cache, flush+reload attacks to recover keys via the L3 cache, cache-timing attacks that thwart naive RSA timing countermeasures, acoustic cryptanalysis using a microphone to hear variations in the spectrum of sound produced by secret-dependent timing in crypto algorithms, and so on.

$\endgroup$
  • $\begingroup$ I'm glad to see we have the same seminal references. :) Did you also hesitate to mention CacheBleed? $\endgroup$ – Lery Dec 5 '17 at 16:19
  • $\begingroup$ I can only conclude that you must have peeked over my shoulder while I was editing my answer, and/or surreptitiously measured my browser link color while I was browsing around to load the references in order to determine which pages I had already visited! Cachebleed: No, I didn't think of it for this post, although that's a good one to add to the hodgepodge of different attack types, to attack modular exponentiation with a cache-timing side channel. $\endgroup$ – Squeamish Ossifrage Dec 5 '17 at 16:21
  • $\begingroup$ What a ominous thought: an ubiquitous Lery! I'll wait to get 3 upvotes and will delete my answer then, since yours is longer, and more complete, plus I'm intent on getting that infamous "Disciplined" badge... :3 $\endgroup$ – Lery Dec 5 '17 at 16:28
  • 1
    $\begingroup$ Let me add here that one should notice that with RSA the "problem" is not necessarily at the multiplication level, since both Bleichenbacher's and Manger's attacks are at the padding level. Which means that, upon decryption, timing discrepancies even in RSA OAEP can be used as a padding oracle allowing for decryption of a given message. $\endgroup$ – Lery Dec 6 '17 at 9:17
1
$\begingroup$

I have been wondering the same thing and am currently investigating the issue. There was a conference called Zero Nights from 2013 where one of the speakers - Roman Korkikyan - talked about this (slides and notes are available online). Based on my understanding of his explanations, the timing attack occurs at the Mix Columns layer in AES - there we have binary multiplication, which in my mind is inherently depended on the input (0 or 1) and this introduces the timing attack. I am still researching this and if looking for the ways this can be avoided and will keep you posted on my progress.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.