[cryptography] Why using asymmetric crypto like symmetric crypto isn't secure

Hans-Joachim Knobloch hans-joachim.knobloch at secorvo.de
Wed Nov 14 06:04:56 EST 2012

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.


[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.knobloch at secorvo.de, http://www.secorvo.de
PGP: A766 A23F 1079 3075  DF18 56E0 F61F A8F8

Mannheim HRB 108319, Geschäftsführer: Dirk Fox

More information about the cryptography mailing list