5
$\begingroup$

Alice and Bob are using DHKE in the group $\mathbb{Z}_p^ * $, where $p = 1031 = 2 \cdot 5 \cdot 103 + 1$. Their generator $g = 2$, which generates a multiplicative group of order $515$ in $\mathbb{Z}_{1031}^ * $. This group has a subgroup consisting of $5$ elements $\{ 1,518,264 = {518^2},660 = {518^3},619 = {518^4}\} $. Eve uses this subgroup to find out DH keys exchanged by Alice and Bob. In one exchange, Alice sends ${2^a} = 919$ to Bob. Eve intercepts the message, raises $919$ to the power $103$ and gets $619\,\bmod \,1031$. Eve sends $A = 619$ to Bob. Bob replies by sending ${2^b} = 270$. Eve intercepts it, raises $270$ to the power $103$, gets $660\,\bmod \,1031$, and sends $B = 660$ to Alice. Eve now finds the integer value of DH key ${B^a} = {A^b}$ computed by Alice and Bob without knowledge of $a$ and $b$, and actually without any more computations modulo $1031$. Explain how this is possible, and give the value of the resulting DH key.

My solution:

Eve was smart enough to come up with a subgroup $S < \mathbb{Z}_{1031}^ * $ such that $\left| S \right| = 5$ and $S = \left\langle {518} \right\rangle $. By Lagrange theorem we know that all elements of $S$ must have an order $1$ or $5$. Thus it follows that $\left| 1 \right| = 1{\text{ and }}\left| {518} \right| = \left| {264} \right| = \left| {660} \right| = \left| {619} \right| = 5$. Furthermore, we know that $S = \left\langle {264,518,619,660} \right\rangle $.

Alice sends to Bob ${2^a} = 919$, when Eve stops the message she computes ${({2^a})^{103}} = {(919)^{103}} = 619 = {518^4}$ and hence Bob receives $619 = {518^4}$. Bob sends to Alice ${2^b} = 270$, when Eve stops the message she computes ${({2^b})^{103}} = {(270)^{103}} = 660 = {518^3}$ and hence Alice receives $660 = {518^3}$.

The value of the key is $$K = {B^a} = {660^a} = {518^{3a}} = {518^{4b}} = {619^b} = {A^b}$$Clearly the usage of much smaller subgroup with the following properties allow Eve to forge the message and limit a search domain to $5$ values. However, i do not understand how Eve can find the integer value of the key without knowing $a$ or $b$ and without more computations modulo $1031$.

For different values of $a$ and $b$ the generator of $S$ - $518$ will produce one of five possible values that will satisfy the equality. The only way i see Eve finds the key is by trying all five possible values (e.g small exhaustive search). In this way Eve does not need to do more computations modulo $1031$ as she knows the elements of $S$.

However the problem asks to give the value of the key. Does it mean that i have to try all $5$ values from $S$ or the key can be indeed determined uniquely without performing exhaustive search on $S$?

$\endgroup$
1
$\begingroup$

Does it mean that i have to try all 5 values from S or the key can be indeed determined uniquely without performing exhaustive search on S?

In the general case, you cannot determine the key without performing exhaustive search on $S$.

Small subgroup attacks aim to make the key belong to a small subgroup to make the exhaustive search feasible in practice. So by definition, usual small subgroup attacks require exhaustive search.

I posted something about Small subgroup confinement attack on Diffie-Hellman to fully understand the functioning of the attack, maybe it can help you.

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