PIN-based authentication with Diffie-Hellman modular arithmetic

Question

Given $\text{server}_\text{pub}= ((2^\text{largerandom}\bmod P) \cdot (2^{\operatorname{intvalueof}(“XXXX”)} \bmod P)^\text{pin})\bmod P$

We know the $\text{server}_\text{pub}$ and we know that $\text{pin} \in [0,9999]$. What we want to find out is the pin. You could write it as $( (2^x \bmod P) \cdot Z ) \bmod P = \text{server}_\text{pub}$

$Z$ is one of 10K values.

I think somehow since $\text{pin} \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.

$(2^\text{largerandom} \bmod P) = (\text{server}_\text{pub}\cdot(2^{\operatorname{intvalueof}(“XXXX”)^{-\text{pin}}} \bmod P)) % prime$

So the question is: how can use the fact that $\text{pin} \in [0,9999]$ to determine the value $(2^\text{largerandom} \bmod P)$. Where $\text{largerandom}\in [1, P-1]$ and $P$ is a large RFC-based prime.

Answer 1

I think somehow since $pin \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.

Unless the random number generator is broken, there is no way to recover pin; this would remain true even if we were able to compute discrete logs mod $P$ (which we can't).

The issue is that the public key is generated as:

$$server\_pub = 2^{R + N \cdot pin} \bmod P$$

(where $R$ is largerandom, and N is the publicly known intvalueof("server") value)

Even if we were able to compute the discrete log, that would give us $R + N \cdot pin \bmod (P-1)/2$ [1]; however for any potential value of $pin$, there is a value of $R$ that gives us the value consistent with the observed server_pub; because $R$ is assumed to be (almost) uniformly distributed over $[0, (P-1)/2)$ [2], that observed public value gives us no information about the value of pin.

Our inability to compute discrete logs does not change the above reasoning.

---

[1]: why $\bmod (P-1)/2$? That's the size of the group that $2$ generates modulo this prime

[2]: in your code, $R$ is generated uniformly randomly in the code over $[1, P-1]$; that does mean that the possible value $R \equiv 0 \bmod (P-1)/2$ is less than any other value of $R$. This would, at extremely rare occasions, allow us to deduce that a specific pin value is somewhat less likely to be the correct value - however, this is so rare (probability of us being able to deduce that is approximately $1000/ P \approx 3 \cdot 10^{-613}$) that we can ignore that.