Exponent 3 damage spreads...

[Ben Laurie]

Thierry Moreau wrote:
> 
> 
> 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

You need at least 8 FFs here, or it will fail the padding check.

> 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,
> 


-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com