1
$\begingroup$

A safe way to generate a 256 bit ECC key from 128 bits of entropy is to use a CSPRNG, according to this answer: https://crypto.stackexchange.com/a/56551/43864

However, it's difficult to find a cross language, cross platform CSPRNG that guarantees to produce the same result across all implementations.

What would be a safe alternative to using a CSPRNG? Ideally the answer would involve just the use of SHA3-256, for which implementations are widely available.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Do you have any specific examples of CSPRNGs that aren't repeatable? This would imply that different AES implementations do not adhere to the standard test vectors. That would also imply that a router's embedded WEP can't talk to my Linux /Windows boxes as they all used RC4, which was a CSPRNG. $\endgroup$
    – Paul Uszak
    Commented Mar 18, 2018 at 12:49
  • $\begingroup$ @PaulUszak I've searched for implementations of SHA1PRNG or any other CSPRNG for Javascript, and there doesn't appear to be one. The Web Crypto API does not allow the seed to be specified for the Crypto.getRandomValues() method. Other people seem to have this issue too: crypto.stackexchange.com/questions/11444/… $\endgroup$
    – knaccc
    Commented Mar 18, 2018 at 22:18
  • $\begingroup$ Ah. I don't do JavaScript, sorry. But I would post /ask e-sushi why he recommends against JavaScript crypto. There might be fundamental reasons why it's a bad idea... $\endgroup$
    – Paul Uszak
    Commented Mar 18, 2018 at 22:48
  • 1
    $\begingroup$ I think a big element to this question is the widespread ambiguity and resulting confusion over what the term "CSPRNG" means. Stream ciphers are commonplace, produce consistent results across implementations, and is in a minimal sense a "CSPRNG." $\endgroup$
    – Luis Casillas
    Commented May 4, 2018 at 20:41

3 Answers 3

Reset to default
2
$\begingroup$

A simple, good enough method is to apply SHA-256 to

  • a per-user 128-bit secret full-entropy key
  • a fixed-size constant pepper (constant for a given application, mildly confidential that is distributed only on need-to-know basis; distribution in code is not ideal, but better than no pepper, and there is little alternative.
  • the user ID (can be variable-length)

and use the result as the 256-bit private key. An academically better option is SHA-3-256, or HMAC-SHA-256 with secret∥pepper the HMAC key, because that's a stronger keyed PRF.

Introducing the user ID is useful to prevent multi-target attack (attempting to find a private key matching any of many public keys). Without this, the expected effort for breaking one random private key among those of $n$ users is $2^{127}/n$ operations (hash, compute public key, find a match among the $n$ public keys), almost $n$ times lower than $2^{127}$ operations (hash, compute public key, compare to the one public key) with the user ID hashed.

Depending on perspective, what's proposed could be criticized as giving equivalent security as a full 256-bit random private key, or not:

  • The best additional attack enabled is brute force search of the 128-bit seed, which requires an expected $2^{127}$ tests, each with a hash and some nontrivial ECC operation. That additional attack does not improve when attacking multiple targets. Other attack on ECC with 256-bit public key (Polard's Rho..) essentially breaking the discrete logarithm have comparable expected cost (like $2^{129}$) measured in number of some (other) elementary operations (I'm unsure about their multi-target status).
  • But if we dive deeper: if we want that odds of success for an adversary doing a certain amount of work be below some low residual probability of break for a given of operations (say $\epsilon<2^{-30}$ for $2^{100}$ operations), then we have a problem: brute force search of the per-user 128-bit secret has $\epsilon\approx2^{128}/n=2^{-28}$ (not meeting our residual probability gooal), while for Pollard's Rho and friends $\epsilon\approx2^{257}/{n^2}=2^{-57}$ (acceptable with flying colors). And there is the additional, independent issue that perhaps the ECC cost for a brute force search can be lowered sizably with some pre-computations.

If we want an extra level of assurance, we can use an iterated hash function (PBKDF2, Bcrypt, Scrypt, Argon2, Balloon..) instead of a hash and get significant extra resistance to brute force search of the per-user 128-bit secret; like +20 bits of security for that attack.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. Since this is intended for an app, is it OK if the pepper is visible in the source code?. Secondly, I'm a little worried that people would criticise the use of only a 128 bit full entropy key when I could have used more entropy. Do you think this would be a valid criticism, or do you think I would be able to confidently say that 256 bits of entropy would be no better than 128 bits, given that ECC keys only have 128 bits of security? (See crypto.stackexchange.com/questions/26791/…) $\endgroup$
    – knaccc
    Commented May 4, 2018 at 11:19
  • $\begingroup$ Btw, how severe would the security impact be of eliminating the user ID component, and using only the per-user 128-bit secret full-entropy key to identify the user? Another way of asking this question would be to say: "Why are 128 bit Bitcoin wallet seeds enough, and why does e.g. Ledger use a 256 bit seed? Is that senseless?" $\endgroup$
    – knaccc
    Commented May 4, 2018 at 12:20
  • $\begingroup$ @knaccc The impact of eliminating the unique user id is that the best generic multi-target attacks (‘brute force’), finding the key for at least one of many users at once, cost much less than $2^{127}$ bit operations for a 1/2 chance of success. See crypto.stackexchange.com/a/58669/49826 for more details and references. $\endgroup$
    – Squeamish Ossifrage
    Commented May 5, 2018 at 17:26
4
$\begingroup$

If you need a CSPRNG, there is no safe alternative.

Your assertions that “it's difficult to find a cross language, cross platform CSPRNG” and “SHA3-256, for which implementations are widely available” are contradictory. SHA3 implementations are not very common, whereas every cryptography library provides a CSPRNG. Furthermore, given a hash implementation, it is fairly easy to construct a CSPRNG: use either Hash_DRBG or HMAC_DRBG, both defined by NIST SP 800-09A. Hash_DRBG is slightly faster and HMAC_DRBG is slightly more resistant in case a weakness in the hash algorithm is found.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for an excellent answer. What I meant was that although one can find a CSPRNG on every platform, as far as I can tell it's hard to find an implementation that guarantees to produce the same result from identical IVs on every platform and every language. Implementing my own HMAC_DRBG using a SHA3 implementation sounds like rolling my own crypto, so I'll leave the question open a little longer in case someone has a simpler solution. I was hoping the answer would be as simple as just using SHA3-256 n times on the entropy. $\endgroup$
    – knaccc
    Commented Mar 18, 2018 at 12:07
  • 1
    $\begingroup$ @knaccc If you use a specific CSPRNG algorithm (e.g. “Hash_DRBG using SHA3-256”, it'll give the same results on every implementation. “Using SHA3-256 n times” is a very rough approximation of what Hash_DRBG does — if you want to do it right, use Hash_DRBG. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Mar 18, 2018 at 12:22
  • $\begingroup$ What I don't really understand is the advantage of using HMAC_DRBG when, for example, BIP32 simply generates an ECC key as the first 256 bits of HMAC-SHA512("Bitcoin seed", 128 bits of entropy) github.com/bitcoin/bips/blob/master/… If it's good enough for BIP32, shouldn't that be good enough for me? Why wouldn't just one round of SHA3-256 on the 128 bits of entropy be good enough? $\endgroup$
    – knaccc
    Commented Mar 18, 2018 at 12:58
  • 1
    $\begingroup$ @knaccc If you want output that's smaller than the hash, then a simple hash or HMAC is ok. A CSPRNG gives you unlimited output. Depending on what curve you're generating the point on, you may or may not need more than the length of the hash. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Mar 18, 2018 at 14:24
  • 2
    $\begingroup$ @knaccc Yes. Oh, and if you're using SHA3, then as suggested by Squeamish Ossifrage, you can use SHAKE instead of Hash_DRBG or HMAC_DRBG. I recommend calling SHAKE or DRBG in your code, because otherwise if you ever change the curve and don't add the XOF/DRBG at this point there's a risk that your key generation code will become disastrously wrong. The code size is very small and most libraries do provide Hash_DRBG or HMAC_DRBG. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Mar 19, 2018 at 8:03
2
$\begingroup$

You can just use any extendable-output function like SHAKE128 or HKDF-SHA256 for this purpose. For the specific size of 256 bits, even SHA-256 or SHA3-256 would work just fine: $$k = \operatorname{SHA-256}(\text{‘my application 128-bit key derivation’} \mathbin\Vert p).$$ This is effectively a kind of single-output CSPRNG, which is standard and easy to implement and will behave the same way on all platforms.

This isn't the US federal government standard procedure from NIST—to approximate one standard procedure of sampling twice the bits you need, you could use SHA-512 instead; for the alternative standard procedure of rejection sampling, in principle you'll need a CSPRNG with arbitrarily many 256-bit outputs, but in practice you will never need more than one output. (In this case the benefit of the standard procedure is negligible, but maybe you don't want to risk it when you're cutting corners already so you keep the auditor's job easy.)

Caveat: I am taking as a premise that you want to select users' keys from among only $2^{128}$ distinct scalars, and not addressing the cost of a multi-target attack with high probability of success against any one of your users. I would not recommend this! At the very least, you should include a unique per-user id in the hash too, if you insist on passwords with <256 bits of entropy.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The reason for asking the question is that I saw that BIP32 only uses a 13 word 128 bit seed to generate a 256 bit ECC key. I also saw that 256 bit ECC keys only actually have 128 bits of security ( crypto.stackexchange.com/questions/26791/… ). I was therefore guessing that the use of a 128 bit seed instead of a 256 bit seed was because there would be no point in using a seed with 256 bits given that the maximum security of an ECC key is only 128 bits. Is my reasoning correct? $\endgroup$
    – knaccc
    Commented Mar 18, 2018 at 23:11
  • $\begingroup$ I've also been told that multi-target attacks would not be a problem with ECC keys, especially if I'm only using the entropy to generate a tiny number of keys. See crypto.stackexchange.com/questions/56541/… $\endgroup$
    – knaccc
    Commented Mar 18, 2018 at 23:14
  • 1
    $\begingroup$ @knaccc The reasoning in crypto.stackexchange.com/a/56551/49826 does not support the conclusion that multi-target attacks are not a problem—unless I'm missing something obvious, it seems to me that inverting $k \mapsto \operatorname{X25519}(H(k), 9)$ for uniform 128-bit $k$ should scale like inverting $k \mapsto \operatorname{AES}_k(1283748)$ for uniform 128-bit $k$, using rainbow tables, qualitatively different from—and faster at first success than—using Pollard's $\rho$ to invert $n \mapsto \operatorname{X25519}(n, 9)$ for uniform 256-bit $n$. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 19, 2018 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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