Determine secure amount of private key modulo bias

[paulmillr]

For a curve like secp256k1, which has 32-byte (256-bit) $G$, we take 32+8 bytes (256+64 bits) from CSPRNG and mod-divide it by curve order $n$. This follows FIPS guidelines and has $2^{-64}$ bias:

https://github.com/paulmillr/noble-curves/blob/8c48abe16acddaaabfaf75b9d669f515f129a67d/src/abstract/weierstrass.ts#L847-L855

1. FIPS 186 B.4.1 was replaced by FIPS 186-5 in Appendix A.2.1 this year. The amount of bytes was changed a bit
2. It was suggested by an outside auditor that this could be adjusted to match the security level of a curve, as per draft-irtf-cfrg-hash-to-curve:

To control bias, hash_to_field instead uses random integers whose length is at least ceil(log2(p)) + k bits, where k is the target security level for the suite in bits. Reducing such integers mod p gives bias at most 2^-k for any p; this bias is appropriate when targeting k-bit security. For each such integer, hash_to_field uses expand_message to obtain L uniform bytes, where

L = ceil((ceil(log2(p)) + k) / 8)

These uniform bytes are then interpreted as an integer via OS2IP. For example, for a 255-bit prime p, and k = 128-bit security, L = ceil((255 + 128) / 8) = 48 bytes.

I think it's fine to adjust the amount of bytes. Several questions still arise:

1. What does a $2^{-64}$ bias actually mean? Is there any realistic attack? How many keys would an attacker need to walk through before gaining meaningful advantage?
2. How was the formula from hash-to-curve draft calculated? Why does it consider 384 bits from csprng "match 128-bit security" for 256-bit $G$?
3. What other standards are out there with regards to bias?
4. DJB used $2^{-259}$ bias for eddsa nonce: r = mod(sha512(prefix, msg), ed25519.l). Why not $2^{-128}$?
5. How should a generic rule look like? We can't use Fp.BYTES + Math.ceil(Fp.BYTES/2), because it's field - not curve group.
   • For ed25519, which has $P = 2^{255}-19$ and $n=2^{252}+27742317777372353535851937790883648493$ that would mean we'll fetch 253+127=380 bits - which is rounded to 384 (48 bytes)

[sylvainpelissier]

Hi, Thank you for opening the discussion. Here is an answer of point 3 for hash functions: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf at Appendix B. They advised to use 128 bits with a similar formula.

[sylvainpelissier]

Here are my ideas for the other points:

1. I do not know if there is realistic attack or not. The point is that according to the paper by Bier et al mentioned in the IRTF Draft, in Appendix C.3, the condition to have the function hashToPrivateScalar behaving like a random oracle and thus outputting uniformly distributed values according to the security level you have is to choose k as explained early according to your security level. There is also an extension to the NIST curves in appendix C.4 which explains the numbers in FIPS 186-5.

2. For a 256-bit group you have about a 128-bit security level. Then according to the previous formula we have $L = 256 + 128 = 384$ bits. It is the output length you need out of the CSPRNG.

3. You can choose bigger values, the bias will be smaller.

4. You may add a security parameter to the function or does Fp.BYTES + Math.ceil(Math.log2(CURVE_ORDER)/(2*8)) work ?

[paulmillr]

For 4 I don't see how $Fp$ is related to the security at all. I think the only thing we should base it on is CURVE_ORDER aka $Fn$ aka nByteLength which we already have for all curves.

[sylvainpelissier]

Yes you are right it should be the order of the group.

[matthiasgeihs]

Regarding 1.

A 2^-64 bias means that the statistical distance between the uniform distribution and the actual distribution (assuming a perfect underlying rng) is 2^-64 (see the appendix of https://eprint.iacr.org/2023/1254.pdf, for a derivation of this bound).

Here is a survey on the consequences of partial information leakage: https://eprint.iacr.org/2020/1506.pdf.

That being said, I believe a bias of 2^-64 should be acceptable for all practical purposes!? (Even statistical security of 2^-40 can be considered practically secure.)

[paulmillr]

Thanks Matthias, that's very helpful.

[sylvainpelissier]

Is it solved by 1545230ee59b6e360f0e660cc2eb567d46ff3805 ?

[paulmillr]

We've decreased bias, yes, but the security story still needs to be understood.

[nflatrea]

Bias in the context of cryptographic key generation refers to the deviation from a perfectly uniform distribution when generating random numbers, which can have security implications.

I'm sure you already have most of the explanation, but here's mine, hoping it'll help :

What does bias actually mean? Is there any realistic attack? How many keys would an attacker need to walk through before gaining a meaningful advantage?

Bias refers to the statistical deviation from a perfectly uniform distribution. In the context of cryptographic key generation, bias can be problematic because it may introduce vulnerabilities. While a bias of 2^-64 might seem small, it could potentially be exploited by an attacker who has knowledge of the bias and can use it to their advantage.

To understand the implications, consider an attacker who can observe multiple key generation attempts. With a bias of 2^-64, an attacker might need to analyze around 2^64 keys before gaining a meaningful advantage. This is a massive number and generally considered secure for most practical purposes. However, it's essential to remember that security depends on multiple factors, including the cryptographic primitives used and the specific context of the application.

The security implications also depend on the nature of the attack. The papers you cited (e.g., https://eprint.iacr.org/2023/1254.pdf) delve into the consequences of partial information leakage. For practical security, a bias of 2^-40 is often considered secure. However, the level of security required depends on the specific use case.

We might also ensure entropy quality by collecting sufficient bits (B) from a high-entropy source. Use NIST SP 800-90B recommendations to estimate the entropy. If collected entropy is H bits, the min-entropy is something like E_min = -log2(2^(-H/B)).

How was the formula from hash-to-curve draft calculated? Why does it consider 384 bits from CSPRNG to match 128-bit security for a 256-bit curve?

The formula in the hash-to-curve draft calculates the number of bits needed from the CSPRNG to achieve a specific level of security. It takes into account the size of the prime (p) for the elliptic curve and the desired security level (k bits). The formula for L is:

L = ceil((ceil(log2(p)) + k) / 8)

For a 256-bit curve with 128-bit security (k = 128), the formula becomes:

L = ceil((ceil(log2(2^256)) + 128) / 8) = ceil((256 + 128) / 8) = ceil(384 / 8) = 48 bytes.

This calculation ensures that the randomness obtained from the CSPRNG is sufficient to provide a 128-bit security level for the 256-bit curve.

What other standards are out there with regards to bias?

There are various standards and recommendations related to bias in cryptographic applications. For example, NIST's guidelines for cryptographic algorithms (e.g., FIPS 140-2) provide recommendations for generating random numbers with minimal bias. Additionally, standards such as RFC 6979 offer deterministic approaches for generating cryptographic nonces, reducing the risk of bias. You can also refer to academic papers and recommendations from organizations like the IETF for more specific guidance.

DJB used bias for eddsa nonce: r = mod(sha512(prefix, msg), ed25519.l). Why not?

Bernstein used bias in the context of EdDSA (Edwards-curve Digital Signature Algorithm) to address concerns about the security of nonces. In the case of EdDSA, it's important to avoid reusing nonces to prevent certain attacks. The modulo operation used in generating 'r' ensures that nonces stay within a specific range and avoids any bias that could be introduced by raw CSPRNG output.

How should a generic rule look like? We can't use Fp.BYTES + Math.ceil(Fp.BYTES/2) because it's field - not curve group.

A generic rule for obtaining random values for cryptographic operations, such as private key generation, should consider the following:

• The size of the prime (p) for the elliptic curve in use.
• The desired security level (in bits).
• The specific cryptographic context (e.g., private key generation, nonce generation).

As demonstrated in the hash-to-curve draft, we could use a formula that calculates the number of bytes (or bits) needed from the CSPRNG based on the curve's size and the desired security level. It shouldn theoretically, ensure that the generated random values meet the required level of security and avoid biases.

Mathias and Silvain provided some valuable insights, and you can refer to the provided papers for further details.

To avoid bias inside the randomness extraction function (e.g., HMAC-DRBG), I'd suggest, analyzing it's properties. We need to ensure that the function's output is statistically uniform, ideally using statistical tests like NIST SP 800-22.

[paulmillr]

Bernstein used bias in the context of EdDSA (Edwards-curve Digital Signature Algorithm) to address concerns about the security of nonces. In the case of EdDSA, it's important to avoid reusing nonces to prevent certain attacks. The modulo operation used in generating 'r' ensures that nonces stay within a specific range and avoids any bias that could be introduced by raw CSPRNG output

But there IS bias in eddsa. It's $2^{-259}$.

[nflatrea]

Oops ! You're right.

But I don't think it's always the case, no ? I might be wrong but... In this case, the hash function and modulo operation in the 'r' nonce generation might be the source issue.

r = sha512(prefix, msg) mod ed25519.l

Where,

• 'r' is the nonce,
• 'prefix' is a user-defined prefix (additional data),
• 'msg' is the message to be signed,
• 'ed25519.l' represents the order of the curve.

To my understanding, the 'mod' operation introduces this bias. In practice, the 2^(-259) bias in EdDSA is generally considered negligible and doesn't pose significant security risks. But using SHA-512 for nonce generation in EdDSA may introduce potential issues related to those.

Again, I might be wrong and I'd be happy to be corrected.

SHA-512 has a fixed output length of 512 bits (64 bytes) meaning that regardless of the input size, the hash function always produces a 512-bit output. The nonce 'r' is calculated modulo 'ed25519.l' to ensure that it falls within a specific range. If the SHA-512 output is too long or contains more bits than needed, this can introduce biases.

When you take the modulo of a large number ('sha512(prefix, msg)') by a smaller number ('ed25519.l'), some values in the output range may have a higher probability of occurrence than others. This introduces bias, albeit very small, into the nonce generation process.

The bias can be quantified as 2^(-259), meaning that some nonces are slightly more likely to be selected than others, which could theoretically be exploited by an attacker.

As always just giving info, I forgot a lot about EdDSA, I need to restretch my brain 😅

[suchislife801]

Understanding Bias in Cryptographic Keys

What is Bias in Cryptography?

• Definition: In cryptographic contexts, 'bias' refers to the deviation from perfect randomness in key generation. It's crucial because even a slight bias can make a system vulnerable to attacks.
• Risk: A biased key generation can lead to patterns or predictability. An attacker might exploit this to reduce the keyspace they need to search, potentially breaking the cryptographic system.

Bias in Different Key Generation Methods

1. FIPS 186-5 Appendix A.2.1

   • Approach: It suggests using random integers of length ceil(log2(p)) + k bits. Reducing these mod p yields a bias of at most 2^-k. This aligns with targeting k-bit security.
   • For 256-bit Curve: If k = 128-bit security, for a 255-bit prime p, L = ceil((255 + 128) / 8) = 48 bytes.

2. DJB's Approach for EdDSA (e.g., Ed25519)

   • Method: r = mod(sha512(prefix, msg), ed25519.l).
   • Rationale: This method introduces negligible bias. The SHA-512 ensures a wide dispersion over the group, and the modulo operation with the large prime group order (ed25519.l) ensures uniform distribution.

Analyzing the Bias

• Attack Feasibility: To gain an advantage, an attacker would typically need to analyze a vast number of keys, often impractical with current technology.
• Realistic Threat: The actual risk depends on the specific curve and key generation method. For well-designed systems, the risk is often theoretical rather than practical.

Generic Rule for Key Generation

• Approach: Use a function of the curve's security level and field/group size.
• Example for Ed25519:
  • Bits Needed: 253+127=380 bits, rounded to 384 bits (48 bytes).
  • Rationale: Aligns with the security level and accommodates for the curve's properties.

Conclusion

• Adjusting Bytes: Modifying the byte amount in key generation to match security levels as per new standards is acceptable.
• Standard Variance: Different standards (like FIPS, DJB's approach) have their reasoning and are designed to balance security and practicality.

Code Implementation (Conceptual)

function generateSecureKey(curveProperties, securityLevel) {
    const requiredBits = Math.ceil(Math.log2(curveProperties.prime)) + securityLevel;
    const requiredBytes = Math.ceil(requiredBits / 8);
    const randomBytes = getRandomBytes(requiredBytes); // CSPRNG
    const key = reduceModPrime(randomBytes, curveProperties.order);
    return key;
}

Note: This is a high-level conceptual representation and needs to be adapted to specific curve properties and cryptographic libraries.

[paulmillr]

Your replies don't answer the questions. I highlight the important parts:

1. What does a $2^{-64}$ bias actually mean? Is there any realistic attack? How many keys would an attacker need to walk through before gaining meaningful advantage?
2. How was the formula from hash-to-curve draft calculated? Why does it consider 384 bits from csprng "match 128-bit security" for 256-bit $G$?
3. What other standards are out there with regards to bias?
4. DJB used $2^{-259}$ bias for eddsa nonce: r = mod(sha512(prefix, msg), ed25519.l). Why not $2^{-128}$?
5. How should a generic rule look like? We can't use Fp.BYTES + Math.ceil(Fp.BYTES/2), because it's field - not curve group.
   • For ed25519, which has $P = 2^{255}-19$ and $n=2^{252}+27742317777372353535851937790883648493$ that would mean we'll fetch 253+127=380 bits - which is rounded to 384 (48 bytes)

To summarize:

1. Provide realistic attacks and key bruteforce calculation
2. Provide other standards for bias management
3. Understand why there is a biased nonce in eddsa and what consequences it may have e.g. https://eprint.iacr.org/2019/023. Nonce - not key.
4. Understand if it's field OR group byte length, and if it's group, understand how it will work with P521, BLS12-381, BW, and all kinds of other curves. Create an exact generic rounding formula. Round to how many bytes? etc

[suchislife801]

I understand your questions better now.

1. Bias in Cryptography

• Meaning: In cryptographic key generation, 'bias' refers to a deviation from an ideal distribution, where each possible key should have an equal chance of being chosen. If some keys are more likely than others, the system is biased.
• Realistic Attacks and Key Brute-force Calculation:
  • Scenario: If a key generation process is biased, an attacker might exploit this to reduce the effective keyspace.
  • Calculation: The number of keys an attacker needs to walk through depends on the degree of bias. If the bias is slight, the number could be astronomically high, making a practical attack infeasible. Precise calculations would require a detailed analysis of the bias's nature and magnitude.

2. Formula from Hash-to-Curve Draft

• Calculation Basis: The formula ceil((ceil(log2(p)) + k) / 8) ensures that the generated number has enough entropy to match the desired security level.
• For 256-bit curve with 128-bit security: The formula calculates to ceil((255 + 128) / 8) = 48 bytes. This is to ensure that the randomness covers the entire range of the curve and has additional bits to meet the 128-bit security strength.

3. Other Standards for Bias Management

• Examples:
  • NIST SP 800-90A: Provides guidance for Cryptographic Random Number Generators.
  • FIPS 140-2/3: Sets standards for cryptographic modules, including aspects of key generation and randomness.

4. Biased Nonce in EdDSA

• Example in EdDSA (Ed25519): The biased nonce generation (mod(sha512(prefix, msg), ed25519.l)) in EdDSA is considered secure due to the high entropy provided by SHA-512 and the large prime group order.
• Consequences: Research like IACR's Eprint 2019/023 discusses potential vulnerabilities, but they often require specific conditions or weaknesses in implementation rather than inherent flaws in the concept.

5. Generic Rounding Formula for Various Curves

• Field vs. Group Byte Length:

  • Field Size: Relates to the underlying mathematical field of the curve.
  • Group Size: Relates to the order of the curve, often a large prime number in ECC.

• Generic Formula:

  • For Security Level ( k ): Use ceil((bitLengthOfGroup + k) / 8) bytes.
  • For Different Curves (e.g., P521, BLS12-381): The formula adapts to each curve's specific group order and desired security level.

• Example Application:

  • For Ed25519 (253-bit group): ceil((253 + 127) / 8) = ceil(380 / 8) = 48 bytes.

Conclusion

• Customization for Each Curve: The exact byte count for randomness in key generation must be tailored to the specific curve and security requirements.
• Security Considerations: While the bias in some designs is theoretically present, the practical implications for security depend heavily on the specifics of the implementation and the magnitude of the bias.

[paulmillr]

Do you copy this from chatgpt?