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