CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Password space (20 minutes)

How many passwords are there of 5 lowercase letters, and of 4 digits?

Done when: 11,881,376 and 10,000.

Hint

26^5 and 10^4.

Easy 2: Guess rate (20 minutes)

One hash takes 5 ms. How many guesses per second does one core make, and how many do 100 cores make?

Done when: 200 and 20,000.

Hint

one divided by the time of one hash.

Easy 3: Read a shadow field (20 minutes)

What do the prefix, salt and hash tell you in $6$abcd1234$XYZ...?

Done when: method 6 (SHA-512 crypt), salt abcd1234, hash XYZ....

Hint

the parts are separated by $.

Medium

Medium 1: Time to search (45 minutes)

An attacker makes 50,000 guesses per second. How long does a search of 7 lowercase letters take, and of 10 digits?

Done when: 26^7 = 8,031,810,176 / 50,000 = 160,636 s (1.9 days), and 10^10 / 50,000 = 200,000 s (2.3 days).

Hint

divide the space by 50,000.

Medium 2: Run the program (45 minutes)

Compile the program of section 3 with -lcrypt and run it on your machine. Report the hash times, and the guesses per second.

Done when: your own timings, and a sentence on how they compare with 1.6 ms and 13.7 ms.

Hint

use gcc hash.c -o hash -lcrypt.

Medium 3: Two factors (45 minutes)

A password is guessed with probability 1 in 5,000 per attempt window, and a phone code with 1 in 1,000,000. What is the chance that both are guessed in one attempt, and how much safer is it than the password alone?

Done when: 1 in 5 x 10^9 and a factor of 1,000,000 smaller.

Hint

multiply the two probabilities.

Hard

Hard 1: Check a password (90 minutes)

Write a program that reads a shadow-style hash string and a password from the command line (use a test hash that you make with your own program), uses crypt_r with the stored string as salt, and reports whether they match. Compare the result with == on strings, and explain why you must compare in constant time in a real program.

Done when: a match for the right password and a mismatch for a wrong one, and a paragraph that says that a comparison that stops at the first difference leaks timing.

Hint

pass the whole stored string as the salt argument of crypt_r. It stops at the hash part.

Hard 2: Cost tuning (90 minutes)

Use crypt_gensalt with a cost setting for yescrypt (for example $y$j9T$ against a higher $y$jCT$, or read the manual) to find a setting that takes about 100 ms on your machine. Report the settings and times.

Done when: a table of at least three settings with their times, and the one that is close to 100 ms.

Hint

the cost field follows the second $. A larger value raises the cost.

Hard 3: Policy (90 minutes)

A company must choose between requiring 8 characters with complexity rules, or 16 characters with no rules, for a system that uses yescrypt at 71 guesses per second per core and faces 10,000 cores. Estimate the search time for each if users pick uniformly at random from the full space, and say what changes if they do not.

Done when: 95^8 / 710,000 = 9.3 x 10^9 s (296 years) and 95^16 / 710,000, a far larger value, with a note that human choices are not uniform, so dictionaries apply.

Hint

95 symbols is the number of printable ASCII characters.