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