~seirdy/moac

aab46ebc5f7fd269757f9c2eea7273f145087dfe β€” Rohan Kumar 8 months ago e057b4d v0.3.1
Fix: make char insertion more random

Before this commit:

The requirements of "uniform randomness" and "one element of each
charset requested" are in conflict, so GenPW() previously generated two
passwords and concatenated them. PassA is one random char from each
charset and PassB randomly samples from all charsets combined. PassB has
uniform randomness provided by crypto/rand but might not contain one
element from each charset, especially if one charset is very small.

PassA+PassB wouldn't be random enough, since the resulting password
would have a non-random lump of "one of each charset" at the beginning;
to work around this, MOAC used to "shuffle" PassA+PassB. This shuffler
used math/rand; unlike crypto/rand, this isn't actually random.

After this commit:

This commit changes the mechanism for combining the "one from each
charset" requirement with an otherwise uniformly random password:
instead of generating PassA and PassB, just generate Pass; however, at
random indexes, insert chars that would normally be part of PassA.

After this, the password might still not be long enough: the measured
entropy might be lower than the actual entropy since the entropy
measuring function doesn't know about custom charsets. This means that
additional characters might still need to be added. We now insert these
additional characters into random indexes as well.
2 files changed, 120 insertions(+), 46 deletions(-)

M pwgen/pwgen.go
M pwgen/pwgen_test.go
M pwgen/pwgen.go => pwgen/pwgen.go +75 -29
@@ 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 {

M pwgen/pwgen_test.go => pwgen/pwgen_test.go +45 -17
@@ 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 {