8dd8c294 |
1 | /* -*-c-*- |
2 | * |
b817bfc6 |
3 | * $Id: seal.c,v 1.2 2004/04/08 01:36:15 mdw Exp $ |
8dd8c294 |
4 | * |
5 | * The SEAL pseudo-random function family |
6 | * |
7 | * (c) 2000 Straylight/Edgeware |
8 | */ |
9 | |
10 | /*----- Licensing notice --------------------------------------------------* |
11 | * |
12 | * This file is part of Catacomb. |
13 | * |
14 | * Catacomb is free software; you can redistribute it and/or modify |
15 | * it under the terms of the GNU Library General Public License as |
16 | * published by the Free Software Foundation; either version 2 of the |
17 | * License, or (at your option) any later version. |
18 | * |
19 | * Catacomb is distributed in the hope that it will be useful, |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22 | * GNU Library General Public License for more details. |
23 | * |
24 | * You should have received a copy of the GNU Library General Public |
25 | * License along with Catacomb; if not, write to the Free |
26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
27 | * MA 02111-1307, USA. |
28 | */ |
29 | |
8dd8c294 |
30 | /*----- Header files ------------------------------------------------------*/ |
31 | |
32 | #include <assert.h> |
33 | #include <stdarg.h> |
34 | #include <stdio.h> |
35 | |
36 | #include <mLib/bits.h> |
37 | |
38 | #include "arena.h" |
39 | #include "gcipher.h" |
40 | #include "grand.h" |
41 | #include "paranoia.h" |
42 | #include "seal.h" |
43 | #include "sha.h" |
44 | |
45 | /*----- Global variables --------------------------------------------------*/ |
46 | |
47 | const octet seal_keysz[] = { KSZ_ANY, SHA_HASHSZ }; |
48 | |
49 | /*----- Main code ---------------------------------------------------------*/ |
50 | |
51 | /* --- @gamma@ --- * |
52 | * |
53 | * Arguments: @uint32 *p@ = output table |
54 | * @size_t sz@ = size of the output table |
55 | * @const void *k@ = pointer to key material |
56 | * @unsigned i@ = integer offset |
57 | * |
58 | * Returns: --- |
59 | * |
60 | * Use: Initializes a SEAL key table. |
61 | */ |
62 | |
63 | static void gamma(uint32 *p, size_t sz, const void *k, unsigned i) |
64 | { |
65 | uint32 buf[80] = { 0 }; |
66 | const octet *kk = k; |
67 | uint32 aa = LOAD32(kk); |
68 | uint32 bb = LOAD32(kk + 4); |
69 | uint32 cc = LOAD32(kk + 8); |
70 | uint32 dd = LOAD32(kk + 12); |
71 | uint32 ee = LOAD32(kk + 16); |
72 | |
73 | unsigned skip = i % 5; |
74 | i /= 5; |
75 | |
76 | /* --- While there's hashing to do, do hashing --- */ |
77 | |
78 | while (sz) { |
79 | uint32 a = aa, b = bb, c = cc, d = dd, e = ee; |
80 | int j; |
81 | |
82 | /* --- Initialize and expand the buffer --- */ |
83 | |
84 | buf[0] = i++; |
85 | |
86 | for (j = 16; j < 80; j++) { |
87 | uint32 x = buf[j - 3] ^ buf[j - 8] ^ buf[j - 14] ^ buf[j - 16]; |
88 | buf[j] = ROL32(x, 1); |
89 | } |
90 | |
91 | /* --- Definitions for round functions --- */ |
92 | |
93 | #define F(x, y, z) (((x) & (y)) | (~(x) & (z))) |
94 | #define G(x, y, z) ((x) ^ (y) ^ (z)) |
95 | #define H(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) |
96 | |
97 | #define T(v, w, x, y, z, i, f, k) do { \ |
98 | uint32 _x; \ |
99 | z = ROL32(v, 5) + f(w, x, y) + z + buf[i] + k; \ |
100 | w = ROR32(w, 2); \ |
101 | _x = v; v = z; z = y; y = x; x = w; w = _x; \ |
102 | } while (0) |
103 | |
104 | #define FF(v, w, x, y, z, i) T(v, w, x, y, z, i, F, 0x5a827999) |
105 | #define GG(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0x6ed9eba1) |
106 | #define HH(v, w, x, y, z, i) T(v, w, x, y, z, i, H, 0x8f1bbcdc) |
107 | #define II(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0xca62c1d6) |
108 | |
109 | /* --- The main compression function --- * |
110 | * |
111 | * Since this isn't doing bulk hashing, do it the easy way. |
112 | */ |
113 | |
114 | for (j = 0; j < 20; j++) |
115 | FF(a, b, c, d, e, j); |
116 | for (j = 20; j < 40; j++) |
117 | GG(a, b, c, d, e, j); |
118 | for (j = 40; j < 60; j++) |
119 | HH(a, b, c, d, e, j); |
120 | for (j = 60; j < 80; j++) |
121 | II(a, b, c, d, e, j); |
122 | |
123 | /* --- Do the chaining at the end --- */ |
124 | |
125 | a += aa; b += bb; c += cc; d += dd; e += ee; |
126 | |
127 | /* --- Write to the output buffer --- */ |
128 | |
129 | switch (skip) { |
130 | case 0: |
131 | if (sz) { *p++ = a; sz--; } |
132 | case 1: |
133 | if (sz) { *p++ = b; sz--; } |
134 | case 2: |
135 | if (sz) { *p++ = c; sz--; } |
136 | case 3: |
137 | if (sz) { *p++ = d; sz--; } |
138 | case 4: |
139 | if (sz) { *p++ = e; sz--; } |
140 | skip = 0; |
141 | } |
142 | } |
143 | } |
144 | |
145 | /* --- @seal_initkey@ --- * |
146 | * |
147 | * Arguments: @seal_key *k@ = pointer to key block |
148 | * @const void *buf@ = pointer to key material |
149 | * @size_t sz@ = size of the key material |
150 | * |
151 | * Returns: --- |
152 | * |
153 | * Use: Initializes a SEAL key block. The key material may be any |
154 | * size, but if it's not 20 bytes long it's passed to SHA for |
155 | * hashing first. |
156 | */ |
157 | |
158 | void seal_initkey(seal_key *k, const void *buf, size_t sz) |
159 | { |
160 | /* --- Hash the key if it's the wrong size --- */ |
161 | |
162 | if (sz == SHA_HASHSZ) |
163 | memcpy(k->k, buf, sizeof(k->k)); |
164 | else { |
165 | sha_ctx c; |
166 | sha_init(&c); |
167 | sha_hash(&c, buf, sz); |
168 | sha_done(&c, k->k); |
169 | } |
170 | |
171 | /* --- Expand the key to fit the various tables --- */ |
172 | |
173 | gamma(k->t, 512, k->k, 0); |
174 | gamma(k->s, 256, k->k, 0x1000); |
175 | gamma(k->r, SEAL_R, k->k, 0x2000); |
176 | } |
177 | |
178 | /* --- @seal_reset@ --- * |
179 | * |
180 | * Arguments: @seal_ctx *c@ = pointer to a SEAL context |
181 | * |
182 | * Returns: --- |
183 | * |
184 | * Use: Resets the context so that more data can be extracted from |
185 | * it. |
186 | */ |
187 | |
188 | static void seal_reset(seal_ctx *c) |
189 | { |
190 | seal_key *k = c->k; |
191 | uint32 n = c->n; |
192 | uint32 A, B, C, D; |
193 | unsigned p; |
194 | |
195 | /* --- Initialize the new chaining variables --- */ |
196 | |
197 | if (c->l >= SEAL_R) { |
198 | gamma(c->rbuf, SEAL_R, k->k, c->ri); |
199 | c->ri += SEAL_R; |
200 | c->l = 0; |
201 | c->r = c->rbuf; |
202 | } |
203 | |
204 | A = n ^ c->r[0]; |
205 | B = ROR32(n, 8) ^ c->r[1]; |
206 | C = ROR32(n, 16) ^ c->r[2]; |
207 | D = ROR32(n, 24) ^ c->r[3]; |
208 | c->l += 4; |
209 | c->r += 4; |
210 | |
211 | /* --- Ensure that everything is sufficiently diffused --- */ |
212 | |
213 | p = A & 0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9); |
214 | p = B & 0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9); |
215 | p = C & 0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9); |
216 | p = D & 0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9); |
217 | p = A & 0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9); |
218 | p = B & 0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9); |
219 | p = C & 0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9); |
220 | p = D & 0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9); |
221 | |
222 | /* --- Write out some context --- */ |
223 | |
224 | c->n1 = D; c->n2 = B; c->n3 = A; c->n4 = C; |
225 | |
226 | /* --- Diffuse some more --- */ |
227 | |
228 | p = A & 0x7fc; B += k->t[p >> 2]; A = ROR32(A, 9); |
229 | p = B & 0x7fc; C += k->t[p >> 2]; B = ROR32(B, 9); |
230 | p = C & 0x7fc; D += k->t[p >> 2]; C = ROR32(C, 9); |
231 | p = D & 0x7fc; A += k->t[p >> 2]; D = ROR32(D, 9); |
232 | |
233 | /* --- Write out the magic numbers --- */ |
234 | |
235 | c->a = A; c->b = B; c->c = C; c->d = D; |
236 | c->i = 0; |
237 | } |
238 | |
239 | /* --- @seal_initctx@ --- * |
240 | * |
241 | * Arguments: @seal_ctx *c@ = pointer to a SEAL context |
242 | * @seal_key *k@ = pointer to a SEAL key |
243 | * @uint32 n@ = integer sequence number |
244 | * |
245 | * Returns: --- |
246 | * |
247 | * Use: Initializes a SEAL context which can be used for random |
248 | * number generation or whatever. |
249 | */ |
250 | |
251 | void seal_initctx(seal_ctx *c, seal_key *k, uint32 n) |
252 | { |
253 | c->k = k; |
254 | c->n = n; |
255 | c->l = 0; |
256 | c->r = k->r; |
257 | c->ri = 0x2000 + SEAL_R; |
258 | c->qsz = 0; |
259 | seal_reset(c); |
260 | } |
261 | |
262 | /* --- @seal_encrypt@ --- * |
263 | * |
264 | * Arguments: @seal_ctx *c@ = pointer to a SEAL context |
265 | * @const void *src@ = pointer to source data |
266 | * @void *dest@ = pointer to destination data |
267 | * @size_t sz@ = size of the data |
268 | * |
269 | * Returns: --- |
270 | * |
271 | * Use: Encrypts a block of data using SEAL. If @src@ is zero, |
272 | * @dest@ is filled with SEAL output. If @dest@ is zero, the |
273 | * SEAL generator is just spun around for a bit. This shouldn't |
274 | * be necessary, because SEAL isn't RC4. |
275 | */ |
276 | |
277 | void seal_encrypt(seal_ctx *c, const void *src, void *dest, size_t sz) |
278 | { |
279 | const octet *s = src; |
280 | octet *d = dest; |
281 | |
282 | /* --- Expect a big dollop of bytes --- */ |
283 | |
284 | if (sz > c->qsz) { |
285 | seal_key *k = c->k; |
286 | uint32 A = c->a, B = c->b, C = c->c, D = c->d; |
287 | uint32 n1 = c->n1, n2 = c->n2, n3 = c->n3, n4 = c->n4; |
288 | uint32 aa, bb, cc, dd; |
289 | unsigned j = c->i; |
290 | |
291 | /* --- Empty the queue first --- */ |
292 | |
293 | if (c->qsz) { |
294 | if (d) { |
295 | unsigned i; |
296 | octet *p = c->q + sizeof(c->q) - c->qsz; |
297 | for (i = 0; i < c->qsz; i++) |
298 | *d++ = (s ? *s++ ^ *p++ : *p++); |
299 | } |
300 | sz -= c->qsz; |
301 | } |
302 | |
303 | /* --- Main sequence --- */ |
304 | |
305 | for (;;) { |
306 | unsigned P, Q; |
307 | |
308 | /* --- Reset if we've run out of steam on this iteration --- */ |
309 | |
310 | if (j == 256) { |
311 | seal_reset(c); |
312 | A = c->a, B = c->b, C = c->c, D = c->d; |
313 | n1 = c->n1, n2 = c->n2, n3 = c->n3, n4 = c->n4; |
314 | j = 0; |
315 | } |
316 | |
317 | /* --- Make some new numbers --- */ |
318 | |
319 | P = A & 0x7fc; B += k->t[P >> 2]; A = ROR32(A, 9); B ^= A; |
320 | Q = B & 0x7fc; C ^= k->t[Q >> 2]; B = ROR32(B, 9); C += B; |
321 | P = (P + C) & 0x7fc; D += k->t[P >> 2]; C = ROR32(C, 9); D ^= C; |
322 | Q = (Q + D) & 0x7fc; A ^= k->t[Q >> 2]; D = ROR32(D, 9); A += D; |
323 | P = (P + A) & 0x7fc; B ^= k->t[P >> 2]; A = ROR32(A, 9); |
324 | Q = (Q + B) & 0x7fc; C += k->t[Q >> 2]; B = ROR32(B, 9); |
325 | P = (P + C) & 0x7fc; D ^= k->t[P >> 2]; C = ROR32(C, 9); |
326 | Q = (Q + D) & 0x7fc; A += k->t[Q >> 2]; D = ROR32(D, 9); |
327 | |
328 | /* --- Remember the output and set up the next round --- */ |
329 | |
330 | aa = B + k->s[j + 0]; |
331 | bb = C ^ k->s[j + 1]; |
332 | cc = D + k->s[j + 2]; |
333 | dd = A ^ k->s[j + 3]; |
334 | j += 4; |
335 | |
336 | if (j & 4) |
337 | A += n1, B += n2, C ^= n1, D ^= n2; |
338 | else |
339 | A += n3, B += n4, C ^= n3, D ^= n4; |
340 | |
341 | /* --- Bail out here if we need to do buffering --- */ |
342 | |
343 | if (sz < 16) |
344 | break; |
345 | |
346 | /* --- Write the next 16 bytes --- */ |
347 | |
348 | if (d) { |
349 | if (s) { |
350 | aa ^= LOAD32_L(s + 0); |
351 | bb ^= LOAD32_L(s + 4); |
352 | cc ^= LOAD32_L(s + 8); |
353 | dd ^= LOAD32_L(s + 12); |
354 | s += 16; |
355 | } |
356 | STORE32_L(d + 0, aa); |
357 | STORE32_L(d + 4, bb); |
358 | STORE32_L(d + 8, cc); |
359 | STORE32_L(d + 12, dd); |
360 | d += 16; |
361 | } |
362 | sz -= 16; |
363 | } |
364 | |
365 | /* --- Write the new queue --- */ |
366 | |
367 | STORE32_L(c->q + 0, aa); |
368 | STORE32_L(c->q + 4, bb); |
369 | STORE32_L(c->q + 8, cc); |
370 | STORE32_L(c->q + 12, dd); |
371 | c->qsz = 16; |
372 | |
373 | c->a = A; c->b = B; c->c = C; c->d = D; |
374 | c->i = j; |
375 | } |
376 | |
377 | /* --- Deal with the rest from the queue --- */ |
378 | |
379 | if (sz) { |
380 | unsigned i; |
381 | octet *p = c->q + sizeof(c->q) - c->qsz; |
382 | if (d) { |
383 | for (i = 0; i < sz; i++) |
384 | *d++ = (s ? *s++ ^ *p++ : *p++); |
385 | } |
386 | c->qsz -= sz; |
387 | } |
388 | } |
389 | |
390 | /*----- Generic cipher interface ------------------------------------------*/ |
391 | |
392 | typedef struct gctx { |
393 | gcipher c; |
394 | seal_key k; |
395 | seal_ctx cc; |
396 | } gctx; |
397 | |
398 | static const gcipher_ops gops; |
399 | |
400 | static gcipher *ginit(const void *k, size_t sz) |
401 | { |
402 | gctx *g = S_CREATE(gctx); |
403 | g->c.ops = &gops; |
404 | seal_initkey(&g->k, k, sz); |
405 | seal_initctx(&g->cc, &g->k, 0); |
406 | return (&g->c); |
407 | } |
408 | |
409 | static void gencrypt(gcipher *c, const void *s, void *t, size_t sz) |
410 | { |
411 | gctx *g = (gctx *)c; |
412 | seal_encrypt(&g->cc, s, t, sz); |
413 | } |
414 | |
415 | static void gsetiv(gcipher *c, const void *iv) |
416 | { |
417 | gctx *g = (gctx *)c; |
418 | uint32 n = *(const uint32 *)iv; |
419 | seal_initctx(&g->cc, &g->k, n); |
420 | } |
421 | |
422 | static void gdestroy(gcipher *c) |
423 | { |
424 | gctx *g = (gctx *)c; |
425 | BURN(*g); |
426 | S_DESTROY(g); |
427 | } |
428 | |
429 | static const gcipher_ops gops = { |
430 | &seal, |
431 | gencrypt, gencrypt, gdestroy, gsetiv, 0 |
432 | }; |
433 | |
434 | const gccipher seal = { |
435 | "seal", seal_keysz, 0, |
436 | ginit |
437 | }; |
438 | |
439 | /*----- Generic random number generator interface -------------------------*/ |
440 | |
441 | typedef struct grctx { |
442 | grand r; |
443 | seal_key k; |
444 | seal_ctx cc; |
445 | } grctx; |
446 | |
447 | static void grdestroy(grand *r) |
448 | { |
449 | grctx *g = (grctx *)r; |
450 | BURN(*g); |
451 | S_DESTROY(g); |
452 | } |
453 | |
454 | static int grmisc(grand *r, unsigned op, ...) |
455 | { |
456 | grctx *g = (grctx *)r; |
457 | va_list ap; |
458 | int rc = 0; |
459 | va_start(ap, op); |
460 | |
461 | switch (op) { |
462 | case GRAND_CHECK: |
463 | switch (va_arg(ap, unsigned)) { |
464 | case GRAND_CHECK: |
465 | case GRAND_SEEDINT: |
466 | case GRAND_SEEDUINT32: |
467 | case GRAND_SEEDBLOCK: |
468 | case GRAND_SEEDRAND: |
469 | rc = 1; |
470 | break; |
471 | default: |
472 | rc = 0; |
473 | break; |
474 | } |
475 | break; |
476 | case GRAND_SEEDINT: |
477 | seal_initctx(&g->cc, &g->k, va_arg(ap, int)); |
478 | break; |
479 | case GRAND_SEEDUINT32: |
480 | seal_initctx(&g->cc, &g->k, va_arg(ap, uint32)); |
481 | break; |
482 | case GRAND_SEEDBLOCK: { |
483 | const void *p = va_arg(ap, const void *); |
484 | size_t sz = va_arg(ap, size_t); |
485 | uint32 n; |
486 | if (sz >= 4) |
487 | n = LOAD32_L(p); |
488 | else { |
489 | octet buf[4] = { 0 }; |
490 | memcpy(buf, p, sz); |
491 | n = LOAD32_L(p); |
492 | } |
493 | seal_initctx(&g->cc, &g->k, n); |
494 | } break; |
495 | case GRAND_SEEDRAND: { |
496 | grand *rr = va_arg(ap, grand *); |
497 | seal_initctx(&g->cc, &g->k, rr->ops->word(rr)); |
498 | } break; |
499 | default: |
500 | GRAND_BADOP; |
501 | break; |
502 | } |
503 | |
504 | va_end(ap); |
505 | return (rc); |
506 | } |
507 | |
508 | static octet grbyte(grand *r) |
509 | { |
510 | grctx *g = (grctx *)r; |
511 | octet o; |
512 | seal_encrypt(&g->cc, 0, &o, 1); |
513 | return (o); |
514 | } |
515 | |
516 | static uint32 grword(grand *r) |
517 | { |
518 | grctx *g = (grctx *)r; |
519 | octet b[4]; |
520 | seal_encrypt(&g->cc, 0, b, 4); |
521 | return (LOAD32(b)); |
522 | } |
523 | |
524 | static void grfill(grand *r, void *p, size_t sz) |
525 | { |
526 | grctx *g = (grctx *)r; |
527 | seal_encrypt(&g->cc, 0, p, sz); |
528 | } |
529 | |
530 | static const grand_ops grops = { |
531 | "seal", |
532 | GRAND_CRYPTO, 0, |
533 | grmisc, grdestroy, |
534 | grword, grbyte, grword, grand_range, grfill |
535 | }; |
536 | |
537 | /* --- @seal_rand@ --- * |
538 | * |
539 | * Arguments: @const void *k@ = pointer to key material |
540 | * @size_t sz@ = size of key material |
541 | * @uint32 n@ = sequence number |
542 | * |
543 | * Returns: Pointer to generic random number generator interface. |
544 | * |
545 | * Use: Creates a random number interface wrapper around a SEAL |
546 | * pseudorandom function. |
547 | */ |
548 | |
549 | grand *seal_rand(const void *k, size_t sz, uint32 n) |
550 | { |
551 | grctx *g = S_CREATE(grctx); |
552 | g->r.ops = &grops; |
553 | seal_initkey(&g->k, k, sz); |
554 | seal_initctx(&g->cc, &g->k, n); |
555 | return (&g->r); |
556 | } |
557 | |
558 | /*----- Test rig ----------------------------------------------------------*/ |
559 | |
560 | #ifdef TEST_RIG |
561 | |
562 | #include <string.h> |
563 | |
564 | #include <mLib/testrig.h> |
565 | |
566 | static int verify(dstr *v) |
567 | { |
568 | seal_key k; |
569 | seal_ctx c; |
570 | uint32 n = *(uint32 *)v[1].buf; |
571 | dstr d = DSTR_INIT; |
572 | dstr z = DSTR_INIT; |
573 | int i; |
574 | int ok = 1; |
575 | |
576 | DENSURE(&d, v[2].len); |
577 | DENSURE(&z, v[2].len); |
578 | memset(z.buf, 0, v[2].len); |
579 | z.len = d.len = v[2].len; |
580 | seal_initkey(&k, v[0].buf, v[0].len); |
581 | |
582 | for (i = 0; i < v[2].len; i++) { |
583 | seal_initctx(&c, &k, n); |
584 | seal_encrypt(&c, 0, d.buf, i); |
585 | seal_encrypt(&c, z.buf, d.buf + i, d.len - i); |
586 | if (memcmp(d.buf, v[2].buf, d.len) != 0) { |
587 | ok = 0; |
588 | printf("*** seal failure\n"); |
589 | printf("*** k = "); type_hex.dump(&v[0], stdout); putchar('\n'); |
590 | printf("*** n = %08lx\n", (unsigned long)n); |
591 | printf("*** i = %i\n", i); |
592 | printf("*** expected = "); type_hex.dump(&v[2], stdout); putchar('\n'); |
593 | printf("*** computed = "); type_hex.dump(&d, stdout); putchar('\n'); |
594 | } |
595 | } |
596 | |
597 | dstr_destroy(&d); |
598 | dstr_destroy(&z); |
599 | |
600 | return (ok); |
601 | } |
602 | |
603 | static test_chunk defs[] = { |
604 | { "seal", verify, { &type_hex, &type_uint32, &type_hex, 0 } }, |
605 | { 0, 0, { 0 } } |
606 | }; |
607 | |
608 | int main(int argc, char *argv[]) |
609 | { |
610 | test_run(argc, argv, defs, SRCDIR"/tests/seal"); |
611 | return (0); |
612 | } |
613 | |
614 | #endif |
615 | |
616 | /*----- That's all, folks -------------------------------------------------*/ |