Needham–Schroeder protocol facts for kids

Symmetric Needham–Schroeder protocol scheme

The Needham–Schroeder protocol is a set of rules that computers use to talk to each other safely over the internet. Imagine you want to send a secret message to a friend. You need a way to make sure only your friend can read it, and that no one else can pretend to be your friend. This protocol helps computers do just that!

It was created by two smart people, Roger Needham and Michael Schroeder. They came up with two main versions:

The Needham–Schroeder Symmetric Key Protocol: This one uses a special secret code that both computers know. It's like having a secret language only you and your friend understand. This protocol helps computers create a temporary secret code (called a session key) to protect their conversation. It's the basis for a very important system called Kerberos.
The Needham–Schroeder Public-Key Protocol: This version uses two different keys, one public and one private. It's like having a public mailbox where anyone can drop a letter, but only you have the key to open it. This protocol helps computers check if they are really talking to the right computer. However, the original idea for this one had a small problem that made it not completely safe.

How the Symmetric Protocol Works
- Problems with the Symmetric Protocol
- How to Fix the Symmetric Protocol
How the Public-Key Protocol Works
- An Attack on the Public-Key Protocol
- Fixing the Man-in-the-Middle Attack
See also

How the Symmetric Protocol Works

Let's imagine two computers, Alice and Bob, want to talk secretly. They both trust a special server, like a helpful post office, that knows a secret code with each of them.

Here's what the different parts mean:

Alice (A) and Bob (B) are the computers talking.
Server (S) is the trusted helper.
Secret Key (K): This is a special code. For example, K_AS is the secret code only Alice and the Server know. K_BS is the secret code only Bob and the Server know.
Nonce (N): This is a random, one-time number. It's like a secret handshake that changes every time. It helps make sure messages are fresh and not old, replayed ones.
Session Key (K_AB): This is a new, temporary secret code that Alice and Bob will use only for their current conversation.

Here are the steps Alice and Bob take to get their secret session key:

Step 1: Alice asks the Server for help.

* Alice sends a message to the Server saying, "Hi, I'm Alice, and I want to talk to Bob!" She also sends a random number (her nonce, N_A) so she knows the Server's reply is new.

Step 2: The Server helps Alice.

* The Server creates a brand new secret session key (K_AB) for Alice and Bob. * The Server sends a message back to Alice. This message is encrypted with Alice's secret key (K_AS). Inside, it has Alice's nonce (N_A), the new session key (K_AB), Bob's name, and a special package for Bob. * The special package for Bob is the new session key (K_AB) and Alice's name, all encrypted with Bob's secret key (K_BS).

Step 3: Alice sends the package to Bob.

* Alice takes the special package from the Server and sends it to Bob. She can't read it because it's encrypted with Bob's secret key. * Bob gets the package. Since it's encrypted with his secret key (K_BS), he can open it and find the new session key (K_AB) and Alice's name. This tells Bob that Alice is real and the key is from the trusted Server.

Step 4: Bob proves he has the key.

* Bob creates his own random number (his nonce, N_B). * He encrypts his nonce (N_B) with the new session key (K_AB) and sends it to Alice. This shows Alice that Bob successfully got the session key.

Step 5: Alice proves she has the key.

* Alice takes Bob's encrypted nonce (N_B), does a tiny change to it (like subtracting 1), encrypts it again with the session key (K_AB), and sends it back to Bob. This proves to Bob that Alice also has the session key and is ready to talk.

Now, Alice and Bob can use their new secret session key (K_AB) to send messages back and forth, knowing they are safe from snoopers!

Problems with the Symmetric Protocol

Even with all these steps, smart hackers found a way to trick this protocol. It's called a replay attack. Imagine a hacker secretly records the message Alice sent to Bob in Step 3, which contains the session key (K_AB) encrypted for Bob. If that session key somehow becomes old or "compromised" (meaning the hacker figures it out), the hacker can then "replay" that old message to Bob. Bob would think it's a new, fresh key from Alice, even though it's an old, unsafe one. He wouldn't know the difference!

How to Fix the Symmetric Protocol

This problem was fixed in the Kerberos system by adding a timestamp to messages. A timestamp is like a date and time stamp on a letter. If a message has an old timestamp, the computer knows it's not fresh and won't accept it.

Another way to fix it is to add an extra step at the beginning, using another nonce:

Alice asks Bob for a special number.

* Alice sends a simple message to Bob saying, "Hi, I'm Alice."

Bob sends Alice a special number.

* Bob sends Alice a random number (N_B') encrypted with his secret key with the Server (K_BS).

Alice sends her request to the Server, including Bob's special number.

* Alice sends her original request to the Server, but now she also includes Bob's encrypted random number (N_B').

The Server sends its reply, including Bob's special number.

* The Server's reply to Alice now includes Bob's random number (N_B') inside the encrypted package for Bob.

Because Bob's random number (N_B') is now part of the message that gets encrypted for Bob, a hacker can't just replay an old message. The hacker wouldn't know the new random number (N_B') to put into the message, so Bob would know it's fake.

How the Public-Key Protocol Works

This version uses a different kind of secret code system called public-key cryptography. In this system, everyone has two keys:

A public key: This key is like your public email address. Anyone can have it and use it to send you an encrypted message.
A private key: This key is secret, and only you have it. It's the only key that can unlock messages sent to your public key.

Alice and Bob still use a trusted Server to find each other's public keys.

K_PA and K_SA: These are Alice's public and private keys.
K_PB and K_SB: These are Bob's public and private keys.
K_PS and K_SS: These are the Server's public and private keys. The Server uses its private key to "sign" messages, proving they are from the Server. Alice and Bob use the Server's public key to check these signatures.

Here's how the public-key protocol works:

Step 1: Alice asks the Server for Bob's public key.

* Alice sends a message to the Server saying, "I'm Alice, and I need Bob's public key."

Step 2: The Server sends Bob's public key to Alice.

* The Server sends Bob's public key (K_PB) and Bob's name to Alice. The Server "signs" this message with its private key (K_SS) to prove it's really from the Server.

Step 3: Alice sends a secret number to Bob.

* Alice creates a random number (her nonce, N_A). * She encrypts her nonce (N_A) and her name (A) using Bob's public key (K_PB). Only Bob, with his private key, can read this.

Step 4: Bob asks the Server for Alice's public key.

* Bob now knows Alice wants to talk. He sends a message to the Server asking for Alice's public key.

Step 5: The Server sends Alice's public key to Bob.

* The Server sends Alice's public key (K_PA) and Alice's name to Bob, also signed by the Server.

Step 6: Bob sends secret numbers back to Alice.

* Bob creates his own random number (his nonce, N_B). * He encrypts both Alice's nonce (N_A) and his own nonce (N_B) using Alice's public key (K_PA). This proves to Alice that he could read her first message.

Step 7: Alice confirms Bob's secret number.

* Alice decrypts the message from Bob using her private key. She sees both nonces. * She then encrypts Bob's nonce (N_B) using Bob's public key (K_PB) and sends it back. This proves to Bob that she could read his message.

At the end, Alice and Bob both know each other's random numbers (N_A and N_B), and they know these numbers are secret from anyone else.

An Attack on the Public-Key Protocol

This protocol has a big problem called a man-in-the-middle attack. Imagine a sneaky impostor (let's call them I) who wants to trick both Alice and Bob. The impostor can pretend to be Alice to Bob, and pretend to be Bob to Alice.

Here's how the attack works, ignoring the messages to the Server (which are the same):

Alice thinks she's talking to Bob, but she's talking to the Impostor.

* Alice sends her secret number (N_A) and her name, encrypted with what she thinks is Bob's public key, but it's actually the Impostor's public key (K_PI). * The Impostor gets the message and decrypts it with their own private key (K_SI). Now the Impostor knows N_A.

The Impostor pretends to be Alice to Bob.

* The Impostor takes Alice's secret number (N_A) and Alice's name, encrypts them with Bob's real public key (K_PB), and sends it to Bob. Bob thinks it's from Alice.

Bob sends his secret numbers, thinking he's talking to Alice, but it goes to the Impostor.

* Bob creates his secret number (N_B). He encrypts N_A and N_B with what he thinks is Alice's public key (K_PA) and sends it. * The Impostor gets this message. But the Impostor doesn't have Alice's private key, so they can't decrypt it to learn N_B.

The Impostor relays Bob's message to Alice.

* The Impostor just forwards the encrypted message from Bob to Alice. Alice decrypts it with her private key and learns N_B.

Alice confirms Bob's secret number, but sends it to the Impostor.

* Alice encrypts N_B with what she thinks is Bob's public key, but it's the Impostor's public key (K_PI). * The Impostor gets this message and decrypts it with their private key. Now the Impostor knows N_B too!

The Impostor relays the confirmation to Bob.

* The Impostor encrypts N_B with Bob's real public key (K_PB) and sends it to Bob. Bob thinks Alice confirmed his number.

At the end of this trick, Bob thinks he's talking to Alice, and Alice thinks she's talking to Bob. But really, the Impostor is in the middle, reading and controlling everything! The Impostor now knows both N_A and N_B, which were supposed to be secret between Alice and Bob.

Fixing the Man-in-the-Middle Attack

This clever attack was found by a computer scientist named Gavin Lowe in 1995. He also came up with a simple fix.

The fix is to change just one message:

Instead of Bob sending: N_A and N_B encrypted with Alice's public key
Bob now sends: N_A, N_B, and his own name (B) encrypted with Alice's public key

Now, if an Impostor tries the trick, when Alice gets the message in Step 6, she will see Bob's name (B) inside the message. But she expects to see the Impostor's name (I) because she thinks she's talking to the Impostor. Since the names don't match, Alice knows something is wrong and stops the conversation. This simple change makes the protocol much safer!