In practice, what are the identities in the Needham–Schroeder protocol?

Question

In the Needham–Schroeder public-key protocol we have the identities A and B of Alice and Bob, respectively. The initial version of the protocol was vulnerable to a MitM attack where the fix consists of adding Bob's identity to message 6.

Let's say someone wants to write an implementation of the protocol. I was trying to picture how this would look, as a mental exercise, and I'm having difficulties with the identities.

Q: For practical purposes, what are the identities A and B of Alice and Bob?

Would this be a fixed string or maybe the location of the parties, for example, String alice = "A" or String alice = "192.168.1.10:50100"?

Answer 1

The identities are any identifiers which allow Alice and Bob to uniquely identify each other in the current context, and which allow the Authentication Server to look up the keys of Alice and Bob and send them messages. The exact format of the identifiers is outside the scope of the protocol – it could be numbers, names, special strings, anything that works for the specific use case. IP addresses aren't necessarily the best choice, because they can change when a network is restructured, forcing you to update your identity database accordingly.

For a practical example, you can look at Kerberos which is based on the symmetric variant of the Needham-Schoeder protocol. It uses IDs called principals with the format primary/instance@REALM, where primary is, for example, a username, instance can be used to distinguish between different roles of the user, and REALM is a domain name.

Answer 2

The identities A and B in the Needham-Schroeder public-key protocol are unique identifiers for the parties involved in communications. This is to avoid confusion in communications (essential for security as you might know already). In real world implementations, their values generally are not strings rather unique identifiers. This hardly varies case over case, however, organisations might be using public key fingerprinting or employee IDs for example. This is a complete Python explanation of this concept along with comments that can aid you understanding how this all is practically handled.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import serialization, hashes
import os

class PublicKey:
    def __init__(self):
        self._private_key = None
        self._public_key = None

    def generate_key(self, key_size=2048):
        self._private_key = rsa.generate_private_key(
            public_exponent=65537,
            key_size=key_size
        )
        self._public_key = self._private_key.public_key()

    def encrypt(self, message: bytes) -> bytes:
        if not self._public_key:
            raise ValueError("No public key available")
        
        return self._public_key.encrypt(
            message,
            padding.OAEP(
                mgf=padding.MGF1(algorithm=hashes.SHA256()),
                algorithm=hashes.SHA256(),
                label=None
            )
        )

    def decrypt(self, ciphertext: bytes) -> bytes:
        if not self._private_key:
            raise ValueError("No private key available")
        
        return self._private_key.decrypt(
            ciphertext,
            padding.OAEP(
                mgf=padding.MGF1(algorithm=hashes.SHA256()),
                algorithm=hashes.SHA256(),
                label=None
            )
        )

    def get_public_key_pem(self) -> bytes:
        if not self._public_key:
            raise ValueError("No public key available")
        
        return self._public_key.public_bytes(
            encoding=serialization.Encoding.PEM,
            format=serialization.PublicFormat.SubjectPublicKeyInfo
        )

class Party:
    def __init__(self, identity: str):
        self.identity = identity
        self.key_pair = PublicKey()
        self.key_pair.generate_key()

    def get_identity(self) -> str:
        return self.identity

    def get_public_key(self) -> PublicKey:
        return self.key_pair

    def encrypt_for(self, recipient: 'Party', message: bytes) -> bytes:
        return recipient.get_public_key().encrypt(message)

    def decrypt(self, ciphertext: bytes) -> bytes:
        return self.key_pair.decrypt(ciphertext)

def needham_schroeder_protocol(alice: Party, bob: Party):
    # Step 1: Alice sends her identity and a nonce to Bob
    nonce_a = os.urandom(16)
    message_1 = alice.identity.encode() + b"|" + nonce_a
    ciphertext_1 = alice.encrypt_for(bob, message_1)

    # Step 2: Bob decrypts the message and sends back the nonce along with his own
    decrypted_1 = bob.decrypt(ciphertext_1)
    alice_id, nonce_a = decrypted_1.split(b"|")
    nonce_b = os.urandom(16)
    message_2 = nonce_a + b"|" + nonce_b + b"|" + bob.identity.encode()  # Added Bob's identity
    ciphertext_2 = bob.encrypt_for(alice, message_2)

    # Step 3: Alice verifies her nonce and sends Bob's nonce back
    decrypted_2 = alice.decrypt(ciphertext_2)
    nonce_a_received, nonce_b, bob_id = decrypted_2.split(b"|")
    if nonce_a != nonce_a_received or bob_id.decode() != bob.identity:
        raise ValueError("Protocol failed: nonce mismatch or wrong identity")
    
    message_3 = nonce_b
    ciphertext_3 = alice.encrypt_for(bob, message_3)

    # Step 4: Bob verifies his nonce
    decrypted_3 = bob.decrypt(ciphertext_3)
    if nonce_b != decrypted_3:
        raise ValueError("Protocol failed: nonce mismatch")

    print("Needham-Schroeder protocol completed successfully")

if __name__ == "__main__":
    alice = Party("[email protected]")
    bob = Party("[email protected]")

    print(f"Alice's identity: {alice.get_identity()}")
    print(f"Bob's identity: {bob.get_identity()}")
    print(f"Alice's public key:\n{alice.get_public_key().get_public_key_pem().decode()}")
    print(f"Bob's public key:\n{bob.get_public_key().get_public_key_pem().decode()}")

    needham_schroeder_protocol(alice, bob)

I hope this helped you working this out!

P.S: You can access Google Colab to try this script in a .pynb cell.