Table of contents
1. Field of application of the proposal 2. Session key establishment is critical to data protection 3. PEKE overview . . . . PEKE is effective in automatically providing a session key . . . . PEKE is efficient 4. PEKE security . . . . PEKE protection is features-rich . . . . PEKE security may readily be audited and endorsed . . . . PEKE security foundation is already widely accepted 5. PEKE ease of implementation . . . . PEKE protocol is simple . . . . PEKE uses familiar mathematical programming . . . . PEKE allows "entry level" public key cryptography 6. PEKE and other cryptosystems . . . . PEKE and prior patented technology . . . . PEKE and other methods for session key exchange (Diffie-Hellman and public key encryption) . . . . PEKE and secret key cryptosystems . . . . PEKE and RSA digital signatures . . . . PEKE and digital signatures based on the discrete logarithm ReferencesThis proposal facilitates the development of new information security applications, or the revision of existing ones. With the ever-increasing importance of computers, telecommunications and electronics in every aspects of our lives, information security is becoming a growing concern (rights to privacy, controlling access to databases and networks, fraud prevention, accountability of trading partners).
In the field of information security, cryptographic methods are involved. The reader may already know the distinction between secret-key cryptography and public-key cryptography. In short, secret-key cryptosystems are based on preliminary mutual agreement on secret keys. Public key cryptosystems are based on ingenious mathematical transformations allowing data protection between unrelated parties.
Any cryptographic method is easily classified as either a secret-key cryptosystem or a public key cryptosystem. This proposal (PEKE) is a public key cryptosystem with a combination of characteristics previously not found in any single cryptosystem.
In practice, an information security application implements a number of cryptographic methods whose characteristics complement each other. There are many good technical reasons why this proposal (PEKE) should be one of them.
In summary, this proposal will be very attractive to system designers that were assigned the task of implementing information security functions in a hardware, software or telecommunications product. They will find the PEKE technology effective, efficient, features-rich, and readily available.
This proposal (PEKE) is an automated method for session key establishment. In this section, the notion of a session key is explained. The reader familiar with this notion may skip to next section.
A session key is secret information (in the form of an arbitrary bit string or number). This secret is shared between two parties involved in a message transmission or a connection. A session key enables encryption of message contents, encryption of password (e.g. a personal identification number, PIN, entered at an automated banking machine), and facilitates data integrity protection (prevention of malicious data modification).
Strictly speaking, a session key is not always required for a cryptographic application. A digital signature may provide authentication (assurance about the identity of the remote communicating party), non-repudiation (authentication that can be used as evidence for a third party, e.g. a judge), and data integrity (a digital signature is bound to a specific message). In practice however, implementing digital signatures requires ancillary protection (e.g. data integrity for the public key of a certification authority) that usually requires a session key.
How a session key is obtained in the first place is important. If a session key is manually and securely provided to its legitimate user, it may provide authentication (this is a classical application of secret key cryptography). If a session key is known to be unique to a transmission or a connection, it prevents replay of an old message. If a party participates in the session key selection, he gets assurance about the timeliness or freshness of any reply based on this session key.
PEKE stands for Probabilistic Encryption Key Exchange. The PEKE technology is a public key cryptosystem specialized in automated session key establishment. This proposal encompasses the core PEKE technology (covered by a patent application in Canada [17], in the public domain elsewhere) and related know-how, software, and products to assist in smooth and efficient implementation of information security applications.
The PEKE technology allows the creation of a session key as if some magic allowed two unrelated parties to agree on a secret without talking to each other in confidence. This problem was described by the cryptographer Gilles Brassard in these terms [5]:
"... Assume to the contrary that two given users initially share no secret information, and that they suddenly wish to establish secure communications between them. The conventional solution would be for them to meet physically in order to exchange a secret key, or to make use of some sort of trusted courier. Both these solutions are slow and expensive, and they may not be all that safe. The purpose of a public-key distribution system is to allow two such users to come up with a secret key as a result of a discussion over an insecure channel, in a way that an eventual eavesdropper cannot figure out the key after listening to the entire discussion. ... Let us stress again that this must be achieved even though A and B share no information beforehand that is unknown to the eavesdropper. ..."
With the PEKE technology, one of the two parties in the secret key exchange is assigned the initiator role. For instance in the context of an application, the called party could be assigned the initiator role (like saying "hello" when answering the telephone). The other party is assigned the responder role. There is one message sent from the initiator to the responder, and one reply sent from the responder back to the initiator. After these two messages (and some specific mathematical transformations of randomly selected values), there is a shared secret key that the eavesdropper can not recover. This is explained in details in [17] (the PEKE patent application) and reference [16] (available on-line).
Public key cryptosystems are usually so compute-intensive that even the fastest computers process data at a deceptively low throughput. The public key cryptosystems that are reportedly efficient are, like PEKE itself, asymmetrical: the mathematical transformations (hence the computation workload) are different for each of the two parties. For instance, with the introduction of the NIST's Digital Signature Algorithm, there was much debate over the relative efficiency of digital signature generation versus digital signature verification [24].
The following observations relate to the PEKE efficiency:
The significant fact about PEKE efficiency is the small workload assigned to the responder of the secret key exchange. It makes PEKE especially well suited for low power applications like smart cards and cellular telephones.
In an information security application, a number of cryptographic mechanisms provide protection that complement each other (confidentiality, data integrity, authentication in each direction, non-repudiation, timeliness, ...).
PEKE integrates a greater number of protection in a single mathematical formulation than any other cryptosystem used for session key establishment. This is discussed at length in another document that is intended for a meticulous threat analysis of security applications. In summary:
Integration of protection in the smallest number of cryptographic mechanisms is a good way to strengthen the security of the whole application (identifying and fixing the weakest link in a small chain is easier than with a long one). Also, given the small computation workload to the responder, PEKE is a very productive way of securing an application.
The security of the PEKE technology originates from theoretical work done in the early 1980's by a number or distinguished mathematicians and published in 1984-1986 ([3], [26], [4]). This body of scientific knowledge is very well explained by cryptographer Gilles Brassard in chapter 4 of [5], which is an excellent introduction.
This theoretical foundation facilitates the review of the PEKE technology by practitioners of cryptography. An independent reviewer may focus his attention on diverse and creative attacks that could threaten the PEKE secret key exchange, to find out that a proven mathematical property of the "x² mod N" counters these attacks or voids any information obtained from them.
Recent experience showed once again that theoretical concerns should be taken seriously. Until recently, the adaptatively chosen ciphertext attack could be looked at as an issue discussed among academic circles. The PEKE underlying security foundation is definitely vulnerable to this attack, but an explicit countermeasure is built-in the PEKE scheme. The RSA cryptosystem is less conspicuously vulnerable to the attack, so some countermeasures were put in place, maybe without sufficient attention to their criticalness. One such countermeasure present in the number one standard related to RSA, has now been attacked by a researcher [2], so that the standard has now to be phased out (it's literally the nomber one standard by its name PKCS #1 [20]). Also, an international standard for digital signature ([12], [8]) is currently being put into question. The PEKE countermeasure is more squarely put in the way of the adaptatively chosen ciphertext attack.
PEKE has the same security foundation as the foremost public key cryptosystem (RSA, [19], [21]). This security foundation is the difficulty of factoring a large integer (public parameter N of "x² mod N") that is the product of two large prime numbers. Since there is abundant literature on the selection of N for this other cryptosystem, this aspect of the PEKE technology is already addressed by outside reviewers.
In contrast with other public key cryptosystems, secret key exchange is conceptually simpler and the PEKE effective security is more directly related to its ultimate security foundation.
The PEKE secret key exchange requires a simple message-then-reply protocol. This protocol may be off-line, or embedded in the connection establishment phase of an existing protocol.
The PEKE technology uses the same basic mathematical programming as every leading public key cryptosystem. It means that if an application requires a digital signature, its design will include the required basic maths for PEKE. Moreover, a current design may easily be upgraded to PEKE if it uses any public key algorithm. The basic arithmetic computations required for the PEKE responder are explained in two other on-line documents, respectively in the narrow context of subtle software optimizations and in the broader context of programming a pseudo-random number generator using the same "x² mod N" construct as PEKE.
Since its inception in the late 1970's, the field of public key cryptography promised the ubiquitous use of digital signatures, obsolescence of handwritten signatures, and guaranteed privacy in telecommunications. This has yet to occur, but the specialists are refining this vision with the addition of central administrations (certification authorities) that will foster the advent of ubiquitous public key cryptography by authenticating the public key of user entities (see for instance [25]). A end-user system relies on security certificates to authenticate other end-user systems. A cornerstone public key always remain (the certification authority's public key) that must be protected by data integrity within the end-user system.
The PEKE technology is compatible with the notion of certification authorities. The PEKE initiator's public key may be authenticated by a security certificate, like any other public key cryptosystem.
There are two ways in which PEKE can free an application from the requirements of certification authorities:
In the course of its R&D activities, CONNOTECH is dedicated to searching available sources of knowledge. This prior art research focuses on primary sources of information and includes patents (and patent applications when available). In the course of this research CONNOTECH never became aware of any disclosure of an invention more closely related to the PEKE technology than any reference of this document. References [15], [10], [9], and [1] may be cited as indicative of other directions for improvements in the area of session key exchange.
The PEKE technology is an alternative to the Diffie-Hellman cryptosystem ([6], [11]). The correspondence between the two is direct: same functionality and same underlying protocol requirements. PEKE has an efficiency advantage and offers additional protection (e.g. authentication).
The PEKE technology is an alternative to public key encryption (used for secret key transport, e.g. RSA). PEKE offers additional protection against replay attacks. Moreover, PEKE makes active eavesdropping attacks much harder to complete. For the designer, the only difference is the simple PEKE protocol (message-then-reply) which must be accommodated in replacement of a single message transmission.
By definition, secret key cryptosystems require a secret key. The most frequent application of public key cryptography is indeed session key establishment for secret key cryptosystems, notably secret key encryption. PEKE is well suited to this application.
When an application requires digital signatures, RSA ([19], [21]) is a foremost alternative. In tandem with RSA digital signatures, PEKE has a potential efficiency advantage in public key management: the public key used for PEKE and for RSA signatures may be the same (for the RSA modulus component), without loss of security. It is recommended to use a different public key for RSA signature than for RSA encryption. Given that the PEKE and the RSA algorithms are radically different but share a common subset of requirements (for the modulus), using the same modulus should not create any theoretical difficulty. This idea is suggested in [14] where the "x² mod N" generator is used in combination with RSA encryption to counter some very specialized forms of attack.
The efficiency advantages of a single public key for RSA digital signature and PEKE secret key exchange are many: memory savings for keys and security certificate storage, less processing and transmission time devoted to security certificate issue, storage, delivery and verification. This processing efficiency advantage is compounded by the observation that RSA signatures are relatively more efficient for the verification operation, which is done by the very same party (the PEKE responder) already benefiting from the PEKE efficiency.
There are a few digital signature schemes based on the discrete logarithm problem (ElGamal [7], Schnorr [22], [23], DSA [18], [13], [24]). They don't offer a session key establishment capability. So PEKE is nicely complementing the functions of these digital signature schemes. In addition, this type of digital signatures requires a random secret number different for each digital signature.
Two of these schemes (namely Schnorr and DSA) are efficient for signature generation. For an application requiring the PEKE responder to digitally sign a message, this suggests PEKE and a digital signature scheme based on discrete logarithm as a way to minimize computation workload.
[1] USA patent document 5,406,628, Beller, Michael J., Yacobi, Yacov, Public Key Authentication and Key Agreement for Low-cost Terminals, April 11, 1995 (application number 101,437, August 2, 1993)
[2] Bleichenbacher D., Chosen Ciphertext Attacks against Protocols Based on RSA Encryption Standard PKCS #1 in Advances in Cryptology, CRYPTO'98, LNCS vol. 1462, pages: 1-12, 1998.
[3] Blum, Leonore, Blum, Manuel, and Shub, M., A Simple Unpredictable Pseudo-random Number Generator, SIAM Journal of Computing, vol. 15, no. 2, May 1986, pp 364-383
[4] Blum, Manuel, and Goldwasser, Shafi, An Efficient Probabilistic Public-key Encryption Scheme which Hides All Partial Information, In Advances in Cryptology: Proceedings of Crypto'84, Springer-Verlag, 1985, pp 289-299
[5] Brassard, Gilles, Modern Cryptology, a Tutorial, Lecture Notes in Computer Science, no. 325, Springer-Verlag, 1988
[6] Diffie, Bailey Whitfield, Hellman, Martin E., New Directions in Cryptography, IEEE Transactions in Information Theory, vol IT-22, 1976, pp 644-654
[7] ElGamal, Taher, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory, Vol. IT-31, No. 4, July 1985, pp 469-472
[8] Guillou, Louis Claude, Quisquater, Jean-Jacques, Walker, Mike, Landrock, Peter, and Shaer, Caroline, Precautions taken against various potential attacks in ISO/IEC DIS 9796 'Digital signature scheme giving message recovery', Advances in Cryptology, Eurocrypt'90, Lecture Notes In Computer Science no. 473, pp 465-473
[9] Harn, Lein, Digital signature for Diffie-Hellman public keys without using a one-way function, Electronics Letters, to appear
[10] Harn, Lein, Modified Key Agreement Protocol based on the Digital Signature Standard, Electronics Letters, March 1st, 1995, v.31 no.6, pp 448-449
[11] USA patent document 4,200,770 Hellman, Martin E., Diffie, Bailey Whitfield, Merkle, Ralph C., Cryptographic Apparatus and Method, April 29, 1980 (the Canadian equivalent to this patent is patent number 1,121,480)
[12] ISO/IEC 9796:1991, Information Technology - Security Techniques - Digital Signature Scheme Giving Message Recovery
[13] Kravitz, David William, Digital Signature Algorithm, International application published under the Patent Cooperation Treaty (PCT), number WO 93/03526, World Intellectual Property Organization, February 18, 1993 (U.S. patent application 736,451, July 26, 1991, canadian patent application 2,111,572, July 24, 1992)
[14] Lim, Chae Hoon, and Lee, Pil Joong, Another Method for Attaining Security Against Adaptively Chosen Ciphertext Attack, in Advances in Cryptology, CRYPTO'93, LNCS no. 733, Springer-Verlag, 1994, pp 420-434
[15] Lim, Chae Hoon, and Lee, Pil Joong, Several Protocols for Authentication and Key Exchange, in Information Processing Letters 53 (1995) 91-96
[16] Moreau, Thierry, Probabilistic Encryption Key Exchange, Electronics Letters, Vol. 31, number 25, 7th December 1995, pp 2166-2168
[17] Moreau, Thierry, Apparatus and Method for Cryptographic System Users to Obtain a Jointly Determined, Secret, Shared, and Unique Bit String, Canadian patent application number 2,156,780, filed on August 23, 1995, laid-open to the public on September 23, 1995, CONNOTECH Experts-conseils Inc., Montréal, Canada
[18] National Institute of Standards and Technology (NIST), Digital Signature Standard, Federal Information Processing Standards Publication FIPS PUB 186, U.S. Department of Commerce, May 1994
[19] Rivest, Ronald L., Shamir, Adi, Adleman, Leonard M., A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, vol 21, 1978, pp 120-126
[20] RSA Laboratories, PKCS #1: RSA Encryption Standard, version 1.5, November 1993.
[21] USA patent document 4,405,829 Rivest, Ronald L., Shamir, Adi, Adleman, Leonard M., Cryptographic Communications System and Method, September 20, 1983
[22] Schnorr, Claus P., Efficient Identification and Signatures for Smart Cards, in Advances in Cryptology - Crypto'89, Springer-Verlag, 1990, pp 239-251
[23] USA patent document 4,995,082, Schnorr, Claus P., Method for Identifying Subscribers and for Generating and Verifying Electronic Signatures in a Data Exchange System, February 19, 1991
[24] Smid, Miles E., and Branstrad, Dennis K., Response to Comments on the NIST Proposed Digital Signature Standard, Advances in Cryptology, Proceedings of Crypto'92, pp 76-88
[25] Tardo, J.J., and Alagappan, K., SPX: Global Authentication Using Public Key Certificates, in Proceedings of the 1991 IEEE Computer Society Symposium on Research in Security and Privacy, 1991, pp 232-244
[26] Vazirani, Umesh V., and Vazirani, Vijay V., Efficient and Secure Pseudo-random Number Generation, Proceedings of the 25th IEEE Symposium on the Foundations of Computer Science, 1984, pp 458-463
CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691
Fax: +1-514-385-5900