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