D   A   T   A   W   O   K





Creation: February 16 2019
Modified: February 05 2022

Authentication Protocols

Using One-Way Functions

Alice wants to authenticate in Bob's host using a password. Bob holds the one-way hash function result of Alice's password.

  1. Alice sends to Bob her password.
  2. Bob performs a one-way hash function on the password.
  3. Bob compares the result with the value it previously stored.

Bob no longer stores a table of everybody's valid password, thus the thread of someone breaking into the host ans stealing the passwords list is mitigated.

Dictionary attack

Somehow Mallory has stealed the hashed passwords list from the Bob's host.

Mallory can compile a list of N (with N big) very common passwords and apply the one-way function to the list. Mallory can now compare the results to each of the hashed passwords list.

If a match is found then Mallory has found the password to be used for the respective user.

Salt

Salt is a random string that is concatenated with the password vefore being operated on by the one-way function. A different salt string is used for each different password. Both the salt and the result of the one-way function are stored in the database on the Bob's host.

Salt mitigates the dictionary attack threat. Now Mallory has to do a trial of each password in his dictionary every time he tries to break another person's password, rather that just doin one massive precomputation for all possible passwords (and possibly have it ready for other hosts).

Eavesdropping

If the password is sent in cleartext then Eve, can intercept it. Thus is recomended to enforce the protocol with a cryptographic protocol.

If Eve has access to the authentication host, then it can read it from a memory dump, before the host hash it for further checks.

S/KEY One-Time Password

To set up the system Alice enters a random number, R. The computer computes f(R), f(f(R)), f(f(f(R))), and so on, about a hundred times. Call these numbers x1,...,x100. The computer prints the list of numbers and Alice puts it away. The computer stores x101 in a login database next to Alice's name.

To log in, Alice enters the number x100. The computer computes f(x100) and if it match x101 then alice is logged in and the value x100 is substituted to x101 in the database. The next time that Alice wants to log in she has to enter x99. And so on.

When Alice runs out of numbers the system should be reinitialized.

With the expiration of the basic patents on public-key cryptography and the widespread use of SSH and other crypto protocols that can secure an entire session, not just the password, S/KEY is falling into disuse.

Public key authentication

The Bob's host holds a list of the users public keys.

  1. Bob sends to Alice a random string.
  2. Alice encrypts the string with her private key and sends it back.
  3. Bob decrypts the Alice string with Alice public key.
  4. If the decrypted string matches what Bob sent to Alice in the first place, then Alice is authenticated.

auth1

Neither the Bob's host nor the communication channel needs to be secure.

Alice never sends her private key over the transmission network. Eve listening on the interaction can't get any information that would enable her to imprersonate Alice.

A variant is where Bob sends to Alice an encrypted random string using her public key. Alice must send to Bob the decrypted content to prove that she is the owner of the private key.

Anyway it is not secure to encrypt/decrypt arbitrary strings.

A more secure protocol takes the following form.

  1. Alice encrypts using her private key a random string RA.
  2. Bob decrypts the message using Alice public key. And gets RA.
  3. Bob sends to Alice a random string R2.
  4. Alice apply a known funciton 'f' to R1 and R2, then sends to Bob the function result encrypted using her private key.
  5. Bob decrypt the message and check if the result is equal to the one he've computed independently.

auth2

With this protocol Alice never encrypts/decrypts strings choosen by Bob and can prove that she have the correct private key.

Interlock Protocol Mutual Authentication

Alice and Bob are two users that want to authenticate each other. Each of them has a password that the other knows: Alice has PA and Bob has PB.

The following protocol is vulnerable to MitM attack:

  1. Alice and Bob trade public keys.
  2. Alice encrypts PA with Bob's public key and sends it to him.
  3. Bob encrypts PB with Alice's public key and sends it to her.
  4. Alice decrypts the message received in step 3 and verifies it is correct.
  5. Bob decrypts the message received in step 2 and verifies it is correct.

interlock

A MitM attack here is trivial for Mallory. She can subvert the public keys exchange in step 1 by giving to the peers her public key and easily get PA and PB in the step that follows.

The interlock protocol can make the MitM attack more difficult.

  1. Alice and Bob trade public keys.
  2. Alice encrypts PA with Bob's public key and sends half of it to him.
  3. Bob encrypts PB with Alice's public key and sends half of it to him.
  4. Alice sends the other half.
  5. Bob sends the other half.
  6. Alice and Bob can decrypt the messages and get PA and PB.

Mallory can't decrypt the message in step 2. And to let the protocol continue he must send "something" to Alice to get the other half of the key. But the protocol is not even started for Bob, so Alice is not authenticated, nor is Bob.

Anyway now Mallory has PA and can easily independently start the protocol with Bob to get in a similar manner the Bob's password PB.

When Alice will restart the protocol then Mallory, knowing PA and PB, can immediatelly forward the messages to the other party and reaching the mutual authentication point.

SKID2 and SKID3

The protocols use a MAC and thus is assumed that Alice and Bob share a secret key, K. The MAC function is H(K,params), with K the key and params are additional parameters.

SKID2 allows Bob to provide his identity to Alice

  1. Alice chooses a random number RA and sends it to Bob.
  2. Bob chooses a random number RB and he sends to Alice RB and H(K,RA||RB||B).
  3. Alice computes H(K,RA||RB||B) and compares it to the Bob's message.

SKID3 additionally allows Alice to prove his identity to Bob.

  1. Alice sends to Bob H(K,RB||A).
  2. Bob computes H(K,RB||A) and compares it to the Alice's message.

Proudly self-hosted on a cheap Raspberry Pi