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