Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Basic Terminologies Related to Interactive Protocol
3.
Challenge and Response Protocol
3.1.
Weakness of Challenge and Response Protocol
3.2.
Unconditional Security and Computational Security
3.2.1.
MAC 
3.2.2.
Identification Scheme 
4.
Attack Model and Adversarial Goals 
5.
Mutual Authentication 
5.1.
Conditions Specifying the Outcome of a Secure Mutual Authentication Scheme 
5.2.
Ways in Which the Attacker Could be Active in a Session of a Scheme
5.3.
What Constitutes a Successful Attack?
6.
Frequently Asked Questions
6.1.
When is the situation of matching conversation possible?
6.2.
What is a secret-key cryptosystem?
6.3.
What is hybrid cryptography?
6.4.
What is an Adversarial Goal?
6.5.
What is an Attack Model?
7.
Conclusion
Last Updated: Mar 27, 2024

There is a Challenge and Response in the Secret Key Setting

Author RAGHAV ANUSHA
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This article will introduce the Challenge and response in the Secret-key setting, random challenges, MAC security, attack model and adversarial goals, and mutual authentication. We will start with identification in the secret key setting where two users have the same secret key, explore the challenge and response protocol, parallel session attack, and look into what is meant by an intruder in the middle scenario along with various other insightful details. 

Challenge and Response in the Secret-Key Setting

In this blog, we will begin this topic by examining a simple yet insecure scheme that can be message authentication code based, for example - MACs. So let's get started!

Basic Terminologies Related to Interactive Protocol

Generally, an interactive protocol involves two or more parties that are interacting with each other. Let's look at the basic terminologies related to Interactive Protocol - 

  • Session: As mentioned above, an interactive protocol involves two or more interactive parties modeled by algorithms that send and receive information alternatively. Every run of this protocol is called a session.
     
  • Flow: Every step within a protocol session is called a flow. The flow contains the information transmitted between two parties. 
     
  • Internal State: When a session ends, the user who sent the Challenge, User 2, "accepts" or "rejects." This act is called the internal state of User 2. User 1 may not know if User 2 is accepted or rejected. 
Basic Terminologies Related to Interactive Protocol
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Challenge and Response Protocol

In Challenge and Response Protocol, we assume that User 1 identifies itself as User 2 and vice versa. They share a standard secret key denoted as K. In this scheme, User 2 sends a challenge to User 1, and then User 1 responds to User 2.  

Weakness of Challenge and Response Protocol

In this section of the article “There is a challenge and response in the secret-key setting” we will talk about the weakness of the challenge and response protocol. It's not a surprise, however, that the Challenge and Response Protocol is not very secure, even if the MAC used in it is secure. An active adversary here can still perform a parallel session attack, wherein they can impersonate one of the users. The following points breakdown the attack into two sessions - 

  • In session one, we assume that the attacker is impersonating, let's say, User 1. 
     
  • When the attacker initiates a second session, they ask User 2 to identify themselves. In this session, the attacker gives User 2 the same Challenge they received from User 2 in the first session. Once User 2 responds, the attacker resumes the first session, in which the attacker relays User 2's response back to them. 
     

We have a solution to this problem. The only change made is to include the identity of the person creating the MAC tag in the computation of the tag. This, however, does not prove that the protocol is secure from all kinds of attacks. Later in the article, we will look into the proof of security. Let us first list all the assumptions we will make related to the cryptographic components used in the scheme. 

  • Secret Key - We assume that the secret key is only known to User 1 and User 2.
     
  • Random Challenges - We assume that User 1 and User 2 have perfect random number generators, which are used to determine their challenges. Henceforth, there is a minimal possibility that in two different sessions, the same Challenge occurs.
     
  • MAC Security - We assume that MAC is secure here. 
Assumptions we will make related to the cryptographic components used in the scheme


The attacker can observe various sessions between User 1 and User 2. Their goal is to fool either of them. As discussed above, if the attacker chooses to impersonate User 1, they will make User 2 "accept" a session in which User 1 is not taking part and vice versa. We show that the attacker will not succeed in fooling User 1 or User 2 in this way. However, there still is a slight chance that they might succeed when the assumptions mentioned above are valid. This is achieved quite easily by analyzing the structure of the identification scheme.

Let's suppose that User 2 "accepts." Then the value User 2 receives in the second flow is equal to the MACK = (ID(User 1) || challenge received by User 2 from the first flow of the scheme). We make a statement that if the probability is high, the value User 2 receives must have been built by User 1 in response to the Challenge that User 2 received in his first flow of the scheme.

Now to support the statement we made, let's consider the sources of the response in case it didn't come from User 1. Firstly, as the key K is only known to users 1 and 2, we need not worry about the possibility that the value User 2 receives in the second flow is equal to the MACK = (ID(User 1) || Challenge received by User 2 from the first flow of the scheme) was decoded by a third party. Therefore, it's either that the attacker cracked the value User 2 receives in the second flow or was generated by User 1 or User 2 in a previous session, which the attacker is now reusing.

Let's consider these cases one by one - 

  • Assuming the value User 2 receives in the second flow is equal to the MACK = (ID(User 1) || Challenge received by User 2 from the first flow of the scheme) was generated by User 2 in a previous session. Moreover, User 2 only computes tags of the form mentioned in the equation above. So, the possibility that they would've created the value they received in the second flow becomes zero. Therefore, this possibility does not hold.  
     
  • Assuming the value User 2 receives in the second flow is generated by User 1 in a previous session. This is possible only if the Challenge (this Challenge is created by User 2 using a perfect random number generator) received by User 2 from the first flow is being reused. Therefore, the probability that User 2 would not have issued the same Challenge in a different session is minimal.
     
  • Assuming the value User 2 receives in the second flow is generated by the attacker and the MAC is secured, the attacker does not know the value of K. The probability that the attacker could pull this off is minimal. 
     

To be more precise, we can give an exact security guarantee for the identification scheme if we prove the security of the underlying MAC. However, this is only possible if the MAC is secured unconditionally. The security of the identification scheme guarantees to quantify the probability that the attacker deceives User 2 to accept when the attacker is an active part of the scheme. 

Unconditional Security and Computational Security

Let us see how a MAC and identification scheme is secured unconditionally and computationally - 

MAC 

In this section of the article “There is a challenge and response in the secret-key setting” we will talk about an unconditionally secured MAC. In an unconditionally secured MAC, the attacker cannot construct a tag for a new message with a probability greater than the probability of the attacker being able to compute MACK (xi) correctly. This holds if the attacker has seen at most n number of tags (n here is the given number of tags). 

What is an Unconditionally secured MAC?

Unconditionally secured MACs persist for any desired value of a given number of tags and the probability of the attacker being able to compute MACK (xi) correctly, for example - using strong universal hash families. These MACs, however, require large keys if the probability of the attacker being able to compute MACK (xi) accurately is large. This results in computationally secure MACs. In this condition, we must assume the security of MAC. This assumption is similar to our earlier assumptions; we add the time factor here. 

In an unconditionally secured MAC, the attacker cannot generate a valid tag for a new message with a probability greater than the probability of the attacker being able to compute MACK (xi) correctly. This holds if the attacker has seen at most n number of tags (n here is the given number of tags) within the computational time, T.

Identification Scheme 

In this section of the article “There is a challenge and response in the secret-key setting” we will talk about an unconditionally secured identification scheme. We assume that there is a fixed key, K and that the value of this set key is unknown to the attacker. K here is being used to generate a given number of tags. Now the possibility of an identification scheme being unconditionally secure is possible when the attacker can not deceive both users into accepting, with a probability greater than the probability of the attacker being able to compute MACK (xi) correctly. This holds if the attacker has observed at most n number of given tags in previous sessions between users (n here is the given number of tags). 

When we consider the time factor in an unconditionally secured identification scheme, the attacker cannot fool both users to accept with a probability greater than the probability of the attacker being able to compute MACK (xi) correctly. This holds true if the attacker has observed at most n number of given tags in previous sessions between both the users (n here is the given number of tags) within computational time T. 

For simplicity purposes, we don't consider the explicit notation of parameter T in both unconditional and computational security. 

Now let's assume that the identification scheme is based on an unconditionally secured MAC, given that the attacker can access most given valid tags in various sessions using the same MAC key. As a result, the identification scheme will be unconditionally secured. Here, we also consider the size parameter of a random challenge used in a scheme. Let k denote the size. Using these conditions, we can give an upper bound on the probability that the attacker will fool User 2. Let's consider the following three cases - 

  • The value User 2 receives in the second flow is equal to the MACK = (ID(User 1) || Challenge received by User 2 from the first flow of the scheme) that wouldn't have been generated by User 2 previously in some other session.
     
  • Assuming the value User 2 receives in the second flow is generated by User 1 in a previous session. This is possible only if the Challenge (this Challenge is created by User 2 using a perfect random number generator) received by User 2 from the first flow is a random challenge and is generated by User 2. The probability of User 2 already using the Challenge mentioned above is 1/2k. Here the given number of valid tags used in previous sessions is considered. This results in the attacker reusing the MAC from a previous session. 
     
  • Assuming the value User 2 receives in the second flow is generated by the attacker. This would result in the attacker being successful, followed by the MAC's security.
     

To conclude, using the above assumptions, we have established the security of the underlying primitives as a function of the security of the identification scheme. This process is similar to computationally secure MAC.

Attack Model and Adversarial Goals 

Attack Models and Adversarial Goals

In this section of the article “There is a challenge and response in the secret-key setting” we will talk about Attack Model and Adversarial Goals. In an identification scheme, there are various subtleties that are associated with the attack models and adversarial goals. Let's look at the intruder-in-the-middle scenario - 

  • Note that this is not a parallel session attack, even though the attacker impersonates User 1 to User 2 in the first session and User 2 to User 1 in a parallel session. When the attacker receives User 2's Challenge, they send it to User 1. The response received by the attacker here is sent to User 2 and is accepted by User 2. 
     
  • However, this is not considered an actual attack as the two combined sessions result in a single session wherein User 1 has identified themselves successfully to User 2. The attacker is not an active part of the scheme here. We can demonstrate that this is not an attack with a precise formulation of the adversarial Goal. We do this by defining the attacker as an active adversary in a specified session if the attacker changes, diverts, or creates a message of the channel. Note that the attacker is not considered to be an active attacker if they only forward a message. 
     
  • The goal of the attacker is to make the initiator of the scheme "accept" in a session in which they are active. Therefore, according to the definition, the attacker here is not active in the scenario explained above. 
     

Another way to decide if there is an active attacker is to consider the view of a particular session for both users. Both the users interact with an intended peer here, i.e., User 1's intended peer is User 2 and vice versa. However, both users will have compatible views on the session if there isn't any active attack meaning that no message will be received out of order, and every message sent by User 1 will be received by User 2 and vice versa. This situation is known as matching conversations. In this model, we assume that candidates participating in the session are honest. 

Let's consider the attack models now. The attacker will gather information before deceiving User 2. In this phase, the attacker is a passive attacker as they observe the conversation between the users and not causing any harm. However, there may be an active attacker present in this phase. This is possible if the attacker can access the authentication tags for the key being used by both users. In this time frame, the attacker can deceive both User 1 and User 2. 

Mutual Authentication 

Mutual identification or mutual authentication is a scheme in which User 1 and User 2 prove and justify their identity to each other. If a session of the scheme is to be successful and completed, both users have to "accept." The attacker can deceive any or both of the users into accepting. The adversarial goal is to make an innocent user "accept" after a flow where the attacker is active.

Mutual Authentication

Conditions Specifying the Outcome of a Secure Mutual Authentication Scheme 

In this section of the article, we will talk about the conditions specifying the outcome of a secure Mutual Authentication scheme. The conditions mentioned below specify the outcomes of a secure mutual authentication scheme -

  • Assume that User 1 and User 2 are the two honest candidates in a session of a scheme and that a passive attacker exists. Then both of the users will "accept."
     
  • If there exists an active attacker in a scheme during a mentioned flow, then after the flow, no innocent candidates will "accept."


The attacker here may be inactive for a peculiar session and only become active once any one of the candidates accepts. Henceforth, it is essential for at least one candidate to "reject." The outcome of this session is that User 2 fails to prove their identity to User 1, but User 1 successfully proves its identity to User 2. This is known as disruption of the scheme. 

Ways in Which the Attacker Could be Active in a Session of a Scheme

In this section of the article, we will talk about the ways in which the attacker could be active in a session of a scheme -

  • The attacker will impersonate User 1 to deceive User 2 into "accepting."
     
  • The attacker will impersonate User 2 to deceive User 1 into "accepting."
     
  • The attacker tries to make both users accept. 
Ways in which the attacker could be active in a session of a scheme

We can achieve mutual authentication by making User 1 verify the identity of User 2 and vice versa in separate sessions. Designing a single scheme to identify both users will be more efficient.

If both users were to combine the two sessions of the one-way identification into one scheme, the number of flows required would be reduced significantly. But the resulting Mutual authentication scheme would be insecure. 

What Constitutes a Successful Attack?

In a parallel session attack, if the attacker impersonates User 2, initiates a new session with User 1, and deceives User 1, the scheme becomes insecure. This is because the attacker receives User 1's Challenge in the second flow and "accepts" before initiating the second session impersonating User 1. Now, the attacker will impersonate User 2 in the next session by sending the same Challenge to User 2 in the first flow, receiving User 2's response, and forwarding it to User 1 in the first session as the third flow. User 1 will now accept, making the attacker successful in impersonating User 2. Note that the second session was abandoned and not completed. This results in a successful attack. 

We can observe that the attacker reused a flow from the first session in a different flow and session. This is a problem, and there are ways to fix it. We need to design the flows such that every flow has information computed in it differently.

Frequently Asked Questions

When is the situation of matching conversation possible?

A matching conversation is possible between both users if there isn't any active attacker in the session.  

What is a secret-key cryptosystem?

It is a cryptosystem in which one secret key is mutually decided between the parties in this system. This private key is used to encrypt and decrypt data.

What is hybrid cryptography?

It is a technique that combines the benefits of both secret and public-key cryptosystems.

What is an Adversarial Goal?

The second aspect of security in cryptography is the Adversarial Goal. It tells us what the attacker is attempting to do and the motive behind the attacks. 

What is an Attack Model?

The first aspect of security in cryptography is the Attack Model. It tells us about the information that the attacker can access.

Conclusion

This article made us aware that there is a challenge and response in the secret-key setting, random challenges, MAC security, attack model and adversarial goals, and mutual authentication. If you want to dig deeper, here are some related articles - 


You may refer to our Guided Path on Code Studios to enhance your skill set on DSACompetitive ProgrammingSystem Design, and many more. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Previous article
Securing the Identification Schemes
Next article
Attack With Model With Adversarial Goals
Live masterclass