Needham-Schroeder Replay Attacks (EC)

The goals of this assignment are to:

  1. Gain experience with key agreement protocols for symmetric key exchange over untrusted networks
  2. Implement a “stolen ticket” attack against Needham-Schroeder

This assignment is extra credit and to be completed individually.

Needham-Schroeder (NS) is a session key agreement protocol that was adapted for the Kerberos network authentication protocol. It is a classic example of a protocol that was proven to be secure, only to later be found to be vulnerable to an attack due to flaws in the formal model used to verify its security. In particular, if an attacker steals a session key and corresponding ticket that was previously issued by the authentication server to a victim client, they can replay the last three steps of the NS protocol and authenticate as the victim.

For reference, the version of NS used here is the following. Let Alice \(A\) and Bob \(B\) be two parties that trust server \(S\) but not each other. Alice wants to prove her identity to Bob. Let \(K_{A,S}, K_{B,S}\) be shared secrets between \(A,S\) and \(B,S\) and \(N_A,N_B\) be nonces generated by \(A,B\). Finally, let \(T\) be a ticket expiration expressed as seconds since UNIX epoch that is enforced iff \(T \neq 0\). \[ \begin{align*} A \rightarrow S &: A,B,N_A \\ S \rightarrow A &: \left\{ N_A, K_{A,B}, B, \left\{ K_{A,B}, A, T \right\}_{K_{B,S}} \right\}_{K_{A,S}} \\ A \rightarrow B &: \left\{ K_{A,B}, A, T \right\}_{K_{B,S}} \\ B \rightarrow A &: \left\{ N_B \right\}_{K_{A,B}} \\ A \rightarrow B &: \left\{ N_B - 1 \right\}_{K_{A,B}} \\ \end{align*} \]

In this assignment, you are given two pairs of “stolen” tickets and session keys. Your goal is to authenticate to a service using each of these. The “eternal” ticket does not expire (i.e., \(T = 0\)). The other, however, is only valid for a short time window.

The authentication server runs on This NS implementation uses protobuf v3. Messages are defined as follows:

syntax = "proto3";

package wire;

// Network messages.
// Each message sent over the network can be an encrypted message or a plaintext error message.
message WireMessage {
    oneof m {
        Encrypted encrypted = 1;
        string error = 2;

// Encrypted messages.
// The ciphertext decrypts to one of the messages below.
message Encrypted {
    bytes ciphertext = 1;
    bytes nonce = 2;

message Ticket {
    bytes session_key = 1;
    string client_principal = 2;
    uint64 timestamp = 3;

message Challenge {
    bytes nonce = 1;

message ChallengeResponse {
    bytes nonce_sub_1 = 1;

message Authenticated {}

message Request {
    string challenge = 1;

message Response {
    bytes response = 1;

All messages sent over the network are WireMessages, which are in turn either a plaintext error message or an Encrypted message. Message encryption is performed using libsodium; a compatible python implementation is provided by pysodium.

Encrypted messages are a combination of a nonce and ciphertext produced using libsodium’s secretbox API.

As the attacker \(M\), you should use your stolen ticket and session key to engage in the following protocol which consists of the last three steps of NS followed by an authenticated request-response pair. Each message should be prepended by its two-byte, big-endian length as usual. Also, the tickets you are given are serialized WireMessages. Finally, the NS challenge nonce (which is different from the libsodium encryption nonce) should be treated as a little-endian integer.

\[ \begin{align*} M \rightarrow S &: \mathsf{u16}(|\mathsf{Ticket}|) \cdot \mathsf{Ticket} \\ S \rightarrow M &: \mathsf{u16}(|\mathsf{Challenge}|) \cdot \mathsf{Challenge} \\ M \rightarrow S &: \mathsf{u16}(|\mathsf{ChallengeResponse}|) \cdot \mathsf{ChallengeResponse} \\ S \rightarrow M &: \mathsf{u16}(|\mathsf{Authenticated}|) \cdot \mathsf{Authenticated} \\ M \rightarrow S &: \mathsf{u16}(|\mathsf{Request}|) \cdot \mathsf{Request} \\ S \rightarrow M &: \mathsf{u16}(|\mathsf{Response}|) \cdot \mathsf{Response} \\ \end{align*} \]

Your attack should use your email address as the client principal. Having obtained a Response message, it should output a base64-encoded response in the following JSON object:

    "id": "{{client_principal}}",
    "response": "{{response}}"

Submission Instructions

Submit to Canvas a TAR archive containing your code and the JSON objects output by your code for each ticket you successfully replay.

© 2023 wkr