Dr. Melissa Danforth

Computer and Electrical Engineering and Computer Science Department
California State University, Bakersfield

Password Complexity and Cracking Speed

Note to Teachers
This activity can be used to learn about permutations with repetition, exponents, and unit conversions.

This activity can be prepared as either an interactive activity or a pre-defined worksheet. Interactive components are asking students for password patterns and asking students to look up cracking speeds of GPU machines online.

If used in non-interactive mode, prepare password patterns and cracking speeds in the handout ahead of time. Here is a table of common password cracking rates:

GPU Power MD5 Algorithm SHA1 Algorithm SHA256 Algorithm SHA512 Algorithm bcrypt Algorithm
1 low-end GPU (Classroom computers) 480 million/sec 127 million/sec 56 million/sec 21 million/sec 150 hashes/sec
1 mid-to-high-end GPU 12.5 billion/sec 4.4 billion/sec 1.9 billion/sec 450 million/sec 8 thousand/sec
1 high-end GPU (NVIDIA 1080 Ti) 31 billion/sec 11 billion/sec 4.4 billion/sec 1.5 billion/sec 21 thousand/sec
2 low-end GPUs (old GPU rig) 10.9 billion/sec 3.8 billion/sec 1.3 billion/sec 335 million/sec 2.5 thousand/sec
2 mid-end GPUs (new GPU rig) 25 billion/sec 8.8 billion/sec 3.8 billion/sec 900 million/sec 16 thousand/sec
4 high-end GPUs (4 NVIDIA 1080 Ti) 125 billion/sec 45.5 billion/sec 17.7 billion/sec 6 billion/sec 85.4 thousand/sec
8 mid-end GPUs (2015 build) 93.8 billion/sec 29.5 billion/sec 12.3 billion/sec 2 billion/sec n/a
8 high-end GPUs (8 NVIDIA 1080 Ti) 307 billion/sec 101 billion/sec 39.2 billion/sec 13 billion/sec 184.5 thousand/sec
25 mid-end GPUs8 (2015 build) 180 billion/sec 63 billion/sec n/a n/a 71 thousand/sec
Activity Preparation
Walk the students through several examples of how to determine the size of the password search space from the number of characters, patterns, and types of characters chosen (see Introduction, Ethics, Operational Security, Passwords for background information).

The important part of determining the search space is knowing the number of possible characters in each type of character set. The following are common character sets:

Type of charset Number of Characters
Digits/Numbers 10
Lower-case Letters 26
Upper-case Letters 26
Symbols (e.g. # ! @ * % } = ? ,) 34
All 7-bit Characters 96

Calculating the Size of the Search Space
The size of the search space is the total number of possible combinations of characters in the character set, given a specific password length. Patterns can be uniform (same charset for each character in the password, e.g. all lower-case) or it can be mixed (1st three characters are digits, next three characters are lower-case). It is easier to begin the examples with uniform patterns.

For the examples, draw an empty box for each character in the password. Under the box, say what type of charset it is. Inside the box, write how many characters are in that charset. Then show the students how to calculate the number of permutations by multiplying the boxes together. If the pattern uses the same type for each character, this can also be used to show how permutations can be calculated by exponents.

Example 1: 8 lower-case characters

 ____     ____     ____     ____     ____     ____     ____     ____ 
|    |   |    |   |    |   |    |   |    |   |    |   |    |   |    |
| 26 | * | 26 | * | 26 | * | 26 | * | 26 | * | 26 | * | 26 | * | 26 |
|____|   |____|   |____|   |____|   |____|   |____|   |____|   |____|
Lower    Lower    Lower    Lower    Lower    Lower    Lower    Lower
26 * 26 * 26 * 26 * 26 * 26 * 26 * 26 = 268

Example 2: 7 characters, either lower-case or digits/numbers

Now the number of characters for each "slot" will be 26 + 10 = 36.

 ____     ____     ____     ____     ____     ____     ____ 
|    |   |    |   |    |   |    |   |    |   |    |   |    |
| 36 | * | 36 | * | 36 | * | 36 | * | 36 | * | 36 | * | 36 |
|____|   |____|   |____|   |____|   |____|   |____|   |____|
LowerNum LowerNum LowerNum LowerNum LowerNum LowerNum LowerNum
36 * 36 * 36 * 36 * 36 * 36 * 36 = 367

Example 3: 6 lower-case characters followed by 2 numbers/digits

 ____     ____     ____     ____     ____     ____     ____     ____ 
|    |   |    |   |    |   |    |   |    |   |    |   |    |   |    |
| 26 | * | 26 | * | 26 | * | 26 | * | 26 | * | 26 | * | 10 | * | 10 |
|____|   |____|   |____|   |____|   |____|   |____|   |____|   |____|
Lower    Lower    Lower    Lower    Lower    Lower    Number   Number
26 * 26 * 26 * 26 * 26 * 26 * 10 * 10 = 266 * 102

You can either pre-calculate the result or have students use calculators to calculate the results, depending on their level of mathematics preparation.

Calculating the Time to Crack Passwords
Take the size of the search space from the previous step and divide it by the cracking rate for one of the password algorithms (either have the students use the Internet to search for rates or give them the table at the top of this guide). This will give you maximum the number of seconds it takes to crack the password space. This calculation is an upper bound.

Note: If you give the students the above table, this exercise can also be used to show how to convert between billion, million, etc. The numbers can also be expressed in scientific notation to reinforce those lessons.

                        Size of the Search Space
Maximum Time to Crack = ------------------------
                         Password Cracking Rate
If the result is large, this exercise can also be used to teach time unit conversions, e.g. convert seconds into minutes, hours, days, years, etc.
Running the Activity
Either give students specific patterns or ask the students to create patterns on the fly. Have the students calculate the size of the search space and then calculate the time it would take to crack the passwords using one or more of the algorithms.

Comparing a fast algorithm (e.g. MD5) to a slow algorithm (e.g. bcrypt) can also be done during the activity.