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 bool 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         bool found = false;
 173
 174         for (cur = *packet_list; !found && (cur != NULL); cur = cur->next) {
 175                 if (compare_packets(cur->packet, packet) == 0) {
 176                         found = true;
 177                         if (prev == NULL) {
 178                                 *packet_list = cur->next;
 179                         } else {
 180                                 prev->next = cur->next;
 181                         }
 182                         if (cur->next == NULL) {
 183                                 *list_end = prev;
 184                         }
 185                         /*
 186                          * TODO: Free the removed signed packet...
 187                          */
 188                 }
 189                 prev = cur;
 190         }
 191
 192         return found;
 193 }
 194
 195 /**
 196  *      merge_packet_sigs - Takes 2 signed packets and merges their sigs.
 197  *      @old: The old signed packet.
 198  *      @new: The new signed packet.
 199  *
 200  *      Takes 2 signed packet list structures and the sigs of the packets on
 201  *      the head of these structures. These packets must both be the same and
 202  *      the fully merged structure is returned in old and the minimal
 203  *      difference to get from old to new in new.
 204  */
 205 int merge_packet_sigs(struct openpgp_signedpacket_list *old,
 206                         struct openpgp_signedpacket_list *new)
 207 {
 208         struct openpgp_packet_list      *lastpacket = NULL;
 209         struct openpgp_packet_list      *curpacket = NULL;
 210         struct openpgp_packet_list      *nextpacket = NULL;
 211
 212         assert(compare_packets(old->packet, new->packet) == 0);
 213
 214         curpacket = new->sigs;
 215         while (curpacket != NULL) {
 216                 nextpacket = curpacket->next;
 217                 /*
 218                  * TODO: We should be checking the signature and then
 219                  * potentially merging/replacing it depending on the subpackets
 220                  * really. For now this stops us adding the same one twice
 221                  * however.
 222                  */
 223                 if (find_signature(old->sigs, curpacket->packet)) {
 224                         /*
 225                          * We already have this sig, remove it from the
 226                          * difference list and free the memory allocated for
 227                          * it.
 228                          */
 229                         if (lastpacket != NULL) {
 230                                 lastpacket->next = curpacket->next;
 231                         } else {
 232                                 assert(curpacket == new->sigs);
 233                                 new->sigs = curpacket->next;
 234                         }
 235                         curpacket->next = NULL;
 236                         free_packet_list(curpacket);
 237                 } else {
 238                         lastpacket = curpacket;
 239                 }
 240                 curpacket = nextpacket;
 241         }
 242         new->last_sig = lastpacket;
 243
 244         /*
 245          * What's left on new->sigs now are the new signatures, so add them to
 246          * old->sigs.
 247          */
 248         packet_list_add(&old->sigs, &old->last_sig, new->sigs);
 249
 250         return 0;
 251 }
 252
 253 /**
 254  *      merge_signed_packets - Takes 2 lists of signed packets and merges them.
 255  *      @old: The old signed packet list.
 256  *      @new: The new signed packet list.
 257  *
 258  *      Takes 2 lists of signed packets and merges them. The complete list of
 259  *      signed packets & sigs is returned in old and the minimal set of
 260  *      differences required to get from old to new in new.
 261  */
 262 int merge_signed_packets(struct openpgp_signedpacket_list **old,
 263                         struct openpgp_signedpacket_list **old_end,
 264                         struct openpgp_signedpacket_list **new,
 265                         struct openpgp_signedpacket_list **new_end)
 266 {
 267         struct openpgp_signedpacket_list *curelem = NULL;
 268         struct openpgp_signedpacket_list *newelem = NULL;
 269
 270         for (curelem = *old; curelem != NULL; curelem = curelem->next) {
 271                 newelem = find_signed_packet(*new, curelem->packet);
 272                 if (newelem != NULL) {
 273                         merge_packet_sigs(curelem, newelem);
 274
 275                         /*
 276                          * If there are no sigs left on the new signed packet
 277                          * then remove it from the list.
 278                          */
 279                         if (newelem->sigs == NULL) {
 280                                 remove_signed_packet(new,
 281                                                 new_end,
 282                                                 newelem->packet);
 283                         }
 284                 }
 285         }
 286
 287         /*
 288          * If *new != NULL now then there might be UIDs on the new key that
 289          * weren't on the old key. Walk through them, checking if the UID is
 290          * on the old key and if not adding them to it.
 291          */
 292         for (curelem = *new; curelem != NULL;
 293                         curelem = curelem->next) {
 294
 295                 if (find_signed_packet(*old, curelem->packet) == NULL) {
 296                         ADD_PACKET_TO_LIST((*old_end),
 297                                 packet_dup(curelem->packet));
 298                         if (*old == NULL) {
 299                                 *old = *old_end;
 300                         }
 301                         packet_list_add(&(*old_end)->sigs,
 302                                 &(*old_end)->last_sig,
 303                                 curelem->sigs);
 304                 }
 305         }
 306
 307         return 0;
 308 }
 309
 310 /**
 311  *      merge_keys - Takes 2 public keys and merges them.
 312  *      @a: The old key. The merged key is returned in this structure.
 313  *      @b: The new key. The changed from old to new keys are returned in this
 314  *              structure.
 315  *
 316  *      This function takes 2 keys and merges them. It then returns the merged
 317  *      key in a and the difference between this new key and the original a
 318  *      in b (ie newb contains the minimum amount of detail necessary to
 319  *      convert olda to newa). The intention is that olda is provided from
 320  *      internal storage and oldb from the remote user. newa is then stored in
 321  *      internal storage and newb is sent to all our keysync peers.
 322  */
 323 int merge_keys(struct openpgp_publickey *a, struct openpgp_publickey *b)
 324 {
 325         int rc = 0; /* Return code */
 326         struct openpgp_packet_list      *curpacket = NULL;
 327         struct openpgp_packet_list      *lastpacket = NULL;
 328         struct openpgp_packet_list      *nextpacket = NULL;
 329         uint64_t keya, keyb;
 330
 331         if (a == NULL || b == NULL) {
 332                 /*
 333                  * Do nothing.
 334                  */
 335                 return 1;
 336         }
 337
 338         if (get_keyid(a, &keya) != ONAK_E_OK) {
 339                 return 1;
 340         } else if (get_keyid(b, &keyb) != ONAK_E_OK) {
 341                 return 1;
 342         } else if (keya != keyb) {
 343                 /*
 344                  * Key IDs are different.
 345                  */
 346                 rc = -1;
 347         } else {
 348                 /*
 349                  * Key IDs are the same, so I guess we have to merge them.
 350                  */
 351                 curpacket = b->sigs;
 352                 while (curpacket != NULL) {
 353                         nextpacket = curpacket->next;
 354                         if (find_packet(a->sigs, curpacket->packet)) {
 355                                 /*
 356                                  * We already have this signature, remove it
 357                                  * from the difference list and free the memory
 358                                  * allocated for it.
 359                                  */
 360
 361                                 if (lastpacket != NULL) {
 362                                         lastpacket->next = curpacket->next;
 363                                 } else {
 364                                         assert(curpacket == b->sigs);
 365                                         b->sigs = curpacket->next;
 366                                 }
 367                                 curpacket->next = NULL;
 368                                 free_packet_list(curpacket);
 369
 370                         } else {
 371                                 lastpacket = curpacket;
 372                         }
 373                         curpacket = nextpacket;
 374                 }
 375                 b->last_sig = lastpacket;
 376
 377                 /*
 378                  * Anything left on b->sigs doesn't exist on
 379                  * a->sigs, so add them to the list.
 380                  */
 381                 packet_list_add(&a->sigs,
 382                                 &a->last_sig,
 383                                 b->sigs);
 384
 385                 /*
 386                  * Merge uids (signed list).
 387                  * Merge subkeys (signed list).
 388                  */
 389                 merge_signed_packets(&a->uids, &a->last_uid,
 390                                 &b->uids, &b->last_uid);
 391                 merge_signed_packets(&a->subkeys, &a->last_subkey,
 392                                 &b->subkeys, &b->last_subkey);
 393
 394         }
 395
 396         /*
 397          * If either key was revoked, make sure both the new ones are marked as
 398          * being so.
 399          */
 400         if (a->revoked || b->revoked) {
 401                 a->revoked = b->revoked = true;
 402         }
 403
 404         return rc;
 405 }