I am reading collin boyd textbook to learn MTI key agreement and various attacks on them . I encountered two such attacks called Small sub group attack and Lim-Lee attack where in

Small sub group attack : sub group works on the whole group itself (p-1) and reducing search space by pushing the value ( w = p-1/r. , powering with w) to a small order and then conducting exhaustive search among elements which has this order in the whole group enter image description here

Lim -Lee :

enter image description here

  • $\begingroup$ The first one is a tree party, in the second, party C uses the small group to extract information. I think you need to separate this question. Pohlig Hellman and small subgroup attacks $\endgroup$
    – kelalaka
    Commented Apr 7 at 11:27

1 Answer 1


In the first instance we have two legitimate users $A$ and $B$ attempting to establish an ephemeral one-time shared secret key using their both static long term public private pairs $(x_A,y_A=g^{x_A})$ and $(x_B,y_B=g^{x_B})$ and short term ephemeral values $r_A$ and $r_B$. We assume that $y_A$ and $y_B$ have been pre-shared and the intended protocol is intended to settle on the shared ephemeral key $g^{x_Ax_Br_Ar_B}=y_A^{x_Br_Ar_B}=y_B^{x_Ar_Ar_B}=z_A^{r_B}=z_B^{r_A}$ where $z_A=y_A^{x_Br_B}$ and $z_B=y_B^{x_Ar_A}$ with information exchanged as follows $${{\tiny z_A}\atop\longrightarrow}$$ $${{\tiny z_B}\atop\longleftarrow}.$$

The scheme is attacked by the active adversary $C$ who cause both sides to compute a shared secret value with low entropy via a man-in-the-middle attack. $C$ achieves this by replacing $z_A$ and $z_B$ with their $w$th powers (which both lie in a subgroup of order $r$ so that the final shared secret value lies in subgroup of order $r$.

In the second instance, the attack is on an authenticated key exchange algorithm per section 2.2 of the Lim Lee paper. The protocol again uses long-term static pairs $(x_A,y_A=g^{x_A})$ and $(x_B,y_B=g^{x_B})$ and short term ephemeral values $r_A$ and $r_B$. We again assume that $y_A$ and $y_B$ have been pre-shared. The ephemeral shared value $g^{x_Ar_B+x_Br_A}$ is intended to be formed with information exchanged $${{\tiny t_A=g^{r_A}}\atop\longrightarrow}$$ $${{\tiny t_B=g^{r_B}}\atop\longleftarrow}.$$

In this case the user $C$ is attempting to obtain information about the long term secret value $x_B$ by pretending to be a legitimate user. They generate $t_A$, but instead transmit $\beta t^a$ which lies in a coset of the subgroup of order $q$ rather the subgroup itself. This causes $B$ to compute a version of the shared secret value that is shifted by an amount $x_B\mod r$. By exhausting over possible shifts, $C$ can then learn $x_B\mod r$. Repeating this for several $r$ values could be enough to recover $X_B$ itself.

Comparing the two attacks we see that the first is an active ephemeral shared-key compromise on an exchange where both users are legitimately fulfilling their roles; the second is part of an attack to recover a users static private key by $C$ pretending to by a legitmate user, but abusing their role.

  • $\begingroup$ Lim Lee attack is still confusing , if its possible can you elaborate more ? $\endgroup$ Commented Apr 8 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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