Exponent 3 damage spreads...
Thierry Moreau
thierry.moreau at connotech.com
Mon Sep 11 10:09:19 EDT 2006
Jostein Tveit wrote:
> Ben Laurie <ben at algroup.co.uk> writes:
>
>
>>...thought this might interest people here.
>
>
> Anyone got a test key with a real and a forged signature to test
> other implementations than OpenSSL?
>
If I understand the attack mathematics correctly, the following
algorithm should give you an alleged signature value that would be
mistakenly accepted by a flawed RSA implementation. I didn't implement
the algorithm, and I will not make suggestions as a convenient big
number arithmetic tool to implement it.
Note: The algorithm output value is NOT A FORGED SIGNATURE, since a
non-flawed RSA signature verification implementation will correctly
reject it. Nonetheless, using public exponent 3 with any use of RSA
should be deprecated.
For the record, I am referring to
Hal Finney, "Bleichenbacher's RSA signature forgery based on
implementation error" Wed, 30 Aug 2006
http://www.mail-archive.com/cryptography@metzdowd.com/msg06537.html
Input:
N, large public modulus (of unknown factorization)
h, hash value
Constant:
p: hex 01 FF 00 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14
A random binary source (e.g. large enough PRNG output)
Algorithm:
(A) find the largest value of r such that b=(p*2^20+h)*2^(8r) such that
b+2^(8r)-1<N
(B) select random a, 0<a<N^2, then set c=a*N^2+b+2^(8r)-1
(C) using a simple binary search, find the d = integer cubic root of c
(D) if d^3<a*N^2+b, go back to step (B) -- if it occurs with a high
probability, that's a failure of the approach proposed here, intuition
suggests that the probability is either very close to zero, or very
close to one
(E) set alleged signature s=d mod N (indeed, d<N, so s=d) and validate
(merely as a software self-check) that (s^3 mod N) div 2^(8r) equals
(p*2^20+h)
(F) output alleged signature s
Regards,
--
- Thierry Moreau
CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, Qc
Canada H2M 2A1
Tel.: (514)385-5691
Fax: (514)385-5900
web site: http://www.connotech.com
e-mail: thierry.moreau at connotech.com
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list