Diffie-Hellman Key Exchange

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

"""
Conceptual Illustration of Forward Secrecy
 
This demonstrates the difference between protocols with
and without forward secrecy.
"""
 
from dataclasses import dataclass
from typing import Optional
import secrets
import hashlib
 
@dataclass
class Session:
    """Represents a TLS-like session."""
    session_id: str
    session_key: bytes
    ephemeral_private: Optional[int]  # Only exists during session
    timestamp: str
 
class WithoutForwardSecrecy:
    """
    Traditional RSA key exchange: no forward secrecy.
    
    The server's static private key can decrypt any session.
    """
    
    def __init__(self):
        # Long-term RSA key (simulated)
        self.private_key = secrets.token_bytes(32)  # In reality: RSA private key
        self.public_key = hashlib.sha256(self.private_key).digest()  # Public key
        self.sessions: list[Session] = []
    
    def establish_session(self, session_id: str) -> Session:
        """
        Client generates session key, encrypts with server public key.
        Server decrypts with private key.
        """
        # Client generates random session key
        session_key = secrets.token_bytes(32)
        
        # "Encrypted" with public key (simulated)
        # In real RSA, this would be encrypted_key = RSA_encrypt(session_key, public_key)
        
        session = Session(
            session_id=session_id,
            session_key=session_key,
            ephemeral_private=None,  # No ephemeral keys used!
            timestamp="2024-01-15"
        )
        self.sessions.append(session)
        return session
    
    def attacker_with_private_key(self, stolen_private_key: bytes) -> list[bytes]:
        """
        If attacker obtains private key, ALL past sessions are compromised.
        """
        if stolen_private_key == self.private_key:
            # Can decrypt all historic session keys!
            return [s.session_key for s in self.sessions]
        return []
 
 
class WithForwardSecrecy:
    """
    Ephemeral Diffie-Hellman: provides forward secrecy.
    
    Each session uses fresh DH keys that are deleted afterward.
    """
    
    def __init__(self, p: int, g: int):
        self.p = p
        self.g = g
        # Long-term key only for authentication (signing)
        self.signing_key = secrets.token_bytes(32)
        self.sessions: list[Session] = []
    
    def establish_session(self, session_id: str, client_public: int) -> Session:
        """
        Generate ephemeral DH key pair for THIS SESSION ONLY.
        """
        # Fresh ephemeral private key
        ephemeral_private = secrets.randbelow(self.p - 2) + 2
        
        # Compute ephemeral public key (sent to client)
        ephemeral_public = pow(self.g, ephemeral_private, self.p)
        
        # Compute shared secret
        shared_secret = pow(client_public, ephemeral_private, self.p)
        
        # Derive session key from shared secret
        session_key = hashlib.sha256(
            shared_secret.to_bytes((shared_secret.bit_length() + 7) // 8, 'big')
        ).digest()
        
        session = Session(
            session_id=session_id,
            session_key=session_key,
            ephemeral_private=ephemeral_private,  # Will be deleted!
            timestamp="2024-01-15"
        )
        self.sessions.append(session)
        
        # CRITICAL: Delete ephemeral private key!
        del ephemeral_private
        session.ephemeral_private = None  # Securely erased
        
        return session
    
    def attacker_with_signing_key(self, stolen_signing_key: bytes) -> list[bytes]:
        """
        Even with the signing key, attacker CANNOT recover past sessions.
        
        The signing key authenticates but doesn't derive session keys.
        Ephemeral private keys are gone forever.
        """
        if stolen_signing_key == self.signing_key:
            # Signing key gives:
            # - Ability to impersonate server for FUTURE connections
            # - NOTHING about past session keys
            return []  # Cannot recover ANY past session
        return []
 
 
# Demonstration
print("="*60)
print("FORWARD SECRECY COMPARISON")
print("="*60)
 
# Without forward secrecy
print("
[Without Forward Secrecy - RSA Key Exchange]")
no_fs = WithoutForwardSecrecy()
for i in range(5):
    no_fs.establish_session(f"session_{i}")
 
print(f"Sessions established: {len(no_fs.sessions)}")
print("Attacker steals private key...")
compromised = no_fs.attacker_with_private_key(no_fs.private_key)
print(f"Sessions compromised: {len(compromised)} (ALL OF THEM)")
 
# With forward secrecy
print("
[With Forward Secrecy - Ephemeral DH]")
p, g = 2357, 2  # Demo parameters
fs = WithForwardSecrecy(p, g)
for i in range(5):
    # Simulate client's ephemeral public key
    client_private = secrets.randbelow(p - 2) + 2
    client_public = pow(g, client_private, p)
    fs.establish_session(f"session_{i}", client_public)
 
print(f"Sessions established: {len(fs.sessions)}")
print("Attacker steals signing key...")
compromised = fs.attacker_with_signing_key(fs.signing_key)
print(f"Sessions compromised: {len(compromised)} (ZERO!)")
 
print("
" + "="*60)
print("The ephemeral keys were deleted after each session.")
print("Past sessions are PERMANENTLY protected.")
print("="*60)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

"""
TLS Cipher Suite Analysis for Forward Secrecy
 
Understanding cipher suite naming helps identify whether
a connection has forward secrecy.
"""
 
def analyze_cipher_suite(suite: str) -> dict:
    """
    Parse a TLS cipher suite name and determine security properties.
    
    Format (TLS 1.2): TLS_KEYEXCHANGE_WITH_CIPHER_HASH
    Format (TLS 1.3): TLS_AEAD_HASH (key exchange is always ECDHE/DHE)
    """
    result = {
        "suite": suite,
        "forward_secrecy": False,
        "key_exchange": None,
        "cipher": None,
        "notes": []
    }
    
    parts = suite.upper().split("_")
    
    # TLS 1.3 suites
    if suite.startswith("TLS_AES") or suite.startswith("TLS_CHACHA"):
        result["forward_secrecy"] = True
        result["key_exchange"] = "ECDHE/DHE (TLS 1.3 mandates)"
        result["cipher"] = parts[1] if len(parts) > 1 else "Unknown"
        result["notes"].append("TLS 1.3: Always forward secret")
        return result
    
    # TLS 1.0-1.2 suites
    if "ECDHE" in suite or "DHE" in suite:
        result["forward_secrecy"] = True
        if "ECDHE" in suite:
            result["key_exchange"] = "ECDHE"
            result["notes"].append("Ephemeral EC Diffie-Hellman")
        else:
            result["key_exchange"] = "DHE"
            result["notes"].append("Ephemeral Diffie-Hellman")
    elif "RSA" in suite and "ECDHE_RSA" not in suite and "DHE_RSA" not in suite:
        result["forward_secrecy"] = False
        result["key_exchange"] = "RSA"
        result["notes"].append("⚠️ NO forward secrecy!")
        result["notes"].append("Private key compromise exposes all past sessions")
    elif "DH_" in suite and "DHE_" not in suite:
        result["forward_secrecy"] = False
        result["key_exchange"] = "Static DH"
        result["notes"].append("⚠️ Static DH, no forward secrecy")
    
    return result
 
 
# Analyze common cipher suites
suites = [
    # TLS 1.2 - No forward secrecy
    "TLS_RSA_WITH_AES_128_CBC_SHA256",
    "TLS_RSA_WITH_AES_256_GCM_SHA384",
    
    # TLS 1.2 - With forward secrecy  
    "TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256",
    "TLS_DHE_RSA_WITH_AES_256_GCM_SHA384",
    "TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256",
    
    # TLS 1.3 - Always forward secrecy
    "TLS_AES_128_GCM_SHA256",
    "TLS_AES_256_GCM_SHA384",
    "TLS_CHACHA20_POLY1305_SHA256",
]
 
print("CIPHER SUITE FORWARD SECRECY ANALYSIS")
print("=" * 60)
 
for suite in suites:
    result = analyze_cipher_suite(suite)
    fs_status = "✓ Forward Secret" if result["forward_secrecy"] else "✗ NO Forward Secrecy"
    print(f"
{suite}")
    print(f"  Key Exchange: {result['key_exchange']}")
    print(f"  Status: {fs_status}")
    for note in result["notes"]:
        print(f"  → {note}")
 
print("
" + "=" * 60)
print("RECOMMENDATION:")
print("  - Configure servers to prefer ECDHE/DHE suites")
print("  - Disable RSA key exchange entirely")
print("  - Upgrade to TLS 1.3 where possible (FS is mandatory)")
print("=" * 60)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

/**
 * Secure Key Erasure in C
 * 
 * Demonstrates proper ephemeral key handling for forward secrecy.
 * Improper erasure is a common implementation failure.
 */
 
#include <string.h>
#include <stdlib.h>
 
/* INCORRECT: Compiler may optimize away */
void insecure_clear(void *buffer, size_t len) {
    // Compiler sees that buffer is never used after this
    // and may remove the memset entirely!
    memset(buffer, 0, len);
}
 
/* CORRECT for Windows */
#ifdef _WIN32
#include <windows.h>
void secure_clear_win(void *buffer, size_t len) {
    // SecureZeroMemory is guaranteed not to be optimized away
    SecureZeroMemory(buffer, len);
}
#endif
 
/* CORRECT for C11+ with explicit_bzero */
#ifdef __STDC_VERSION__ >= 201112L
void secure_clear_c11(void *buffer, size_t len) {
    // explicit_bzero writes zeros and is guaranteed not
    // to be optimized away
    explicit_bzero(buffer, len);
}
#endif
 
/* CORRECT: Volatile pointer trick (portable but check assembly) */
typedef void *(*memset_t)(void *, int, size_t);
static volatile memset_t memset_func = memset;
 
void secure_clear_portable(void *buffer, size_t len) {
    // Using volatile function pointer prevents optimization
    memset_func(buffer, 0, len);
}
 
/* Ephemeral key structure with secure destruction */
typedef struct {
    unsigned char private_key[32];  // 256-bit private key
    unsigned char public_key[32];   // 256-bit public key
    int is_valid;
} ephemeral_keypair_t;
 
ephemeral_keypair_t* create_ephemeral_keypair() {
    ephemeral_keypair_t* kp = malloc(sizeof(ephemeral_keypair_t));
    if (!kp) return NULL;
    
    // Generate keys using secure RNG
    // ... crypto key generation code ...
    
    kp->is_valid = 1;
    return kp;
}
 
void destroy_ephemeral_keypair(ephemeral_keypair_t* kp) {
    if (!kp) return;
    
    // CRITICAL: Securely erase the private key
    secure_clear_portable(kp->private_key, sizeof(kp->private_key));
    
    // Public key doesn't need secure erasure (it's public)
    // but we do it anyway for defense in depth
    secure_clear_portable(kp->public_key, sizeof(kp->public_key));
    
    kp->is_valid = 0;
    
    // Don't just free - the OS might not clear the page
    // Consider using locked memory that won't be swapped
    free(kp);
}
 
/**
 * Usage pattern for forward secrecy:
 * 
 * 1. Create ephemeral keypair at session start
 * 2. Use for key exchange
 * 3. Derive session keys
 * 4. IMMEDIATELY destroy ephemeral keypair
 * 5. Continue session with derived symmetric keys
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

"""
Simplified Double Ratchet Concept (Signal Protocol)
 
This illustrates how per-message forward secrecy works.
The actual Signal Protocol is more complex but builds on these ideas.
"""
 
import hashlib
import secrets
 
class SimpleRatchet:
    """
    A simplified symmetric ratchet for forward secrecy.
    
    After deriving each message key, the ratchet advances
    and old keys cannot be recovered.
    """
    
    def __init__(self, root_key: bytes):
        self.chain_key = root_key
        self.message_number = 0
    
    def derive_message_key(self) -> bytes:
        """
        Derive the next message key and advance the ratchet.
        
        After this call, the previous chain_key is gone forever.
        Even if current state is compromised, past messages are safe.
        """
        # Derive message key from chain key
        message_key = hashlib.sha256(
            self.chain_key + b"message_key"
        ).digest()
        
        # CRITICAL: Advance the ratchet (one-way function)
        self.chain_key = hashlib.sha256(
            self.chain_key + b"chain_key"
        ).digest()
        
        self.message_number += 1
        return message_key
    
    def get_state(self) -> dict:
        return {
            "message_number": self.message_number,
            "chain_key": self.chain_key.hex()[:16] + "..."
        }
 
 
def demonstrate_forward_secrecy():
    """
    Show how ratcheting provides forward secrecy.
    """
    print("DOUBLE RATCHET FORWARD SECRECY DEMONSTRATION")
    print("=" * 60)
    
    # Initialize ratchet with a root key (derived from DH exchange)
    root_key = secrets.token_bytes(32)
    ratchet = SimpleRatchet(root_key)
    
    # Derive several message keys
    message_keys = []
    print("
Deriving message keys:")
    
    for i in range(5):
        state_before = ratchet.get_state()
        mk = ratchet.derive_message_key()
        message_keys.append(mk)
        
        print(f"
  Message {i+1}:")
        print(f"    Key: {mk.hex()[:24]}...")
        print(f"    Chain key after: {ratchet.chain_key.hex()[:16]}...")
    
    print("
" + "="*60)
    print("FORWARD SECRECY ANALYSIS:")
    print("="*60)
    
    # Simulate attacker who captures current state
    compromised_chain = ratchet.chain_key
    print(f"
Attacker captures current chain state!")
    print(f"  Compromised chain key: {compromised_chain.hex()[:16]}...")
    
    print("
Can attacker derive PAST message keys?")
    print("  ❌ NO - The chain is one-way. Previous chain keys are gone.")
    print("  The SHA-256 advancement cannot be reversed.")
    
    print("
Can attacker derive FUTURE message keys?")
    print("  ⚠️ YES - Until the next DH ratchet step occurs.")
    print("  This is why Signal combines symmetric + DH ratcheting.")
    
    # Derive next message with compromised state
    future_mk = ratchet.derive_message_key()
    print(f"
Future message key (attacker can compute): {future_mk.hex()[:24]}...")
    
    print("
" + "="*60)
    print("KEY INSIGHT:")
    print("  - Symmetric ratchet: Forward secrecy, not future secrecy")
    print("  - Adding DH ratchet: Regains future secrecy after compromise")
    print("  - Combined (Double Ratchet): Best of both worlds")
    print("="*60)
 
 
demonstrate_forward_secrecy()