1
$\begingroup$

I have made some reverse engineering on proprietary software and came up with some DHE algorithm that works like this:

First and foremost, the client and the server shares some public parameters (g, p) where p is a prime number :

# the client generates some random number X
# Then...
A = g^X % p
B = 4^X % p

At this stade, A and B are two numbers computed with some exponentioation modulus p.

The client keeps A for itself and sends B over network to the server.

I can't guess out what's the server doing with B.

What comes up next is that the server sends the client back some buffer which is 20 bytes long. This buffer is xored with the first 20 bytes of the little-endian representation of A. Meaning something like this:

key = buffer ^ A[0...20]

And there you go, key is the shared key between the client and the server.

I am trying to guess out how the server generated that xoring buffer, and what did it compute with 'B'. Any clue?

Edit:

For instance, I have these numbers:

g=4251748925932087506992136911681457196421197968417424634771122535345596546655443876920558972863202693157925206950493858768680434551750613271334944372387511

p=7552255105811443149655814117645061441469802313473420161620729142606560015854445500056007762660457578016660416343667268412286196867181440500178902692672641

X (random number) = 8788592173807205653697600075440308493757969005221433286958441247128089107594429784362875543428031794230308326680487467902465260209524609291268858491985100

How could the server compute A?

$\endgroup$
  • $\begingroup$ Is that a typo in B? Is it really $4$ instead of $g$? $\endgroup$ – mikeazo Jul 16 '15 at 16:09
  • $\begingroup$ 20 bytes is 160 bits, which could be SHA-1. You could try sending specific values to the server, and see if it is just a SHA-1 hash of the data you send it. I don't see how a shared key is even possible unless the server knows $X$, which it doesn't appear to. $\endgroup$ – mikeazo Jul 16 '15 at 16:11
  • $\begingroup$ @mikeazo it's not a typo in B and it is both g and 4. Though It would be SHA-1, how the server would even know the value of A? $\endgroup$ – Geoffrey R. Jul 16 '15 at 17:43
  • $\begingroup$ It can't (unless p is really small). $\endgroup$ – mikeazo Jul 16 '15 at 17:47
  • $\begingroup$ p is 512 bits long $\endgroup$ – Geoffrey R. Jul 16 '15 at 20:19
3
$\begingroup$

I haven't checked, is $p$ a safe prime and/or is 4 a generator over $p$?

Server has random secret $S$, known $p$ and $g$ a generator. I'm substituting in $V$ for your $g$, with $g = 4$.

$V = g^S \mod p$

$V$ is a verifier of the server, as in SRP.

$V$ is your $g$, so known by the client. Anyone knowing $V$ can establish communications with the server.

You calculate for random $X$

$A = V^X \mod p$
$B = g^X \mod p$

So, when you send $B$, server calculates

$A = B^S = g^{XS} = V^X \mod p$

This is one-way authentication, of the server only. You could do the same thing with the client, and have a mutually authenticated DH key exchange (each client would need a secret as well, and the server would have to know the corresponding verifier).

What's curious is why bother sending back anything, why not just use $A$ directly (or a hash of it, for example)? If the 20-byte value isn't checked against anything else, it seems sort of useless. It could be used as a proof, e.g. hash of $A$, but you don't indicate that it's used for anything except to XOR it with $A$. Since it's being sent in the clear, it doesn't really add anything to the security.

$\endgroup$
  • $\begingroup$ Your answer makes sense! For your last paragraph, my guess is that the server sends some buffer back to actually both acknowledge the client's $B$ and to obfuscate a little bit more the key generation. Thanks a lot! $\endgroup$ – Geoffrey R. Jul 20 '15 at 8:05
1
$\begingroup$

As long as your understanding the protocol correctly, the only way this can work is if the server is figuring out $X$ and using that to compute $A$. With $p$ being only 512 bits, it is possible to compute $X$, given $B$. But it would still take a fairly long time to do that, so I'm guessing that is not what the server is doing.

So, I'm guessing your understanding of the protocol is incorrect.

$\endgroup$
  • $\begingroup$ Well, ... if $p$ is constant, this would enable Logjam-style attacks meaning one could recover $X$ in 90s on consumer machines... $\endgroup$ – SEJPM Jul 16 '15 at 20:30
  • $\begingroup$ @sejpm good point $\endgroup$ – mikeazo Jul 16 '15 at 23:05
  • $\begingroup$ Maybe my understanding is incorrect; I get a correct shared key with the server though. $\endgroup$ – Geoffrey R. Jul 17 '15 at 6:38
  • $\begingroup$ @SEJPM Assuming the precomputation for that $p$ is available. $\endgroup$ – fkraiem Jul 18 '15 at 15:54
1
$\begingroup$

What is the value of $p$? What is the value of $g$?

If $g = 2$, when he receives $4^X$, he could compute the square root of it so that he has $2^X$ which is your $A$.

$\endgroup$
  • $\begingroup$ p is a large 512 bits prime number and g is a large 512 random number. There value are shared between the client and the server. $\endgroup$ – Geoffrey R. Jul 17 '15 at 6:37
  • 2
    $\begingroup$ My guess is g is some power of 4, so the server knows g = 4^y, so when he receives your B = 4^x, he computes B^y to get (4^x)^y = (4^y)^x= g^x, which is the client's A. $\endgroup$ – user13741 Jul 17 '15 at 8:00
  • $\begingroup$ you might be right, I didn't check that g and p would be "bound" (don't know how do you say it) but I'll tell you what. $\endgroup$ – Geoffrey R. Jul 17 '15 at 8:04
  • $\begingroup$ I mean, g and 4 would be bound*, not p and g (since p is definitely a prime number). $\endgroup$ – Geoffrey R. Jul 17 '15 at 9:12
  • $\begingroup$ user13741: I have edited my question to provide readers with numbers. As one can see, g isn't a power of 4. Can you still help me though? $\endgroup$ – Geoffrey R. Jul 18 '15 at 15:37

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.