Security bits

[Dmitry Chestnykh <dmitry@codingrobots.com>]

Hello,

People love talking about “bits of security” to compare and match security levels of various cryptographic primitives even when such comparison may not make sense (for example, https://www.ietf.org/mail-archive/web/cfrg/current/msg04820.html, or — as it’s pointed out in the scrypt paper — it doesn’t take into account the *cost* of operation).

Nevertheless, it’s a useful metric for intuitive and… ugh marketing… comparison. For example, Signal messenger calculates 30-digit fingerprints of public keys by running SHA-512 on them for some predefined number of iterations to make it harder to produce preimages of fingerprints, and they have the following estimation:

   *                   The higher the iteration count, the higher the security level:
   *
   *                   - 1024 ~ 109.7 bits
   *                   - 1400 > 110 bits
   *                   - 5200 > 112 bits

Source: https://github.com/WhisperSystems/libsignal-protocol-java/blob/5c784ead7f7c5f0c2ffa2ad3fb09febe58b84718/java/src/main/java/org/whispersystems/libsignal/fingerprint/NumericFingerprintGenerator.java#L26-L41

That is, log2(10^30) + log2(5200) ~= 112 bits

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

Thank you!

-- 
Dmitry Chestnykh
Coding Robots
https://www.codingrobots.com