This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week we look at a security definition for authenticated key exchange.
Establishing a shared key between two parties is one of the oldest problems in cryptography, and turns out to be much harder than standard encryption, even when just considering definitions. Although the classic Diffie-Hellman protocol from 1976 seems to solve the problem, it provides no authenticity guarantee - i.e. that a key has been agreed with the right person - since a man-in-the-middle attack can easily be performed.
To model this kind of attack, and others, we need a security definition. There are two main approaches when defining the security of a key exchange protocol, namely those based on a symbolic model and those using a computational model. In the symbolic model, which become popular in the '90s after the classic paper on BAN logic, techniques from formal methods are used to model and analyse a protocol. The symbolic model is good for identifying attacks, but it is difficult for the underlying logic to capture all classes of attacks, so analysis in this model does not provide great security guarantees, but can be semi-automated using theorem provers.
In their seminal 1993 paper, Bellare and Rogaway instead created a game-based security definition for authenticated key exchange in a computational model, similar to the IND-CPA and IND-CCA definitions for encryption. In this model, cryptographic primitives are not assumed to be unbreakable, but instead we attempt to quantify the success probability of an adversary by computing their 'advantage' in a security game. The main feature of an adversary that we wish to encompass is that all communication is under the adversary's control: they can read, modify, delay and replay messages. They can also run any number of instances of the protocol simultaneously with other parties. The intuition behind the AKA security game is that the only way an adversary can get a party to accept an agreed key is by forwarding honest messages from a genuine protocol run, in which case they cannot possibly learn anything new.
The security game consists of a number of different oracles that an adversary can query. The three main oracles are the corruption oracle, which allows the adversary to take control of a chosen party, the key registration oracle, which registers a public key for any chosen user, and the message oracle, which is the main oracle used for passing messages. Note that messages are not sent directly between the participants, instead the adversary does this using the message oracle.
The message oracle is the main oracle allowing the adversary to create protocol sessions with parties (where they aim to establish a short-term, or ephemeral, shared key) and send messages. When querying the oracle, they can take one of the following actions:
A protocol is said to be a secure authenticated key exchange protocol if it is correct, and any adversary's strategy is the above game is no better than random guessing. The above outline is only a rough sketch, of course, and there are many further details in the paper.
Establishing a shared key between two parties is one of the oldest problems in cryptography, and turns out to be much harder than standard encryption, even when just considering definitions. Although the classic Diffie-Hellman protocol from 1976 seems to solve the problem, it provides no authenticity guarantee - i.e. that a key has been agreed with the right person - since a man-in-the-middle attack can easily be performed.
To model this kind of attack, and others, we need a security definition. There are two main approaches when defining the security of a key exchange protocol, namely those based on a symbolic model and those using a computational model. In the symbolic model, which become popular in the '90s after the classic paper on BAN logic, techniques from formal methods are used to model and analyse a protocol. The symbolic model is good for identifying attacks, but it is difficult for the underlying logic to capture all classes of attacks, so analysis in this model does not provide great security guarantees, but can be semi-automated using theorem provers.
In their seminal 1993 paper, Bellare and Rogaway instead created a game-based security definition for authenticated key exchange in a computational model, similar to the IND-CPA and IND-CCA definitions for encryption. In this model, cryptographic primitives are not assumed to be unbreakable, but instead we attempt to quantify the success probability of an adversary by computing their 'advantage' in a security game. The main feature of an adversary that we wish to encompass is that all communication is under the adversary's control: they can read, modify, delay and replay messages. They can also run any number of instances of the protocol simultaneously with other parties. The intuition behind the AKA security game is that the only way an adversary can get a party to accept an agreed key is by forwarding honest messages from a genuine protocol run, in which case they cannot possibly learn anything new.
The security game consists of a number of different oracles that an adversary can query. The three main oracles are the corruption oracle, which allows the adversary to take control of a chosen party, the key registration oracle, which registers a public key for any chosen user, and the message oracle, which is the main oracle used for passing messages. Note that messages are not sent directly between the participants, instead the adversary does this using the message oracle.
The message oracle is the main oracle allowing the adversary to create protocol sessions with parties (where they aim to establish a short-term, or ephemeral, shared key) and send messages. When querying the oracle, they can take one of the following actions:
- Start a new session between two users
- Learn the secret key of any terminated session
- Send a message in an existing session and receive the response
A protocol is said to be a secure authenticated key exchange protocol if it is correct, and any adversary's strategy is the above game is no better than random guessing. The above outline is only a rough sketch, of course, and there are many further details in the paper.
No comments:
Post a Comment