Image of the glider from the Game of Life by John Conway
Skip to content

{ entropy“” } Search Results

The Entropy of a Digital Camera CCD/CMOS Sensor

Recently, Vault12 released an app for iOS that uses the mobile device's camera as a source of randomness. Unfortunately, when putting the generated binary files through the Dieharder tests, it comes out pretty bad. I get 20 "PASSED", 13 "WEAK", and 81 "FAILED" results. For a TRNG, it should be doing much better than that. Now, to be clear, I'm not writing this post to shame Vault12. I actually really love the TrueEntropy app, and am eagerly waiting for it to hit Android, so I can carry around a TRNG in my pocket. However, things can get better, and that is what this post is hopefully addressing.

Using a camera as a TRNG is nothing new. SGI created a patent for pointing a webcam at a lava lamp, using the chaotic nature of the lava lamp itself as the source of entropy. Later, it was realized that this was unnecessary. The CCD/CMOS in the camera was experiencing enough noise from external events to be more than sufficient. This noise is shown in the photo itself, and is appropriately referred to as "image noise".

The primary sources of noise come from the following:

  • Thermal noise- Caused by temperature fluctuations due to electrons flowing across resistant mediums.
  • Photon noise- Caused by photons hitting the CCD/CMOS and releasing energy to neighboring electronics.
  • Shot noise- Caused by current flow across diodes and bipolar transistors.
  • Flicker noise- Caused by traps due to crystal defects and contaniments in the CCD/CMOS chip.
  • Radiation noise- Caused by alpha, beta, gamma, x-ray, and proton decay from radioactive sources (such as outer-space) interacting with the CCD/CMOS.

Some of these noise sources can be manipulated. For example, by cooling the camera, we can limit thermal noise. A camera at 0 degrees Celsius will experience less noise than one at 30 degrees Celsius. A camera in a dark room with less photons hitting the sensor will experience less noise than a bright room. Radiation noise can be limited by isolating the sensor in a radiation-protective barrier.

Let's put this to the test, and see if we can actually calculate the noise in a webcam. To do this, we'll look at a single frame with the lens cap covered, where the photo is taken in a dark room, and the web cam is further encompassed in a box. We'll take the photo at about 20 degrees Celsius (cool room temperature).

In order to get a basis for the noise in the frame, we'll use Shannon Entropy from information theory. Thankfully, understanding Shannon Entropy isn't that big of a deal. My frame will be taken with OpenCV from a PlayStation 3 Eye webcam, which means the frame itself is just a big multidimensional array of numbers between 0 and 255 (each pixel only provides 8 bits of color depth). So, to calculate the Shannon Entropy of a frame, we'll do the following:

  1. Place each number in its own unique bin of 0 through 255.
  2. Create an observed probability distribution (histogram) by counting the numbers in each bin.
  3. Normalize the distribution, creating 256 p-values (the sum of which should equal "1").
  4. For each of the 256 bins, calculate: -p_i*log_2(p_i).
  5. Sum the 256 values.

Thankfully, I don't have all of this by hand- numpy provides a function for me to call that does a lot of the heavy lifting for me.

So, without further ado, let's look at the code, then run it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#!/usr/bin/python

import cv2
import math
import numpy

def max_brightness(frame):
    hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
    h, s, v = cv2.split(hsv)
    v[v > 0] = 255
    v[v < = 0] += 255
    final_hsv = cv2.merge((h, s, v))
    frame = cv2.cvtColor(final_hsv, cv2.COLOR_HSV2BGR)
    return frame

def get_entropy(frame):
    histogram = numpy.histogram(frame, bins=256)[0]
    histogram_length = sum(histogram)
    samples_probability = [float(h) / histogram_length for h in histogram]
    entropy = -sum([p * math.log(p, 2) for p in samples_probability if p != 0])
    return entropy

cap = cv2.VideoCapture(0)
cap.set(3, 640)
cap.set(4, 480)

ret, frame1 = cap.read()
ret, frame2 = cap.read()
frame_diff = cv2.absdiff(frame1, frame2)

cv2.imwrite('/tmp/frame1.bmp', frame1)
cv2.imwrite('/tmp/frame2.bmp', frame2)
cv2.imwrite('/tmp/frame_diff.bmp', frame_diff)

frame1_max = max_brightness(frame1)
frame2_max = max_brightness(frame2)
frame_diff_max = max_brightness(frame_diff)

cv2.imwrite('/tmp/frame1_max.bmp', frame1_max)
cv2.imwrite('/tmp/frame2_max.bmp', frame2_max)
cv2.imwrite('/tmp/frame_diff_max.bmp', frame_diff_max)

print("Entropies:")
print("    frame1: {}".format(get_entropy(frame1)))
print("    frame2: {}".format(get_entropy(frame2)))
print("    frame_diff: {}".format(get_entropy(frame_diff)))
print("    frame1_max: {}".format(get_entropy(frame1_max)))
print("    frame2_max: {}".format(get_entropy(frame2_max)))
print("    frame_diff_max: {}".format(get_entropy(frame_diff_max)))

Let's look over the code before running it. First, I'm actually capturing two frames right next to each other, then taking their composite difference. We know that a photo consists of its signal (the data most people are generally interested in) and its noise (the data they're not). By taking the composite difference between the two, I'm attempting to remove the signal. Because the frames were taken in rapid succession, provided nothing was drastically changing between the frames, most of the data will be nearly identical. So the signal should disappear.

But what about the noise? Well, as discussed above, the noise is a bit unpredictable and slightly unmanageable. Unlike my signal, the noise will be drastically different between the two frames. So, rather than removing noise, I'll actually be adding noise in the difference.

The next thing you'll notice is that I'm either maximizing or completely removing the luminosity in an HSV color profile. This is done just as a visual demonstration of what the noise actually "looks like" in the frame. You can see this below (converted to PNG for space efficiency).

Frame 1

Frame 2

Difference of frames 1 & 2

Frame 1 maxed luminosity

Frame 2 maxed luminosity

Difference of frames 1 & 2 maxed luminosity


Running the Python script in my 20 degrees Celsius dark room with the lens cap on and all light removed as much as possible, I get:

$ python frame-entropy.py
Entropies:
    frame1: 0.0463253223509
    frame2: 0.0525489364555
    frame_diff: 0.0864590940377
    frame1_max: 0.0755975713815
    frame2_max: 0.0835428883103
    frame_diff_max: 0.134900632254

The "ent(1)" userspace utility confirms these findings when saving the frames as uncompressed bitmaps:

$ for I in frame*.bmp; do printf "$I: "; ent "$I" | grep '^Entropy'; done
frame1.bmp: Entropy = 0.046587 bits per byte.
frame1_max.bmp: Entropy = 0.076189 bits per byte.
frame2.bmp: Entropy = 0.052807 bits per byte.
frame2_max.bmp: Entropy = 0.084126 bits per byte.
frame_diff.bmp: Entropy = 0.086713 bits per byte.
frame_diff_max.bmp: Entropy = 0.135439 bits per byte.

It's always good to use an independent source to confirm your findings.

So, in the standard frames, I'm getting about 0.05 bits per byte of entropy. However, when taking the composite difference, that number almost doubles to about 0.09 bits per byte. This was expected, as you remember, we're essentially taking the noise from both frames, and composing them in the final frame. Thus, the noise is added in the final frame.

What was actually surprising to me were the entropy values after setting the extreme luminosity values. This may be due to the fact that there are larger deltas between adjacent pixels when creating our histogram. When taking the difference of the two adjusted frames, the entropy jumps up to about 0.13 bits per byte. So, we could safely say that a composed frame with maxed luminosity that is the difference of two frames has about 0.11 bits of entropy per byte, plus or minus 0.02 bits per byte.

What does this say about the frame as a whole though? In my case, my frame is 640x480 pixels. Knowing that each pixel in my PS3 Eye webcam only occupies 1 byte or 8 bits, we can calculate the entropy per frame:

(640*480) pixels/frame * 1 byte/pixel = 307200 bytes/frame
307200 bytes/frame * 0.11 entropy bits/byte = 33792 entropy bits/frame

Each frame in my 640x480 PS3 Eye webcame provides about 33,792 bits of entropy. For comparison SHA-256 theoretically provides a maximum of 256-bits of entropic security. Of course, we should run millions of trials, collecting the data, calculate the standard deviation, and determine a more true average entropy. But, this will suffice for this post.

So, now that we know this, what can we do with this data? Well, we can use it as a true random number generator, but we have to be careful. Unfortunately, as the frame is by itself, it's heavily biased. In the frame, there exists spatial correlation with adjacent pixels. In the frame difference, there exists both spatial and time correlations. This isn't sufficient as a secure true random number generator. As such, we need to remove the bias. There are a few ways of doing this, called "randomness extraction", "software whitening", "decorrelation", or "debiasing". Basically, we want to take a biased input, and remove any trace of bias in the output.

We could use John von Neumann decorrelation, where we look at two non-overlapping consecutive bits. If the two bits are identical, then both bits are discarded. If they are different, then the most significant bit is output, while the least significant bit is discarded. This means that at a best, you are discarding half of your data, but how much is discarded all depends on how badly biased the data is. We know that our frame is only providing 0.11 bits of entropy per 8 bits. So we're keeping 11 bits out of 800. That's a lot of data that is discarded. One drawback with this approach, however, is if one or more bits are "stuck", such is an a dead pixel. Of course, this will lower the overall entropy of the frame, but will also drastically impact the extractor.

A different approach would be to use chaos machines. This idea is relatively new and not thoroughly studied; at least I'm struggling to find good research papers on the topic. The idea is taking advantage of the chaotic behavior of certain dynamical systems, such as a double pendulum. Due to the nature of chaos, small fluctuations in initial conditions lead to large changes in the distant future. The trick here is selecting your variables, such as the time distance and chaotic process correctly. Unlike John von Neumann decorrelation, that automatically discovers the bias and discards it for you, care has to be taken to make sure that the resulting output is debiased.

A better approach is using cryptographic primitives like one-way hashing or encryption, sometimes called "Kaminsky debiasing". Because most modern crytographic primitives are designed to emulate theoretical uniform unbiased random noise, the security rests on whether or not that can be achieved. In our case, we could encrypt the frame with AES and feed the ciphertext as our TRNG output. Unfortunately, this means also managing a key, which doesn't necessarily have to be kept secret. A better idea would be to use cryptographic hashing functions, like SHA-2, or even better, extendable output functions (XOFs).

Obviously, it should go without stating, that encrypting or hashing your biased input isn't increasing the entropy. This means that we need to have a good handle on what our raw entropy looks like (as we did above) beforehand. We know in our case that we're getting about 35 kilobits of entropy per frame, so hashing with SHA-256 is perfectly acceptable, even if we're losing a great deal of entropy in the output. However, if we were only getting 200-bits of security in each frame, while SHA-256 is debiasing the data, we still only have 200-bits of entropy in the generated output.

Really though, the best approach is an XOF. We want to output as much of our raw entropy as we can. Thankfully, NIST has 2 XOFs standardized as part of the SHA-3: SHAKE128 and SHAKE256. An XOF allows you to output a digest of any length, where SHA-256 for example, only allows 256-bits of output. The security margin of the SHAKE128 XOF function is the minimum of half of the digest or 128-bits. If I have an entropy 35 kilobits, I would like to have all of that entropy available in the output. As such, I can output 4 KB in the digest knowing full well that's within my entropy margin. Even though I'm losing as much data as the John von Neumann extractor, I'm not vulnerable to "stuck pixels" being a problem manipulating the extractor.

When I put all this code together in Python:

  1. Take the difference of two consecutive overlapping frames.
  2. Maximize the luminosity of the new composed frame.
  3. Hash the frame with SHAKE128.
  4. Output 4 KB of data as our true random noise.

At 30 frames per second for a resolution of 640x480, outputting 4 KB per frame will provide 120 KBps of data per second, and this is exactly what I see when executing the Python script. The PS3 Eye camera also supports 60 fps at a lower resolution, so I could get 240 KBps if I can keep the same security margin of 4 KB per frame. I haven't tested this, but intuition tells me I'll have a lower security margin at the lower resolution.

Coming full circle, when we put our TRNG to the Dieharder test, things come out vastly different than Vault12's results:

  • Vault12 TrueEntropy:
    1. PASSED: 20
    2. WEAK: 13
    3. FAILED: 81
  • My webcam TRNG:
    1. PASSED: 72
    2. WEAK: 12
    3. FAILED: 30

CPU Jitter Entropy for the Linux Kernel

Normally, I keep a sharp eye on all things cryptographic-related with the Linux kernel. However, in 4.2, I missed something fantastic: jitterentropy_rng.ko. This is a Linux kernel module that measures the jitter of the high resolution timing available in modern CPUs, and uses this jitter as a source of true randomness. In fact, using the CPU timer as a source of true randomness isn't anything new. If you're read my blog for some time, you're already familiar with haveged(8). This daemon also collects CPU jitter and feeds the collected data into the kernel's random number generator.

The main site is at http://www.chronox.de/jent.html and the PDF paper describing the CPU jitter entropy can be found on the site.

So why the blog post about jitterentropy_rng.ko? Because now that we have something in the mainline kernel, we get a few benefits:

  1. More eyes are looking at the code, and can adjust, analize, and refine the entropy gathering process, making sure it's not to aggressive nor conservative in its approach.
  2. We now have something that can collect entropy much earlier in the boot sequence, even before the random number generator has been initialized. This means we can have a properly seeded CSPRNG when the CSPRNG is initialized.
  3. While not available now, we could have a kernelspace daemon collecting entropy and feeding it to the CSPRNG without the need for extra software.
  4. This isn't just for servers, desktops, and VMs, but anything that runs the Linux kernel on a modern CPU, including Android phones, embedded devices, and SoC.
  5. While haveged(8) has been a good solution for a long time, it has been heavily criticized, and it seems development on it has stalled. Here is another software solution for true randomness without the need of potentially dangerous 3rd party USB random number generators.
  6. You don't need Intel's RDRAND. Any modern CPU with a high resolution timer will work. AMD, SPARC, ARM, MIPS, PA-RISC, Power, etc.

As mentioned in the list, unfortunately, loading the kernel doesn't automatically top-off the entropy estimate of the internal state of the CSPRNG (/proc/sys/kernel/random/entropy_avail). As such, /dev/random will still block when the estimate is low or exhausted. So you'll still need to run a userspace daemon to prevent this behavior. The author has also shipped a clean, light userspace daemon that just reads the data provided by the jitterentropy_rng.ko kernel module, and uses ioctl(2) to increase the estimate. The jitterentropy_rng.ko module provides about 10 KBps of random data.

Again, this isn't anything that something like haveged(8) doesn't already have access to. However, by taking advantage of a loaded kernel module, we can ensure that randomness is being collected before the CSPRNG is initialized. So, when CSPRNG initialization happens, we can ensure that it is properly seeded on first boot, minimizing the likelihood that exact keys will be created on distinct systems. This is something haveged(8) can't provide, as it runs entirely in userspace.

Unfortunately, jitterentropy-rngd(8) isn't available in the Debian repositories yet, so you'll need to download the compressed tarball from the author's website, manually compile and install yourself. However, he does ship a systemd(8) service file, which makes it easy to get the daemon up and running on boot with minimal effort.

I've had the jitterentropy_rng.ko module installed with the jitterentropy-rngd(8) userspace daemon running all day today, without haveged(8), and needless to say, I'm pleased. It keeps the CSPRNG entropy estimate sufficiently topped off for software that still relies on /dev/random (please stop doing this developers- start using /dev/urandom please) and provides adequate performance. Near as I can tell, there is not a character device created when loading the kernel module, so you can't access the unbiased data before feeding it into the CSPRNG. As such, I don't have a way to test its randomness quality. Supposedly, there is a way to access this via debugfs, but I haven't found it.

Anyway, I would recommend using jitterentropy_rng.ko and jitterentropy-rngd(8) over haveged(8) as the source for your randomness.

Entropy As A Service

Back in October 2012, I announced hundun.ae7.st. It's an "entropy server" that delivers encrypted random bits that are indistinguishable from true random, directly to your GNU/Linux input entropy pool. Per the Linux CSPRNG source code, the bits in the input entropy pool are then cryptographically hashed with SHA1 before sending the bits to the blocking and non-blocking pools. The bits generated by my entropy server come only from 5 Entropy Keys, which appear to no longer be in production. I'm working on a "version 2.0" of the server, where more true random sources will be mixed into the pool, such as the onboard Broadcom HWRNG, atmospheric noise, haveged(8), and 2 TrueRNG HWRNGs. Keep an eye out both on this blog, and the entropy server web page for updates.

However, it appears that I am not the only one who has thought of this idea.

In September 2013, the U.S. National Institude of Standards and Technology introduced the NIST Randomness Beacon. Every 60 seconds, a random number is "broadcast", which is cryptographically signed, timestamped, and contains the value of the random number from the previous minute's broadcast. It comes complete with a REST API, which you can take advantage of for your internal application. They warn, very strictly, that these bits should not be used for cryptographic keys. Instead, it would be more fitting to use these random bits as for things such as lottery drawings, dice rolls, and other non-sensitive randomness implementations. However, you could write a REST application that took this data, and reseeded the Linux CSPRNG every 60 seconds. Because SHA1 is only theoretically broken, and not practically broken, and further because the Linux kernel is receiving other sources of input to reseed the CSPRNG, it seems difficult for an attacker to recover the internal state of your CSPRNG without compromising the computer, to determine the sequence of the CSPRNG. A simple shell script could be something like this (assuming you have rhash(1) installed):

1
2
3
4
5
6
7
#!/bin/sh
# Reseed the Linux kernel CSPRNG with data from NIST
SALT=$(dd if=/dev/urandom bs=64 count=1 2> /dev/null)
EPOCH=$(date --date="$(date +%H:%M:00)" +%s)
RESULTS=$(GET https://beacon.nist.gov/rest/record/"$EPOCH")
DATA=$(echo "${SALT}${RESULTS}" | rhash --sha3-512 - | cut -d ' ' -f 1)
echo "$DATA" > /dev/random

Further, in February 2014, Canonical announced entropy.ubuntu.com. Canonical is providing their own application, which currently seems to be only packaged for Ubuntu, called pollinate. The idea is for newly created Ubuntu VMs or containers to immediately have a source of entropy to rely on, to quickly feed the Linux CSPRNG before it is needed in generating cryptographic keys, such as SSH or SSL keys. Whlie some criticize its security, it seems more like FUD from those who don't fully understand the internal workings of the Linux kernel CSRNG, than actual security concerns. Reseeding the CSPRNG is less of an issue for me, as much as Canonical tracking which IP requested bits from their server, and logging them (as should be the case for any service from any provider). It may be true that on first boot, not enough entropy may have been generated to seed the CSPRNG. As such, initiating a TLS session to a server may open the network connection up for an attack. While the theory might be sound, I would like to see a proof of concept or even an implementation of the attack, before I start FUD slinging.

So, as it sits, there are to my knowledge, three Entropy-as-a-Service (EaaS) servers online, each with different implementations, that require different software, that you could use for a variety of applications. Of course, there is also random.org which has been on the Internet for a good long while, long before "as a service" was a buzz term. However, I don't see them as an entropy server as much as an implementation server. They are great for getting dice rolls, lottery picks, card shuffles, etc, but not so much "raw data", even though it does have a "random number sequence" generator, and it does provide an API.

With the revelations about the NSA and the increasing weight put on cryptography as a result, I'm guessing more of these types of servers will pop up. Also, only my service, so far, actually increases your entropy estimate in your kernel. The other services mentioned here only reseed the Linux kernel CSPRNG, without increasing the entropy estimate.

Creating Strong Passwords Without A Computer, Part 0 - Understanding Entropy

I've written a new series that investigates the art of creating very strong passwords without the aid of a computer. Sure, there are many software applications that will generate strong passwords for you, each with their own advantages and disadvantages. They're so plentiful, that it would be impossible to outline them all. However, generating passwords without the aid of a computer can be a very challenging, yet very rewarding process. It may even be impractical or impossible for you to install software on the computer you're using at the moment, when you need to generate a password.

Introduction

Before we start diving into passwords, we need to define what a "strong password" is. I've defined this many times on this blog, and as long as I keep blogging about passwords, I'll continue to define it. A "strong password" is one that is defined by entropy. The more the entropy, the stronger the password. Further, a "strong password" is one that is defined by true randomness, which means it was not influenced by a human being during the creation.

We're told that passwords must have the following characteristics when creating them:

  • Passwords should be long.
  • Passwords should contain both uppercase and lowercase letters.
  • Passwords should contain digits.
  • Passwords should contain special punctuation characters.
  • Passwords should be unique for every account.
  • Passwords should be easy to remember.
  • Passwords should not be written down.
  • Passwords should not be based on dictionary words.
  • Passwords should not contain birthdates, anniversaries, other other personally identifiable information.

These rules can be difficult, because remembering all these rules make passwords difficult to remember, especially if you have a unique password for every account. It's almost like creating a witches brew, just so you can create the perfect password potion:

Double, double toil and trouble;
Fire burn and cauldron bubble.
Fillet of a fenny snake,
In the cauldron boil and bake;
Eye of newt, and toe of frog,
Wool of bat, and tongue of dog,
Adder’s fork, and blind-worm’s sting,
Lizard’s leg, and howlet’s wing,
For a charm of powerful trouble,
Like a hell-broth boil and bubble.

Personally, I find it all a bit confusing, and even more annoying that security-conscious blogs endorse that garbage. I tend to keep things much more simple:

  • A password must contain great amounts of entropy (we'll quantify this in a minute).
  • A password must be truly random (no human interference).

So, what is entropy, and how do we quantify it? Let's begin.

Defining Entropy

Entropy can be found in many fields of study. Abstractly, entropy is defined as:

1. a thermodynamic quantity representing the unavailability of a system's thermal energy for conversion into mechanical work, often interpreted as the degree of disorder or randomness in the system.
2. lack of order or predictability; gradual decline into disorder. "a marketplace where entropy reigns supreme".

So entropy is a measure of disorder, or unpredictability. For our needs, we'll use entropy from Claude Shannon's Information Theory, a branch of Mathematics, which is defined mathematically as follows:

Definition of entropy.

where:

  • H = entropy in binary bits.
  • L = the number of symbols chosen for your message (length).
  • N = Total number of unique possibilities each symbol could be.

Or, if you would like to enter this on your calculator:

Entopy equation suitable for calculator entry.

This can be proven quite simply. First off, let us define the logarithm. As with standard mathematics, we'll define it as the inverse of the exponential function. In other words:

Definition of the logarithm.

Suppose we want to find the entropy size of of a 13-character password taking advantage of all 94 possible printable symbols on the ASCII keyboard. Then, if all 94 printable symbols are a valid choice for each of the 13 characters in my passphrase, then to find the total number of combinations that my password could be, we write it as:

logarithm2

Now, a property of logarithms is the ability to change base. Because entropy is defined in bits, or base-2, I'll change the base of my logarithm, as follows:

logarithm3

Rewritting the equation, we get the following result:

logarithm4

And thus, we've arrived at our conclusion.

This assumes that the message was chosen completely at random. However, if there is human intervention in creating the message, then the equation gets much more difficult. As such, for the point of this post, and most of my posts detailing entropy, we'll assume that the password or message was chosen completely at random.

Some Entropy Equation Examples

If you create a message from lowercase letters only, then the number of unique possibilities for each symbol is 26, as there are only 26 letters in the English alphabet. So, each character provides only 4.7 bits of entropy:

Entropy example equation 1.

If you created a message from lowercase letters, uppercase letters and digits, then the number of unique possibilities for each symbol is 62, as there are 26 unique lowercase letters, 26 unique uppercase letters, and 10 digits in the English language. So, each character would provide only 5.95 bits of entropy:

Entropy example equation 2.

A Needle In A Haystack

Knowing how much entropy is needed when creating a password can be tricky. Is 50-bits enough? Do I need 60-bits instead? 80-bits? 128? 256? More? In order to get a good firm grasp on quantifying entropy, I want to first create an analogy:

Entropy is to a haystack, as your password is to a needle.

Finding your password means searching through your entropy space. Your password should have a minimum amount of entropy. That means that the password will NOT be found in entropy spaces smaller than what your password is defined in. So if your haystack, or entropy, is 256-bits in size, your needle, or password, should not be found in 255-bit haystacks, or smaller.

To quantify this a bit, in a previous post, I demonstrated that a SHA1 hash has an output space of 61-bits due to cryptanalysis techniques, and it turns out that it was far too small. At the time of this writing, the bitcoin network is processing 2^61 SHA256 hashes every 76 seconds using specialized hardware called ASICs. The computing power is only going to grow also, as there is financial gain to be made from mining.

In other words, with these ASICs, 30 quadrillion pieces of hay can be analyzed every second. If your haystack has 2^61 pieces of hay, one of which is actually your needle, this haystack can be fully processed in 76 seconds flat.

How Entropy Relates To Passwords

If you continue using the same bitcoin network model for our speed benchmark, then at 30 quadrillion pieces of hay (passwords) every second, to completely exhaust the full output space, for the following haystack sizes, it would take:

  • 64-bits: 10 minutes.
  • 72-bits: 2 days.
  • 80-bits: 15 months.
  • 88-bits: 327 years.

In the past, I've shown that 72-bits of entropy (your haystack) seems to be sufficient for passwords (your needle) using the RSA 72-bit distributed computing project on distributed.net. After analyzing the bitcoin network mining operations, and how trivial it is to build specialized ASICs for these tasks, I'm beginning to think that you should have at least 80-bits of entropy for your passwords. As computing gets more and more stronger, that number will continue to increase.

As a result, to create a "strong password", I would recommend the following:

  • A password must contain at least 80-bits of entropy.
  • A password must be truly random.

Conclusion

Entropy is how we measure unpredictability. If we need any sort of unpredictability, such as finding passwords (needles in a haystack), then the more entropy we have, the better off we are. On computer systems, entropy is stored in what's called an "entropy pool". The larger the pool, the more reliably the operating system can generate true random numbers for security applications, such as GPG and long term SSL keys. The same can be said for passwords. The more entropy we have, the better off our passwords can become.

So, don't starve yourself by selecting weak 8-10 character passwords, and trying to generate random data in your head. Generate real random passwords and use large amounts of entropy.

The Entropy Server

With my last post about the entropy key hardware true random number generator (TRNG), I was curious if I could set this up as a server. Basically, bind to a port that spits out true random bits over the internet, and allow clients to connect to it to fill their own entropy pools. One of the reasons I chose the entropy key from Simtec was because they provide Free Software client and server applications to make this possible.

So, I had a mission- make it happen and cost effective as possible. To be truly cost effective, the server the keys are plugged into cannot consume a great amount of wattage. It should be headless, not needing a monitor. It shouldn't be a large initial cost up front either. The application should be lightweight, and the client should only request the bits when needed, rather than consuming a constant stream. Thankfully, that last requirement is already met in the client software provided by Simtec. However, to reach the other points was a bit of a challenge, until I stumbled upon the Raspberry Pi. For only $35, and consuming no more than 1Whr, I found my target.

Unfortunately, the "Raspbian" operating system uses some binary blobs as part of the ARM architecture where source code is not available. Further, they chose HDMI over the cheaper and less proprietary DisplayPort as the digital video out. However, it's only $35, so meh. After getting the operating system installed on the SD card, I installed ekeyd per my previous post, and setup the entropy keys. Now, at this point, it's not bound to a TCP port. That needs to be enabled. Further, if binding to a TCP port, the data will be unencrypted. Because the data is whitened and true random noise, it would prefer to keep it that way, and not hav ethe data biased on the wire. So, I would also need to setup stunnel.

First, to install the packages:

$ sudo aptitude install ekeyd stunnel4

Now, you'll also need to setup your entropy keys. That won't be covered here. You do need to configure ekeyd to bind to a port on localhost. We'll use stunnel to bind to an external port. Edit the /etc/entropykey/ekeyd.conf, and comment out the following line:

TCPControlSocket "1234"

The default port of 1234 is fine, as it's local. If it's already in use, you may want to choose something else. Whatever you do use, this is what stunnel will connect to. So, let's edit the /etc/stunnel/stunnel.conf file, and setup the connection. To make sure you understand this, stunnel will be acting as a client to ekeyd. Further, stunnel will be acting as a server to the network. Stunnel clients will be connecting on this external port.

cert = /etc/stunnel/ekeyd.pem
[ekeyd]
accept=8086
connect=1234

This configuration says that stunnel will connect locally on port 1234 and serve the resulting data on port 8086, encrypted with the /etc/stunnel/ekeyd.pem SSL certificate. Notice that we are actually using a PEM key and certificate for handling the encrypted bits. This can be signed by a CA authority for your domain already, or it can be self-signed. In my case, I went with self-signed and issued the following command, making the certificate good for 10 years:

# openssl req -new -out mail.pem -keyout /etc/stunnel/ekeyd.pem -nodes -x509 -days 3650

When finished with creating the SSL certificate, we are ready to start serving the bits. Start up the ekeyd server, then the stunnel one:

$ sudo /etc/init.d/ekeyd restart
$ sude /etc/init.d/stunnel4 restart

You can now verify that everything is setup correctly by verifying the connections on the box. You should see both ports bound, and waiting for connections based on our configuration above:

$ netstat -tan | awk '/LISTEN/ && /(8086|1234)/'
tcp        0      0 127.0.0.1:1234          0.0.0.0:*               LISTEN
tcp        0      0 0.0.0.0:8086            0.0.0.0:*               LISTEN

At this point, the only thing left to do is to poke a hole in your firewall for port 8086 (not port 1234), and allow stunnel clients to connect. The clients will also need to install the ekeyd-egd-linux and stunnel4 packages. A separate post on this is forth-coming.

The Entropy Key

Recently, I purchased 5 entropy keys from http://entropykey.co.uk. They are hardware true random number generators using reverse bias P-N junctions. Basically, they time when electrons jump a depeltion zone in the junction, where a voltage is applied to the point of near breakdown. Basically, taking advantage of the random characteristics of quantum mechanics.

There are a lot of really interesting things about the keys that brought me to purchase them. First, is the fact that they use two junctions along with the XOR function to test for corellations. If corellations exist, then the keys shutdown. Second, they use skein 256 internally as an encryption mechanism to deliver the random bits to the kernel, where they are decrypted. The bits are encrypted to ensure that an attacker on the box cannot manipulate the bits. Third, the keys are protected physically against tampering. If the temperature is outside of operating range, the keys will shut down, and if the keys are opened, epoxy will spill out on the board, shorting the board, preventing operation.

Tollef Fog Heen is seeing about 4 KBps with his key. I hooked my keys up to my Raspberry Pi, and I'm only seeing about 2 KBps per key. However, when connected to my T61, or other computers, I see about 3.5-4 KBps. Installing haveged along side with the entropy keys on my Raspberry Pi, and I have a total throughput of about 150 KBps of random data.

To setup the entropy key, you will receive a package with a DVD, the entropy key, and a paper for the master password to decrypt the bits from the key. To get the keys setup, you will need to match the key ID "EKXXXXX" with the same ID on the paper, if you have multiple keys. Then, in Debian/Ubuntu, you can install the daemon to talk to the keys:

sudo aptitude install ekeyd

You will now have the userspace utility to talk to the keys. As you plugin each key into your computer, the ekeyd daemon will setup a device in /dev/entropykey/. My five keys show me:

$ ls -l /dev/entropykey/
total 0
lrwxrwxrwx 1 root root 10 Oct  4 07:04 Sf9sBkiDUkkSGBSH -> ../ttyACM0
lrwxrwxrwx 1 root root 10 Oct  4 07:04 Sf9sBkiDUkkTJRSH -> ../ttyACM4
lrwxrwxrwx 1 root root 10 Oct  4 07:04 Sf9tBkiDUkkHNBWH -> ../ttyACM1
lrwxrwxrwx 1 root root 10 Oct  4 07:04 Sf9tBkiDUkkJOBWH -> ../ttyACM2
lrwxrwxrwx 1 root root 10 Oct  4 07:04 Sf9vBkiDUkkTNBSH -> ../ttyACM3

Further, when using the ekeydctl userspace utility, you can see the status of each key:

$ ekeydctl list
NR,OK,Status,Path,SerialNo
1,NO,Long-Term-Key is bad,/dev/entropykey/Sf9sBkiDUkkSGBSH,Sf9sBkiDUkkSGBSH
2,NO,Long-Term-Key is bad,/dev/entropykey/Sf9tBkiDUkkHNBWH,Sf9tBkiDUkkHNBWH
3,NO,Long-Term-Key is bad,/dev/entropykey/Sf9tBkiDUkkJOBWH,Sf9tBkiDUkkJOBWH
4,NO,Long-Term-Key is bad,/dev/entropykey/Sf9vBkiDUkkTNBSH,Sf9vBkiDUkkTNBSH
5,NO,Long-Term-Key is bad,/dev/entropykey/Sf9sBkiDUkkTJRSH,Sf9sBkiDUkkTJRSH

So, we need to setup the keys, and make them live, so we can start using the entropy that comes from them. By using the ekey-rekey userspace utility, I can setup each key with the master psasword sent on my card:

# ekey-rekey 'Sf9sBkiDUkkSGBSH' 'ajx1 b52m cHvd d51n e4tS fYPs g2p3 xDAZ IeYf jCYM kqWi'

Of course, I changed my master key in the example above. I only wish to show that the spaces are important when setting up your keys. Do this for each of your keys, and you should see something to the effect:

NR,OK,Status,Path,SerialNo
1,YES,RUNNING OK,/dev/entropykey/Sf9sBkiDUkkSGBSH,Sf9sBkiDUkkSGBSH
2,YES,RUNNING OK,/dev/entropykey/Sf9tBkiDUkkHNBWH,Sf9tBkiDUkkHNBWH
3,YES,RUNNING OK,/dev/entropykey/Sf9tBkiDUkkJOBWH,Sf9tBkiDUkkJOBWH
4,YES,RUNNING OK,/dev/entropykey/Sf9vBkiDUkkTNBSH,Sf9vBkiDUkkTNBSH
5,YES,RUNNING OK,/dev/entropykey/Sf9sBkiDUkkTJRSH,Sf9sBkiDUkkTJRSH

Your entropy pool is now being filled with real, true, random numbers. You can test this by looking at the raw random data, and when exhausting the pool, you can see how quickly it fills:

$ dd if=/dev/random count=1 | xxd
0+1 records in
0+1 records out
128 bytes (128 B) copied, 8.6482e-05 s, 1.5 MB/s
0000000: d932 fc37 089e 4229 81cd d433 4e62 472a  .2.7..B)...3NbG*
0000010: 3383 1f64 9b33 5797 f001 aa9a b15d 6581  3..d.3W......]e.
0000020: 758f cb1c a797 a39a 37c8 db67 ae0b ff19  u.......7..g....
0000030: bf0e 891d 702e 2f58 cfd8 963d e499 13db  ....p./X...=....
0000040: 5f48 f7d3 cdcc 2e52 e2fc 4685 ad38 68bd  _H.....R..F..8h.
0000050: 6de3 917b 4627 4695 3371 3335 9304 0f7a  m..{F'F.3q35...z
0000060: a540 62aa 01a6 1006 84b2 1cb5 23ce 790e  .@b.........#.y.
0000070: 12fb 8edc 78a2 13bf 1780 eb7e 1fbf a400  ....x......~....
$ pv -a < /dev/random > /dev/null
[18.5 kB/s]

Lastly, it's probably a good idea to test the quality of bias existing in the random stream using the dieharder suite of tests, or the FIPS 140-2 tests with rngtest. I have run both. The tests are slow, so let them run for a while to collect a lot of data. However, after about 3-4 minutes, here is the output from rngtest. You will certainly want to let it run longer, like an hour or so:

# rngtest < /dev/random 
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
^Crngtest: bits received from input: 27814504
rngtest: FIPS 140-2 successes: 1389
rngtest: FIPS 140-2 failures: 1
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=34.735; avg=79.156; max=675.401)Kibits/s
rngtest: FIPS tests speed: (min=968.716; avg=4301.815; max=5622.121)Kibits/s
rngtest: Program run time: 349417245 microsecond

Strong Passwords NEED Entropy

I just finished reading an article on Ars Technica titled "Ask Ars: Where should I store my passwords?". There was a specific paragraph that I took issue with, which in turn prompted me to write this post. It is:

"Still, it would take thousands of years to crack an 8-character password when checking both small and capital letters, spaces, and numbers. That's on a low-power computer, but the time it takes to crack a string of characters goes up exponentially the more characters you use. So again, use a long password and you can foil even the Watsons of today for long enough that you would probably decide on a whim to change your password before the password is solved."

I guess I should expect more out of them, but I was disappointed, and I want to use this blog post explaining why. If you wish to write an article about password security, regardless of the angle from which you approach it, if you don't mention entropy to your readers, you are doing them a GREAT disservice. Let me rephrase:

If you don't mention entropy in your article about passwords, you did it wrong.

If you've taken physics in secondary or undergraduate school, chances are good that you've heard about entropy. If not, you'll learn about it now. Entropy in computer science is very similar to entropy in physics. To put it straight, entropy is defined as the total combination of states that a system can be in. For example, if you have 3 cups, and 4 ping pong balls, how many ways can you arrange all 4 ping pong balls in the 3 cups? Assuming that 4 ping pong balls will fit in 1 cup, and order is not important, you can arrange the ping pong balls 12 different ways: {4,0,0},{3,1,0},{3,0,1},{2,2,0},{2,0,2},{2,1,1},{1,1,2},{1,2,1},{1,3,0},{1,0,3},{0,4,0},{0,0,4} So, this system has an entropy of 12. Entropy in physics is useful to show the Ideal Gas Law, among other things, showing the possible number of states various gases can be in, and it's useful for explaining why some things systems behave one way, but not in the reverse (such as temperature "flowing" from hot to cold, and not the reverse).

It turns out that entropy has a great deal of use in computer science. For example, on most Unix-like operating systems, there is a /dev/random and /dev/urandom device. These devices are useful for extracting random bits to build encryption keys, one-time session keys, seeds for probability outcomes, etc. These devices hold entropy. In /dev/random, for example, environmental "noise" is gathered from the user, such as mouse movements, disk usage, etc. and thrown into an entropy pool. This pool is then hashed with the SHA1 hashing algorithm to provide a total of 160-bits of entropy. Thus, when generating a 160-bit key, the data in /dev/random can be used. If more bits are needed, entropy is gathered by hashing the already hashed bits, as well as gathering additional noise from the environment, and appending to outcome until the number of bits is satisfied. The point is, /dev/random and /dev/urandom are sources of entropy.

So, what does this have to do with passwords? Your password has a certain amount of entropy. This means, that it belongs to a pool of passwords that have the same amount of entropy. The question is, though: "how do you calculate the amount of entropy in a password?" Thankfully, we don't have too think to terribly hard about this one. If you've taken college algebra, the math is pretty straight forward. Entropy in information comes from a branch of probability called "information theory". Any message contains some amount of entropy, and we can measure that entropy in binary bits. The formula for calculating this entropy is:

H = L * log_2(N)

H is the size of the message measured in binary bits. L is the length of the message- in our case, the length of your password. log_2() is the log function, base 2, and N is the number of possible symbols in the password (only lowercase letters provide 26 possible characters, uppercase provide an additional 26 possible characters, the digits provide 10 possible characters and punctuation provides 32 possible characters on an United States English keyboard). I rewrote the equation, so you could find it using your calculator:

H = L * log(N) / log(2)

Having this formula makes calculating the entropy of passwords straight forward. Here are some examples:

  • password: 38 bits (8 * log_2(26)
  • RedSox: 34 bits (6 * log_2(52))
  • B1gbRother|$alw4ysriGHt!?: 164 bits (26 * log_2(94))
  • deer2010: 41 bits (8 * log_2(36))
  • l33th4x0r: 46 bits (9 * log_2(36))
  • !Aaron08071999Keri|: 131 bits (28 * log_2(94))
  • PassWord: 46 bits (8 * log_2(52))
  • 4pRte!aii@3: 78 bits (12 * log_2(94))

Question: what gives you more entropy per bit- length or possible characters? If you passed college algebra, you would know that the answer is length, not total possible characters (if you need to think about this, graph the log function on your calculator, then graph a multiple of it). Of course, you shouldn't ignore using lowercase, uppercase, numbers and punctuation in your password, but they won't buy you as much entropy as length will. Thus, I prefer the term "passphrase" over "password", as it implies this concept to the user.

Here's a table showing the length your password must be given the possible character combinations in your password, if you want a certain entropy. Say you want an entropy of 64-bits using only numbers, it would need to be 20 characters long. If you wanted an entropy of 80 bits using characters from the entire ASCII set, it would only need to be 13 characters long.

Entropy (H) Numbers Alphabet Alphanumeric All ASCII characters
32 10 6 6 5
40 13 8 7 7
64 20 12 11 10
80 25 15 14 13
96 29 17 17 15
128 39 23 22 20
160 49 29 27 25
192 58 34 33 30
224 68 40 38 35
256 78 45 43 40
384 116 68 65 59
512 155 90 86 79
1024 309 180 172 157

So, how much entropy should you have in your password? What is considered "strong"? Well, let us look at Distributed.net. They are working on two projects: Optimal Golomb Rulers and cracking an RSA 72-bit message. Let's look at the RSA project. In January 1997, RSA Laboratories issued a secret key challenge. They generated random keys ranging from 40-bits to 128-bits. They provided the ciphertext, and a $1,000 prize to the person who find the private key that generated the message, for every message. In order to know whether or not you found the key, they gave you the first two words of the message.

Currently, as already mentioned, Distributed.net is working on the 72-bit key from that challenge. If you check the stats page, you can see that it has been running for 3,017 days as of the writing of this post, and at the current pace, it would take roughly 200,000 days to search the entire key space. Now, of course it is probable that they will find the key before exhausting the entire space, but knowing when that will be is anyone's guess. Needless to say, 200,000 days or about 540 years at the current pace is substantially large. If they kept that pace up for the 80-bit key, it would take them roughly 140,000 years to search the entire space. However, it only took them 1,726 days, or 4-and-a-half years, to find the 64-bit key, and only 193 days, or 6 months to find the 56-bit key.

So, I think that should give you a good rule of thumb to go by. 72-bits of entropy for your password seems strong enough for the short term, but it wouldn't hurt to probably increase your passwords to contain 80-bits of entropy for the long term. Of course, I don't think I need to mention not using your names, birthdates, or other silliness in your password. That's been beaten to death plenty online. Search Google for generating strong passwords, and you'll find plenty of them (all of which don't mention entropy either, I would be willing to bet).

Now, to be fair, the Ars Technica article mostly mentioned STORING your passwords, not how to create strong ones. I've already written about this before, and I think it's the perfect solution. http://passwordcard.org is the exact solution for storing strong passwords that have a good amount of entropy in them. The great thing about it too, is it does not require any software once generated. It stays with you in your wallet, so if you visit a computer that doesn't have your encrypted database, or you are not allowed to install software on the machine so you can restore your password database, the password card is the perfect fit. It's entirely platform-independent. Just pull it out of your wallet or purse, type in your password, and move on with your life. All you need to remember on the card is three things:

  1. The starting column and row of your password.
  2. The length of the password.
  3. The path your password takes on the card.

I've been using it since it first "released", and I use it for all my passwords on all my accounts, web-based, key-based or account-based. Every password is unique, they all contain more than 100-bits of entropy, and every password follows the "best rules" for creating strong passwords. I've typed many of them enough to have them memorized; I rarely pull out my card (there is also an Android and Apple application if you want).

So, next time you read an article about password strength, do a quick search for the word "entropy". If it's not mentioned, take the article in stride, or at least notify the author of this post, and that they should discuss entropy to their readers. Entropy is your friend.

The Ouroboros Card Shuffle

Introduction

For the most part, I don't play a lot of table games, and I don't play party games. But occasionally, I'll sit down with my family and play a board game or card game. When we play a card game though, I get teased by how I shuffle the deck of cards.

I know that to maximize entropy in the deck, it should be riffle shuffled at least 7 times, but a better security margin would be around 10 shuffles, and after 12, I'm just wasting my time. But I don't always riffle shuffle. I'll also do various deterministic shuffles as well, such as the pile shuffle to separate cards from each other.

I'm familiar with a number of deterministic card shuffles, which I didn't even know had names:

  • Pile shuffle- Separate the cards into piles, one at a time, until exhausted, then collect the piles. I usually just do 4 or 5 piles, and pick up in order.
  • Mongean shuffle- Move the cards from one had to the other, strictly alternating placing each discard on top then beneath the previously discarded cards.
  • Mexican spiral shuffle- Discard the top card on the table, and the second card to the bottom of the deck in your hard. Continue discarding all odd cards to the table, all even cards beneath the deck in hand until exhausted. I never do this shuffle, because it takes too long to execute.

In practice, when I'm playing a card game with my family, I'll do something like 3 riffle shuffles, a pile shuffle, 3 more riffle shuffles, a Mongean shuffle, 3 more riffle shuffles, another pile shuffle, then one last riffle shuffle. I'll get teased about it, of course: "Dad, I'm sure the cards are shuffled just fine. Can we just play now?", but when we play the game, I'll never hear complaints about how poorly the deck was shuffled.

This got me thinking though- there aren't that many simple deterministic blind card shuffles (I say "blind", because any of the playing card ciphers would work, but that requires seeing the cards, which is generally frowned upon when playing competitive card games). I wonder what else is out there. Well, doing some web searches didn't turn out much. In fact, all I could find were variations of the above shuffles, such as random pile discarding and pickup, but nothing new.

So the question then turned into- could I create my own simple deterministic card shuffle? It didn't take me long before I came up with what I call the "Ouroboros shuffle".

The Ouroboros Shuffle

Before going any further, let me state that I very much doubt I'm the first to come up with this idea, but I have searched and couldn't find where anyone else had documented it. If it does in fact exist, let me know, and I'll gladly give credit where credit is due. Until then, however, I'll stick with calling it the "Ouroboros Shuffle", named after the serpent or dragon eating its own tail.

The shuffle is simple:

  1. Holding the deck in your hard, discard the first card from the bottom of the deck to the table.
  2. Discard the top card of the deck to the discard pile on the table.
  3. Repeat steps 1 and 2, strictly alternating bottom and top cards until the deck is exhausted.

If the playing cards are plastic-based, like those from Kem or Copag, then you could "pinch" the top and bottom cards simultaneously, and pull them out of the deck in your hand to the tale. If you do this perfectly, you will pinch 2 cards only 26 times. If they're paper-based though, this may or may not work as efficiently due to cards having a tendency to stick together after heavy use.

If the deck was unshuffled as "1, 2, 3, ..., 50, 51, 52", then the first shuffle would look like this:

Step: 0
Unshuffled: 1, 2, 3, ..., 50, 51, 52
Shuffled: <none>

Step: 1
Unshuffled: 1, 2, 3, ..., 49, 50, 51
Shuffled: 52

Step: 2
Unshuffled: 2, 3, 4, ..., 49, 50, 51
Shuffled: 1, 52

Step: 3
Unshuffled: 2, 3, 4, ..., 48, 49, 50
Shuffled: 51, 1, 52

Step: 4
Unshuffled: 3, 4, 5, ..., 48, 49, 50
Shuffled: 2, 51, 1, 52

Step: 5
Unshuffled: 3, 4, 5, ..., 47, 48, 49
Shuffled: 50, 2, 51, 1, 52

Step: 6
Unshuffled: 4, 5, 6, ..., 47, 48, 49
Shuffled: 3, 50, 2, 51, 1, 52

....

Step 50:
Unshuffled: 26, 27
Shuffled: 25, 28, 24, ..., 51, 1, 52

Step 51:
Unshuffled: 26
Shuffled: 27, 25, 28, ..., 51, 1, 52

Step 52:
Unshuffled: <none>
Shuffled: 26, 27, 25, ..., 51, 1, 52

As you can see, the top and bottom cards are always paired together in the unshuffled deck, and discarded as a pair to the shuffled deck. The top and bottom cards could also be thought of as the head and tail of a list, and thus why I called it the Ouroboros shuffle.

If you execute this algorithm perfectly from an unshuffled deck, it will take 51 rounds to before restoring the deck to its unshuffled state.

Observations

Almost immediately, I noticed a bias. It doesn't matter how many times I execute this algorithm, the bottom card will always remain on the bottom. In the above example, the King of Spades (if assigned the value of "52") will stay at the bottom of the deck, due to the nature of the shuffle of discarding the bottom card first. So I recognized that I would need to cut at least 1 card from the top of the deck to the bottom of the deck before the next round of the shuffle, to ensure the bottom card gets mixed in with the rest of the deck.

Other questions started popping up, specifically:

  • How many perfect shuffles will it take to restore the deck to an unshuffled state now?
  • Is there a different bias hidden after cutting the top card to the bottom?
  • What if I cut 2 cards? 3 cards? 51 cards?

Whelp, time to code up some Python, and see what pops out. What I'm looking for is what the state of the deck looks like after each round. In other words, I want to know which card occupies which positions in the deck. For example, does the Seven of Clubs see all possible 52 positions in the deck? Without the cut, we know that's not possible, because the bottom card stubbornly stays in the bottom position.

Typing up a quick script and graphing with Gnuplot gave me the following images. The first image on the left is the Ouroboros shuffle with no cuts, where the right image is the Ouroboros shuffle followed by cutting the top card to the bottom of the deck as the end of the round. Click to enlarge.

What you're looking at is the card position in the deck along the X-axis and the card value along the Y-axis. In the left image, where the Ouroboros shuffle is executed without any following cuts, the 52nd card in the deck is always the face value of 52. But in the right image, where the Ouroboros shuffle is followed by cutting one card from the top of the unshuffled deck to the bottom, every card position sees every face value.

So what would happen if instead of cutting 1 card off the top to the bottom at the end of each round, I cut 2 cards, and cards, etc. all the way to cutting 51 cards off the top to the bottom? Well, more Python scripting, and I generated a total of 52 images showing every possible position a card occupies in the deck until the deck returns to its unshuffled state.

Visualizations of the Ouroboros card shuffle with cuts

Interestingly enough, executing the Ouroboros shuffle followed by cutting 19 cards, leads to a cycle length of 6,090 perfect shuffles before restoring the deck back to its unshuffled state. Awesome! Except, as you can see in the Imgur post above, it's extremely biased.

Every shuffle-and-cut is listed here with its cycle length:

Cut: 0, iter: 51
Cut: 1, iter: 52
Cut: 2, iter: 51
Cut: 3, iter: 272
Cut: 4, iter: 168
Cut: 5, iter: 210
Cut: 6, iter: 217
Cut: 7, iter: 52
Cut: 8, iter: 418
Cut: 9, iter: 52
Cut: 10, iter: 24
Cut: 11, iter: 350
Cut: 12, iter: 387
Cut: 13, iter: 252
Cut: 14, iter: 1020
Cut: 15, iter: 144
Cut: 16, iter: 1972
Cut: 17, iter: 34
Cut: 18, iter: 651
Cut: 19, iter: 6090
Cut: 20, iter: 175
Cut: 21, iter: 90
Cut: 22, iter: 235
Cut: 23, iter: 60
Cut: 24, iter: 2002
Cut: 25, iter: 144
Cut: 26, iter: 12
Cut: 27, iter: 50
Cut: 28, iter: 24
Cut: 29, iter: 10
Cut: 30, iter: 44
Cut: 31, iter: 72
Cut: 32, iter: 297
Cut: 33, iter: 90
Cut: 34, iter: 45
Cut: 35, iter: 132
Cut: 36, iter: 12
Cut: 37, iter: 210
Cut: 38, iter: 207
Cut: 39, iter: 104
Cut: 40, iter: 420
Cut: 41, iter: 348
Cut: 42, iter: 30
Cut: 43, iter: 198
Cut: 44, iter: 35
Cut: 45, iter: 140
Cut: 46, iter: 390
Cut: 47, iter: 246
Cut: 48, iter: 28
Cut: 49, iter: 12
Cut: 50, iter: 36
Cut: 51, iter: 30

The only "shuffle then cut" rounds that are uniform appear to be cutting 1 card, 7 cards, and 9 cards. The other 49 shuffles are biased in one way or another, even if each of them have different cycle lengths.

Here's the Python code I used to create the shuffled lists, each into their own comma-separated file:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/python

def step_1(deck):
    tmp = []
    for card in range(26):
        tmp.insert(0, deck[-1])
        deck.pop(-1)
        tmp.insert(0, deck[0])
        deck.pop(0)
    return tmp

def step_2(deck, cut):
    return deck[cut:] + deck[:cut]

orig = [_ for _ in range(1, 53)]
deck = [_ for _ in range(1, 53)]

for i in range(52):
    with open("cut_{}.csv".format(i), "w") as f:
        f.write(",".join(map(str, deck)) + "\n")
    deck = step_1(deck)
    deck = step_2(deck, i)
    n = 1
    while deck != orig:
        with open("cut_{}.csv".format(i), "a") as f:
            f.write(",".join(map(str, deck)) + "\n")
        deck = step_1(deck)
        deck = step_2(deck, i)
        n += 1
    print "Cut: {}, iter: {}".format(i, n)

Conclusion

This was a fun shuffle to play with and one that I'll incorporate into my card playing with my family. Now I could do something like: 3 riffle shuffles, Ouroboros shuffle with 1 card cut, 3 riffle shuffles, Mongean shuffle, 3 riffle shuffles, pile shuffle, 1 riffle shuffle, and I will be happy.

Getting Up To 8 Possibilities From A Single Coin Toss

Introduction

Lately, I've been interested in pulling up some classical modes of generating randomness. That is, rather than relying on a computer to generate my random numbers for me, which is all to common and easy these days, I wanted to go offline, and generate random numbers the classical way- coin flips, dice rolls, card shuffling, roulette wheels, bingo ball cages, paper shredding, etc.

In fact, if randomness interests you, I recently secured the r/RNG subreddit, where we discuss everything from random number generators, to hashing functions, to quantum mechanics and chaos to randomness extraction. I invite you to hang out with us.

Anyway, I was a bit bothered that all I could get out of a single coin toss was 2 outcomes- heads or tails. It seems like there just is no way around it. It's the most basic randomness mechanic, yet it seems so limiting. Then I came across 18th century mathematician Gearges-Louis Leclerc, Comte de Buffon, where he played a common game of placing bets on tossing a coin onto a tiled floor, and whether or not the coin landed squarely in the tile without crossing any edges, or if the coin did actually cross a tile edge.

Then it hit me- I can extract more entropy out of a coin toss by printing a grid on a piece of paper. So, I put this up on Github as a simple specification. So far, I have papers you can print that are letter, ledger, a3, or a4 sizes, and coins for United States, Canada, and the European Union.

The theory

Assume a tile has a length of "l" and is square, and assume a coin has a diameter "d" such that "d < l". In other words, the tile is larger than the coin, and there is a place on the tile where the coin can sit without crossing any edges of the tile.

This means that if the edge of the coin is tangent to the edge of the tile, then we can draw a smaller square with the center of the coin, inside our tile. This smaller square tells us that if the center of the coin lands anywhere inside of that smaller square, the edges of the coin will not cross the edges of the tile.

Image showing 4 pennies in the corners of a tile, drawing a smaller center square

Now we know the coin diameter, but we would like to know the tile edge length, so we can draw our grid on a paper to toss the coin to. As such, we need to know the ratio of the area of the tile to the area of the smaller inner square drawn by the coin.

Know that the area of the tile with length "l" is:

A(tile) = l^2

The area of the smaller square inside the tile is determined by both the tile length "l" and the coin diameter "d":

A(inner_square) = (l-d)^2

So the ratio of the two is:

P = (l-d)^2/l^2

I use "P" for our variable as this the probability of where the center of the coin lands. We want our outcomes equally likely, so we want the center of the coin to land with 50% probability inside the inner square and 50% probability outside of the inner square.

1/2 = (l-d)^2/l^2

We know the diameter of the coin, so we just need to solve for the tile edge length. This is a simple quadratic equation:

1/2 = (l-d)^2/l^2
l^2 = 2*(l-d)^2
l^2 = 2*(l^2 - 2*l*d + d^2)
l^2 = 2*l^2 - 4*l*d + 2*d^2
0 = l^2 - 4*l*d + 2*d^2

If you remember from your college or high school days, the quadratic formula solution to the quadratic equation is:

x = (-b +/- Sqrt(b^2 - 4*a*c))/(2*a)

Plugging that in, we get:

l = (-(-4*d) +/- Sqrt((4*d)^2 - 4*1*(2*d^2)))/2
l = (4*d +/- Sqrt(16*d^2-8*d^2))/2
l = (4*d +/- Sqrt(8*d^2))/2
l = (2*d +/- 2*d*Sqrt(2))/2
l = d*(2 +/- Sqrt(2))

No surprise, we have 2 solutions. So, which one is the correct one? Well, we set the restriction that "d < l" earlier, and we can't break that. So, we can clearly see that:

l = d*(2 - Sqrt(2))
l = d*(Something less than 1)
l < d

So, this equation would mean that our coin diameter "d" is larger than our tile edge "l", which doesn't mean anything to us. As such, the solution to our problem for finding the tile edge length when we know the coin diameter is:

l = d*(2 + Sqrt(2))

Getting 4 outcomes from one coin toss

Now that we have the theory knocked out, let's apply it. I know that a United States penny diameter is 1.905 centimeters. As such, my grid dege length needs to be:

l = 1.905*(2+Sqrt(2))
l ~= 6.504 centimeters

This means then that when I flip my coin onto the paper grid, there is now a 50% chance that the coin will cross a grid line and a 50% chance that it won't. But this result runs orthogonal to whether or not the coin lands on a heads or tails. As such, I have the following uniformly distributed outcomes:

  1. Tails, does not cross an edge = 00
  2. Tails, crosses any edge(s) = 01.
  3. Heads, does not cross an edge = 10.
  4. Heads, crosses any edge(s) = 11.

If we do a visual check, whenever the coin center lands in the white square of the following image, the edges of the coin will not cross the edge of the square. However, if the coin center lands in the red area, then the edge of the coin will cross an edge or edges.

Grid square showing where the coin center must lie to cross an edge.

You can measure the ratios of the area of the red to that of the white to convince yourself they're equal, although careful- my image editor didn't allow me to calculate sub-pixel measurements when building this image.

Getting 8 outcomes from one coin toss

Remarkably, rather than treat the grid as a single dimensional object (does it cross any grid edge or not), I can use the grid an an X/Y plane, and treat crossing an x-axis edge differently than crossing a y-axis edge. However, that only gives me 6 outcomes, and it is possible that the coin will land in a corner, crossing both the x-axis and y-axis simultaneously. So, I need to treat that separately.

Just like we calculated the odds of crossing an edge to be 50%, now I have 4 outcomes:

  1. Does not cross an edge.
  2. Crosses an x-axis edge only.
  3. Crosses a y-axis edge only.
  4. Crosses both the x-axis and y-axis edges (corner).

As such, each outcome needs to be equally likely, or 25%. Thus, my problem now becomes:

1/4 = (l-d)^2/l^2

Just like we solved the quadratic equation for P=50%, we will do the same here. However, I'll leave the step-by-step as an exercise for the user. Our solution becomes:

l = 2*d

Simple. The length of the grid edge must by twice the diameter of the coin. No square roots or distributed multiplication. Double the diameter of the coin, and we're good to go. However, this has a benefit and a drawback. The benefit is that the grid is more compact (2*d vs ~3.4*d). This reduces your ability to "aim" for a grid edge or not. The drawback is that you will have to make more ambiguous judgment calls on whether or not the coin crosses an edge (75% of the time vs 50% in the previous approach).

So, like the previous approach of getting 4 outcomes, we have a visual check. If the coin center lands anywhere in the white area of the following image, it won't cross an edge. If the coin center lands anywhere in the green area, the coin will cross an x-axis edge. If the coin center lands anywhere in the blue, it will cross a y-axis edge, and if the coin center lands anywhere in the red, it will cross both an x-axis and y-axis edge simultaneously.

Grid showing the areas the coin center must lie to cross an edge or corner.

As with the previous 4 outcome approach, we can convince ourselves this holds. The area of the white square should equal the are of the blue, as well as equal the area of green, as well as equal the area of the red.

This means now we have 8 uniformly distributed outcomes:

  1. Tails, does not cross an edge = 000
  2. Tails, crosses the x-axis only = 001
  3. Tails, crosses the y-axis only = 010
  4. Tails, crosses both axes (corner) = 011
  5. Heads, does not cross an edge = 100
  6. Heads, crosses the x-axis only = 101
  7. Heads, crosses the y-axis only = 110
  8. Heads, crosses both axis (corner) = 111

How do you like them apples? 8 equally likely outcomes from a single coin toss.

As mentioned, one big advantage, aside from getting 3-bits per coin toss, is the smaller grid printed on paper. You have a less opportunity to try to cheat the system, and influence the results, but you also may have a more difficult time deciding if the coin crossed a grid edge.

On the left is the paper grid used for 2-bit coin toss extraction, while the paper grid on the right is used for 3-bit coin toss extraction.

Image showing the grid sizes for a 2-bit coin toss extraction. Image showing the grid sizes for a 3-bit coin toss extraction.

Some thoughts

Both fortunately and unfortunately, the coin will bounce when it lands on the paper. If the bounce causes the coin to ounce off the paper, all you can record is a single bit, or one of two outcomes- heads or tails, because it becomes ambiguous on whether or not the coin would have crossed a grid edge, and which edge it would have crossed.

You could probably minimize the bouncing by putting the paper on something less hard than a table, such as a felt card table, a towel or rag, or even a carpeted floor. But this may also create unwanted bias in the result. For example, if the paper is placed on something too soft, such as a carpeted floor, when the coin hits the paper, it could create damage to the paper, thus possibly influencing future flips, and as a result, introducing bias into the system.

Surrounding the paper with "walls", such that the coin cannot pass the boundaries of the grid may work, but the coin bouncing off the walls will also impact the outcomes. It seems clear that the walls would need to be placed immediately against the outer edge of the grid to prevent from introducing any bias.

Additional approaches

This is hardly conclusive on extracting extra randomness from a coin flip. It is known that coins precess when flying through the air, and as part of that precess, the coin may be spinning like a wheel. Which means that the coin could be "facing north" or "facing south" in addition to heads or tails. However, it's not clear to me how much spin exists in a standard flip, and if this could be a reliable source of randomness.

Further, in our 8-outcome approach, we used the center of the coin as the basis for our extra 2 bits, in addition to heads and tails. However, we could have made the grid edge length "4d" instead of "2d", and ignored the toss if the coin crosses both edges. This means a larger grid, which could improve your chances of aiming the coin in an attempt to skew the results, and also means sticking with smaller coins, as larger coins just won't have many grids that can fit on a paper.

Other ideas could be adding color to each grid. So not only do we identify edge crossing, but use color as a third dimension to get up to 4-bits of randomness. So maybe the x-axes have alternating black and white areas, as do the y-axis, and the corners. The center of the grid could be possibly alternating red/blue quadrants. Where the center of the coin lands determines the extracted bits. Of course, this would be a visually busy, and possibly confusing paper.

None of these have been investigated, but I think each could be interesting approaches to how to extract more bits out of a coin toss.

Conclusion

I think this is a refreshing approach to an age-old problem- the coin toss. Extracting 3-bits from a single flip is extracting more entropy than a fair d6 die can produce (~2.5 bits). This means that practically speaking, the coin is more efficient at entropy extraction than dice. However, you can roll multiple dice simultaneously, where it's more difficult to toss multiple coins simultaneously.

Acknowledgments

Thanks to Dr. Markku-Juhani O. Saarinen, Marsh Ray, and JV Roig for the discussions we had on Twitter, and for helping me flush out the ideas.

Use A Good Password Generator

Introduction

Screenshot of a Google Sheets spreadsheet showing my browser password generator audit.

For the past several months now, I have been auditing password generators for the web browser in Google Sheets. It started by looking for creative ideas I could borrow or extend upon for my online password generator. Sure enough, I found some, such as using mouse movements as a source of entropy to flashy animations of rolling dice for a Diceware generator. Some were deterministic, using strong password hashing or key derivation functions, and some had very complex interfaces, allowing you to control everything from letter case to pronounceable passwords and unambiguity.

However, the deeper I got, the more I realized some were doing their generation securely and others weren't. I soon realized that I wanted to grade these online generators and sift out the good from the bad. So, I created a spreadsheet to keep track of what I was auditing, and it quickly grew from "online generators" to "password generators and passphrase generators", to "web password, web passphrase, bookmarklet, chrome extensions, and firefox extenions".

When all was said and done, I had audited 300 total generators that can be used with the browser. Some were great while some were just downright horrible. So, what did I audit, why did I choose that criteria, and how did the generators fall out?

I audited:

  • Software license
  • Server vs. client generation
  • RNG security, bias, and entropy
  • Generation type
  • Network security
  • Mobile support
  • Ads or tracker scripts
  • Subresource integrity

No doubt this is a "version 1.0" of the spreadsheet. I'm sure those in the security community will mock me for my choices of audit categories and scoring. However, I wanted to be informed of how each generator was generating the passwords, so when I made recommendations about using a password generator, I had confidence that I was making a good recommendation.

Use A Password Manager

Before I go any further, the most important advice with passwords, is to use a password manager. There are a number of reasons for this:

  • They encourage unique passwords for each account.
  • They encourage passwords with sufficient entropy to withstand offline clustered attacks.
  • They allow storage of other types of data, such as SSNs or credit card numbers.
  • Many provide online synchronization support across devices, either internally or via Dropbox and Google Drive.
  • Many ship additional application support, such as browser extensions.
  • They ship password generators.

So before you go any further, the Best Practice for passwords is "Use A Password Manager". As members of the security community, this is the advice we should be giving to our clients, whether they are family, friends, coworkers, or professional customers. But, if they are already using a password manager, and discussions arise about password generation, then this audit is to inform members of the security community which generators are "great", which generators are "good", which generators are "okay", and finally, which generators are "bad".

So to be clear, I don't expect mom, dad, and Aunt Josephine to read this spreadsheet, so they make informed decisions about which password generator to use. I do hope however that security researchers, cryptographers, auditors, security contractors, and other members of the security community to take advantage of it.

So with that said, let me explain the audit categories and scoring.

Software License

In an ethical software development community, there is value granted when software is licensed under a permissive "copyleft" license. Not necessarily GPL, but any permissive license, from the 2-clause BSD to the GPL, from the Creative Commons to unlicensed public domain software. When the software is licensed liberally, it allows developers to extend, modify, and share the code with the larger community. There are a number of different generators I found in my audit where this happened; some making great changes in the behavior of the generator, others not-so-much.

License Open Source Proprietary

So when a liberal license was explicitly specified, I awarded one point for being "Open Source" and no points for being "Proprietary" when a license either was either not explicitly specified or was licensed under a EULA or "All Rights Reserved".

This is something to note- just because the code is on a public source code repository, does not mean the code is licensed under a permissive license. United States copyright law states that unless explicitly stated, all works fall under a proprietary "All Rights Reserved" copyright to the creator. So if you didn't specify a license in your Github repository, it got labeled as "Proprietary". It's unfortunate, because I think a lot of generators missed getting awarded that point for a simple oversight.

Server vs. Client Generation

Every generator should run in the browser client without any knowledge of the generation process by a different computer, even the web server. No one should have any knowledge whatsoever of what passwords were generated in the browser. Now, I recognize that this is a bit tricky. When you visit a password generator website such as my own, you are showing a level of trust that the JavaScript delivered to your browser is what you expect, and is not logging the generated passwords back to the server. Even with TLS, unless you're checking the source code on every page refresh and disconnecting your network, you just cannot guarantee that the web server did not deliver some sort of logging script.

Generator Client Server

With that said, you still should be able to check the source code on each page refresh, and check if it's being generated in the client or on the server. I awarded one point of being a "Client" generator and no points for being a "Server" generator. Interestingly enough, I thought I would just deal with this for the website generators, and wouldn't have to worry about this with bookmarklets or browser extensions. But I was wrong. I'll expand on this more in the "Network Security" category, but suffice it to say, this is still a problem.

Generation Type

I think deterministic password generators are fundamentally flawed. Fatally so, even. Tony Arcieri wrote a beautiful blog post on this matter, and it should be internalized across the security community. The "four fatal flaws" of deterministic password generators are:

  1. Deterministic password generators cannot accommodate varying password policies without keeping state.
  2. Deterministic password generators cannot handle revocation of exposed passwords without keeping state.
  3. Deterministic password managers can’t store existing secrets.
  4. Exposure of the master password alone exposes all of your site passwords.

Number 4 in that list is the most fatal. We all know the advice that accounts should have unrelated randomized unique passwords. When one account is compromised, the exposed password does not compromise any of the other accounts. This is not the case with deterministic password generators. Every account that uses a password from a deterministic generator shares a common thread via the master secret. When that master secret is exposed, all online accounts remain fatally vulnerable to compromise.

Proponents of deterministic generators will argue that discovery of the master password of an encrypted password manager database will also expose every online account to compromise. They're not wrong, but let's consider the attack scenarios. In the password manager scenario, a first compromise needs to happen in order to get access to the encrypted database file. Then a second compromise needs to happen in discovering the master password. But with deterministic generators, only one compromise needs to take place- that is using dictionary or brute force attacks to discover the master password that led to password for the online account.

With password managers, two compromises are necessary. With determenistic generators, only one compromise is necessary. As such, the generator was awardeded a point for being "Random" and no points for being "Deterministic".

Generator Random Unknown Deterministic

RNG Security

Getting random number generation is one of those least understood concepts in software development, but ironically, developers seem to think they have a firm grasp of the basic principles. When generating passwords, never at any point should a developer choose anything but a cryptographic random number generator. I awarded one point for using a CRNG, and no points otherwise. In some cases, the generation is done on the server, so I don't know or can't verify its security, and in some cases, the code is so difficult to analyze, that I cannot determine its security that way either.

CRNG Yes Maybe Unknown No

In JavaScript, using a CRNG primarily means using the Web Crypto API via "window.crypto.genRandomValues()", or "window.msCrypto.getRandomValues()" for Microsoft-based browsers. Never should I see "Math.random()". Even though it may be cryptographically secure in Opera, it likely isn't in any of the other browsers. Some developrs shipped the Stanford JavaScript Cryptographic Library. Others shipped a JavaScript implementation of ISAAC, and others yet shipped some AES-based CSPRNG. While these are "fine", you really should consider ditching those userspace scripts in favor of just calling "window.crypto.getRandomValues()". It's less software the user has to download, and as a developer, you are less likely to introduce a vulnerability.

Also, RC4 is not a CSPRNG, neither is ChaCha20, SHA-256, or any other hash function, stream cipher, or block cipher. So if you were using some JavaScript library that is using a vanilla hashing function, stream cipher, or block cipher as your RNG, then I did not consider it as secure generation. The reason being, is that even though ChaCha20 or SHA-256 may be prediction resistant, it is not backtracking resistant. To be a CRNG, the generator must be both prediction and backtracking resistant.

However, in deterministic password generators that are based on a master password, the "RNG" (using this term loosely here) should be a dedicated password hashing function or password-based key derivation function with an appropriate cost. This really means using only:

  • sha256crypt or sha512crypt with at least 5,000 rounds.
  • PBKDF2 with at least 1,000 rounds.
  • bcrypt with a cost of at least 5.
  • scrypt with a cost of at least 16 MiB of RAM and at least 0.5s execution.
  • Argon2 with sufficient cost of RAM and execution time.

Anything else, like hashing the master password or mouse entropy with MD5, SHA-1, SHA-2, or even SHA-3 will not suffice. The goal of those dedicated password generators or key derivation functions is to slow down an offline attempt at discovering the password. Likely the master password does not contain sufficient entropy, so it remains the weakest link in the generation process. By using a dedicated password hashing or key derivation function with an appropriate cost, we can guarantee a certain "speed limit" with offline clustered password attacks, making it difficult to reconstruct the password.

RNG Uniformity

Even though the developer may have chosen a CRNG, they may not be using the generator uniformly. This is probably the most difficult aspect of random number generation to grasp. It seems harmless enough to call "Math.floor(Math.random() * length)" or "window.crypto.getRandomValues(new UInt32Array(1))[0] % length". In both cases, unless "length" is a power of 2, the generator is biased. I awarded one point for being an unbiased generator, and zero points otherwise.

Uniform Yes Maybe Unknown No

To do random number generation in an unbiased manner, you need to find how many times the length divides the period of the generator, and note the remainder. For example, if using "window.crypto.getRandomValues(new UInt32Array(1))", then the generator has a period of 32-bits. If your length is "7,776", is in the case of Diceware, then 7,776 divides 232 552,336 times with a remainder of 2,560. This means that 7,776 divides values 0 through 232-2,561 evenly. So if your random number is between the range of 232-2,560 through 232-1, the value needs to be tossed out, and a new number generated.

Oddly enough, you could use a an insecure CRNG, such as SHA-256, but truncate the digest to a certain length. While the generator is not secure, the generator in this case is unbiased. More often than not actually, deterministic generators seem to fall in this category, where a poor hashing function was chosen, but the digest was truncated.

RNG Entropy

I've blogged about this a number of times, so I won't repeat myself here. Search by blog for password entropy, and get caught up with the details. I awarded one point for generators with at least 70 bits of entropy, 0.5 points for 55 through 69 bits of entropy, and no points for entropy less than 55 bits.

Entropy 70 69 55 54

I will mention however that I chose the default value that was presented to me when generating the password. Worse, if I was forced to chose my length, and I could chose a password of one character, then I awarded it as such. When you're presenting password generators to people like Aunt Josephine, they'll do anything they can do get away with as little as possible. History has shown this is 6-8 characters in length. This shouldn't be possible. A few Nvidia GTX960 GPUs can crack every 8 character ASCII password hashed with SHA-1 in under a week. There is no reason why the password generator should not present minimum defaults that are outside the scope of practical hobbyist brute force searching.

So while that may be harsh, if you developed one of the generators in my audit, and you were dinged for this- I'm calling you out. Stop it.

Network Security

When delivering the software for the password generation, it's critical that the software is delivered over TLS. There should be no room for a man-in-the-middle to inject malicious code to discover what passwords your generating, send you a determined list passwords, or any other sort of compromise. This means, however, that I expect a green lock in the browser's address or status bars. The certificate should not be self-signed, it should not be expired, it should not be missing intermediate certificates, it should not be generated for a different CN, or any other certificate problems. Further, the site should be HTTPS by default.

HTTPS Yes Not Default Expired No

I awarded one point for "Yes", serving the software over secure and problem-free HTTPS, and zero points otherwise.

Mobile View Support

For the most part, due to their ubiquity, developers are designing websites that support mobile devices with smaller screens and touch interfaces. It's as simple as adding a viewport in the HTML header, and as complex as customized CSS and JavaScript rules for screen widths, user agents, and other tests. Ultimately, when I'm recommending a password generator to Aunt Josephine while she's using her mobile phone, she shouldn't have to pinch-zoom, scroll, and other nuisances when generating and copying the password. As silly as that may sound, if the site doesn't support a mobile interface, then it wasn't awarded a point.

Mobile Yes No

Ads and Tracker Scripts

Screenshot showing the Lightbeam extension for Firefox after several days of use.

I get it. I know that as a developer, you want easy access to analytics about who is visiting your site. Having that data can help you learn what is driving traffic to your site, and how you can make adjustments as necessary to improve that traffic. But when it comes to password generators, no one other than me and the server that sent the code to my browser, should know that I'm about to generate passwords. I awarded a point for not shipping trackers, and zero points if the generator did.

Trackers No Yes

Google Analytics, social media scripts, ads, and other 3rd party browser scripts track me via fingerprinting, cookies, and other methods to learn more about who I am and what I visited. If you want to see how extensive this is, install the Lightbeam extension for Firefox. This shows the capability of companies to share data and learn more about who you are and where you've been on the web. Recently, Cambridge Analytica, a small unknown company, was able to mine data on millions of Facebook users, and the data mining exposed just how easy it was for Facebook to track your web behavior even when not on the site.

At first, I thought this would be just something with website generators, but when I started auditing browser extensions, I quickly saw that developers were shipping Google Analytics, and other tracking scripts in the bundled extension as well.

Offline

When I started auditing the bookmarklets and extensions, I pulled up my developer console, and watched for any network activity when generating the passwords or using the software. To my dismay, some do "call home" by either wrapping the generator around an <iframe> or requiring an account, such as in the case with password managers. I awarded one point for staying completely offline, zero points for any sort of network activity.

Offline Yes No

Now, you may be thinking that this isn't exactly fair for password generators or just <iframe>s, but the generation is still happening client-side and without trackers. For the most part, I agree, except, when installing browser extensions, the developer has the opportunity to make the password generation fully offline. That may sound a touch silly for a browser extension, but regardless, it removes the risk of a web server administrator from modifying the delivered JavaScript on every page load. The only times the JavaScript would be changed, is when the extension is updated. This behaves more like standard desktop software.

Subresource Integrity

Finally, the last category I audited was subresource integrity. SRI is this idea that a developer can add cryptographic integrity to <link> and <script< resources. The reason the W3C gives for the motivation of SRI is:

"Compromise of a third-party service should not automatically mean compromise of every site which includes its scripts. Content authors will have a mechanism by which they can specify expectations for content they load, meaning for example that they could load a specific script, and not any script that happens to have a particular URL."

So SRI guarantees that even though the data is delivered under TLS, if the cryptographic hashes are valid, then the data has not been compromised, even if the server has. More information about SRI can be found at the W3C Github page, and I encourage everyone to check out the links there.

I awarded one point if "Yes" or "N/A" (no resources called), and zero points for "No".

SRI Yes N/A No

Scoring

With all these audit categories taken into account, I gave a total score to see how generators ranked among others. Each generator has different auditing criteria, so the score varies from generator type to generator type. I treated the scoring like grade school- 100% is an "A", 99% to roughly 85% as "great", 84% to 51% is "okay", and 50% or less is failing. I translated that grade school score into the following:

Score Perfect Perfect - 1 Perfect - 2 51% 50%

When you look at the spreadsheet, you'll see that it is sorted first by score in descending order then alphabetically by "Name" in ascending order. It's sorted this way, so as a security consultant, you can quickly get a high-level overview of the "good" versus the "bad", and you should be able to find the generator you're looking for quickly. The names are just generic unique identifiers, and sometimes there are notes accompanying each generator when I found odd behavior, interesting generation templates, or other things that stood out.

Conclusion

This audit is for the security community, not for Aunt Josephine and friends or family. I don't expect you to share this with your dad or your spouse or your Facebook friends, and expect them to know what they're looking at, or why they should care. However, I recently took a poll on Twitter, asking the security community if they recommended password generators to family and friends. Only 90 votes came in, but 69% of you said that you did, with a few comments coming in saying that they would only recommend them if they shipped with a password manager (see the beginning of this post). I suspect that some of the 31% of the "No" votes are in this category.

Screenshot of a Twitter poll I took asking if people recommend password generators. 69% said yes, 31% said no.

So, of those 69% of you that said "Yes", I hope this audit will be of some value.

Password Best Practices I - The Generator

This is the first in a series of posts about password best practices. The series will cover best practices from a few different angles- the generator targeted at developers creating those generators, the end user (you, mom, dad, etc.) as you select passwords for accounts from those generators, and the service provider storing passwords in the database for accounts that your users are signing up for.

Motivation

When end users are looking for passwords, they may turn to password generators, whether they be browser extensions, websites, or offline installable executables. Regardless, as a developer, you will need to ensure that the passwords you your providing for your users are secure. Unfortunately, that's a bit of a buzzword, and can be highly subjective. So, we'll motivate what it means to be "secure" here:

  • The generator is downloaded via HTTPS, whether it's a website, executable ZIP, or browser extension.
  • The generator uses a cryptographically secure random number generator.
  • The generator provides at least 70-bits of entropy behind the password.
  • The generator is open source.
  • The generator generates passwords client-side, not server-side.
  • The generator does not serve any ads or client-side tracking software.

I think most of us can agree on these points- the software should be downloaded over HTTPS to mitigate man-in-the-middle attacks. A cryptographically secure RNG should be used to ensure unpredictability in the generated password. In addition to that, the CRNG should also be uniformly distributed across the set, so no elements of the password are more likely to appear than any other. Creating an open source password generator ensures that the software can be audited for correctness and instills trust in the application. Generating passwords client-side, means the server hos now possible way of knowing what passwords were generated, unless the client is also calling home (the code should be inspected). And of course, we don't want any adware or malware installed in the password generating application to further compromise the security of the generator.

Okay. That's all well and good, but what about this claim to generate passwords from at least 70-bits in entropy? Let's dig into that.

Brute force password cracking

Password cracking is all about reducing possibilities. Professional password crackers will have access to extensive word lists of previously compromised password databases, they'll have access to a great amount of hardware to rip through the password space, and they'll employ clever tricks in the password cracking software, such as Hashcat or MDXFind, to further reduce the search space, to make finding the passwords more likely. In practice, 90% of leaked hashed password databases are reversed trivially. With the remaining 10%, half of that space takes some time to find, but those passwords are usually recovered. The remaining few, maybe 3%-5%, contain enough entropy that the password cracking team likely won't recover those passwords in a week, or a month, or even a year.

So the question is this- what is that minimum entropy value that thwarts password crackers? To answer this question, let's look at some real-life brute force searching to see if we can get a good handle on the absolute minimum security margin necessary to keep your client's leaked password hash out of reach.

Bitcoin mining

Bitcoin mining is the modern-day version of the 1849 California Gold Rush. As of right now, Bitcoin is trading at $3,665.17 per BTC. As such, people are fighting over each other to get in on the action, purchasing specialized mining hardware, called "Bitcoin ASICs", to find those Bitcoins as quickly as possible. These ASICs are hashing blocks of data with SHA-256, and checking a specific difficulty criteria to see if it meets the requirements as a valid Bitcoin block. If so, the miner that found that block is rewarded that Bitcoin and it's recorded in the never-ending, ever-expanding, non-scalable blockchain.

How many SHA-256 hashes is the word at large calculating? As of this writing, the current rate is 7,751,843.02 TH/s, which is 7,751,843,020,000,000,000 SHA-256 hashes per second. At one point, it peaked at 8,715,000 THps, and there is no doubt in my mind that it will pass 10,000,000 THps before the end of the year. So let's run with that value, of 10,000,000,000,000,000,000 SHA-256 hashes per second, or 1019 SHA-256 hashes per second.

If we're going to talk about that in terms of bits, we need to convert it to a base-2 number, rather than base-10. Thankfully, this is easy enough. All we need to calculate is the log2(X) = log(X)/log(2). Doing some math, we see that Bitcoin mining is roughly flipping every combination of bits in a:

  • 63-bit number every second.
  • 69-bit number every minute.
  • 74-bit number every hour.
  • 79-bit number every day.
  • 84-bit number every month.
  • 88-bit number every year.

What does this look like? Well, the line is nearly flat. Here in this image, the x-axis is the number of days spent mining for Bitcoin, starting from 0 through a full year of 365 days. The y-axis is the search space exhaustion in bits. So, you can see that in roughly 45 days, Bitcoin mining have calculated enough SHA-256 hashes to completely exhaust an 85-bit search space (click to enlarge):

Plot showing log(x*10^19*86400)/log(2) for Bitcoin mining.

Real-world password cracking

That's all fine and dandy, but I doubt professional password crackers have access to that sort of hardware. Instead, let's look at a more realistic example.

Recently, Australian security researcher Troy Hunt, the guy that runs https://haveibeenpwned.com/, released a ZIP of 320 million SHA-1 hashed passwords that he's collected over the years. Because the passwords were hashed with SHA-1, recovering them should be like shooting fish in a barrel. Sure enough, a team of password crackers got together, and made mincemeat of the dataset.

In the article, it is mentioned that they had a peak password cracking speed of 180 GHps, or 180,000,000,000 SHA-1 hashes per second, or 18*1010 SHA-1 hashes per second. The article mentions that's the equivalent of 25 NVidia GTX1080 GPUs working in concert. To compare this to Bitcoin mining, the team was flipping every combination of bits in a:

  • 41-bit number every second.
  • 47-bit number every minute.
  • 53-bit number every hour.
  • 58-bit number every day.
  • 63-bit number every month.
  • 66-bit number every year.

As we can see, this is a far cry from the strength of Bitcoin mining. But, are those numbers larger than you expected? Let's see how it looks on the graph, compared to Bitcoin (click to enlarge):

Plot showing log(x*18*10^10*86400)/log(2) for this cluster of password cracking hobbyists.

So, it seems clear that our security margin is somewhere above that line. Let's look at one more example, a theoretical one.

Theoretical password cracking by Edward Snowden

Before Edward Snowden became known to the world as Edward Snowden, he was known to Laura Poitras as "Citizenfour". In emails back-and-forth between Laura and himself, he told her (emphasis mine):

"Please confirm that no one has ever had a copy of your private key and that it uses a strong passphrase. Assume your adversary is capable of one trillion guesses per second. If the device you store the private key and enter your passphrase on has been hacked, it is trivial to decrypt our communications."

But one trillion guesses per second is only about 5x the collective power of our previous example of a small team of password cracking hobbyists. That's only about 125 NVidia GTX1080 GPUs. Certainly interested adversaries would have more money on hand to invest in more computing power than that. So, let's increase the rate to 10 trillion guesses per second. 1,250 NVidia GTX1080 GPUs would cost our adversary maybe $500,000. A serious investment, but possibly justifiable, and certainly not outside the $10 billion annual budget of the NSA. So let's roll with it.

At 1013 password hashes per second, we are flipping every combination of bits in a:

  • 43-bits every second.
  • 49-bits every minute.
  • 54-bits every hour.
  • 59-bits every day.
  • 64-bits every month.
  • 68-bits every year.

Plotting this on our chart with both Bitcoin mining and clustered hobbyist password cracking, we see (click to enlarge):

Plot of log(x*86400*10^13)/log(2)

The takeaway

What does all this math imply? That as a developer of password generator software, you should be targeting a minimum of 70-bits of entropy with your password generator. This will give your users the necessary security margins to steer clear of well-funded adversaries, should some service provider's password database get leaked to the Internet, and they find themselves as a target.

As a general rule of thumb, for password generator developers, these are the sort of security margins your can expect with entropy:

  • 70-bits or more: Very secure.
  • 65-69 bits: Moderately secure.
  • 60-64 bits: Weakly secure.
  • 59 bits or less: Not secure.

Colored recommendation of the previous plot showing all brute force attempts.

What does this mean for your generator then? This means that the number of size of the password or passphrase that you are giving users should be at least:

  • Base-94: 70/log2(94)=11 characters
  • Base-64: 70/log2(64)=12 characters
  • Base-32: 70/log2(32)=14 characters
  • Base-16: 70/log2(16)=18 characters
  • Base-10: 70/log2(10)=22 characters
  • Diceware: 70/log2(7776)=6 words

Now, there is certainly nothing wrong with generating 80-bit, 90-bit, or even 128-bit entropy. The only thing you should consider with this, is the size of the resulting password and passphrases. For example, if you were providing a minimum of 128-bit security for your users with the password generator, then things would look like:

  • Base-94: 128/log2(94)=20 characters
  • Base-64: 128/log2(64)=22 characters
  • Base-32: 128/log2(32)=26 characters
  • Base-16: 128/log2(16)=32 characters
  • Base-10: 128/log2(10)=39 characters
  • Diceware: 128/log2(7776)=10 words

As you can see, as you increase the security for your users, the size of the generated passwords and passphrases will also increase.

Conclusion

It's critical that we are doing right by our users when it comes to security. I know Randall Munroe of XKCD fame created the "correct horse battery staple" comic, advising everyone to create 4-word passphrases. This is fine, provided that those 4 words meets that minimum 70-bits of entropy. In order for that to happen though, the word list needs to be:

   4 = 70/log2(x)
=> 4 = 70/log(x)/log(2)
=> 4 = 70*log(2)/log(x)
=> 4*log(x) = 70*log(2)
=> log(x) = 70/4*log(2)
=> x = 1070/4*log(2)
=> x ~= 185,364

You would need a word list of at least 185,364 words to provide at least 17.5-bits of entropy per word, which brings us to required 70-bits of total entropy for 4 words. All too often, I see generators providing four words, but the word list is far too small, like around Diceware size, which is only around 51-bits of entropy. As we just concluded, that's not providing the necessary security for our users.

So, developers, when creating password and passphrase generators, make sure they are at least targeting the necessary 70-bits of entropy, in addition to the other qualifications that we outlined at the beginning of this post.

Colorful Passphrases

Since the development of my passphrase and password generator, I started working toward improving the other online generators out there on the web. I created a Google Spreadsheet to work toward that goal, by doing reasonable audits to "rank" each generator, and see how they stacked up against the rest. Then, I started submitting patches in hopes of making things better.

One passphrase generator that was brought to my attention was Pass Plum. Pass Plum supplies an example word list to use for generating your passphrases, if you choose to install the software on your own server. Unfortunately, the list is only 140 words in size, so if you choose to use that for your word list, then you only get about 7.13-bits of entropy per word. Sticking to the default configuration 4 words given to the user, that's a scant 28-bits of security on your passphrase, which is trivially reversed. I submitted a pull request to extend it to 4,096 words, providing exactly 13-bits of entropy per word, or about 52-bits of entropy for a 4-word passphrase- a significant improvement.

I noticed, however, that the default list was nothing but color names, and that got me thinking- what if not only the generator provided color names for passphrases, but also colored the word that color name? Basically, a sort of false visual synesthesia. What I want to know is this, is it easier to remember passphrases when you can associate each word with a visual color?

So, over the past several nights, and during weekends, I've been putting this together. So, here is is- colorful passphrases.

Collage of 4 separate screenshots of what the color passphrase generator looks like.

Head over to my site to check it out. If a color is too light (its luma value is very high), then the word is outlined with CSS. Every word is bold, to make the word even more visible on the default white background.

As I mentioned, the idea is simple: people struggle remembering random meaningless strings of characters for passwords, so passphrases are a way to make a random series of words easier to recall. After all, it should be easier to remember "gnu hush gut modem scamp giddy" than it is to remember "$5hKXuE[\NK". It's certainly easier to type on mobile devices, and embedded devices without keyboards, like smart TVs and video game consoles.

But, even then, there is nothing that is really tying "gnu hush gut modem scamp giddy" together, so you force yourself in some sort of mnemonic to recall it. Visually stimulated color passphrases have the benefit of not only using a mnemonic to recall the phrase, but an order of colors as well. For example, you might not recall "RedRobin Pumpkin Revolver DeepPuce Lucky Crail TealDeer", but you may remember its color order of roughly "red orange black purple gold brown teal". "A RedRobin is red. A pumpkin is orange. A revolver (gun) is black. DeepPuce is a purple. Lucky coins are gold. Crail, Soctand has brown dirt. TealDeer are teal."

However, it also comes with a set of problems. First, what happens if you actually have visual synesthesia? Will seeing these colors conflict with your mental image of what the color should be for that word? Second, many of the words are very obscure, such as "Crail" or "Tussock" or "Tuatara" (as all seen in the previous screenshot collage). Finally, what happens when you have a color passphrase where two similar colors are adjacent to each other? Something like "Veronica Affair Pipi DeepOak Atoll BarnRed RedOxide"? Both "BarnRed" and "RedOxide" are a deep reddish color. Will it be more difficult to recall which comes first?

A screenshot showing a color collision between "BarnRed" and "RexOxide"

As someone who is interested in password research, I wanted to see what sort of memory potential visually colorful passphrases could have. As far as I know, this has never been investigated before (at least I could find any research done in this area, and I can't find any passphrase generators doing it). This post from Wired investigates alternatives to text entry for password support, such as using color wheels, but doesn't say anything about visual text. Here is a browser extension that colors password form fields on websites, with the SHA-1 hash of your password as you type it. You know if it's correct, by recognizing if the pattern is the same it always is when logging in.

Long story short, I think I'm wading into unknown territory here. If you find this useful, or even if you don't, I would be very interested in your feedback.

A Practical and Secure Password and Passphrase Generator

The TL;DR

Go to https://ae7.st/g/ and check out my new comprehensive password and passphrase generator. Screenshots and longer explanation below.

Introduction

Sometime during the middle of last summer, I started thinking about password generators. The reason for this, was that I noticed a few things when I used different password generators, online or offline:

  1. The generator created random meaningless strings.
  2. The generator created XKCD-style passphrases.
  3. The generator gave the user knobs and buttons galore to control
    • Uppercase characters
    • Lowercase characters
    • Digits
    • Nonalphanumeric characters
    • Pronounceable passwords
    • Removing ambiguous characters
    • Password Length

The Problem

Here is just one example of what I'm talking about:

Screenshot showing a "secure" password generator from a website.

This password generator has a lot of options for tweaking your final password.

Ever since Randal Munroe published https://xkcd.com/936/, people started creating "XKCD-style" passphrase generators. Here's a very simple one that creates a four-word passphrase. No knobs, bells, or whistles. Just a button to generate a new XKCD passphrase. Ironically, the author provides an XKCD passphrase generator for you to use, then tells you not to use it. 🙂

On the other hand, why not make the XKCD password generation as complex as possible? Here at https://xkpasswd.net/s/, not only do you have an XKCD password generator, but you have all the bells, whistles, knobs, buttons, and control to make it as ultimately complex as possible. Kudos to the generator even make entropy estimates about the generated passwords!

Screenshot showing a very complex control board of an XKCD style password generator.

Why not add all the complexity of password generation to XKCD passwords?

What bothers me about the "XKCD password" crowd, however, is that no one knows that Diceware was realized back in 1995, making passphrases commonplace. Arnold Reinhold created a list of 7,776 words, enough for every combination of a 6-sided die rolled 5 times. Arnold explains that the passphrase needs to be chosen from a true random number generator (thus the dice) and as a result each word in the list will have approximately 12.9-bits of entropy. Arnold recommends throwing the dice enough times to create a five-word Diceware passphrase. That would provide about 64-bits of entropy, a modestly secure result.

A five-word Diceware passphrase could be:

  • soot laid tiger rilly feud pd
  • 31 al alibi chick retch bella
  • woven error rove pliny dewey quo

My Solution

While these password generators are all unique, and interesting, and maybe even secure, it boils down to the fact that my wife, never mind my mom or grandma, isn't going to use them. They're just too complex. But worse, they give the person using them a false sense of security, and in most cases, they're not secure at all. I've talked with my wife, family, and friends about what it requires to have a strong password, and I've asked them to give me examples. You can probably guess what I got.

  • Spouse's first name with number followed by special character. EG: "Alan3!"
  • Favorite sports team in CamelCase. EG: "UtahUtes"
  • Keyboard patterns. EG: "qwertyasdf"

The pain goes on and on. Usually, the lengths of each password is somewhere around 6-7 characters. However, when you start talking about some of these generators, and they see passwords like "(5C10#+b" or "V#4I5'4c", their response is usually "I'm never going to remember that!". Of course, this is a point of discussion about password managers, but I'll save that for another post.

So I wanted to create a password and passphrase generator that met everyone's needs:

  • Simplicity of use
  • Length and complexity
  • Provably secure
  • Desktop and mobile friendly

If you've been a subscriber to my blog, you'll know that I post a lot about Shannon entropy. Entropy is maximized when a uniform unbiased random function controls the output. Shannon entropy is just a fancy way for estimating the total number of possibilities something could be, and it's measured in bits. So, when I say a Diceware passphrase as approximately 64-bits of entropy, I'm saying that the passphrase that was generated is 1 in 2^64 or 18,446,744,073,709,551,616 possibilities. Again, this is only true if the random function is uniform and unbiased.

So, I built a password generator around entropy, and entropy only. The question became, what should the range be, and what's my threat model? I decided to build my threat model after offline brute force password cracking. A single computer with a few modest GPUs can work through every 8-character password built from all 94 graphical characters on the ASCII keyboard hashed with SHA-1 in about a week. That's 94^8 or 6,095,689,385,410,816 total possibilities. If chosen randomly, Shannon entropy places any password built from that set at about 52-bits. If the password chosen randomly from the same set of 94 graphical characters was 9 characters long, then the password would have about 59-bits of Shannon entropy. This would also take that same GPU password cracking machine 94 weeks to fully exhaust every possibility.

This seemed like a good place to start the range. So, for simplicity sake, I started the entropy range at 55-bits, then incremented by 5 bits until the maximum of 80-bits. As you can see from the screenshot of the entropy toolbar, 55-bits is red as we are in dangerous territory of an offline password cracker with maybe a cluster of GPUs finding the password. But things get exponentially expensive very quickly. Thus, 60-bits is orange, 65-bits is yellow, and 70-bits and above are green. Notice that the default selection is 70-bits.

Screenshot showing the entropy toolbar of my password generator.

The entropy toolbar of my password generator, with 70-bits as the default.

When creating the generator, I realized that some sites will have length restrictions on your password, such as not allowing more than 12 characters, or not allowing certain special characters, or forcing at least one uppercase character and one digit, and so forth. Some service providers, like Google, will allow you any length with any complexity. But further, people remember things differently. Some people don't need to recall the passwords, as they are using password managers on all their devices, with a synced database, and can just copy/paste. Others want to remember the password, and others yet want it easy to type.

So, it seemed to me that not only could I build a password generator, but also a passphrase generator. However, I wanted this to be portable, so rather than create a server-side application, I made a client-side one. This does mean that you download the wordlists as you need them to generate the passphrases, and the wordlists are anything but light. However, you only download them as you need them, rather than downloading all on page load.

To maximize Shannon entropy, I am using the cryptographically secure pseudorandom number generator from the Stanford Javascript Crypto Library. I'm using this, rather than the web crypto API, because I use some fairly obscure browsers, that don't support it. It's only another 11KB download, which I think is acceptable. SJCL does use the web crypto API to seed its generator, if the browser supports it. If not, a entropy collector listener event is launched, gathering entropy from mouse movements. The end result, is that Shannon entropy is maximized.

Passphrases

There are 5-types of passphrases in my generator:

  • Alternate
  • Bitcoin
  • Diceware
  • EFF
  • Pseudowords

Diceware

For the Diceware generator, I support all the languages that you'll find on the main Diceware page, in addition to the Beale word list. As of this writing, that's Basque, Bulgarian, Catalan, Chinese, Czech, Danish, Dutch, English, Esperanto, Finnish, French, German, Italian, Japanese (Romaji), Maori, Norwegian, Polish, Portuguese, Russian, Slovenian, Spanish, Swedish, and Turkish. There are 7,776 words in each word list, providing about 12.9248-bits of entropy per word.

EFF

For the EFF generator, I support the three word lists that the EFF has created- the short word list, the long word list, and the "distant" word list, where every work has an edit distance of at least three from the others in the list. The long list is similar to the Diceware list, in that it is 7,776 words providing about 12.9248-bits of entropy per word. However, the number of characters in each word in the word list are longer on average, at around 7 characters per word than the Diceware word list, at around 4.3 characters per word. So, for the same entropy estimate, you'll have a longer EFF passphrase than a Diceware passphrase. The short word list contains only 1,296 words, to be used with 4 dice, instead of 5, and the maximum character length of any word is 5 characters. The short word list provides about 10.3399-bits of entropy per word. Finally, the "distant" word list is short in number of words also at 1,296 words, but longer in character count, averaging 7 characters per word.

Bitcoin

For the Bitcoin generator, I am using the BIP-0039 word lists to create the passphrase. These lists are designed to be a mnemonic code or sentence for generating deterministic Bitcoin wallets. However, because they are a list of words, they can be used for building passphrases too. Each list is 2,048 words, providing exactly 11-bits of entropy per word. Like Diceware, I support all the languages of the BIP-0039 proposal, which as of this writing includes Simplified Chinese, Traditional Chinese, English, French, Italian, Japanese (Hiragana), Korean (Hangul), and Spanish.

Alternate

Elvish

In the Alternate generator, I have a few options that provide various strengths and weaknesses. The Elvish word list is for entertainment value only. The word list consists of 7,776 words, making it suitable for Diceware, and provides about 12.9248-bits of entropy per word. However, because the generator is strictly electronic, and I haven't assigned dice roll values to each word, I may bump this up to 8,192 words providing exactly 13-bits of entropy per word. The word list was built from the Eldamo lexicon.

Klingon

Another passphrase generator for entertainment value is the Klingon generator. This word list comes from the Klingon Pocket Dictionary, and my word list provides exactly 2,604 unique words from the 3,028 words in the Klingon language. Thus, each word provides about 11.3465-bits of entropy.

PGP

The PGP word list was created to make reading hexadecimal strings easier to speak and phonetically unambiguous. It comprises of exactly 256 words providing exactly 8-bits of entropy per word. This generator works well in noisy environments, such as server rooms, where passwords need to be spoken from one person to another to enter into a physical terminal.

Simpsons

The Simpson's passphrase generator consists of 5,000 words, providing about 12.2877-bits of entropy per word. The goal of this generator is not only educational to show that any source of words can be used for a password generator, such as a television series of episodes, but also more memorable. Because this list contains the most commonly spoken 5,000 words from the Simpson's episodes, a good balance of verbs, nouns, adjectives, etc. are supplied. As such, the generated passphrases seem to be easier to read, and less noun-heavy than the Diceware or EFF word lists. These passphrases may just be the easiest to recall, aside from the Trump word list.

Trump

And now my personal favorite. The Trump generator was initially built for entertainment purposes, but ended up having the advantage of providing a good balanced passphrase of nouns, verbs, adjectives, etc. much like the Simpson's generator. As such, these passphrases may be easier to recall, because they are more likely to read as valid sentences than the Diceware or EFF generators. This list is pulled from Donald J. Trump's Twitter account. The list is always growing, currently at 5,343 words providing about 12.3404-bits of entropy per word.

Pseudowords

The pseudowords generator is a cross between unreadable/unpronounceable random strings and memorable passphrases. They are pronounceable, even if the words themselves are gibberish. They are generally shorter in practice than passphrases, and longer than pure random strings. The generators are here to show what you can do with random pronounceable strings.

Bubble Babble

Bubble Babble is a hexadecimal encoder, with builtin checksumming, initially created Antti Huima, and implemented in the original proprietary SSH tool (not the one by the OpenSSH developers). Part of the specification is that every encoded string begins and ends with "x". However, rather than encode data from the RNG, it is randomly generating 5-characters words in the syntax of "". As such, each 5-character word, except for the end points, provides 21521521=231,525 unique combinations, or about 17.8208-bits of entropy. The end points are in the syntax of "x" or "x, which is about 21521*5=11,025 unique combinations, or about 13.4285-bits of entropy.

Secret Ninja

This generator comes from a static character-to-string assignment that produces pronounceable Asian-styled words. As such, there are only 26 assignments, providing about 4.7004-bits of entropy per string. There are three strings concatenated together per hyphenated word.

Cosby Bebop

I was watching this YouTube video with Bill Cosby and Stewie from Family Guy, and about half-way through the skit, Bill Cosby starts using made-up words as part of his routine. I've seen other skits by comedians where they use made-up words to characterize Bill Cosby, so I figured I would create a list of these words, and see how they fell out. There are 32 unique words, providing exactly 5-bits of entropy per word. Unlike the Bubble Babble and Secret Ninja generators, this generator uses both uppercase and lowercase Latin characters.

Korean K-pop

In following with the Bill Cosby Bebop generator, I created a Korean "K-pop" generator that used the 64-most common male and female Korean names, providing exactly 6-bits of entropy per name. I got the list of names from various sites listing common male and female Korean names.

Random

These are random strings provided as a last resort for sites or accounting software that have very restrictive password requirements. These passwords will be some of the shortest generated while meeting the same minimum entropy requirement. Because these passwords are not memorable, they should be absolutely stored in a password manager (you should be using one anyway).

  • Base-94: Uses all graphical U.S. ASCII characters (does not include horizontal space). Each character provides about 6.5546-bits of entropy. This password will contain ambiguous characters.
  • Base-64- Uses all digits, lowercase and uppercase Latin characters, and the "+" and "/". Each character provides exactly 6-bits of entropy. This password will contain ambiguous characters.
  • Base-32: Uses the characters defined in RFC 4648, which strives to use an unambiguous character set. Each character provides exactly 5-bits of entropy.
  • Base-16: Uses all digits and lowercase characters "a" through "f". Each character provides exactly 4-bits of entropy. This password will contain fully unambiguous characters.
  • Base-10: Uses strictly the digits "0" through "9". This is mostly useful for PINs or other applications where only digits are required. Each digits provides about 3.3219-bits of entropy. This password will contain fully unambiguous characters.
  • Emoji: There are 881 emoji glyphs provided by that font, yielding about 9.7830-bits per glyph. One side-effect, is that even though there is a character count in the generator box, each glyph may be more than 1 byte, so some input forms may count that glyph as more than 1 character. Regardless, the minimum entropy is met, so the emoji password is still secure.

I want to say something a bit extra about the Emoji generator. With the rise of Unicode and the UTF-8 standard, and the near ubiquitous popularity of smartphones and mobile devices, having access to non-Latin character sets is becoming easier and easier. As such, password forms are more likely supporting UTF-8 on input to allow Cyrillic, Coptic, Arabic, and East Asian ideographs. So, if Unicode is vastly becoming the norm, why not take advantage of it while having a little fun?

I opted for the black-and-white font, as opposed to the color font, to stay consistent with the look and feel of the other generators. This generator uses the emoji character sets provided by Google's Noto Emoji fonts, as that makes it easy for me to support the font in CSS 3, allowing every browser that supports CSS 3 to take advantage of the font and render the glyphs in a standard fashion. The license is also open so that I can redistribute the font without paying royalties, and others can do the same.

Screenshots

The post wouldn't be complete without some screenshots. The generator is both desktop friendly, fitting comfortably in a 1280x800 screen resolution, as well a mobile friendly, working well on even some of the oldest mobile devices.

Desktop screenshot of my password generator.

Desktop screenshot.

First mobile screenshot of my password generator.

First mobile screenshot.

Second mobile screenshot of my password generator.

Second mobile screenshot.

Random Passphrases Work, Even If They're Built From Known Passwords

Just this morning, security researcher Troy Hunt released a ZIP containing 306 million passwords that he's collected over the years from his ';--have i been pwned? service. As an extension, he created a service to provide either a password or a SHA-1 hash to see if your password has been pwnd.

Screenshot showing the entry text field to test your password from the new password checking service Troy Hunt has provided.

In 2009, the social network RockYou was breached, and 32 million accounts of usernames and passwords was released to the public Internet. No doubt those 32 million passwords are included in Troy Hunt's password dump. What's interesting, and the point of this post, is individually, each password from the RockYou breach will fail.

Collage of six screenshots of individual RockYou passwords failing Troy Hunt's password check. They were: caitlin, peachy, keeley, doreen, ursulet, & juggalo.

However, what would happen if you took 6 random RockYou passwords, and created a passphrase? Below is screenshot demonstrating just that using the above 6 randomly chosen RockYou passwords. Individually, they all fail. Combined, they pass.

Screenshot showing how creating the passphrase 'caitlinpeachykeeleydoreenursuletjuggalo' passes Troy Hunt's check.

Now, to be fair, I'm choosing these passwords from my personalized password generator. The list is the top 7,776 passwords from the 32 million RockYou dump. As such, you could use this list as a Diceware replacement with 5 dice. Regardless, each password is chosen at random from that list, and enough passwords are chosen to reach a 70-bits of entropy target, which happen to be 6 passwords. Mandatory screenshot below:

Screenshot showing my password generator using the RockYou passwords as a source for a strong passphrase. One screenshot is hyphenating the passwords, the other is not.

The point of this post, is that you can actually build a secure password for sites and services using previously breached passwords for your word list source, in this case, RockYou. The only conditions is that you have a word list large enough create a reasonable passphrase with few selections, and that the process picking the passwords for you is cryptographically random.

Electronic Slot Machines and Pseudorandom Number Generators

TL;DR

An Austrian casino company used a predictable pseudorandom number generator, rather than a cryptographically secure one, and people are taking advantage of it, and cashing out big.

The Story

Wired reported on an article about an amazing operation at beating electronic slot machines, by holding your phone to the slot machine screen for a time while playing, leaving the slot machine, then coming back an additional time, and cashing in big.

Unlike most slots cheats, he didn’t appear to tinker with any of the machines he targeted, all of which were older models manufactured by Aristocrat Leisure of Australia. Instead he’d simply play, pushing the buttons on a game like Star Drifter or Pelican Pete while furtively holding his iPhone close to the screen.

He’d walk away after a few minutes, then return a bit later to give the game a second chance. That’s when he’d get lucky. The man would parlay a $20 to $60 investment into as much as $1,300 before cashing out and moving on to another machine, where he’d start the cycle anew.

These machines were made by Austrian company Novomatic, and when Novomatic engineers learned of the problem, after a deep investigation, the best thing they could come up with, was that the random number generator in the machine was predictable:

Novomatic’s engineers could find no evidence that the machines in question had been tampered with, leading them to theorize that the cheaters had figured out how to predict the slots’ behavior. “Through targeted and prolonged observation of the individual game sequences as well as possibly recording individual games, it might be possible to allegedly identify a kind of ‘pattern’ in the game results,” the company admitted in a February 2011 notice to its customers.

The article, focused on a single incident in Missouri, mentions that the state vets the machines before they go into production:

Recognizing those patterns would require remarkable effort. Slot machine outcomes are controlled by programs called pseudorandom number generators that produce baffling results by design. Government regulators, such as the Missouri Gaming Commission, vet the integrity of each algorithm before casinos can deploy it.

On random number generators

I'll leave you to read the rest of the article. Suffice it to say, the Novomatic machines were using a predictable pseudorandom number generator after observing its output for a period of time. This poses some questions that should immediately start popping up in your head:

  1. What is the vetting process by states to verify the quality of the pseudorandom number generators in solt machines?
  2. Who is on that vetting commission? Is it made up of mathematicians and cryptographers? Or just a board of executives and politicians?
  3. Why aren't casino manufacturers using cryptographically secure pseudorandom number generators?

For me, that third item is the most important. No doubt, as the Wired article states, older machines just cannot be fixed. They need to be taken out of production. So long as they occupy casinos, convenience stores, and gas stations, they'll be attacked, and the owner will lose money. So let's talk about random number generators for a second, and see what the gambling industry can do to address this problem.

You can categorize random number generators into four categories:

  1. Nonsecure pseudorandom
  2. Cryptographically secure pseudorandom
  3. Chaotic true random
  4. Quantum true random

What I would be willing to bet, is that most electronic machines out there are of the "nonsecure pseudorandom" type of random number generator, and Novomatic just happened to pick a very poor one. Again, there likely isn't anything they can do about existing machines in production now, but what can they do moving forward? They should start using cryptographically secure pseudorandom number generators (CSPRNGs).

In reality, this is trivial. There are plenty of CSPRNGs to choose from. CSPRNGs can be broken down further into three subcategories:

  1. Designs based on cryptographic primitives.
  2. Number theoretic designs.
  3. Special-purpose designs.

Let's look at each of these in turn.

Designs based on cryptographic primitives.

These are generators that use things like block ciphers, stream ciphers, or hashing functions for the generator. There are some NIST and FIPS standardized designs:

  • NIST SP 800-90A rev. 1 (PDF): CTR_DRBG (a block cipher, such as AES in CTR mode), HMAC_DRBG (hash-based message authentication code), and Hash_DRBG (based on cryptographically secure hashing functions such as SHA-256).
  • ANSI X9.31 Appendix A.2.4: This is based on AES, and obsoletes ANSI X9.17 Appendix C, which is based on 3DES. It requires a high-precision clock to initially seed the generator. It was eventually obsoleted by ANSI X9.62-1998 Annex A.4.
  • ANSI X9.62-2005 Annex D: This standard is defines an HMAC_DRBG, similar to NIST SP 800-90A, using an HMAC as the cryptographic primitive. It obsoletes ANSI X9.62-1998 Annex A.4, and also requires a high-precision clock to initially seed the generator.

It's important that these designs are backtracking resistant, meaning that if you know the current state of the RNG, you cannot construct all previous states of the generator. The above standards are backtracking resistant.

Number theoretic designs

There are really only two current designs, that are based on either the factoring problem or the discrete logarithm problem:

  • Blum-Blum-Shub: This is generator based on the fact that it is difficult to compute the prime factors of very large composites (on the order of 200 or more digits in length). Due to the size of the prime factors, this is a very slow algorithm, and not practical generally.
  • Blum-Micali: This is a generator based on the discrete logarithm problem, when given two known integers "b" and "g", it is difficult to find "k" where "b^k = g". Like Blum-Blum-Shub, this generator is also very slow, and not practical generally.

Special-purpose designs

Thankfully, there are a lot of special purpose designs designed by cryptographers that are either stream ciphers that can be trivially ported to a CSPRNG, or deliberately designed CSPRNGs:

  • Yarrow: Created by cryptographer Bruce Schneier (deprecated by Fortuna)
  • Fortuna: Also created by Bruce Schneier, and obsoletes Yarrow.
  • ISAAC: Designed to address the problems in RC4.
  • ChaCha20: Designed by cryptographer Daniel Bernstein, our crypto Lord and Savior.
  • HC-256: The 256-bit alternative to HC-128, which is part of the eSTREAM portfolio.
  • eSTREAM portfolio: (7 algorithms- 3 hardware, 4 software)
  • Random123 suite: Contains four highly parallelizable counter-based algorithms, only two of which are cryptographically secure.

The solution for slot machines

So now what? Slot machine manufacturers should be using cryptographically secure algorithms in their machines, full stop. To be cryptographically secure, the generator:

  • Must past the next-bit test (you cannot predict the next bit any better than 50% probability).
  • Must withstand a state compromise (you cannot reconstruct past states of the generator based on the current state).

If those two properties are met in the generator, then the output will be indistinguishable from true random noise, and the generator will be unbiased, not allowing an adversary, such as someone with a cellphone monitoring the slot machine, to get the upperhand on the slot machine, and prematurely cash out.

However, the question should then be raised- "How do you properly seed the CSPRNG, so it starts in an unpredictable state, before release?" Easy, you have two options here:

  • Seed the CSPRNG with a hardware true RNG (HWRNG), such as a USB HWRNG, or....
  • Build the machine such that it collects environmental noise as entropy

The first point is much easier to achieve than the second. Slot machines likely don't have a lot of interrupts built into the system-on-a-chip (SoC). So aside from a microphone, video camera, or antenna recording external events, you're going to be hard-pressed to get any sort of high-quality entropy into the generator. USB TRNGs are available all over the web, and cheap. When the firmware is ready to be deployed, read 512-bits out of the USB generator, hash it with SHA-256, and save the resulting hash on disk as an "entropy file".

Then all that is left is when the slot machine boots up and shuts down:

  • On startup, read the "entropy file" saved from the previous shutdown, to seed the CSPRNG.
  • On shutdown, save 256-bits of data out of the generator to disk as an "entropy file".

This is how most operating systems have solved the problem with their built-in CSPRNGs. Provided that the very first "entropy file" was initially seeded with a USB true HWRNG, the state of every slot machine will be always be different, and will always be unpredictable. Also, 256-bits is more than sufficient to make sure the initial state of the generator is unpredictable; physics proves it.

Of course, the SoC could have a HWRNG onboard, but then you run the risk of hardware failure, and the generator becoming predictable. This risk doesn't exist with software-based CSPRNGs, so provided you can always save the state of the generator on disk at shutdown, and read it on startup, you'll always have an unpredictable slot machine.