putty/crypto/prng.c

/*
 * 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;
}