Authentication Protocol Design Concepts

What is Challenge Response mechanism?

Sometimes we need to prove the knowledge of a secret without actually revealing the secret. This is particularly useful when the channel is insecure . Challenge response is a method used to prove the knowledge of a secret key without revealing it.

Protocol Decription: In the scenario where two parties share a secret key.

• The two parties exchange random numbers, Ra & Rb. 
• Each receiving party encrypts the Random number with its Secret key and transmits it back to the sender. 
• On receiving the encrypted random number, the sender tries to decrypt it with the secret key it knows. If the decryption is successful then sender knows that the other party has knowledge of the secret.

Security Pitfalls: Minor variant of a secure protocol can have security holes.

How would you do an Integrity Check?

There are two methods

1. Checksum
2. MAC or HMAC - requires a key

How to design a protocol?

• Start with a design, which will most certainly have flaws.
• Check for all possible weaknesses and fix them.
• So the more we know about types of possible flaws the better it is.

Below is a description of some simple protocols, their weaknesses and possible fixes.

Protocol Flaws associated with Secret Key Based Protocols

1. Protocol: Sending the password in clear text.

    Problems: Eavesdropper can intercept to the password during transmission.

    Enhancement: Instead send a challenge to the client, the client applies a function on the Shared         Secret key and the challenge and sends the value to the server. 

Function (Shared Secret, Challenge)

    

2. Protocol: Only the client side authenticates itself using Function (Shared Secret, Challenge)

Problems: 

• If an attacker can intercept the communication between client & server, then the attacker can send responses to the client by spoofing the server IP address as it doesn't need to know the secret key shared between the server & client. Attacker can simply retransmit an old challenge to the client.
• Attacker can mount an offline password guessing attack, to guess the key assuming he knows the Challenge, Function used, and value of Function (Shared Secret, Challenge)

3. Protocol: After one side authentication, the conversation is sent over clear text

Problems:

• Attacker simply hijacks the conversation (after the initial authentication), if he is able to send packets using the server's IP address.

4. Protocol: 

• Client claims, (I am Alice) to the Sever. 
• Then server sends an encrypted Random Number, with the Key shared with Alice. 
• Client decrypts the Random Number and sends it to Server there by proving knowledge of Key.

Problems:

• This protocol will require reversible cryptography algorithm to decrypt the Random Number. Hashes cannot be used in this case. Hashes provide performance advantage. Sometimes export issues arise when Encryption is used. Hashing is less likely to have export problems.
• If shared key is derived from a Dictionary word, it is vulnerable to dictionary attack.
• If the Random Number is recognizable, the attacker can simply claim to be Alice ( I am Alice) and receive an Encrypted challenge, try to decrypt it using dictionary attack. Once a recognizable number ( say 32bit number padded with 32 bit zeros) is generated, the attacker will know the Secret.
• If the attacker is eavesdropping (more difficult than claiming to be Alice), then he can read both the Random Number & the encrypted value. He can then try to mount a dictionary attack.

Enhancement: Random Number R is made to have a limited lifetime by concatenating it with a timestamp. This will foil replaying of an old  Encrypted Random Number, as the decrypting party will realize that this random number was generated at an earlier time.

5. Protocol: A single handshake is sent to the server, containing the identify claim and an encrypted time-stamp.

                  I am Alice, Key[timestamp]

Problems:

• Requires that client & server have reasonably synchronized clocks (within acceptable clock skew)
• An eavesdropper can retransmit I am Alice, Key[timestamp] within acceptable clock skew and impersonate Alice.                                                                                                            Enchancement: Server keeps a history of all timestamps sent by Alice, until the acceptable clock skew expires, thus detecting a re-transmission
• If Alice, uses the same key for multiple servers, then I am Alice, Key[timestamp] can be re-transmitted to other servers if done within acceptable clock skew.                                           Enchancement: Concatenate the server-name with the timestamp to foil this.                                                          I am Alice, Key[ServerBob + timestamp]
• If the server is vulnerable to clock resetting attack, then the Attacker may be able to reuse old encrypted time-stamps by resetting the clock on the server.                                                           Enchancement:  Authenticate based on challenge/response to allow server clock management.

6. Protocol: A single handshake is sent to the server, containing the identify claim and a hash of Secret key & time-stamp.

                          I am Alice, HASH[SecretKey ,timestamp]

Problems:

• If the timestamp is in minutes and the allowed clock skew is 10 minutes, the Server will need to Hash 10 different timestamps to verify the secret key. This might be acceptable.
• If timestamp is in milliseconds, trying all timestamps would be unacceptably inefficient.

Enchancement: Send the timestamp along with the identity claim

                I am Alice, TimeStamp, HASH[SecretKey,timestamp]

 

Common Problem with Secret Key Based Protocols

If the attacker gets access to the Database of one of the communicating parties. The attacker may be able to get access to shared secret keys as well as any encrypted timestamps received.

Protocols Flaws Associated with Public Key Based Protocols

1. Protocol: 

• Client claims, (I am Alice) to the Sever. 
• Then server sends a Random Number, to the Client (Alice.)
• Client SIGNS the Random Number with his Private Key,and sends it to the Server.
• Server verifies the Random Number based on Client's Public Key, thereby ensuring that Client knows his Private Key.

Problem: 

• Attacker, can trick the Client (Alice) into signing something, and use that Signed Value later to forge the Client's Signature. ( If he impersonates the Server's address, waits for Client to connect and then send the quantity as a challenge to the Client)

2. Protocol: 

• Client claims, (I am Alice) to the Sever. 
• Then server sends a Random Number, encrypted with the Client's Public Key, to the Client (Alice.)
• Client DECRYPTS the Random Number with his Private Key,and sends it to the Server.
• Server verifies the Random Number, thereby ensuring that Client knows his Private Key.

Problem:

• If the attacker is able to impersonate Server's address, then the Attacker can trick the Client (Alice) into decrypting something that was earlier sent to the Client encrypted with his Public key. 

Solutions to Protocol 1 & Protocol 2 Problems:

Issue: Each independently secure protocol scheme, can compromise the security of another if you use same keys for both.

• Do not use the same key for two different purposes ( Encryption, Signature). This will prevent an attacker from using one protocol to break another.
• Ensure that different uses of the same key are coordinated. Example: If the key is used to encrypt a Challenge and a Message, then add structure to the Quantity by Concatenating a Field before the quantity to identify the type of Field.

What is the reflection Attack?

When mutual authentication is part of a protocol, then each party needs to solve the challenge sent by the other party. 

The attacker posing as Alice and attempting to connect to Bob, is able to trick one of the parties to provide an answer to the challenge posed by Bob.

1. Bob provides the solution to Bob's challenge.

Connection 1

• Attacker poses as Alice and sends his challenge R1 while trying to connect to Bob.
• Bob replies with solution to Attacker's Challenge S1, and sends his own challenge R2 to Attacker.
• (Attacker now needs to provide Solution S2 to prove the knowledge of the shared secret)

Connection 2

• Attacker poses as Alice and send another challenge R2 while trying to connect to Bob again.
• Bob replies with S2 and sends his own challenge R3 to the Attacker.

Now Attacker, goes back to the Connection 1 and uses the solution S2 provided by Bob in Connection 2 and proves knowledge of Bob's shared secret key with Alice. Thus Bob himself got tricked into providing the solution to his own challenge.

2. Alice Provides the solution to Bob's challenge

Connection 1

• Attacker poses as Alice and sends his challenge R1 while trying to connect to Bob.
• Bob replies with solution to Attacker's Challenge S1, and sends his own challenge R2 to Attacker.
• (Attacker now needs to provide Solution S2 to prove the knowledge of the shared secret)

Connection 2

• Attacker poses as BOB and send a challenge R2 while trying to connect to Alice.
• Alice replies with S2 and sends his own challenge R3 to the Attacker.

Now Attacker, goes back to the Connection 1 and uses the solution S2 provided by ALICE in Connection 2 and proves knowledge of Bob's shared secret key with Alice. Thus Alice got tricked into providing the solution to BOB's challenge.

Solution to Reflection Attack

• Have both Bob & Alice do the same thing differently.
• Also Initiator should be the first one to prove its Identity.

1. Use two different keys to Authenticate Bob & Alice. This will require additional storage and configuration.
2. Challenge from Initiator should be different from the challenge from the responder. Eg : Initiator of the connection can use Even numbers while Responder can use Odd Numbers.

Authentication Protocol Design Flaws CheckList

Consider the following as a list of things when you have to design a new Authentication Protocol.

Lets Assume, Alice is the Client and Initiates the conversation and Bob is the Server.

If an attacker 

• Shouldn't be able to understand the conversation between Client & Server
• Shouldn't be able to do a reflection attack to impersonate either Client or Server
• Shouldn't be able to Impersonate by replaying the authentication information to other servers & get authenticated
• Shouldn't be able to do an offline password guessing attack to find the Secret Key.
• Shouldn't be able to convince the Server that he is Alice.
• Shouldn't be able to convince the Client that he is Server.
• Shouldn't be able to trick either party into signing or decrypting something. 
• Shouldn't be able to decrypt old recorded conversations between Client & Server.
• Shouldn't be able to Hijack a conversation that was started by either Client or Server, without having one of the parties notice the change. 
• Modify the messages or replay, rearrange, or reverse the direction of messages.