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
  13 #include "keyid.h"
  14 #include "keystructs.h"
  15 #include "ll.h"
  16 #include "mem.h"
  17 #include "merge.h"
  18
  19 /**
  20  *      compare_packets - Check to see if 2 OpenPGP packets are the same.
  21  *      @a: The first key to compare.
  22  *      @b: The second key to compare.
  23  *
  24  *      Takes 2 keys and returns true if they are the same and false otherwise.
  25  */
  26 bool compare_packets(struct openpgp_packet *a, struct openpgp_packet *b)
  27 {
  28         return (a->tag == b->tag && a->length == b->length &&
  29                 !memcmp(a->data, b->data, b->length));
  30 }
  31
  32 /**
  33  *      find_packet - Checks to see if an OpenPGP packet exists in a list.
  34  *      @packet_list: The list of packets to look in.
  35  *      @packet: The packet to look for.
  36  *
  37  *      Walks through the packet_list checking to see if the packet given is
  38  *      present in it. Returns true if it is.
  39  */
  40 bool find_packet(struct openpgp_packet_list *packet_list,
  41                         struct openpgp_packet *packet)
  42 {
  43         bool found = false;
  44
  45         while (!found && packet_list != NULL) {
  46                 if (compare_packets(packet_list->packet, packet)) {
  47                         found = true;
  48                 }
  49                 packet_list = packet_list -> next;
  50         }
  51
  52         return found;
  53 }
  54
  55 /**
  56  *      get_signed_packet - Gets a signed packet from a list.
  57  *      @packet_list: The list of packets to look in.
  58  *      @packet: The packet to look for.
  59  *
  60  *      Walks through the signedpacket_list looking for the supplied packet and
  61  *      returns it if found. Otherwise returns NULL.
  62  */
  63 struct openpgp_signedpacket_list *find_signed_packet(
  64                 struct openpgp_signedpacket_list *packet_list,
  65                 struct openpgp_packet *packet)
  66 {
  67         struct openpgp_signedpacket_list *found = NULL;
  68
  69         while (found == NULL && packet_list != NULL) {
  70                 if (compare_packets(packet_list->packet, packet)) {
  71                         found = packet_list;
  72                 }
  73                 packet_list = packet_list -> next;
  74         }
  75
  76         return found;
  77 }
  78
  79 /**
  80  *      remove_signed_packet - Removes a signed packet from a list.
  81  *      @packet_list: The list of packets to look in.
  82  *      @packet: The packet to remove.
  83  *
  84  *      Walks through the signedpacket_list looking for the supplied packet and
  85  *      removes it if found. Assumes the packet can only exist a maximum of
  86  *      once in the list.
  87  */
  88 bool remove_signed_packet(struct openpgp_signedpacket_list **packet_list,
  89                 struct openpgp_signedpacket_list **list_end,
  90                 struct openpgp_packet *packet)
  91 {
  92         struct openpgp_signedpacket_list *cur = NULL;
  93         struct openpgp_signedpacket_list *prev = NULL;
  94         bool found = false;
  95
  96         for (cur = *packet_list; !found && (cur != NULL); cur = cur->next) {
  97                 if (compare_packets(cur->packet, packet)) {
  98                         found = true;
  99                         if (prev == NULL) {
 100                                 *packet_list = cur->next;
 101                         } else {
 102                                 prev->next = cur->next;
 103                         }
 104                         if (cur->next == NULL) {
 105                                 *list_end = prev;
 106                         }
 107                 }
 108         }
 109
 110         return found;
 111 }
 112
 113 /**
 114  *      merge_packet_sigs - Takes 2 signed packets and merges their sigs.
 115  *      @old: The old signed packet.
 116  *      @new: The new signed packet.
 117  *
 118  *      Takes 2 signed packet list structures and the sigs of the packets on
 119  *      the head of these structures. These packets must both be the same and
 120  *      the fully merged structure is returned in old and the minimal
 121  *      difference to get from old to new in new.
 122  */
 123 int merge_packet_sigs(struct openpgp_signedpacket_list *old,
 124                         struct openpgp_signedpacket_list *new)
 125 {
 126         struct openpgp_packet_list      *lastpacket = NULL;
 127         struct openpgp_packet_list      *curpacket = NULL;
 128         struct openpgp_packet_list      *nextpacket = NULL;
 129
 130         assert(compare_packets(old->packet, new->packet));
 131
 132         curpacket = new->sigs;
 133         while (curpacket != NULL) {
 134                 nextpacket = curpacket->next;
 135                 if (find_packet(old->sigs, curpacket->packet)) {
 136                         /*
 137                          * We already have this sig, remove it from the
 138                          * difference list and free the memory allocated for
 139                          * it.
 140                          */
 141                         if (lastpacket != NULL) {
 142                                 lastpacket->next = curpacket->next;
 143                         } else {
 144                                 assert(curpacket == new->sigs);
 145                                 new->sigs = curpacket->next;
 146                         }
 147                         curpacket->next = NULL;
 148                         free_packet_list(curpacket);
 149                 } else {
 150                         lastpacket = curpacket;
 151                 }
 152                 curpacket = nextpacket;
 153         }
 154         new->last_sig = lastpacket;
 155
 156         /*
 157          * What's left on new->sigs now are the new signatures, so add them to
 158          * old->sigs.
 159          */
 160         packet_list_add(&old->sigs, &old->last_sig, new->sigs);
 161
 162         return 0;
 163 }
 164
 165 /**
 166  *      merge_signed_packets - Takes 2 lists of signed packets and merges them.
 167  *      @old: The old signed packet list.
 168  *      @new: The new signed packet list.
 169  *
 170  *      Takes 2 lists of signed packets and merges them. The complete list of
 171  *      signed packets & sigs is returned in old and the minimal set of
 172  *      differences required to get from old to new in new.
 173  */
 174 int merge_signed_packets(struct openpgp_signedpacket_list **old,
 175                         struct openpgp_signedpacket_list **old_end,
 176                         struct openpgp_signedpacket_list **new,
 177                         struct openpgp_signedpacket_list **new_end)
 178 {
 179         struct openpgp_signedpacket_list *curelem = NULL;
 180         struct openpgp_signedpacket_list *newelem = NULL;
 181
 182         for (curelem = *old; curelem != NULL; curelem = curelem->next) {
 183                 newelem = find_signed_packet(*new, curelem->packet);
 184                 if (newelem != NULL) {
 185                         merge_packet_sigs(curelem, newelem);
 186
 187                         /*
 188                          * If there are no sigs left on the new signed packet
 189                          * then remove it from the list.
 190                          */
 191                         if (newelem->sigs == NULL) {
 192                                 remove_signed_packet(new,
 193                                                 new_end,
 194                                                 curelem->packet);
 195                         }
 196                 }
 197         }
 198
 199         /*
 200          * If *new != NULL now then there are UIDs on the new key that weren't
 201          * on the old key. Add them.
 202          */
 203         for (curelem = *new; curelem != NULL;
 204                         curelem = curelem->next) {
 205                 ADD_PACKET_TO_LIST((*old_end),
 206                                 packet_dup(curelem->packet));
 207                 if (*old == NULL) {
 208                         *old = *old_end;
 209                 }
 210                 packet_list_add(&(*old_end)->sigs,
 211                                 &(*old_end)->last_sig,
 212                                 curelem->sigs);
 213         }
 214
 215         return 0;
 216 }
 217
 218 /**
 219  *      merge_keys - Takes 2 public keys and merges them.
 220  *      @a: The old key. The merged key is returned in this structure.
 221  *      @b: The new key. The changed from old to new keys are returned in this
 222  *              structure.
 223  *
 224  *      This function takes 2 keys and merges them. It then returns the merged
 225  *      key in a and the difference between this new key and the original a
 226  *      in b (ie newb contains the minimum amount of detail necessary to
 227  *      convert olda to newa). The intention is that olda is provided from
 228  *      internal storage and oldb from the remote user. newa is then stored in
 229  *      internal storage and newb is sent to all our keysync peers.
 230  */
 231 int merge_keys(struct openpgp_publickey *a, struct openpgp_publickey *b)
 232 {
 233         int rc = 0; /* Return code */
 234         struct openpgp_packet_list      *curpacket = NULL;
 235         struct openpgp_packet_list      *lastpacket = NULL;
 236         struct openpgp_packet_list      *nextpacket = NULL;
 237
 238         if (a == NULL || b == NULL) {
 239                 /*
 240                  * Do nothing.
 241                  */
 242                 rc = 1;
 243         } else if (get_keyid(a) != get_keyid(b)) {
 244                 /*
 245                  * Key IDs are different.
 246                  */
 247                 rc = -1;
 248         } else {
 249                 /*
 250                  * Key IDs are the same, so I guess we have to merge them.
 251                  */
 252                 curpacket = b->revocations;
 253                 while (curpacket != NULL) {
 254                         nextpacket = curpacket->next;
 255                         if (find_packet(a->revocations, curpacket->packet)) {
 256                                 /*
 257                                  * We already have this revocation, remove it
 258                                  * from the difference list and free the memory
 259                                  * allocated for it.
 260                                  */
 261
 262                                 if (lastpacket != NULL) {
 263                                         lastpacket->next = curpacket->next;
 264                                 } else {
 265                                         assert(curpacket == b->revocations);
 266                                         b->revocations = curpacket->next;
 267                                 }
 268                                 curpacket->next = NULL;
 269                                 free_packet_list(curpacket);
 270
 271                         } else {
 272                                 lastpacket = curpacket;
 273                         }
 274                         curpacket = nextpacket;
 275                 }
 276                 b->last_revocation = lastpacket;
 277
 278                 /*
 279                  * Anything left on b->revocations doesn't exist on
 280                  * a->revocations, so add them to the list.
 281                  */
 282                 packet_list_add(&a->revocations,
 283                                 &a->last_revocation,
 284                                 b->revocations);
 285
 286                 /*
 287                  * Merge uids (signed list).
 288                  * Merge subkeys (signed list).
 289                  */
 290                 merge_signed_packets(&a->uids, &a->last_uid,
 291                                 &b->uids, &b->last_uid);
 292                 merge_signed_packets(&a->subkeys, &a->last_uid,
 293                                 &b->subkeys, &b->last_subkey);
 294
 295         }
 296
 297         return rc;
 298 }