[cryptography] RSA signatures without padding

Jonathan Katz jkatz at cs.umd.edu
Sun Jul 12 16:44:25 EDT 2015


On Fri, Jul 10, 2015 at 7:42 PM, Filip Paun <paunfilip at gmail.com> wrote:
> Hello,
>
> Thank you for your feedback. Please see my comments below.
>
> On Fri, Jul 10, 2015 at 3:59 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:
>>
>> On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun <paunfilip at gmail.com> wrote:
>> > Suppose I have a message M for which I generate an RSA-2048 digital
>> > signature as follows:
>> >
>> >   H = SHA-256(M)
>> >   S = H^d mod N
>> >
>> > Assume N = p*q is properly generated and d is the RSA private key.
>> >
>> >
>> > And I verify the signature as follows:
>> >
>> >   S^e mod N == H'
>> >
>> > where H' is the SHA-256 of the message to be authenticated. Assume e is
>> > the
>> > RSA public key.
>> >
>> > Since I've not used any padding then are there any flaws with the above
>> > approach? What if e = 3? What if e = 2^16+1?
>> >
>> > Your guidance is much appreciated.
>> >
>> > Thank you,
>> > Filip
>>
>> This is a bad idea.
>
>
> Specifically, I am interested in the reasons why this is a bad idea for the
> case where e = 2^16+1 and the hash is SHA256. Also, it's important to point
> out that given my particular use case, an attacker can only see a few
> pre-computed signatures and cannot generate any new signatures by using the
> signer as a oracle.

The value of e is irrelevant, as the attack is based on the
homomorphic properties of RSA.

>>
>> Note that the Full-Domain Hash (FDH) signature scheme would use a hash
>> mapping the message to all of Z*_N, where here you have a hash mapping
>> to the (much smaller) space of 256-bit strings.
>
>
> My first impression was similar to yours where it just didn't feel right to
> exponentiate a 256-bit number instead of a 2048-bit number. So now I'm
> trying to search for an actual proof for why this would be bad.
>
>>
>> The problem is that this makes attacks based on factoring H(m) (in
>> your case a 256-bit number rather than a 2048-bit number) and then
>> using multiplicative properties of RSA much easier. The size of e is
>> irrelevant.
>
>
> Not sure what you mean by factoring H(m). Why would an attacker try to
> factor H(m)? Do you instead mean finding the e-th root of H(m)? (My
> assumption is that finding e-th roots in mod N is hard as claimed in
> RFC3447.)

No. The issue is that one can factor H(m), and with high probability
H(m) will even have small prime factors. You can then use an
index-calculus style attack to forge signatures.

The following papers have more details:
http://www.jscoron.fr/publications/padding.pdf
http://www.jscoron.fr/publications/isodcc.pdf

> Thanks,
> Filip
>


More information about the cryptography mailing list