Requirement

The system must use CBC mode with PKCS7 for the padding block.

This is a chosen-ciphertext attack, The adversary can submit encrypted messages to the system, and the system will return valid or invalid as response. Assume block size is 8.

Background

Encryption	Decryption
Ci = Encrypt(Pi ⊕ Ci-1)	Pi = Decrypt(Ci ⊕ Ci-1)

Previous posts: The TESLA Broadcast Authentication Protocol, Lamport's Hash

Requirements

A Strong Password-Based Protocols should have these requirements:

• Prevent attackers to eavesdrop the conversation on an authentication exchange
• Prevent attackers to obtain any information by impersonating either endpoint
• Prevent attackers to do off-line attack *
• Attackers should not be able to obtain any further information from observing any number of legitimate exchanges
• Ensure forward secrecy

* An attacker impersonating either endpoint will be able to do a single or small amount of on-line password guess, which is unavoidable. However, multiple guesses should generate alarms to the server.

Strong Password Protocols

Encrypted Key Exchange (EKE)

This is the basic form of strong password protocol.

Premise:
A has a weak password (i.e. A and B share a weak secret W derived from password, usually hash(password)).

Approach:
A -> B: W{g^a mod p}
B -> A: W{g_b mod p}, c1
The key K establishment is based on Diffie-Hellman exchange, so K = g^ab mod p
A -> B: K{c1, c2}
B -> A: K{c2 - 1}
The last two steps is to authenticate between A and B by providing challenges c1 and c2.

Does it prevent off-line attack?
Yes. T can only get Diffle-Hellman messages from off-line guessing, which is impossible to derive K. Also, W{g^a mode p} is just a random number. For any password W’ there exist an r such that W’{r} = W{g^a mod p}

How about Forward Secrecy?
It ensures forward secrecy. a, b, K are only used in this session and will be forgotten later on. If T compromises K, T will not be able to get further information in latter communication.
The only information that will not be forgotten is W. However, T still cannot get K with W.(Unless A or B get compromised and a, b is known by T).

Simple Password Expotential Key Exchange (SPEKE)

Approach:
It uses W in place of g in the Diffle-Hellman exchange:

A -> B: w^a mod p
B -> A: w^b mod p

Where K = w^ab mod p

Password Derived Moduli (PDM)

Approach:
It uses a modulus p which is a function of the password. And uses 2 as the base:

A -> B: 2^a mod p
B -> A: 2^a mod p

Where K = 2^ab mod p

Flaws and Attacks

In EKE

If p is only a little more than a power of 2, for example, p = 2^k+i for small i.
Since g^a mod p < p. A eavesdropper can try guessing the password, if the password is correct, the result will definitely less than p, if it is not correct, the result will fall randomly between [0, 2^k+1-1]([0, p+p-1]). The attacker will know the result is incorrect if it is larger than p.
The changes of getting a correctly password will be (2^k+i)/2^b, which is almost 50%.
To eliminate this flaw, we need to choose a p which is a little less than a power of 2.

In SPEKE

The eavesdropper might be able to eliminate some pasword guesses based on seeing w^a mod p. If some of the Ws generated from passwords for use in SPEKE were perfect squares and some not, then if w^a mod p was not a perfect square, the attacker could know none of passwords resulted in Ws that were perfect square could have been A’s password.
To check if a number w=x² mod p is a perfect square mod p, we can do w^(p-1)/2 mod p. If the result is 1 mod p, then it is a perfect square.

To eliminate this problem, we simply need to ensure every w is a perfect square mod p.

Augmented Strong Password Protocols

Goal: If an attacker T compromises B, T cannot succeed with an offline attack

Approach: Avoiding storing W in B’s database but only something derived from W.

Requirement: The password must be strong so that the off-line attack will not succeed.

Augmented PDM

1. B stores A, p, 2^w mod p (p is derived from password)
2. A -> B: 2^a mod p
3. B -> A: 2^b mod p, hash(2^ab mod p, 2^bw mod p)
4. A -> B: hash’(2^ab mod p, 2^bw mod p) (this hash’ is for B to authenticate A)

Note that it is not possible for attacker T to do this:
T impersonate A, sends 2^k mod p to B. T gets 2^b mod p and hash(2^kb mod p, 2^bw mod p) from B, then do offline attacks by trying different w.

Because p is derived from password, so B will recognize it’s not a valid message.

Augmentation Based on RSA Public Keys

1. B stores A, W, {A}(A’s public key), Y=W’{[A]}(A’s private key)
2. A -> B: A, W{g^a mod p}
3. B choose b and challenge c
4. B -> A: W{g^b mod p}, ((g^ab mod p)){Y}
5. A -> B: [hash(g^ab mod p, c)]_sign-A

Note that if T breaks into B, T can get W, but T cannot get W’

Secure Remote Password (SRP)

1. B stores A, g^w mod p
2. A choose a, compute W from password
3. A -> B: A, g^a mod p
4. B choose b, c1 and a 32-bit number u
5. B sends g^b+g^w mod p, u, c1
   (K = g^b(a+uW) mod p)
6. A -> B: K{c1}, c2
7. B -> A: K{c2}

** How is the common key computed on both ends? **
For A: g^b+g^w mod p - g^w mod p = g^b
Then (g^b)^(a+uw) mod p
For B: (g^a)^b*(g^w)^bu mod p

Previous post: Lamport's Hash.

Approach

• Sender A splits time into intervals of equal duration I.
• A forms a one-way chain of self-authenticating values X_n, assign the values sequentially. The one-way chain is used in the reverse order of generation, so any value of a time interval can be used to derive values of previous time intervals.
• A defines a disclosure time for one-way chain values. A will publish the value after the disclosure time. For example, on time interval i, A publish X_n-(i-1).
• A attaches MAC to each packet, and use the key on that time interval to compute MAC: MAC(M_i, X_n-i)(on time i). A also sends the value it can disclose.
• When B receives the packet, it checks that A has not disclose the value X to make sure the key is still secret. Then B buffers the packet.
• B also checks the disclosed value is correct and verify MAC of this packet(base on time interval). If MAC is correct. B accept the packet.

One-Way Chains

Any value of a time interval can be used to derive values of previous time intervals.
So even if some disclosed keys are lost, B can still recover the key chain.

Requirements

• Receivers should be loosely time synchronized with the sender.
• Either receiver or senders must buffer some messages.

Advantages

• Low communication overhead (and for generation and verification of authentication information)
• Limited buffering required for the sender and the receiver, hence timely authentication for each individual packet
• Robustness to packet loss
• Scales to a large number of receivers
• Low authentication delay

Source: The TESLA Broadcast Authentication Protocol

Intro

Suppose A wants to log into a server B, and A’s work station has no user specific configurations(e.g. CAs or private keys). Here are several ways A can use a password to authenticate to server:

• Send password directly to B (vulnerable to eavesdropping and impersonating)
• Diffie-Hellman key establishment(vulnerable to impersonating)
• SSL (need trust configuration and certificates)
• Use A’s hash(password) as a secret key:
  B->A: R
  A->B: hash(pwd, R)
  (vulnerable to dictionary attack)
• Use one time password scheme like Lamport’s Hash
• Use Strong password protocol

Lamport’s Hash

Implementations

A->B: A
B->A: n(a reasonably large number)
B: Computes x_n=hashⁿ(password)
A->B: x_n-1=hash^n-1(password)
B: Computes x_n‘ = hash(x_n-1)
B then compares x_n‘ and x_n, if they match, B consider the response is valid, then replace n to n-1

Advantages

• Prevents Eavesdropping attack
• If attacker compromises B, it cannot find the pre image of A’s password.

Problems

• If n get to 1, A needs to set its password again with B. This process is vulnerable to Man in the Middle Attack(Small N attack):

  1. A sends B A
  2. B sends A n. T intercepts it and replaces n to n’ = n-10
  3. A computes h = hash^n-11(password). T intercepts it and replace h to h’ = hash^n-1(password) = hash¹⁰(h)
  4. B hashes h’ once, get the match.

  A possible solution to this is for A to remember the approximate value of n, and do some sanity check for n.
  Now T can calculate the next 10 hashes that matches B’s expectations.
  This allows T login as A multiple times.

• When n drops to 1, A have to change its password for security issue(Enhancement: using salt–hash(password|salt))

• Time complexity

Human and Paper

Note that Lamport’s Hash can be used in environments that workstation do not have the hash. We call this Human and Paper environment(vs. Workstation environment).
The way it works is that the values hashⁱ(password) will be pre-computed for all i in n. Then printed these hashes on a paper and give it to A. A crosses out hashes whenever it uses that hash to log in. Next time A will use the next value to login.