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