[cryptography] Order of blinding and consistency checking in avoiding fault attacks

Jack Lloyd lloyd at randombit.net
Fri Mar 12 16:16:38 EST 2010


There have been several recent papers on fault attacks against general
PCs using low-voltage situations to make the multiplier fail
(http://lists.randombit.net/pipermail/cryptography/2010-March/000000.html)

The results from these papers suggest that two effective techniques
against fault attacks of this nature for public key algorithms are
randomized blinding and consistency checking (preferably both).

In the specific case of RSA, blinding might work as

Choose a random k between 1 and n

Multiply the input by k^e mod n

Perform the modular exponentiation to d mod n

Multiply the output by k^-1 mod n

Consistency checking is simply making sure the signature verifies
(testing to confirm that input == sig^e mod n).

Can anyone think of a particular reason why it would be better to
perform one of these before or after another? That is, if it's better
to do

(1)
m = m * k^e    # blind
s = m^d        # modexp
m == s^e?      # check
s = s * k^-1   # unblind

or

(2)
m = m * k^e    # blind
s = m^d        # modexp
m = m * k^-1   # unblind
s = s * k^-1   # unblind
m == s^e?      # check

The only considerations I've come up with are:

(2) Would potentially detect errors/faults in the blinding code.

(2) Might be vulnerable to timing attacks on the exponentation
    by e (applies to encryption more than signatures)

(As I've written it, 2 looks slower than 1 because it would require an
extra multiply to get the original value of m back, but making a copy
of m before blinding it would typically be cheap and would avoid the
extra multiply).

Are there other differences in these approaches that I've missed?

-Jack



More information about the cryptography mailing list