merge.c

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