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

Jon Callas jon at callas.org
Sat Nov 3 17:29:50 EDT 2012

> In the past there have been a few proposals to use asymmetric cryptosystems,
> typically RSA, like symmetric ones by keeping the public key secret, the idea
> behind this being that if the public key isn't known then there isn't anything
> for an attacker to factor or otherwise attack.  Turns out that doing this
> isn't secure:
>  http://eprint.iacr.org/2012/588
>  Breaking Public Keys - How to Determine an Unknown RSA Public Modulus
>  Hans-Joachim Knobloch
>  [...] We show that if the RSA cryptosystem is used in such a symmetric
>  application, it is possible to determine the public RSA modulus if the
>  public exponent is known and short, such as 3 or F4=65537, and two or more
>  plaintext/ciphertext (or, if RSA is used for signing, signed
>  value/signature) pairs are known.

Great paper, however, the conclusions here and in replies are not quite right. The paper itself says,

it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, 

Which immediately prompts the question of "what if it's long or secret?" [1] This attack doesn't work on that.

What it tells you is that if for some strange reason, you are going to keep the public key secret, you need to make the exponent part of the secret. That's the real, real lesson here -- an RSA key has an exponent and a modulus and unless the exponent is secret, the key isn't secret. And of course secret doesn't mean the usual ones just put in a cabinet.

And for us logic weenies, he does not show that a secret public key is insecure. He shows that there is no added security for secret public keys where the exponent is known and short. Those keys are just as secure as they would be if they had known public keys (which could be not at all).

The danger is not using a public key algorithm in a novel way, it's using it in a novel way and thinking that your intuition is correct. It's thinking through the consequences of your actions.

If you believe that the only attack against RSA is factoring the modulus, then you can be seduced into thinking that hiding the modulus makes the attacker's job harder. The brilliance of this paper is that is concisely shows that unless you take care is selecting an exponent, the modulus leaks easily. 

Obviously, a secret public key isn't *less* secure. (The reductio ad absurdum is left as an exercise for the reader.) It must be as secure or greater. But if it's greater, by how much and how would you know? If you can't answer that question, or at least handwave in the direction of an answer.

If you don't have a lower bound on the improved security of that tweak, then you should consider it to be zero. This is why although it's still left open as to whether a truly secret public key adds security, we should assume there's no added security.

The engineering dope-slapping that needs to happen is over getting distracted. Security systems are designed to meet certain assumptions. Changing the assumptions changes the result. Public-key cryptosystems are designed in such a way that the public key is a public parameter. They are not designed to have added security when the public key is secret. This paper shows a case in which there is no added security, and as a matter of fact, the modulus leaks from the ciphertext.

If you want to make the public key secret, you have to do more work and there's no indication of how much added security there is -- it could be zero. No one has ever done a keygen with any work done into considering the care you need to make the exponent be a secret parameter. On the contrary, it's usually a quasi-constant.

All that added work could be put somewhere else, and as we all know there's plenty of ways to induce bugs by doing the extra work. Therefore, in the words of Elvis Costello, don't get cute. If you use reasonable parameters in off-the-shelf subsystems, you work just fine. Getting cute at best adds in some undefinable bit of good-feeling, which isn't the same thing as security.


[1] Operationally, long or secret will be long *and* secret because there are no commonly used long exponents, and all the common exponents are short. Phrased another way, the short exponents are easily iterated over.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20121103/ddbb0f1b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20121103/ddbb0f1b/attachment.sig>

More information about the cryptography mailing list