Authentication Protocols
Created:
20190216
Updated:
20231021
DataOrigin Authentication: the process of verifying that the data comes from the source it claims coming from. This is typically done using some cryptographic technique such as digital signatures or message authentication codes.
PeerEntity Authentication: the process of verifying the identity of a communicating actor, such as a user or a device. This is typically done using methods such as passwords, biometric authentication or digital certificates.
In other words dataorigin authentication is about verifying the source of the data, while peerentity authentication is more about verifying the identity of the sender (or recipient) the data.
A security service which often comes bounded with authentication is data integrity, which allows the recipient to detect if a message has been tampered during transmission.
Note that modifications to messages are not always introduced by a malicious actor, alterations may be due to networking or physical issues.
Simple Protocols
Using OneWay Functions
Alice wants to authenticate to Bob’s using a secret password or passphrase. Bob holds the oneway hash function output of Alice’s secret.
 Alice sends to Bob her password.
 Bob performs a oneway hash function on the password.
 Bob compares the result with the value it previously stored.
Bob doesn’t store the table of everybody’s valid password, thus the threat of someone breaking into the host and steal the passwords is mitigated.
Dictionary attack
Mallory can compile offline a list of very common passwords and apply the oneway function to the list. Mallory then compares the results to each of the hashed passwords list. If a match is found then Mallory has found the secret.
Salt
A random string concatenated with the password before being fed to a oneway function.
Typically, a different salt is used for each different secret. Both the salt and the result of the oneway function are stored in the Bob’s host.
Salt mitigates dictionary attack. Mallory has to do a trial of each password in his dictionary every time he tries to break a different person’s password, rather that just doing one massive precomputation for all possible passwords and have it ready for other host to attack.
Eavesdropping
If the password is sent in cleartext then Eve, can trivially intercept it. It is thus recommended to enforce the scheme with a cryptographic protocol which provides confidentiality.
However, 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 OneTime Passwords
At system initialization time:
 Alice enters a random number,
r
.  The authentication host computes
{ x₁ = f(r), .. , xₙ = f(xₙ₋₁) }
. Alice puts this list away.  The authentication host stores
xₙ₊₁
in a database next to Alice’s name.
To login:
 Alice enters
xₙ
 The host computes
f(xₙ)
and check if matches the valuexₙ₊₁
saved in the database.  If matches, Alice is authenticated and the value
xₙ₊₁
is replaced withxₙ
in the database.
If the host database stores the value xᵢ
then Alice authenticates with the
value xᵢ₋₁
.
When Alice runs out of numbers the system should be reinitialized.
With the expiration of the basic patents on publickey cryptography and the widespread usage of SSH and other strong cryptographic protocols that can secure an entire session, not just the password, S/KEY is falling in disuse.
Shared Key Authentication
We assume an encryption algorithm with some form of avalanche effect.
c = E(k, m)
If the encrypted message c
is altered, then almost surely we end up decrypting
some junk.
Assuming that we are able to distinguish junk from a legit message then the encryption function gives us some kind of integrity check service.
If our endgoal is to only provide integrity and authentication, and we don’t require for the function to be reversible, there are more efficient ways to provide the same service.
Message Authentication Codes
A MAC is a cryptographic hash function which output also depends on a secret k
.
h = H(k, m)
The MAC h
is typically shared together with the message.
Everyone that has the secret key k
can check m'
by computing H(k, m)
and
comparing the result with the h
found together with m'
.
One trivial, but not secure, form of MAC is to just hash the concatenation of the message with the key:
h = H(m  k)
Popular secure MAC schemes are HMAC and CMAC.
Mutual authentication protocol
SecretKey IDentification protocol (SKID) allows two parties to authenticate with each other.
SKID2 allows Alice to prove his identity to Bob and is resistant to replay attacks.
 Bob chooses a random number
b
and sends it to Alice.  Alice chooses a random number
a
and sends to Boba
andH(k,abA)
.  Bob computes
H(k,abA)
and compares it to Alice’s MAC.
SKID3 additionally allows Bob to prove his identity to Alice (mutual authentication).
 Bob sends to Alice
H(k,abB)
.  Alice computes
H(k,abB)
and compares it to the Bob’s MAC.
Authentication and Confidentiality
Let’s assume we have two keys, one to encrypt k₁
and one for the MAC k₂
.
EncryptandMAC

Encrypt the plaintext using
k₁
; 
Compute the MAC of the plaintext using
k₂
; 
Append the MAC to the ciphertext.
E(k₁, m)  H(k₂, m)
Provides integrity of the plaintext only.
If the cipher is malleable, the contents of the ciphertext could be altered, but after decryption, we should find an invalid plaintext.
May reveal information about the plaintext in the MAC. This occurs if the plaintext messages are repeated, and the MACed data does not include a nonce.
MACthenEncrypt

Compute the MAC of the plaintext using
k₂
; 
Append the MAC to the plaintext;

Encrypt everything using
k₁
.E(k₁, m  H(k₂, m))
Provides integrity of the plaintext only.
If the cipher is malleable it may be possible to alter the message to appear valid and have a valid MAC. This is a theoretical attack, practically speaking a good MAC algorithm and secret should provide good protection.
The MAC doesn’t leak any information on the plaintext, since it is encrypted.
EncryptthenMAC

Encrypt the plaintext using
k₁
; 
Compute the MAC of the ciphertext using
k₂
; 
Append the MAC to the ciphertext.
c = E(k₁, m)
c  H(k₂, c)
Provides integrity of both ciphertext and plaintext. We should be able to deduce whether a given ciphertext is indeed authentic or has been forged.
If the cipher scheme is malleable we need not be so concerned since the MAC will filter out any invalid ciphertext.
The MAC does not provide any information on the plaintext since, assuming the output of the cipher appears random, so does the MAC.
In short, EncryptthenMAC seems to be the most ideal scheme. Any modifications to the ciphertext that do not also have a valid MAC can be filtered out before decryption, protecting against any attacks on the implementation.
Public Key Authentication
Given the keypair (pub, sec)
, the owner of the keys can prove message
authenticity by digitally signing the message:
s = sign(sec, m)
Everyone can then check if the message is from the owner of pub
:
verify(pub, m, s)
Digital signatures also provide nonrepudiation property. That is, a valid signature can only be produced by the owner of the keypair and noone else. This can be proven to any third party.
Typically, what is digitally signed is not m
but a hash of the message H(m)
.
Authentication and Confidentiality
As for MAC, there are three popular approaches:
 EncryptAndSign
 SignThenEncrypt
 EncryptthenSign
The procedures are similar to the ones proposed for MAC and have the same security properties.
Simple Protocols
Bob’s host holds the list of authorized users public keys.
 Bob sends to Alice a random challenge.
 Alice signs the challenge with her private key and sends it back.
 Bob verifies the signature with Alice public key.
 If the signature is valid then Alice is authenticated.
Neither 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 impersonate Alice.
A variant is where Bob sends to Alice a challenge encrypted using Alice’s public key. Alice must send back to Bob the decrypted challenge to prove that she is the owner of the private key.
However, for Alice it is not a good practice to encrypt or decrypt arbitrary strings from a potentially rogue authentication hosts.
A more secure protocol takes the following form.
 Alice encrypts using her private key a random challenge
c₁
.  Bob decrypts the challenge using Alice public key. And gets
c₁
.  Bob sends to Alice a random challenge
c₂
.  Alice applies a public shared function
f
(e.g. a hash) toc₁c₂
and sends to Bob the output encrypted using her private key.  Bob decrypt the message and checks if the result is equal to the one he computed independently.
With this protocol Alice never encrypts or decrypts strings chosen by Bob and can still prove that she have the correct private key.