Re: [cryptography] RSA signatures without padding

[Filip Paun]

Jonathan,

Thank you for the links; very helpful.

Thanks,
Filip


On Sun, Jul 12, 2015 at 1:44 PM, Jonathan Katz  wrote:

> On Fri, Jul 10, 2015 at 7:42 PM, Filip Paun  wrote:
> > Hello,
> >
> > Thank you for your feedback. Please see my comments below.
> >
> > On Fri, Jul 10, 2015 at 3:59 PM, Jonathan Katz  wrote:
> >>
> >> On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun 
> 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
> >
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Jonathan Katz]

On Fri, Jul 10, 2015 at 7:42 PM, Filip Paun  wrote:
> Hello,
>
> Thank you for your feedback. Please see my comments below.
>
> On Fri, Jul 10, 2015 at 3:59 PM, Jonathan Katz  wrote:
>>
>> On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun  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
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Filip Paun]

Hello,

Thank you for your feedback. Please see my comments below.

On Fri, Jul 10, 2015 at 3:59 PM, Jonathan Katz  wrote:

> On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun  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.


> 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
.)

Thanks,
Filip
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Jonathan Katz]

On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun  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.

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.

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.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Michael Greene]

It is my understanding that, on a very basic level, using RSA without padding 
allows computing “valid” signatures for new messages by combining two existing 
signatures, because a^d * b^d == (a * b) ^ d

The use of sha256 in this case probably makes this task slightly more annoying, 
but by no means impossible - it raises the bar only to crafting a message m 
where Hm(m) == H(m1) * H(m2) mod N. With padding the scheme becomes H = 
(PAD(SHA256(M))) which makes the resulting signature probabilistic rather than 
deterministic, and combining signatures to create new signatures no longer 
works.

It is also my understanding that the malleability problem with textbook (i.e. 
unpadded) RSA relates to encryption/decryption rather than 
signing/verification, not signing/verification, but I could be wrong about that.
--
Michael Greene
Software Engineer
mgre...@securityinnovation.com

> On Jul 10, 2015, at 1:15 PM, Filip Paun  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
> ___
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography



smime.p7s
Description: S/MIME cryptographic signature
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Jeffrey Walton]

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

I *think* the signature could be malleable. That is, you could get
both S to verify, and N - S to verify. Whether its a problem (or not)
depends on your expectations.

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

Bernstein provides a really good history in "RSA signatures and
Rabin–Williams signatures: the state of the art",
http://cr.yp.to/sigs/rwsota-20080131.pdf. He discusses why various
steps are performed, like hashing the message rather than using the
message directly.

You should be OK with 3 or even 2, though it complicates signing.
Taking from Bernstein:

State-of-the-art systems use exponent 2 rather than
exponent 3. This speeds up verification, and improves
the signature-compression and signature-expansion
features discussed in subsequent sections. The signer’s
secret primes p and q are chosen from 3 + 4 Z to
simplify signing

Jeff
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Alexandre Anzala-Yamajako]

This paper probably helps answering part of your question :
http://www.iacr.org/archive/crypto2000/18800229/18800229.pdf
Note that you can't replace a random oracle by SHA256 but you might have
better luck with HMAC-SHA256 (https://eprint.iacr.org/2013/382.pdf)
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography