diff options
Diffstat (limited to 'crypto/prng.c')
| -rw-r--r-- | crypto/prng.c | 287 |
1 files changed, 287 insertions, 0 deletions
diff --git a/crypto/prng.c b/crypto/prng.c new file mode 100644 index 00000000..247d1dcf --- /dev/null +++ b/crypto/prng.c @@ -0,0 +1,287 @@ +/* + * PuTTY's cryptographic pseudorandom number generator. + * + * This module just defines the PRNG object type and its methods. The + * usual global instance of it is managed by sshrand.c. + */ + +#include "putty.h" +#include "ssh.h" +#include "mpint_i.h" + +#ifdef PRNG_DIAGNOSTICS +#define prngdebug debug +#else +#define prngdebug(...) ((void)0) +#endif + +/* + * This random number generator is based on the 'Fortuna' design by + * Niels Ferguson and Bruce Schneier. The biggest difference is that I + * use SHA-256 in place of a block cipher: the generator side of the + * system works by computing HASH(key || counter) instead of + * ENCRYPT(counter, key). + * + * Rationale: the Fortuna description itself suggests that using + * SHA-256 would be nice but people wouldn't accept it because it's + * too slow - but PuTTY isn't a heavy enough user of random numbers to + * make that a serious worry. In fact even with SHA-256 this generator + * is faster than the one we previously used. Also the Fortuna + * description worries about periodic rekeying to avoid the barely + * detectable pattern of never repeating a cipher block - but with + * SHA-256, even that shouldn't be a worry, because the output + * 'blocks' are twice the size, and also SHA-256 has no guarantee of + * bijectivity, so it surely _could_ be possible to generate the same + * block from two counter values. Thirdly, Fortuna has to have a hash + * function anyway, for reseeding and entropy collection, so reusing + * the same one means it only depends on one underlying primitive and + * can be easily reinstantiated with a larger hash function if you + * decide you'd like to do that on a particular occasion. + */ + +#define NCOLLECTORS 32 +#define RESEED_DATA_SIZE 64 + +typedef struct prng_impl prng_impl; +struct prng_impl { + prng Prng; + + const ssh_hashalg *hashalg; + + /* + * Generation side: + * + * 'generator' is a hash object with the current key preloaded + * into it. The counter-mode generation is achieved by copying + * that hash object, appending the counter value to the copy, and + * calling ssh_hash_final. + */ + ssh_hash *generator; + BignumInt counter[128 / BIGNUM_INT_BITS]; + + /* + * When re-seeding the generator, you call prng_seed_begin(), + * which sets up a hash object in 'keymaker'. You write your new + * seed data into it (which you can do by calling put_data on the + * PRNG object itself) and then call prng_seed_finish(), which + * finalises this hash and uses the output to set up the new + * generator. + * + * The keymaker hash preimage includes the previous key, so if you + * just want to change keys for the sake of not keeping the same + * one for too long, you don't have to put any extra seed data in + * at all. + */ + ssh_hash *keymaker; + + /* + * Collection side: + * + * There are NCOLLECTORS hash objects collecting entropy. Each + * separately numbered entropy source puts its output into those + * hash objects in the order 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,..., + * that is to say, each entropy source has a separate counter + * which is incremented every time that source generates an event, + * and the event data is added to the collector corresponding to + * the index of the lowest set bit in the current counter value. + * + * Whenever collector #0 has at least RESEED_DATA_SIZE bytes (and + * it's not at least 100ms since the last reseed), the PRNG is + * reseeded, with seed data on reseed #n taken from the first j + * collectors, where j is one more than the number of factors of 2 + * in n. That is, collector #0 is used in every reseed; #1 in + * every other one, #2 in every fourth, etc. + * + * 'until_reseed' counts the amount of data that still needs to be + * added to collector #0 before a reseed will be triggered. + */ + uint32_t source_counters[NOISE_MAX_SOURCES]; + ssh_hash *collectors[NCOLLECTORS]; + size_t until_reseed; + uint32_t reseeds; + uint64_t last_reseed_time; +}; + +static void prng_seed_BinarySink_write( + BinarySink *bs, const void *data, size_t len); + +prng *prng_new(const ssh_hashalg *hashalg) +{ + prng_impl *pi = snew(prng_impl); + + memset(pi, 0, sizeof(prng_impl)); + pi->hashalg = hashalg; + pi->keymaker = NULL; + pi->generator = NULL; + memset(pi->counter, 0, sizeof(pi->counter)); + for (size_t i = 0; i < NCOLLECTORS; i++) + pi->collectors[i] = ssh_hash_new(pi->hashalg); + pi->until_reseed = 0; + BinarySink_INIT(&pi->Prng, prng_seed_BinarySink_write); + + pi->Prng.savesize = pi->hashalg->hlen * 4; + + return &pi->Prng; +} + +void prng_free(prng *pr) +{ + prng_impl *pi = container_of(pr, prng_impl, Prng); + + smemclr(pi->counter, sizeof(pi->counter)); + for (size_t i = 0; i < NCOLLECTORS; i++) + ssh_hash_free(pi->collectors[i]); + if (pi->generator) + ssh_hash_free(pi->generator); + if (pi->keymaker) + ssh_hash_free(pi->keymaker); + smemclr(pi, sizeof(*pi)); + sfree(pi); +} + +void prng_seed_begin(prng *pr) +{ + prng_impl *pi = container_of(pr, prng_impl, Prng); + + assert(!pi->keymaker); + + prngdebug("prng: reseed begin\n"); + + /* + * Make a hash instance that will generate the key for the new one. + */ + if (pi->generator) { + pi->keymaker = pi->generator; + pi->generator = NULL; + } else { + pi->keymaker = ssh_hash_new(pi->hashalg); + } + + put_byte(pi->keymaker, 'R'); +} + +static void prng_seed_BinarySink_write( + BinarySink *bs, const void *data, size_t len) +{ + prng *pr = BinarySink_DOWNCAST(bs, prng); + prng_impl *pi = container_of(pr, prng_impl, Prng); + assert(pi->keymaker); + prngdebug("prng: got %"SIZEu" bytes of seed\n", len); + put_data(pi->keymaker, data, len); +} + +void prng_seed_finish(prng *pr) +{ + prng_impl *pi = container_of(pr, prng_impl, Prng); + unsigned char buf[MAX_HASH_LEN]; + + assert(pi->keymaker); + + prngdebug("prng: reseed finish\n"); + + /* + * Actually generate the key. + */ + ssh_hash_final(pi->keymaker, buf); + pi->keymaker = NULL; + + /* + * Load that key into a fresh hash instance, which will become the + * new generator. + */ + assert(!pi->generator); + pi->generator = ssh_hash_new(pi->hashalg); + put_data(pi->generator, buf, pi->hashalg->hlen); + + pi->until_reseed = RESEED_DATA_SIZE; + pi->last_reseed_time = prng_reseed_time_ms(); + + smemclr(buf, sizeof(buf)); +} + +static inline void prng_generate(prng_impl *pi, void *outbuf) +{ + ssh_hash *h = ssh_hash_copy(pi->generator); + + prngdebug("prng_generate\n"); + put_byte(h, 'G'); + for (unsigned i = 0; i < 128; i += 8) + put_byte(h, pi->counter[i/BIGNUM_INT_BITS] >> (i%BIGNUM_INT_BITS)); + BignumCarry c = 1; + for (unsigned i = 0; i < lenof(pi->counter); i++) + BignumADC(pi->counter[i], c, pi->counter[i], 0, c); + ssh_hash_final(h, outbuf); +} + +void prng_read(prng *pr, void *vout, size_t size) +{ + prng_impl *pi = container_of(pr, prng_impl, Prng); + unsigned char buf[MAX_HASH_LEN]; + + assert(!pi->keymaker); + + prngdebug("prng_read %"SIZEu"\n", size); + + uint8_t *out = (uint8_t *)vout; + while (size > 0) { + prng_generate(pi, buf); + size_t to_use = size > pi->hashalg->hlen ? pi->hashalg->hlen : size; + memcpy(out, buf, to_use); + out += to_use; + size -= to_use; + } + + smemclr(buf, sizeof(buf)); + + prng_seed_begin(&pi->Prng); + prng_seed_finish(&pi->Prng); +} + +void prng_add_entropy(prng *pr, unsigned source_id, ptrlen data) +{ + prng_impl *pi = container_of(pr, prng_impl, Prng); + + assert(source_id < NOISE_MAX_SOURCES); + uint32_t counter = ++pi->source_counters[source_id]; + + size_t index = 0; + while (index+1 < NCOLLECTORS && !(counter & 1)) { + counter >>= 1; + index++; + } + + prngdebug("prng_add_entropy source=%u size=%"SIZEu" -> collector %zi\n", + source_id, data.len, index); + + put_datapl(pi->collectors[index], data); + + if (index == 0) + pi->until_reseed = (pi->until_reseed < data.len ? 0 : + pi->until_reseed - data.len); + + if (pi->until_reseed == 0 && + prng_reseed_time_ms() - pi->last_reseed_time >= 100) { + prng_seed_begin(&pi->Prng); + + unsigned char buf[MAX_HASH_LEN]; + uint32_t reseed_index = ++pi->reseeds; + prngdebug("prng entropy reseed #%"PRIu32"\n", reseed_index); + for (size_t i = 0; i < NCOLLECTORS; i++) { + prngdebug("emptying collector %"SIZEu"\n", i); + ssh_hash_digest(pi->collectors[i], buf); + put_data(&pi->Prng, buf, pi->hashalg->hlen); + ssh_hash_reset(pi->collectors[i]); + if (reseed_index & 1) + break; + reseed_index >>= 1; + } + smemclr(buf, sizeof(buf)); + prng_seed_finish(&pi->Prng); + } +} + +size_t prng_seed_bits(prng *pr) +{ + prng_impl *pi = container_of(pr, prng_impl, Prng); + return pi->hashalg->hlen * 8; +} |