The following information and exercises relate to some of the theory and mathematics of password complexity (entropy).

Frink engineering calculator

Frink is a text-based units-aware engineering calculator, with programming features and the ability to do interval arithmetic. Since Frink is aware of the different units of information (bit, byte, nat), hartley)) and their decimal and binary multipliers (e.g. mega, mebi), and provides functions for calculating logarithms, it is well suited for carrying out information theory calculations.

To run a Frink interpreter in the Linux CLI, simply run frink and it will take over the terminal (Type Ctrl-D to exit from Frink when you are done). Try the example commands provided to check the output. You can use the up and down arrow keys to navigate your recent Frink command history.

Frink understands common mathematical operators, and uses ^ for exponentiation.

1 + 1
7 * 9
2 ^ 8

Frink understands a wide variety of physical quantities and their units, including the SI multiplier prefixes. It can also perform unit conversions using the -> operator.

lightspeed -> terafurlongs/fortnight
80 kg * lightspeed^2 -> trillion kWh
1920 * 1080 * 32 bit -> mebibyte

Frink also has a library of common functions, although note that it uses square brackets rather than round parentheses to delimit function parameter/argument lists. It has no built-in function for calculating base-2 logarithms, but you can create one easily enough using the built-in log functions:

log2[x] := log[x] / log[2]

You can then call the function as follows (in this case, 2 to the power of what gives 4?):

log2[4]

Frink also has some handy date and time capabilities, which may be helpful in calculating how long a brute-force attack might take, for example:

now[] + 3 hours
2^32 s -> years
52^8 / (10 million/s) -> months

Exercises

Use Frink and your understanding of password complexity and entropy to perform the following calculations. Tabulate your answers in a spreadsheet as you go.

1. How many possible passwords (permutations) exist for a fixed 8-character length password scheme consisting only of lowercase letters?

2. Calculate the binary entropy (number of bits) of such a password pattern (use the log2[]) function defined earlier, applied to the number of permutations). Assume that each pattern is equally likely (uniform probability). How does the result compare with the recommended minimum number of bits from the lectures?

3. How long would it take to conduct an exhaustive character-wise brute-force attack on such a password pattern? Assume 1 million hashes per second (not unrealistic for specialised software on a modern PC, but bear in mind than on average only half the space needs to be searched if looking for a single hash; use the worst-case figure here).

4. What if you extended the alphabet size to include mixed case, digits, and punctuation (95 possible characters in total)? Keep the length at 8 characters. Calculate the number of permutations, binary entropy, and estimated time to hash all permutations.

5. What if you limited the alphabet to lowercase letters only, but extended the length to 18 characters?

6. Of course, when people are able to choose their own passwords, certain permutations of characters are (far!) more likely than others. Discuss how this would affect the entropy, and how an attacker might use the popularity of certain passwords to their advantage.

7. Of course, the effective entropy also depends on the attack scheme used. What if you used the "correct horse battery staple" scheme from the xkcd cartoon? Assume a dictionary of 2000 words, and a dictionary-based attack rather than character-wise brute-force.

8. Critique the proposed xkcd password scheme. Is it sufficiently secure in terms of the number of permutations? What are the main points the author was trying to make?