]> git.sommitrealweird.co.uk Git - onak.git/blob - merge.c
Switch debian build system to dh
[onak.git] / 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         uint64_t keya, keyb;
331
332         if (a == NULL || b == NULL) {
333                 /*
334                  * Do nothing.
335                  */
336                 return 1;
337         }
338
339         if (get_keyid(a, &keya) != ONAK_E_OK) {
340                 return 1;
341         } else if (get_keyid(b, &keyb) != ONAK_E_OK) {
342                 return 1;
343         } else if (keya != keyb) {
344                 /*
345                  * Key IDs are different.
346                  */
347                 rc = -1;
348         } else {
349                 /*
350                  * Key IDs are the same, so I guess we have to merge them.
351                  */
352                 curpacket = b->sigs;
353                 while (curpacket != NULL) {
354                         nextpacket = curpacket->next;
355                         if (find_packet(a->sigs, curpacket->packet)) {
356                                 /*
357                                  * We already have this signature, remove it
358                                  * from the difference list and free the memory
359                                  * allocated for it.
360                                  */
361
362                                 if (lastpacket != NULL) {
363                                         lastpacket->next = curpacket->next;
364                                 } else {
365                                         log_assert(curpacket == b->sigs);
366                                         b->sigs = curpacket->next;
367                                 }
368                                 curpacket->next = NULL;
369                                 free_packet_list(curpacket);
370
371                         } else {
372                                 lastpacket = curpacket;
373                         }
374                         curpacket = nextpacket;
375                 }
376                 b->last_sig = lastpacket;
377
378                 /*
379                  * Anything left on b->sigs doesn't exist on
380                  * a->sigs, so add them to the list.
381                  */
382                 packet_list_add(&a->sigs,
383                                 &a->last_sig,
384                                 b->sigs);
385
386                 /*
387                  * Merge uids (signed list).
388                  * Merge subkeys (signed list).
389                  */
390                 merge_signed_packets(&a->uids, &a->last_uid, 
391                                 &b->uids, &b->last_uid);
392                 merge_signed_packets(&a->subkeys, &a->last_subkey,
393                                 &b->subkeys, &b->last_subkey);
394
395         }
396
397         /*
398          * If either key was revoked, make sure both the new ones are marked as
399          * being so.
400          */
401         if (a->revoked || b->revoked) {
402                 a->revoked = b->revoked = true;
403         }
404
405         return rc;
406 }