merge.c

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