CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 4 of 7 · 4 min read

Salt and cost

Think of a safe whose dial turns slowly, so that trying a combination takes a minute. A legitimate owner opens it once a day and does not mind. A thief with a million combinations to try is stopped. The analogy stops in one place: the owner's safe has one slow dial, while a thief can buy many safes and try them in parallel.

In plain words: A good password hash is slow on purpose. It does the same work for the real user, who logs in once, and for the attacker, who must try millions of guesses. SHA-512 crypt uses many rounds of a fast function. yescrypt, the default of many current systems, also needs a lot of memory, which makes it harder to run on many small units at once. The program below shows two facts. First, a salt changes the hash, so two users with the same password differ. Second, it times one hash to find how many guesses a core can try in a second.

A worked example.

#include <crypt.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

static double now(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(void) {
    static struct crypt_data cd;
    const char *prefixes[] = {"$6$", "$y$"};          /* SHA-512 crypt and yescrypt */
    const char *names[] = {"sha512crypt", "yescrypt"};
    for (int i = 0; i < 2; i++) {
        char s1[128], s2[128];                       /* crypt_gensalt reuses one buffer, so copy at once */
        snprintf(s1, sizeof s1, "%s", crypt_gensalt(prefixes[i], 0, NULL, 0));
        snprintf(s2, sizeof s2, "%s", crypt_gensalt(prefixes[i], 0, NULL, 0));
        char h1[256], h2[256], h3[256];
        snprintf(h1, sizeof h1, "%s", crypt_r("secret", s1, &cd));
        snprintf(h2, sizeof h2, "%s", crypt_r("secret", s2, &cd));
        snprintf(h3, sizeof h3, "%s", crypt_r("secret", s1, &cd));
        printf("%s: same password, two salts give %s hashes; same salt twice gives %s hashes\n",
               names[i], strcmp(h1, h2) ? "different" : "equal", strcmp(h1, h3) ? "different" : "equal");
        printf("  hash length %zu, sample: %.30s...\n", strlen(h1), h1);
        int n = 20; double t0 = now();
        for (int k = 0; k < n; k++) crypt_r("secret", s1, &cd);
        double t = (now() - t0) / n;
        printf("  one hash takes %.1f ms, so one core tries %.0f passwords per second\n", t * 1e3, 1 / t);
    }
    return 0;
}

Output on the test machine:

sha512crypt: same password, two salts give different hashes; same salt twice gives equal hashes
  hash length 106, sample: $6$5zr5LS8i6Ij5UElr$L7xMiHH5Wb...
  one hash takes 1.6 ms, so one core tries 616 passwords per second
yescrypt: same password, two salts give different hashes; same salt twice gives equal hashes
  hash length 73, sample: $y$j9T$myFDa2igZ6mtE67lZAbTU/$...
  one hash takes 13.7 ms, so one core tries 73 passwords per second

The same salt and password always give the same hash, which is how the login check works. A new salt gives a new hash, which is how users are kept apart. yescrypt took 13.7 ms for one hash against 1.6 ms for SHA-512 crypt, about 8 times as long, which means about 8 times fewer guesses for the attacker per core. Salts are random, so the sample strings differ from run to run, and timings vary by a few per cent. Section 4 uses rounded rates from an earlier run on the same machine: 71 and 588 guesses per second.

The key lines. The time per hash is a setting, and it is a trade. A login takes about 14 ms of one core, which no user notices, and a guess takes the same.

Password hashing cost

The cost of a password hash is the amount of work (time, and often memory) that one evaluation needs. It is set so that one check is affordable at login and a search over many guesses is not.

Example: yescrypt at its default setting took 13.7 ms per hash on one core of the test machine.

Check yourself: 1. What does the program show about the same salt used twice? 2. How many guesses per second does one core make at 13.7 ms per hash? 3. Why is a slow hash good for defence?