2

I have following requirement for software I'm working on:

Use strong asymmetric key exchange with public key size <16 bytes.

I know it is pretty hard for this amount of bytes, but I've came up with following solution and wanted some feedback:

Use Diffie Hellman Key Exchange algorithm with P (prime modulus) parameter <2^128, and then use some key derivation algorithm like pbkdf2 on generated shared secret to generate much stronger symmetric key, and use this key to encrypt any data passed.

I want to know if this will improve safety of such protocol compared to simple Diffie Hellman over 2^128.

Gregory
  • 21
  • 2
  • 3
    Where does this requirement come from? Is this from someone who wants to be able to break your encryption? – Paŭlo Ebermann Aug 28 '11 at 20:44
  • It's protection for software licensing, where appication is kept encrypted on hard drive and decrypted on the fly when starting an instance. The idea is, unless client has a licensing key generated by us, he is not able to crack (in this case decrypt) the application. – Gregory Aug 29 '11 at 04:52
  • 2
    OK. 1. Make sure you understand that it is inherently impossible to provide strong security. Generally, all you can do is introduce a speedbump (e.g., to keep honest people honest, and delay cracks of the copy protection scheme). No amount of sophisticated crypto-mathematics can change that. 2. My impression is that there is standard third-party software for software licensing. Have you considered just used that, rather than implementing your own? It might be cheaper. – D.W. Aug 29 '11 at 06:31
  • To add to @DW's post - have a read of http://security.stackexchange.com/questions/4637/are-there-drm-techniques-to-effectively-prevent-pirating for some more info on how difficult/impossible it is to prevent pirating. – Rory Alsop Aug 29 '11 at 10:14

2 Answers2

4

I don't think this is a good idea.

The problem in Diffie-Hellman key exchange is not the size of the generated key (this can be as big as required), but the need to authenticate one side to avoid man-in-the-middle attacks.

And this is the reason to have a public-key component at all - without this, DH could even work anonymously (and works, if you have only passive attackers to fear).

So, my idea would be to use standard (big-modulus) Diffie-Hellman, and authenticate the result with a public-key signature.

But then the problem with small asymmetric public keys is that it is not that hard to derive the corresponding private key from them (in the RSA case, factoring the modulus, in the DSA or Diffie-Hellman case: solving a discrete logarithm).

This needs to be done only once (for each key), and then the attacker can play man-in-the-middle for every following session authenticated with this key.

(Removed the last paragraph about ECC, since it was not really thought through, and I'm now to tired to do it right.)

Paŭlo Ebermann
  • 2,467
  • 19
  • 20
  • The last paragraph is not quite right. There are two parameters that matter: the size of the modulus, and the size of the exponent. They *both* need to be large enough. If you use a prime number modulus, the modulus probably should be around 2048 bits long or so. A 256-bit prime modulus is *totally insecure*. The exponent does not need to be as large. If the modulus is of adequate size, then a 256-bit exponent is adequate. A 109-bit exponent is not sufficient for good security, because it can be broken with about 2^55 work, regardless of the size of the modulus. – D.W. Aug 28 '11 at 23:11
  • @DW: thanks for the note. I'll read about it tomorrow and then try to put the right information here, for now I simply deleted this paragraph. – Paŭlo Ebermann Aug 28 '11 at 23:18
4

Your proposed scheme is highly insecure. Don't use it!

It is trivial to solve the discrete log problem modulo a 128-bit prime. Consequently, it is trivial to break Diffie-Hellman if you are using a 128-bit prime modulus. pbkdf2 won't save you from that attack.

Instead, here's what you should do. Use 127-bit elliptic curve cryptography (ECC) (i.e., working in a group of order around 2^127). Then, the public key can be represented in 127+1 = 128 bits, if you use point compression or similar methods. Now, you can do key exchange with this ECC group, using any accepted well-vetted ECC cryptosystem (e.g., ECMQV). Make sure you use authenticated key exchange, so that each party authenticates the other. Note that this will only provide approximately 63-bit security, so it does not provide strong security, but it may be enough for many purposes.

Do note that cryptography alone is usually not enough to solve all data security needs. To provide security, it will be necessary to examine the threats the system is likely to face and design a complete solution. Crypto isn't magic pixie dust that can single-handedly solve all your security problems; usually it has to be complemented by secure software design, secure development practices, and other security processes.

D.W.
  • 98,420
  • 30
  • 267
  • 572
  • 3
    You can make it a 128-bit curve by representing only the _X_ coordinate of the public key point. Since ECDH ends up with using only the resulting _X_ coordinate as shared secret, the missing bit on the public key does not matter (it would matter for ECDSA, though). – Thomas Pornin Aug 29 '11 at 02:03
  • Rumor has it that an effort at breaking an EC discrete logarithm on a 128-bit curve has begun in a handful of universities -- it will still take some time (years) to complete. – Thomas Pornin Aug 29 '11 at 02:05