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