Food allergies, brown M&Ms, and random passwords

Food allergies

My daughter has a life-threatening food allergy, so eating out is always a little scary. Over the years, we have learned which restaurants are “safe” for her and which are not. Those restaurants that are safe for her have one thing in common – an established protocol for dealing with food allergies. The typical protocol is something along these lines:

1. Inform the server of the food allergy and the specific allergen.
2. The server informs the kitchen of the allergy.
3. The manager makes the food or supervises the making of the food.
4. Her food is brought out on a special plate or by the manager.

Having a documented protocol allows us to enforce adherence to the protocol, and the simplicity of the protocol allows us to easily spot violations. As an example, one restaurant we visited frequently would plate all allergy orders on yellow plates instead of their usual white. If my daughter’s order came out on a white plate, we spoke to the manager, reminded them of their protocol, and sent the food back.

Brown M&Ms

In the 1970s, Van Halen was touring the country with one of the largest stage productions at the time, and many venues had to make infrastructure upgrades to support the show. In order to ensure the safety of the band, crew, and audience, they provided a rider to their contract that included very detailed instructions on what infrastructure had to be in place for the show to happen. Buried in that rider was a clause that said there should be a bowl of M&Ms placed backstage and there should be no brown M&Ms in the bowl. It seems petty at first but, in reality, it was a simple way to ensure the venue had performed the safety-related items in the rider. If they walked backstage and found brown M&Ms, they knew they had to check every other item in the rider to ensure the safety of the band, crew, and audience.

Random passwords

Generating random passwords is much like these two situations in that we have well-established protocols for generating random passwords – and if we fail to generate them correctly, we can bring harm to our users. The following protocol is generally accepted to produce strong random passwords:

1. Use a cryptographically-secure pseudorandom number generator (CSPRNG) to generate random numbers.
2. Adjust those numbers to be within a specified range without introducing a modulo bias.
3. Use the adjusted numbers to pick a random character from your character set.

If you are generating passphrases, you would have a word list instead of a character set, but the algorithm is essentially the same. Again, the simplicity of the algorithm allows us to quickly identify violations and choose how to react.

By looking at our open source Strong Password Generator Go module, you can see that 1Password follows this simple protocol. The module allows you to generate passwords and passphrases that meet a number of different requirements, but they all boil down to the same basic algorithm.

To generate a password using a character set, we use the Generate() method in the char_gen.go file.

	tokens := make([]Token, r.Length)
	for i := 0; i < r.Length; i++ {
		c := chars[randomUint32n(uint32(len(chars)))]
		tokens[i] = Token{c, AtomType}
	}

First, we create a list of tokens and then we populate the list of tokens by choosing random characters from the character set chars. After some additional checks to ensure we met any password policy requirements, that list of tokens becomes our password.

The randomUint32n function is used to generate a random 32-bit unsigned integer within a specified range – in this case, the length of the character set. That function is found in the util.go file.

func randomUint32n(n uint32) uint32 {
	if n < 1 {
		panic("randomUint32n called with 0")
	}
	if n&(n-1) == 0 { // n is power of two, can mask
		return randomUint32() & (n - 1)
	}
	discard := uint32(math.MaxUint32 - math.MaxUint32%n)
	v := randomUint32()
	for v >= discard {
		v = randomUint32()
	}
	return v % n
}

After making sure n is not zero (you cannot choose a random number between 0 and 0 after all), we then check to see if n is a power of 2. If so, there is no modulo bias to remove and we can safely return our random number modulo n. (In this case, we use a bit mask to perform the modulo function). If n is not a power of 2, then we must do a little extra work to get rid of the modulo bias before returning our number. Specifically, we are using rejection sampling to discard the biased numbers.

In either case, we rely on the crypto/rand module in the Go standard libary to provide us with strong random numbers, which can be seen in the randomUint32 function in the util.go file.

func randomUint32() uint32 {
	b := make([]byte, 4)
	_, err := rand.Read(b)
	if err != nil {
		panic("PRNG gen error:" + err.Error())
	}

	return binary.BigEndian.Uint32(b)
}

By using easily understood, well-tested protocols for generating random passwords, 1Password can ensure we provide you with strong passwords for all of your accounts.

Stephen Haywood

Manager, Security Engineering