Elgamal decryption failing using GnuPG generated key

[Alan Rushforth]

Hello,

I have generated a key pair using GnuPG and am trying to use Crypto++ to decrypt an Elgamal encrypted PGP message with the private key. I have extracted the p,g and x values from the private key and can use these to encrypt and decrypt arbitrary strings. However when ever I try to decrypt my encrypted PGP session key it fails. I get a DL_BadElement element exception. My problem is exactly the same as the one mentioned in the following post from 2003 but it doesn't look like he ever got an answer.

https://groups.google.com/d/topic/cryptopp-users/_NJoj8Dqtws/discussion

I am using Crypto++ 5.6.1. I have run crypttest and all the tests pass. I have also put the key and the message through http://www.pgpdump.net/  (it was only a test key) and have compared all the values to ensure I am extracting them correctly. The bit that fails seems to be the jacobi test on the first half of my cipher text and the modulus. It complains that it is not a quadratic residue. As I understand it this means that it isnt a very good key. It seems unlikely (but not impossible) that GnuPG would select a poor key but even if this is the case why does it stop me decrypting it?

I have tried validating the keys and they pass up to level 1 but fail on 2 and 3 as it says my q value (p/2) is not prime. Again it would seem odd for GnuPG to have selected a bad key. Is there another way that I can verify the key?

Any help on this would be greatly appreciated as I have been banging my head against it for days now.

And just to prempt the inevitable; i do have to use Elgamal  :)

Thanks,
Alan.

[Jeffrey Walton]

On Dec 16, 9:35 pm, Atif <atif1...@gmail.com> wrote:
> Hey Alan, wanted to see if you had any luck tracking down the issue.
So, there appears to be two issues here.

First is cyclic subgroup attacks due to Schnorr (also known as
confinement attacks). That means we don't necessarily have to choose p
= 2q + 1, but there is a limit on what we chose. For example, we can
chose p = 3q + 1 or p = 4q + 1. p = 2q + 1 just happens to be the
hardest case for the known attacks by generating the largest subgroup.
Also see the Pohlig-Hellman algorithm which attacks the subgroup's
structure.

In the past, I did some experimenting with the general form of p = qr
+ 1. I know Crypto++ will take the generalized parameters, and the
parameters will validate. See "Details Lost in Generation and
Initialization" at http://www.cryptopp.com/wiki/Diffie-Hellman.

Second is the choice of a "non-safe" or "non-strong" primes. We know
that some algorithms, such a Pollard's Rho, runs in time proportional
q - 1 (in, for example, p = 2q + 1). So I'm skeptical about PGP's
choice or selection of parameters.

Finally, a quick search of Google and Google Scholar did not turn up
ElGamal key requirements with non-safe primes. This is not surprising,
since we generally choose safe parameters.

In the end, I would probably file a bug report with PGP and have the
maintainers go on record with their rationale behind the choice of
parameters. It could be they have read a paper that states its not
necessary to use safe and strong primes, or its OK to have q - 1 non-
prime. Ask them to provide a reference.

Jeff

> On Thursday, May 17, 2012 11:25:00 AM UTC-4, Alan Rushforth wrote:
>
> > Hello,
>
> > I have generated a key pair using GnuPG and am trying to use Crypto++ to
> > decrypt an Elgamal encrypted PGP message with the private key. I have
> > extracted the p,g and x values from the private key and can use these to
> > encrypt and decrypt arbitrary strings. However when ever I try to decrypt
> > my encrypted PGP session key it fails. I get a DL_BadElement element
> > exception. My problem is exactly the same as the one mentioned in the
> > following post from 2003 but it doesn't look like he ever got an answer.
>
> >https://groups.google.com/d/topic/cryptopp-users/_NJoj8Dqtws/discussion
>
> > I am using Crypto++ 5.6.1. I have run crypttest and all the tests pass. I

> > have also put the key and the message throughhttp://www.pgpdump.net/

[Jeffrey Walton]

On Dec 16, 9:35 pm, Atif <atif1...@gmail.com> wrote:
> Hey Alan, wanted to see if you had any luck tracking down the issue.

After some more searching and a message on the Cryptography mailing
list (http://lists.randombit.net/pipermail/cryptography/2012-December/
003542.html), here is the documentation on generation:
http://www.gnupg.org/documentation/manuals/gcrypt/Prime_002dNumber_002dGenerator-Subsystem-Architecture.html
(thanks Adam Back).

GnuPG is using Lim-Lee primes from "A Key Recovery Attack on Discrete
Log-based Schemes Using a Prime Order Subgroup,"
http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.44.5296%26rep%3Drep1%26type%3Dpdf.

libgcrypt offers _gcry_derive_x931_prime and
_gcry_generate_fips186_2_prime to generate safe primes of the form p =
2q + 1.

Jeff

> On Thursday, May 17, 2012 11:25:00 AM UTC-4, Alan Rushforth wrote:
>

> > Hello,
>
> > I have generated a key pair using GnuPG and am trying to use Crypto++ to
> > decrypt an Elgamal encrypted PGP message with the private key. I have
> > extracted the p,g and x values from the private key and can use these to
> > encrypt and decrypt arbitrary strings. However when ever I try to decrypt
> > my encrypted PGP session key it fails. I get a DL_BadElement element
> > exception. My problem is exactly the same as the one mentioned in the
> > following post from 2003 but it doesn't look like he ever got an answer.
>
> >https://groups.google.com/d/topic/cryptopp-users/_NJoj8Dqtws/discussion
>
> > I am using Crypto++ 5.6.1. I have run crypttest and all the tests pass. I

> > have also put the key and the message throughhttp://www.pgpdump.net/

[Jeffrey Walton]

On Dec 16, 9:35 pm, Atif <atif1...@gmail.com> wrote:
> Hey Alan, wanted to see if you had any luck tracking down the issue.

So, you are going to love this (and please correct me if I am
wrong)....

Note Well (N.B.): the cited paper clearly states (Section 5),
"...therefore, our attack can be easily prevented if the relevant
protocol variables are properly checked". GnuPG is apparently using
Lim-Lee primes because libraries *don't* validate parameters. I'm not
sure if that's the GnuPG library, other libraries, or a combination.

Here, the traditional validation would include primality tests and
safe-prime checks, and verifying q is of the subgroup's order with a
modular exponentiation. The validation is required for a number of
real life protocols, and [what appears to] include GnuPG's corner
cases of ElGamal shared decryption and ElGamal shared verification.

To validate the GnuPG ElGamal key, you need to validate at level one
and then obtain the unique factorization of p (from Section 4 of the
paper: p = q p_1 p_2 p_3 ... p_n). You then need to ensure each p_i is
prime and |p_i| > l. l is approximately the size of q, and q is chosen
due to Schnorr's subgroup attacks. To obtain the unique factorization,
you can get it from the peer or factor it.

The concern here is *not* the "good case," where a honest actor
generates a Lim-Lee prime. The concerns are the "bad cases" when a
dishonest player generates or influences a purported Lim-Lee prime and
you can't easily validate the parameter. GnuPG made catching a
dishonest player orders of magnitude more difficult.

In the end, its probably easiest to reject GnuPG ElGamal keys and ask
for a traditional key that you can validate with customary methods.
The folks generating the keys should be happy to oblige since you are
performing the validation.

Jeff

> On Thursday, May 17, 2012 11:25:00 AM UTC-4, Alan Rushforth wrote:
>

> > Hello,
>
> > I have generated a key pair using GnuPG and am trying to use Crypto++ to
> > decrypt an Elgamal encrypted PGP message with the private key. I have
> > extracted the p,g and x values from the private key and can use these to
> > encrypt and decrypt arbitrary strings. However when ever I try to decrypt
> > my encrypted PGP session key it fails. I get a DL_BadElement element
> > exception. My problem is exactly the same as the one mentioned in the
> > following post from 2003 but it doesn't look like he ever got an answer.
>
> >https://groups.google.com/d/topic/cryptopp-users/_NJoj8Dqtws/discussion
>
> > I am using Crypto++ 5.6.1. I have run crypttest and all the tests pass. I

> > have also put the key and the message throughhttp://www.pgpdump.net/

[Atif]

Interesting.  So it may be the case that when the keys are generated by GnuPG we may not be able to use them to decrypt the session key with crypto++ because of the bad prime issue.  However if we use crypto++ to generate the keys, would we expect GnuPG to be able to use them? 

At the end of the day what I'm trying to do is generate an OpenPGP encrypted package using crypto++.  From the looks of things I'll have to implement OpenPGP's variant of CFB and get their binary format right, but all the tools exist in crypto++ to generate something compatible?

Thanks
-Atif

[Atif]

Morning guys, so after reading more of the documentation I found a reference to "PGP CFB mode (classes PGP_CFBEncryption and PGP_CFBDecryption)".  The wiki (http://cryptopp.com/wiki/User_Guide:_Header_Files) claims these modes are available in modes.h, however they don't seem to exist.  grep-ing through the rest of the code base didn't find any matches as well.

Perhaps they were in an older version of the library and were deprecated? Anyway just wanted to verify that I'm not missing something.  Their variant of CFB seems simple enough to implement.  Also I noticed there is a CFB_CipherAbstractPolicy class.  Is the CFB implementation in crypto++ configurable in some way?

Thanks
-Atif

[Jeffrey Walton]

On Dec 20, 12:34 pm, Atif <atif1...@gmail.com> wrote:
> Morning guys, so after reading more of the documentation I found a
> reference to "PGP CFB mode (classes PGP_CFBEncryption and PGP_CFBDecryption)".
> The wiki (http://cryptopp.com/wiki/User_Guide:_Header_Files) claims these
> modes are available in modes.h, however they don't seem to exist.  grep-ing
> through the rest of the code base didn't find any matches as well.
>
> Perhaps they were in an older version of the library and were deprecated?

Yes, they look like Crypto++ 4.2 or earlier (perhaps much earlier). A
lot of things changed at Crypto++ 5.0.

Grepping the SVN logs (svn log -v | grep -i PGP_CFBDecryption)
returned no hits.

Crypto++ does not have a proper change log, so it will take some
digging to find when they were deprecated or removed.

Jeff

[Jeffrey Walton]

On Dec 19, 10:53 pm, Atif <atif1...@gmail.com> wrote:
> Interesting.  So it may be the case that when the keys are generated by
> GnuPG we may not be able to use them to decrypt the session key with
> crypto++ because of the bad prime issue.

You can use them, but you likely cannot validate them. Use them at
your own peril. Personally, I would reject them and stop processing.

I did not analyze the use cases too much, so take this with a grain of
salt... If you have a secret, *do not* apply your secret to their key
(since their key is not validated). If someone else has applied their
secret to their key, you may be able to use the result. But in the
case of a bad key, I would think the data could have been tampered. So
make sure there are authenticity assurances (i.e., a signature) on the
encrypted data. Obviously, if its a ElGamal signature over the
encrypted data based on a Lim-Lee prime, then you are back to your
original problem.

According to Werner Kock, secring.pgp up-to version 1.4.1 used to
include the unique factorization. But it was removed some 7 years ago.

> However if we use crypto++ to
> generate the keys, would we expect GnuPG to be able to use them?

It appears GnuPG would happily use them since it looks like it does
not validate its keys. If GnuPG validated its keys, it would fail for
those keys based on Lim-Lee primes.

That's probably the best course of action: generate your keys with
Crypto++, and then import them into GnuPG for use. Anything that comes
out of GnuPG can then be validated, including the original Crypto++
key.

> At the end of the day what I'm trying to do is generate an OpenPGP
> encrypted package using crypto++.  From the looks of things I'll have to
> implement OpenPGP's variant of CFB and get their binary format right, but
> all the tools exist in crypto++ to generate something compatible?

I did not look into this problem. It's probably just CFB with a
different feedback size (Crypto++ uses the cipher's block size by
default, IIRC). I've seen similar interop issues with, for example,
mcrypt.

If its just feedback size, then the necessary steps are examined here:
http://www.codeproject.com/Articles/21877/Applied-Crypto-Block-Ciphers.
It needs to be moved to the Crypto++ wiki. Its been on my TODO list
for years :(

Jeff

[Jeffrey Walton]

The wiki has been updated with the information, so future information
hunters can find it at http://www.cryptopp.com/wiki/Keys_and_Formats#Validating_Keys.