Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I need to use “ECDH with a cofactor key” for generating symmetric key. I have a fair idea on how ECDH works, but I don’t understand the cofactor part.

What is the difference between ”ECDH with a co-factor key” and ”ECDH without a co-factor key”?

Also, it would be great if you could point me to information related to the implementation itself.

Nota Bene: my related StackOverflow question got closed and I was advised to ask at Crypto.SE.

share|improve this question

1 Answer 1

First, a bit of background. If we refer to the size of an elliptic curve group as $n$, we select an elliptic curve with $n = hq$, where $q$ is a large prime, and $h$ is a small integer called the cofactor; it is typically either 1, 4 or 8. The values of $q$ and $h$ will be part of the curve definition.

As you know, with straight DH, we agree on a point $G$, Alice selects a random value $a$ and computes $aG$; Bob selects a random value $b$ and computes $bG$; they exchange values, and then Alice computes $a(bG)$, Bob computes $b(aG)$, and those are the same value.

When we use the cofactor variant of DH, the first part is exactly the same; Alice selects a random value $a$ and computes $aG$; Bob selects a random value $b$ and computes $bG$; they exchange values. However, Alice then computes $ha(bG)$, and Bob computes $hb(aG)$. That is, in the second phase, they internally multiply their random value by $h$ before doing the point multiplication.

Why do they do this? Well, it helps avoid a small potential data leakage if Bob doesn't play by the rules. If $h>1$, there are points with small order, we'll call such a point $H$ (there won't always be a point of order $h$, however to make this argument slightly simpler, we'll assume there is). Then, suppose an attacker didn't give Alice the value $bG$, he gave him the value $bG+H$. Alice would then compute $a(bG+H) = abG + aH = abG + (a \bmod h)H$. As Bob knows the value $abG$ (he does his half of the second phase honestly), he can compute Alice's shared secret with $h$ different alternatives, and so recover $a \bmod h$.

By internally multiplying by $h$ in the second phase, this doesn't happen; we have $ah(bG+H) = abhG + ahH = abhG$ (as the point $H$ is of order $h$), independent of what $a \bmod h$ is.

This isn't the only possible way to defend against this; Alice could also compute $q(bG)$, and verify that it's the point at infinity ($q(bG + H)$ won't be), however that's fairly expensive, while the cofactor method just uses two or three point doublings over the computations we would be doing for ECDH anyways.

Now, if this is the only place that Alice uses $a$ (that is, if she is using ephemeral ECDH), this leakage doesn't matter a bit - Bob already knows the shared secret, and he can't leverage that into any knowledge of any other secret. However, if Alice reuses her $a, aG$ pair for other exchanges, the leakage is there (and whether it's enough to worry about is another question entirely).

One last word of warning: when we compute the value $(ab)G$, we typically actually compute $(ab \pmod q)G$, as normally they're the same (and computing things $\bmod q$ makes things more efficient). However, this is one place where we don't; we really do formally compute $(ah)bG$, even if $ah > q$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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