FAQ
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
On Saturday, March 1, 2014 7:29:30 AM UTC-5, Justin Judd wrote:

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.
On Saturday, March 1, 2014 7:22:37 AM UTC-5, Justin Judd wrote:

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.
On Saturday, March 1, 2014 3:35:56 AM UTC-5, Nick Craig-Wood wrote:
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
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 8 of 11 | next ›
Discussion Overview
groupgolang-nuts @
categoriesgo
postedMar 1, '14 at 1:46a
activeMar 3, '14 at 2:53a
posts11
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase