1 /* $OpenBSD: math_group.c,v 1.27 2005/04/08 22:32:10 cloder Exp $ */
2 /* $EOM: math_group.c,v 1.25 2000/04/07 19:53:26 niklas Exp $ */
3
4 /*
5 * Copyright (c) 1998 Niels Provos. All rights reserved.
6 * Copyright (c) 1999, 2000 Niklas Hallqvist. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /*
30 * This code was written under funding by Ericsson Radio Systems.
31 */
32
33 #include <sys/param.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "log.h"
38 #include "math_2n.h"
39 #include "math_ec2n.h"
40 #include "math_group.h"
41 #include "math_mp.h"
42 #include "util.h"
43
44 /* We do not want to export these definitions. */
45 int modp_getlen(struct group *);
46 void modp_getraw(struct group *, math_mp_t, u_int8_t *);
47 int modp_setraw(struct group *, math_mp_t, u_int8_t *, int);
48 int modp_setrandom(struct group *, math_mp_t);
49 int modp_operation(struct group *, math_mp_t, math_mp_t, math_mp_t);
50
51 int ec2n_getlen(struct group *);
52 void ec2n_getraw(struct group *, ec2np_ptr, u_int8_t *);
53 int ec2n_setraw(struct group *, ec2np_ptr, u_int8_t *, int);
54 int ec2n_setrandom(struct group *, ec2np_ptr);
55 int ec2n_operation(struct group *, ec2np_ptr, ec2np_ptr, ec2np_ptr);
56
57 struct ec2n_group {
58 ec2np_t gen; /* Generator */
59 ec2ng_t grp;
60 ec2np_t a, b, c, d;
61 };
62
63 struct modp_group {
64 math_mp_t gen; /* Generator */
65 math_mp_t p; /* Prime */
66 math_mp_t a, b, c, d;
67 };
68
69 /*
70 * This module provides access to the operations on the specified group
71 * and is absolutly free of any cryptographic devices. This is math :-).
72 */
73
74 #define OAKLEY_GRP_1 1
75 #define OAKLEY_GRP_2 2
76 #define OAKLEY_GRP_3 3
77 #define OAKLEY_GRP_4 4
78 #define OAKLEY_GRP_5 5
79 #define OAKLEY_GRP_6 6
80 #define OAKLEY_GRP_7 7
81 #define OAKLEY_GRP_8 8
82 #define OAKLEY_GRP_9 9
83 #define OAKLEY_GRP_10 10
84 #define OAKLEY_GRP_11 11
85 #define OAKLEY_GRP_12 12
86 #define OAKLEY_GRP_13 13
87 #define OAKLEY_GRP_14 14
88 #define OAKLEY_GRP_15 15
89 #define OAKLEY_GRP_16 16
90 #define OAKLEY_GRP_17 17
91 #define OAKLEY_GRP_18 18
92
93 /* Describe preconfigured MODP groups */
94
95 /*
96 * The Generalized Number Field Sieve has an asymptotic running time
97 * of: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))), where q is the
98 * group order, e.g. q = 2**768.
99 */
100
101 struct modp_dscr oakley_modp[] =
102 {
103 {OAKLEY_GRP_1, 72, /* This group is insecure, only sufficient
104 * for DES */
105 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
106 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
107 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
108 "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
109 "0x02"
110 },
111 {OAKLEY_GRP_2, 82, /* This group is a bit better */
112 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
113 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
114 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
115 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
116 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
117 "FFFFFFFFFFFFFFFF",
118 "0x02"
119 },
120 {OAKLEY_GRP_5, 102,
121 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
122 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
123 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
124 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
125 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
126 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
127 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
128 "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
129 "0x02"
130 },
131 {OAKLEY_GRP_14, 135, /* 2048 bit */
132 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
133 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
134 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
135 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
136 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
137 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
138 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
139 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
140 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
141 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
142 "15728E5A8AACAA68FFFFFFFFFFFFFFFF",
143 "0x02"
144 },
145 {OAKLEY_GRP_15, 170, /* 3072 bit */
146 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
147 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
148 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
149 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
150 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
151 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
152 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
153 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
154 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
155 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
156 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
157 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
158 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
159 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
160 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
161 "43DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF",
162 "0x02"
163 },
164 {OAKLEY_GRP_16, 195, /* 4096 bit */
165 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
166 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
167 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
168 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
169 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
170 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
171 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
172 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
173 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
174 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
175 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
176 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
177 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
178 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
179 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
180 "43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7"
181 "88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA"
182 "2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6"
183 "287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED"
184 "1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9"
185 "93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199"
186 "FFFFFFFFFFFFFFFF",
187 "0x02"
188 },
189 {OAKLEY_GRP_17, 220, /* 6144 bit */
190 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
191 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
192 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
193 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
194 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
195 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
196 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
197 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
198 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
199 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
200 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
201 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
202 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
203 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
204 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
205 "43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7"
206 "88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA"
207 "2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6"
208 "287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED"
209 "1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9"
210 "93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934028492"
211 "36C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BD"
212 "F8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831"
213 "179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1B"
214 "DB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF"
215 "5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6"
216 "D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F3"
217 "23A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AA"
218 "CC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE328"
219 "06A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55C"
220 "DA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE"
221 "12BF2D5B0B7474D6E694F91E6DCC4024FFFFFFFFFFFFFFFF",
222 "0x02"
223 },
224 {OAKLEY_GRP_18, 250, /* 8192 bit */
225 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
226 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
227 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
228 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
229 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
230 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
231 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
232 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
233 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
234 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
235 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
236 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
237 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
238 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
239 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
240 "43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7"
241 "88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA"
242 "2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6"
243 "287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED"
244 "1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9"
245 "93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934028492"
246 "36C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BD"
247 "F8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831"
248 "179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1B"
249 "DB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF"
250 "5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6"
251 "D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F3"
252 "23A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AA"
253 "CC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE328"
254 "06A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55C"
255 "DA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE"
256 "12BF2D5B0B7474D6E694F91E6DBE115974A3926F12FEE5E4"
257 "38777CB6A932DF8CD8BEC4D073B931BA3BC832B68D9DD300"
258 "741FA7BF8AFC47ED2576F6936BA424663AAB639C5AE4F568"
259 "3423B4742BF1C978238F16CBE39D652DE3FDB8BEFC848AD9"
260 "22222E04A4037C0713EB57A81A23F0C73473FC646CEA306B"
261 "4BCBC8862F8385DDFA9D4B7FA2C087E879683303ED5BDD3A"
262 "062B3CF5B3A278A66D2A13F83F44F82DDF310EE074AB6A36"
263 "4597E899A0255DC164F31CC50846851DF9AB48195DED7EA1"
264 "B1D510BD7EE74D73FAF36BC31ECFA268359046F4EB879F92"
265 "4009438B481C6CD7889A002ED5EE382BC9190DA6FC026E47"
266 "9558E4475677E9AA9E3050E2765694DFC81F56E880B96E71"
267 "60C980DD98EDD3DFFFFFFFFFFFFFFFFF",
268 "0x02"
269 },
270 };
271
272 /* Describe preconfigured EC2N groups */
273
274 /*
275 * Related collision-search methods can compute discrete logarithmns
276 * in O(sqrt(r)), r being the subgroup order.
277 */
278
279 struct ec2n_dscr oakley_ec2n[] = {
280 { OAKLEY_GRP_3, 76, /* This group is also considered insecure
281 * (P1363) */
282 "0x0800000000000000000000004000000000000001",
283 "0x7b",
284 "0x00",
285 "0x7338f" },
286 { OAKLEY_GRP_4, 91,
287 "0x020000000000000000000000000000200000000000000001",
288 "0x18",
289 "0x00",
290 "0x1ee9" },
291 };
292
293 /* XXX I want to get rid of the casting here. */
294 struct group groups[] = {
295 {
296 MODP, OAKLEY_GRP_1, 0, &oakley_modp[0], 0, 0, 0, 0, 0,
297 (int (*) (struct group *)) modp_getlen,
298 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
299 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
300 (int (*) (struct group *, void *)) modp_setrandom,
301 (int (*) (struct group *, void *, void *, void *)) modp_operation
302 },
303 {
304 MODP, OAKLEY_GRP_2, 0, &oakley_modp[1], 0, 0, 0, 0, 0,
305 (int (*) (struct group *)) modp_getlen,
306 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
307 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
308 (int (*) (struct group *, void *)) modp_setrandom,
309 (int (*) (struct group *, void *, void *, void *)) modp_operation
310 },
311 {
312 EC2N, OAKLEY_GRP_3, 0, &oakley_ec2n[0], 0, 0, 0, 0, 0,
313 (int (*) (struct group *)) ec2n_getlen,
314 (void (*) (struct group *, void *, u_int8_t *)) ec2n_getraw,
315 (int (*) (struct group *, void *, u_int8_t *, int)) ec2n_setraw,
316 (int (*) (struct group *, void *)) ec2n_setrandom,
317 (int (*) (struct group *, void *, void *, void *)) ec2n_operation
318 },
319 {
320 EC2N, OAKLEY_GRP_4, 0, &oakley_ec2n[1], 0, 0, 0, 0, 0,
321 (int (*) (struct group *)) ec2n_getlen,
322 (void (*) (struct group *, void *, u_int8_t *)) ec2n_getraw,
323 (int (*) (struct group *, void *, u_int8_t *, int)) ec2n_setraw,
324 (int (*) (struct group *, void *)) ec2n_setrandom,
325 (int (*) (struct group *, void *, void *, void *)) ec2n_operation
326 },
327 {
328 MODP, OAKLEY_GRP_5, 0, &oakley_modp[2], 0, 0, 0, 0, 0,
329 (int (*) (struct group *)) modp_getlen,
330 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
331 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
332 (int (*) (struct group *, void *)) modp_setrandom,
333 (int (*) (struct group *, void *, void *, void *)) modp_operation
334 },
335 /* XXX Higher EC2N group go here... */
336 /* XXX group 6 to 13 are not yet defined (draft-ike-ecc) */
337 {
338 NOTYET, OAKLEY_GRP_6, 0, NULL, 0, 0, 0, 0, 0,
339 NULL, NULL, NULL, NULL, NULL
340 },
341 {
342 NOTYET, OAKLEY_GRP_7, 0, NULL, 0, 0, 0, 0, 0,
343 NULL, NULL, NULL, NULL, NULL
344 },
345 {
346 NOTYET, OAKLEY_GRP_8, 0, NULL, 0, 0, 0, 0, 0,
347 NULL, NULL, NULL, NULL, NULL
348 },
349 {
350 NOTYET, OAKLEY_GRP_9, 0, NULL, 0, 0, 0, 0, 0,
351 NULL, NULL, NULL, NULL, NULL
352 },
353 {
354 NOTYET, OAKLEY_GRP_10, 0, NULL, 0, 0, 0, 0, 0,
355 NULL, NULL, NULL, NULL, NULL
356 },
357 {
358 NOTYET, OAKLEY_GRP_11, 0, NULL, 0, 0, 0, 0, 0,
359 NULL, NULL, NULL, NULL, NULL
360 },
361 {
362 NOTYET, OAKLEY_GRP_12, 0, NULL, 0, 0, 0, 0, 0,
363 NULL, NULL, NULL, NULL, NULL
364 },
365 {
366 NOTYET, OAKLEY_GRP_13, 0, NULL, 0, 0, 0, 0, 0,
367 NULL, NULL, NULL, NULL, NULL
368 },
369 {
370 MODP, OAKLEY_GRP_14, 0, &oakley_modp[3], 0, 0, 0, 0, 0,
371 (int (*) (struct group *)) modp_getlen,
372 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
373 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
374 (int (*) (struct group *, void *)) modp_setrandom,
375 (int (*) (struct group *, void *, void *, void *)) modp_operation
376 },
377 {
378 MODP, OAKLEY_GRP_15, 0, &oakley_modp[4], 0, 0, 0, 0, 0,
379 (int (*) (struct group *)) modp_getlen,
380 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
381 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
382 (int (*) (struct group *, void *)) modp_setrandom,
383 (int (*) (struct group *, void *, void *, void *)) modp_operation
384 },
385 {
386 MODP, OAKLEY_GRP_16, 0, &oakley_modp[5], 0, 0, 0, 0, 0,
387 (int (*) (struct group *)) modp_getlen,
388 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
389 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
390 (int (*) (struct group *, void *)) modp_setrandom,
391 (int (*) (struct group *, void *, void *, void *)) modp_operation
392 },
393 {
394 MODP, OAKLEY_GRP_17, 0, &oakley_modp[6], 0, 0, 0, 0, 0,
395 (int (*) (struct group *)) modp_getlen,
396 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
397 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
398 (int (*) (struct group *, void *)) modp_setrandom,
399 (int (*) (struct group *, void *, void *, void *)) modp_operation
400 },
401 {
402 MODP, OAKLEY_GRP_18, 0, &oakley_modp[7], 0, 0, 0, 0, 0,
403 (int (*) (struct group *)) modp_getlen,
404 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
405 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
406 (int (*) (struct group *, void *)) modp_setrandom,
407 (int (*) (struct group *, void *, void *, void *)) modp_operation
408 },
409 };
410
411 /*
412 * Initialize the group structure for later use,
413 * this is done by converting the values given in the describtion
414 * and converting them to their native representation.
415 */
416 void
group_init(void)417 group_init(void)
418 {
419 int i;
420
421 for (i = sizeof(groups) / sizeof(groups[0]) - 1; i >= 0; i--)
422 switch (groups[i].type) {
423 case EC2N: /* Initialize an Elliptic Curve over GF(2**n) */
424 ec2n_init(&groups[i]);
425 break;
426
427 case MODP: /* Initialize an over GF(p) */
428 modp_init(&groups[i]);
429 break;
430
431 case NOTYET: /* Not yet assigned, drop silently */
432 break;
433
434 default:
435 log_print("Unknown group type %d at index %d in "
436 "group_init().", groups[i].type, i);
437 break;
438 }
439 }
440
441 struct group *
group_get(u_int32_t id)442 group_get(u_int32_t id)
443 {
444 struct group *new, *clone;
445
446 if (id < 1 || id > (sizeof(groups) / sizeof(groups[0]))) {
447 log_print("group_get: group ID (%u) out of range", id);
448 return 0;
449 }
450 clone = &groups[id - 1];
451
452 new = malloc(sizeof *new);
453 if (!new) {
454 log_error("group_get: malloc (%lu) failed",
455 (unsigned long)sizeof *new);
456 return 0;
457 }
458 switch (clone->type) {
459 case EC2N:
460 new = ec2n_clone(new, clone);
461 break;
462 case MODP:
463 new = modp_clone(new, clone);
464 break;
465 default:
466 log_print("group_get: unknown group type %d", clone->type);
467 free(new);
468 return 0;
469 }
470 LOG_DBG((LOG_MISC, 70, "group_get: returning %p of group %d", new,
471 new->id));
472 return new;
473 }
474
475 void
group_free(struct group * grp)476 group_free(struct group *grp)
477 {
478 switch (grp->type) {
479 case EC2N:
480 ec2n_free(grp);
481 break;
482 case MODP:
483 modp_free(grp);
484 break;
485 default:
486 log_print("group_free: unknown group type %d", grp->type);
487 break;
488 }
489 free(grp);
490 }
491
492 struct group *
modp_clone(struct group * new,struct group * clone)493 modp_clone(struct group *new, struct group *clone)
494 {
495 struct modp_group *new_grp, *clone_grp = clone->group;
496
497 new_grp = malloc(sizeof *new_grp);
498 if (!new_grp) {
499 log_print("modp_clone: malloc (%lu) failed",
500 (unsigned long)sizeof *new_grp);
501 free(new);
502 return 0;
503 }
504 memcpy(new, clone, sizeof(struct group));
505
506 new->group = new_grp;
507 new_grp->p = BN_dup(clone_grp->p);
508 new_grp->gen = BN_dup(clone_grp->gen);
509
510 new_grp->a = BN_new();
511 new_grp->b = BN_new();
512 new_grp->c = BN_new();
513
514 new->gen = new_grp->gen;
515 new->a = new_grp->a;
516 new->b = new_grp->b;
517 new->c = new_grp->c;
518
519 return new;
520 }
521
522 void
modp_free(struct group * old)523 modp_free(struct group *old)
524 {
525 struct modp_group *grp = old->group;
526
527 BN_clear_free(grp->p);
528 BN_clear_free(grp->gen);
529 BN_clear_free(grp->a);
530 BN_clear_free(grp->b);
531 BN_clear_free(grp->c);
532
533 free(grp);
534 }
535
536 void
modp_init(struct group * group)537 modp_init(struct group *group)
538 {
539 struct modp_dscr *dscr = (struct modp_dscr *)group->group;
540 struct modp_group *grp;
541
542 grp = malloc(sizeof *grp);
543 if (!grp)
544 log_fatal("modp_init: malloc (%lu) failed",
545 (unsigned long)sizeof *grp);
546
547 group->bits = dscr->bits;
548
549 grp->p = BN_new();
550 BN_hex2bn(&grp->p, dscr->prime + 2);
551 grp->gen = BN_new();
552 BN_hex2bn(&grp->gen, dscr->gen + 2);
553
554 grp->a = BN_new();
555 grp->b = BN_new();
556 grp->c = BN_new();
557
558 group->gen = grp->gen;
559 group->a = grp->a;
560 group->b = grp->b;
561 group->c = grp->c;
562
563 group->group = grp;
564 }
565
566 struct group *
ec2n_clone(struct group * new,struct group * clone)567 ec2n_clone(struct group *new, struct group *clone)
568 {
569 struct ec2n_group *new_grp, *clone_grp = clone->group;
570
571 new_grp = malloc(sizeof *new_grp);
572 if (!new_grp) {
573 log_error("ec2n_clone: malloc (%lu) failed",
574 (unsigned long)sizeof *new_grp);
575 free(new);
576 return 0;
577 }
578 memcpy(new, clone, sizeof(struct group));
579
580 new->group = new_grp;
581 ec2ng_init(new_grp->grp);
582 ec2np_init(new_grp->gen);
583 ec2np_init(new_grp->a);
584 ec2np_init(new_grp->b);
585 ec2np_init(new_grp->c);
586
587 if (ec2ng_set(new_grp->grp, clone_grp->grp))
588 goto fail;
589 if (ec2np_set(new_grp->gen, clone_grp->gen))
590 goto fail;
591
592 new->gen = new_grp->gen;
593 new->a = new_grp->a;
594 new->b = new_grp->b;
595 new->c = new_grp->c;
596 new->d = ((ec2np_ptr) new->a)->x;
597
598 return new;
599
600 fail:
601 ec2ng_clear(new_grp->grp);
602 ec2np_clear(new_grp->gen);
603 ec2np_clear(new_grp->a);
604 ec2np_clear(new_grp->b);
605 ec2np_clear(new_grp->c);
606 free(new_grp);
607 free(new);
608 return 0;
609 }
610
611 void
ec2n_free(struct group * old)612 ec2n_free(struct group *old)
613 {
614 struct ec2n_group *grp = old->group;
615
616 ec2ng_clear(grp->grp);
617 ec2np_clear(grp->gen);
618 ec2np_clear(grp->a);
619 ec2np_clear(grp->b);
620 ec2np_clear(grp->c);
621
622 free(grp);
623 }
624
625 void
ec2n_init(struct group * group)626 ec2n_init(struct group *group)
627 {
628 struct ec2n_dscr *dscr = (struct ec2n_dscr *)group->group;
629 struct ec2n_group *grp;
630
631 grp = malloc(sizeof *grp);
632 if (!grp)
633 log_fatal("ec2n_init: malloc (%lu) failed",
634 (unsigned long)sizeof *grp);
635
636 group->bits = dscr->bits;
637
638 ec2ng_init(grp->grp);
639 ec2np_init(grp->gen);
640 ec2np_init(grp->a);
641 ec2np_init(grp->b);
642 ec2np_init(grp->c);
643
644 if (ec2ng_set_p_str(grp->grp, dscr->polynomial))
645 goto fail;
646 grp->grp->p->bits = b2n_sigbit(grp->grp->p);
647 if (ec2ng_set_a_str(grp->grp, dscr->a))
648 goto fail;
649 if (ec2ng_set_b_str(grp->grp, dscr->b))
650 goto fail;
651
652 if (ec2np_set_x_str(grp->gen, dscr->gen_x))
653 goto fail;
654 if (ec2np_find_y(grp->gen, grp->grp))
655 goto fail;
656
657 /* Sanity check */
658 if (!ec2np_ison(grp->gen, grp->grp))
659 log_fatal("ec2n_init: generator is not on curve");
660
661 group->gen = grp->gen;
662 group->a = grp->a;
663 group->b = grp->b;
664 group->c = grp->c;
665 group->d = ((ec2np_ptr) group->a)->x;
666
667 group->group = grp;
668 return;
669
670 fail:
671 log_fatal("ec2n_init: general failure");
672 }
673
674 int
modp_getlen(struct group * group)675 modp_getlen(struct group *group)
676 {
677 struct modp_group *grp = (struct modp_group *)group->group;
678
679 return BN_num_bytes(grp->p);
680 }
681
682 void
modp_getraw(struct group * grp,math_mp_t v,u_int8_t * d)683 modp_getraw(struct group *grp, math_mp_t v, u_int8_t *d)
684 {
685 math_mp_t a;
686 int len;
687
688 len = grp->getlen(grp);
689
690 /* XXX bn2bin? */
691 a = BN_dup(v);
692
693 while (len-- > 0)
694 d[len] = BN_div_word(a, 256);
695
696 BN_clear_free(a);
697 }
698
699 int
modp_setraw(struct group * grp,math_mp_t d,u_int8_t * s,int l)700 modp_setraw(struct group *grp, math_mp_t d, u_int8_t *s, int l)
701 {
702 u_int32_t i;
703
704 /* XXX bin2bn? */
705 BN_set_word(d, 0);
706 for (i = 0; i < l; i++) {
707 BN_mul_word(d, 256);
708 BN_add_word(d, s[i]);
709 }
710 return 0;
711 }
712
713 int
modp_setrandom(struct group * grp,math_mp_t d)714 modp_setrandom(struct group *grp, math_mp_t d)
715 {
716 int i, l = grp->getlen(grp);
717 u_int32_t tmp = 0;
718
719 BN_set_word(d, 0);
720
721 for (i = 0; i < l; i++) {
722 if (i % 4)
723 tmp = rand_32();
724
725 BN_lshift(d, d, 8);
726 BN_add_word(d, tmp & 0xFF);
727 tmp >>= 8;
728 }
729 return 0;
730 }
731
732 int
modp_operation(struct group * group,math_mp_t d,math_mp_t a,math_mp_t e)733 modp_operation(struct group *group, math_mp_t d, math_mp_t a, math_mp_t e)
734 {
735 struct modp_group *grp = (struct modp_group *)group->group;
736
737 BN_CTX *ctx = BN_CTX_new();
738 BN_mod_exp(d, a, e, grp->p, ctx);
739 BN_CTX_free(ctx);
740 return 0;
741 }
742
743 int
ec2n_getlen(struct group * group)744 ec2n_getlen(struct group *group)
745 {
746 struct ec2n_group *grp = (struct ec2n_group *)group->group;
747 int bits = b2n_sigbit(grp->grp->p) - 1;
748
749 return (7 + bits) >> 3;
750 }
751
752 void
ec2n_getraw(struct group * group,ec2np_ptr xo,u_int8_t * e)753 ec2n_getraw(struct group *group, ec2np_ptr xo, u_int8_t *e)
754 {
755 struct ec2n_group *grp = (struct ec2n_group *) group->group;
756 int chunks, bytes, i, j;
757 b2n_ptr x = xo->x;
758 CHUNK_TYPE tmp;
759
760 bytes = b2n_sigbit(grp->grp->p) - 1;
761 chunks = (CHUNK_MASK + bytes) >> CHUNK_SHIFTS;
762 bytes = ((7 + (bytes & CHUNK_MASK)) >> 3);
763
764 for (i = chunks - 1; i >= 0; i--) {
765 tmp = (i >= x->chunks ? 0 : x->limp[i]);
766 for (j = (i == chunks - 1 ? bytes : CHUNK_BYTES) - 1; j >= 0;
767 j--) {
768 e[j] = tmp & 0xff;
769 tmp >>= 8;
770 }
771 e += (i == chunks - 1 ? bytes : CHUNK_BYTES);
772 }
773 }
774
775 int
ec2n_setraw(struct group * grp,ec2np_ptr out,u_int8_t * s,int l)776 ec2n_setraw(struct group *grp, ec2np_ptr out, u_int8_t *s, int l)
777 {
778 int len, bytes, i, j;
779 b2n_ptr outx = out->x;
780 CHUNK_TYPE tmp;
781
782 len = (CHUNK_BYTES - 1 + l) / CHUNK_BYTES;
783 if (b2n_resize(outx, len))
784 return -1;
785
786 bytes = ((l - 1) % CHUNK_BYTES) + 1;
787
788 for (i = len - 1; i >= 0; i--) {
789 tmp = 0;
790 for (j = (i == len - 1 ? bytes : CHUNK_BYTES); j > 0; j--) {
791 tmp <<= 8;
792 tmp |= *s++;
793 }
794 outx->limp[i] = tmp;
795 }
796 return 0;
797 }
798
799 int
ec2n_setrandom(struct group * group,ec2np_ptr x)800 ec2n_setrandom(struct group *group, ec2np_ptr x)
801 {
802 b2n_ptr d = x->x;
803 struct ec2n_group *grp = (struct ec2n_group *) group->group;
804
805 return b2n_random(d, b2n_sigbit(grp->grp->p) - 1);
806 }
807
808 /*
809 * This is an attempt at operation abstraction. It can happen
810 * that we need to initialize the y variable for the operation
811 * to proceed correctly. When this is the case operation has
812 * to supply the variable 'a' with the chunks of the Y cooridnate
813 * set to zero.
814 */
815 int
ec2n_operation(struct group * grp,ec2np_ptr d,ec2np_ptr a,ec2np_ptr e)816 ec2n_operation(struct group *grp, ec2np_ptr d, ec2np_ptr a, ec2np_ptr e)
817 {
818 b2n_ptr ex = e->x;
819 struct ec2n_group *group = (struct ec2n_group *)grp->group;
820
821 if (a->y->chunks == 0)
822 if (ec2np_find_y(a, group->grp))
823 return -1;
824
825 return ec2np_mul(d, a, ex, group->grp);
826 }
827