@@ 2,43 2,32 @@
package pwgen
import (
- cryptoRand "crypto/rand"
+ "crypto/rand"
"errors"
"fmt"
"log"
"math"
"math/big"
- "math/rand"
"strings"
- "unicode/utf8"
"git.sr.ht/~seirdy/moac"
"git.sr.ht/~seirdy/moac/entropy"
)
-func randRune(runes []rune) rune {
- i, err := cryptoRand.Int(cryptoRand.Reader, big.NewInt(int64(len(runes))))
+func randInt(max int) int {
+ newInt, err := rand.Int(rand.Reader, big.NewInt(int64(max)))
if err != nil {
- log.Panicf("crypto/rand errored when generating a random number: %v", err)
+ log.Panicf("specialIndexes: %v", err)
}
- return runes[i.Int64()]
+ return int(newInt.Int64())
}
func addRuneToPw(password *strings.Builder, runes []rune) {
- newChar := randRune(runes)
+ newChar := runes[randInt(len(runes))]
password.WriteRune(newChar)
}
-func shuffle(password string) string {
- runified := []rune(password)
- rand.Shuffle(len(runified), func(i, j int) {
- runified[i], runified[j] = runified[j], runified[i]
- })
-
- return string(runified)
-}
-
// ErrInvalidLenBounds represents bad minLen/maxLen values.
var ErrInvalidLenBounds = errors.New("bad length bounds")
@@ 46,6 35,7 @@ func computePasswordLength(charsetSize int, pwEntropy float64, minLen, maxLen in
if maxLen > 0 && minLen > maxLen {
return 0, fmt.Errorf("%w: maxLen can't be less than minLen", ErrInvalidLenBounds)
}
+
// combinations is 2^entropy, or 2^s
// password length estimate is the logarithm of that with base charsetSize
// logn(2^s) = s*logn(2) = s/log2(n)
@@ 61,42 51,98 @@ func computePasswordLength(charsetSize int, pwEntropy float64, minLen, maxLen in
return length, nil
}
+// computeSpecialIndexes determines the random locations at which to insert additional preselected chars.
+// Generated passwords don't have truly uniform randomness; they also must have at
+// least one of each charset, no matter how big/small that charset is. When we select
+// one member of each charset, we need to insert those characters at random locations.
+// specialIndexes determines those locations.
+func computeSpecialIndexes(pwLength, charsetCount int) []int {
+ res := make([]int, charsetCount)
+
+ for i := 0; i < charsetCount; i++ {
+ newInt := randInt(pwLength)
+
+ for indexOf(res[0:i], newInt) >= 0 {
+ newInt = randInt(pwLength)
+ }
+
+ res[i] = newInt
+ }
+
+ return res
+}
+
+func indexOf(src []int, e int) int {
+ for i, a := range src {
+ if a == e {
+ return i
+ }
+ }
+
+ return -1
+}
+
func genpwFromGivenCharsets(charsetsGiven [][]rune, entropyWanted float64, minLen, maxLen int) (string, error) {
var charsToPickFrom, pwBuilder strings.Builder
- // at least one element from each charset
+ if maxLen > 0 && maxLen < len(charsetsGiven) {
+ return pwBuilder.String(), fmt.Errorf(
+ "%w: maxLen too short to use all available charsets", ErrInvalidLenBounds,
+ )
+ }
+
for _, charset := range charsetsGiven {
charsToPickFrom.WriteString(string(charset))
-
- addRuneToPw(&pwBuilder, charset)
}
runesToPickFrom := []rune(charsToPickFrom.String())
- // figure out the minimum acceptable length of the password and fill that up before measuring entropy.
+ // figure out the minimum acceptable length of the password
+ // and fill that up before measuring entropy.
pwLength, err := computePasswordLength(len(runesToPickFrom), entropyWanted, minLen, maxLen)
if err != nil {
return pwBuilder.String(), fmt.Errorf("can't generate password: %w", err)
}
+ if pwLength < len(charsetsGiven) {
+ pwLength = len(charsetsGiven) // we know this is below maxLen
+ }
+
pwBuilder.Grow(pwLength + 1)
- currentLength := utf8.RuneCountInString(pwBuilder.String())
- for ; currentLength < pwLength; currentLength++ {
- addRuneToPw(&pwBuilder, runesToPickFrom)
+ specialIndexes := computeSpecialIndexes(pwLength, len(charsetsGiven))
+ currentLength := 0
+
+ for specialI := 0; currentLength < pwLength; currentLength++ {
+ if i := indexOf(specialIndexes, currentLength); i >= 0 {
+ addRuneToPw(&pwBuilder, charsetsGiven[i]) // one of each charset @ a special index
+ specialI++
+ } else {
+ addRuneToPw(&pwBuilder, runesToPickFrom)
+ }
}
+ pw := pwBuilder.String()
+ pwRunes := []rune(pw)
+
+ // keep inserting chars at random locations until the pw is long enough
for ; maxLen == 0 || currentLength < maxLen; currentLength++ {
- addRuneToPw(&pwBuilder, runesToPickFrom)
+ newChar := runesToPickFrom[randInt(len(runesToPickFrom))]
+ index := randInt(len(pwRunes))
+ pwRunes = append(pwRunes[:index+1], pwRunes[index:]...)
+ pwRunes[index] = newChar
+ pw = string(pwRunes)
- pw := pwBuilder.String()
computedEntropy, err := entropy.Entropy(pw)
+ if err != nil {
+ log.Panicf("failed to determine if password is long enough: %v", err)
+ }
- if err != nil || entropyWanted < computedEntropy {
- return shuffle(pw), err
+ if entropyWanted < computedEntropy {
+ break
}
}
- return shuffle(pwBuilder.String()), nil
+ return pw, nil
}
func buildCharsets(charsetsEnumerated []string) [][]rune {
@@ 26,7 26,7 @@ type minMaxLen struct {
// Number of times to run each test-case.
// We run each test case multiple times because of the non-determinism inherent to GenPW().
-const loops int = 16
+const loops int = 32
func buildTestCases() []pwgenTestCase {
return append(buildGoodTestCases(), buildBadTestCases()...)
@@ 38,7 38,7 @@ func buildBadTestCases() []pwgenTestCase {
name: "too short for all charsets",
charsetsWanted: []string{"lowercase", "uppercase", "numbers", "symbols", "latin", "π¦ΨΨ΅π"},
maxLen: 5,
- expectedErr: entropy.ErrPasswordInvalid,
+ expectedErr: ErrInvalidLenBounds,
},
{
name: "bad lengths",
@@ 50,18 50,20 @@ func buildBadTestCases() []pwgenTestCase {
}
}
-func buildGoodTestCases() []pwgenTestCase {
- pwgenCharsets := []struct {
- name string
- charsetsWanted []string
- }{
+type pwgenCharset struct {
+ name string
+ charsetsWanted []string
+}
+
+func goodTestData() ([]pwgenCharset, []minMaxLen, []float64) {
+ pwgenCharsets := []pwgenCharset{
{
name: "everything",
charsetsWanted: []string{"lowercase", "uppercase", "numbers", "symbols", "latin", "δΈηπ§"},
},
{
name: "alnum",
- charsetsWanted: []string{"lowercase", "uppercases", "numbers"},
+ charsetsWanted: []string{"lowercase", "uppercase", "numbers"},
},
{
name: "tinyPassword",
@@ 81,9 83,15 @@ func buildGoodTestCases() []pwgenTestCase {
},
},
}
- minMaxLengths := []minMaxLen{{0, 0}, {0, 32}, {0, 65537}, {80, 0}, {12, 50}}
+ minMaxLengths := []minMaxLen{{0, 0}, {0, 32}, {0, 65537}, {80, 0}, {12, 50}, {0, 1}, {1, 1}, {12, 12}}
entropiesWanted := []float64{0, 1, 32, 64, 256, 512}
+ return pwgenCharsets, minMaxLengths, entropiesWanted
+}
+
+func buildGoodTestCases() []pwgenTestCase {
+ pwgenCharsets, minMaxLengths, entropiesWanted := goodTestData()
+
log.Printf(
"running %d pwgen test cases %d times each\n",
len(pwgenCharsets)*len(minMaxLengths)*len(entropiesWanted), loops,
@@ 97,13 105,18 @@ func buildGoodTestCases() []pwgenTestCase {
for _, entropyWanted := range entropiesWanted {
for _, minMaxLengths := range minMaxLengths {
for _, pwgenCharset := range pwgenCharsets {
+ newCase := pwgenTestCase{
+ pwgenCharset.name, pwgenCharset.charsetsWanted,
+ entropyWanted, minMaxLengths.minLen, minMaxLengths.maxLen,
+ nil,
+ }
+ if minMaxLengths.maxLen > 0 && minMaxLengths.maxLen < len(pwgenCharset.charsetsWanted) {
+ newCase.expectedErr = ErrInvalidLenBounds
+ }
+
testCases = append(
testCases,
- pwgenTestCase{
- pwgenCharset.name, pwgenCharset.charsetsWanted,
- entropyWanted, minMaxLengths.minLen, minMaxLengths.maxLen,
- nil,
- },
+ newCase,
)
caseIndex++
}
@@ 188,12 201,27 @@ func pwHasGoodLength(password string, minLen, maxLen int, entropyWanted float64)
func validateTestCase(test pwgenTestCase, charsets [][]rune) error {
password, err := GenPW(test.charsetsWanted, test.entropyWanted, test.minLen, test.maxLen)
if err != nil && !errors.Is(err, test.expectedErr) {
- return fmt.Errorf("GenPW() = %w", err)
+ return fmt.Errorf("GenPW() errored: %w", err)
+ }
+
+ if err == nil && test.expectedErr != nil {
+ return fmt.Errorf("Expected error %w from GenPW, got nil", test.expectedErr)
}
pwRunes := []rune(password)
- if unusedCharset, validPW := pwUsesEachCharset(&charsets, &pwRunes); !validPW {
- return fmt.Errorf("GenPW() = %s; didn't use each charset\nunused charset: %s", password, unusedCharset)
+ if err == nil {
+ if unusedCharset, validPW := pwUsesEachCharset(&charsets, &pwRunes); !validPW {
+ errorStr := fmt.Sprintf(
+ "GenPW() = %s; didn't use each charset\nunused charset: %s\ncharsets wanted are",
+ password, unusedCharset,
+ )
+ for _, charset := range charsets {
+ errorStr += "\n"
+ errorStr += string(charset)
+ }
+
+ return fmt.Errorf(errorStr)
+ }
}
if invalidRune, validPW := pwOnlyUsesAllowedRunes(&charsets, &pwRunes); !validPW {