Jonathan, Thank you for the links; very helpful.
Thanks, Filip On Sun, Jul 12, 2015 at 1:44 PM, Jonathan Katz <jk...@cs.umd.edu> wrote: > On Fri, Jul 10, 2015 at 7:42 PM, Filip Paun <paunfi...@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 <jk...@cs.umd.edu> wrote: > >> > >> On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun <paunfi...@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 > > >
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
