Is it safe to generate two 256-bit ECC keys from 128 bits of entropy?

Question

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.

Answer 1

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!

Answer 2

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.