Thierry Moreau wrote: > > > Jostein Tveit wrote: > >> Ben Laurie <[EMAIL PROTECTED]> 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/[email protected]/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 [EMAIL PROTECTED]
