From 44ff6c114bdcd5cef753d2788d029ce46e35727a Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Mon, 16 May 2016 00:25:05 +0100 Subject: [PATCH] Shore up the `grand' protocol. This is a bit of a mess, really. There are two main problems. * Firstly, the business of comparing function pointers simply doesn't work on Windows, because the dynamic linker is too hopeless. If the class implementation is in a different module from Catacomb itself, then the vtable may have a pointer to an import-library stub, which won't compare equal to the library's idea of the default method function. It's basically a mistake to have tried to use the same functions as both user interface and default implementation. Split the two apart. Leave the hacky function-pointer comparisons in the user- interface functions for compatibility with existing out-of-tree generators, which will carry on working about as well as they ever did. Note, however, that the defaulting strategy is now less `clever', and implementations which don't provide native versions of all the methods may end up suffering more than they used to. * The `grand_range' function was simply broken if the `raw' method's output is too small. Synthesizing a full uniform-value-in-range from a narrow primitive generator in single precision arithmetic is rather difficult, so rather than do that I've decided to insist that all `raw' methods have a range of at least a byte's worth, so we can synthesize a word generator out of bytes if necessary, and then use that to satisfy the original larger range request. This is all a bit unsatisfactory, really. I must remember to revisit it when all of these gets made out of a proper object system. --- pub/bbs-rand.c | 2 +- rand/dsarand.c | 3 +- rand/grand.c | 177 ++++++++++++++++++++++++++++++++++------------------- rand/grand.h | 73 ++++++++++++++++++++-- rand/lcrand.c | 2 +- rand/rand.c | 2 +- rand/sslprf.c | 2 +- rand/tlsprf.c | 4 +- symm/chacha.c | 4 +- symm/counter-def.h | 2 +- symm/mgf-def.h | 2 +- symm/ofb-def.h | 2 +- symm/rc4.c | 2 +- symm/salsa20.c | 4 +- symm/seal.c | 2 +- 15 files changed, 199 insertions(+), 84 deletions(-) diff --git a/pub/bbs-rand.c b/pub/bbs-rand.c index 58b62b10..c7dc86e6 100644 --- a/pub/bbs-rand.c +++ b/pub/bbs-rand.c @@ -348,7 +348,7 @@ static const grand_ops gops = { "bbs", GRAND_CRYPTO, 0, gmisc, gdestroy, - gword, gbyte, gword, grand_range, grand_fill + gword, gbyte, gword, grand_defaultrange, grand_defaultfill }; /* --- @bbs_rand@ --- * diff --git a/rand/dsarand.c b/rand/dsarand.c index 9b18ab06..70ffaf81 100644 --- a/rand/dsarand.c +++ b/rand/dsarand.c @@ -310,7 +310,8 @@ static const grand_ops gops = { "dsarand", 0, 0, gmisc, gdestroy, - grand_word, grand_byte, grand_word, grand_range, gfill + grand_defaultword, grand_defaultbyte, grand_defaultword, + grand_defaultrange, gfill }; /* --- @dsarand_create@ --- * diff --git a/rand/grand.c b/rand/grand.c index 17d248b5..e4451917 100644 --- a/rand/grand.c +++ b/rand/grand.c @@ -33,6 +33,111 @@ #include "grand.h" +/*----- Default operations ------------------------------------------------*/ + +/* --- @grand_defaultbyte@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * + * Returns: A uniformly-distributed pseudorandom integer in the interval + * %$[0, 256)$%. + * + * Use: Default @byte@ output method. This calls the @range@ method + * to return a uniform random value between 0 and 255. + */ + +octet grand_defaultbyte(grand *r) + { return (r->ops->range(r, 256)); } + +/* --- @grand_defaultword@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * + * Returns: A uniformly-distributed pseudorandom integer in the interval + * %$[0, 2^{32})$%. + * + * Use: Default @word@ output method. This calls the @fill@ method + * to fill a 4-octet buffer with uniform random bytes, and then + * converts them to an integer. + */ + +uint32 grand_defaultword(grand *r) + { octet buf[4]; r->ops->fill(r, buf, sizeof(buf)); return (LOAD32(buf)); } + +/* --- @grand_defaultrange@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * @uint32 l@ = limit for acceptable results + * + * Returns: A uniformly-distributed pseudorandom integer in the interval + * %$[0, l)$%. + * + * Use: Default @range@ output method. This falls back to either + * @word@ (if the generator's @max@ is zero, or if @max < l@) or + * @raw@ (otherwise). This might recurse via @fill@ and @byte@, + * but this is safe because of the constraint on the @raw@ + * method. + */ + +uint32 grand_defaultrange(grand *r, uint32 l) +{ + uint32 m, z; + uint32 (*w)(grand */*r*/); + uint32 x; + + /* --- Decide where to get data from --- * + * + * The choice of %$2^{32} - 1$% as a limit when using @grand_word@ isn't + * wonderful, but working with %$2^{32}$% is awkward and the loss of a few + * return values isn't significant. The algorithm below still successfully + * returns uniformly distributed results. + * + * If there's a raw generator, and it can cope with the limit, then use it; + * otherwise use the @word@ generator, which may recurse via @fill@ and + * @byte@, but by that point it must be able to satisfy us. + */ + + if (r->ops->max && r->ops->max >= l) { + w = r->ops->raw; + m = r->ops->max; + } else { + assert(!r->ops->max || r->ops->max >= 256); + w = grand_word; + m = 0xffffffff; + } + + /* --- Work out maximum acceptable return value --- * + * + * This will be the highest multiple of @l@ less than @m@. + */ + + z = m - m%l; + + /* --- Generate numbers until something acceptable is found --- * + * + * This will require an expected number of attempts less than 2. + */ + + do x = w(r); while (x >= z); + return (x%l); +} + +/* --- @grand_defaultfill@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * @void *p@ = pointer to a buffer + * @size_t sz@ = size of the buffer + * + * Returns: --- + * + * Use: Fills a buffer with uniformly distributed pseudorandom bytes. + * This calls the @byte@ method repeatedly to fill in the output + * buffer. + */ + +void grand_defaultfill(grand *r, void *p, size_t sz) + { octet *q = p; while (sz--) *q++ = r->ops->byte(r); } + /*----- Main code ---------------------------------------------------------*/ /* --- @grand_byte@ --- * @@ -45,16 +150,8 @@ octet grand_byte(grand *r) { - if (r->ops->byte != grand_byte) - return (r->ops->byte(r)); - else if (r->ops->word != grand_word) - return (r->ops->word(r) & 0xff); - else if (r->ops->fill != grand_fill) { - octet o; - r->ops->fill(r, &o, 1); - return (o); - } else - return (grand_range(r, 256)); + if (r->ops->byte == grand_byte) return (grand_defaultbyte(r)); + else return (r->ops->byte(r)); } /* --- @grand_word@ --- * @@ -67,13 +164,8 @@ octet grand_byte(grand *r) uint32 grand_word(grand *r) { - if (r->ops->word != grand_word) - return (r->ops->word(r)); - else { - octet b[4]; - grand_fill(r, b, sizeof(b)); - return (LOAD32(b)); - } + if (r->ops->word == grand_word) return (grand_defaultword(r)); + else return (r->ops->word(r)); } /* --- @grand_range@ --- * @@ -87,44 +179,8 @@ uint32 grand_word(grand *r) uint32 grand_range(grand *r, uint32 l) { - if (r->ops->range != grand_range) - return (r->ops->range(r, l)); - else { - uint32 m, z; - uint32 (*w)(grand */*r*/); - uint32 x; - - /* --- Decide where to get data from --- * - * - * The choice of %$2^{32} - 1$% as a limit when using @grand_word@ isn't - * wonderful, but working with %$2^{32}$% is awkward and the loss of a - * few return values isn't significant. The algorithm below still - * successfully returns uniformly distributed results. - */ - - if (r->ops->max) { - w = r->ops->raw; - m = r->ops->max; - } else { - w = grand_word; - m = 0xffffffff; - } - - /* --- Work out maximum acceptable return value --- * - * - * This will be the highest multiple of @l@ less than @m@. - */ - - z = m - (m % l); - - /* --- Generate numbers until something acceptable is found --- * - * - * This will require an expected number of attempts less than 2. - */ - - do x = w(r); while (x >= z); - return (x % l); - } + if (r->ops->range == grand_range) return (grand_defaultrange(r, l)); + else return (r->ops->range(r, l)); } /* --- @grand_fill@ --- * @@ -141,15 +197,8 @@ uint32 grand_range(grand *r, uint32 l) void grand_fill(grand *r, void *p, size_t sz) { - if (r->ops->fill != grand_fill) - r->ops->fill(r, p, sz); - else { - octet *q = p; - while (sz) { - *q++ = r->ops->byte(r); - sz--; - } - } + if (r->ops->fill == grand_fill) grand_defaultfill(r, p, sz); + else r->ops->fill(r, p, sz); } /*----- That's all, folks -------------------------------------------------*/ diff --git a/rand/grand.h b/rand/grand.h index ec11404d..b45f0451 100644 --- a/rand/grand.h +++ b/rand/grand.h @@ -51,7 +51,10 @@ typedef struct grand_ops { const char *name; /* Generator's name */ unsigned f; /* Various flags */ - uint32 max; /* Maximum raw output */ + uint32 max; /* Maximum raw output, if nonzero; + * must be either zero or at least + * 256 + */ /* --- Maintenance methods --- */ @@ -60,9 +63,10 @@ typedef struct grand_ops { /* --- Output methods --- * * - * Only one of these operations need actually be implemented. All the - * other operations may be synthesized. Of course, performance is improved - * if more are provided. + * Of these, only @raw@ need be implemented directly by the generator: the + * others can point to provided @grand_default...@ functions, which will + * synthesize the necessary behaviour. Of course, this comes at an + * efficiency penalty. */ uint32 (*raw)(grand */*r*/); /* Uniform over %$[0, max)$% */ @@ -105,6 +109,67 @@ enum { #define GRAND_BADOP assert(((void)"bad grand_misc op", 0)) +/*----- Default operations ------------------------------------------------*/ + +/* --- @grand_defaultbyte@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * + * Returns: A uniformly-distributed pseudorandom integer in the interval + * %$[0, 256)$%. + * + * Use: Default @byte@ output method. This calls the @range@ method + * to return a uniform random value between 0 and 255. + */ + +extern octet grand_defaultbyte(grand */*r*/); + +/* --- @grand_defaultword@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * + * Returns: A uniformly-distributed pseudorandom integer in the interval + * %$[0, 2^{32})$%. + * + * Use: Default @word@ output method. This calls the @fill@ method + * to fill a 4-octet buffer with uniform random bytes, and then + * converts them to an integer. + */ + +extern uint32 grand_defaultword(grand */*r*/); + +/* --- @grand_defaultrange@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * @uint32 l@ = limit for acceptable results + * + * Returns: A uniformly-distributed pseudorandom integer in the interval + * %$[0, l)$%. + * + * Use: Default @range@ output method. This falls back to either + * @word@ (if the generator's @max@ is zero, or if @max < l@) or + * @raw@ (otherwise). This might recurse via @fill@ and @byte@, + * but this is safe because of the constraint on the @raw@ + * method. + */ + +extern uint32 grand_defaultrange(grand */*r*/, uint32 /*l*/); + +/* --- @grand_defaultfill@ --- * + * + * Arguments: @grand *r@ = pointet to generic generator + * @void *p@ = pointer to a buffer + * @size_t sz@ = size of the buffer + * + * Returns: --- + * + * Use: Fills a buffer with uniformly distributed pseudorandom bytes. + * This calls the @byte@ method repeatedly to fill in the output + * buffer. + */ + +extern void grand_defaultfill(grand */*r*/, void */*p*/, size_t /*sz*/); + /*----- Functions provided ------------------------------------------------*/ /* --- @grand_byte@ --- * diff --git a/rand/lcrand.c b/rand/lcrand.c index 6944a71d..d8c4a378 100644 --- a/rand/lcrand.c +++ b/rand/lcrand.c @@ -246,7 +246,7 @@ static const grand_ops gops = { "lcrand", LCRAND_P, 0, gmisc, gdestroy, - graw, gbyte, grand_word, grange, grand_fill + graw, gbyte, grand_defaultword, grange, grand_defaultfill }; /* --- @lcrand_create@ --- * diff --git a/rand/rand.c b/rand/rand.c index e0bebbfa..6fcdf439 100644 --- a/rand/rand.c +++ b/rand/rand.c @@ -560,7 +560,7 @@ static const grand_ops gops = { "rand", GRAND_CRYPTO, 0, gmisc, gdestroy, - gword, gbyte, gword, grand_range, gfill + gword, gbyte, gword, grand_defaultrange, gfill }; /* --- @rand_create@ --- * diff --git a/rand/sslprf.c b/rand/sslprf.c index 83a4c842..06187b39 100644 --- a/rand/sslprf.c +++ b/rand/sslprf.c @@ -270,7 +270,7 @@ static const grand_ops grops = { "", GRAND_CRYPTO, 0, grmisc, grdestroy, - grword, grbyte, grword, grand_range, grfill + grword, grbyte, grword, grand_defaultrange, grfill }; /* ---@sslprf_rand@ --- * diff --git a/rand/tlsprf.c b/rand/tlsprf.c index 3f055b0d..fa28faf4 100644 --- a/rand/tlsprf.c +++ b/rand/tlsprf.c @@ -249,7 +249,7 @@ static const grand_ops dx_grops = { "", GRAND_CRYPTO, 0, dx_grmisc, dx_grdestroy, - dx_grword, dx_grbyte, dx_grword, grand_range, dx_grfill + dx_grword, dx_grbyte, dx_grword, grand_defaultrange, dx_grfill }; /* ---@tlsdx_rand@ --- * @@ -454,7 +454,7 @@ static const grand_ops prf_grops = { "", GRAND_CRYPTO, 0, prf_grmisc, prf_grdestroy, - prf_grword, prf_grbyte, prf_grword, grand_range, prf_grfill + prf_grword, prf_grbyte, prf_grword, grand_defaultrange, prf_grfill }; /* ---@tlsprf_rand@ --- * diff --git a/symm/chacha.c b/symm/chacha.c index bd94ffde..e694ad22 100644 --- a/symm/chacha.c +++ b/symm/chacha.c @@ -672,7 +672,7 @@ static void grdestroy(grand *r) static const grand_ops grops_rand_##rr = { \ "chacha" #rr, GRAND_CRYPTO, 0, \ grmisc, grdestroy, grword, \ - grbyte, grword, grand_range, grfill \ + grbyte, grword, grand_defaultrange, grfill \ }; \ \ grand *chacha##rr##_rand(const void *k, size_t ksz, const void *n) \ @@ -714,7 +714,7 @@ CHACHA_VARS(DEFGRAND) static const grand_ops grxops_rand_##rr = { \ "xchacha" #rr, GRAND_CRYPTO, 0, \ grmisc, grxdestroy_##rr, grword, \ - grbyte, grword, grand_range, grfill \ + grbyte, grword, grand_defaultrange, grfill \ }; \ \ grand *xchacha##rr##_rand(const void *k, size_t ksz, const void *n) \ diff --git a/symm/counter-def.h b/symm/counter-def.h index 2f353232..ead615a3 100644 --- a/symm/counter-def.h +++ b/symm/counter-def.h @@ -398,7 +398,7 @@ static const grand_ops grops = { \ #pre "-counter", \ GRAND_CRYPTO, 0, \ grmisc, grdestroy, \ - grword, grbyte, grword, grand_range, grfill \ + grword, grbyte, grword, grand_defaultrange, grfill \ }; \ \ /* --- @pre_counterrand@ --- * \ diff --git a/symm/mgf-def.h b/symm/mgf-def.h index b5105ed3..529428f9 100644 --- a/symm/mgf-def.h +++ b/symm/mgf-def.h @@ -327,7 +327,7 @@ static const grand_ops grops = { \ #pre "-mgf", \ GRAND_CRYPTO, 0, \ grmisc, grdestroy, \ - grword, grbyte, grword, grand_range, grfill \ + grword, grbyte, grword, grand_defaultrange, grfill \ }; \ \ /* --- @pre_mgfrand@ --- * \ diff --git a/symm/ofb-def.h b/symm/ofb-def.h index 6b1357d0..7f111cb9 100644 --- a/symm/ofb-def.h +++ b/symm/ofb-def.h @@ -410,7 +410,7 @@ static const grand_ops grops = { \ #pre "-ofb", \ GRAND_CRYPTO, 0, \ grmisc, grdestroy, \ - grword, grbyte, grword, grand_range, grfill \ + grword, grbyte, grword, grand_defaultrange, grfill \ }; \ \ /* --- @pre_ofbrand@ --- * \ diff --git a/symm/rc4.c b/symm/rc4.c index 38f00973..214dbc17 100644 --- a/symm/rc4.c +++ b/symm/rc4.c @@ -267,7 +267,7 @@ static const grand_ops grops = { "rc4", GRAND_CRYPTO, 0, grmisc, grdestroy, - grword, grbyte, grword, grand_range, grfill + grword, grbyte, grword, grand_defaultrange, grfill }; /* --- @rc4_rand@ --- * diff --git a/symm/salsa20.c b/symm/salsa20.c index c12945ef..4b35cbd7 100644 --- a/symm/salsa20.c +++ b/symm/salsa20.c @@ -663,7 +663,7 @@ static void grdestroy(grand *r) static const grand_ops grops_rand_##rr = { \ SALSA20_NAME_##rr, GRAND_CRYPTO, 0, \ grmisc, grdestroy, grword, \ - grbyte, grword, grand_range, grfill \ + grbyte, grword, grand_defaultrange, grfill \ }; \ \ grand *SALSA20_DECOR(salsa20, rr, _rand) \ @@ -706,7 +706,7 @@ SALSA20_VARS(DEFGRAND) static const grand_ops grxops_rand_##rr = { \ "x" SALSA20_NAME_##rr, GRAND_CRYPTO, 0, \ grmisc, grxdestroy_##rr, grword, \ - grbyte, grword, grand_range, grfill \ + grbyte, grword, grand_defaultrange, grfill \ }; \ \ grand *SALSA20_DECOR(xsalsa20, rr, _rand) \ diff --git a/symm/seal.c b/symm/seal.c index 57cfc10f..0ba56c0e 100644 --- a/symm/seal.c +++ b/symm/seal.c @@ -529,7 +529,7 @@ static const grand_ops grops = { "seal", GRAND_CRYPTO, 0, grmisc, grdestroy, - grword, grbyte, grword, grand_range, grfill + grword, grbyte, grword, grand_defaultrange, grfill }; /* --- @seal_rand@ --- * -- 2.11.0