3
$\begingroup$

The specification for a project I'm working on says to use elliptic curve Diffie-Hellman for key exchange, specifically using the secp224r1 curve. In the notes it is stated:

take the last 16 bytes of the shared secret byte array (do not use the first 16 bytes — those are not as uniformly distributed as the last 16 bytes!).

So my questions are:

  1. Why are the last 16 bytes more random than the first 16?
  2. Is this specific to the secp224r1 curve, or is it general to the elliptic curve version of the Diffie-Hellman algorithm?
$\endgroup$

migrated from security.stackexchange.com Feb 23 '18 at 9:11

This question came from our site for information security professionals.

  • $\begingroup$ I think you need to provide more context of how the secret shared byte array is constructed. If I'm right the quotation if from this site. Also, this is probably more on-topic at Cryptography. $\endgroup$ – Steffen Ullrich Feb 16 '18 at 18:52
  • $\begingroup$ significance. think of time, like "08:28:12.423"; are the mins, hours, or millis more uniform? $\endgroup$ – dandavis Feb 16 '18 at 18:53
  • $\begingroup$ Yep, that's the source. And I wasn't aware that there was a cryptography site (oops). $\endgroup$ – Matthew Cline Feb 16 '18 at 18:59
  • $\begingroup$ Truncating a raw DH shared secret is wrong. You should always hash it first (or if you want to be fancy, use a key derivation function like HKDF). So it looks like the designer of the protocol you're implementing didn't really know what they were doing. $\endgroup$ – CodesInChaos Feb 23 '18 at 10:47
  • $\begingroup$ It's not clear to me what they mean by the last 16 bytes. Do they mean the most significant or the least significant? And do they talk about just the x-coordinate of the shared secret (28 bytes) or an encoding of both x and y coordinate (2*28 bytes)? $\endgroup$ – CodesInChaos Feb 23 '18 at 10:51
1
$\begingroup$

Fix a short Weierstrass curve $y^2 = x^3 + a x + b$ over a finite field $\mathbb F_p$ of order $n$. (secp224r1 is an example, with $p = 2^{224} - 2^{96} + 1$, $a = -3$, and $b$ selected from an allegedly randomly chosen but unexplained seed passed through SHA-1.)

There are at most $n$ distinct values of $(x, y) = [\alpha \beta]G$ where $\alpha$ and $\beta$ are secret scalars in $\mathbb Z/n\mathbb Z$ and $G$ is the standard base point, all satisfying this equation.

If you choose uniformly among them, e.g. by choosing $\alpha$ and $\beta$ independently uniformly at random, and encode the pair $(x, y)$ into a $2 \lceil\log_2 p\rceil$-bit string, there is a trivial algorithm to distinguish the resulting string from a uniform random $2 \lceil\log_2 p\rceil$-bit string: decode it as a pair of integers $x$ and $y$ and test whether $y^2 \equiv x^3 + a x + b \pmod p$. So not only do the encoded values of $(x, y)$ cover a tiny fraction of the space of $2 \lceil\log_2 p\rceil$-bit strings—square root of the number of all such strings of that length—but they're trivial to distinguish from uniform random.

But that's partly because for each $x$, there's only at most two values of $\pm y$, so we can compress it into a much shorter $(1 + \lceil\log_2 p\rceil)$-bit string by storing only a bit to discriminate between the two possible values of $y$. Is that uniform random? No! If you decode $x$, you can test whether $x^3 + a x + b$ is a quadratic residue modulo $p$, which only about half of the integers are.

Distinguishers for the encoding of uniform random elliptic curve points were some of the first problems documented publicly in Dual_EC_DRBG[1], before everyone realized it was an obvious vector for a back door.

In general, when a random string is readily distinguishable from uniform like this, it is unfit to be used as a secret key in a cryptosystem whose contract demands a uniform random key—if you violate the security contract, it is null and void. But if the random string, while not uniform, nevertheless has high min-entropy, you can effectively get a uniform random string by hashing it, say with SHAKE256—what this means is that the best an adversary can do is test a guess about what the input might have been.

As for the low-order or high-order bits of $x$ and $y$? Don't bother; just hash them all. The cost of computing a hash like SHAKE256 is negligible compared to the cost of computing an elliptic curve scalar multiplication even on a small curve like secp224r1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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