Why is "Diffie-Hellman Key Exchange" secure?

Question

I'm not sure if I misunderstood these codes. First Alice generate her keypair and sent the public key to Bob. Then Bob uses the parameter in the public key to generate his keypair and sent the public key back to Alice. So Alice can generate a shared secret based on Bob's public key and vise versa. Here's the question, Bob can generate a secret key by only getting a public key from Alice. Doesn't it mean that anyone can create the same secret key by using any of these public keys? How can it be secure? If there's someone can eavesdropping this communication, the public key is surely be leaked. So anyone is able to generate a secret key by this public key and decrypt any message.

Someone may say that it's not possible to generate a private key from public key. But in this case, it just can.

I know it's not working like that in the Wikipedia. But this implementation can't be wrong. It's from the Oracle after all.

Here's the implementation by Oracle.

public class DHKeyAgreement2 {
 private DHKeyAgreement2() {}
 public static void main(String argv[]) throws Exception {
 
 /*
 * Alice creates her own DH key pair with 2048-bit key size
 */
 System.out.println("ALICE: Generate DH keypair ...");
 KeyPairGenerator aliceKpairGen = KeyPairGenerator.getInstance("DH");
 aliceKpairGen.initialize(2048);
 KeyPair aliceKpair = aliceKpairGen.generateKeyPair();
 
 // Alice creates and initializes her DH KeyAgreement object
 System.out.println("ALICE: Initialization ...");
 KeyAgreement aliceKeyAgree = KeyAgreement.getInstance("DH");
 aliceKeyAgree.init(aliceKpair.getPrivate());
 
 // Alice encodes her public key, and sends it over to Bob.
 byte[] alicePubKeyEnc = aliceKpair.getPublic().getEncoded();
 
 /*
 * Let's turn over to Bob. Bob has received Alice's public key
 * in encoded format.
 * He instantiates a DH public key from the encoded key material.
 */
 KeyFactory bobKeyFac = KeyFactory.getInstance("DH");
 X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(alicePubKeyEnc);
 PublicKey alicePubKey = bobKeyFac.generatePublic(x509KeySpec);
 /*
 * Bob gets the DH parameters associated with Alice's public key.
 * He must use the same parameters when he generates his own key
 * pair.
 */
 DHParameterSpec dhParamFromAlicePubKey = ((DHPublicKey)alicePubKey).getParams();
 // Bob creates his own DH key pair
 System.out.println("BOB: Generate DH keypair ...");
 KeyPairGenerator bobKpairGen = KeyPairGenerator.getInstance("DH");
 bobKpairGen.initialize(dhParamFromAlicePubKey);
 KeyPair bobKpair = bobKpairGen.generateKeyPair();
 // Bob creates and initializes his DH KeyAgreement object
 System.out.println("BOB: Initialization ...");
 KeyAgreement bobKeyAgree = KeyAgreement.getInstance("DH");
 bobKeyAgree.init(bobKpair.getPrivate());
 // Bob encodes his public key, and sends it over to Alice.
 byte[] bobPubKeyEnc = bobKpair.getPublic().getEncoded();
 /*
 * Alice uses Bob's public key for the first (and only) phase
 * of her version of the DH
 * protocol.
 * Before she can do so, she has to instantiate a DH public key
 * from Bob's encoded key material.
 */
 KeyFactory aliceKeyFac = KeyFactory.getInstance("DH");
 x509KeySpec = new X509EncodedKeySpec(bobPubKeyEnc);
 PublicKey bobPubKey = aliceKeyFac.generatePublic(x509KeySpec);
 System.out.println("ALICE: Execute PHASE1 ...");
 aliceKeyAgree.doPhase(bobPubKey, true);
 /*
 * Bob uses Alice's public key for the first (and only) phase
 * of his version of the DH
 * protocol.
 */
 System.out.println("BOB: Execute PHASE1 ...");
 bobKeyAgree.doPhase(alicePubKey, true);
 /*
 * At this stage, both Alice and Bob have completed the DH key
 * agreement protocol.
 * Both generate the (same) shared secret.
 */
 try {
 byte[] aliceSharedSecret = aliceKeyAgree.generateSecret();
 int aliceLen = aliceSharedSecret.length;
 byte[] bobSharedSecret = new byte[aliceLen];
 int bobLen;
 } catch (ShortBufferException e) {
 System.out.println(e.getMessage());
 } // provide output buffer of required size
 bobLen = bobKeyAgree.generateSecret(bobSharedSecret, 0);
 System.out.println("Alice secret: " +
 toHexString(aliceSharedSecret));
 System.out.println("Bob secret: " +
 toHexString(bobSharedSecret));
 if (!java.util.Arrays.equals(aliceSharedSecret, bobSharedSecret))
 throw new Exception("Shared secrets differ");
 System.out.println("Shared secrets are the same");
 /*
 * Now let's create a SecretKey object using the shared secret
 * and use it for encryption. First, we generate SecretKeys for the
 * "AES" algorithm (based on the raw shared secret data) and
 * Then we use AES in CBC mode, which requires an initialization
 * vector (IV) parameter. Note that you have to use the same IV
 * for encryption and decryption: If you use a different IV for
 * decryption than you used for encryption, decryption will fail.
 *
 * If you do not specify an IV when you initialize the Cipher
 * object for encryption, the underlying implementation will generate
 * a random one, which you have to retrieve using the
 * javax.crypto.Cipher.getParameters() method, which returns an
 * instance of java.security.AlgorithmParameters. You need to transfer
 * the contents of that object (e.g., in encoded format, obtained via
 * the AlgorithmParameters.getEncoded() method) to the party who will
 * do the decryption. When initializing the Cipher for decryption,
 * the (reinstantiated) AlgorithmParameters object must be explicitly
 * passed to the Cipher.init() method.
 */
 System.out.println("Use shared secret as SecretKey object ...");
 SecretKeySpec bobAesKey = new SecretKeySpec(bobSharedSecret, 0, 16, "AES");
 SecretKeySpec aliceAesKey = new SecretKeySpec(aliceSharedSecret, 0, 16, "AES");
 /*
 * Bob encrypts, using AES in CBC mode
 */
 Cipher bobCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
 bobCipher.init(Cipher.ENCRYPT_MODE, bobAesKey);
 byte[] cleartext = "This is just an example".getBytes();
 byte[] ciphertext = bobCipher.doFinal(cleartext);
 // Retrieve the parameter that was used, and transfer it to Alice in
 // encoded format
 byte[] encodedParams = bobCipher.getParameters().getEncoded();
 /*
 * Alice decrypts, using AES in CBC mode
 */
 // Instantiate AlgorithmParameters object from parameter encoding
 // obtained from Bob
 AlgorithmParameters aesParams = AlgorithmParameters.getInstance("AES");
 aesParams.init(encodedParams);
 Cipher aliceCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
 aliceCipher.init(Cipher.DECRYPT_MODE, aliceAesKey, aesParams);
 byte[] recovered = aliceCipher.doFinal(ciphertext);
 if (!java.util.Arrays.equals(cleartext, recovered))
 throw new Exception("AES in CBC mode recovered text is " +
 "different from cleartext");
 System.out.println("AES in CBC mode recovered text is "
 "same as cleartext");
 }
 /*
 * Converts a byte to hex digit and writes to the supplied buffer
 */
 private static void byte2hex(byte b, StringBuffer buf) {
 char[] hexChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
 '9', 'A', 'B', 'C', 'D', 'E', 'F' };
 int high = ((b & 0xf0) >> 4);
 int low = (b & 0x0f);
 buf.append(hexChars[high]);
 buf.append(hexChars[low]);
 }
 /*
 * Converts a byte array to hex string
 */
 private static String toHexString(byte[] block) {
 StringBuffer buf = new StringBuffer();
 int len = block.length;
 for (int i = 0; i < len; i++) {
 byte2hex(block[i], buf);
 if (i < len-1) {
 buf.append(":");
 }
 }
 return buf.toString();
 }
}

Diffie-Hellman Key Exchange Implementation

In these codes, you can totally get the private key by only using Alice's public key. If the DH is secure, then Oracle must did it in the wrong way. If not, why is it secure?

• Ccm: What makes you think you can get the private key using that code?
• Kimi Chiu: I just ran through it again and found out that without Bob's public key, the other's can't generate the same private key. So Bob did generate his private key by only getting Alice's public key. But to make a pair, you have to get both Alice's and Bob's public key. Which means, you get a public key from the communication and generate a private key, but this private key won't be the same as Bob's and Alice's private key. So it is safe if you don't leak both public keys.
• pjc50: Read the protocol again. You've overlooked Diffie-Hellman entirely. Neither Alice nor Bob send readable versions of their keys, they send encoded versions.
• Martin Maat: Please watch this excellent episode of Computerphile: youtu.be/NmM9HA2MQGI And if you are still hungry for more: youtu.be/Yjrfm_oRO0w

Answer 1

If I'm not mistaken, if you can read Alice and Bob conversation, you still can't know the agreed key and decrypt the messages. The agreed key is never sent through the channel. So even if you can read all message passed between Alice and Bob, it's still hard to know what the agreed key was.

IIRC, one simple version of Diffie-Hellman uses a modulo and exponentiation. From wikipedia, it goes like this:

1. Alice and Bob agree on 2 numbers: p and g.
2. Alice choose a secret integer a, and sends g^a mod p to Bob. Note that, the integer a itself is never part of the communication, it's probably in Alice's RAM and never sent or persisted (theoretically).
3. Bob also does the same, choose a secret number b, and sends g^b mod p to Alice. The number b is never sent.
4. Alice compute the agreed key (g^b mod p)^a mod p, which is: g^(ab) mod p.
5. Bob also does the same. He computes (g^a mod p)^b mod p = g^(ba) mod p.
6. Now they share the secret number g^(ab) mod p = g^(ba) mod p.

Now, even if you can get the (g^a mod p) and (g^b mod p), you have no way to know what a and b are, and you can't compute g^(ab) mod p. The bigger the a and b, the harder it is to crack. And I think there is a version of Diffie-Hellman that uses elliptic curve, that supposed to be harder to crack, but I don't really get the math.

Now, why do we need the public and private keypair? The Diffie-Hellman algorithm is only solving one problem: agreeing on a common key without sending that key. But, an attacker can still pretend to be Bob or Alice. For example, I'm Charlie, there's nothing stopping me from pretending to be Alice in front of Bob, and pretending to be Bob in front of Alice. But, with public & private key, we can be sure who are we talking to.

• Kimi Chiu: You're right, even if I got both public key's I still can't generate the same secret they are using. Because I don't have the private key of Alice and Bob. So the generated secret is always not guaranteed to be the same.
• Jauhar Arifin: Yes, even if you got the g^a and g^b, you can't compute g^ab without knowing a and b.
• Deduplicator: Neither a nor b need to be all that big for security, though should not be pathologically small either. As they have to be chosen with a uniform chance from a huge part of the key-space, which is dependent on g and p, they may tend to be fairly big, but that's just a natural result.