valpass

README

valpass - a small golang module to verify passwords

Background

A decade ago I designed an encryption algorithm just for fun and to learn more about cryptography. During development I wrote a little helper tool which I could use to verify some quality metrics of my algorithm: analyze.c.

This module is a re-implementation of this code with go as a reusable module.

Features

• standalone module without external dependencies
• uses 5 different metrics to measure password quality
• you can configure which metric to use
• you can also configure the quality thresholds
• there's support for dictionary lookup, but you need to provide the dictionary yourself
• it's reasonably fast
• the code is small enough to just copy it into your code

Quality metrics

A good password is easy to remember and hard to guess. Don't be fooled by those "use special characters" evangelists: diceware passwords as outlined in the well known xkcd comic are by far the best ones.

However, if it's your job to implement a registration user interface, then sooner or later you'll need to validate passwords.

This module can be used for this job.

By default it checks 3 metrics:

Entropy

Entropy in this case measures the cryptographic strength of the password. In non-technical words: it checks how scrambled the password looks or how many different bits it uses.

We only look for printable US-ASCII characters.

Character diffusion

Of course just measuring entropy is insufficient. For instance a password 12345678 consists of 8 different characters and might pass the entropy check. However, as can be easily seen, the characters are sorted and therefore this password would be a terrible one.

Thus, character diffusion measures how characters are distributed.

Keep in mind that these two metrics would flag the Tr0ub4dor&3 password of the comic as pretty good, while in reality it's not! You might remedy this problem with a longer mandatory password length. But the harsh reality is that people still use such passwords.

Compression

We go one step further and also measure how much the password can be compressed. For instance, let's look at this run length encoding example:

The string aaabggthhhh can be rle encoded to 2ab2gt4h. The result is shorter than the original, it is compressed. The ideal password cannot be compressed or not much.

Of course we do not use RLE. We measure compression using the Flate algorithm.

Optional: dictionary check

You can supply a dictionary of words of your liking and check if the password under test matches one of the words. Submatches can also be done.

Custom measurements

You can also enable or disable certain metrics and you can tune the quality thresholds as needed.

Future/ ToDo

• checksum test using supplied checksum list, e.g. of leaked passwords
• fuzzy testing against dictionary to catch variations, using Levenshtein or something similar.

Usage

Usage is pretty simple:

import "github.com/tlinden/valpass"

[..]
   res, err := valpass.Validate("password"); if err != nil {
     log.Fatal(err)
   }
   
   if !res.Ok {
     log.Fatal("Password is unsecure!")
   }
[..]

You may also tune which tests you want to execute and with wich parameters. To do this, just supply a second argument, which must be a valpas.Options struct:

type Options struct {
	Compress         int         // minimum compression rate in percent, default 10%
	CharDistribution float64     // minimum character distribution in percent, default 10%
	Entropy          float64     // minimum entropy value in bits/char, default 3 bits/s
	Dictionary       *Dictionary // lookup given dictionary, the caller has to provide it
}

To turn off a test, just set the tunable to zero.

Please take a look at the example or at the unit tests.

Performance

Benchmark results of version 0.0.1:

% go test -bench=. -count 5
goos: linux
goarch: amd64
pkg: github.com/tlinden/valpass
cpu: Intel(R) Core(TM) i7-10610U CPU @ 1.80GHz
BenchmarkValidateEntropy-8         98703             12402 ns/op
BenchmarkValidateEntropy-8         92745             12258 ns/op
BenchmarkValidateEntropy-8         94020             12495 ns/op
BenchmarkValidateEntropy-8         96747             12349 ns/op
BenchmarkValidateEntropy-8         94790             12368 ns/op
BenchmarkValidateCharDist-8        95610             12184 ns/op
BenchmarkValidateCharDist-8        96631             12305 ns/op
BenchmarkValidateCharDist-8        97537             12215 ns/op
BenchmarkValidateCharDist-8        97544             13703 ns/op
BenchmarkValidateCharDist-8        95139             15392 ns/op
BenchmarkValidateCompress-8         2140            636274 ns/op
BenchmarkValidateCompress-8         5883            204162 ns/op
BenchmarkValidateCompress-8         5341            229536 ns/op
BenchmarkValidateCompress-8         4590            221610 ns/op
BenchmarkValidateCompress-8         5889            186709 ns/op
BenchmarkValidateDict-8               81          13730450 ns/op
BenchmarkValidateDict-8               78          16081013 ns/op
BenchmarkValidateDict-8               74          17545981 ns/op
BenchmarkValidateDict-8               92          12830625 ns/op
BenchmarkValidateDict-8               94          12564205 ns/op
BenchmarkValidateAll-8              5084            200770 ns/op
BenchmarkValidateAll-8              6054            193329 ns/op
BenchmarkValidateAll-8              5998            186064 ns/op
BenchmarkValidateAll-8              5996            191017 ns/op
BenchmarkValidateAll-8              6268            173846 ns/op
BenchmarkValidateAllwDict-8          374           3054042 ns/op
BenchmarkValidateAllwDict-8          390           3109049 ns/op
BenchmarkValidateAllwDict-8          404           3022698 ns/op
BenchmarkValidateAllwDict-8          393           3075163 ns/op
BenchmarkValidateAllwDict-8          381           3112361 ns/op
PASS
ok      github.com/tlinden/valpass      54.017s

License

This module is licensed under the BSD license.

Prior art

go-password provides similar functionality and it's stable and battle tested. However ir only measures the character entropy.

Documentation

Overview

Package valpass can be used to validate password quality using different metrics.

Index

• Constants
• func Max(args ...int) int
• func Min(args ...int) int
• type Dictionary
• type Levenshtein
  • func NewLevenshtein() *Levenshtein
  • func (m *Levenshtein) Compare(a, b string) float64
  • func (m *Levenshtein) Distance(a, b string) int
• type Options
• type Result
  • func Validate(passphrase string, opts ...Options) (Result, error)

Constants

const (
	MIN_COMPRESS int     = 10
	MIN_DIST     float64 = 10.0
	MIN_ENTROPY  float64 = 3.0
	MIN_DICT_LEN int     = 5000
	MAX_CHARS    int     = 95 // maximum printable US ASCII chars

)

Functions

func Max

func Max(args ...int) int

Max returns the value of the largest argument, or 0 if no arguments are provided.

func Min

func Min(args ...int) int

Min returns the value of the smallest argument, or 0 if no arguments are provided.

Types

type Dictionary

type Dictionary struct {
	Words    []string // Contains the actual dictionary.
	Submatch bool     // Set to true to enable submatches, e.g. 'foo' would match 'foobar', default is false.
	Fuzzy    bool     // Set to true to enable more lax dictionary checks, default is false.
}

Dictionary is a container struct to store and submit a dictionary of words.

type Levenshtein

type Levenshtein struct {
	// CaseSensitive specifies if the string comparison is case sensitive.
	CaseSensitive bool

	// InsertCost represents the Levenshtein cost of a character insertion.
	InsertCost int

	// InsertCost represents the Levenshtein cost of a character deletion.
	DeleteCost int

	// InsertCost represents the Levenshtein cost of a character substitution.
	ReplaceCost int
}

Levenshtein represents the Levenshtein metric for measuring the similarity between sequences.

For more information see https://en.wikipedia.org/wiki/Levenshtein_distance.

func NewLevenshtein

func NewLevenshtein() *Levenshtein

NewLevenshtein returns a new Levenshtein string metric.

Default options:

CaseSensitive: true
InsertCost: 1
DeleteCost: 1
ReplaceCost: 1

func (*Levenshtein) Compare

func (m *Levenshtein) Compare(a, b string) float64

Compare returns the Levenshtein similarity of a and b. The returned similarity is a number between 0 and 1. Larger similarity numbers indicate closer matches.

func (*Levenshtein) Distance

func (m *Levenshtein) Distance(a, b string) int

Distance returns the Levenshtein distance between a and b. Lower distances indicate closer matches. A distance of 0 means the strings are identical.

type Options

type Options struct {
	Compress         int         // minimum compression rate in percent, default 10%
	CharDistribution float64     // minimum character distribution in percent, default 10%
	Entropy          float64     // minimum entropy value in bits/char, default 3 bits/s
	Dictionary       *Dictionary // lookup given dictionary, the caller has to provide it
}

Options struct can be used to configure the validator, turn on/off certain validator functions and tune the thresholds when to flag a password as valid.

Set option to zero or false to disable the feature.

type Result

type Result struct {
	Ok               bool    // overall result
	DictionaryMatch  bool    // true if the password matched a dictionary entry
	Compress         int     // actual compression rate in percent
	CharDistribution float64 // actual character distribution in percent
	Entropy          float64 // actual entropy value in bits/chars
}

Result stores the results of all validations.

func Validate

func Validate(passphrase string, opts ...Options) (Result, error)

Validate validates a given password. You can tune its behavior using the Options struct. However, options are optional, there are sensible defaults builtins.

The returned Result struct returns the password quality.