making passwords

[Kragen Sitaker]

It has been asserted that passwords are obsolete, because they are
either too long to memorize or too easy to crack by exhaustive search.
This program generates strongly random passwords using data from
/dev/random that are both short enough to memorize and type accurately
and impractical to attack by exhaustive search.

However, I have had several incidents of forgetting passwords
generated by this program.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>

static int randomdev = -1;
static int reads = 0;
static char *devname = "/dev/random";
static void open_random_device()
{
    randomdev = open(devname, O_RDONLY);
    if (randomdev < 0)
    {
        perror(devname);
        exit(1);
    }
}


static int flip_coin()
{
    int rv;
    static char randbits;
    static int nbits = 0;

    if (!nbits)
    {
        /* replenish randomness */
        rv = read(randomdev, &randbits, 1);
        reads++;
        if (rv < 0)
        {
            perror("read");
            exit(1);
        }
        nbits = 8;
    }
    rv = randbits & 1;
    randbits >>= 1;
    nbits--;
    return rv;
}

static int getbits(int nbits)
{
    int rv = 0;
    for (;;)
    {
        rv |= flip_coin();
        nbits--;
    if (!nbits) return rv;
        rv <<= 1;
    }
}

static char *passchars = " !\"#$%&'()*+,-./0123456789:;<=>?"
                         "@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_"
                         "`abcdefghijklmnopqrstuvwxyz{|}~"; /* omit DEL */
static char passwdchar()
{
    int nbits = 7;
    int passcharslen = strlen(passchars);
    int index;

    assert(1 << (nbits-1) < passcharslen && passcharslen <= 1 << nbits);
    index = getbits(nbits);
    if (index >= passcharslen) return passwdchar();  /* roll again */
    return passchars[index];
}

static void usage(char *argv0)
{
    fprintf(stderr, "Usage: %s pwlen\n", argv0);
    exit(1);
}

static double bitsfor(int len)
{
    return len * log((double)strlen(passchars))/log(2);
}

static double yearsfor(double bits)
{
    /* in 2001 on a 1GHz PIII coppermine using John 1.6, john -test
     * says it can try a little over a million NT LAN Manager keys
     * per second.  Other algorithms are as much as 250 times slower. */
    double keys_per_sec = 2000000;
    double keys_per_year = 86400 * 365.25 * keys_per_sec;
    double keys = pow(2.0, bits);
    return keys / keys_per_year / 2;
}

int main(int argc, char **argv)
{
    int len;
    double bits;
    if (argc != 2) usage(argv[0]);
    len = atoi(argv[1]);
    if (!len) usage(argv[0]);
    open_random_device();
    printf("%d-char random password \"", len);
    bits = bitsfor(len);
    while (len--) printf("%c", passwdchar());
    printf("\"; equivalent to %.1f-bit key.\n", bits);
    printf("Exhaustive search should take %g CPU-years, assuming a CPU from 2001.\n",
           yearsfor(bits));
    printf("Used up %d bytes of randomness from %s\n", reads, devname);
    return 0;
}