[17513] in cryptography@c2.net mail archive
Re: RSA signatures without padding
daemon@ATHENA.MIT.EDU (James Muir)
Mon Jun 20 20:50:04 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Mon, 20 Jun 2005 17:08:50 -0400 (EDT)
From: James Muir <jamuir@math.uwaterloo.ca>
To: cryptography@metzdowd.com
In-Reply-To: <87slzd58c0.fsf@deneb.enyo.de>
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 majordomo@metzdowd.com
>
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
