1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* plugins/preauth/spake/groups.c - SPAKE group interfaces */
3 /*
4 * Copyright (C) 2015 by the Massachusetts Institute of Technology.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
24 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
28 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
30 * OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 /*
34 * The SPAKE2 algorithm works as follows:
35 *
36 * 1. The parties agree on a group, a base element G, and constant elements M
37 * and N. In this mechanism, these parameters are determined by the
38 * registered group number.
39 * 2. Both parties derive a scalar value w from the initial key.
40 * 3. The first party (the KDC, in this mechanism) chooses a random secret
41 * scalar x and sends T=xG+wM.
42 * 4. The second party (the client, in this mechanism) chooses a random
43 * secret scalar y and sends S=yG+wN.
44 * 5. The first party computes K=x(S-wN).
45 * 6. The second party computes the same value as K=y(T-wM).
46 * 7. Both parties derive a key from a random oracle whose input incorporates
47 * the party identities, w, T, S, and K.
48 *
49 * We implement the algorithm using a vtable for each group, where the primary
50 * vtable methods are "keygen" (corresponding to step 3 or 4) and "result"
51 * (corresponding to step 5 or 6). We use the term "private scalar" to refer
52 * to x or y, and "public element" to refer to S or T.
53 */
54
55 #include "iana.h"
56 #include "trace.h"
57 #include "groups.h"
58
59 #define DEFAULT_GROUPS_CLIENT "edwards25519"
60 #define DEFAULT_GROUPS_KDC ""
61
62 typedef struct groupent_st {
63 const groupdef *gdef;
64 groupdata *gdata;
65 } groupent;
66
67 struct groupstate_st {
68 krb5_boolean is_kdc;
69
70 /* Permitted and groups, from configuration */
71 int32_t *permitted;
72 size_t npermitted;
73
74 /* Optimistic challenge group, from configuration */
75 int32_t challenge_group;
76
77 /* Lazily-initialized list of gdata objects. */
78 groupent *data;
79 size_t ndata;
80 };
81
82 extern groupdef builtin_edwards25519;
83 #ifdef SPAKE_OPENSSL
84 extern groupdef ossl_P256;
85 extern groupdef ossl_P384;
86 extern groupdef ossl_P521;
87 #endif
88
89 static const groupdef *groupdefs[] = {
90 &builtin_edwards25519,
91 #ifdef SPAKE_OPENSSL
92 &ossl_P256,
93 &ossl_P384,
94 &ossl_P521,
95 #endif
96 NULL
97 };
98
99 /* Find a groupdef structure by group number. Return NULL on failure. */
100 static const groupdef *
find_gdef(int32_t group)101 find_gdef(int32_t group)
102 {
103 size_t i;
104
105 for (i = 0; groupdefs[i] != NULL; i++) {
106 if (groupdefs[i]->reg->id == group)
107 return groupdefs[i];
108 }
109
110 return NULL;
111 }
112
113 /* Find a group number by name. Return 0 on failure. */
114 static int32_t
find_gnum(const char * name)115 find_gnum(const char *name)
116 {
117 size_t i;
118
119 for (i = 0; groupdefs[i] != NULL; i++) {
120 if (strcasecmp(name, groupdefs[i]->reg->name) == 0)
121 return groupdefs[i]->reg->id;
122 }
123 return 0;
124 }
125
126 static krb5_boolean
in_grouplist(const int32_t * list,size_t count,int32_t group)127 in_grouplist(const int32_t *list, size_t count, int32_t group)
128 {
129 size_t i;
130
131 for (i = 0; i < count; i++) {
132 if (list[i] == group)
133 return TRUE;
134 }
135
136 return FALSE;
137 }
138
139 /* Retrieve a group data object for group within gstate, lazily initializing it
140 * if necessary. */
141 static krb5_error_code
get_gdata(krb5_context context,groupstate * gstate,const groupdef * gdef,groupdata ** gdata_out)142 get_gdata(krb5_context context, groupstate *gstate, const groupdef *gdef,
143 groupdata **gdata_out)
144 {
145 krb5_error_code ret;
146 groupent *ent, *newptr;
147
148 *gdata_out = NULL;
149
150 /* Look for an existing entry. */
151 for (ent = gstate->data; ent < gstate->data + gstate->ndata; ent++) {
152 if (ent->gdef == gdef) {
153 *gdata_out = ent->gdata;
154 return 0;
155 }
156 }
157
158 /* Make a new entry. */
159 newptr = realloc(gstate->data, (gstate->ndata + 1) * sizeof(groupent));
160 if (newptr == NULL)
161 return ENOMEM;
162 gstate->data = newptr;
163 ent = &gstate->data[gstate->ndata];
164 ent->gdef = gdef;
165 ent->gdata = NULL;
166 if (gdef->init != NULL) {
167 ret = gdef->init(context, gdef, &ent->gdata);
168 if (ret)
169 return ret;
170 }
171 gstate->ndata++;
172 *gdata_out = ent->gdata;
173 return 0;
174 }
175
176 /* Destructively parse str into a list of group numbers. */
177 static krb5_error_code
parse_groups(krb5_context context,char * str,int32_t ** list_out,size_t * count_out)178 parse_groups(krb5_context context, char *str, int32_t **list_out,
179 size_t *count_out)
180 {
181 const char *const delim = " \t\r\n,";
182 char *token, *save = NULL;
183 int32_t group, *newptr, *list = NULL;
184 size_t count = 0;
185
186 *list_out = NULL;
187 *count_out = 0;
188
189 /* Walk through the words in profstr. */
190 for (token = strtok_r(str, delim, &save); token != NULL;
191 token = strtok_r(NULL, delim, &save)) {
192 group = find_gnum(token);
193 if (!group) {
194 TRACE_SPAKE_UNKNOWN_GROUP(context, token);
195 continue;
196 }
197 if (in_grouplist(list, count, group))
198 continue;
199 newptr = realloc(list, (count + 1) * sizeof(*list));
200 if (newptr == NULL) {
201 free(list);
202 return ENOMEM;
203 }
204 list = newptr;
205 list[count++] = group;
206 }
207
208 *list_out = list;
209 *count_out = count;
210 return 0;
211 }
212
213 krb5_error_code
group_init_state(krb5_context context,krb5_boolean is_kdc,groupstate ** gstate_out)214 group_init_state(krb5_context context, krb5_boolean is_kdc,
215 groupstate **gstate_out)
216 {
217 krb5_error_code ret;
218 groupstate *gstate;
219 const char *defgroups;
220 char *profstr1 = NULL, *profstr2 = NULL;
221 int32_t *permitted = NULL, challenge_group = 0;
222 size_t npermitted;
223
224 *gstate_out = NULL;
225
226 defgroups = is_kdc ? DEFAULT_GROUPS_KDC : DEFAULT_GROUPS_CLIENT;
227 ret = profile_get_string(context->profile, KRB5_CONF_LIBDEFAULTS,
228 KRB5_CONF_SPAKE_PREAUTH_GROUPS, NULL, defgroups,
229 &profstr1);
230 if (ret)
231 goto cleanup;
232 ret = parse_groups(context, profstr1, &permitted, &npermitted);
233 if (ret)
234 goto cleanup;
235 if (npermitted == 0) {
236 ret = KRB5_PLUGIN_OP_NOTSUPP;
237 k5_setmsg(context, ret, _("No SPAKE preauth groups configured"));
238 goto cleanup;
239 }
240
241 if (is_kdc) {
242 /*
243 * Check for a configured optimistic challenge group. If one is set,
244 * the KDC will send a challenge in the PREAUTH_REQUIRED method data,
245 * before receiving the list of supported groups.
246 */
247 ret = profile_get_string(context->profile, KRB5_CONF_KDCDEFAULTS,
248 KRB5_CONF_SPAKE_PREAUTH_KDC_CHALLENGE, NULL,
249 NULL, &profstr2);
250 if (ret)
251 goto cleanup;
252 if (profstr2 != NULL) {
253 challenge_group = find_gnum(profstr2);
254 if (!in_grouplist(permitted, npermitted, challenge_group)) {
255 ret = KRB5_PLUGIN_OP_NOTSUPP;
256 k5_setmsg(context, ret,
257 _("SPAKE challenge group not a permitted group: %s"),
258 profstr2);
259 goto cleanup;
260 }
261 }
262 }
263
264 gstate = k5alloc(sizeof(*gstate), &ret);
265 if (gstate == NULL)
266 goto cleanup;
267 gstate->is_kdc = is_kdc;
268 gstate->permitted = permitted;
269 gstate->npermitted = npermitted;
270 gstate->challenge_group = challenge_group;
271 permitted = NULL;
272 gstate->data = NULL;
273 gstate->ndata = 0;
274 *gstate_out = gstate;
275
276 cleanup:
277 profile_release_string(profstr1);
278 profile_release_string(profstr2);
279 free(permitted);
280 return ret;
281 }
282
283
284 void
group_free_state(groupstate * gstate)285 group_free_state(groupstate *gstate)
286 {
287 groupent *ent;
288
289 for (ent = gstate->data; ent < gstate->data + gstate->ndata; ent++) {
290 if (ent->gdata != NULL && ent->gdef->fini != NULL)
291 ent->gdef->fini(ent->gdata);
292 }
293
294 free(gstate->permitted);
295 free(gstate->data);
296 free(gstate);
297 }
298
299 krb5_boolean
group_is_permitted(groupstate * gstate,int32_t group)300 group_is_permitted(groupstate *gstate, int32_t group)
301 {
302 return in_grouplist(gstate->permitted, gstate->npermitted, group);
303 }
304
305 void
group_get_permitted(groupstate * gstate,int32_t ** list_out,int32_t * count_out)306 group_get_permitted(groupstate *gstate, int32_t **list_out, int32_t *count_out)
307 {
308 *list_out = gstate->permitted;
309 *count_out = gstate->npermitted;
310 }
311
312 krb5_int32
group_optimistic_challenge(groupstate * gstate)313 group_optimistic_challenge(groupstate *gstate)
314 {
315 assert(gstate->is_kdc);
316 return gstate->challenge_group;
317 }
318
319 krb5_error_code
group_mult_len(int32_t group,size_t * len_out)320 group_mult_len(int32_t group, size_t *len_out)
321 {
322 const groupdef *gdef;
323
324 *len_out = 0;
325 gdef = find_gdef(group);
326 if (gdef == NULL)
327 return EINVAL;
328 *len_out = gdef->reg->mult_len;
329 return 0;
330 }
331
332 krb5_error_code
group_keygen(krb5_context context,groupstate * gstate,int32_t group,const krb5_data * wbytes,krb5_data * priv_out,krb5_data * pub_out)333 group_keygen(krb5_context context, groupstate *gstate, int32_t group,
334 const krb5_data *wbytes, krb5_data *priv_out, krb5_data *pub_out)
335 {
336 krb5_error_code ret;
337 const groupdef *gdef;
338 groupdata *gdata;
339 uint8_t *priv = NULL, *pub = NULL;
340
341 *priv_out = empty_data();
342 *pub_out = empty_data();
343 gdef = find_gdef(group);
344 if (gdef == NULL || wbytes->length != gdef->reg->mult_len)
345 return EINVAL;
346 ret = get_gdata(context, gstate, gdef, &gdata);
347 if (ret)
348 return ret;
349
350 priv = k5alloc(gdef->reg->mult_len, &ret);
351 if (priv == NULL)
352 goto cleanup;
353 pub = k5alloc(gdef->reg->elem_len, &ret);
354 if (pub == NULL)
355 goto cleanup;
356
357 ret = gdef->keygen(context, gdata, (uint8_t *)wbytes->data, gstate->is_kdc,
358 priv, pub);
359 if (ret)
360 goto cleanup;
361
362 *priv_out = make_data(priv, gdef->reg->mult_len);
363 *pub_out = make_data(pub, gdef->reg->elem_len);
364 priv = pub = NULL;
365 TRACE_SPAKE_KEYGEN(context, pub_out);
366
367 cleanup:
368 zapfree(priv, gdef->reg->mult_len);
369 free(pub);
370 return ret;
371 }
372
373 krb5_error_code
group_result(krb5_context context,groupstate * gstate,int32_t group,const krb5_data * wbytes,const krb5_data * ourpriv,const krb5_data * theirpub,krb5_data * spakeresult_out)374 group_result(krb5_context context, groupstate *gstate, int32_t group,
375 const krb5_data *wbytes, const krb5_data *ourpriv,
376 const krb5_data *theirpub, krb5_data *spakeresult_out)
377 {
378 krb5_error_code ret;
379 const groupdef *gdef;
380 groupdata *gdata;
381 uint8_t *spakeresult = NULL;
382
383 *spakeresult_out = empty_data();
384 gdef = find_gdef(group);
385 if (gdef == NULL || wbytes->length != gdef->reg->mult_len)
386 return EINVAL;
387 if (ourpriv->length != gdef->reg->mult_len ||
388 theirpub->length != gdef->reg->elem_len)
389 return EINVAL;
390 ret = get_gdata(context, gstate, gdef, &gdata);
391 if (ret)
392 return ret;
393
394 spakeresult = k5alloc(gdef->reg->elem_len, &ret);
395 if (spakeresult == NULL)
396 goto cleanup;
397
398 /* Invert is_kdc here to use the other party's constant. */
399 ret = gdef->result(context, gdata, (uint8_t *)wbytes->data,
400 (uint8_t *)ourpriv->data, (uint8_t *)theirpub->data,
401 !gstate->is_kdc, spakeresult);
402 if (ret)
403 goto cleanup;
404
405 *spakeresult_out = make_data(spakeresult, gdef->reg->elem_len);
406 spakeresult = NULL;
407 TRACE_SPAKE_RESULT(context, spakeresult_out);
408
409 cleanup:
410 zapfree(spakeresult, gdef->reg->elem_len);
411 return ret;
412 }
413
414 krb5_error_code
group_hash_len(int32_t group,size_t * len_out)415 group_hash_len(int32_t group, size_t *len_out)
416 {
417 const groupdef *gdef;
418
419 *len_out = 0;
420 gdef = find_gdef(group);
421 if (gdef == NULL)
422 return EINVAL;
423 *len_out = gdef->reg->hash_len;
424 return 0;
425 }
426
427 krb5_error_code
group_hash(krb5_context context,groupstate * gstate,int32_t group,const krb5_data * dlist,size_t ndata,uint8_t * result_out)428 group_hash(krb5_context context, groupstate *gstate, int32_t group,
429 const krb5_data *dlist, size_t ndata, uint8_t *result_out)
430 {
431 krb5_error_code ret;
432 const groupdef *gdef;
433 groupdata *gdata;
434
435 gdef = find_gdef(group);
436 if (gdef == NULL)
437 return EINVAL;
438 ret = get_gdata(context, gstate, gdef, &gdata);
439 if (ret)
440 return ret;
441 return gdef->hash(context, gdata, dlist, ndata, result_out);
442 }
443