 Threepass protocol

In cryptography, the threepass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute encryption keys. This message protocol should not be confused with various other algorithms which use 3 passes for authentication.
It is called the threepass protocol because the sender and the receiver exchange three encrypted messages. The first threepass protocol was developed by Adi Shamir circa 1980, and is described in more detail in a later section. The basic concept of the ThreePass Protocol is that each party has a private encryption key and a private decryption key. The two parties use their keys independently, first to encrypt the message, and then to decrypt the message.
The protocol uses an encryption function E and a decryption function D. The encryption function uses an encryption key e to change a plaintext message m into an encrypted message, or ciphertext, E(e,m). Corresponding to each encryption key e there is a decryption key d which allows the message to be recovered using the decryption function, D(d,E(e,m))=m. Sometimes the encryption function and decryption function are the same.
In order for the encryption function and decryption function to be suitable for the ThreePass Protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, D(d,E(k,E(e,m))) = E(k,m). In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is orderindependent, i.e. it satisfies E(a,E(b,m))=E(b,E(a,m)) for all encryption keys a and b and all messages m. Commutative encryptions satisfy D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).
The ThreePass Protocol works as follows:
 The sender chooses a private encryption key s and a corresponding decryption key t. The sender encrypts the message m with the key s and sends the encrypted message E(s,m) to the receiver.
 The receiver chooses a private encryption key r and a corresponding decryption key q and superencrypts the first message E(s,m) with the key r and sends the doubly encrypted message E(r,E(s,m)) back to the sender.
 The sender decrypts the second message with the key t. Because of the commutativity property described above D(t,E(r,E(s,m)))=E(r,m) which is the message encrypted with only the receiver's private key. The sender sends this to the receiver.
The receiver can now decrypt the message using the key q, namely D(q,E(r,m))=m the original message.
Notice that all of the operations involving the sender's private keys s and t are performed by the sender, and all of the operations involving the receiver's private keys r and q are performed by the receiver, so that neither party needs to know the other party's keys.
Contents
Shamir threepass protocol
The first ThreePass Protocol was the Shamir ThreePass Protocol developed circa 1980. It is also called the Shamir NoKey Protocol because the sender and the receiver do not exchange any keys, however the protocol requires the sender and receiver to have two private keys for encrypting and decrypting messages. The Shamir algorithm uses exponentiation modulo a large prime as both the encryption and decryption functions. That is E(e,m) = m^{e} mod p and D(d,m) = m^{d} mod p where p is a large prime. For any encryption exponent e in the range 1..p1 with gcd(e,p1) = 1. The corresponding decryption exponent d is chosen such that de ≡ 1 (mod p1). It follows from Fermat's Little Theorem that D(d,E(e,m)) = m^{de} mod p = m.
The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = m^{ab} mod p = m^{ba} mod p = E(b,E(a,m)).
MasseyOmura cryptosystem
The MasseyOmura Cryptosystem was proposed by James Massey and Jim K. Omura in 1982 as a possible improvement over the Shamir protocol. The MasseyOmura method uses exponentiation in the Galois field GF(2^{n}) as both the encryption and decryption functions. That is E(e,m)=m^{e} and D(d,m)=m^{d} where the calculations are carried out in the Galois field. For any encryption exponent e with 0<e<2^{n}1 and gcd(e,2^{n}1)=1 the corresponding decryption exponent is d such that de ≡ 1 (mod 2^{n}1). Since the multiplicative group of the Galois field GF(2^{n}) has order 2^{n}1 Lagrange's theorem implies that m^{de}=m for all m in GF(2^{n})^{*} .
Each element of the Galois field GF(2^{n}) is represented as a binary vector over a normal basis in which each basis vector is the square of the preceding one. That is, the basis vectors are v^{1}, v^{2}, v^{4}, v^{8}, ... where v is a field element of maximum order. By using this representation, exponentiations by powers of 2 can be accomplished by cyclic shifts. This means that raising m to an arbitrary power can be accomplished with at most n shifts and n multiplications. Moreover, several multiplications can be performed in parallel. This allows faster hardware realizations at the cost of having to implement several multipliers.
Security
A necessary condition for a threepass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages E(s,m), E(r,E(s,m)) and E(r,m).
For the encryption functions used in the Shamir algorithm and the MasseyOmura algorithm described above, the security relies on the difficulty of computing discrete logarithms in a finite field. If an attacker could compute discrete logarithms in GF(p) for the Shamir method or GF(2^{n}) for the MasseyOmura method then the protocol could be broken. The key s could be computed from the messages m^{r} and m^{rs}. When s is known, it is easy to compute the decryption exponent t. Then the attacker could compute m by raising the intercepted message m^{s} to the t power. K. Sakurai and H. Shizuya show that under certain assumptions breaking MasseyOmura cryptosystem is equivalent to the DiffieHellman assumption.
Authentication
The threepass protocol as described above does not provide any authentication. Hence, without any additional authentication the protocol is susceptible to a maninthemiddle attack if the opponent has the ability to create false messages, or to intercept and replace the genuine transmitted messages.
References
 U.S. Patent 4,567,600, U.S. patent on the MasseyOmura cryptosystem
 Alan G. Konheim (1981) Cryptography: A Primer 3467.
 A. Menezes, P. VanOorschot, S. Vanstone (1996) Handbook of Applied Cryptography 500, 642.
 K. Sakurai and H. Shizuya (1998) "A Structural Comparison of the Computational Difficulty of Breaking Discrete Log Cryptosystems" Journal of Cryptology 11: 2943.
Publickey cryptography Algorithms Benaloh · Blum–Goldwasser · Cayley–Purser · CEILIDH · Cramer–Shoup · Damgård–Jurik · DH · DSA · EPOC · ECDH · ECDSA · EKE · ElGamal (encryption · signature scheme) · GMR · Goldwasser–Micali · HFE · IES · Lamport · McEliece · Merkle–Hellman · MQV · Naccache–Stern · NTRUEncrypt · NTRUSign · Paillier · Rabin · RSA · Okamoto–Uchiyama · Schnorr · Schmidt–Samoa · SPEKE · SRP · STS · Threepass protocol · XTR
Theory Standardization ANS X9F1 · CRYPTREC · IEEE P1363 · NESSIE · NSA Suite B
Topics Digital signature · OAEP · Fingerprint · PKI · Web of trust · Key size
Cryptography Categories: Asymmetrickey cryptosystems
Wikimedia Foundation. 2010.
Look at other dictionaries:
Protocol stack — The protocol stack is an implementation of a computer networking protocol suite. The terms are often used interchangeably. Strictly speaking, the suite is the definition of the protocols, and the stack is the software implementation of them.[1]… … Wikipedia
Oakley protocol — The Oakley Key Determination Protocol is a key agreement protocol that allows authenticated parties to exchange keying material across an insecure connection using the Diffie Hellman key exchange algorithm. The protocol was proposed by H. Orman… … Wikipedia
Aggregate Level Simulation Protocol — The Aggregate Level Simulation Protocol (ALSP) is a protocol and supporting software that enables simulations to interoperate with one another. Replaced by the High Level Architecture (simulation) (HLA), it was used by the US military to link… … Wikipedia
Simple Network Management Protocol — (SNMP) forms part of the internet protocol suite as defined by the Internet Engineering Task Force (IETF). SNMP is used in network management systems to monitor network attached devices for conditions that warrant administrative attention. It… … Wikipedia
The Fourth Protocol — Infobox Book name = The Fourth Protocol title orig = translator = image caption = author = Frederick Forsyth illustrator = cover artist = country = United Kingdom language = English series = subject = genre = Thriller novel publisher = Hutchinson … Wikipedia
MQV — (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie Hellman schemes, MQV provides protection against an active attacker. The protocol can be modified to work in… … Wikipedia
Publickey cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key … Wikipedia
Diffie–Hellman key exchange — (D–H)[nb 1] is a specific method of exchanging keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge … Wikipedia
Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… … Wikipedia
Distributed key generation — For some protocols no party should be in the sole possession of the secret key. Rather, during distributed key generation every party obtains a share of the key. A threshold of the participating parties need to cooperate in order to achieve a… … Wikipedia