Determining a Private Key (Diffie-Hellman)

Question

I've been given a challenge and it has to do with testing a friend's encryption process.

It's a Diffie-Hellman exchange process, and here are the known variables / constants:

• P, G
• my generated private key (variable)
• my generated public key(variable)
• the recipients public key (constant).

When looking at my private key - P and G are both within it. For example, the first 'x' bytes seem to have no relation to anything, then the next 'y' bytes are P, the next two bytes are static, and the next 'z' bytes are G, the remainder are variable.

The process is to encrypt a file, and send it to a device, which will in turn decrypt it - my ideas of attack are this:

1. try to duplicate the secret shared key. The problem here is that is fine as long as I know my generated private key, at which case - I don't for the files he's given me.

2. Try to find the recipients private key. Here, I could brute force my way in - but would take forever unless I had some sort of supercomputer.

Are there any other options to look at when trying to attack this?

Answer 1

I probably should keep my mouth shut, but it is also an opportunity for those interested in Diffie-Hellman to learn something:

1. Simple implementation of Diffie-Hellman to generate the shared key is vulnerable to man-in-the-middle attacks. However, most implementation of DH tackle this issue properly by adding authentication between Alice and Bob.

2. If your implementation of DH allows declaring a new set of PQG, you could request the other peer to use a new weak set. If Bob does not verify the quality of this set, then it is vulnerable to attacks.

3. DH requires Alice to send X = g^x, if Bob does not check the quality of X, he is vulnerable, since the space of possible values of the secret key can significantly be reduced by Eve in the middle.

4. If your implementation does not remember compromised keys, they can be re-used by Eve.

5. If your implementation does not remember compromised certificates, they can be re-used by Eve.

6. If your implementation does not check certificates, Eve will have fun for sure.