Key stretching

Provide a functions that generates a 256bit key from a 256bit key.


void key_expand(void *dst, const void *src, u64 effort);

dst is the 256bit output key to be generated, src is the 256bit input key, effort is an opaque parameter that somehow tunes the effort.

The effort parameter is technically not necessary, but can be used to tune runtime to take roughly 100ms. See rationale.

Evaluation

Performance evaluation would be silly when all candidates take about 100ms to run. The real evaluation is the cost of the function to an attacker. Measuring that cost is impossible, so we have to accept paper arguments for the cost.

As a somewhat simplistic model, I will use gate-cycles as the currency we are trying to maximize. Any 2-input boolean function (and, or, xor, etc) is considered a gate. Occupying one such function for one cycle costs a gate-cycle. Memory can be translated into gates, I think 6 gates for 1 bit of memory might be a reasonable conversion factor.

For security, this function should have all the attributes of a cryptographic hash function. If there is no faster way to find collisions or determine the input based on the output than brute force, the candidate is considered barely secure.

Rationale

The idea is to strengthen weak passwords as much as possible. Given typical hash functions, it is far to cheap for an attacker to do a dictionary attack and simply try quadrillions of passwords. We want to make that process significantly more expensive to an attacker without making things significantly more annoying to the user.

For me personally, a 1s delay is long enough to be a serious annoyance, a 100ms delay is fast enough to be almost imperceptible. So I will arbitrarily make a 100ms threshold the target. Equally arbitrarily I will set CPU frequency to 1GHz. So we have 100M cycles available to turn one 256bit key into another 256bit key.