3.4 Diffie-Hellman and related Key Agreement Protocols

3.4 Diffie-Hellman and related Key Agreement Protocols

Key establishment protocols come in various avors. In key transport protocols, a key is created by one entity and securely transmitted to the second entity, while in key agreement proto cols both entities contribute information which is used to derive the shared secret key. In symmetric proto cols the two entities a priori possess common secret information, while in asymmetric protocols the two entities share only public informaiton that has been authenticated. This research is concerned with two-party authenticated key agreement proto cols in the asymmetric setting.

The design of asymmetric authenticated key agreement protocols has a checkered his-tory. Over the years, numerous protocols have been proposed to meet a variety of desirable security and performance requirements. Many of these protocols were subsequently found to be awed, and then either were modified to resist the new attacks, or were totally aban-doned. After a series of attacks and modifications, only those surviving protocols which had received substantial public security and were believed to resist all known attacks were deemed secure for practical usage [18].

This section focuses on asymmetric authentication key agreement protocols whose se-curity is based on intractability of the Diffie-Hellman problem. Next section says about the idea why discrete logs are generally used.

3.4.1 Why discrete logs and Diffie-Hellman?

Almost everything that public key cryptography provides, such as digital signatures and key exchange, can be accomplished with RSA and its variants. However, cryptosystems based on discrete exponentiation remain of interest for three main reasons [26]:

1. Patent issues The Diffie-Hellman patent expired in 1997. Therefore anyone in-terested in using public key cryptography in the United States (which is the only place where this patent was applied for and issued) can save money and also avoid licensing negotiations.

2. Technical advantages In many cases where algorithms of comparable function-ality exist, say one over the finite field of integers modulo a prime p, and another using a composite integer n of the same size, breaking the discrete log modulo p appears to be somewhat harder than factoring the integer n. Some other advantages of discrete log cryptosystems come from their limitations. It is widely believed that the U.S. Digital Signature Algorithm is based on discrete logs because it is harder to use it for encryption than if it were based on RSA (and thus on integer factorization). This helps enforce export control regulations on strong encryption without weakening the digital signature methods that are less stringently controlled. On the other hand, many people like the Diffie-Hellman algorithm, since the session key it generates is evanescent. In the simplest application of RSA to key generation, Alice creates a session key and transmits it to Bob using Bob’s public key. An eavesdropper who can co erce Bob afterwards into revealing his private key can then recover the full text of the communication exchanged by Alice and Bob. In contrast, if Alice and Bob use Diffie-Hellman to generate the session key, destroy it after the session ends, and do not store their communication, then neither coercion nor cryptanalysis will enable the eavesdropper to find out what information was exchanged.

3. They are Diffirent. Cryptographers have learned by bitter experience that it is unwise to put all eggs in a single basket. It is desirable to have a diversity of cryptosystems, in case one is broken. It is an unfortunate fact that discrete logs and integer factorization are so close that many algorithms developed for one problem can be modified to apply to the other. For security, it would be better to have much more diversity. However, more than two decades after the publication of the first two practical public key systems, the Diffiee-Hellman and the RSA algorithms, the only public key cryptosystems that are trusted and widely deployed are based on the presumed di culty of the same two problems those schemes relied upon. There have been many attempts to find public key schemes based on other principles, but so far most have led to systems that were broken, and the ones that are still standing are often regarded with suspicion.

The following notation is used throughout this chapter and the next.