On 11.11.2012 14:13, Adam Back wrote: > Note they are only saying fixed or small e because their approach requires > to know or guess e in order to compute m^e (if e is small you can try all > possible e). > I wouldnt think thats the end of it either - more things are clearly > leaking. eg Even with large, unknown e st |e| = |n| if you had known > plaintext ciphertext pairs with a multiplicative relationship like c1 = > m1^e > mod n, and c2 = m2^e mod n and c3 = m3^e mod n where m3 = m1*m2. Then > c1*c2-c3 = k.n and we're back to the find small factors to find k trick.
Thank you very much for pointing that out. I also have the feeling that there are ways to extend the simple basic idea presented in the paper to other scenarios like large secret exponents or maybe PKCS#1-v1.5 encryption[1] but did not yet pursue that. Even the simple attack is a positive proof that the bad gut feeling about using RSA with a secret 64 bit modulus (in a place where something like Triple-DES would be quite sufficient) was not unjustified. And it covers the cases that are in my opinion the main practical risk, namely system designers tempted to use standard public key libraries for the described symmetric purposes in straight-forward way. Arjen Lenstra et al. in "Ron was wrong, Whit is right" (http://eprint.iacr.org/2012/064) tell us, >95% of all practical RSA exponents to be found on the Internet are 65537 while the overwhelming part of the rest is even smaller. So system designers who use something else than RSA with e=65537 will with a good probability have made a concious decision and invested some more thought about the crypto they are using (at least that is what I would hope). Then again, as Jon Callas correctly concluded, the additional work to invest in assuring that such an usual scheme is secure might be more economically put into other parts of system design. Hans-Joachim [1] My footnote (sorry, Peter, couldn't resist): Note that PKCS#1-v1.5 signature padding is deterministic, i. e. using RSA with short secret modulus as a private integrity mechanism for data deposited in the hands of other parties (in other words: cookies) in place of a symmetric MAC would also be susceptible to the simple attack. As James Muir pointed out, using OAEP/PSS with enough salt would prevent that. But way too many users/applications like DNSSEC still use PKCS#1-v1.5. -- -------------------------------------------------------- Hans-Joachim Knobloch Security Consulting Secorvo Security Consulting GmbH Ettlinger Strasse 12-14, D-76137 Karlsruhe Tel. +49 721 255171-305, Fax +49 721 255171-100 hans-joachim.knobl...@secorvo.de, http://www.secorvo.de PGP: A766 A23F 1079 3075 DF18 56E0 F61F A8F8 Mannheim HRB 108319, Geschäftsführer: Dirk Fox _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
