FAQ
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

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

  • OpenNota at Mar 1, 2014 at 2:49 am
    Looks like your generator is slightly
    biased: https://gist.github.com/opennota/038f732a8d42f671e83a

    Look at the first and last lines of output.

    --
    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.
  • Justin Judd at Mar 1, 2014 at 3:28 am
    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.

    On Friday, February 28, 2014 9:49:20 PM UTC-5, OpenNota wrote:

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

    Look at the first and last lines of output.
    --
    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.
  • Nick Craig-Wood at Mar 1, 2014 at 8:36 am

    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 <nick@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.
  • Justin Judd at Mar 1, 2014 at 12:22 pm
    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 <javascript:>> --
    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.
  • Justin Judd at Mar 1, 2014 at 12:29 pm
    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.
  • Justin Judd at Mar 2, 2014 at 8:31 pm
    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.
  • Nick Craig-Wood at Mar 2, 2014 at 9:50 pm

    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
    --
    Nick Craig-Wood <nick@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.
  • OpenNota at Mar 1, 2014 at 4:28 am
    I'm not much of a statistician, but I would think of something like
    chi-square test.

    --
    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.
  • OpenNota at Mar 2, 2014 at 10:33 pm
    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

    --
    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.
  • Justin Judd at Mar 3, 2014 at 2:53 am
    Thanks for the recommendation, that is a great idea.
    On Sunday, March 2, 2014 5:33:10 PM UTC-5, OpenNota wrote:

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

Related Discussions

Discussion Navigation
viewthread | post
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