Cryptanalysis and protocol failures (abstract)

ABSTRACT

In this lecture examples will be given of key distribution protocols that distribute keys to unintended recipients, secrecy protocols that publicly reveal the contents of (supposedly) secret communications, digital signature protocols that make forgery easy — all based on cryptoalgorithms that are sound so far as is known. In at least one case the cryptographic algorithm that is employed is Vernam encryption/decryption with a properly chosen one time key which is well known to be unconditionally secure; in spite of which the protocol fails totally.

From the standpoint of applications there is scarcely any topic of greater importance than the cryptanalysis of protocols, since protocols are — in the vernacular of advertising — “where the rubber meets the road”, i.e. where the principles of cryptography get applied to the practice of insuring the integrity of information. The design and/or analysis of cryptographic algorithms is the domain of the mathematician and the cryptographer and can be carried out in large part without regard to applications. The design and analysis of protocols, however, is inextricably linked to the system in which the protocol is to be used, and originates with an application: the function of the protocol being to realize the integrity properties required by the application. Cryptographic algorithms are simply component elements in the design of protocols — and as we've indicated, the security of the one does not necessarily imply the security of the other. When expressed in this way, protocol failures do not seem so improbable or surprising as they do when described as defined above. In real life though, almost every example of a true protocol failure is also an example of what can aptly be characterized as “Well I'll be damned” discoveries, since this describes the reaction of most people when they first have such a failure pointed out to them.

Similiarly, if a protocol calls for one of the participants — who may be a “trusted” key generation bureau for example — to start by constructing a composite number as the product of two primes, chosen so as to make the factorization of their product be computationally infeasible, the suspicion must be that the product is not of this form. It is easy to verify in probability that a number is not a prime, and computationally feasible for numbers of a few hundred decimal digits in size to do so deterministically. It is generally believed by computational number theorists, however, that it just as difficult to test whether a composite number is the product of more than two factors as it is to factor it. Consequently, if a protocol calls for such a composite number to be generated by one of the participants, it is essential in the cryptanalysis to examine whether there are any exploitable consequences of it being the product of more than two prime numbers. For example, it is easy to conceal a covert channel in a signature protocol that calls for the use of a modulus which is the product of two primes, if the modulus is the product of three primes instead.

There is a long list — too long for a single paper and much too long for an abstract — of examples of protocol failures that derive from a quantity not being what it is supposed to be, or what it is advertised to be. The two examples above should give the reader a feeling for what is involved in protocol analysis.

The cryptanalysis of protocols consists of three steps:

• Carefully enumerate all of the properties of all of the quantities involved; both those explicitly stated in the protocol and those implicitly assumed in the setting.

• Take nothing for granted. In other words go through the list of properties assuming that none of them are as they are claimed or tacitly assumed to be unless a proof technique exists to verify their nature. For each such violation of property, critically examine the protocol to see if this makes any difference in the outcome of the execution of the protocol. Combinations of parameters as well as single parameters must be considered.

• Finally, if the outcome can be influenced as a result of a violation of one or more of the assumed properties, it is essential to then determine whether this can be exploited to advance some meaningful deception. There are several well known protocols in which it is possible to influence the outcome by violating the assumed properties of one or more of the parameters involved, but in which no known meaningful deception can be worked or furthered as a result. Protocol failures occur whenever the function of the protocol can be subverted as a consequence of the violations.

This lecture will illustrate the application of these rules for the cryptanalysis of protocols with several examples of pure protocol failures discovered using them.

Index Terms

• Security and privacy

  • Cryptography

  • Security services

    • Access control

  • Systems security

    • Operating systems security