Re: Security bits

[Colin Percival <cperciva@tarsnap.com>]

On 05/12/17 04:32, Dmitry Chestnykh wrote:
> [... “bits of security” ...]
> I was wondering what would be a similar metric for scrypt if we were to
> compare their method of stretching to the one that uses scrypt? Can we take
> the number of Salsa20/8 iterations to estimate the number of “security
> bits”. Would it make any sense at all — even for comparison purposes? For
> example, if I take N = 2^14, r = 8, p = 1, which makes 524288 Salsa dances,
> will a claim that it approximately adds log2(524288) = 19 bits to the
> “security level” be somewhat accurate?
> 
> Another estimate that I can think of is performing the same cost estimation
> as in scrypt paper, for example, for PBKDF-HMAC-SHA-256 and scrypt and then
> giving scrypt security level in PBKDF2-equivalent unit:
> 
> 	if 86,000 iterations of PBKDF2-HMAC-SHA-256 costing $160M get us log2(86,000) ~= 16 bits,
>         then scrypt (2^14, 8, 1), running for the similar time, costing $43B will give:
> 
> 			log2(43B*86K/160M) ~= 24 bits

I think the most meaningful estimate will come from taking the number of salsa
operations or the number of SHA256 hashes for an equivalent cost, whichever is
greater.

For N=2^n and the usual r = 8, p = 1, the first option yields n + 5 "bits of
security" based on the number of Salsa20/8 operations, while the second yields
2n - 3 "bits of security" based on the cost of the RAM needed.  (Note that one
HMAC-SHA256 operation is two SHA256 operations.)

The crossover point is at N=2^8, which makes sense; the cost of 256 kB of RAM
is on the same order as a SHA256 or Salsa20/8 circuit.  For very small scrypt
computations the RAM area can be ignored; for large scrypt computations the
RAM dominates the cost.

-- 
Colin Percival
Security Officer Emeritus, FreeBSD | The power to serve
Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid