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

```