a22394de84b833bf9e391c4347f72aaf96500d8b
[gnupg.git] / g10 / key-check.c
1 /* key-check.c - Detect and fix various problems with keys
2  * Copyright (C) 1998-2010 Free Software Foundation, Inc.
3  * Copyright (C) 1998-2017 Werner Koch
4  * Copyright (C) 2015-2017 g10 Code GmbH
5  *
6  * This file is part of GnuPG.
7  *
8  * GnuPG is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * GnuPG is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, see <https://www.gnu.org/licenses/>.
20  */
21
22 #include <config.h>
23
24 #include "gpg.h"
25 #include "options.h"
26 #include "packet.h"
27 #include "keydb.h"
28 #include "main.h"
29 #include "../common/ttyio.h"
30 #include "../common/i18n.h"
31 #include "keyedit.h"
32
33 #include "key-check.h"
34
35 /* Order two signatures.  The actual ordering isn't important.  Our
36    goal is to ensure that identical signatures occur together.  */
37 static int
38 sig_comparison (const void *av, const void *bv)
39 {
40   const KBNODE an = *(const KBNODE *) av;
41   const KBNODE bn = *(const KBNODE *) bv;
42   const PKT_signature *a;
43   const PKT_signature *b;
44   int ndataa;
45   int ndatab;
46   int i;
47
48   log_assert (an->pkt->pkttype == PKT_SIGNATURE);
49   log_assert (bn->pkt->pkttype == PKT_SIGNATURE);
50
51   a = an->pkt->pkt.signature;
52   b = bn->pkt->pkt.signature;
53
54   if (a->digest_algo < b->digest_algo)
55     return -1;
56   if (a->digest_algo > b->digest_algo)
57     return 1;
58
59   ndataa = pubkey_get_nsig (a->pubkey_algo);
60   ndatab = pubkey_get_nsig (b->pubkey_algo);
61   if (ndataa != ndatab)
62     return (ndataa < ndatab)? -1 : 1;
63
64   for (i = 0; i < ndataa; i ++)
65     {
66       int c = gcry_mpi_cmp (a->data[i], b->data[i]);
67       if (c != 0)
68         return c;
69     }
70
71   /* Okay, they are equal.  */
72   return 0;
73 }
74
75 /* Perform a few sanity checks on a keyblock is okay and possibly
76    repair some damage.  Concretely:
77
78      - Detect duplicate signatures and remove them.
79
80      - Detect out of order signatures and relocate them (e.g., a sig
81        over user id X located under subkey Y).
82
83    Note: this function does not remove signatures that don't belong or
84    components that are not signed!  (Although it would be trivial to
85    do so.)
86
87    If ONLY_SELFSIGS is true, then this function only reorders self
88    signatures (it still checks all signatures for duplicates,
89    however).
90
91    Returns 1 if the keyblock was modified, 0 otherwise.  */
92 int
93 key_check_all_keysigs (ctrl_t ctrl, kbnode_t kb,
94                        int only_selected, int only_selfsigs)
95 {
96   gpg_error_t err;
97   PKT_public_key *pk;
98   KBNODE n, n_next, *n_prevp, n2;
99   char *pending_desc = NULL;
100   PKT_public_key *issuer;
101   KBNODE last_printed_component;
102   KBNODE current_component = NULL;
103   int dups = 0;
104   int missing_issuer = 0;
105   int reordered = 0;
106   int bad_signature = 0;
107   int missing_selfsig = 0;
108   int modified = 0;
109
110   log_assert (kb->pkt->pkttype == PKT_PUBLIC_KEY);
111   pk = kb->pkt->pkt.public_key;
112
113   /* First we look for duplicates.  */
114   {
115     int nsigs;
116     kbnode_t *sigs;
117     int i;
118     int last_i;
119
120     /* Count the sigs.  */
121     for (nsigs = 0, n = kb; n; n = n->next)
122       {
123         if (is_deleted_kbnode (n))
124           continue;
125         else if (n->pkt->pkttype == PKT_SIGNATURE)
126           nsigs ++;
127       }
128
129     if (!nsigs)
130       return 0; /* No signatures at all.  */
131
132     /* Add them all to the SIGS array.  */
133     sigs = xtrycalloc (nsigs, sizeof *sigs);
134     if (!sigs)
135       {
136         log_error (_("error allocating memory: %s\n"),
137                    gpg_strerror (gpg_error_from_syserror ()));
138         return 0;
139       }
140
141     i = 0;
142     for (n = kb; n; n = n->next)
143       {
144         if (is_deleted_kbnode (n))
145           continue;
146
147         if (n->pkt->pkttype != PKT_SIGNATURE)
148           continue;
149
150         sigs[i] = n;
151         i ++;
152       }
153     log_assert (i == nsigs);
154
155     qsort (sigs, nsigs, sizeof (sigs[0]), sig_comparison);
156
157     last_i = 0;
158     for (i = 1; i < nsigs; i ++)
159       {
160         log_assert (sigs[last_i]);
161         log_assert (sigs[last_i]->pkt->pkttype == PKT_SIGNATURE);
162         log_assert (sigs[i]);
163         log_assert (sigs[i]->pkt->pkttype == PKT_SIGNATURE);
164
165         if (sig_comparison (&sigs[last_i], &sigs[i]) == 0)
166           /* They are the same.  Kill the latter.  */
167           {
168             if (DBG_PACKET)
169               {
170                 PKT_signature *sig = sigs[i]->pkt->pkt.signature;
171
172                 log_debug ("Signature appears multiple times, "
173                            "deleting duplicate:\n");
174                 log_debug ("  sig: class 0x%x, issuer: %s,"
175                            " timestamp: %s (%lld), digest: %02x %02x\n",
176                            sig->sig_class, keystr (sig->keyid),
177                            isotimestamp (sig->timestamp),
178                            (long long) sig->timestamp,
179                            sig->digest_start[0], sig->digest_start[1]);
180               }
181
182             /* Remove sigs[i] from the keyblock.  */
183             {
184               KBNODE z, *prevp;
185               int to_kill = last_i;
186               last_i = i;
187
188               for (prevp = &kb, z = kb; z; prevp = &z->next, z = z->next)
189                 if (z == sigs[to_kill])
190                   break;
191
192               *prevp = sigs[to_kill]->next;
193
194               sigs[to_kill]->next = NULL;
195               release_kbnode (sigs[to_kill]);
196               sigs[to_kill] = NULL;
197
198               dups ++;
199               modified = 1;
200             }
201           }
202         else
203           last_i = i;
204       }
205
206     xfree (sigs);
207   }
208
209   /* Make sure the sigs occur after the component (public key, subkey,
210      user id) that they sign.  */
211   issuer = NULL;
212   last_printed_component = NULL;
213   for (n_prevp = &kb, n = kb;
214        n;
215        /* If we moved n, then n_prevp is need valid.  */
216        n_prevp = (n->next == n_next ? &n->next : n_prevp), n = n_next)
217     {
218       PACKET *p;
219       int processed_current_component;
220       PKT_signature *sig;
221       int rc;
222       int dump_sig_params = 0;
223
224       n_next = n->next;
225
226       if (is_deleted_kbnode (n))
227         continue;
228
229       p = n->pkt;
230
231       if (issuer && issuer != pk)
232         {
233           free_public_key (issuer);
234           issuer = NULL;
235         }
236
237       xfree (pending_desc);
238       pending_desc = NULL;
239
240       switch (p->pkttype)
241         {
242         case PKT_PUBLIC_KEY:
243           log_assert (p->pkt.public_key == pk);
244           if (only_selected && ! (n->flag & NODFLG_SELKEY))
245             {
246               current_component = NULL;
247               break;
248             }
249
250           if (DBG_PACKET)
251             log_debug ("public key %s: timestamp: %s (%lld)\n",
252                        pk_keyid_str (pk),
253                        isotimestamp (pk->timestamp),
254                        (long long) pk->timestamp);
255           current_component = n;
256           break;
257         case PKT_PUBLIC_SUBKEY:
258           if (only_selected && ! (n->flag & NODFLG_SELKEY))
259             {
260               current_component = NULL;
261               break;
262             }
263
264           if (DBG_PACKET)
265             log_debug ("subkey %s: timestamp: %s (%lld)\n",
266                        pk_keyid_str (p->pkt.public_key),
267                        isotimestamp (p->pkt.public_key->timestamp),
268                        (long long) p->pkt.public_key->timestamp);
269           current_component = n;
270           break;
271         case PKT_USER_ID:
272           if (only_selected && ! (n->flag & NODFLG_SELUID))
273             {
274               current_component = NULL;
275               break;
276             }
277
278           if (DBG_PACKET)
279             log_debug ("user id: %s\n",
280                        p->pkt.user_id->attrib_data
281                        ? "[ photo id ]"
282                        : p->pkt.user_id->name);
283           current_component = n;
284           break;
285         case PKT_SIGNATURE:
286           if (! current_component)
287             /* The current component is not selected, don't check the
288                sigs under it.  */
289             break;
290
291           sig = n->pkt->pkt.signature;
292
293           pending_desc = xasprintf ("  sig: class: 0x%x, issuer: %s,"
294                                     " timestamp: %s (%lld), digest: %02x %02x",
295                                     sig->sig_class,
296                                     keystr (sig->keyid),
297                                     isotimestamp (sig->timestamp),
298                                     (long long) sig->timestamp,
299                                     sig->digest_start[0], sig->digest_start[1]);
300
301
302           if (keyid_cmp (pk_keyid (pk), sig->keyid) == 0)
303             issuer = pk;
304           else /* Issuer is a different key.  */
305             {
306               if (only_selfsigs)
307                 continue;
308
309               issuer = xmalloc (sizeof (*issuer));
310               err = get_pubkey (ctrl, issuer, sig->keyid);
311               if (err)
312                 {
313                   xfree (issuer);
314                   issuer = NULL;
315                   if (DBG_PACKET)
316                     {
317                       if (pending_desc)
318                         log_debug ("%s", pending_desc);
319                       log_debug ("    Can't check signature allegedly"
320                                  " issued by %s: %s\n",
321                                  keystr (sig->keyid), gpg_strerror (err));
322                     }
323                   missing_issuer ++;
324                   break;
325                 }
326             }
327
328           if ((err = openpgp_pk_test_algo (sig->pubkey_algo)))
329             {
330               if (DBG_PACKET && pending_desc)
331                 log_debug ("%s", pending_desc);
332               tty_printf (_("can't check signature with unsupported"
333                             " public-key algorithm (%d): %s.\n"),
334                           sig->pubkey_algo, gpg_strerror (err));
335               break;
336             }
337           if ((err = openpgp_md_test_algo (sig->digest_algo)))
338             {
339               if (DBG_PACKET && pending_desc)
340                 log_debug ("%s", pending_desc);
341               tty_printf (_("can't check signature with unsupported"
342                             " message-digest algorithm %d: %s.\n"),
343                           sig->digest_algo, gpg_strerror (err));
344               break;
345             }
346
347           /* We iterate over the keyblock.  Most likely, the matching
348              component is the current component so always try that
349              first.  */
350           processed_current_component = 0;
351           for (n2 = current_component;
352                n2;
353                n2 = (processed_current_component ? n2->next : kb),
354                  processed_current_component = 1)
355             if (is_deleted_kbnode (n2))
356               continue;
357             else if (processed_current_component && n2 == current_component)
358               /* Don't process it twice.  */
359               continue;
360             else
361               {
362                 err = check_signature_over_key_or_uid (ctrl,
363                                                        issuer, sig, kb, n2->pkt,
364                                                        NULL, NULL);
365                 if (! err)
366                   break;
367               }
368
369           /* n/sig is a signature and n2 is the component (public key,
370              subkey or user id) that it signs, if any.
371              current_component is that component that it appears to
372              apply to (according to the ordering).  */
373
374           if (current_component == n2)
375             {
376               if (DBG_PACKET)
377                 {
378                   log_debug ("%s", pending_desc);
379                   log_debug ("    Good signature over last key or uid!\n");
380                 }
381
382               rc = 0;
383             }
384           else if (n2)
385             {
386               log_assert (n2->pkt->pkttype == PKT_USER_ID
387                           || n2->pkt->pkttype == PKT_PUBLIC_KEY
388                           || n2->pkt->pkttype == PKT_PUBLIC_SUBKEY);
389
390               if (DBG_PACKET)
391                 {
392                   log_debug ("%s", pending_desc);
393                   log_debug ("    Good signature out of order!"
394                              "  (Over %s (%d) '%s')\n",
395                              n2->pkt->pkttype == PKT_USER_ID
396                              ? "user id"
397                              : n2->pkt->pkttype == PKT_PUBLIC_SUBKEY
398                              ? "subkey"
399                              : "primary key",
400                              n2->pkt->pkttype,
401                              n2->pkt->pkttype == PKT_USER_ID
402                              ? n2->pkt->pkt.user_id->name
403                              : pk_keyid_str (n2->pkt->pkt.public_key));
404                 }
405
406               /* Reorder the packets: move the signature n to be just
407                  after n2.  */
408
409               /* Unlink the signature.  */
410               log_assert (n_prevp);
411               *n_prevp = n->next;
412
413               /* Insert the sig immediately after the component.  */
414               n->next = n2->next;
415               n2->next = n;
416
417               reordered ++;
418               modified = 1;
419
420               rc = 0;
421             }
422           else
423             {
424               if (DBG_PACKET)
425                 {
426                   log_debug ("%s", pending_desc);
427                   log_debug ("    Bad signature.\n");
428                 }
429
430               if (DBG_PACKET)
431                 dump_sig_params = 1;
432
433               bad_signature ++;
434
435               rc = GPG_ERR_BAD_SIGNATURE;
436             }
437
438           /* We don't cache the result here, because we haven't
439              completely checked that the signature is legitimate.  For
440              instance, if we have a revocation certificate on Alice's
441              key signed by Bob, the signature may be good, but we
442              haven't checked that Bob is a designated revoker.  */
443           /* cache_sig_result (sig, rc); */
444
445           {
446             int has_selfsig = 0;
447             if (! rc && issuer == pk)
448               {
449                 if (n2->pkt->pkttype == PKT_PUBLIC_KEY
450                     && (/* Direct key signature.  */
451                         sig->sig_class == 0x1f
452                         /* Key revocation signature.  */
453                         || sig->sig_class == 0x20))
454                   has_selfsig = 1;
455                 if (n2->pkt->pkttype == PKT_PUBLIC_SUBKEY
456                     && (/* Subkey binding sig.  */
457                         sig->sig_class == 0x18
458                         /* Subkey revocation sig.  */
459                         || sig->sig_class == 0x28))
460                   has_selfsig = 1;
461                 if (n2->pkt->pkttype == PKT_USER_ID
462                     && (/* Certification sigs.  */
463                         sig->sig_class == 0x10
464                         || sig->sig_class == 0x11
465                         || sig->sig_class == 0x12
466                         || sig->sig_class == 0x13
467                         /* Certification revocation sig.  */
468                         || sig->sig_class == 0x30))
469                   has_selfsig = 1;
470               }
471
472             if ((n2 && n2 != last_printed_component)
473                 || (! n2 && last_printed_component != current_component))
474               {
475                 int is_reordered = n2 && n2 != current_component;
476                 if (n2)
477                   last_printed_component = n2;
478                 else
479                   last_printed_component = current_component;
480
481                 if (!modified)
482                   ;
483                 else if (last_printed_component->pkt->pkttype == PKT_USER_ID)
484                   {
485                     tty_printf ("uid  ");
486                     tty_print_utf8_string (last_printed_component
487                                            ->pkt->pkt.user_id->name,
488                                            last_printed_component
489                                            ->pkt->pkt.user_id->len);
490                   }
491                 else if (last_printed_component->pkt->pkttype
492                          == PKT_PUBLIC_KEY)
493                   tty_printf ("pub  %s",
494                               pk_keyid_str (last_printed_component
495                                             ->pkt->pkt.public_key));
496                 else
497                   tty_printf ("sub  %s",
498                               pk_keyid_str (last_printed_component
499                                             ->pkt->pkt.public_key));
500
501                 if (modified)
502                   {
503                     if (is_reordered)
504                       tty_printf (_(" (reordered signatures follow)"));
505                     tty_printf ("\n");
506                   }
507               }
508
509             if (modified)
510               keyedit_print_one_sig (ctrl, rc, kb, n, NULL, NULL, NULL,
511                                      has_selfsig, 0, only_selfsigs);
512           }
513
514           if (dump_sig_params)
515             {
516               int i;
517
518               for (i = 0; i < pubkey_get_nsig (sig->pubkey_algo); i ++)
519                 {
520                   char buffer[1024];
521                   size_t len;
522                   char *printable;
523                   gcry_mpi_print (GCRYMPI_FMT_USG,
524                                   buffer, sizeof (buffer), &len,
525                                   sig->data[i]);
526                   printable = bin2hex (buffer, len, NULL);
527                   log_info ("        %d: %s\n", i, printable);
528                   xfree (printable);
529                 }
530             }
531           break;
532         default:
533           if (DBG_PACKET)
534             log_debug ("unhandled packet: %d\n", p->pkttype);
535           break;
536         }
537     }
538
539   xfree (pending_desc);
540   pending_desc = NULL;
541
542   if (issuer != pk)
543     free_public_key (issuer);
544   issuer = NULL;
545
546   /* Identify keys / uids that don't have a self-sig.  */
547   {
548     int has_selfsig = 0;
549     PACKET *p;
550     PKT_signature *sig;
551
552     current_component = NULL;
553     for (n = kb; n; n = n->next)
554       {
555         if (is_deleted_kbnode (n))
556           continue;
557
558         p = n->pkt;
559
560         switch (p->pkttype)
561           {
562           case PKT_PUBLIC_KEY:
563           case PKT_PUBLIC_SUBKEY:
564           case PKT_USER_ID:
565             if (current_component && ! has_selfsig)
566               missing_selfsig ++;
567             current_component = n;
568             has_selfsig = 0;
569             break;
570
571           case PKT_SIGNATURE:
572             if (! current_component || has_selfsig)
573               break;
574
575             sig = n->pkt->pkt.signature;
576
577             if (! (sig->flags.checked && sig->flags.valid))
578               break;
579
580             if (keyid_cmp (pk_keyid (pk), sig->keyid) != 0)
581               /* Different issuer, couldn't be a self-sig.  */
582               break;
583
584             if (current_component->pkt->pkttype == PKT_PUBLIC_KEY
585                 && (/* Direct key signature.  */
586                     sig->sig_class == 0x1f
587                     /* Key revocation signature.  */
588                     || sig->sig_class == 0x20))
589               has_selfsig = 1;
590             if (current_component->pkt->pkttype == PKT_PUBLIC_SUBKEY
591                 && (/* Subkey binding sig.  */
592                     sig->sig_class == 0x18
593                     /* Subkey revocation sig.  */
594                     || sig->sig_class == 0x28))
595               has_selfsig = 1;
596             if (current_component->pkt->pkttype == PKT_USER_ID
597                 && (/* Certification sigs.  */
598                     sig->sig_class == 0x10
599                     || sig->sig_class == 0x11
600                     || sig->sig_class == 0x12
601                     || sig->sig_class == 0x13
602                     /* Certification revocation sig.  */
603                     || sig->sig_class == 0x30))
604               has_selfsig = 1;
605
606             break;
607
608           default:
609             if (current_component && ! has_selfsig)
610               missing_selfsig ++;
611             current_component = NULL;
612           }
613       }
614   }
615
616   if (dups || missing_issuer || bad_signature || reordered)
617     tty_printf (_("key %s:\n"), pk_keyid_str (pk));
618
619   if (dups)
620     tty_printf (ngettext ("%d duplicate signature removed\n",
621                           "%d duplicate signatures removed\n", dups), dups);
622   if (missing_issuer)
623     tty_printf (ngettext ("%d signature not checked due to a missing key\n",
624                           "%d signatures not checked due to missing keys\n",
625                           missing_issuer), missing_issuer);
626   if (bad_signature)
627     tty_printf (ngettext ("%d bad signature\n",
628                           "%d bad signatures\n",
629                           bad_signature), bad_signature);
630   if (reordered)
631     tty_printf (ngettext ("%d signature reordered\n",
632                           "%d signatures reordered\n",
633                           reordered), reordered);
634
635   if (only_selfsigs && (bad_signature || reordered))
636     tty_printf (_("Warning: errors found and only checked self-signatures,"
637                   " run '%s' to check all signatures.\n"), "check");
638
639   return modified;
640 }