projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
New function and example program computes Fibonacci numbers fairly fast.
[u/mdw/catacomb] / seal.c
1 /* -*-c-*-
2 *
3 * $Id: seal.c,v 1.2 2004/04/08 01:36:15 mdw Exp $
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
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 -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)