inconsistent timings for rsa sign/verify with 100K bit rsa keys

[Georgi Guninski]

inconsistent timings for rsa sign/verify with 100K bit rsa keys.

using pycrypto i generated two valid 100 000 bit rsa keys with the same modulus:

key1: log(n)=100K, e=2^16-1,d=BIG
key2: log(n)=100K, e=BIG, d=BIG
(note key1 and key2 share the same modulus)

recompiled openssl with increased parameters so the keys are usable.

i expect the keys to be slow, but this benchmarks quite surprise me:

sign verify
key1 5min <1sec
key2 48min 21min
(tested on patched openssl1.0.0a)

is it normal key2 to be so slower compared with the signing of key1 (the 1sec verification with low exponent is clear to me).

signature verification passes for both keys and the big exponents seem of the right size. both keys passed "rsa check" with reduced number of pseudoprimality tests (to 3).

pycrypto is much faster with key2 and general purpose math program suggest sign/verify to be about 5min for big exponents (<phi(n)).

the tarball with the private keys + 2 certs (190K) is at:

http://seclists.org/fulldisclosure/2010/Aug/384
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[PMHager]

Could you please count the 1-bits in each exponent (e and d).
This might give an explanation.

-----Original Message-----
From: owner-openssl-***@openssl.org [mailto:owner-openssl-***@openssl.org] On Behalf Of
Georgi Guninski
Sent: Sunday, August 29, 2010 10:51 AM
To: openssl-***@openssl.org
Subject: inconsistent timings for rsa sign/verify with 100K bit rsa keys

inconsistent timings for rsa sign/verify with 100K bit rsa keys.

using pycrypto i generated two valid 100 000 bit rsa keys with the same modulus:

key1: log(n)=100K, e=2^16-1,d=BIG
key2: log(n)=100K, e=BIG, d=BIG
(note key1 and key2 share the same modulus)

recompiled openssl with increased parameters so the keys are usable.

i expect the keys to be slow, but this benchmarks quite surprise me:

sign verify
key1 5min <1sec
key2 48min 21min
(tested on patched openssl1.0.0a)

is it normal key2 to be so slower compared with the signing of key1 (the 1sec verification
with low exponent is clear to me).

signature verification passes for both keys and the big exponents seem of the right size.
both keys passed "rsa check" with reduced number of pseudoprimality tests (to 3).

pycrypto is much faster with key2 and general purpose math program suggest sign/verify to
be about 5min for big exponents (<phi(n)).

the tarball with the private keys + 2 certs (190K) is at:

http://seclists.org/fulldisclosure/2010/Aug/384
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Mounir IDRASSI]

Hi,

The big difference in the sign operation timings between the two keys is
not caused by any property of the second key parameters (like their
hamming weight) but it is rather the expected manifestation of two
counter-measures implemented by OpenSSL. Those are :
- RSA Blinding that protects against timing attacks.
- Verification of CRT output that protects against fault attacks.

Each of these counter-measures involves a modular exponentiation by the
public exponent e.
When the public exponent e is equal to 2^16-1, then the cost of these
two counter-measures is negligible.
When e is big (in your case the same size as the modulus), then these
counter-measures add an overhead that is equal to twice the cost of an
RSA verification.
In your case, for the second key, this overhead is expected to be equal
to 2x21 min = 42 min. The cost of a pure CRT signature without
counter-measures is roughly 5 min (taken from CRT of key1 for whom
counter-measures are negligible).
This gives us an expected running time for a signature with key2 of 42 +
5 = 47 min, that is very close to what you actually obtained.

You can deactivate the blinding counter-measure by calling the function
RSA_blinding_off. On the other hand, CRT output verification
counter-measure can't be deactivated.
I hope this clarifies the behavior you have encountered.

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Post by Georgi Guninski
inconsistent timings for rsa sign/verify with 100K bit rsa keys.
key1: log(n)=100K, e=2^16-1,d=BIG
key2: log(n)=100K, e=BIG, d=BIG
(note key1 and key2 share the same modulus)
recompiled openssl with increased parameters so the keys are usable.
sign verify
key1 5min<1sec
key2 48min 21min
(tested on patched openssl1.0.0a)
is it normal key2 to be so slower compared with the signing of key1 (the 1sec verification with low exponent is clear to me).
signature verification passes for both keys and the big exponents seem of the right size. both keys passed "rsa check" with reduced number of pseudoprimality tests (to 3).
pycrypto is much faster with key2 and general purpose math program suggest sign/verify to be about 5min for big exponents (<phi(n)).
http://seclists.org/fulldisclosure/2010/Aug/384
______________________________________________________________________
OpenSSL Project http://www.openssl.org

______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Mounir IDRASSI]

you write "sign operation", does it explain "verification operation" -
timings for signing with low pub exponent key vs verification with big exponent ?

To answer this question, one must remember that the signing is done
using the CRT parameters (p, q, dp, dq and d^-1 mod p) and that
theoretically it is 4 times faster than doing a raw exponentiation with
the private exponent d (see section 14.75 in Handbook Of Applied
Cryptography for a justification).
Your figures exactly meet this. I'll explain.

The verification with key2 involves a modular exponentiation with a
public exponent of 100 001 bits with a hamming weight equal to 49945.
The private exponent of key1 is 100 002 bits and it has a hamming
weight of 49 922.
Thus, a modular exponentiation with the public exponent of key2 will
cost roughly the same as the modular exponentiation with the private
exponent of key1.
Moreover, as I explained at the beginning of this email, the actual
signing is done using CRT which is 4 times faster that the modular
exponentiation with the private exponent.

So, the modular exponentiation with the public exponent of key2 is 4
times slower that the signing operation of key1 and it should cost 4 x 5
min = 20 min which is very close to the 21 min you actually obtained.

Does this answer your question?

--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

Post by Mounir IDRASSI
Hi,
The big difference in the sign operation timings between the two
keys is not caused by any property of the second key parameters
(like their hamming weight) but it is rather the expected
manifestation of two counter-measures implemented by OpenSSL. Those
- RSA Blinding that protects against timing attacks.
- Verification of CRT output that protects against fault attacks.

ok, thanks.

______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Georgi Guninski]

Post by Mounir IDRASSI
So, the modular exponentiation with the public exponent of key2 is 4
times slower that the signing operation of key1 and it should cost 4
x 5 min = 20 min which is very close to the 21 min you actually
obtained.
Does this answer your question?

yes, thanks.

i didn't know about the implementation details + openssl being visibly slower than
general purpose programs on generic 100K exponentiations added up to the
confusion.

thanks.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org