Florida State University
Computer Science Department
NSA Security Proffesional
Security Related Courses
Security Related Conferences
Grant Proposal Tips
Protocols are rules that govern interactions between communicating parties and are fundamental to the implementation of communications systems. Protocols are used to allow parties in a communication session to remotely reach agreement in some area. Cryptographic protocols are security related interactions that support the same objective: gaining agreement regarding some important topic. In security related protocols, two common agreements to be reached are for authentication and key distribution.
Authentication, the act of determining the identity of a principal, is fundamental to any security system. Because of this, and because of its complexity and potential for error, authentication methods have been the topic of intense research. Most authentication schemes rely on some interaction, or challenge and response, between the authenticator and the one to be identified. These exchanges are called authentication protocols. Authentication protocols may be as simple as the authenticator offering a challenge to someone seeking physical access, such as the verbal command , to which the one to be identified would respond with some predefined password. If this password is sufficiently hard to guess and is well managed so that only the two principals in the exchange know it, success of this protocol offers reasonably sound evidence that the respondent is actually who the authenticator believes they are. If, however, an intruder is able to overhear the interaction and if the password is reused or is used to identify more than one individual, the intruder may use the overheard password to defeat the protocol.
Research in authentication protocols is aimed at identifying the potential threats to authentication and devising interactions that cannot be broken, i.e., that the successful execution of the authentication protocol does indeed provide strong evidence as to the identity of the subject(s). Cryptography is very useful for this purpose, which we will see in greater detail later.
There is no doubt that the introduction of keys into cryptographic systems was a revolutionary change that gave cryptographers a decided advantage over intruders, at least for a while. It also introduced the problem of key distribution into cryptographic systems. A characteristic of key-dependent systems is that the longer a key is used, the less secure are the communications using that key. Keys must be changed regularly and often. Privately distributing keys between remote principals is a very difficult, now classical, problem termed the Key Distribution problem. Like authentication, key distribution is routinely accomplished by a cryptographic protocol.
In order to address the network security problems of privacy, integrity, authentication, key distribution, etc., a strong cryptographic algorithm must be combined with a valid cryptographic protocol that establishes the rules governing interactions between participants (principals) in the communication. Only when combined with a valid protocol can cryptography provide the principals with a secure channel.
Cryptographic protocols are routinely represented as action lists describing the alternate transmission and receipt of messages between principals. The steps of the action list specify the contents of each message and the encryption and decryption operations utilized to protect and divulge the message meaning. The content and sequence of messages in the protocol agree to some pre-defined format and sequence. A successful run of the protocol may be seen as a serial trace of the steps of the protocol in the specified sequence.
It is the requirement for serial sequencing that is of interest here. The de facto serialization method that provides the sequencing in protocol runs is the blocking nature of the send and receive statements. This means that in a protocol run, a principal may not receive a message of a certain format until after a message of that format has been generated and transmitted. While it is clear that a receive cannot be legally accomplished unless a message of the specified format has been sent, it is not clear that the appearance of a message of the correct format means the protocol has executed in the correct sequence.
The below protocol is an example of a cryptographic protocol; in fact, one of the earliest published ones. The Needham and Schroeder Private Key Protocol [NS78] played a large part in the field of cryptographic protocol verification. The meaning of the notation is intuitive; the arrows indicate transmission and receipt of messages. The items after the colon for each step reflect the data to be transmitted and the braces signify encryption of the data within the braces. The identifier immediately after each right brace is the key used for encryption. The protocol is expressed in an hoc standard cryptographic protocol pseudocode language with the messages presented in the order they are expected to be executed.
Needham and Schroeder Private Key Protocol
In order to illustrate the meaning of the pseudocode notation, consider the given protocol. In the first step, principal A indicates to the central authentication server that A desires to initiate a secure communication with principal B. A includes with this message a random number called a nonce to be used to guarantee the freshness of a later message. Nonces are, as Webster defines in the new world dictionary, ?... created only once for a special occasion". They are selected randomly so that they are unpredictable so any message received containing a specific nonce is assumed to be a response to the original message containing the nonce.
In the second step, S provides A a key to be used in a communication session between A and B, appropriately named kab. Also included in the second message is an encrypted component that A cannot read containing the key kab and the identity of A encrypted under the key shared between B and S (kbs). This encrypted catenation will be forwarded by A to B in the next step. The entire second message is encrypted under the private key kas that A shares with S. A uses kas to decrypt the message and obtain the session key kab, nonce na, and the encrypted message to be relayed to B. Before executing the third step, A verifies the currency of nonce na by comparing the representation of na that was received from the second step with the value na that A transmitted in the first message.
In the third step of this protocol, A forwards the message generated by S to B. B uses the key kbs that B shares with S to decrypt the message and obtain the key kab and the identity of the originator, A. In step four, B forwards a new nonce to A encrypted under the session key kab. When A receives the message sent in step 4 and uses kab to decrypt the nonce from B, A then believes B has the key and is ready to communicate because A believes that only B could know key kab.
In the last step, A modifies the nonce from B slightly, re-encrypts the new value and sends it to B. Because A modifies the nonce from B in a predetermined way and since B believes that only A could have the key kab, when B decrypts the modified nonce and compares it to the expected response, B believes that A has the key and is ready to communicate.
As this simple example illustrates, it is easy to see how verifying security protocols can be difficult. Nonetheless, it is essential to network and information security. Research in this area is fertile and will be for the foreseeable future.
Additional Protocol Information