4
$\begingroup$

Apparently it is perfectly safe to use 128 bits of entropy to generate a single 256 bit ECC key. Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key?

I assume this is because 256 bit ECC keys have a bit strength of 128 bits according to How many bits of entropy does an elliptic curve key of length n provide?

The first article linked above however stipulates that if more than one 256-bit ECC key was being generated from the 128-bits of entropy, there might be the possiblitity of a 'multi target attack'.

Consider the following scenario:

128 bits of entropy are passed through keccak-256 to generate a 256-bit ECC private key. A second ECC private key would then be generated by hashing the first 256-bit ECC private key.

Would this be liable to such a 'multi target attack'? If so, how would that attack work? Can this situation be resolved by increasing the initial entropy above 128 bits, and if so, how much higher would it need to be to allow for the two ECC private keys to be safely generated?

This question is applicable to Monero, where it is the case that 256 bits of entropy are used for a wallet's private spend key. That key is then hashed with keccak-256 to generate the wallet's private view key. The necessity of 256 bits of entropy has been questioned.

$\endgroup$
  • 1
    $\begingroup$ I do not like the idea of hashing a private key to create another key $\endgroup$ – Richie Frame Mar 17 '18 at 0:48
  • $\begingroup$ @RichieFrame Please could you elaborate? Are you essentially saying that the BIP 32 HID wallet system is, in your opinion, flawed? See CKDF "Child Key Derivation Function" here: github.com/bitcoin/bips/blob/master/… $\endgroup$ – knaccc Mar 17 '18 at 10:29
  • $\begingroup$ HMAC is generally a little different, and their derivation function is more complex than just a hash $\endgroup$ – Richie Frame Mar 17 '18 at 11:34
  • $\begingroup$ @RichieFrame Are you therefore saying that if BIP32 used keccak256 instead of HMAC-SHA512 for the CKDF, it would be flawed? Are you able to specifically state why please? $\endgroup$ – knaccc Mar 17 '18 at 11:46
  • $\begingroup$ No. Different hash functions work differently internally, HMAC performs hashing of the key to create an unknown IV. If you used Keccak you just have to do it differently, but the functions they are using are not just HMAC, they are doing other things to the data before and after $\endgroup$ – Richie Frame Mar 17 '18 at 12:09
2
$\begingroup$

Let $P$ be the standard base point of order $\ell$ on some elliptic curve, and $H\colon \{0,1\}^* \to \mathbb Z/\ell\mathbb Z$ be a uniform random function. Let $[\alpha]Q$ denote scalar multiplication by $\alpha \in \mathbb Z/\ell\mathbb Z$ of the point $Q$ on the curve.

Suppose the adversary is given a collection of values $\{[H(k_i)]P\}_{i = 1}^n$ for $n$ uniform random keys $k_i$ in some 128-bit space. (This is a weaker adversary than, e.g., the Diffie–Hellman adversary who also learns $[H(k_i)]Q$ for any $Q$ of their choice, but let's focus on the weaker adversary first.) Their goal is to compute any one of the $H(k_i)$.

What can they do?

  • Suppose they apply Pollard's $\rho$ algorithm to find any one of the scalars $H(k_i)$ directly, or a modern variant of it. The expected number of elliptic curve additions before they can get the first $k_i$ is $\sqrt{\ell\pi/4}$. When $\ell \approx 2^{256}$, as in, e.g., Curve25519 or NIST P-256, this cost is pretty much guaranteed to exceed $2^{128}$ bit operations, so it is infeasible. The expected cost of breaking all of the $k_i$ is only $\sqrt{n}$ times more than the cost of breaking at least one of the $k_i$, but the cost of the first one is still $\sqrt{\ell\pi/4}$ additions or at least $2^{128}$ bit operations when $\ell\approx 2^{256}$.

  • Suppose they apply Oechslin's rainbow tables to invert the function $F\colon k \mapsto [H(k)]P$ as a black box. A machine parallelized $n^2$ ways has probability $p$ of finding the first of $n$ keys in the time for approximately $2^{128} p/n^3$ evaluations of $F$, or in the area*time cost of $2^{128} p/n$ evaluations of $F$, which costs one hash and one scalar multiplication. The individual cost of evaluating $F$ is a lot more than an elliptic curve addition—but only a constant multiple, so the net expected area*cost to find the first key is likely to be substantially less than Pollard's $\rho$ once you get to, say, a million users.

What can you do to drive up the adversary's cost for a multi-target attack?

  • You can drive the keys up to 256-bit spaces so that the cost of Oechslin's rainbow tables exceeds the cost of Pollard's $\rho$ for all imaginable numbers of users.

  • You can separate the input space by using a globally unique name for each user and computing $H(k_i, \mathit{username}_i)$ instead of $H(k_i)$ as the $i^{\mathit{th}}$ user's secret scalar.

    Make sure to uniquely map the passphrase and username into the input of $H$, so that if Bob Willy's passphrase is ‘Wonka’ and Bob's passphrase is ‘Willy Wonka’ then they don't end up with the same key. Better, if your protocol is shared by multiple applications (like Signal and WhatsApp) with independent user namespaces, name the application in the hash too.

    Of course, if this is a cryptocurrency where a user's identity is just their public key and there is no other notion of namespace and you're trying to avoid any additional storage alongside the key, this doesn't help!

$\endgroup$
  • $\begingroup$ Please could you clarify what you mean by "drive the keys up to 256-bit spaces"? Do you mean that you'd just simply use more than 128 bits of entropy? $\endgroup$ – knaccc Mar 19 '18 at 15:37
  • $\begingroup$ @knaccc Yes, that's what I mean. $\endgroup$ – Squeamish Ossifrage Mar 19 '18 at 15:46
3
$\begingroup$

The safe way to generate a large amount of entropy from a small seed is to use a CSPRNG. Most CSPRNGs in practice use a stream cipher at their core to expand a small amount of input entropy into a large keystream. The way this is done (and the process of seeding and re-seeding the generator) is very important to security, so it's best to use an existing library or your operating system's built-in CSPRNG.

The multi-target attacks are better described in DJB's page on batch attacks. They're an issue whenever there are a large number of users each with a large number of keys. The chances that an attacker will guess at least one key that at least one user has used can be quite large, even though the chance that the attacker will guess one specific key of any one specific user is still minuscule.

Batch attacks are an issue for AES-128 because 128-bit AES keys are often generated in the ephemeral key exchanges of TLS sessions. Every time a user goes to a new https webpage a new key is generated with them. Consider all users across all https pages on the internet and the chances that the NSA/PLA/FSB/Mossad/etc will be able to decrypt at least some traffic are actually quite high.

Batch attacks are much less of an issue for ECC keys, as they are often quite long term. There simply aren't enough private keys for Monero wallets for this to be a significant issue.

$\endgroup$
  • $\begingroup$ BIP 32 generates the master secret key as the first 256 bits of HMAC-SHA512("Bitcoin seed", 128 bits of entropy). If this is an acceptable practice, and given that keccak is not vulnerable to length extension attacks, would you agree that simply doing keccak-256("Monero seed" || 128 bits of entropy) would be an acceptable practice for generating a wallet's ECC private key? (See the "Master key generation" section here: github.com/bitcoin/bips/blob/master/bip-0032.mediawiki ) $\endgroup$ – knaccc Mar 17 '18 at 8:42
  • $\begingroup$ Keccak alone isn't quite equivalent to HMAC. KMAC is. SP 800-185 has the specification. $\endgroup$ – SAI Peregrinus Mar 17 '18 at 14:50
  • $\begingroup$ This doesn't really answer the question: What is the adversary's cost to break any one of $n$ keys with probability $p$? Is it the same as for $k \mapsto \operatorname{AES-128}_k(182758)$, which is significantly less than for $k \mapsto \operatorname{X25519}(k, 9)$ for values of $n \ggg 1$ at any fixed $p$? Is there a way to thwart multi-target attacks without requiring longer passphrases? $\endgroup$ – Squeamish Ossifrage Mar 17 '18 at 16:42
  • $\begingroup$ There is no ‚safe‘ key stretching, you always have to deal with the limited keyspace. $\endgroup$ – eckes Mar 19 '18 at 17:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.