gpg format(s) emits false positives

[magnumripper]

Fix if possible. Otherwise set FMT_NOT_EXACT.

[magnumripper]

Actually, I got a report from that off-list guy saying he got 42,000 false positives in two days. That's probably bad enough that we should kick these formats to broken/ until they are fixed :-(

[kholia]

I can't find the link now, but we had a similar report previously too. IIRC, we deduced that such keys were "peculiar" and didn't have sufficient information to rule out the false positives. Do you remember this case?

[magnumripper]

Aha, so you mean it won't normally happen? I can't remember the previous case.

[kholia]

A "normal" SHA1-CAST5 DSA key hash looks like $gpg$*17*42*1024*d974ae70cfbf8ab05... but these shorter keys look like $gpg$*17*24*1024*.... Notice that cs.datalen value (24) is less in the second case.

Maybe we can hack static int check(unsigned char *keydata, int ks) further to handle such keys properly. I can look into it (I need some sample keys to start with).

[magnumripper]

Found the previous case: http://www.openwall.com/lists/john-users/2012/12/16/1

[kholia]

Cool. It seems that it is possible to borrow some code from GnuPG to rule out such false positives.

[magnumripper]

That would be awesome. BTW, FMT_NOT_EXACT was originally meant to be used for cases where the positives are actually usable - like for a crc32 hash collision.

[kholia]

https://tools.ietf.org/html/rfc4880 says,

The two-octet checksum that follows the algorithm-specific portion is
the algebraic sum, mod 65536, of the plaintext of all the algorithm-
specific octets (including MPI prefix and data).  With V3 keys, the
checksum is stored in the clear.  With V4 keys, the checksum is
encrypted like the algorithm-specific data.  This value is used to
check that the passphrase was correct.  However, this checksum is
deprecated; an implementation SHOULD NOT use it, but should rather
use the SHA-1 hash denoted with a usage octet of 254.  The reason for
this is that there are some attacks that involve undetectably
modifying the secret key.

[kholia]

To generate these shorter keys (which look like $gpg$*17*24*1024*....), one can use GnuPG 1.0.3 from https://bitbucket.org/dhiru/gnupg-1.0.3-fixed/ URL.

We now have all the information to solve this problem.

[kholia]

The following patch reduces false positives but still break at some point.

diff --git a/src/gpg_fmt_plug.c b/src/gpg_fmt_plug.c
index cc22c4c..2f0570c 100644
--- a/src/gpg_fmt_plug.c
+++ b/src/gpg_fmt_plug.c
@@ -27,6 +27,7 @@
 #include <openssl/ripemd.h>
 #include <openssl/cast.h>
 #include <openssl/bn.h>
+#include <openssl/dsa.h>
 #ifdef _OPENMP
 #include <omp.h>
 #define OMP_SCALE               64
@@ -828,11 +829,12 @@ static int check(unsigned char *keydata, int ks)
                                  SHA1_Update(&ctx, out, cur_salt->datalen - SHA_DIGEST_LENGTH);
                                  SHA1_Final(checksum, &ctx);
                                  if (memcmp(checksum, out + cur_salt->datalen - SHA_DIGEST_LENGTH, SHA_DIGEST_LENGTH) == 0) {
-                                         checksumOk = 1;
+                                         return 1;  /* we have a 20 byte verifier ;) */
                                  }
                          } break;
                case 0:
                case 255: {
+                                 // https://tools.ietf.org/html/rfc4880#section-3.7.2
                                  uint16_t sum = 0;
                                  for (i = 0; i < cur_salt->datalen - 2; i++) {
                                          sum += out[i];
@@ -848,7 +850,15 @@ static int check(unsigned char *keydata, int ks)
        if (checksumOk) {
                BIGNUM *b = NULL;
                uint32_t blen = (num_bits + 7) / 8;
+               if (cur_salt->datalen == 24 && blen != 20)  /* verifier 1 */
+                       return 0;
                if (blen < cur_salt->datalen && ((b = BN_bin2bn(out + 2, blen, NULL)) != NULL)) {
+                       char *str = BN_bn2hex(b);
+                       /* blen * 2 == 40 when blen is 20 */
+                       if (strlen(BN_bn2hex(b)) != 40) { /* verifier 2 */
+                               free(str);
+                               return 0;
+                       }
                        BN_free(b);
                        return 1;
                }

GnuPG doesn't have this problem because it does proper DSA verification math.

In order to solve this problem, we will need to extract more data from the GPG key files. Let me see if we can do it without breaking the existing hashes.