1783231 - RSA exponentiation blinding

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement, P3)

Description

[Anna Weine]

I would like to open a discussion about adding an exponentiation blinding for RSA as a response to https://bugzilla.mozilla.org/show_bug.cgi?id=1761036. TLDR: The RSA algorithm in NSS leaks some information about the secret key.

I looked at RSA CRT implemented in NSS, and drafted an algorithm to blind the exponent. In the comments I will put the code I have implemented. What do you think about it, would it help to decrease the information leaking?

Comment 1

[Anna Weine]

m = getrandbits(200)
p = next_prime(getrandbits(512))
q = next_prime(getrandbits(512))
n = p * q

d = next_prime(getrandbits(1024))
phi = (p - 1) * (q - 1)
e = power_mod(d, -1, phi)

c1 = power_mod(m, d % (p - 1), n)
c2 = power_mod(m, d % (q - 1), n)
h = (c1 - c2) * (power_mod(q, -1, p)) % p
c = c2 + h * q

m1 = power_mod(c, e, n)

print("Without blinding")
print(m == m1)

print("With blinding")
r = next_prime(getrandbits(64))

c1 = power_mod(m, d % (p - 1) + getrandbits(64) * (p - 1) , n)
c2 = power_mod(m, d % (q - 1) + getrandbits(64) * (q - 1), n)
h = (c1 - c2) * (power_mod(q, -1, p)) % p

c = c2 + h * q
m1 = power_mod(c, e, n)

print(m == m1)

(The code could be run here: https://sagecell.sagemath.org/)

Comment 2

[Anna Weine]

Attachment: Bug 1783231 - Adding exponent blinding for RSA

Comment 3

[Alicja Kario]

Shouldn't this rather be

c1 = power_mod(m, d % (p - 1) + getrandbits(64) * (p - 1), p)
c2 = power_mod(m, d % (q - 1) + getrandbits(64) * (q - 1), q)
h = (c1 - c2) * (power_mod(q, -1, p)) % p

(the modulus is wrong)

Also, the key generation at the beginning doesn't look right to me, shouldn't we generally select the public exponent (e) to be 0x10001 and then calculate the private exponent (d) as follows?:

e = 0x10001
t = lcm(p - 1, q - 1)
d = power_mod(e, -1, t)

(also don't see why we need r)

That being said, the main part (adding getrandbits(64) * (p - 1) or * (q - 1) is correct. Simple proof:
From Euler's theorem we have a ^ phi(n) = 1 mod n, for any positive coprime integers a and n (and thus power to any multiple of phi(n) is equal 1).
Given that x ^ (a + b) = x ^ a * x ^ b; in modulo arithmetic, if b is a multiple of phi() of the modulus, we're essentially multiplying the result of exponentiation by 1. Finally, as p and q are prime, the phi(p) = p-1 and phi(q) = q-1.

Which should be enough to hide the side channel from exponentiation provided that the random number generation, multiplication by phi() and addition to d mod phi(prime) is not leaky for the given attack vector.

Comment 4

[Anna Weine]

(In reply to Hubert Kario from comment #3)

Shouldn't this rather be

c1 = power_mod(m, d % (p - 1) + getrandbits(64) * (p - 1), p)
c2 = power_mod(m, d % (q - 1) + getrandbits(64) * (q - 1), q)
h = (c1 - c2) * (power_mod(q, -1, p)) % p

(the modulus is wrong)

Also, the key generation at the beginning doesn't look right to me, shouldn't we generally select the public exponent (e) to be 0x10001 and then calculate the private exponent (d) as follows?:

e = 0x10001
t = lcm(p - 1, q - 1)
d = power_mod(e, -1, t)

(also don't see why we need r)

That being said, the main part (adding getrandbits(64) * (p - 1) or * (q - 1) is correct. Simple proof:
From Euler's theorem we have a ^ phi(n) = 1 mod n, for any positive coprime integers a and n (and thus power to any multiple of phi(n) is equal 1).
Given that x ^ (a + b) = x ^ a * x ^ b; in modulo arithmetic, if b is a multiple of phi() of the modulus, we're essentially multiplying the result of exponentiation by 1. Finally, as p and q are prime, the phi(p) = p-1 and phi(q) = q-1.

Which should be enough to hide the side channel from exponentiation provided that the random number generation, multiplication by phi() and addition to d mod phi(prime) is not leaky for the given attack vector.

Hi! Thanks for looking at the code.

Actually, the part about e/d does not represent the NSS code, it was just my draft to implement RSA in Sage and to be sure that the countermeasure works for RSA-CRT.

Comment 5

[Anna Weine]

I don't remember if we have the unique public exponent :) I built the blinding above the existing code :)

Comment 6

[Alicja Kario]

Yes, the proposed patch doesn't have the issues from the sage code.

One more assumption for the fix to actually work: the power_mod() must not leak the modulus.

Comment 7

[Anna Weine]

You mean here? https://searchfox.org/mozilla-central/source/security/nss/lib/freebl/rsa.c#1035

Comment 8

[Alicja Kario]

yes, and 3 lines below, for the q prime

Comment 9

[Alicja Kario]

Hi Jan, could you test this proposed patch?

Comment 10

[Anna Weine]

I am slightly annoyed at the https://searchfox.org/mozilla-central/source/security/nss/lib/freebl/mpi/mpi.c#1006 (mp_div) function, but I don't know how much it's gonna leak.

Comment 11

[Alicja Kario]

Yes, https://searchfox.org/mozilla-central/source/security/nss/lib/freebl/mpi/mpi.c#1045-1060 (both the branch on check and vastly different code executed in the branches) will definitely leak, I don't know how exploitable it is though. Generally for multiplication and exponentiation the intermediate values will by much larger than the modulus, so the shortcut should generally not be taken, but I haven't analysed the algorithms where it's used.

Comment 12

[Anna Weine]

I can try to write it SCA-protected way to compare the speed.

Comment 13

[Ján Jančár]

The patch looks good and should make attacking RSA-CRT in NSS via a timing/cache attack way harder. I tested a bit with dudect but am getting weird results (as is usual with a tool based on runtime statistics). Testing with valgrind is pointless since that will still complain as this is a randomization countermeasure that a simple information-flow tracker cannot reason about (without telling it to).

Otherwise, I agree with @hkario here, the exponentiation is the big thing, the individual multiplications, divisions etc. are smaller issues. Generally, very few libraries have fully constant-time big-number implementations.

Comment 14

[Anna Weine]

So, do you think that the patch will solve (make it less exploitable) the leakage we have now? Or we better concentrate of hiding the modulus in exponent?

Comment 15

[Ján Jančár]

Yeah, I think it will be pretty hard to exploit. Tbh to properly quantify the leakage and make claims about fixes one would need to understand the leakage way better than I currently do (i.e. look at the modexp algorithm variants implemented, look at all the other bignum functions handling the secret key values, etc.). Unfortunately, I do not currently have time to do that. With that said, I think exponent blinding is a good countermeasure to use in this case (more randomness is always good w.r.t. these types of attacks), and it can give more time to reevaluate the leakage/RSA implementation.

Comment 16

[Anna Weine]

Attachment: Bug 1783231 - Initialising variables in the rsa blinding code

Comment 17

[John Schanck [:jschanck]]

https://hg.mozilla.org/projects/nss/rev/e5cf3f1b4ebfb71661c8b4400e118fc4193ee71e
https://hg.mozilla.org/projects/nss/rev/88c82a2639b25d5be36656f708e82cd0fc2cba8b

Comment 18

[Ryan VanderMeulen [:RyanVM]]

For posterity, this shipped in NSS 3.85, which went out with Firefox 108.