ff218ad80ce811181a86c7106dce246eb39b1173
[gnupg.git] / g10 / trustdb.c
1 /* trustdb.c
2  * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
3  *               2007 Free Software Foundation, Inc.
4  *
5  * This file is part of GnuPG.
6  *
7  * GnuPG is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 3 of the License, or
10  * (at your option) any later version.
11  *
12  * GnuPG is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, see <http://www.gnu.org/licenses/>.
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <assert.h>
26
27 #ifndef DISABLE_REGEX
28 #include <sys/types.h>
29 #include <regex.h>
30 #endif /* !DISABLE_REGEX */
31
32 #include "gpg.h"
33 #include "status.h"
34 #include "iobuf.h"
35 #include "keydb.h"
36 #include "util.h"
37 #include "options.h"
38 #include "packet.h"
39 #include "main.h"
40 #include "i18n.h"
41 #include "tdbio.h"
42 #include "trustdb.h"
43
44
45 /*
46  * A structure to store key identification as well as some stuff needed
47  * for validation 
48  */
49 struct key_item {
50   struct key_item *next;
51   unsigned int ownertrust,min_ownertrust;
52   byte trust_depth;
53   byte trust_value;
54   char *trust_regexp;
55   u32 kid[2];
56 };
57
58
59 typedef struct key_item **KeyHashTable; /* see new_key_hash_table() */
60
61 /*
62  * Structure to keep track of keys, this is used as an array wherre
63  * the item right after the last one has a keyblock set to NULL. 
64  * Maybe we can drop this thing and replace it by key_item
65  */
66 struct key_array {
67   KBNODE keyblock;
68 };
69
70
71 /* control information for the trust DB */
72 static struct {
73     int init;
74     int level;
75     char *dbname;
76 } trustdb_args;
77
78 /* some globals */
79 static struct key_item *user_utk_list; /* temp. used to store --trusted-keys */
80 static struct key_item *utk_list;      /* all ultimately trusted keys */
81
82 static int pending_check_trustdb;
83
84 static int validate_keys (int interactive);
85
86 \f
87 /**********************************************
88  ************* some helpers *******************
89  **********************************************/
90
91 static struct key_item *
92 new_key_item (void)
93 {
94   struct key_item *k;
95   
96   k = xmalloc_clear (sizeof *k);
97   return k;
98 }
99
100 static void
101 release_key_items (struct key_item *k)
102 {
103   struct key_item *k2;
104
105   for (; k; k = k2)
106     {
107       k2 = k->next;
108       xfree (k->trust_regexp);
109       xfree (k);
110     }
111 }
112
113 /*
114  * For fast keylook up we need a hash table.  Each byte of a KeyIDs
115  * should be distributed equally over the 256 possible values (except
116  * for v3 keyIDs but we consider them as not important here). So we
117  * can just use 10 bits to index a table of 1024 key items. 
118  * Possible optimization: Don not use key_items but other hash_table when the
119  * duplicates lists gets too large. 
120  */
121 static KeyHashTable 
122 new_key_hash_table (void)
123 {
124   struct key_item **tbl;
125
126   tbl = xmalloc_clear (1024 * sizeof *tbl);
127   return tbl;
128 }
129
130 static void
131 release_key_hash_table (KeyHashTable tbl)
132 {
133   int i;
134
135   if (!tbl)
136     return;
137   for (i=0; i < 1024; i++)
138     release_key_items (tbl[i]);
139   xfree (tbl);
140 }
141
142 /* 
143  * Returns: True if the keyID is in the given hash table
144  */
145 static int
146 test_key_hash_table (KeyHashTable tbl, u32 *kid)
147 {
148   struct key_item *k;
149
150   for (k = tbl[(kid[1] & 0x03ff)]; k; k = k->next)
151     if (k->kid[0] == kid[0] && k->kid[1] == kid[1])
152       return 1;
153   return 0;
154 }
155
156 /*
157  * Add a new key to the hash table.  The key is identified by its key ID.
158  */
159 static void
160 add_key_hash_table (KeyHashTable tbl, u32 *kid)
161 {
162   struct key_item *k, *kk;
163
164   for (k = tbl[(kid[1] & 0x03ff)]; k; k = k->next)
165     if (k->kid[0] == kid[0] && k->kid[1] == kid[1])
166       return; /* already in table */
167   
168   kk = new_key_item ();
169   kk->kid[0] = kid[0];
170   kk->kid[1] = kid[1];
171   kk->next = tbl[(kid[1] & 0x03ff)];
172   tbl[(kid[1] & 0x03ff)] = kk;
173 }
174
175 /*
176  * Release a key_array
177  */
178 static void
179 release_key_array ( struct key_array *keys )
180 {
181     struct key_array *k;
182
183     if (keys) {
184         for (k=keys; k->keyblock; k++)
185             release_kbnode (k->keyblock);
186         xfree (keys);
187     }
188 }
189
190 \f
191 /*********************************************
192  **********  Initialization  *****************
193  *********************************************/
194
195
196
197 /*
198  * Used to register extra ultimately trusted keys - this has to be done
199  * before initializing the validation module.
200  * FIXME: Should be replaced by a function to add those keys to the trustdb.
201  */
202 void
203 register_trusted_keyid(u32 *keyid)
204 {
205   struct key_item *k;
206
207   k = new_key_item ();
208   k->kid[0] = keyid[0];
209   k->kid[1] = keyid[1];
210   k->next = user_utk_list;
211   user_utk_list = k;
212 }
213
214 void
215 register_trusted_key( const char *string )
216 {
217   KEYDB_SEARCH_DESC desc;
218
219   if (classify_user_id (string, &desc) != KEYDB_SEARCH_MODE_LONG_KID )
220     {
221       log_error(_("`%s' is not a valid long keyID\n"), string );
222       return;
223     }
224
225   register_trusted_keyid(desc.u.kid);
226 }
227
228 /*
229  * Helper to add a key to the global list of ultimately trusted keys.
230  * Retruns: true = inserted, false = already in in list.
231  */
232 static int
233 add_utk (u32 *kid)
234 {
235   struct key_item *k;
236
237   for (k = utk_list; k; k = k->next) 
238     {
239       if (k->kid[0] == kid[0] && k->kid[1] == kid[1])
240         {
241           return 0;
242         }
243     }
244
245   k = new_key_item ();
246   k->kid[0] = kid[0];
247   k->kid[1] = kid[1];
248   k->ownertrust = TRUST_ULTIMATE;
249   k->next = utk_list;
250   utk_list = k;
251   if( opt.verbose > 1 )
252     log_info(_("key %s: accepted as trusted key\n"), keystr(kid));
253   return 1;
254 }
255
256
257 /****************
258  * Verify that all our secret keys are usable and put them into the utk_list.
259  */
260 static void
261 verify_own_keys(void)
262 {
263   TRUSTREC rec;
264   ulong recnum;
265   int rc;
266   struct key_item *k;
267
268   if (utk_list)
269     return;
270
271   /* scan the trustdb to find all ultimately trusted keys */
272   for (recnum=1; !tdbio_read_record (recnum, &rec, 0); recnum++ ) 
273     {
274       if ( rec.rectype == RECTYPE_TRUST 
275            && (rec.r.trust.ownertrust & TRUST_MASK) == TRUST_ULTIMATE)
276         {
277             byte *fpr = rec.r.trust.fingerprint;
278             int fprlen;
279             u32 kid[2];
280             
281             /* Problem: We do only use fingerprints in the trustdb but
282              * we need the keyID here to indetify the key; we can only
283              * use that ugly hack to distinguish between 16 and 20
284              * butes fpr - it does not work always so we better change
285              * the whole validation code to only work with
286              * fingerprints */
287             fprlen = (!fpr[16] && !fpr[17] && !fpr[18] && !fpr[19])? 16:20;
288             keyid_from_fingerprint (fpr, fprlen, kid);
289             if (!add_utk (kid))
290               log_info(_("key %s occurs more than once in the trustdb\n"),
291                        keystr(kid));
292         }
293     }
294
295   /* Put any --trusted-key keys into the trustdb */
296   for (k = user_utk_list; k; k = k->next) 
297     {
298       if ( add_utk (k->kid) ) 
299         { /* not yet in trustDB as ultimately trusted */
300           PKT_public_key pk;
301
302           memset (&pk, 0, sizeof pk);
303           rc = get_pubkey (&pk, k->kid);
304           if (rc)
305             log_info(_("key %s: no public key for trusted key - skipped\n"),
306                      keystr(k->kid));
307           else
308             {
309               update_ownertrust (&pk,
310                                  ((get_ownertrust (&pk) & ~TRUST_MASK)
311                                   | TRUST_ULTIMATE ));
312               release_public_key_parts (&pk);
313             }
314
315           log_info (_("key %s marked as ultimately trusted\n"),keystr(k->kid));
316         }
317     }
318
319   /* release the helper table table */
320   release_key_items (user_utk_list);
321   user_utk_list = NULL;
322   return;
323 }
324
325 \f
326 /*********************************************
327  *********** TrustDB stuff *******************
328  *********************************************/
329
330 /*
331  * Read a record but die if it does not exist
332  */
333 static void
334 read_record (ulong recno, TRUSTREC *rec, int rectype )
335 {
336   int rc = tdbio_read_record (recno, rec, rectype);
337   if (rc)
338     {
339       log_error(_("trust record %lu, req type %d: read failed: %s\n"),
340                 recno, rec->rectype, g10_errstr(rc) );
341       tdbio_invalid();
342     }
343   if (rectype != rec->rectype)
344     {
345       log_error(_("trust record %lu is not of requested type %d\n"),
346                 rec->recnum, rectype);
347       tdbio_invalid();
348     }
349 }
350
351 /*
352  * Write a record and die on error
353  */
354 static void
355 write_record (TRUSTREC *rec)
356 {
357   int rc = tdbio_write_record (rec);
358   if (rc)
359     {
360       log_error(_("trust record %lu, type %d: write failed: %s\n"),
361                             rec->recnum, rec->rectype, g10_errstr(rc) );
362       tdbio_invalid();
363     }
364 }
365
366 /*
367  * sync the TrustDb and die on error
368  */
369 static void
370 do_sync(void)
371 {
372     int rc = tdbio_sync ();
373     if(rc)
374       {
375         log_error (_("trustdb: sync failed: %s\n"), g10_errstr(rc) );
376         g10_exit(2);
377       }
378 }
379
380 static const char *
381 trust_model_string(void)
382 {
383   switch(opt.trust_model)
384     {
385     case TM_CLASSIC:  return "classic";
386     case TM_PGP:      return "PGP";
387     case TM_EXTERNAL: return "external";
388     case TM_ALWAYS:   return "always";
389     case TM_DIRECT:   return "direct";
390     default:          return "unknown";
391     }
392 }
393
394 /****************
395  * Perform some checks over the trustdb
396  *  level 0: only open the db
397  *        1: used for initial program startup
398  */
399 int
400 setup_trustdb( int level, const char *dbname )
401 {
402     /* just store the args */
403     if( trustdb_args.init )
404         return 0;
405     trustdb_args.level = level;
406     trustdb_args.dbname = dbname? xstrdup(dbname): NULL;
407     return 0;
408 }
409
410 void
411 init_trustdb()
412 {
413   int level = trustdb_args.level;
414   const char* dbname = trustdb_args.dbname;
415
416   if( trustdb_args.init )
417     return;
418
419   trustdb_args.init = 1;
420
421   if(level==0 || level==1)
422     {
423       int rc = tdbio_set_dbname( dbname, !!level );
424       if( rc )
425         log_fatal("can't init trustdb: %s\n", g10_errstr(rc) );
426     }
427   else
428     BUG();
429
430   if(opt.trust_model==TM_AUTO)
431     {
432       /* Try and set the trust model off of whatever the trustdb says
433          it is. */
434       opt.trust_model=tdbio_read_model();
435
436       /* Sanity check this ;) */
437       if(opt.trust_model!=TM_CLASSIC
438          && opt.trust_model!=TM_PGP
439          && opt.trust_model!=TM_EXTERNAL)
440         {
441           log_info(_("unable to use unknown trust model (%d) - "
442                      "assuming %s trust model\n"),opt.trust_model,"PGP");
443           opt.trust_model=TM_PGP;
444         }
445
446       if(opt.verbose)
447         log_info(_("using %s trust model\n"),trust_model_string());
448     }
449
450   if(opt.trust_model==TM_PGP || opt.trust_model==TM_CLASSIC)
451     {
452       /* Verify the list of ultimately trusted keys and move the
453          --trusted-keys list there as well. */
454       if(level==1)
455         verify_own_keys();
456
457       if(!tdbio_db_matches_options())
458         pending_check_trustdb=1;
459     }
460 }
461
462
463 /***********************************************
464  *************  Print helpers   ****************
465  ***********************************************/
466
467 /****************
468  * This function returns a letter for a trustvalue  Trust flags
469  * are ignore.
470  */
471 static int
472 trust_letter (unsigned int value)
473 {
474   switch( (value & TRUST_MASK) ) 
475     {
476     case TRUST_UNKNOWN:   return '-';
477     case TRUST_EXPIRED:   return 'e';
478     case TRUST_UNDEFINED: return 'q';
479     case TRUST_NEVER:     return 'n';
480     case TRUST_MARGINAL:  return 'm';
481     case TRUST_FULLY:     return 'f';
482     case TRUST_ULTIMATE:  return 'u';
483     default:              return '?';
484     }
485 }
486
487 /* NOTE TO TRANSLATOR: these strings are similar to those in
488    trust_value_to_string(), but are a fixed length.  This is needed to
489    make attractive information listings where columns line up
490    properly.  The value "10" should be the length of the strings you
491    choose to translate to.  This is the length in printable columns.
492    It gets passed to atoi() so everything after the number is
493    essentially a comment and need not be translated.  Either key and
494    uid are both NULL, or neither are NULL. */
495 const char *
496 uid_trust_string_fixed(PKT_public_key *key,PKT_user_id *uid)
497 {
498   if(!key && !uid)
499     return _("10 translator see trustdb.c:uid_trust_string_fixed");
500   else if(uid->is_revoked || (key && key->is_revoked))
501     return                         _("[ revoked]");
502   else if(uid->is_expired)
503     return                         _("[ expired]");
504   else if(key)
505     switch(get_validity(key,uid)&TRUST_MASK)
506       {
507       case TRUST_UNKNOWN:   return _("[ unknown]");
508       case TRUST_EXPIRED:   return _("[ expired]");
509       case TRUST_UNDEFINED: return _("[  undef ]");
510       case TRUST_MARGINAL:  return _("[marginal]");
511       case TRUST_FULLY:     return _("[  full  ]");
512       case TRUST_ULTIMATE:  return _("[ultimate]");
513       }
514
515   return "err";
516 }
517
518 /* The strings here are similar to those in
519    pkclist.c:do_edit_ownertrust() */
520 const char *
521 trust_value_to_string (unsigned int value)
522 {
523   switch( (value & TRUST_MASK) ) 
524     {
525     case TRUST_UNKNOWN:   return _("unknown");
526     case TRUST_EXPIRED:   return _("expired");
527     case TRUST_UNDEFINED: return _("undefined");
528     case TRUST_NEVER:     return _("never");
529     case TRUST_MARGINAL:  return _("marginal");
530     case TRUST_FULLY:     return _("full");
531     case TRUST_ULTIMATE:  return _("ultimate");
532     default:              return "err";
533     }
534 }
535
536 int
537 string_to_trust_value (const char *str)
538 {
539   if(ascii_strcasecmp(str,"undefined")==0)
540     return TRUST_UNDEFINED;
541   else if(ascii_strcasecmp(str,"never")==0)
542     return TRUST_NEVER;
543   else if(ascii_strcasecmp(str,"marginal")==0)
544     return TRUST_MARGINAL;
545   else if(ascii_strcasecmp(str,"full")==0)
546     return TRUST_FULLY;
547   else if(ascii_strcasecmp(str,"ultimate")==0)
548     return TRUST_ULTIMATE;
549   else
550     return -1;
551 }
552
553 /****************
554  * Recreate the WoT but do not ask for new ownertrusts.  Special
555  * feature: In batch mode and without a forced yes, this is only done
556  * when a check is due.  This can be used to run the check from a crontab
557  */
558 void
559 check_trustdb ()
560 {
561   init_trustdb();
562   if(opt.trust_model==TM_PGP || opt.trust_model==TM_CLASSIC)
563     {
564       if (opt.batch && !opt.answer_yes)
565         {
566           ulong scheduled;
567
568           scheduled = tdbio_read_nextcheck ();
569           if (!scheduled)
570             {
571               log_info (_("no need for a trustdb check\n"));
572               return;
573             }
574
575           if (scheduled > make_timestamp ())
576             {
577               log_info (_("next trustdb check due at %s\n"),
578                         strtimestamp (scheduled));
579               return;
580             }
581         }
582
583       validate_keys (0);
584     }
585   else
586     log_info (_("no need for a trustdb check with `%s' trust model\n"),
587               trust_model_string());
588 }
589
590
591 /*
592  * Recreate the WoT. 
593  */
594 void
595 update_trustdb()
596 {
597   init_trustdb();
598   if(opt.trust_model==TM_PGP || opt.trust_model==TM_CLASSIC)
599     validate_keys (1);
600   else
601     log_info (_("no need for a trustdb update with `%s' trust model\n"),
602               trust_model_string());
603 }
604
605 void
606 revalidation_mark (void)
607 {
608   init_trustdb();
609   /* we simply set the time for the next check to 1 (far back in 1970)
610    * so that a --update-trustdb will be scheduled */
611   if (tdbio_write_nextcheck (1))
612       do_sync ();
613   pending_check_trustdb = 1;
614 }
615
616 int
617 trustdb_pending_check(void)
618 {
619   return pending_check_trustdb;
620 }
621
622 /* If the trustdb is dirty, and we're interactive, update it.
623    Otherwise, check it unless no-auto-check-trustdb is set. */
624 void
625 trustdb_check_or_update(void)
626 {
627   if(trustdb_pending_check())
628     {
629       if(opt.interactive)
630         update_trustdb();
631       else if(!opt.no_auto_check_trustdb)
632         check_trustdb();
633     }
634 }
635
636 void
637 read_trust_options(byte *trust_model,ulong *created,ulong *nextcheck,
638                    byte *marginals,byte *completes,byte *cert_depth)
639 {
640   TRUSTREC opts;
641
642   init_trustdb();
643
644   read_record(0,&opts,RECTYPE_VER);
645
646   if(trust_model)
647     *trust_model=opts.r.ver.trust_model;
648   if(created)
649     *created=opts.r.ver.created;
650   if(nextcheck)
651     *nextcheck=opts.r.ver.nextcheck;
652   if(marginals)
653     *marginals=opts.r.ver.marginals;
654   if(completes)
655     *completes=opts.r.ver.completes;
656   if(cert_depth)
657     *cert_depth=opts.r.ver.cert_depth;
658 }
659
660 /***********************************************
661  ***********  Ownertrust et al. ****************
662  ***********************************************/
663
664 static int 
665 read_trust_record (PKT_public_key *pk, TRUSTREC *rec)
666 {
667   int rc;
668   
669   init_trustdb();
670   rc = tdbio_search_trust_bypk (pk, rec);
671   if (rc == -1)
672     return -1; /* no record yet */
673   if (rc) 
674     {
675       log_error ("trustdb: searching trust record failed: %s\n",
676                  g10_errstr (rc));
677       return rc; 
678     }
679       
680   if (rec->rectype != RECTYPE_TRUST)
681     {
682       log_error ("trustdb: record %lu is not a trust record\n",
683                  rec->recnum);
684       return G10ERR_TRUSTDB; 
685     }      
686   
687   return 0;
688 }
689
690 /****************
691  * Return the assigned ownertrust value for the given public key.
692  * The key should be the primary key.
693  */
694 unsigned int 
695 get_ownertrust ( PKT_public_key *pk)
696 {
697   TRUSTREC rec;
698   int rc;
699   
700   rc = read_trust_record (pk, &rec);
701   if (rc == -1)
702     return TRUST_UNKNOWN; /* no record yet */
703   if (rc) 
704     {
705       tdbio_invalid ();
706       return rc; /* actually never reached */
707     }
708
709   return rec.r.trust.ownertrust;
710 }
711
712 unsigned int 
713 get_min_ownertrust (PKT_public_key *pk)
714 {
715   TRUSTREC rec;
716   int rc;
717   
718   rc = read_trust_record (pk, &rec);
719   if (rc == -1)
720     return TRUST_UNKNOWN; /* no record yet */
721   if (rc) 
722     {
723       tdbio_invalid ();
724       return rc; /* actually never reached */
725     }
726
727   return rec.r.trust.min_ownertrust;
728 }
729
730 /*
731  * Same as get_ownertrust but this takes the minimum ownertrust value
732  * into into account, and will bump up the value as needed.
733  */
734 static int
735 get_ownertrust_with_min (PKT_public_key *pk)
736 {
737   unsigned int otrust,otrust_min;
738
739   otrust = (get_ownertrust (pk) & TRUST_MASK);
740   otrust_min = get_min_ownertrust (pk);
741   if(otrust<otrust_min)
742     {
743       /* If the trust that the user has set is less than the trust
744          that was calculated from a trust signature chain, use the
745          higher of the two.  We do this here and not in
746          get_ownertrust since the underlying ownertrust should not
747          really be set - just the appearance of the ownertrust. */
748
749       otrust=otrust_min;
750     }
751
752   return otrust;
753 }
754
755 /*
756  * Same as get_ownertrust but return a trust letter instead of an
757  * value.  This takes the minimum ownertrust value into account.
758  */
759 int
760 get_ownertrust_info (PKT_public_key *pk)
761 {
762   return trust_letter(get_ownertrust_with_min(pk));
763 }
764
765 /*
766  * Same as get_ownertrust but return a trust string instead of an
767  * value.  This takes the minimum ownertrust value into account.
768  */
769 const char *
770 get_ownertrust_string (PKT_public_key *pk)
771 {
772   return trust_value_to_string(get_ownertrust_with_min(pk));
773 }
774
775 /*
776  * Set the trust value of the given public key to the new value.
777  * The key should be a primary one.
778  */
779 void
780 update_ownertrust (PKT_public_key *pk, unsigned int new_trust )
781 {
782   TRUSTREC rec;
783   int rc;
784   
785   rc = read_trust_record (pk, &rec);
786   if (!rc)
787     {
788       if (DBG_TRUST)
789         log_debug ("update ownertrust from %u to %u\n",
790                    (unsigned int)rec.r.trust.ownertrust, new_trust );
791       if (rec.r.trust.ownertrust != new_trust)
792         {
793           rec.r.trust.ownertrust = new_trust;
794           write_record( &rec );
795           revalidation_mark ();
796           do_sync ();
797         }
798     }
799   else if (rc == -1)
800     { /* no record yet - create a new one */
801       size_t dummy;
802
803       if (DBG_TRUST)
804         log_debug ("insert ownertrust %u\n", new_trust );
805
806       memset (&rec, 0, sizeof rec);
807       rec.recnum = tdbio_new_recnum ();
808       rec.rectype = RECTYPE_TRUST;
809       fingerprint_from_pk (pk, rec.r.trust.fingerprint, &dummy);
810       rec.r.trust.ownertrust = new_trust;
811       write_record (&rec);
812       revalidation_mark ();
813       do_sync ();
814       rc = 0;
815     }
816   else 
817     {
818       tdbio_invalid ();
819     }
820 }
821
822 static void
823 update_min_ownertrust (u32 *kid, unsigned int new_trust )
824 {
825   PKT_public_key *pk;
826   TRUSTREC rec;
827   int rc;
828
829   pk = xmalloc_clear (sizeof *pk);
830   rc = get_pubkey (pk, kid);
831   if (rc)
832     {
833       log_error(_("public key %s not found: %s\n"),keystr(kid),g10_errstr(rc));
834       return;
835     }
836
837   rc = read_trust_record (pk, &rec);
838   if (!rc)
839     {
840       if (DBG_TRUST)
841         log_debug ("key %08lX%08lX: update min_ownertrust from %u to %u\n",
842                    (ulong)kid[0],(ulong)kid[1],
843                    (unsigned int)rec.r.trust.min_ownertrust,
844                    new_trust );
845       if (rec.r.trust.min_ownertrust != new_trust)
846         {
847           rec.r.trust.min_ownertrust = new_trust;
848           write_record( &rec );
849           revalidation_mark ();
850           do_sync ();
851         }
852     }
853   else if (rc == -1)
854     { /* no record yet - create a new one */
855       size_t dummy;
856
857       if (DBG_TRUST)
858         log_debug ("insert min_ownertrust %u\n", new_trust );
859
860       memset (&rec, 0, sizeof rec);
861       rec.recnum = tdbio_new_recnum ();
862       rec.rectype = RECTYPE_TRUST;
863       fingerprint_from_pk (pk, rec.r.trust.fingerprint, &dummy);
864       rec.r.trust.min_ownertrust = new_trust;
865       write_record (&rec);
866       revalidation_mark ();
867       do_sync ();
868       rc = 0;
869     }
870   else 
871     {
872       tdbio_invalid ();
873     }
874 }
875
876 /* Clear the ownertrust and min_ownertrust values.  Return true if a
877    change actually happened. */
878 int
879 clear_ownertrusts (PKT_public_key *pk)
880 {
881   TRUSTREC rec;
882   int rc;
883   
884   rc = read_trust_record (pk, &rec);
885   if (!rc)
886     {
887       if (DBG_TRUST)
888         {
889           log_debug ("clearing ownertrust (old value %u)\n",
890                      (unsigned int)rec.r.trust.ownertrust);
891           log_debug ("clearing min_ownertrust (old value %u)\n",
892                      (unsigned int)rec.r.trust.min_ownertrust);
893         }
894       if (rec.r.trust.ownertrust || rec.r.trust.min_ownertrust)
895         {
896           rec.r.trust.ownertrust = 0;
897           rec.r.trust.min_ownertrust = 0;
898           write_record( &rec );
899           revalidation_mark ();
900           do_sync ();
901           return 1;
902         }
903     }
904   else if (rc != -1)
905     {
906       tdbio_invalid ();
907     }
908   return 0;
909 }
910
911 /* 
912  * Note: Caller has to do a sync 
913  */
914 static void
915 update_validity (PKT_public_key *pk, PKT_user_id *uid,
916                  int depth, int validity)
917 {
918   TRUSTREC trec, vrec;
919   int rc;
920   ulong recno;
921
922   namehash_from_uid(uid);
923
924   rc = read_trust_record (pk, &trec);
925   if (rc && rc != -1)
926     {
927       tdbio_invalid ();
928       return;
929     }
930   if (rc == -1) /* no record yet - create a new one */
931     { 
932       size_t dummy;
933
934       rc = 0;
935       memset (&trec, 0, sizeof trec);
936       trec.recnum = tdbio_new_recnum ();
937       trec.rectype = RECTYPE_TRUST;
938       fingerprint_from_pk (pk, trec.r.trust.fingerprint, &dummy);
939       trec.r.trust.ownertrust = 0;
940       }
941
942   /* locate an existing one */
943   recno = trec.r.trust.validlist;
944   while (recno)
945     {
946       read_record (recno, &vrec, RECTYPE_VALID);
947       if ( !memcmp (vrec.r.valid.namehash, uid->namehash, 20) )
948         break;
949       recno = vrec.r.valid.next;
950     }
951
952   if (!recno) /* insert a new validity record */
953     {
954       memset (&vrec, 0, sizeof vrec);
955       vrec.recnum = tdbio_new_recnum ();
956       vrec.rectype = RECTYPE_VALID;
957       memcpy (vrec.r.valid.namehash, uid->namehash, 20);
958       vrec.r.valid.next = trec.r.trust.validlist;
959       trec.r.trust.validlist = vrec.recnum;
960     }
961   vrec.r.valid.validity = validity;
962   vrec.r.valid.full_count = uid->help_full_count;
963   vrec.r.valid.marginal_count = uid->help_marginal_count;
964   write_record (&vrec);
965   trec.r.trust.depth = depth;
966   write_record (&trec);
967 }
968
969
970 /***********************************************
971  *********  Query trustdb values  **************
972  ***********************************************/
973
974 /* Return true if key is disabled */
975 int
976 cache_disabled_value(PKT_public_key *pk)
977 {
978   int rc;
979   TRUSTREC trec;
980   int disabled=0;
981
982   if(pk->is_disabled)
983     return (pk->is_disabled==2);
984
985   init_trustdb();
986
987   rc = read_trust_record (pk, &trec);
988   if (rc && rc != -1)
989     {
990       tdbio_invalid ();
991       goto leave;
992     }
993   if (rc == -1) /* no record found, so assume not disabled */
994     goto leave;
995  
996   if(trec.r.trust.ownertrust & TRUST_FLAG_DISABLED)
997     disabled=1;
998  
999   /* Cache it for later so we don't need to look at the trustdb every
1000      time */
1001   if(disabled)
1002     pk->is_disabled=2;
1003   else
1004     pk->is_disabled=1;
1005
1006  leave:
1007    return disabled;
1008 }
1009
1010 void
1011 check_trustdb_stale(void)
1012 {
1013   static int did_nextcheck=0;
1014
1015   init_trustdb ();
1016   if (!did_nextcheck
1017       && (opt.trust_model==TM_PGP || opt.trust_model==TM_CLASSIC))
1018     {
1019       ulong scheduled;
1020
1021       did_nextcheck = 1;
1022       scheduled = tdbio_read_nextcheck ();
1023       if (scheduled && scheduled <= make_timestamp ())
1024         {
1025           if (opt.no_auto_check_trustdb) 
1026             {
1027               pending_check_trustdb = 1;
1028               log_info (_("please do a --check-trustdb\n"));
1029             }
1030           else
1031             {
1032               log_info (_("checking the trustdb\n"));
1033               validate_keys (0);
1034             }
1035         }
1036     }
1037 }
1038
1039 /*
1040  * Return the validity information for PK.  If the namehash is not
1041  * NULL, the validity of the corresponsing user ID is returned,
1042  * otherwise, a reasonable value for the entire key is returned. 
1043  */
1044 unsigned int
1045 get_validity (PKT_public_key *pk, PKT_user_id *uid)
1046 {
1047   TRUSTREC trec, vrec;
1048   int rc;
1049   ulong recno;
1050   unsigned int validity;
1051   u32 kid[2];
1052   PKT_public_key *main_pk;
1053
1054   if(uid)
1055     namehash_from_uid(uid);
1056
1057   init_trustdb ();
1058   check_trustdb_stale();
1059
1060   keyid_from_pk (pk, kid);
1061   if (pk->main_keyid[0] != kid[0] || pk->main_keyid[1] != kid[1])
1062     { /* this is a subkey - get the mainkey */
1063       main_pk = xmalloc_clear (sizeof *main_pk);
1064       rc = get_pubkey (main_pk, pk->main_keyid);
1065       if (rc)
1066         {
1067           char *tempkeystr=xstrdup(keystr(pk->main_keyid));
1068           log_error ("error getting main key %s of subkey %s: %s\n",
1069                      tempkeystr, keystr(kid), g10_errstr(rc));
1070           xfree(tempkeystr);
1071           validity = TRUST_UNKNOWN; 
1072           goto leave;
1073         }
1074     }
1075   else
1076     main_pk = pk;
1077
1078   if(opt.trust_model==TM_DIRECT)
1079     {
1080       /* Note that this happens BEFORE any user ID stuff is checked.
1081          The direct trust model applies to keys as a whole. */
1082       validity=get_ownertrust(main_pk);
1083       goto leave;
1084     }
1085
1086   rc = read_trust_record (main_pk, &trec);
1087   if (rc && rc != -1)
1088     {
1089       tdbio_invalid ();
1090       return 0;
1091     }
1092   if (rc == -1) /* no record found */
1093     {
1094       validity = TRUST_UNKNOWN; 
1095       goto leave;
1096     }
1097
1098   /* loop over all user IDs */
1099   recno = trec.r.trust.validlist;
1100   validity = 0;
1101   while (recno)
1102     {
1103       read_record (recno, &vrec, RECTYPE_VALID);
1104
1105       if(uid)
1106         {
1107           /* If a user ID is given we return the validity for that
1108              user ID ONLY.  If the namehash is not found, then there
1109              is no validity at all (i.e. the user ID wasn't
1110              signed). */
1111           if(memcmp(vrec.r.valid.namehash,uid->namehash,20)==0)
1112             {
1113               validity=(vrec.r.valid.validity & TRUST_MASK);
1114               break;
1115             }
1116         }
1117       else
1118         {
1119           /* If no namehash is given, we take the maximum validity
1120              over all user IDs */
1121           if ( validity < (vrec.r.valid.validity & TRUST_MASK) )
1122             validity = (vrec.r.valid.validity & TRUST_MASK);
1123         }
1124
1125       recno = vrec.r.valid.next;
1126     }
1127   
1128   if ( (trec.r.trust.ownertrust & TRUST_FLAG_DISABLED) )
1129     {
1130       validity |= TRUST_FLAG_DISABLED;
1131       pk->is_disabled=2;
1132     }
1133   else
1134     pk->is_disabled=1;
1135
1136  leave:
1137   /* set some flags direct from the key */
1138   if (main_pk->is_revoked)
1139     validity |= TRUST_FLAG_REVOKED;
1140   if (main_pk != pk && pk->is_revoked)
1141     validity |= TRUST_FLAG_SUB_REVOKED;
1142   /* Note: expiration is a trust value and not a flag - don't know why
1143    * I initially designed it that way */
1144   if (main_pk->has_expired || pk->has_expired)
1145     validity = (validity & ~TRUST_MASK) | TRUST_EXPIRED;
1146   
1147   if (pending_check_trustdb)
1148     validity |= TRUST_FLAG_PENDING_CHECK;
1149
1150   if (main_pk != pk)
1151     free_public_key (main_pk);
1152   return validity;
1153 }
1154
1155 int
1156 get_validity_info (PKT_public_key *pk, PKT_user_id *uid)
1157 {
1158     int trustlevel;
1159
1160     trustlevel = get_validity (pk, uid);
1161     if( trustlevel & TRUST_FLAG_REVOKED )
1162         return 'r';
1163     return trust_letter ( trustlevel );
1164 }
1165
1166 const char *
1167 get_validity_string (PKT_public_key *pk, PKT_user_id *uid)
1168 {
1169   int trustlevel;
1170
1171   trustlevel = get_validity (pk, uid);
1172   if( trustlevel & TRUST_FLAG_REVOKED )
1173     return _("revoked");
1174   return trust_value_to_string(trustlevel);
1175 }
1176
1177 static void
1178 get_validity_counts (PKT_public_key *pk, PKT_user_id *uid)
1179 {
1180   TRUSTREC trec, vrec;
1181   ulong recno;
1182
1183   if(pk==NULL || uid==NULL)
1184     BUG();
1185
1186   namehash_from_uid(uid);
1187
1188   uid->help_marginal_count=uid->help_full_count=0;
1189
1190   init_trustdb ();
1191
1192   if(read_trust_record (pk, &trec)!=0)
1193     return;
1194
1195   /* loop over all user IDs */
1196   recno = trec.r.trust.validlist;
1197   while (recno)
1198     {
1199       read_record (recno, &vrec, RECTYPE_VALID);
1200
1201       if(memcmp(vrec.r.valid.namehash,uid->namehash,20)==0)
1202         {
1203           uid->help_marginal_count=vrec.r.valid.marginal_count;
1204           uid->help_full_count=vrec.r.valid.full_count;
1205           /*  printf("Fetched marginal %d, full %d\n",uid->help_marginal_count,uid->help_full_count); */
1206           break;
1207         }
1208
1209       recno = vrec.r.valid.next;
1210     }
1211 }
1212
1213 void
1214 list_trust_path( const char *username )
1215 {
1216 }
1217
1218 /****************
1219  * Enumerate all keys, which are needed to build all trust paths for
1220  * the given key.  This function does not return the key itself or
1221  * the ultimate key (the last point in cerificate chain).  Only
1222  * certificate chains which ends up at an ultimately trusted key
1223  * are listed.  If ownertrust or validity is not NULL, the corresponding
1224  * value for the returned LID is also returned in these variable(s).
1225  *
1226  *  1) create a void pointer and initialize it to NULL
1227  *  2) pass this void pointer by reference to this function.
1228  *     Set lid to the key you want to enumerate and pass it by reference.
1229  *  3) call this function as long as it does not return -1
1230  *     to indicate EOF. LID does contain the next key used to build the web
1231  *  4) Always call this function a last time with LID set to NULL,
1232  *     so that it can free its context.
1233  *
1234  * Returns: -1 on EOF or the level of the returned LID
1235  */
1236 int
1237 enum_cert_paths( void **context, ulong *lid,
1238                  unsigned *ownertrust, unsigned *validity )
1239 {
1240     return -1;
1241 }
1242
1243
1244 /****************
1245  * Print the current path
1246  */
1247 void
1248 enum_cert_paths_print( void **context, FILE *fp,
1249                                        int refresh, ulong selected_lid )
1250 {
1251     return;
1252 }
1253
1254
1255 \f
1256 /****************************************
1257  *********** NEW NEW NEW ****************
1258  ****************************************/
1259
1260 static int
1261 ask_ownertrust (u32 *kid,int minimum)
1262 {
1263   PKT_public_key *pk;
1264   int rc;
1265   int ot;
1266
1267   pk = xmalloc_clear (sizeof *pk);
1268   rc = get_pubkey (pk, kid);
1269   if (rc)
1270     {
1271       log_error (_("public key %s not found: %s\n"),
1272                  keystr(kid), g10_errstr(rc) );
1273       return TRUST_UNKNOWN;
1274     }
1275  
1276   if(opt.force_ownertrust)
1277     {
1278       log_info("force trust for key %s to %s\n",
1279                keystr(kid),trust_value_to_string(opt.force_ownertrust));
1280       update_ownertrust(pk,opt.force_ownertrust);
1281       ot=opt.force_ownertrust;
1282     }
1283   else
1284     {
1285       ot=edit_ownertrust(pk,0);
1286       if(ot>0)
1287         ot = get_ownertrust (pk);
1288       else if(ot==0)
1289         ot = minimum?minimum:TRUST_UNDEFINED;
1290       else
1291         ot = -1; /* quit */
1292     }
1293
1294   free_public_key( pk );
1295
1296   return ot;
1297 }
1298
1299
1300 static void
1301 mark_keyblock_seen (KeyHashTable tbl, KBNODE node)
1302 {
1303   for ( ;node; node = node->next )
1304     if (node->pkt->pkttype == PKT_PUBLIC_KEY
1305         || node->pkt->pkttype == PKT_PUBLIC_SUBKEY)
1306       {
1307         u32 aki[2];
1308
1309         keyid_from_pk (node->pkt->pkt.public_key, aki);
1310         add_key_hash_table (tbl, aki);
1311       }
1312 }
1313
1314
1315 static void
1316 dump_key_array (int depth, struct key_array *keys)
1317 {
1318   struct key_array *kar;
1319
1320   for (kar=keys; kar->keyblock; kar++)
1321     {
1322       KBNODE node = kar->keyblock;
1323       u32 kid[2];
1324
1325       keyid_from_pk(node->pkt->pkt.public_key, kid);
1326       printf ("%d:%08lX%08lX:K::%c::::\n",
1327               depth, (ulong)kid[0], (ulong)kid[1], '?');
1328
1329       for (; node; node = node->next)
1330         {
1331           if (node->pkt->pkttype == PKT_USER_ID)
1332             {
1333               int len = node->pkt->pkt.user_id->len;
1334
1335               if (len > 30)
1336                 len = 30;
1337               printf ("%d:%08lX%08lX:U:::%c:::",
1338                       depth, (ulong)kid[0], (ulong)kid[1],
1339                       (node->flag & 4)? 'f':
1340                       (node->flag & 2)? 'm':
1341                       (node->flag & 1)? 'q':'-');
1342               print_string (stdout,  node->pkt->pkt.user_id->name, len, ':');
1343               putchar (':');
1344               putchar ('\n');
1345             }
1346         }
1347     }
1348 }  
1349
1350
1351 static void
1352 store_validation_status (int depth, KBNODE keyblock, KeyHashTable stored)
1353 {
1354   KBNODE node;
1355   int status;
1356   int any = 0;
1357
1358   for (node=keyblock; node; node = node->next)
1359     {
1360       if (node->pkt->pkttype == PKT_USER_ID)
1361         {
1362           PKT_user_id *uid = node->pkt->pkt.user_id;
1363           if (node->flag & 4)
1364             status = TRUST_FULLY;
1365           else if (node->flag & 2)
1366             status = TRUST_MARGINAL;
1367           else if (node->flag & 1)
1368             status = TRUST_UNDEFINED;
1369           else
1370             status = 0;
1371           
1372           if (status)
1373             {
1374               update_validity (keyblock->pkt->pkt.public_key,
1375                                uid, depth, status);
1376
1377               mark_keyblock_seen(stored,keyblock);
1378
1379               any = 1;
1380             }
1381         }
1382     }
1383
1384   if (any)
1385     do_sync ();
1386 }  
1387
1388 /*
1389  * check whether the signature sig is in the klist k
1390  */
1391 static struct key_item *
1392 is_in_klist (struct key_item *k, PKT_signature *sig)
1393 {
1394   for (; k; k = k->next)
1395     {
1396       if (k->kid[0] == sig->keyid[0] && k->kid[1] == sig->keyid[1])
1397         return k;
1398     }
1399   return NULL;
1400 }
1401
1402 /*
1403  * Mark the signature of the given UID which are used to certify it.
1404  * To do this, we first revmove all signatures which are not valid and
1405  * from the remain ones we look for the latest one.  If this is not a
1406  * certification revocation signature we mark the signature by setting
1407  * node flag bit 8.  Revocations are marked with flag 11, and sigs
1408  * from unavailable keys are marked with flag 12.  Note that flag bits
1409  * 9 and 10 are used for internal purposes.
1410  */
1411 static void
1412 mark_usable_uid_certs (KBNODE keyblock, KBNODE uidnode,
1413                        u32 *main_kid, struct key_item *klist,
1414                        u32 curtime, u32 *next_expire)
1415 {
1416   KBNODE node;
1417   PKT_signature *sig;
1418   
1419   /* first check all signatures */
1420   for (node=uidnode->next; node; node = node->next)
1421     {
1422       int rc;
1423
1424       node->flag &= ~(1<<8 | 1<<9 | 1<<10 | 1<<11 | 1<<12);
1425       if (node->pkt->pkttype == PKT_USER_ID
1426           || node->pkt->pkttype == PKT_PUBLIC_SUBKEY)
1427         break; /* ready */
1428       if (node->pkt->pkttype != PKT_SIGNATURE)
1429         continue;
1430       sig = node->pkt->pkt.signature;
1431       if (main_kid
1432           && sig->keyid[0] == main_kid[0] && sig->keyid[1] == main_kid[1])
1433         continue; /* ignore self-signatures if we pass in a main_kid */
1434       if (!IS_UID_SIG(sig) && !IS_UID_REV(sig))
1435         continue; /* we only look at these signature classes */
1436       if(sig->sig_class>=0x11 && sig->sig_class<=0x13 &&
1437          sig->sig_class-0x10<opt.min_cert_level)
1438         continue; /* treat anything under our min_cert_level as an
1439                      invalid signature */
1440       if (klist && !is_in_klist (klist, sig))
1441         continue;  /* no need to check it then */
1442       if ((rc=check_key_signature (keyblock, node, NULL)))
1443         {
1444           /* we ignore anything that won't verify, but tag the
1445              no_pubkey case */
1446           if(rc==G10ERR_NO_PUBKEY)
1447             node->flag |= 1<<12;
1448           continue;
1449         }
1450       node->flag |= 1<<9;
1451     }      
1452   /* reset the remaining flags */
1453   for (; node; node = node->next)
1454       node->flag &= ~(1<<8 | 1<<9 | 1<<10 | 1<<11 | 1<<12);
1455
1456   /* kbnode flag usage: bit 9 is here set for signatures to consider,
1457    * bit 10 will be set by the loop to keep track of keyIDs already
1458    * processed, bit 8 will be set for the usable signatures, and bit
1459    * 11 will be set for usable revocations. */
1460
1461   /* for each cert figure out the latest valid one */
1462   for (node=uidnode->next; node; node = node->next)
1463     {
1464       KBNODE n, signode;
1465       u32 kid[2];
1466       u32 sigdate;
1467
1468       if (node->pkt->pkttype == PKT_PUBLIC_SUBKEY)
1469         break;
1470       if ( !(node->flag & (1<<9)) )
1471         continue; /* not a node to look at */
1472       if ( (node->flag & (1<<10)) )
1473         continue; /* signature with a keyID already processed */
1474       node->flag |= (1<<10); /* mark this node as processed */
1475       sig = node->pkt->pkt.signature;
1476       signode = node;
1477       sigdate = sig->timestamp;
1478       kid[0] = sig->keyid[0]; kid[1] = sig->keyid[1];
1479
1480       /* Now find the latest and greatest signature */
1481       for (n=uidnode->next; n; n = n->next)
1482         {
1483           if (n->pkt->pkttype == PKT_PUBLIC_SUBKEY)
1484             break;
1485           if ( !(n->flag & (1<<9)) )
1486             continue;
1487           if ( (n->flag & (1<<10)) )
1488             continue; /* shortcut already processed signatures */
1489           sig = n->pkt->pkt.signature;
1490           if (kid[0] != sig->keyid[0] || kid[1] != sig->keyid[1])
1491             continue;
1492           n->flag |= (1<<10); /* mark this node as processed */
1493
1494           /* If signode is nonrevocable and unexpired and n isn't,
1495              then take signode (skip).  It doesn't matter which is
1496              older: if signode was older then we don't want to take n
1497              as signode is nonrevocable.  If n was older then we're
1498              automatically fine. */
1499           
1500           if(((IS_UID_SIG(signode->pkt->pkt.signature) &&
1501                !signode->pkt->pkt.signature->flags.revocable &&
1502                (signode->pkt->pkt.signature->expiredate==0 ||
1503                 signode->pkt->pkt.signature->expiredate>curtime))) &&
1504              (!(IS_UID_SIG(n->pkt->pkt.signature) &&
1505                 !n->pkt->pkt.signature->flags.revocable &&
1506                 (n->pkt->pkt.signature->expiredate==0 ||
1507                  n->pkt->pkt.signature->expiredate>curtime))))
1508             continue;
1509
1510           /* If n is nonrevocable and unexpired and signode isn't,
1511              then take n.  Again, it doesn't matter which is older: if
1512              n was older then we don't want to take signode as n is
1513              nonrevocable.  If signode was older then we're
1514              automatically fine. */
1515           
1516           if((!(IS_UID_SIG(signode->pkt->pkt.signature) &&
1517                 !signode->pkt->pkt.signature->flags.revocable &&
1518                 (signode->pkt->pkt.signature->expiredate==0 ||
1519                  signode->pkt->pkt.signature->expiredate>curtime))) &&
1520              ((IS_UID_SIG(n->pkt->pkt.signature) &&
1521                !n->pkt->pkt.signature->flags.revocable &&
1522                (n->pkt->pkt.signature->expiredate==0 ||
1523                 n->pkt->pkt.signature->expiredate>curtime))))
1524             {
1525               signode = n;
1526               sigdate = sig->timestamp;
1527               continue;
1528             }
1529
1530           /* At this point, if it's newer, it goes in as the only
1531              remaining possibilities are signode and n are both either
1532              revocable or expired or both nonrevocable and unexpired.
1533              If the timestamps are equal take the later ordered
1534              packet, presuming that the key packets are hopefully in
1535              their original order. */
1536
1537           if (sig->timestamp >= sigdate)
1538             {
1539               signode = n;
1540               sigdate = sig->timestamp;
1541             }
1542         }
1543
1544       sig = signode->pkt->pkt.signature;
1545       if (IS_UID_SIG (sig))
1546         { /* this seems to be a usable one which is not revoked. 
1547            * Just need to check whether there is an expiration time,
1548            * We do the expired certification after finding a suitable
1549            * certification, the assumption is that a signator does not
1550            * want that after the expiration of his certificate the
1551            * system falls back to an older certification which has a
1552            * different expiration time */
1553           const byte *p;
1554           u32 expire;
1555                     
1556           p = parse_sig_subpkt (sig->hashed, SIGSUBPKT_SIG_EXPIRE, NULL );
1557           expire = p? sig->timestamp + buffer_to_u32(p) : 0;
1558
1559           if (expire==0 || expire > curtime )
1560             {
1561               signode->flag |= (1<<8); /* yeah, found a good cert */
1562               if (next_expire && expire && expire < *next_expire)
1563                 *next_expire = expire;
1564             }
1565         }
1566       else
1567         signode->flag |= (1<<11);
1568     }
1569 }
1570
1571 static int
1572 clean_sigs_from_uid(KBNODE keyblock,KBNODE uidnode,int noisy,int self_only)
1573 {
1574   int deleted=0;
1575   KBNODE node;
1576   u32 keyid[2];
1577
1578   assert(keyblock->pkt->pkttype==PKT_PUBLIC_KEY);
1579
1580   keyid_from_pk(keyblock->pkt->pkt.public_key,keyid);
1581
1582   /* Passing in a 0 for current time here means that we'll never weed
1583      out an expired sig.  This is correct behavior since we want to
1584      keep the most recent expired sig in a series. */
1585   mark_usable_uid_certs(keyblock,uidnode,NULL,NULL,0,NULL);
1586
1587   /* What we want to do here is remove signatures that are not
1588      considered as part of the trust calculations.  Thus, all invalid
1589      signatures are out, as are any signatures that aren't the last of
1590      a series of uid sigs or revocations It breaks down like this:
1591      coming out of mark_usable_uid_certs, if a sig is unflagged, it is
1592      not even a candidate.  If a sig has flag 9 or 10, that means it
1593      was selected as a candidate and vetted.  If a sig has flag 8 it
1594      is a usable signature.  If a sig has flag 11 it is a usable
1595      revocation.  If a sig has flag 12 it was issued by an unavailable
1596      key.  "Usable" here means the most recent valid
1597      signature/revocation in a series from a particular signer.
1598
1599      Delete everything that isn't a usable uid sig (which might be
1600      expired), a usable revocation, or a sig from an unavailable
1601      key. */
1602
1603   for(node=uidnode->next;
1604       node && node->pkt->pkttype==PKT_SIGNATURE;
1605       node=node->next)
1606     {
1607       int keep=self_only?(node->pkt->pkt.signature->keyid[0]==keyid[0]
1608                           && node->pkt->pkt.signature->keyid[1]==keyid[1]):1;
1609
1610       /* Keep usable uid sigs ... */
1611       if((node->flag & (1<<8)) && keep)
1612         continue;
1613
1614       /* ... and usable revocations... */
1615       if((node->flag & (1<<11)) && keep)
1616         continue;
1617
1618       /* ... and sigs from unavailable keys. */
1619       /* disabled for now since more people seem to want sigs from
1620          unavailable keys removed altogether.  */
1621       /*
1622         if(node->flag & (1<<12))
1623         continue;
1624       */
1625
1626       /* Everything else we delete */
1627
1628       /* At this point, if 12 is set, the signing key was unavailable.
1629          If 9 or 10 is set, it's superceded.  Otherwise, it's
1630          invalid. */
1631
1632       if(noisy)
1633         log_info("removing signature from key %s on user ID \"%s\": %s\n",
1634                  keystr(node->pkt->pkt.signature->keyid),
1635                  uidnode->pkt->pkt.user_id->name,
1636                  node->flag&(1<<12)?"key unavailable":
1637                  node->flag&(1<<9)?"signature superceded":"invalid signature");
1638
1639       delete_kbnode(node);
1640       deleted++;
1641     }
1642     
1643   return deleted;
1644 }
1645
1646 /* This is substantially easier than clean_sigs_from_uid since we just
1647    have to establish if the uid has a valid self-sig, is not revoked,
1648    and is not expired.  Note that this does not take into account
1649    whether the uid has a trust path to it - just whether the keyholder
1650    themselves has certified the uid.  Returns true if the uid was
1651    compacted.  To "compact" a user ID, we simply remove ALL signatures
1652    except the self-sig that caused the user ID to be remove-worthy.
1653    We don't actually remove the user ID packet itself since it might
1654    be ressurected in a later merge.  Note that this function requires
1655    that the caller has already done a merge_keys_and_selfsig().
1656
1657    TODO: change the import code to allow importing a uid with only a
1658    revocation if the uid already exists on the keyring. */
1659
1660 static int
1661 clean_uid_from_key(KBNODE keyblock,KBNODE uidnode,int noisy)
1662 {
1663   KBNODE node;
1664   PKT_user_id *uid=uidnode->pkt->pkt.user_id;
1665   int deleted=0;
1666
1667   assert(keyblock->pkt->pkttype==PKT_PUBLIC_KEY);
1668   assert(uidnode->pkt->pkttype==PKT_USER_ID);
1669
1670   /* Skip valid user IDs, compacted user IDs, and non-self-signed user
1671      IDs if --allow-non-selfsigned-uid is set. */
1672   if(uid->created || uid->flags.compacted
1673      || (!uid->is_expired && !uid->is_revoked
1674          && opt.allow_non_selfsigned_uid))
1675     return 0;
1676
1677   for(node=uidnode->next;
1678       node && node->pkt->pkttype==PKT_SIGNATURE;
1679       node=node->next)
1680     if(!node->pkt->pkt.signature->flags.chosen_selfsig)
1681       {
1682         delete_kbnode(node);
1683         deleted=1;
1684         uidnode->pkt->pkt.user_id->flags.compacted=1;
1685       }
1686
1687   if(noisy)
1688     {
1689       const char *reason;
1690       char *user=utf8_to_native(uid->name,uid->len,0);
1691
1692       if(uid->is_revoked)
1693         reason=_("revoked");
1694       else if(uid->is_expired)
1695         reason=_("expired");
1696       else
1697         reason=_("invalid");
1698
1699       log_info("compacting user ID \"%s\" on key %s: %s\n",
1700                user,keystr_from_pk(keyblock->pkt->pkt.public_key),
1701                reason);
1702
1703       xfree(user);
1704     }
1705
1706   return deleted;
1707 }
1708
1709 /* Needs to be called after a merge_keys_and_selfsig() */
1710 void
1711 clean_one_uid(KBNODE keyblock,KBNODE uidnode,int noisy,int self_only,
1712               int *uids_cleaned,int *sigs_cleaned)
1713 {
1714   int dummy;
1715
1716   assert(keyblock->pkt->pkttype==PKT_PUBLIC_KEY);
1717   assert(uidnode->pkt->pkttype==PKT_USER_ID);
1718
1719   if(!uids_cleaned)
1720     uids_cleaned=&dummy;
1721
1722   if(!sigs_cleaned)
1723     sigs_cleaned=&dummy;
1724
1725   /* Do clean_uid_from_key first since if it fires off, we don't
1726      have to bother with the other */
1727   *uids_cleaned+=clean_uid_from_key(keyblock,uidnode,noisy);
1728   if(!uidnode->pkt->pkt.user_id->flags.compacted)
1729     *sigs_cleaned+=clean_sigs_from_uid(keyblock,uidnode,noisy,self_only);
1730 }
1731
1732 void
1733 clean_key(KBNODE keyblock,int noisy,int self_only,
1734           int *uids_cleaned,int *sigs_cleaned)
1735 {
1736   KBNODE uidnode;
1737
1738   merge_keys_and_selfsig(keyblock);
1739
1740   for(uidnode=keyblock->next;
1741       uidnode && uidnode->pkt->pkttype!=PKT_PUBLIC_SUBKEY;
1742       uidnode=uidnode->next)
1743     if(uidnode->pkt->pkttype==PKT_USER_ID)
1744       clean_one_uid(keyblock,uidnode,noisy,self_only,
1745                     uids_cleaned,sigs_cleaned);
1746 }
1747
1748 /* Returns a sanitized copy of the regexp (which might be "", but not
1749    NULL). */
1750 #ifndef DISABLE_REGEX
1751 static char *
1752 sanitize_regexp(const char *old)
1753 {
1754   size_t start=0,len=strlen(old),idx=0;
1755   int escaped=0,standard_bracket=0;
1756   char *new=xmalloc((len*2)+1); /* enough to \-escape everything if we
1757                                    have to */
1758
1759   /* There are basically two commonly-used regexps here.  GPG and most
1760      versions of PGP use "<[^>]+[@.]example\.com>$" and PGP (9)
1761      command line uses "example.com" (i.e. whatever the user specfies,
1762      and we can't expect users know to use "\." instead of ".").  So
1763      here are the rules: we're allowed to start with "<[^>]+[@.]" and
1764      end with ">$" or start and end with nothing.  In between, the
1765      only legal regex character is ".", and everything else gets
1766      escaped.  Part of the gotcha here is that some regex packages
1767      allow more than RFC-4880 requires.  For example, 4880 has no "{}"
1768      operator, but GNU regex does.  Commenting removes these operators
1769      from consideration.  A possible future enhancement is to use
1770      commenting to effectively back off a given regex to the Henry
1771      Spencer syntax in 4880. -dshaw */
1772
1773   /* Are we bracketed between "<[^>]+[@.]" and ">$" ? */
1774   if(len>=12 && strncmp(old,"<[^>]+[@.]",10)==0
1775      && old[len-2]=='>' && old[len-1]=='$')
1776     {
1777       strcpy(new,"<[^>]+[@.]");
1778       idx=strlen(new);
1779       standard_bracket=1;
1780       start+=10;
1781       len-=2;
1782     }
1783
1784   /* Walk the remaining characters and ensure that everything that is
1785      left is not an operational regex character. */
1786   for(;start<len;start++)
1787     {
1788       if(!escaped && old[start]=='\\')
1789         escaped=1;
1790       else if(!escaped && old[start]!='.')
1791         new[idx++]='\\';
1792       else
1793         escaped=0;
1794
1795       new[idx++]=old[start];
1796     }
1797
1798   new[idx]='\0';
1799
1800   /* Note that the (sub)string we look at might end with a bare "\".
1801      If it does, leave it that way.  If the regexp actually ended with
1802      ">$", then it was escaping the ">" and is fine.  If the regexp
1803      actually ended with the bare "\", then it's an illegal regexp and
1804      regcomp should kick it out. */
1805
1806   if(standard_bracket)
1807     strcat(new,">$");
1808
1809   return new;
1810 }
1811 #endif /*!DISABLE_REGEX*/
1812
1813 /* Used by validate_one_keyblock to confirm a regexp within a trust
1814    signature.  Returns 1 for match, and 0 for no match or regex
1815    error. */
1816 static int
1817 check_regexp(const char *expr,const char *string)
1818 {
1819 #ifdef DISABLE_REGEX
1820   /* When DISABLE_REGEX is defined, assume all regexps do not
1821      match. */
1822   return 0;
1823 #else
1824   int ret;
1825   char *regexp;
1826
1827   regexp=sanitize_regexp(expr);
1828
1829 #ifdef __riscos__
1830   ret=riscos_check_regexp(expr, string, DBG_TRUST);
1831 #else
1832   {
1833     regex_t pat;
1834
1835     ret=regcomp(&pat,regexp,REG_ICASE|REG_NOSUB|REG_EXTENDED);
1836     if(ret==0)
1837       {
1838         ret=regexec(&pat,string,0,NULL,0);
1839         regfree(&pat);
1840         ret=(ret==0);
1841       }
1842   }
1843 #endif
1844
1845   if(DBG_TRUST)
1846     log_debug("regexp `%s' (`%s') on `%s': %s\n",
1847               regexp,expr,string,ret==0?"YES":"NO");
1848
1849   xfree(regexp);
1850
1851   return ret;
1852 #endif
1853 }
1854
1855 /*
1856  * Return true if the key is signed by one of the keys in the given
1857  * key ID list.  User IDs with a valid signature are marked by node
1858  * flags as follows:
1859  *  flag bit 0: There is at least one signature
1860  *           1: There is marginal confidence that this is a legitimate uid
1861  *           2: There is full confidence that this is a legitimate uid.
1862  *           8: Used for internal purposes.
1863  *           9: Ditto (in mark_usable_uid_certs())
1864  *          10: Ditto (ditto)
1865  * This function assumes that all kbnode flags are cleared on entry.
1866  */
1867 static int
1868 validate_one_keyblock (KBNODE kb, struct key_item *klist,
1869                        u32 curtime, u32 *next_expire)
1870 {
1871   struct key_item *kr;
1872   KBNODE node, uidnode=NULL;
1873   PKT_user_id *uid=NULL;
1874   PKT_public_key *pk = kb->pkt->pkt.public_key;
1875   u32 main_kid[2];
1876   int issigned=0, any_signed = 0;
1877
1878   keyid_from_pk(pk, main_kid);
1879   for (node=kb; node; node = node->next)
1880     {
1881       /* A bit of discussion here: is it better for the web of trust
1882          to be built among only self-signed uids?  On the one hand, a
1883          self-signed uid is a statement that the key owner definitely
1884          intended that uid to be there, but on the other hand, a
1885          signed (but not self-signed) uid does carry trust, of a sort,
1886          even if it is a statement being made by people other than the
1887          key owner "through" the uids on the key owner's key.  I'm
1888          going with the latter.  However, if the user ID was
1889          explicitly revoked, or passively allowed to expire, that
1890          should stop validity through the user ID until it is
1891          resigned.  -dshaw */
1892
1893       if (node->pkt->pkttype == PKT_USER_ID
1894           && !node->pkt->pkt.user_id->is_revoked
1895           && !node->pkt->pkt.user_id->is_expired)
1896         {
1897           if (uidnode && issigned)
1898             {
1899               if (uid->help_full_count >= opt.completes_needed
1900                   || uid->help_marginal_count >= opt.marginals_needed )
1901                 uidnode->flag |= 4; 
1902               else if (uid->help_full_count || uid->help_marginal_count)
1903                 uidnode->flag |= 2;
1904               uidnode->flag |= 1;
1905               any_signed = 1;
1906             }
1907           uidnode = node;
1908           uid=uidnode->pkt->pkt.user_id;
1909
1910           /* If the selfsig is going to expire... */
1911           if(uid->expiredate && uid->expiredate<*next_expire)
1912             *next_expire = uid->expiredate;
1913
1914           issigned = 0;
1915           get_validity_counts(pk,uid);
1916           mark_usable_uid_certs (kb, uidnode, main_kid, klist, 
1917                                  curtime, next_expire);
1918         }
1919       else if (node->pkt->pkttype == PKT_SIGNATURE
1920                && (node->flag & (1<<8)) && uid)
1921         {
1922           /* Note that we are only seeing unrevoked sigs here */
1923           PKT_signature *sig = node->pkt->pkt.signature;
1924           
1925           kr = is_in_klist (klist, sig);
1926           /* If the trust_regexp does not match, it's as if the sig
1927              did not exist.  This is safe for non-trust sigs as well
1928              since we don't accept a regexp on the sig unless it's a
1929              trust sig. */
1930           if (kr && (kr->trust_regexp==NULL || opt.trust_model!=TM_PGP ||
1931                      (uidnode && check_regexp(kr->trust_regexp,
1932                                             uidnode->pkt->pkt.user_id->name))))
1933             {
1934               if(DBG_TRUST && opt.trust_model==TM_PGP && sig->trust_depth)
1935                 log_debug("trust sig on %s, sig depth is %d, kr depth is %d\n",
1936                           uidnode->pkt->pkt.user_id->name,sig->trust_depth,
1937                           kr->trust_depth);
1938
1939               /* Are we part of a trust sig chain?  We always favor
1940                  the latest trust sig, rather than the greater or
1941                  lesser trust sig or value.  I could make a decent
1942                  argument for any of these cases, but this seems to be
1943                  what PGP does, and I'd like to be compatible. -dms */
1944               if(opt.trust_model==TM_PGP && sig->trust_depth
1945                  && pk->trust_timestamp<=sig->timestamp
1946                  && (sig->trust_depth<=kr->trust_depth
1947                      || kr->ownertrust==TRUST_ULTIMATE))
1948                 {
1949                   /* If we got here, we know that:
1950
1951                      this is a trust sig.
1952
1953                      it's a newer trust sig than any previous trust
1954                      sig on this key (not uid).
1955
1956                      it is legal in that it was either generated by an
1957                      ultimate key, or a key that was part of a trust
1958                      chain, and the depth does not violate the
1959                      original trust sig.
1960
1961                      if there is a regexp attached, it matched
1962                      successfully.
1963                   */
1964
1965                   if(DBG_TRUST)
1966                     log_debug("replacing trust value %d with %d and "
1967                               "depth %d with %d\n",
1968                               pk->trust_value,sig->trust_value,
1969                               pk->trust_depth,sig->trust_depth);
1970
1971                   pk->trust_value=sig->trust_value;
1972                   pk->trust_depth=sig->trust_depth-1;
1973
1974                   /* If the trust sig contains a regexp, record it
1975                      on the pk for the next round. */
1976                   if(sig->trust_regexp)
1977                     pk->trust_regexp=sig->trust_regexp;
1978                 }
1979
1980               if (kr->ownertrust == TRUST_ULTIMATE)
1981                 uid->help_full_count = opt.completes_needed;
1982               else if (kr->ownertrust == TRUST_FULLY)
1983                 uid->help_full_count++;
1984               else if (kr->ownertrust == TRUST_MARGINAL)
1985                 uid->help_marginal_count++;
1986               issigned = 1;
1987             }
1988         }
1989     }
1990
1991   if (uidnode && issigned)
1992     {
1993       if (uid->help_full_count >= opt.completes_needed
1994           || uid->help_marginal_count >= opt.marginals_needed )
1995         uidnode->flag |= 4; 
1996       else if (uid->help_full_count || uid->help_marginal_count)
1997         uidnode->flag |= 2;
1998       uidnode->flag |= 1;
1999       any_signed = 1;
2000     }
2001
2002   return any_signed;
2003 }
2004
2005
2006 static int
2007 search_skipfnc (void *opaque, u32 *kid, PKT_user_id *dummy)
2008 {
2009   return test_key_hash_table ((KeyHashTable)opaque, kid);
2010 }
2011
2012
2013 /*
2014  * Scan all keys and return a key_array of all suitable keys from
2015  * kllist.  The caller has to pass keydb handle so that we don't use
2016  * to create our own.  Returns either a key_array or NULL in case of
2017  * an error.  No results found are indicated by an empty array.
2018  * Caller hast to release the returned array.  
2019  */
2020 static struct key_array *
2021 validate_key_list (KEYDB_HANDLE hd, KeyHashTable full_trust,
2022                    struct key_item *klist, u32 curtime, u32 *next_expire)
2023 {
2024   KBNODE keyblock = NULL;
2025   struct key_array *keys = NULL;
2026   size_t nkeys, maxkeys;
2027   int rc;
2028   KEYDB_SEARCH_DESC desc;
2029   
2030   maxkeys = 1000;
2031   keys = xmalloc ((maxkeys+1) * sizeof *keys);
2032   nkeys = 0;
2033   
2034   rc = keydb_search_reset (hd);
2035   if (rc)
2036     {
2037       log_error ("keydb_search_reset failed: %s\n", g10_errstr(rc));
2038       xfree (keys);
2039       return NULL;
2040     }
2041
2042   memset (&desc, 0, sizeof desc);
2043   desc.mode = KEYDB_SEARCH_MODE_FIRST;
2044   desc.skipfnc = search_skipfnc;
2045   desc.skipfncvalue = full_trust;
2046   rc = keydb_search (hd, &desc, 1);
2047   if (rc == -1)
2048     {
2049       keys[nkeys].keyblock = NULL;
2050       return keys;
2051     }
2052   if (rc)
2053     {
2054       log_error ("keydb_search_first failed: %s\n", g10_errstr(rc));
2055       xfree (keys);
2056       return NULL;
2057     }
2058   
2059   desc.mode = KEYDB_SEARCH_MODE_NEXT; /* change mode */
2060   do
2061     {
2062       PKT_public_key *pk;
2063         
2064       rc = keydb_get_keyblock (hd, &keyblock);
2065       if (rc) 
2066         {
2067           log_error ("keydb_get_keyblock failed: %s\n", g10_errstr(rc));
2068           xfree (keys);
2069           return NULL;
2070         }
2071       
2072       if ( keyblock->pkt->pkttype != PKT_PUBLIC_KEY) 
2073         {
2074           log_debug ("ooops: invalid pkttype %d encountered\n",
2075                      keyblock->pkt->pkttype);
2076           dump_kbnode (keyblock);
2077           release_kbnode(keyblock);
2078           continue;
2079         }
2080
2081       /* prepare the keyblock for further processing */
2082       merge_keys_and_selfsig (keyblock); 
2083       clear_kbnode_flags (keyblock);
2084       pk = keyblock->pkt->pkt.public_key;
2085       if (pk->has_expired || pk->is_revoked)
2086         {
2087           /* it does not make sense to look further at those keys */
2088           mark_keyblock_seen (full_trust, keyblock);
2089         }
2090       else if (validate_one_keyblock (keyblock, klist, curtime, next_expire))
2091         {
2092           KBNODE node;
2093
2094           if (pk->expiredate && pk->expiredate >= curtime
2095               && pk->expiredate < *next_expire)
2096             *next_expire = pk->expiredate;
2097
2098           if (nkeys == maxkeys) {
2099             maxkeys += 1000;
2100             keys = xrealloc (keys, (maxkeys+1) * sizeof *keys);
2101           }
2102           keys[nkeys++].keyblock = keyblock;
2103
2104           /* Optimization - if all uids are fully trusted, then we
2105              never need to consider this key as a candidate again. */
2106
2107           for (node=keyblock; node; node = node->next)
2108             if (node->pkt->pkttype == PKT_USER_ID && !(node->flag & 4))
2109               break;
2110
2111           if(node==NULL)
2112             mark_keyblock_seen (full_trust, keyblock);
2113
2114           keyblock = NULL;
2115         }
2116
2117       release_kbnode (keyblock);
2118       keyblock = NULL;
2119     } 
2120   while ( !(rc = keydb_search (hd, &desc, 1)) );
2121   if (rc && rc != -1) 
2122     {
2123       log_error ("keydb_search_next failed: %s\n", g10_errstr(rc));
2124       xfree (keys);
2125       return NULL;
2126     }
2127
2128   keys[nkeys].keyblock = NULL;
2129   return keys;
2130
2131
2132 /* Caller must sync */
2133 static void
2134 reset_trust_records(void)
2135 {
2136   TRUSTREC rec;
2137   ulong recnum;
2138   int count = 0, nreset = 0;
2139
2140   for (recnum=1; !tdbio_read_record (recnum, &rec, 0); recnum++ ) 
2141     {
2142       if(rec.rectype==RECTYPE_TRUST)
2143         {
2144           count++;
2145           if(rec.r.trust.min_ownertrust)
2146             {
2147               rec.r.trust.min_ownertrust=0;
2148               write_record(&rec);
2149             }
2150
2151         }
2152       else if(rec.rectype==RECTYPE_VALID
2153               && ((rec.r.valid.validity&TRUST_MASK)
2154                   || rec.r.valid.marginal_count
2155                   || rec.r.valid.full_count))
2156         {
2157           rec.r.valid.validity &= ~TRUST_MASK;
2158           rec.r.valid.marginal_count=rec.r.valid.full_count=0;
2159           nreset++;
2160           write_record(&rec);
2161         }
2162
2163     }
2164
2165   if (opt.verbose)
2166     log_info (_("%d keys processed (%d validity counts cleared)\n"),
2167               count, nreset);
2168 }
2169
2170 /*
2171  * Run the key validation procedure.
2172  *
2173  * This works this way:
2174  * Step 1: Find all ultimately trusted keys (UTK).
2175  *         mark them all as seen and put them into klist.
2176  * Step 2: loop max_cert_times
2177  * Step 3:   if OWNERTRUST of any key in klist is undefined
2178  *             ask user to assign ownertrust
2179  * Step 4:   Loop over all keys in the keyDB which are not marked seen 
2180  * Step 5:     if key is revoked or expired
2181  *                mark key as seen
2182  *                continue loop at Step 4
2183  * Step 6:     For each user ID of that key signed by a key in klist
2184  *                Calculate validity by counting trusted signatures.
2185  *                Set validity of user ID
2186  * Step 7:     If any signed user ID was found
2187  *                mark key as seen
2188  *             End Loop
2189  * Step 8:   Build a new klist from all fully trusted keys from step 6
2190  *           End Loop
2191  *         Ready  
2192  *
2193  */
2194 static int
2195 validate_keys (int interactive)
2196 {
2197   int rc = 0;
2198   int quit=0;
2199   struct key_item *klist = NULL;
2200   struct key_item *k;
2201   struct key_array *keys = NULL;
2202   struct key_array *kar;
2203   KEYDB_HANDLE kdb = NULL;
2204   KBNODE node;
2205   int depth;
2206   int ot_unknown, ot_undefined, ot_never, ot_marginal, ot_full, ot_ultimate;
2207   KeyHashTable stored,used,full_trust;
2208   u32 start_time, next_expire;
2209
2210   /* Make sure we have all sigs cached.  TODO: This is going to
2211      require some architectual re-thinking, as it is agonizingly slow.
2212      Perhaps combine this with reset_trust_records(), or only check
2213      the caches on keys that are actually involved in the web of
2214      trust. */
2215   keydb_rebuild_caches(0);
2216
2217   start_time = make_timestamp ();
2218   next_expire = 0xffffffff; /* set next expire to the year 2106 */
2219   stored = new_key_hash_table ();
2220   used = new_key_hash_table ();
2221   full_trust = new_key_hash_table ();
2222
2223   kdb = keydb_new (0);
2224   reset_trust_records();
2225
2226   /* Fixme: Instead of always building a UTK list, we could just build it
2227    * here when needed */
2228   if (!utk_list)
2229     {
2230       if (!opt.quiet)
2231         log_info (_("no ultimately trusted keys found\n"));
2232       goto leave;
2233     }
2234
2235   /* mark all UTKs as used and fully_trusted and set validity to
2236      ultimate */
2237   for (k=utk_list; k; k = k->next)
2238     {
2239       KBNODE keyblock;
2240       PKT_public_key *pk;
2241
2242       keyblock = get_pubkeyblock (k->kid);
2243       if (!keyblock)
2244         {
2245           log_error (_("public key of ultimately"
2246                        " trusted key %s not found\n"), keystr(k->kid));
2247           continue;
2248         }
2249       mark_keyblock_seen (used, keyblock);
2250       mark_keyblock_seen (stored, keyblock);
2251       mark_keyblock_seen (full_trust, keyblock);
2252       pk = keyblock->pkt->pkt.public_key;
2253       for (node=keyblock; node; node = node->next)
2254         {
2255           if (node->pkt->pkttype == PKT_USER_ID)
2256             update_validity (pk, node->pkt->pkt.user_id, 0, TRUST_ULTIMATE);
2257         }
2258       if ( pk->expiredate && pk->expiredate >= start_time
2259            && pk->expiredate < next_expire)
2260         next_expire = pk->expiredate;
2261       
2262       release_kbnode (keyblock);
2263       do_sync ();
2264     }
2265
2266   klist = utk_list;
2267
2268   log_info(_("%d marginal(s) needed, %d complete(s) needed, %s trust model\n"),
2269            opt.marginals_needed,opt.completes_needed,trust_model_string());
2270
2271   for (depth=0; depth < opt.max_cert_depth; depth++)
2272     {
2273       int valids=0,key_count;
2274       /* See whether we should assign ownertrust values to the keys in
2275          klist.  */
2276       ot_unknown = ot_undefined = ot_never = 0;
2277       ot_marginal = ot_full = ot_ultimate = 0;
2278       for (k=klist; k; k = k->next)
2279         {
2280           int min=0;
2281
2282           /* 120 and 60 are as per RFC2440 */
2283           if(k->trust_value>=120)
2284             min=TRUST_FULLY;
2285           else if(k->trust_value>=60)
2286             min=TRUST_MARGINAL;
2287
2288           if(min!=k->min_ownertrust)
2289             update_min_ownertrust(k->kid,min);
2290
2291           if (interactive && k->ownertrust == TRUST_UNKNOWN)
2292             {
2293               k->ownertrust = ask_ownertrust (k->kid,min);
2294
2295               if (k->ownertrust == -1)
2296                 {
2297                   quit=1;
2298                   goto leave;
2299                 }
2300             }
2301
2302           /* This can happen during transition from an old trustdb
2303              before trust sigs.  It can also happen if a user uses two
2304              different versions of GnuPG or changes the --trust-model
2305              setting. */
2306           if(k->ownertrust<min)
2307             {
2308               if(DBG_TRUST)
2309                 log_debug("key %08lX%08lX:"
2310                           " overriding ownertrust `%s' with `%s'\n",
2311                           (ulong)k->kid[0],(ulong)k->kid[1],
2312                           trust_value_to_string(k->ownertrust),
2313                           trust_value_to_string(min));
2314
2315               k->ownertrust=min;
2316             }
2317
2318           if (k->ownertrust == TRUST_UNKNOWN)
2319             ot_unknown++;
2320           else if (k->ownertrust == TRUST_UNDEFINED)
2321             ot_undefined++;
2322           else if (k->ownertrust == TRUST_NEVER)
2323             ot_never++;
2324           else if (k->ownertrust == TRUST_MARGINAL)
2325             ot_marginal++;
2326           else if (k->ownertrust == TRUST_FULLY)
2327             ot_full++;
2328           else if (k->ownertrust == TRUST_ULTIMATE)
2329             ot_ultimate++;
2330
2331           valids++;
2332         }
2333
2334       /* Find all keys which are signed by a key in kdlist */
2335       keys = validate_key_list (kdb, full_trust, klist,
2336                                 start_time, &next_expire);
2337       if (!keys) 
2338         {
2339           log_error ("validate_key_list failed\n");
2340           rc = G10ERR_GENERAL;
2341           goto leave;
2342         }
2343
2344       for (key_count=0, kar=keys; kar->keyblock; kar++, key_count++)
2345         ;
2346
2347       /* Store the calculated valididation status somewhere */
2348       if (opt.verbose > 1)
2349         dump_key_array (depth, keys);
2350
2351       for (kar=keys; kar->keyblock; kar++)
2352           store_validation_status (depth, kar->keyblock, stored);
2353
2354       log_info (_("depth: %d  valid: %3d  signed: %3d"
2355                   "  trust: %d-, %dq, %dn, %dm, %df, %du\n"), 
2356                 depth, valids, key_count, ot_unknown, ot_undefined,
2357                 ot_never, ot_marginal, ot_full, ot_ultimate ); 
2358
2359       /* Build a new kdlist from all fully valid keys in KEYS */
2360       if (klist != utk_list)
2361         release_key_items (klist);
2362       klist = NULL;
2363       for (kar=keys; kar->keyblock; kar++)
2364         {
2365           for (node=kar->keyblock; node; node = node->next)
2366             {
2367               if (node->pkt->pkttype == PKT_USER_ID && (node->flag & 4))
2368                 {
2369                   u32 kid[2];
2370
2371                   /* have we used this key already? */
2372                   keyid_from_pk (kar->keyblock->pkt->pkt.public_key, kid);
2373                   if(test_key_hash_table(used,kid)==0)
2374                     {
2375                       /* Normally we add both the primary and subkey
2376                          ids to the hash via mark_keyblock_seen, but
2377                          since we aren't using this hash as a skipfnc,
2378                          that doesn't matter here. */
2379                       add_key_hash_table (used,kid);
2380                       k = new_key_item ();
2381                       k->kid[0]=kid[0];
2382                       k->kid[1]=kid[1];
2383                       k->ownertrust =
2384                         (get_ownertrust (kar->keyblock->pkt->pkt.public_key)
2385                          & TRUST_MASK);
2386                       k->min_ownertrust =
2387                         get_min_ownertrust(kar->keyblock->pkt->pkt.public_key);
2388                       k->trust_depth=
2389                         kar->keyblock->pkt->pkt.public_key->trust_depth;
2390                       k->trust_value=
2391                         kar->keyblock->pkt->pkt.public_key->trust_value;
2392                       if(kar->keyblock->pkt->pkt.public_key->trust_regexp)
2393                         k->trust_regexp=
2394                           xstrdup(kar->keyblock->pkt->
2395                                    pkt.public_key->trust_regexp);
2396                       k->next = klist;
2397                       klist = k;
2398                       break;
2399                     }
2400                 }
2401             }
2402         }
2403       release_key_array (keys);
2404       keys = NULL;
2405       if (!klist)
2406         break; /* no need to dive in deeper */
2407     }
2408
2409  leave:
2410   keydb_release (kdb);
2411   release_key_array (keys);
2412   release_key_items (klist);
2413   release_key_hash_table (full_trust);
2414   release_key_hash_table (used);
2415   release_key_hash_table (stored);
2416   if (!rc && !quit) /* mark trustDB as checked */
2417     {
2418       if (next_expire == 0xffffffff || next_expire < start_time )
2419         tdbio_write_nextcheck (0); 
2420       else
2421         {
2422           tdbio_write_nextcheck (next_expire); 
2423           log_info (_("next trustdb check due at %s\n"),
2424                     strtimestamp (next_expire));
2425         }
2426
2427       if(tdbio_update_version_record()!=0)
2428         {
2429           log_error(_("unable to update trustdb version record: "
2430                       "write failed: %s\n"), g10_errstr(rc));
2431           tdbio_invalid();
2432         }
2433
2434       do_sync ();
2435       pending_check_trustdb = 0;
2436     }
2437
2438   return rc;
2439 }