0
$\begingroup$

This is the attack I am talking about - Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation?

An elliptic curve group of order $8p$ where $p$ is a prime.

Let $G$ be the generator of the subgroup of order $p$. For ECDH, Alice sends $aG$ to Bob & Bob sends back $h$ instead of $bG$ where $h$ is point on the smaller subgroup of order $8$.

I understand the attack conceptually, I think. I wanted to try it out in a small group of Integers $\pmod {8p}$ instead of a similar elliptic curve group so it's easy to understand.

So I chose $p=11$ & used the group $Z/88Z$. The elements in this group which have order $11$ are these $\{8, 16, 24, 32, 40, 48, 56, 64, 72, 80\}$. All these are multiples of $8$. And the subgroup of order $8$ has these elements - $\{11, 33, 55, 77\}$. All these are multiples of $11$.

So generator $g$ will be a multiple of $8$ & $h$ which is the bad element sent by Bob will be a multiple of $11$. So when Alice calculates $ahg \pmod {88}$, it is always going to be zero. I assume any $ahg$ which is $0$ will not be used by Alice. Isn't that a problem for the attack - that Alice's secret key will always be $0$ & thus the attack will not happen.

So is this attack only valid for elliptic curve groups? I can't think of a reason why. Or am I doing something wrong?

$\endgroup$

1 Answer 1

2
$\begingroup$

Or am I doing something wrong?

You're model of what happens within Diffie-Hellman is not correct.

So generator $g$ will be a multiple of $8$ & $h$ which is the bad element sent by Bob will be a multiple of $11$.

Good so far.

So when Alice calculates $ahg \pmod{88}$,

That's where you are mistaken; Alice doesn't compute that; instead, she computes $ah \pmod{88}$. That is one of 0, 11, 22, 33, 44, 55, 66, 77, depending on $a \bmod 8$ (assuming Bob selected an $h$ of order 8; if he selected an $h$ of order 1, 2, 4, some of these can't happen).

$\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.