I'm trying to reverse engineer a key exchange protocol which is based on the Diffie-Hellman key exchange scheme and faced with the following problem:

Let $g$ be the generator, $m$ the modulus.

Alice has a private key $a$ and computes her public key $A = g^a\pmod{m}$.
Bob has a private key $b$ and computes his public key $B = g^b\pmod{m}$.

During exchanges Bob generates password check signature:

  • $C = f(A,B,password)$ where $f$ is cryptographic hash function.
  • $D = f(m,g,password)$
  • $X = \left(\left(D+A\right)\pmod{m}\right)^\left(C+b\right)\pmod{m} $

and then sends $ f(X)$ to Alice.

Alice calculates $X$ on her side without $b$ and I can't figure out how.

Could somebody help me with the algorithm on Alice's side?

  • $\begingroup$ Is my interpretation of "You don't know what $\hspace{.02 in}f$ is and hope that something about $\hspace{.02 in}f$ can be $\hspace{.9 in}$ worked out from the fact that Alice can calculate X" correct? $\;$ $\endgroup$ – user991 Jun 10 '13 at 8:24
  • $\begingroup$ No, I know that $f$ is a cryptographic hash function e.g. sha1, and I'm sure that Alice can calculate X, but she doesn't know b and Bob doesn't send value of X he sends $f(X)$. I think $X = f_1(K,password)$ where K is the shared secret between Alice and Bob. They both know K and password, so there must be an expression equivalent to X on the Alice's side. $\endgroup$ – dr.g100k Jun 10 '13 at 12:36
  • 1
    $\begingroup$ it maybe that: $X \equiv (DA)^{C+b} \pmod{m}$, then it can be rewritten $X \equiv g^{(d+a)(C+b)} \pmod{m}$, so Alice can get $X$ by this way $X \equiv (g^CB)^{d+a}\pmod{m} $ , you can check that $\endgroup$ – T.B Sep 3 '13 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.