[cryptography] RSA signatures without padding

Filip Paun paunfilip at gmail.com
Sun Jul 12 17:55:52 EDT 2015


Jonathan,

Thank you for the links; very helpful.

Thanks,
Filip


On Sun, Jul 12, 2015 at 1:44 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:

> 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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20150712/b612b960/attachment.html>


More information about the cryptography mailing list