How does failing to square a value in this version libcrypt++ cause a timing attack vulnerability?

Question

I'm a crypto beginner and reading about blinding, and my fundamental understanding about preventing timing attacks is that you need to sort of process information in a way that will produce similar processing times for each set of operations.

In CVE-2015-2141 something as simple as failure to call r = modn.Square(r); in a single func seems to have caused a timing attack vulnerability in libcrypt++ in 2015.

I have a multi part question about this:

• First it seems like you'd need some special helper func designed to produce random timing results called in each subroutine to blind a func, why is the process of squaring a value sufficient?

• Second, surely this algorithm has many hundreds of routines that get called every single time it's used - it seems like if nearly all of the subroutines are blinded, the failure to blind just one wouldn't leak enough timing information to cause the entire function to be vulnerable to a timing attack, can someone explain this?

• Is the goal to make every subroutine take exactly the same amount of time to complete, or a random unpredictable time? Why couldn't we paste a helper function call into every module that runs in a securely random amount of time so the timing information released becomes useless?

Answer 1

In CVE-2015-2141 something as simple as failure to call r = modn.Square(r); in a single func seems to have caused a timing attack vulnerability in libcrypt++ in 2015.

Actually no. That's not what CVE-2015-2141 is about. What it is actually about is that the loop originally did not have the squaring and this would result in sometimes not having the blinding removed in a later step after the private key operation which would leak enough information in about 2 signatures on the same message to recover the private key.

First it seems like you'd need some special helper func designed to produce random timing results called in each subroutine to blind a func, why is the process of squaring a value sufficient?

The blinding here is achieved by the fact that computing a signature in rabin-williams is "effectively equivalent" to computing a square root of the message. So it kinda works like this:

• Pick $r\gets_\$ \{1,...,n-1\}$, compute $r^2\bmod n$ and $r^{-1}\bmod n$
• Let $m$ be a message, compute $m'=r^2\cdot m$
• Now compute the signature on $s'=\sqrt {m'}\bmod n=\sqrt {r^2\cdot m}\bmod n=r\cdot\sqrt {m}\bmod n$
• Finally unblind the signature to recover the actual signature $s=r^{-1}\cdot s'\bmod n$

Now what this achieves is prevent an attacker from knowing on which value exactly the private key operation was applied, which should thwart quite a few timing attacks.

Is the goal to make every subroutine take exactly the same amount of time to complete, or a random unpredictable time?

The standard strategy to thwart timing attacks is to either

• ensure the timing doesn't actually depend on the private value in question or
• ensure the timing doesn't actually correlate to known inputs and / or the private key in a meaningful way.

Randomizing the input to the private key operation is part of the second strategy.