lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening linuxcveannounce PHC  
Open Source and information security mailing list archives
 

Date: Sun, 14 Sep 2014 16:53:33 +0200 From: Thomas Pornin <pornin@...et.org> To: discussions@...swordhashing.net Subject: Re: [PHC] Improving Makwa and arguing points for or against On Sun, Sep 14, 2014 at 05:13:11AM 0500, Steve Thomas wrote: > Replacing e=2**n with e=65537**n also require gcd(65537, > (p1)*(q1))=1. This way you can say it's as safe as RSA. It would not make it "as safe as RSA" but "as unsafe as RSA". This is an old debate, between RSA and Rabin encryption systems. Rabin uses squarings modulo a Blum integer N. RSA uses an exponent e which is relatively prime to phi(N). For both systems, factoring N totally breaks the system; however, in the case of Rabin, it can be demonstrated that generic square root extraction modulo N _is_ equivalent to factoring N. No such demonstration exists for RSA. It is thus possible that there exists a method which breaks RSA without requiring modulus factorization (no such method is currently known, but it is not proven that such a method cannot exist). Thereby, Rabin encryption can be said to be at least as safe as RSA, and potentially safer. By relying on squarings instead of RSAlike exponentiations, I am reusing the safety of Rabin encryption, which is thus better (or at least no worse) then that of RSA. This has already been put to work: in a previous email, Bill was worried about "short cycles" in the permutation (squaring modulo a Blum integer is a permutation of the set of quadratic residues); thanks to the use of squarings, I could demonstrate that if short cycles can be found with nonnegligible probability, then they can be turned into an efficient factorization algorithm, which would imply that both Rabin and RSA encryption, as they are used today, are broken. This kind of demonstration is precisely why I want to use squarings instead of RSAlike exponentiations. Squarings are just better. Squarings also make for a simpler implementation. All other things being equal, simplicity is always better: it minimizes risks of bugs and of data leakage through timing attacks. Last but not least, using repeated squarings is an instance of the "timelock puzzles" of Rivest, Shamir and Wagner (1996). This is a process which has sustained the collective scrutiny of cryptographers for quite some time now, and nobody yet found a way to speed up a sequence of squarings (i.e. to obtain the result faster than doing all the squarings one after the other), save by factoring the modulus (and 2500+ years of research show that factoring is hard). This is a nice thing to have: apart from potential mathematical reduction proofs (like the equivalence between factorization and square root extraction), extensive review is the only way to know whether a given cryptographic function is secure or not. By comparison, "repeated RSAlike exponentiation" is an asyet unstudied and notreviewed problem. > I guess that's not really necessary since post hashing is now required. As I explain in another mail, this is a misconception. If you fear that the attacker learns the private factors p and q, then posthashing won't stop him; he still gets tremendous attack power from that knowledge. On the other hand, if he does _not_ know the factors p and q, then without posthashing he still faces the RivestShamirWagner timelock puzzle, which has no known speedup. Therefore, you must not consider posthashing as improving security with regards to the modulus factorization. The role of posthashing is to provide unbiased bytes in arbitrary numbers for when Makwa is used as a passwordbased KDF (usually for passwordbased encryption); incidentally, posthashing also allows for a reduced storage space in password verification scenario, but at a price (it prevents smooth offline work factor increase). > whether we can prevent the author from saying "you could keep p and q > for fast path". Ah, shutting me up... some have tried. Thomas Pornin
Powered by blists  more mailing lists