FAQ
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 | 7 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