On Thu, Nov 14, 2013 at 01:48:17AM -0800, edwintorok wrote: > Following the link to builder.ml from your blogpost I noticed the > make_random_password () function, and I have some suggestions, well nitpicks > really. See the 2 commits from this pull request. > > 1. Using Ocaml's buffered I/O means that one make_random_password() call > reads 64k bytes from /dev/urandom which drops the system's entropy to > minimum ~128 bits. The fix is to use unbuffered I/O from the Unix module. > > 2. There is a modulo bias when generating the random password: [0,256) mod 60 > won't give you uniformly distributed bytes. In this particular case it > probably doesn't matter, but you never know when someone copy+pastes your > code into their project thinking this is a proper way to generate random > passwords, so IMHO its best to avoid the modulo bias. > See here for more details: > http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx > And see arc4random_uniform's implementation: > http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random.c?rev=1.26;content-type=text%2Fplain > > 3. The generated password needs ~2^107 brute-force attempts (16 * log2(60) + > log2(default_rounds=5000)), which is more than enough of course, but usually > 128-bit strength is used for keys. A password length of 20 characters would > achieve that. My pull request doesn't include this change, its up to you. > You can merge this Pull Request by running: > > git pull https://github.com/edwintorok/libguestfs make_random_password-fixes > > Or you can view, comment on it, or merge it online at: > > https://github.com/libguestfs/libguestfs/pull/9 > > -- Commit Summary -- > > * Do not use buffered reads on /dev/urandom > * Avoid modulo bias in random password generation > > -- File Changes -- > > M builder/builder.ml (22) > > -- Patch Links -- > > https://github.com/libguestfs/libguestfs/pull/9.patch > https://github.com/libguestfs/libguestfs/pull/9.diff
I'm posting this patch to the list for review. Please follow up there as we don't use github pull requests. Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones libguestfs lets you edit virtual machines. Supports shell scripting, bindings from many languages. http://libguestfs.org
>From cc4fd66701c7e0a5c72614d695565ba15f2e9212 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?T=C3=B6r=C3=B6k=20Edwin?= <[email protected]> Date: Thu, 14 Nov 2013 11:13:50 +0200 Subject: [PATCH 1/2] Do not use buffered reads on /dev/urandom in_channel has a 64k buffer, so one make_random_password () call removes a lot of the system's entropy (for example /proc/sys/kernel/random/entropy_avail goes from ~3000 to 128) --- builder/builder.ml | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) diff --git a/builder/builder.ml b/builder/builder.ml index 874dc8d..55e639e 100644 --- a/builder/builder.ml +++ b/builder/builder.ml @@ -448,6 +448,14 @@ let main () = * Note 'None' means that we randomize the root password. *) let () = + let read_byte fd = + let s = String.make 1 ' ' in + fun () -> + if read fd s 0 1 = 0 then + raise End_of_file; + Char.code s.[0] + in + let make_random_password () = (* Get random characters from the set [A-Za-z0-9] with some * homoglyphs removed. @@ -456,12 +464,12 @@ let main () = "ABCDEFGHIJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz0123456789" in let nr_chars = String.length chars in - let chan = open_in "/dev/urandom" in + let fd = openfile "/dev/urandom" [O_RDONLY] 0 in let buf = String.create 16 in for i = 0 to 15 do - buf.[i] <- chars.[Char.code (input_char chan) mod nr_chars] + buf.[i] <- chars.[read_byte fd () mod nr_chars] done; - close_in chan; + close fd; buf in -- 1.8.4 >From 4cd1763d1313c102234f8b5fb40f7124795035ff Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?T=C3=B6r=C3=B6k=20Edwin?= <[email protected]> Date: Thu, 14 Nov 2013 11:20:07 +0200 Subject: [PATCH 2/2] Avoid modulo bias in random password generation Char.code (input_char chan) mod nr_chars has modulo bias because the original interval is not a multiple of the destination interval, i.e. 256 mod nr_chars != 0. One way to fix this is to keep generating random numbers until they fall outside the interval where modulo bias occurs, that is accept only c=[256 % nr_chars, 256). That interval maps back to [0, nr_chars), and has a length of (256 - 256 % nr_chars), which is a multiple of nr_chars. --- builder/builder.ml | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) diff --git a/builder/builder.ml b/builder/builder.ml index 55e639e..fd335df 100644 --- a/builder/builder.ml +++ b/builder/builder.ml @@ -456,6 +456,14 @@ let main () = Char.code s.[0] in + (* return a random number uniformly distributed in [0, upper_bound) + * avoiding modulo bias *) + let rec uniform_random read upper_bound = + let c = read () in + if c >= 256 mod upper_bound then c mod upper_bound + else uniform_random read upper_bound + in + let make_random_password () = (* Get random characters from the set [A-Za-z0-9] with some * homoglyphs removed. @@ -467,7 +475,7 @@ let main () = let fd = openfile "/dev/urandom" [O_RDONLY] 0 in let buf = String.create 16 in for i = 0 to 15 do - buf.[i] <- chars.[read_byte fd () mod nr_chars] + buf.[i] <- chars.[uniform_random (read_byte fd) nr_chars] done; close fd; -- 1.8.4
_______________________________________________ Libguestfs mailing list [email protected] https://www.redhat.com/mailman/listinfo/libguestfs
