Password strength and information entropy

Comparison of the password strength of Tr0ub4dor&3 (easy to guess, difficult to remember) and correcthorsebatterystaple (hard to guess but easy to remember if you turn it into a picture) — CREDIT: Randall Munroe, xkcd.com https://xkcd.com/936 – reprinted under a CC Attribution-NonCommercial 2.5 License

How do you decide whether a password is strong? Computer scientists have a mathematical way to do it. Based on an idea called information entropy it’s part of “Information Theory”, invented by electrical engineer Claude Shannon back in 1948. This XKCD cartoon for computer scientists uses this idea to compare two different password. Unless you understand information theory the detail is a bit mind blowing to work out what is going on though… so let’s explain the computer science!

Entropy is based on the number of guesses someone would need to make trying all the possibilities for a password one at a time – doing what computer scientists call a brute force attack. Think about a PIN on a mobile phone or cash point. Suppose it was a single digit – there would be 10 possibilities to try. If 2-digit PINS were required then there are now 100 different possibilities. With the normal 4 digits you need 10,000 (10^4 = 10x10x10x10) guesses to be sure of getting it. Different symbol sets lead to more possibilities. If you had to use lower case letters instead of digits, there are 26 possibilities for length 1 so over 450,000 (26^4 = 26x26x26x26) guesses needed for the 4 letter password. If upper case letters are possible that goes up to more than 7 million (52 letters so 52^4 = 52x52x52x52) guesses. If you know they used a word though you don’t have to try all the possibilities, just the words. There are only about 5000 of those, so far fewer guesses needed. So password strength depends on the number of symbols that could be used, but also whether the PIN or password was chosen randomly (words aren’t a random sequence of letters!)

To make everything standard, Shannon used binary to do entropy calculations so assumed a symbol set of only 0 and 1 (so all the answers become powers of 2 because he used 2 symbols). He then measured them in ‘bits’ needed to count all the guesses. Any other groups of symbols are converted to binary first. If a cashpoint only had buttons A, B, C and D for PINs, then to do the calculation you count those 4 options in binary: 00 (A), 01 (B), 10 (C), 11 (D) and see you need 2 bits to do it (2^2 = 2×2 choices). Real cashpoints have 10 digits and need just over 3 bits to represent all of a 1 digit PIN (2^3 = 2x2x2 = 8 so not enough, 2^4 = 2x2x2x2 = 16 so more than you need so the answer is more than 3 but less than 4). It’s entropy would be just over 3. To count the possibilities for a 4-digit PIN you need just over 13 bits, so that is its entropy. The lower case alphabet needs just under 6 bits to store the number of possibilities, so entropy is about 6, and so on.

So entropy is not measured directly in terms of guesses (which would be very big numbers) but instead indirectly in terms of bits. If you determine the entropy to be 28 bits (as in the cartoon), that means the number of different possibilities to guess would fit in 28 bits if each guess was given its own unique binary code. 28 bits of binary can be used to represent over 268 million different things (2^28), so that is the number of guesses actually needed. It is a lot of guesses but not so many a computer couldn’t try them all fairly quickly as the cartoon points out!

Where do those 28 bits come from? Well they assume the hacker is just trying to crack passwords that follow a common pattern people use (so are not that random). The hacker assumes the person did the following: Take a word; maybe make the first letter a capital; swap digits in place of some similar looking letters; and finally add a symbol and letter at the end. It follows the general advice for passwords, and looks random … but is it?

How do we work out the entropy of a password invented that way? First, think about the base word the password is built around. They estimate it as 16 bits for an up to 9 letter word of lower-case letters, so are assuming there are 2^16 (i.e. 65,000) possible such base words. There are about 40,000 nine letter words in English, so that’s an over estimate if you are assuming you know the length. Perhaps not if you assume things like fictional names and shorter words are possible.

As the pattern followed is that the first letter could be uppercase, that adds 1 more bit for the two guesses now needed for each word tried: check if it’s upper-case, then check if it’s lower-case. Similarly, as any letter ‘o’ might have been swapped for 0, and any ‘a’ for 4 (as people commonly do) this adds 3 more bits (assuming there are at most 3 such opportunities per word). Finally, we need 3 bits for the 9 possible digits and another 4 bits for the common punctuation characters added on the end. Another bit is added for the two possible orders of punctuation and digit. Add up all those bits and we have the 28 bits suggested in the cartoon (where bits are represented by little squares).

Now do a similar calculation for the other way of creating passwords suggested in the cartoon. If there are only about 2000 really common words a person might choose from, we need 11 bits per word. If we string 4 such words together completely at random (not following a recognisable phrase with no link between the words) we get the much larger entropy of 44 bits overall. More bits means harder to crack, so this password will be much, much harder than the first. It takes over 17 trillion guesses rather than 268 million.

The serious joke of the cartoon is that the rules we are told to follow leads to people creating passwords that are not very random at all, precisely because they have been created following rules. That means they are easy to crack (but still hard to remember). If instead you used the 4 longish and unconnected word method which doesn’t obey any of the rules we are told to follow, you actually get a password that is much easier to remember (if you turn it into a surreal picture and remember the picture), but harder to crack because it actually has more randomness in it! That is the real lesson. How ever you create a password, it has to have lots of randomness for it to be strong. Entropy gives you a way to check how well you have done.

Paul Curzon, Queen Mary University of London

Claude Shannon: Inventing for the fun of it

Claude Shannon, inventor of the rocket powered Frisbee, gasoline powered pogo stick, a calculator that worked using roman numerals, and discoverer of the fundamental equation of juggling! Oh yeah, and founder of the most important theory underpinning all digital communication: information theory.

Claude Shannon is perhaps one of the most important engineers of the 20th century, but he did it for fun. Though his work changed the world, he was always playing with and designing things, simply because it amused him. Like his contemporary Richard Feynman, he did it for ‘the pleasure of finding things out.’

As a boy, Claude liked to build model planes and radio-controlled boats. He once built a telegraph system to a friend’s house half a mile away, though he got in trouble for using the barbed wires around a nearby pasture. He earned pocket money delivering telegrams and repairing radios.

He went to the University of Michigan, and then worked on his Masters at MIT. While there, he thought that the logic he learned in his maths classes could be applied to the electronic circuits he studied in engineering. This became his Masters thesis, published in 1938. It was described as ‘one of the most important Master’s theses ever written… helped to change digital circuit design from an art to a science.’

Claude Shannon is known for his serious research, but a lot of his work was whimsical. He invented a calculator called THROBAC (Thrifty Roman numerical BACkward looking computer), that performs all its operations in the Roman numeral system. His home was full of mechanical turtles that would wander around, turning at obstacles; a gasoline-powered pogostick and rocket-powered Frisbee; a machine that juggled three balls with two mechanical hands; a machine to solve the Rubik’s cube; and the ‘Ultimate Machine’, which was just a box that when turned on, would make an angry, annoyed sound, reach out a hand and turn itself off. As Claude once explained with a smile, ‘I’ve spent lots of time on totally useless things.’

A lot of the early psychology experiments used to involve getting a mouse to run through a maze to reach some food at the end. By performing these experiments over and over in different ways, they could figure out how a mouse learns. So Claude built a mouse-shaped robot called Theseus. Theseus could search a maze until he solved it, and then use this knowledge to find its way through the maze from any starting point.

Oh, and there’s one other paper of his that needs mentioning. No, not the one on the science of juggling, or even the one describing his ‘mind reading’ machine. In 1948 he published ‘A mathematical theory of communication.’ Quite simply, this changed the world, and changed how we think about information. It laid the groundwork for a lot of important theory used in developing modern cryptography, satellite navigation, mobile phone networks… and the internet.

– Paul Curzon, Queen Mary University of London.

Related Magazine …

EE4FN Issue 2 – Electronic Engineering For Fun

This article was first published on the original CS4FN website and there is a copy on page 19 of the 2nd issue of the EE4FN (Electronic Engineering For Fun) magazine, which you can download below – along with all of our back issues.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

The computer vs the casino: Wearable tech cheating

Close up of roulette wheel with ball on black 17 — Image by Greg Montani from Pixabay

What happened when a legend of computer science took on the Las Vegas casinos? The answer, surprisingly, was the birth of wearable computing.

There have always been people looking to beat the system, to get that little bit extra of the odds going their way to allow them to clean up at the casino. Over the years maths and technology have been used, from a hidden mechanical arm up your sleeve allowing you to swap cards, to the more cerebral card counting. In the latter, a player remembers a running total of the cards played so they can estimate when high value cards will be dealt. One popular game to try and cheat was Roulette.

A spin of the wheel

Roulette, which comes from the French word ‘little wheel’, involves a dish containing a circular rotating part marked into red and black numbers. A simple version of the game was developed by the French mathematician, Pascal, and it evolved over the centuries to become a popular betting game. The central disc is spun and as it rotates a small ball is thrown into the dish. Players bet on the number that the ball will eventually stop at. The game is based on probability, but like most games there is a house advantage: the probabilities mean that the casino will tend to win more money than it loses.

Gamblers tried to work out betting strategies to win, but the random nature of where the ball stops thwarted them. In fact, the pattern of numbers produced from multiple roulette spins was so random that mathematicians and scientists have used these numbers as a random-number generator. Methods using them are even called Monte Carlo methods after the famous casino town. They are ways to calculate difficult mathematical functions by taking thousands of random samples of their value at different random places.

A mathematical system of betting wasn’t going to work to beat the game, but there was one possible weakness to be exploited: the person who ran the game and threw the ball into the wheel, the croupier.

No more bets please

There is a natural human instinct to spin the wheel and throw the ball in a consistent pattern. Each croupier who has played thousands of games has a slight bias in the speed and force with which they spin the wheel and throw the ball in. If you could just see where the wheel was when the spin started and the ball went in, you could use the short time before betting was suspended to make a rough guess of the area where the ball was more likely to land, giving you an edge. This is called ‘clocking the wheel’, but it requires great skill. You have to watch many games with the same croupier to gain a tiny chance of working out where their ball will go. This isn’t cheating in the same way as physically tampering with the wheel with weights and magnets (which is illegal), it is the skill of the gambler’s observation that gives the edge. Casinos became aware of it, so frequently changed the croupier on each game, so the players couldn’t watch long enough to work out the pattern. But if there was some technological way to work this out quickly perhaps the game could be beaten.

Blackjack and back room

Enter Ed Thorpe, in the 1950s, a graduate student in physics at MIT. Along with his interest in physics he had a love of gambling. Using his access to one of the world’s few room filling IBM computers at the university he was able to run the probabilities in card games and using this wrote a scientific paper on a method to win at Blackjack. This paper brought him to the attention of Claude Shannon, the famous and rather eccentric father of information theory. Shannon loved to invent things: the flame throwing trumpet, the insult machine and other weird and wonderful devices filled the basement workshop of his home. It was there that he and Ed decided to try and take on the casinos at Roulette and built arguably the first wearable computer.

Sounds like a win

The device comprised a pressure switch hidden in a shoe. When the ball was spun and passed a fixed point on the wheel, the wearer pressed the switch. A computer timer, strapped to the wrist, started and was used to track the progress of the ball as it passed around the wheel, using technology in place of human skill to clock the wheel. A series of musical tones told the person using the device where the ball would stop, each tone represented a separate part of the wheel. They tested the device in secret and found that using it gave them a 44% increased chance of correctly predicting the winning numbers. They decided to try it for real … and it worked! However, the fine wires that connected the computer to the earpiece kept breaking, so they gave up after winning only a few dollars. The device, though very simple and for a single purpose, is in the computing museum at MIT. The inventors eventually published the detail in a scientific paper called “The Invention of the First Wearable Computer,” in 1998.

The long arm of the law reaches out

Others followed with similar systems built into shoes, developing more computers and software to help cheat at Blackjack too, but by the mid 1980’s the casino authorities became wise to this way to win, so new laws were introduced to prevent the use of technology to give unfair advantages in casino games. It definitely is now cheating. If you look at the rules for casinos today they specifically exclude the use of mobile phones at the table, for example, just in case your phone is using some clever app to scam the casinos.

From its rather strange beginning, wearable computing has spun out into new areas and applications, and quite where it will go next is anybody’s bet.

by Peter W. McOwan, Queen Mary University of London, Autumn 2018