[Cfrg] Multi-user attack on bottleneck key generation?

[Dan Brown <[e-mail]>]

Dear CFRG,

Is there a multi-user attack (e.g., see below) on _any_ 128-bit-secure public keys (e.g. 256-bit ECC keys) if they are generated by hashing 128-bit uniformly random seed?  I will call this key generation method "bottleneck key generation".  To be clear, all user users share the same 128-bit bottleneck, and that may be the problem.

If there is indeed an multi-user attack here, is the multi-user attack (against 2^N users) prevented by using a (128+N)-bit seed, OR by using a unique-per-public-key salt/nonce/tag/personalization value?

The very notion of multi-user security has always puzzled me: I question its merit as a goal.  This might be why I forget how it works so easily. (Over the last day, I tried to remember/search for existing write-ups on this, see further below.)  

On the issue of naivety of the bottleneck key generation above, I think it very plausible that many would consider it reasonably secure. 

This topic touches a couple CFRG items, but seems to be question of general crypto interest.

***

For completeness, here is what I think the multi-user attack on bottleneck key generation:

Each of 2^32 users does the following.  
- User j chooses a uniformly random 128-bit seed s[j], independently of all other users.  
- User j computes a secret key a[j] by hashing s[j], e.g., using SHA-256 (or some other deterministic, collision-resistant function). 
- User j computes a public key A[j] from a[j], e.g. in ECC A[j]=a[j]*G.

The attacker does the following.
- Obtain all 2^32 values A[j], and sorts them, or stores in a hash-table.
- Does the following up to 2^96 times:
	- compute a 128-bit seed, s', 
	- compute secret key a', the same way as the user, e.g. a' = SHA256(s'), 
	- compute public key A', the same way as the user, e.g. A' = a' * G,
	- check if A' in is list of A[j], via table-lookup.
- If A' in A[j] is found, then attacker outputs a' as the guess for a[j].  The attacker wins the multi-user game.

Success rate: The attack is expected to work with probability near 1/e (e~2.7?), essentially finding a collision at the level of seeds with s[j]=s', being a variation of the birthday paradox.  (Proof sketch? Each s' has prob 2^32/2^128 of hitting an s[j], assuming all user seed distinct.  This is 1/M for M=2^96.  The prob of all M independent s' missing is (1-1/M)^M ~ 1/e.  This ignore the prob of s[j] collisions, and SHA256 collisions, etc.)

Attack cost: The attacker uses 2^96 steps (each step matching the user's cost).

Hmm ... is this somehow an "optimal" multi-user attack, in the sense the cost reduction factor equals the number of users? 

If the seeds above are increased to 160 bits, then the multi-user attack (against 2^32 users) seems to take 2^128 steps.  In this case, the multi-user security is optimal (matching single-user security).  If we put a max of 2^64 users, then a 192-seed may be good enough for maximal multi-user security.

Why do I question multi-user security? The cost of resisting multi-user attacks seems to be nonzero for the single user.  It seems to me that the single-user should only pay for this cost if there is a common interest with other users.  If there is a common interest, then maybe so formalized communal crypto is needed instead?  E.g. group/ring/whatever signature?

***

Relevant past work on multi-user security, in approximate chronological order:

[1] Salting password hashes.  Not sure what the best reference is for this.  I think the oldest work is salting the password hashes.   Is "salt" the usual word here?  The numbers for larger seeds and keys correspond to higher security levels then passwords and hashes, but the logic is otherwise similar, isn't it?  (In other words, not sure why new words would be used instead of salt.) 

[2] Hastad-style security analysis: I lump MANY works together, perhaps originating from Hastad, which all assume full-power key generation, i.e. NOT 128-bit bottleneck key generation.  Instead, these papers ask other important questions about multi-user security.  In other words, the question is whether the public key algorithm itself has some other kind of bottleneck (which all users share).  As some examples of this direction of research, I include Bellare--Boldyreva--Micali work on PKE https://cseweb.ucsd.edu/~mihir/papers/musu.pdf and Bernstein's work on Schnorr signatures https://ia.cr/2015/996, but I would need to re-read these works carefully: perhaps they treat the issue of bottleneck key generation in an off-hand remark as an something obvious, dating back to [1].

[4] The issue seems to be discussed, rather vaguely, in ANSI X9.62-2005, Section K.5, item e.  (I am trying to resolve comments from Elaine Barker about this Section K.5. I eventually clued about the generality of this issue, leading me to this email.)

[5] Zaverucha, https://ia.cr/2012/159, "Hybrid encryption in the multi-user setting" perhaps goes a little further than the Hastad-type attacks that I lumped together in [3], since it describes 128-bottlenecks in key derivation more generally, including the key generation and HKDF.  As with [3], I have forgotten the details, and would need re-read the paper very carefully to see if it really should be lumped together with [3].  

[6] NIST Special publication 800-90Ar1, specifies a "DRBG".  A DRBG can be interpreted as a deterministic function mapping a 128-bit secret seed to a pseudorandom 256-key. The NIST SP 800-90Ar1 requires a "nonce" or a "personalization string", unique to each user.  Is this not just another example of the "salt" solution?  Is the purpose of this "multi-user" security?  I find the NIST document very long, and find it difficult to be certain if the multi-user security is resolved.

[7]  RFC 8032 has a comment about a few missing bits of entropy (in the EdDSA key) missing not being disastrous.  This claim sounds correct (see the attack where I talk about 192-bit seeds). Is the justification for this claim quantified somewhere?    There was also some discussion of multi-user security surrounding EdDSA variants, so maybe bottleneck key generation is an issue for EdDSA too.

[8] The randomness improvement draft https://datatracker.ietf.org/doc/draft-irtf-cfrg-randomness-improvements/ uses the term "tag", which should be user-specific (?).  Another example of a "salt", if I understand it.  See also https://ia.cr/2018/1057


A digression: best practice password-hashing involves costly hashes, e.g. Argon2, not just per-user salts. Costly hashes may be re-usable for public key seeding, no? 



​​​​​Dan Brown
Phone: [phone]
BlackBerry, Security in Motion