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