<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body bgcolor="#ffffff" text="#000000">
I've been looking into writing a unit test for Elgamal. What I was
looking for were public test vectors. Those don't exist. What I
found instead is that our implementation of Elgamal appears
insecure.<br>
<br>
References:<br>
Crypto++ notes on Elgamal, <a class="moz-txt-link-freetext" href="http://weidai.com/scan-mirror/sig.html">http://weidai.com/scan-mirror/sig.html</a><br>
Crypto++ FAQ on Elgamal key generation,
<a class="moz-txt-link-freetext" href="http://www.cryptopp.com/fom-serve/cache/71.html">http://www.cryptopp.com/fom-serve/cache/71.html</a><br>
Bleichenbacher paper on forging Elgamal, <br>
<pre><a class="moz-txt-link-freetext" href="ftp://ftp.inf.ethz.ch/pub/crypto/publications/Bleich96.ps">ftp://ftp.inf.ethz.ch/pub/crypto/publications/Bleich96.ps</a>
IETF paper on DH groups, including pre-computed safe primes, <a class="moz-txt-link-freetext" href="http://tools.ietf.org/html/draft-ietf-ipsec-ike-modp-groups-04">http://tools.ietf.org/html/draft-ietf-ipsec-ike-modp-groups-04</a>
Wikipedia writeup on Elgamal, <a class="moz-txt-link-freetext" href="http://en.wikipedia.org/wiki/ElGamal_encryption">http://en.wikipedia.org/wiki/ElGamal_encryption</a>
What I have found is that pycrypto's Elgamal implementation is, shall we say, naive. Specifically in these regards (and I'll quote others here, these assertions as per crypto safety are not
mine. The conclusions about elgamal.py are mine):
<i>- p</i> SHOULD be a safe prime, i.e. such that (<i>p</i>-1)/2 is prime
TB: elgamal.py makes no effort to find a safe prime. elgamal.py does not allow the user to pass her own safe prime to the key generator.
- The paper by Bleichenbacher referenced above shows that if <i>g</i> has only small prime factors, and if <i>g</i> divides the order of the group it generates, then signatures can be forged.
TB: elgamal.py makes no effort to find a safe "g"
- Elgamal encryption is not secure under chosen ciphertext attack. To achieve chosen-ciphertext security, the scheme must be further modified, or an appropriate padding scheme must be used.
TB: elgamal.py does not implement a padding scheme, or modify Elgamal further afaics.
So far on Elgamal. It makes me reluctant to go through with a unit test for Elgamal. I don't want to validate an implementation that is inherently insecure. Changing Elgamal to be more secure is out of scope of my current effort on the code base. I'll leave that to others.
The broader question that occurs, particularly also in view of the stdlib-crypto discussion (<a class="moz-txt-link-freetext" href="http://bugs.python.org/issue8998">http://bugs.python.org/issue8998</a>) is: What is pycrypto's intent? What should it be?
Should it be a low-level collection of crypto algorithms, suitable for academic and real work, and requiring a strong understanding of crypto and its complexities in either case, with no safeguards should a user choose to shoot himself in the foot?
Should it be a high-level collection of crypto routines, suitable for the crypto-naive coder, offering safe defaults and a few knobs to influence those parameters that should be able to be chosen by a slightly less crypto-naive coder? Note that this would require vigorous debate about what this second tier should look like, which defaults would be chosen, which knobs would still be exposed, and so on. That debate would have to be carried out in public and would have to include all the other movers-and-shakers in the Python crypto community.
Should it be both, offering a two-tiered API?
And further:
Should pycrypto continue to offer its own implementations of crypto algorithms? Or should it be a Python wrapper for existing implementations such as tomlib, Crypto++ or NSS, relying on those implementations to have been coded in a secure manner?
Thank you for reading
Thorsten
</pre>
</body>
</html>