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