Key Exchange Protocols (Protocolos de Troca de Chaves)

Key exchange protocols allow two parties to establish a shared secret over an insecure channel without having exchanged any secret information beforehand. This is fundamental for secure communications on the internet.

Diffie-Hellman Key Exchange

Diffie-Hellman (DH) was one of the first practical key exchange protocols, published in 1976 by Whitfield Diffie and Martin Hellman.

Mathematical Foundation

Given: - A large prime $p$ (typically 2048 bits or more) - A generator $g$ of $\mathbb{Z}_p^*$ (typically 2 or 3)

Alice's steps: 1. Choose a private key $a$ randomly from $[2, p-2]$ 2. Compute public value $A = g^a \mod p$ 3. Send $A$ to Bob over the insecure channel

Bob's steps: 1. Choose a private key $b$ randomly from $[2, p-2]$ 2. Compute public value $B = g^b \mod p$ 3. Send $B$ to Alice over the insecure channel

Shared secret computation: - Alice computes: $s = B^a \mod p = (g^b)^a \mod p = g^{ab} \mod p$ - Bob computes: $s = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p$

Both arrive at the same shared secret $s$, which can be used as a symmetric encryption key.

Security Analysis

The security of Diffie-Hellman relies on the discrete logarithm problem: Given $(p, g, y)$ where $y = g^x \mod p$, finding $x$ is computationally infeasible for large values of $p$.

Attack complexity: - Brute force: $O(\sqrt{p})$ using Baby-step Giant-step or Pollard's rho algorithm - For 2048-bit primes, this requires approximately $2^{1024}$ operations - computationally infeasible with current technology

Java Implementation

import java.math.BigInteger;
import java.security.SecureRandom;

public class DiffieHellmanKeyExchange {

    // Standard parameters from RFC 7919 (modp1)
    private static final BigInteger P = new BigInteger("FFFFFFFFFFFFFFFFC90FDAA2" +
            "2168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A087" +
            "98E3404DDEF9519B3CD3A431B302B026038C13ACFFFFFFFBCFC6EE1BBC7FF59" +
            "B88BB9BCB09CBECECDD4EBA3EDBD4547B9280CD73CDA250F164C406CBBA290" +
            "5F47E52BDF9D8EFF2A30E1F7BB4CC89B68F15D42A58ED30ABDDA62FFCF4F90" +
            "3EBC965FFC9BFD859AC479CA81E99A3ED9B6D1FE609731A", 16);

    private static final BigInteger G = new BigInteger("2");

    /**
     * Generates a Diffie-Hellman key pair.
     */
    public static KeyPair generateKeyPair() {
        SecureRandom random = new SecureRandom();

        // Generate private key (random in range [3, P-2])
        byte[] privateKeyBytes = new byte[128];
        do {
            random.nextBytes(privateKeyBytes);
        } while (new BigInteger(1, privateKeyBytes).compareTo(P.subtract(BigInteger.ONE)) >= 0 || 
                 new BigInteger(1, privateKeyBytes).compareTo(BigInteger.valueOf(2)) <= 0);

        BigInteger x = new BigInteger(1, privateKeyBytes);

        // Compute public key: Y = g^x mod p
        BigInteger y = G.modPow(x, P);

        return new KeyPair(y, x);
    }

    /**
     * Computes shared secret from peer's public key.
     */
    public static byte[] computeSharedSecret(BigInteger theirPublicKey, PrivateKey myPrivateKey) {
        // Shared secret: s = Y^x mod p
        BigInteger sharedSecret = theirPublicKey.modPow(myPrivateKey, P);

        // Hash the result to get a usable key (key derivation function)
        try {
            java.security.MessageDigest digest = java.security.MessageDigest.getInstance("SHA-256");
            return digest.digest(sharedSecret.toByteArray());
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Main demonstration of Diffie-Hellman key exchange.
     */
    public static void main(String[] args) throws Exception {
        System.out.println("=== Diffie-Hellman Key Exchange Demonstration ===\n");

        // Alice generates her key pair
        System.out.println("Alice generating key pair...");
        KeyPair aliceKeys = generateKeyPair();
        BigInteger alicePublic = (BigInteger) aliceKeys.getPublic();
        PrivateKey alicePrivate = (PrivateKey) aliceKeys.getPrivate();
        System.out.println("Alice's public value: " + alicePublic.toString(16).substring(0, 64) + "...");

        // Bob generates his key pair
        System.out.println("\nBob generating key pair...");
        KeyPair bobKeys = generateKeyPair();
        BigInteger bobPublic = (BigInteger) bobKeys.getPublic();
        PrivateKey bobPrivate = (PrivateKey) bobKeys.getPrivate();
        System.out.println("Bob's public value: " + bobPublic.toString(16).substring(0, 64) + "...");

        // Alice computes shared secret using Bob's public key
        System.out.println("\nAlice computing shared secret...");
        byte[] aliceSecret = computeSharedSecret(bobPublic, alicePrivate);

        // Bob computes shared secret using Alice's public key
        System.out.println("Bob computing shared secret...");
        byte[] bobSecret = computeSharedSecret(alicePublic, bobPrivate);

        // Verify they match
        boolean secretsMatch = java.util.Arrays.equals(aliceSecret, bobSecret);
        System.out.println("\nAlice and Bob have the same shared secret: " + secretsMatch);

        if (secretsMatch) {
            System.out.println("Shared secret (first 32 chars): " + 
                new String(aliceSecret, 0, Math.min(32, aliceSecret.length)));
        }
    }
}

Ephemeral Diffie-Hellman (DHE) and Elliptic Curve DH (ECDH)

Modern implementations use ephemeral keys for forward secrecy.

Forward Secrecy

Forward secrecy ensures that even if long-term private keys are compromised, past communications remain secure. This is achieved by using temporary (ephemeral) key pairs for each session.

Ephemeral Diffie-Hellman (DHE)

In DHE: 1. Each party generates a new ephemeral DH key pair for the session 2. The ephemeral private keys are discarded after key exchange 3. Long-term RSA/ECC keys are only used for authentication, not key exchange

Elliptic Curve Diffie-Hellman (ECDH)

ECDH provides equivalent security to traditional DH with much smaller key sizes:

Security Level	Traditional DH Key Size	ECDH Key Size
128-bit	3072 bits	256 bits
192-bit	7680 bits	384 bits

Java Implementation with ECDH

import java.security.*;
import org.bouncycastle.jce.provider.BouncyCastleProvider;

public class ECKeyExchange {

    static {
        Security.addProvider(new BouncyCastleProvider());
    }

    /**
     * Generates an ECDH key pair.
     */
    public static KeyPair generateECDHKeyPair() throws Exception {
        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC", "BC");
        keyGen.initialize(256); // P-256 curve (secp256r1)
        return keyGen.generateKeyPair();
    }

    /**
     * Computes shared secret using ECDH.
     */
    public static byte[] computeSharedSecret(PublicKey theirPublicKey, PrivateKey myPrivateKey) throws Exception {
        // Use KeyAgreement to derive shared secret
        KeyAgreement agreement = new KeyAgreement(KeyAgreement.getInstance("ECDH", "BC"));

        // Initialize with own private key
        agreement.init(myPrivateKey);

        // Process peer's public key
        agreement.doPhase(theirPublicKey, true);

        // Generate the shared secret
        SecretKey sharedSecret = agreement.generateSecret();

        return sharedSecret.getEncoded();
    }

    /**
     * Demonstrates ECDH key exchange with forward secrecy.
     */
    public static void main(String[] args) throws Exception {
        System.out.println("=== ECDH Key Exchange Demonstration ===\n");

        // Alice generates ephemeral keys for this session
        System.out.println("Alice generating ephemeral keys...");
        KeyPair aliceKeys = generateECDHKeyPair();
        PublicKey alicePublic = aliceKeys.getPublic();
        PrivateKey alicePrivate = aliceKeys.getPrivate();

        // Bob generates ephemeral keys for this session
        System.out.println("Bob generating ephemeral keys...");
        KeyPair bobKeys = generateECDHKeyPair();
        PublicKey bobPublic = bobKeys.getPublic();
        PrivateKey bobPrivate = bobKeys.getPrivate();

        // Alice computes shared secret using Bob's public key
        byte[] aliceSecret = computeSharedSecret(bobPublic, alicePrivate);

        // Bob computes shared secret using Alice's public key
        byte[] bobSecret = computeSharedSecret(alicePublic, bobPrivate);

        boolean secretsMatch = java.util.Arrays.equals(aliceSecret, bobSecret);
        System.out.println("\nAlice and Bob have the same shared secret: " + secretsMatch);

        // Demonstrate forward secrecy: even if ephemeral keys are compromised later,
        // past sessions remain secure because each session uses different ephemeral keys.
    }
}

TLS Key Exchange Modes

TLS supports multiple key exchange modes:

Mode	Description	Forward Secrecy
RSA	Server encrypts pre-master secret with RSA public key	No
DHE	Ephemeral Diffie-Hellman	Yes
ECDHE	Ephemeral Elliptic Curve DH	Yes (recommended)

TLS 1.3 Key Exchange

TLS 1.3 only supports forward secrecy modes: - ECDHE: Elliptic curve ephemeral Diffie-Hellman - PSK: Pre-shared keys with ECDHE for key derivation

Security Considerations

Common Attacks and Mitigations

Attack	Description	Mitigation
Man-in-the-middle	Attacker intercepts public values	Use authenticated DH (with certificates)
Small subgroup	Attacker forces use of small subgroups	Validate group order, reject invalid parameters
Timing attack	Side-channel through timing variations	Use constant-time operations

Best Practices

1. Use standard parameters: RFC 7919 for DH, NIST curves for ECDH
2. Enable forward secrecy: Prefer DHE/ECDHE over RSA key exchange
3. Validate peer certificates: Prevent man-in-the-middle attacks
4. Use TLS 1.3: Provides better security and performance

References

1. RFC 7919: Moduli for Diffie-Hellman Finite Fields
2. RFC 5639: Elliptic Curve Cryptography (ECC) Cipher Suites
3. RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3