# Can you help me clear a confusion about small subgroup attack on HMQV?

First,i want to show you with a picture how the HMQV works.

There are some notations you might not familiar, it doesn't matter. I just want to show you the procedure.

Next it's an attack on HMQV

Suppose G is the subgroup of Fp* with the order q, q is a prime. And t is an factor of (p-1)/q . G' is another subgroup of Fp* with the order t.

the attack proceeds as follows

1. adversary M chooses an elemen γ from G' with the order t.

2. then, M chooses a,x uniformly at random in [1,t-1], calculate A=γa , X=γx ; M impersonates party A to send (hat(A),hat(B), X) to party B.(hat(A) means the identity of party A, so does hat(B))

3. when party B receives the message, he will compute the shared session key like this K=H((XAd)sB) where sB=y+eb (as in the HMQV)

4. then, M reveals party B's ephemeral private key y and session key K; Let β=XAdx+da, so K=H(βsB)

5. compute K'=H(βc),where c from 0...t-1, until K=K', so we get sB mod t

My confusion lies in step 5. In party B's view, X ,A and d are just numbers and he doesn't know the order of β — he also won't care about that. He just calculates the result of XAd and then implements K=H(βsB) sB=y+eb (as in the HMQV).

About the form, β=XAdx+da, but remember that party B doesn't know the order of γ so, he won't implement the reduction (x+da mod t). Even, he knows the t, he also won't implement the reduction because he does not have x,a. As to sB, party B just treats it as a number, he just calculates the value of βsB. And then hash that value to get K.

So, I think βc≠βsB⇒H(βc)≠H(βsB)⇒K≠K'.

I debated with others on this, but they all think I'm wrong! But as you can see my thought is very reasonable. Where on Earth is their problem? (in other words: What am I missing that they see?)

-
Have a look at eprint.iacr.org/2005/205.pdf which contains small-subgroup attacks on HMQV. –  minar Aug 1 '13 at 8:02
Look carefully at section 2.2.1. Your implication in bold is correct (unless you find a collision for $H$), now reverse it: $K=K' \Rightarrow \beta^c=\beta^{s_B}$. The last condition is equivalent to $c\equiv s_B\pmod{t}$ since $\beta$ has order $t$. So when $K=K'$, you learn the value of $s_B\pmod{t}$. –  minar Aug 1 '13 at 10:30
they are just numbers , how can they equal to each other? Maybe there some things about protocol implementation that i don't know... –  Alex Aug 1 '13 at 11:40
All computations are modulo $q$ and if $\beta$ has order $t$ modulo $q$ then $\beta^t\equiv 1 \pmod{q}$. As a consequence, you have equality of $\beta^c$ and $\beta^{s_B}$ (modulo $q$) when $c\equiv s_B \pmod{t}$. Example: $6^5\equiv 6^3\pmod{7}$. –  minar Aug 1 '13 at 15:46
thanks minar, i got it. the above you say "modulo $q$", i think it is "mod $p$". –  Alex Aug 5 '13 at 1:12