merge.c

   1 /*
   2  * merge.c - Routines to merge OpenPGP public keys.
   3  *
   4  * Jonathan McDowell <noodles@earth.li>
   5  *
   6  * Copyright 2002 Project Purple
   7  */
   8
   9 #include <assert.h>
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12
  13 #include "keydb.h"
  14 #include "keyid.h"
  15 #include "keyindex.h"
  16 #include "keystructs.h"
  17 #include "ll.h"
  18 #include "mem.h"
  19 #include "merge.h"
  20
  21 /**
  22  *      compare_packets - Check to see if 2 OpenPGP packets are the same.
  23  *      @a: The first packet to compare.
  24  *      @b: The second packet to compare.
  25  *
  26  *      Takes 2 packets and returns true if they are the same and false
  27  *      otherwise.
  28  */
  29 bool compare_packets(struct openpgp_packet *a, struct openpgp_packet *b)
  30 {
  31         return (a->tag == b->tag && a->length == b->length &&
  32                 !memcmp(a->data, b->data, b->length));
  33 }
  34
  35 /**
  36  *      compare_signatures - Check to see if 2 OpenPGP signatures are the same.
  37  *      @a: The first signature to compare.
  38  *      @b: The second signature to compare.
  39  *
  40  *      Takes 2 signature packets and returns true if they are the same and
  41  *      false otherwise.
  42  */
  43 bool compare_signatures(struct openpgp_packet *a, struct openpgp_packet *b)
  44 {
  45         return (sig_keyid(a) == sig_keyid(b));
  46 }
  47
  48 /**
  49  *      find_packet - Checks to see if an OpenPGP packet exists in a list.
  50  *      @packet_list: The list of packets to look in.
  51  *      @packet: The packet to look for.
  52  *
  53  *      Walks through the packet_list checking to see if the packet given is
  54  *      present in it. Returns true if it is.
  55  */
  56 bool find_packet(struct openpgp_packet_list *packet_list,
  57                         struct openpgp_packet *packet)
  58 {
  59         bool found = false;
  60
  61         while (!found && packet_list != NULL) {
  62                 if (compare_packets(packet_list->packet, packet)) {
  63                         found = true;
  64                 }
  65                 packet_list = packet_list -> next;
  66         }
  67
  68         return found;
  69 }
  70
  71 /**
  72  *      find_signature - Checks to see if an OpenPGP signature exists in a list.
  73  *      @packet_list: The list of packets to look in.
  74  *      @packet: The signature to look for.
  75  *
  76  *      Walks through the packet_list checking to see if the signature given is
  77  *      present in it. Returns a pointer to it if it is, NULL otherwise.
  78  *
  79  */
  80 struct openpgp_packet_list *find_signature(
  81                         struct openpgp_packet_list *packet_list,
  82                         struct openpgp_packet *packet)
  83 {
  84         struct openpgp_packet_list *found = NULL;
  85
  86         while (!found && packet_list != NULL) {
  87                 if (compare_signatures(packet_list->packet, packet)) {
  88                         found = packet_list;
  89                 }
  90                 packet_list = packet_list -> next;
  91         }
  92
  93         return found;
  94 }
  95
  96 /**
  97  *      get_signed_packet - Gets a signed packet from a list.
  98  *      @packet_list: The list of packets to look in.
  99  *      @packet: The packet to look for.
 100  *
 101  *      Walks through the signedpacket_list looking for the supplied packet and
 102  *      returns it if found. Otherwise returns NULL.
 103  */
 104 struct openpgp_signedpacket_list *find_signed_packet(
 105                 struct openpgp_signedpacket_list *packet_list,
 106                 struct openpgp_packet *packet)
 107 {
 108         struct openpgp_signedpacket_list *found = NULL;
 109
 110         while (found == NULL && packet_list != NULL) {
 111                 if (compare_packets(packet_list->packet, packet)) {
 112                         found = packet_list;
 113                 }
 114                 packet_list = packet_list -> next;
 115         }
 116
 117         return found;
 118 }
 119
 120 /**
 121  *      remove_signed_packet - Removes a signed packet from a list.
 122  *      @packet_list: The list of packets to look in.
 123  *      @packet: The packet to remove.
 124  *
 125  *      Walks through the signedpacket_list looking for the supplied packet and
 126  *      removes it if found. Assumes the packet can only exist a maximum of
 127  *      once in the list.
 128  */
 129 bool remove_signed_packet(struct openpgp_signedpacket_list **packet_list,
 130                 struct openpgp_signedpacket_list **list_end,
 131                 struct openpgp_packet *packet)
 132 {
 133         struct openpgp_signedpacket_list *cur = NULL;
 134         struct openpgp_signedpacket_list *prev = NULL;
 135         bool found = false;
 136
 137         for (cur = *packet_list; !found && (cur != NULL); cur = cur->next) {
 138                 if (compare_packets(cur->packet, packet)) {
 139                         found = true;
 140                         if (prev == NULL) {
 141                                 *packet_list = cur->next;
 142                         } else {
 143                                 prev->next = cur->next;
 144                         }
 145                         if (cur->next == NULL) {
 146                                 *list_end = prev;
 147                         }
 148                         // TODO: Free the removed signed packet...
 149                 }
 150                 prev = cur;
 151         }
 152
 153         return found;
 154 }
 155
 156 /**
 157  *      merge_packet_sigs - Takes 2 signed packets and merges their sigs.
 158  *      @old: The old signed packet.
 159  *      @new: The new signed packet.
 160  *
 161  *      Takes 2 signed packet list structures and the sigs of the packets on
 162  *      the head of these structures. These packets must both be the same and
 163  *      the fully merged structure is returned in old and the minimal
 164  *      difference to get from old to new in new.
 165  */
 166 int merge_packet_sigs(struct openpgp_signedpacket_list *old,
 167                         struct openpgp_signedpacket_list *new)
 168 {
 169         struct openpgp_packet_list      *lastpacket = NULL;
 170         struct openpgp_packet_list      *curpacket = NULL;
 171         struct openpgp_packet_list      *nextpacket = NULL;
 172
 173         assert(compare_packets(old->packet, new->packet));
 174
 175         curpacket = new->sigs;
 176         while (curpacket != NULL) {
 177                 nextpacket = curpacket->next;
 178                 /*
 179                  * TODO: We should be checking the signature and then
 180                  * potentially merging/replacing it depending on the subpackets
 181                  * really. For now this stops us adding the same one twice
 182                  * however.
 183                  */
 184                 if (find_signature(old->sigs, curpacket->packet)) {
 185                         /*
 186                          * We already have this sig, remove it from the
 187                          * difference list and free the memory allocated for
 188                          * it.
 189                          */
 190                         if (lastpacket != NULL) {
 191                                 lastpacket->next = curpacket->next;
 192                         } else {
 193                                 assert(curpacket == new->sigs);
 194                                 new->sigs = curpacket->next;
 195                         }
 196                         curpacket->next = NULL;
 197                         free_packet_list(curpacket);
 198                 } else {
 199                         lastpacket = curpacket;
 200                 }
 201                 curpacket = nextpacket;
 202         }
 203         new->last_sig = lastpacket;
 204
 205         /*
 206          * What's left on new->sigs now are the new signatures, so add them to
 207          * old->sigs.
 208          */
 209         packet_list_add(&old->sigs, &old->last_sig, new->sigs);
 210
 211         return 0;
 212 }
 213
 214 /**
 215  *      merge_signed_packets - Takes 2 lists of signed packets and merges them.
 216  *      @old: The old signed packet list.
 217  *      @new: The new signed packet list.
 218  *
 219  *      Takes 2 lists of signed packets and merges them. The complete list of
 220  *      signed packets & sigs is returned in old and the minimal set of
 221  *      differences required to get from old to new in new.
 222  */
 223 int merge_signed_packets(struct openpgp_signedpacket_list **old,
 224                         struct openpgp_signedpacket_list **old_end,
 225                         struct openpgp_signedpacket_list **new,
 226                         struct openpgp_signedpacket_list **new_end)
 227 {
 228         struct openpgp_signedpacket_list *curelem = NULL;
 229         struct openpgp_signedpacket_list *newelem = NULL;
 230
 231         for (curelem = *old; curelem != NULL; curelem = curelem->next) {
 232                 newelem = find_signed_packet(*new, curelem->packet);
 233                 if (newelem != NULL) {
 234                         merge_packet_sigs(curelem, newelem);
 235
 236                         /*
 237                          * If there are no sigs left on the new signed packet
 238                          * then remove it from the list.
 239                          */
 240                         if (newelem->sigs == NULL) {
 241                                 remove_signed_packet(new,
 242                                                 new_end,
 243                                                 newelem->packet);
 244                         }
 245                 }
 246         }
 247
 248         /*
 249          * If *new != NULL now then there might be UIDs on the new key that
 250          * weren't on the old key. Walk through them, checking if the UID is
 251          * on the old key and if not adding them to it.
 252          */
 253         for (curelem = *new; curelem != NULL;
 254                         curelem = curelem->next) {
 255
 256                 if (find_signed_packet(*old, curelem->packet) == NULL) {
 257                         ADD_PACKET_TO_LIST((*old_end),
 258                                 packet_dup(curelem->packet));
 259                         if (*old == NULL) {
 260                                 *old = *old_end;
 261                         }
 262                         packet_list_add(&(*old_end)->sigs,
 263                                 &(*old_end)->last_sig,
 264                                 curelem->sigs);
 265                 }
 266         }
 267
 268         return 0;
 269 }
 270
 271 /**
 272  *      merge_keys - Takes 2 public keys and merges them.
 273  *      @a: The old key. The merged key is returned in this structure.
 274  *      @b: The new key. The changed from old to new keys are returned in this
 275  *              structure.
 276  *
 277  *      This function takes 2 keys and merges them. It then returns the merged
 278  *      key in a and the difference between this new key and the original a
 279  *      in b (ie newb contains the minimum amount of detail necessary to
 280  *      convert olda to newa). The intention is that olda is provided from
 281  *      internal storage and oldb from the remote user. newa is then stored in
 282  *      internal storage and newb is sent to all our keysync peers.
 283  */
 284 int merge_keys(struct openpgp_publickey *a, struct openpgp_publickey *b)
 285 {
 286         int rc = 0; /* Return code */
 287         struct openpgp_packet_list      *curpacket = NULL;
 288         struct openpgp_packet_list      *lastpacket = NULL;
 289         struct openpgp_packet_list      *nextpacket = NULL;
 290
 291         if (a == NULL || b == NULL) {
 292                 /*
 293                  * Do nothing.
 294                  */
 295                 rc = 1;
 296         } else if (get_keyid(a) != get_keyid(b)) {
 297                 /*
 298                  * Key IDs are different.
 299                  */
 300                 rc = -1;
 301         } else {
 302                 /*
 303                  * Key IDs are the same, so I guess we have to merge them.
 304                  */
 305                 curpacket = b->revocations;
 306                 while (curpacket != NULL) {
 307                         nextpacket = curpacket->next;
 308                         if (find_packet(a->revocations, curpacket->packet)) {
 309                                 /*
 310                                  * We already have this revocation, remove it
 311                                  * from the difference list and free the memory
 312                                  * allocated for it.
 313                                  */
 314
 315                                 if (lastpacket != NULL) {
 316                                         lastpacket->next = curpacket->next;
 317                                 } else {
 318                                         assert(curpacket == b->revocations);
 319                                         b->revocations = curpacket->next;
 320                                 }
 321                                 curpacket->next = NULL;
 322                                 free_packet_list(curpacket);
 323
 324                         } else {
 325                                 lastpacket = curpacket;
 326                         }
 327                         curpacket = nextpacket;
 328                 }
 329                 b->last_revocation = lastpacket;
 330
 331                 /*
 332                  * Anything left on b->revocations doesn't exist on
 333                  * a->revocations, so add them to the list.
 334                  */
 335                 packet_list_add(&a->revocations,
 336                                 &a->last_revocation,
 337                                 b->revocations);
 338
 339                 /*
 340                  * Merge uids (signed list).
 341                  * Merge subkeys (signed list).
 342                  */
 343                 merge_signed_packets(&a->uids, &a->last_uid,
 344                                 &b->uids, &b->last_uid);
 345                 merge_signed_packets(&a->subkeys, &a->last_subkey,
 346                                 &b->subkeys, &b->last_subkey);
 347
 348         }
 349
 350         return rc;
 351 }
 352
 353 /**
 354  *      update_keys - Takes a list of public keys and updates them in the DB.
 355  *      @keys: The keys to update in the DB.
 356  *      @verbose: Should we output more information as we add keys?
 357  *
 358  *      Takes a list of keys and adds them to the database, merging them with
 359  *      the key in the database if it's already present there. The key list is
 360  *      update to contain the minimum set of updates required to get from what
 361  *      we had before to what we have now (ie the set of data that was added to
 362  *      the DB). Returns the number of entirely new keys added.
 363  */
 364 int update_keys(struct openpgp_publickey **keys, bool verbose)
 365 {
 366         struct openpgp_publickey *curkey = NULL;
 367         struct openpgp_publickey *oldkey = NULL;
 368         struct openpgp_publickey *prev = NULL;
 369         int newkeys = 0;
 370         bool intrans;
 371
 372         for (curkey = *keys; curkey != NULL; curkey = curkey->next) {
 373                 intrans = starttrans();
 374                 if (verbose) {
 375                         fprintf(stderr, "Fetching key 0x%llX, result: %d\n",
 376                                 get_keyid(curkey),
 377                                 fetch_key(get_keyid(curkey), &oldkey, intrans));
 378                 } else {
 379                         fetch_key(get_keyid(curkey), &oldkey, intrans);
 380                 }
 381
 382                 /*
 383                  * If we already have the key stored in the DB then merge it
 384                  * with the new one that's been supplied. Otherwise the key
 385                  * we've just got is the one that goes in the DB and also the
 386                  * one that we send out.
 387                  */
 388                 if (oldkey != NULL) {
 389                         merge_keys(oldkey, curkey);
 390                         if (curkey->revocations == NULL &&
 391                                         curkey->uids == NULL &&
 392                                         curkey->subkeys == NULL) {
 393                                 if (prev == NULL) {
 394                                         *keys = curkey->next;
 395                                 } else {
 396                                         prev->next = curkey->next;
 397                                         prev = curkey->next;
 398                                 }
 399                         } else {
 400                                 prev = curkey;
 401                                 if (verbose) {
 402                                         fprintf(stderr, "Merged key; storing updated key.\n");
 403                                 }
 404                                 store_key(oldkey, intrans, true);
 405                         }
 406                         free_publickey(oldkey);
 407                         oldkey = NULL;
 408                 } else {
 409                         if (verbose) {
 410                                 fprintf(stderr, "Storing completely new key.\n");
 411                         }
 412                         store_key(curkey, intrans, false);
 413                         newkeys++;
 414                 }
 415                 endtrans();
 416                 intrans = false;
 417         }
 418
 419         return newkeys;
 420 }