[ANN] Password and passphrase generator

[Justin Judd]

It appears that I am not the first person to have this idea, but it appears I am doing the password generation in a novel way.

The library is well documented and should be easy to import and use. I have also designed it to be really easy to use your own character set for the password generation.

The code is at https://github.com/JustinJudd/passgen and I tried to really flesh out the documentation and added numerous examples.

There is also a binary go gettable at github.com/JustinJudd/passgen/passgen and they are also available at https://github.com/JustinJudd/passgen/releases/tag/v1.0

I would appreciate any feedback.

Thanks,

  Justin

[OpenNota]

Looks like your generator is slightly biased: https://gist.github.com/opennota/038f732a8d42f671e83a

Look at the first and last lines of output.

[Justin Judd]

Great idea for testing for bias. Very interesting about the bias for the first and last characters of the passwords. I modified the test and found that it is biased for the first character of every "round". 

Thank you for this test. It gives me a good indication of where I need to look. Do you have recommended tolerances I should use to fail the test if those tolerances are not met? This would be a great test to keep for the library.

[OpenNota]

I'm not much of a statistician, but I would think of something like chi-square test.

[Nick Craig-Wood]

On 01/03/14 03:28, Justin Judd wrote:
> Great idea for testing for bias. Very interesting about the bias for the
> first and last characters of the passwords. I modified the test and
> found that it is biased for the first character of every "round".

It is biassed because of this code

// Loop through how ever many rounds we can get unique data from
32-bits of data
for i := p.rounds - 1; i >= 0; i-- {
if p.Func != nil {
dst[i] = p.Func(v % uint32(p.CharLen))
} else {
dst[i] = p.CharStart + byte(v%uint32(p.CharLen))
}

v /= uint32(p.CharLen)
}

Let's make an example to make things clear...

Lets say you have 255 characters in your character set

This will leave p.rounds set to 4. However when you are taking the last
character out of the 32 bit value it will have a maximum value of
(2**32) / 255 / 255 / 255 = 259, which means that you are twice as
likely to get 0, 1, 2, 3 as you are the rest of the character set.

In fact all the characters are biassed, just to a lesser extent.

If you want do so this without bias, I recommend you use crypto rand.Int

http://golang.org/pkg/crypto/rand/#Int

Which does this properly. Just call it with a big.Int version of
p.CharLen and it will produce beautifully unbiased random numbers for
you, eg

// cryptoRand makes a crypto strong unbiased random number from 0..n-1
func cryptoRand(n int) int {
n_big := big.NewInt(int64(n))
result_big, err := rand.Int(rand.Reader, n_big)
if err != nil {
log.Fatalf("Failed to read crypto random number: %s", err)
}
return int(result_big.Int64())
}

It is instructive to look at the source of this too if you want to see
how to do it properly!

http://golang.org/src/pkg/crypto/rand/util.go?s=2942:3004#L94

--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick

[Justin Judd]

Thanks Nick. I was thinking the mod then divide would provide more of a sliding window across the 32 bits of random data, but there would definitely still be some bias there.

Thanks for the recommendation for using rand.Int, it would simplify things, and I might ultimately do that. For now though, rand.Int will use a minimum of 8 bits and will only use bits in increments of 8, which will waste of lot of randomness from the entropy pool. For the example of digits 0-9, this should only require 4 bits of randomness, but rand.Int would consume 8. 

Now that I am back to the drawing board on the sliding window, I think I have the correct math for it, but will test it out, but I think changing this

v%uint32(p.CharLen)

to something like 

(v - charLen^(round-i-1) ) % uint32(p.CharLen)

or else using a bitmask and shifting it - actually, that might be easier/more efficient.

[Justin Judd]

Oh wait, the bit mask and shift could potentially use more bits though than the other sliding window. I will report back after I tinker a little. 

[Justin Judd]

Thanks again OpenNota and Nick for your help. I ended up rewriting the password generation part using some inspiration from how rand.Int works, but my implementation is a lot more efficient, on the order of 8-10x.

 To generate a 10 digit numerical password, using rand.Int would consume on average 127 bytes from the entropy pool. It generates a number between 0 and 127, if number is > 9, the number is disbanded and the process is repeated. The number will be less than 9 on average 117/127 of the times - about 92% misses, which means for each digit it will take approximately 13 runs of grabbing 1 byte from the entropy pool for each character, and this will be repeated for all ten characters for the estimated total of 127 bytes to generate the 10 digit password.

My implementation grabs 4 byte chunks at a time. For the numerical example, 9 random numbers can be extracted from those 32-bits. I determine the maximum bias level available in the 4 bytes ( floor( 2^32/(10^9) ) * 10^9) or 4*10^9. This is 93% hits, or 7% misses, meaning an expectation of 1.074. So to get the 9 digits would require 1.074 runs times the 4 bytes for a total of 4.3 expected bytes per run. We would have to run this again to get the 10th digit for a total expectation of 8.6 bytes. This is approximately 14-15 times less entropy data used than when using rand.Int

I have also included running times of running both implementations for comparing execution times. Note the flag to increase the timeout because the implementation to use rand.Int did not finish in the default 10 minute timeout.

// With the rand.Int

$ go test -test.timeout=30m github.com/JustinJudd/passgen/

'0'  0.01 '1'  0.01 '2'  0.01 '3' -0.01 '4' -0.01 '5'  0.01 '6' -0.00 '7' -0.01 '8' -0.01 '9' -0.01 

'0' -0.01 '1' -0.02 '2'  0.02 '3'  0.02 '4' -0.01 '5'  0.01 '6'  0.02 '7' -0.01 '8'  0.01 '9' -0.01 

'0' -0.02 '1'  0.01 '2'  0.00 '3' -0.00 '4' -0.00 '5' -0.00 '6' -0.01 '7' -0.01 '8'  0.03 '9'  0.01 

'0'  0.01 '1' -0.01 '2'  0.01 '3' -0.01 '4'  0.00 '5'  0.01 '6' -0.00 '7'  0.00 '8' -0.00 '9' -0.00 

'0'  0.02 '1' -0.00 '2' -0.00 '3'  0.01 '4' -0.00 '5' -0.02 '6'  0.01 '7' -0.00 '8' -0.01 '9'  0.01 

'0' -0.01 '1'  0.00 '2' -0.00 '3' -0.01 '4'  0.01 '5'  0.01 '6' -0.01 '7'  0.02 '8'  0.02 '9' -0.02 

'0' -0.02 '1'  0.01 '2' -0.00 '3'  0.01 '4'  0.01 '5'  0.00 '6'  0.01 '7' -0.01 '8'  0.01 '9' -0.01 

'0' -0.00 '1'  0.01 '2' -0.01 '3' -0.00 '4'  0.01 '5'  0.01 '6' -0.01 '7'  0.00 '8' -0.01 '9'  0.00 

'0'  0.01 '1' -0.01 '2' -0.01 '3'  0.00 '4'  0.02 '5' -0.00 '6' -0.00 '7' -0.00 '8' -0.01 '9'  0.00 

'0' -0.01 '1'  0.01 '2' -0.01 '3'  0.00 '4' -0.01 '5'  0.00 '6' -0.00 '7'  0.01 '8'  0.02 '9' -0.01 

--- FAIL: TestGetPasswordBias (707.88 seconds)

password_test.go:195: 

FAIL

FAIL github.com/JustinJudd/passgen 707.984s

// With my implentation

$ go test -test.timeout=30m github.com/JustinJudd/passgen/

'0'  0.01 '1' -0.01 '2'  0.01 '3' -0.01 '4'  0.01 '5'  0.00 '6' -0.01 '7' -0.01 '8' -0.00 '9'  0.01 

'0'  0.02 '1' -0.01 '2' -0.00 '3' -0.00 '4' -0.01 '5'  0.00 '6'  0.01 '7'  0.00 '8'  0.00 '9' -0.01 

'0' -0.01 '1' -0.00 '2'  0.02 '3' -0.01 '4'  0.01 '5' -0.01 '6'  0.01 '7' -0.01 '8' -0.01 '9'  0.00 

'0'  0.01 '1'  0.00 '2'  0.01 '3' -0.02 '4'  0.01 '5'  0.02 '6' -0.01 '7' -0.00 '8' -0.01 '9' -0.00 

'0'  0.01 '1'  0.01 '2' -0.01 '3' -0.01 '4'  0.00 '5'  0.02 '6' -0.00 '7'  0.00 '8'  0.01 '9' -0.03 

'0' -0.01 '1' -0.01 '2' -0.00 '3'  0.02 '4'  0.00 '5' -0.02 '6' -0.03 '7'  0.00 '8'  0.01 '9'  0.02 

'0'  0.00 '1'  0.01 '2' -0.00 '3'  0.01 '4'  0.01 '5' -0.01 '6' -0.01 '7' -0.00 '8' -0.00 '9' -0.01 

'0' -0.00 '1'  0.01 '2'  0.00 '3'  0.01 '4' -0.00 '5' -0.01 '6'  0.00 '7' -0.01 '8'  0.02 '9' -0.01 

'0'  0.02 '1' -0.00 '2' -0.02 '3'  0.00 '4' -0.01 '5'  0.02 '6' -0.00 '7' -0.01 '8'  0.00 '9' -0.01 

'0'  0.01 '1'  0.00 '2' -0.02 '3'  0.00 '4'  0.01 '5'  0.00 '6'  0.00 '7'  0.00 '8' -0.00 '9' -0.00 

--- FAIL: TestGetPasswordBias (83.29 seconds)

password_test.go:195: 

FAIL

FAIL github.com/JustinJudd/passgen 83.389s 

Once again, thanks for your help. This is a much better implementation, and should address the security concerns raised.

Thanks,

   Justin

[Nick Craig-Wood]

On 02/03/14 20:31, Justin Judd wrote:
> Thanks again OpenNota and Nick for your help. I ended up rewriting the
> password generation part using some inspiration from how rand.Int works,
> but my implementation is a lot more efficient, on the order of 8-10x.
>
> To generate a 10 digit numerical password, using rand.Int would consume
> on average 127 bytes from the entropy pool. It generates a number
> between 0 and 127, if number is > 9, the number is disbanded and the
> process is repeated. The number will be less than 9 on average 117/127
> of the times - about 92% misses, which means for each digit it will take
> approximately 13 runs of grabbing 1 byte from the entropy pool for each
> character, and this will be repeated for all ten characters for the
> estimated total of 127 bytes to generate the 10 digit password.
>
> My implementation grabs 4 byte chunks at a time. For the numerical
> example, 9 random numbers can be extracted from those 32-bits. I
> determine the maximum bias level available in the 4 bytes ( floor(
> 2^32/(10^9) ) * 10^9) or 4*10^9. This is 93% hits, or 7% misses, meaning
> an expectation of 1.074. So to get the 9 digits would require 1.074 runs
> times the 4 bytes for a total of 4.3 expected bytes per run. We would
> have to run this again to get the 10th digit for a total expectation of
> 8.6 bytes. This is approximately 14-15 times less entropy data used than
> when using rand.Int

That sounds like the right way of doing things - nice one!

> I have also included running times of running both implementations for
> comparing execution times. Note the flag to increase the timeout because
> the implementation to use rand.Int did not finish in the default 10
> minute timeout.

10 times faster is great! Not sure I'd have put that much effort in for
generating passwords which you don't do that often but it is a good
exercise making an unbiased random number generator - it is harder than
it looks.

Cheers

Nick

[OpenNota]

Great. In order to not forget doing go fmt, you may want to use the following pre-commit git hook:

http://tip.golang.org/misc/git/pre-commit

[Justin Judd]

Thanks for the recommendation, that is a great idea.