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