Public Key Cryptography and Key Distribution

Administrative Concerns and Lecture Logistics

Accessing Recordings: There have been issues with the lecture recordings. Specifically, it was reported that Lecture 2 was a duplicate of Lecture 1. This error was discovered during a morning check of the system.
Material Sharing: Students are encouraged to talk with colleagues and share information among themselves while technical issues regarding system access and enrollment are being sorted out. The instructor permits students to attend lectures even if their enrollment process is not yet complete.
Audio Quality: Feedback from students who accessed recordings confirmed that the audio quality is acceptable, even though the remote microphone was not initially used.
Class Representative: A class representative was needed for standard student meetings. Steve volunteered to take the position. The instructor will provide the necessary registration forms next week.

Application of Public Key Cryptography in Session Key Sharing

Efficiency Considerations: Asymmetric encryption (Public Key Cryptography) is mathematically complex and computationally intensive. Therefore, it is considered inefficient and slow for transmitting large amounts of data over a long session. It is not suitable as a primary means of high-speed data transmission.
Primary Use Case: Asymmetric encryption is highly effective and acceptable for encrypting very small amounts of data. The most common use is the secure transmission of a session key, secret key, or master key.
Merkle’s Proposed Protocol: Merkle proposed a simple protocol for establishing a symmetric session key using a public key system: * $a$ generates a pair of public/private keys. * $b$ generates a pair of public/private keys. * $a$ sends a message to $b$ containing its identity ( $ID_a$ ) and its public key ( ${PK}_a$ ). * $b$ generates a session key ( $K_s$ ), encrypts it using $a$ 's public key ( ${PK}_a$ ), and sends it to $a$ . * Once the session key is established, both parties can eventually discard the temporary asymmetric keys.

Vulnerabilities: Man-in-the-Middle Attacks

Protocol Subversion: The simple protocol described by Merkle is vulnerable to a Man-in-the-Middle (MitM) attack.
The Identity Linkage Problem: The core issue is the lack of a secure, verifiable link between the identity ( $ID$ ) of the sender and the cryptographic material (the public key) provided. Anyone can claim a specific identity and provide their own public key.
Mechanism of Attack: 1. $a$ attempts to send an identity and public key to $b$ . 2. An attacker, $e$ (Eve), intercepts the message and modifies it. 3. $e$ replaces $a$ 's public key with $e$ 's own public key ( ${PK}_e$ ) but maintains the identity as $a$ . 4. $b$ receives the message, believing the public key belongs to $a$ . $b$ generates a session key ( $K_s$ ), encrypts it with ${PK}_e$ , and sends it back. 5. $e$ intercepts this response and decrypts it using their own private key ( ${SK}_e$ ). 6. $e$ then re-encrypts the session key using $a$ 's original public key ( ${PK}_a$ ) and sends it to $a$ . 7. Now, $a$ and $b$ communicate using $K_s$ , which is also known to $e$ , allowing $e$ to read or modify all traffic.
Comparison to Previous MitM Scenarios: * In earlier examples, a MitM attack acted more like a "Denial of Service" because $a$ could detect that a message was altered (e.g., if IDs were messed with) and would drop the connection. * In the current scenario, the attack is silent. Neither $a$ nor $b$ have evidence that the protocol has been subverted. From their perspectives, they have established a secure connection. * Detection would require an offline verification channel (e.g., a physical meeting) to confirm the public keys, which is often not feasible.

Advanced Secure Exchange Protocol

Authentication and Confidentiality: To prevent MitM attacks, the system must be "bootstrapped" so that parties can authenticate the source of a public key.
Protocol Steps involving Nonces: 1. $a$ sends a request to $b$ encrypted with $b$ 's public key ( ${PK}_b$ ). The message includes $ID_a$ and a nonce ( $n_1$ ) for freshness. 2. $b$ responds with a message encrypted under $a$ 's public key ( ${PK}_a$ ). It includes the original nonce ( $n_1$ ) to prove it is a response to the specific request, and a new nonce ( $n_2$ ). 3. $a$ sends a confirmation encrypted under ${PK}_b$ containing $n_2$ . 4. $a$ sends a session key ( $K_s$ ) to $b$ . This is encrypted under ${PK}_b$ but is also signed by $a$ using $a$ 's private key ( ${SK}_a$ ).
Signing vs. Encrypting: Using a private key to "encrypt" is actually a signing operation. While anybody with the public key can verify the signature, only the holder of the private key could have created it, ensuring non-repudiation and authenticity.
Role of Nonces ( $n_1$ , $n_2$ ): These are used for fresh transactions and unique identification of the session to prevent replay attacks.

Schemes for Public Key Distribution

Historically, four main schemes have evolved alongside the growth of the internet:

1. Public Announcement

Method: Manual exchange of public keys through physical meetups or public forums.
Context: Common in the early days of "Pretty Good Privacy" (PGP).
Limitations: It relies on physical delivery or trust in a channel. If a private key is compromised, it is nearly impossible to inform every person who received the public key manually.

2. Publicly Accessible Directories

Method: An organization (like a university) maintains a directory of IDs and associated public keys.
Mechanism: Functions similar to a "Yellow Pages." Users look up individuals and retrieve their keys.
Risk: The directory must be kept highly secure. If a hacker alters the database, they can replace legitimate keys with fraudulent ones.

3. Public Key Authority (PA)

Method: A central authority with stricter security than a simple directory. Users follow a specific protocol to request keys.
Protocol Example: 1. $a$ sends a request to the PA for $b$ 's public key, including a timestamp or nonce. 2. The PA replies with a message containing ${PK}_b$ . This message is signed using the PA's private key. 3. $a$ uses ${PK}_b$ to initiate communication with $b$ . 4. $b$ similarly requests and verifies $a$ 's public key from the PA.
Trust Requirement: All users must pre-establish and trust the public key of the Public Key Authority ( ${PK}_{PA}$ ). Once this trust is established, the PA can manage a massive network of entities.
Advantages: The PA only needs to be involved for initial key discovery; once keys are exchanged, parties communicate directly (offline from the PA).

4. Public Key Certificates

Method: The current standard (forming a Public Key Infrastructure or PKI). It uses digital certificates signed by a Certificate Authority (CA).
Concept: A digital certificate acts like an ID or passport. It contains the user's identity and their public key.
Validity: The certificate is signed by the CA's private key. Anyone with the CA's public key can verify the certificate's authenticity offline.
Components of a Certificate: * Identifier of the entity. * The Entity's Public Key. * Expiration Date (Time stamp). * Signature of the CA.
Life Cycle: Certificates address the problem of compromise through expiration dates and Revocation Lists managed by the CA.
Comparison to Public Key Authority: Certificates are superior because they empower users to perform verification themselves without contacting a central server every time a key is needed. It is a more decentralized approach to key management.

Questions & Discussion

Q: When the PA replies to $a$ with $b$ 's public key, what if it doesn't sign the message?
A: If the message is not signed, an attacker like Eve can intercept the message and replace $b$ 's public key with her own. Signature verification using the PA's public key is essential for security.
Q: How does $a$ get the PA's public key securely?
A: This is the "bootstrapping" problem. It must be established securely once. After that, the PA can certify other authorities or millions of users.
Q: Is a cookie similar to a public key store?
A: Not exactly. A cookie is a specific mechanism within a browser to store session data or tracking information. While both store data on a device, they serve different purposes in security and session management.
Q: If a private key is compromised, how does the other party know?
A: This is a major problem with static keys. Solutions include periodic cache clearing, expiration dates on certificates, or checking revocation lists provided by the CA.