Re: RSA signatures without padding
There is an attack against this type of RSA signature scheme, although cannot remember just now if it requires that the verfication exponent be small (ie. e=3). The attack I am trying to recall is a chosen-message attack and its efficiency is related to the probability that a random 128-bit integer can be factorized over a small set of primes (ie. the prob that a uniformily selected 128-bit integer is B-smooth for a small integer B). Basically, you pick a message for which you'd like to forge a signature, find a variant of the message that hashes to a B-smooth 128-bit integer, and then you construct the forgery after solving a linear system modulo e (the linear system incorporates the signatures on the chosen messages). I can't think of a reference for this but I will post another message if I find it. -James On Mon, 20 Jun 2005, Florian Weimer wrote: I came across an application which uses RSA signatures on plain MD5 hashes, without padding (the more significant bits are all zero). Even worse, the application doesn't check if the padding bits are actually zero during signature verification. The downside is that the encryption exponent is fairly large, compared to the modules (27 vs 1024 bits). A few hundred signed messages have been published so far. What do you think? Are attacks against this application feasible? (It should be corrected, of course, but it's not clear if a high-priority update is needed.) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA signatures without padding
On 6/20/05, James Muir [EMAIL PROTECTED] wrote: The attack I am trying to recall is a chosen-message attack and its efficiency is related to the probability that a random 128-bit integer can be factorized over a small set of primes (ie. the prob that a uniformily selected 128-bit integer is B-smooth for a small integer B). Basically, you pick a message for which you'd like to forge a signature, find a variant of the message that hashes to a B-smooth 128-bit integer, and then you construct the forgery after solving a linear system modulo e (the linear system incorporates the signatures on the chosen messages). I think you're referring to the Desmedt-Odlyzko selective forgery attack. See http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1014_Menezes.sigs.pdf -- Taral [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA signatures without padding
Taral wrote: On 6/20/05, James Muir [EMAIL PROTECTED] wrote: The attack I am trying to recall is a chosen-message attack and its efficiency is related to the probability that a random 128-bit integer can be factorized over a small set of primes (ie. the prob that a uniformily selected 128-bit integer is B-smooth for a small integer B). Basically, you pick a message for which you'd like to forge a signature, find a variant of the message that hashes to a B-smooth 128-bit integer, and then you construct the forgery after solving a linear system modulo e (the linear system incorporates the signatures on the chosen messages). I think you're referring to the Desmedt-Odlyzko selective forgery attack. See http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1014_Menezes.sigs.pdf Yes, that's it. Thanks for the URL. -James - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
