Notes - Computer Security MT24, Protocols

Created: November 17, 2024
Updated: January 13, 2025

The notes cover several different protocols:

  • Unilateral authentication
    • Using a symmetric key
      • A: “My name is Alice”
      • B: “Here’s a nonce encrypted with our shared key”
      • A: “Here’s the decrypted nonce”
      • (There’s also a variant where Alice instead returns $E _ {k _ {AB} }(\mathbf{nonce} + 1)$ since this prevents CPAs)
    • Using a symmetric key, but stateless
      • A: “My name is Alice, and here is the current time encrypted with our shared key”
    • Using a symmetric key, and establishing a session but not a session key
      • A: “My name is Alice”
      • B: “Here’s a nonce I’d like you to encrypt”
      • A: “Here’s the nonce encrypted with our shared key”
      • A: “Now when we talk, let’s include the nonce, our names and a counter in every message”
    • Using a symmetric key, and establishing a session key
      • A: “My name is Alice”
      • B: “Here’s a nonce I’d like you to encrypt”
      • A: “Here’s the nonce encrypted with our shared key, and after it I’ve included a session key”
      • A: “Now when we talk, let’s use the new symmetric key, our names and a counter in every message”
    • Using public and private keys
      • Two variants:
      • A: “My name is Alice”
      • B: “Here’s a nonce I’ve encrypted with your public key”
      • A: “Here’s the nonce, decrypted using my private key”
      • Or:
      • A: “My name is Alice”
      • B: “Here’s a nonce”
      • A: “Here’s the nonce signed with my secret key”
    • Using public and private keys, and establishing a session key
      • A: “My name is Alice”
      • B: “Here’s a nonce I’ve encrypted with your public key”
      • A: “Here’s the nonce back and a shared symmetric key we can use. I’ve encrypted this with your public key so other people can’t see”
      • A: “Now when we talk, lets include out names and a counter”
  • Bilateral authentication
    • Using a symmetric key
      • Only flawed protocols are given in the notes
      • Almost identical to unilateral authentication but Alice also sends a nonce in the first step
    • Using a symmetric key, but using timestamps
      • A: “My name is Alice, and here’s the current time and my name encrypted with our shared key”
      • B: “That checks out, here’s the current time and my name encrypted with our shared key”
    • Using a symmetric key, and establishing a session key
    • Using public and private keys
      • Not discussed in the notes when the authentication isn’t mediated by a third party
  • Mediated authentication

Some general observations:

  • For unilateral protocols, either Alice needs to encrypt or decrypt the nonce. In the notes:
    • Alice decrypts a nonce given to her by Bob when:
      • Not establishing a session, or
      • Using public and private keys.
      • (the fact Alice has to decrypt a nonce when using public and private keys follows from the fact Bob must verify her identity by decrypting something encrypted with her public key)
    • Alice encrypts a nonce given to her by Bob when:
      • Establishing a session using shared symmetric keys
      • (mnemonic: encrypts when establishing).

Flashcards

Unilateral authentication

@Define unilateral authentication.

Alice wants to prove her identity to Bob, but Bob doesn’t need to prove his identity to Alice.

Using shared symmetric keys

Consider the following protocol for unilateral authentication with a symmetric key:

  1. $A \to B$: Alice
  2. $B \to A$: $E _ {k _ {AB} }(\mathbf{nonce})$
  3. $A \to B$: $\mathbf{nonce}$

What is the main disadvantage of this protocol?

An attacker can use Alice as a decryption oracle for any message sent using $k _ {AB}$.

Consider the following protocol for unilateral authentication with a symmetric key:

  1. $A \to B$: Alice
  2. $B \to A$: $\mathbf{nonce}$
  3. $A \to B$: $E _ {k _ {AB} }(\mathbf{nonce})$

What is the main disadvantage of this protocol, and what simple modification means this is not possible?

It allows the attacker to run a chosen plaintext attack against the key $k _ {AB}$.

  1. $A \to B$: Alice
  2. $B \to A$: $E _ {k _ {AB} }(\mathbf{nonce})$
  3. $A \to B$: $E _ {k _ {AB} }(\mathbf{nonce} + 1)$

In other words, each user acts as an encryption oracle for their key.

@Describe a stateless unilateral authentication protocol.
  1. $A \to B$: Alice, $E _ {k _ {AB} } (\mathbf{timestamp})$

Consider the following stateless unilateral authentication protocol:

  1. $A \to B$: Alice, $E _ {k _ {AB} } (\mathbf{timestamp})$

What is its main disadvantage?

Bob must protect his clock against alteration and clock skew.

Consider the following unilateral authentication protocol for establishing a session:

  1. $A \to B$: Alice
  2. $B \to A$: $\mathbf{nonce}$
  3. $A \to B$: $E _ {k _ {AB} }(\mathbf{nonce})$
  4. $A \to B$: $E _ {k _ {AB} }(m _ 1 \parallel \mathbf{nonce} \parallel \text{Alice} \parallel \mathbf{counter})$
  5. $B \to A$: $E _ {k _ {AB} }(m _ 2 \parallel \mathbf{nonce} \parallel \text{Bob} \parallel \mathbf{counter})$

What is the main disadvantage?

The same key is used for the entire session, which means there a lot of ciphertext transmitted for the same key. They should instead establish a session key.

@Describe a unilateral authentication protocol for establishing a session using a shared symmetric key.
  1. $A \to B$: Alice
  2. $B \to A$: $\mathbf{nonce}$
  3. $A \to B$: $E _ {k _ {AB} }(\mathbf{nonce} \parallel k _ s)$
  4. $A \to B$: $E _ {k _ s} (m _ 1 \parallel \text{Alice} \parallel \mathbf{counter})$
  5. …
With public and private keys

What are the disadvantages of the following two protocols for unilateral authentication with a public key?

  1. $A \to B$: Alice
  2. $B \to A$: $E _ {pk _ A} (\mathbf{nonce})$
  3. $A \to B$: $\mathbf{nonce}$

and

  1. $A \to B$: Alice
  2. $B \to A$: $\mathbf{nonce}$
  3. $A \to B$: $\text{SIGN} _ {sk _ A}(\mathbf{nonce})$

Alice is acting as an oracle against her secret key, which allows a CCA or a CMA. She must not use the key for anything else, otherwise an attacker could query the key through this protocol.

@Describe a unilateral authentication protocol for establishing a session, using a public key.
  1. $A \to B$: Alice
  2. $B \to A$: $E _ {pk _ A}(\mathbf{nonce})$
  3. $A \to B$: $E _ {pk _ B}(\mathbf{nonce} \parallel k _ s)$
  4. $A \to B$: $E _ {k _ s}(m _ 1 \parallel \text{Alice} \parallel \mathbf{counter})$
  5. …

Bilateral authentication

Using shared symmetric keys

Consider the following protocol for bilateral authentication using a symmetric key:

  1. $A \to B$: Alice, $\mathbf{nonce} _ A$
  2. $B \to A$: $E _ {k _ {AB} } (\mathbf{nonce} _ A)$, $\mathbf{nonce} _ B$
  3. $A \to B$: $E _ {k _ {AB} }(\mathbf{nonce} _ B)$

What is its main vulnerability?

It is vulnerable to a reflection attack:

Alice messages Bob, but is intercepted:

  1. $A \to I _ B$: Alice, $\mathbf{nonce} _ A$

The intruder, pretending to be Bob, sends a message to Alice and tricks Alice into encrypting her own nonce:

  1. $I _ B \to A$: Bob, $\mathbf{nonce} _ A$
  2. $A \to I _ B$: $E _ {k _ {AB} }(\mathbf{nonce} _ A)$, $\mathbf{nonce} _ X$

Then the intruder resumes the first communication with Alice:

  1. $I _ B \to A$: $E _ {k _ {AB} }(\mathbf{nonce} _ A)$, $\mathbf{nonce} _ B$
  2. $A \to I _ B$: $E _ {k _ {AB} }(\mathbf{nonce} _ B)$

One protocol for bilateral authentication with a symmetric key could be:

  1. $A \to B$: Alice, $\mathbf{nonce} _ A$
  2. $B \to A$: $E _ {k _ {AB} } (\mathbf{nonce} _ A)$, $\mathbf{nonce} _ B$
  3. $A \to B$: $E _ {k _ {AB} }(\mathbf{nonce} _ B)$

But this is vulnerable to a reflection attack. What general principle should be followed to prevent this, and what are some ways of achieving this?
  • Protocols should not be symmetrical.
  • One way is to add structure to the nonces, e.g. Alice’s nonce has to be even while Bob’s nonce has to be odd.

@Describe a bilateral authentication protocol using a timestamp and a symmetric key.
  1. $A \to B$: Alice, $E _ {k _ {AB} }(\text{Alice} \parallel \mathbf{timestamp})$
  2. $B \to A$: $E _ {k _ {AB} }(\text{Bob} \parallel (\mathbf{timestamp} + 1))$

(one way to remember that the participants include their names in the encrypted timestamp is by considering a possible attack if they didn’t: an intruder could try and get Alice to communicate with them and encrypt $E _ {k _ {AB} }(\mathbf{timestamp} + 1)$ for them.

Miscellaneous

What attack model do most protocols assume, and what assumption does this lead to?

The [[Notes - Computer Security MT24, Dolev-Yao model]]U. This means that the underlying cryptographic primitives are assumed to be secure.

@Define the notation

\[\\{m\\} _ {pk _ A}\]

A message encrypted with a public key.

@Define perfect forward secrecy.

Communications are still secure from eavesdroppers if long-term keys are later compromised.

(E.g. session keys are exchanged via Diffie-Hellman, so even if the attacker can see the whole protocol in the clear, they still won’t be able to determine what the key is).

Perfect forward secrecy is where previous sessions are still secure from eavesdroppers even if the long-term keys are later compromised. How is this achieved in practice?

Never send the session key in the clear, agree on the key using something like [[Notes - Computer Security MT24, Diffie-Hellman key exchange]]U.

Consider the following protocol:

  1. $A \to B$: Please send public key
  2. $B \to A$: $pk _ B$
  3. $A \to B$: $E _ {pk _ B} (k _ s)$
  4. $A \to B$: $E _ {k _ s}(m _ 1)$
  5. $B \to A$: $E _ {k _ s}(m _ 2)$
  6. …

What is the main vulnerability?

It is susceptible to a man-in-the-middle attack.

Why are stateless protocols useful?

They are less open to denial of service attacks.

What is the difference between authentication and key establishment?

Authentication can only detect whether a user is alive, whereas the key establishment sets up a short-term key for an authenticated session.

What is the difference between key transport and key agreement?

Why is there a general principle when designing protocols that the initiator should be the first to prove their identity?
  • It helps to prevent reflection attacks, since an attacker can’t reflect Bob’s challenge back to him as though it came from Alice.
  • It helps prevent DoS attacks since the recipient can refuse unauthenticated requests for them to verify their identity.


Related posts