"Work factor" and "iteration count" nomenclature in adaptive functions

Question

In adaptive functions like PBKDF2 / bcrypt I often read people refer to "iteration count" and others refer to "work factor", and they seem to be used interchangeably (even though they're not - the latter is used to calculate the former).

I also see this (commodity hardware circa 2019):

• iteration count: e.g. 100,000
• work factor: e.g. 16 or 17, i.e. 2^16..2^17 (65536..131072)

I like the idea of work factor as it's simpler to reason with when coding, e.g. I can "increase the work factor" every year, which means go from 16 to 17, etc. So it's a base-2 "order of magnitude".

However, what is the "correct" nomenclature?

Answer 1

There is no international committee on which function / term is correct or not.

Work factor seems to be a more generic term, and I'd prefer that when talking about the relative amount of work that needs to be performed. That - at least internally - an iteration count is used together with a hash algorithm is an implementation detail.

The work factor doesn't really have a generic value in itself. So any password hash / KBKDF that performs key stretching must have a work factor. But how this work factor reflects the amount of work is algorithm specific. It could be using a logarithmic scale and for many algorithms this is the case. However, the iteration count - which is linear - is also a work factor - even if the specific algorithm specification doesn't explicitly use that name for it.

In the end, the best way to compare the time required (CPU time or user time) is to test the values. You can make a pretty good bet if you know the internal details, but in the end small changes - for instance the specific implementation - may make a lot of difference.

Answer 2

• Iteration count is a parameter that you can choose directly; likewise memory use and parallelism for other password hashes like Argon2.

  These should be tuned according to the user's available resources: how many CPU cores they can use in parallel to log in, how much memory they can use while logging in, and how many seconds they are willing to wait for login—which, of course, depends on how fast the user's CPU runs.

• Usually work factor is the ratio (or log-ratio, sometimes instead called ‘security level’) of an adversary's expected cost at breaking a cryptosystem, like finding a uniform random 256-bit key $k$ given $\operatorname{AES}_k(81263)$, to the cost of computing AES. For AES-256, we might hope it is around $2^{256}$—although actually, if we have many different keys $k_1, k_2, \dots, k_n$ of interest, the attacker can save effort attacking them simultaneously so that it is actually around $2^{256}/n$ per key.

  Attack costs are sometimes measured in time, but this is not a good unit because if one CPU can evaluate $\operatorname{AES}_k(81263)$ for a thousand different keys in 1000 nanoseconds, a die with 1000 AES circuits can evaluate it for a thousand different keys in 1 nanosecond. But the product of parallelism and time spent is constant. More generally—for algorithms like sorting that have high communication costs as well—the AT or area*time cost, which measures the product of die area and time spent powering the die, is a good proxy for cost in joules or rubles.

• What a good password hash aims to do is raise the adversary's expected cost of brute force attack by raising the average cost of trying a single guess using all the resources a user has at their disposal—time to twiddle thumbs, scratch memory to scribble garbage over, and CPU cores to run in parallel.

  What really determines the work factor is the probability distribution on passwords: choose your password from the space $\{\text{‘password’}, \text{‘hunter2’}\}$, and the work factor is a little pathetic; choose your password to be ten diceware words from a 7776-word list, and the work factor should be around a comfortable $2^{128}$ (unless someone forgot to salt the password hash and it comes out real bland and watery).

  Again, the cost is not about time to evaluate, per se: While a user is limited by latency—how long it takes their CPU to compute a single password hash from start to finish—an adversary is limited by bandwidth—how many password hashes they can compute per second, even if from start to finish the computation of one hash takes an hour.^*

  Although the adversary's hash rate isn't something that can be controlled directly, the designer of the cryptosystem tries to arrange that there are no convenient tradeoffs that an adversary could exploit, e.g. by finding shortcuts in evaluating a hash, or by cramming many parallel hash circuits onto a die to attain a high hash rate at the same energy cost of a user who has a general-purpose CPU with general-purpose RAM to power.

---

_{^* This is related to the old adage that while an ossifrage egg incubates about 54 days before hatching, you can't get an ossifrage in one day just by getting 54 ossifrages to lay one egg apiece. However, you could average one ossifrage hatchling per day with 54 ossifrages (that is, if ossifrages could breed at any time of year, which they can't, unlike you weirdo breeding-crazed humans).}

Answer 3

I think while asking and repeatedly editing the question, I ended up answering it. This is what I think: they are not the same.

Most people incorrectly use the terms interchangeably but they're different:

iteration_count = 2^work_factor

Personally I prefer work factor, a it's easier to use in code. And I like the idea of "order of magnitude" instead of an absolute value.

But it must be clear which an algorithm is expecting, else you might do 2^100000.