Robust, know-entropy password generator

Question

My use case is I want a password generator that generates memorable and robust passwords for users, to give me a known minimum entropy.

For this - I'm approximating set of Consonant-Vowel-Consonant words, because then they are both memorable (ish) and have a known entropy level. The reason for this is because I'm not confident that when asked to pick a password, rules based 'systems' lead to at least some of the passwords being horribly weak.

So my core concern is whether the below has any security flaws - I believe that mapping /dev/urandom onto a flat character space should generally accomplish this, and the CVC groupings give me a known minimum entropy (44.9 bits in this case) over user-set passwords that I believe are often quite a lot worse across a whole set of user accounts.

cvc_gen.pl:

#!/usr/bin/env perl

use strict;
use warnings;

#uses /dev/urandom to fetch bytes.
#generates consonant-vowel-consonant groupings.
#each are 11.22 bits of entropy, meaning a 4-group is 45 bits. 
#( 20 * 6 * 20 = 2400, which is 11.22 bits of entropy log2 2400
#log2(2400 ^ 4) = 44.91
#but because it's generated 'true random' it's a know entropy string.

my $num    = 4;
my $format = "CVC";

my %letters = (
    V => [qw ( a e i o u y )],
    C => [ grep { not /[aeiouy]/ } "a" .. "z" ], 
);

my %bitmask_for;
foreach my $type ( keys %letters ) { 
   #find the next power of 2 for the number of 'letters' in the set.
   #So - for the '20' letter group, that's 31. (0x1F)
   #And for the 6 letter group that's 7.  (0x07)
   $bitmask_for{$type} =  ( 2 << log ( @{$letters{$type}} ) / log 2 ) - 1 ; 
}

open( my $urandom, '<:raw', '/dev/urandom' ) or die $!;

for ( 1 .. $num ) {
    for my $type ( split //, $format ) {
        my $value;
        while ( not defined $value or $value >= @{ $letters{$type} } ) {
            my $byte;
            read( $urandom, $byte, 1 );
            #byte is 0-255. Our key space is 20 or 6. 
            #So rather than modulo, which would lead to an uneven distribution,
            #we just bitmask at '1F' giving 0-31, and discard and 'too high'. 
            $value = (unpack "C", $byte ) & $bitmask_for{$type};
        }
        print $letters{$type}[$value];
    }
    print " ";
}
print "\n";
close($urandom);

Not sure about entropy thing - is this [bit.ly/psswrdg] something similar? It has password generation based on user input. The library used is in javascript so must easy to translate in any other language too. — Kzvi
– Kzvi, Commented Feb 1, 2017 at 0:20
@Kzvi - that is more like a 1 random entropy based pass generation - in this question entropy level needs to be controlled. I guess a good starting point though. — software.wikipedia
– software.wikipedia, Commented Feb 1, 2017 at 0:22

Roland Illig · Accepted Answer · 2017-01-27 08:02:30Z

You don't need the bitmasks here, you can do with just basic arithmetic. You're right that a naive modulo would generate biased letter combinations. Therefore the typical pattern is:

$letters = "aeiouy";
$len = length($letters);
$limit = 255 / $len * $len;   # this must be integer arithmetic
$limit = 255 - 255 % $len;    # alternative spelling for the above line

while (($byte = next_byte()) >= $limit) {
    next;
}
return $letters[$byte % $len];

This pattern consumes less random numbers than yours and still generates a fair distribution.

Your code should not output a space at the end of the line.

To make your code testable, you should write a sub that generates a password from a given stream of bytes. Since this is the completely deterministic part, it's easy to test.

Make sure that the call to read succeeds, since otherwise your randomness gets replaced with undefinedness.

You should use the same code pattern to generate the consonants and vowels, so that the code looks more symmetric. But that's a minor point.

Thank you. I started bitmasking when I was concerned about entropy draining /dev/random, but will review. — Sobrique
– Sobrique, Commented Jan 27, 2017 at 7:53

Sobrique · Accepted Answer · 2018-01-29 14:51:24Z

My final attempted incorporated the advice from above:

#!/usr/bin/env perl

use strict;
use warnings;

my $debug = 0;

if ( $debug ) {
  #conditionally import Data::Dumper;
  require Data::Dumper;
  Data::Dumper -> import();
}

#uses /dev/urandom to fetch bytes.
#generates consonant-vowel-consonant groupings.
#each are 11.22 bits of entropy, meaning a 4-group is 45 bits.
#( 20 * 6 * 20 = 2400, which is 11.22 bits of entropy log2 2400
#log2(2400 ^ 4) = 44.91
#but because it's generated 'true random' it's a know entropy string.

my $num    = 4;
my $format = "CVC";

my $count = 0;

my %letters = (
    V => [qw ( a e i o u y )],
    C => [ grep { not /[aeiouy]/ } "a" .. "z" ], );

if ( $debug ) {
   print Dumper(\%letters);
}

my %limit_for;
foreach my $type ( keys %letters ) {
    #map byte size (255) onto keyspace (6 or 20)
    #this is to ensure a symmetric distribution
    #via a 'modulo' operation (e.g. so if it's on the last remainder, it doesn't 
    #use it, because that'd bias towards earlier letters

    $limit_for{$type} = 255 - 255 % @{$letters{$type}}; }

if ( $debug ) {
   print Dumper(\%limit_for);
}

open( my $urandom, '<:raw', '/dev/urandom' ) or die $!;

my @groups;
for ( 1 .. $num ) {
    push @groups, '';
    for my $type ( split //, $format ) {
        my $value;
        #iterate if undefined, and discard any values above the 'limit'.
        #e.g. for 'C' this is 240 out of 255 possibilities,
        #because otherwise there's a slightly higher chance of getting 
        #the first 15 characters from the array. 
        while ( not defined $value or $value >= $limit_for{$type} ) {
            my $byte;
            #error if we failed to read
            read( $urandom, $byte, 1 ) or die $!;

            #convert byte value to numeric
            $value = ( unpack "C", $byte );
            $count++;
        }
        print "$value \t=> " if $debug;
        $value = $value % @{$letters{$type}};
        print "$value \t= " if $debug;
        #select from the type array, the value modolol
        $groups[$#groups] .= $letters{$type}[$value];
        print $letters{$type}[$value] if $debug;
        print "\n" if $debug;
    }
    #print "";
    print "\n" if $debug;
}
#print "\n";
close($urandom);

print join " ", @groups,"\n";
print join "", @groups,"\n";

print "RNG bytes: ", $count, "\n" if $debug;

rossum · Accepted Answer · 2017-01-26 20:40:52Z

You are right about user-selected passwords. A good password includes digits as well as mixed case letters. Better to include a few of those as well. Unfortunately, such passwords are difficult to remember. As a compromise, you could construct passwords on a pattern: "wwwDDwwwDDwww".

The www are three, (or four or five) letter random 'words' with alternating vowels and consonants, as you currently propose. Though is would be better to include the pattern "vcv" as well.

The DD are either two random digits or a single non-alpha character, like %, =, * etc. The first DD is one type and the second DD is the other.

For capital letters, pick one of a few memorable patterns of capitalisation for the three 'words':

first, first, first: "WwwDDWwwDDWww",
middle, middle, middle: "wWwDDwWwDDwWw"
last, last, last: "wwWDDwwWDDwwW",
first, middle, last: "WwwDDwWwDDwwW",
last, middle, first: "wwWDDwWwDDWww",

or similar. For four letter 'words', middle means capitalise the two middle letters: wWWw.

You could use some real words to make the password easier to remember: oNe42tWo$thRee can be remembered as "one, two, three, 42, dollar". That just leaves the capitalisation pattern to recall.

Using a pattern is a weakness, but it is better than pure lowercase letters. You don't have to incorporate all these suggestions, but you should use more than just lowercase. There are 26 lowercase letters, but 62 lowercase, capitals and digits. That gives you more entropy for the same length of password, or the same entropy in a shorter password.

When you suggest adding characters from a different key space, is that for any more profound a reason than maximum entropy in a fixed character length? Because the reason I am doing this is because I don't actually think compressing 45+ bits of entropy into the shortest string possible is actually useful. — Sobrique
– Sobrique, Commented Jan 26, 2017 at 21:59
Ok. Just wanted to understand the premise. It's one I dispute. All else being equal, 6 random characters is harder to remember than 5. But the thing is - it's the entropy that's important for crack/guess resistance. Length is irrelevant. So the trick is to make something memorable that still has enough entropy, and make it as long as necessary. My only concern with the above is whether 45 bits is sufficient. But it's about the same as a 9 character case sensitive alphanumeric. I will assert that I consider monfyrwizker an easier random than 8hGG95wwp to remember — Sobrique
– Sobrique, Commented Jan 27, 2017 at 7:21

Stack Exchange Network

Robust, know-entropy password generator

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Robust, know-entropy password generator

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions