The "double-lock" algorithm, or more formally a Shamir Three-pass protocol, is an encryption process by which a secure message may be sent without a need for public/private keys. However, it therefore lacks the advantages of such schemes, notably the ability to prove identity, and does not negate the vulnerability to man in the middle attacks. Still, it's relatively simple to understand and thus provides an easy introduction to some of the central ideas of cryptography.
The name arises from a simple explanation of the concept in terms of locks and boxes. Suppose that our protagonists, Alice and Bob, have access to unbreakable boxes and locks that cannot be picked, but only have the keys to their own locks; and that Alice wishes to send a gift to Bob. Alice can lock the gift in one of the boxes, and send that to Bob. Obviously Bob can't open it without the key, but he can attach one of his own locks to the box and mail it back. On receipt of this very secure package, Alice can use her key to remove the lock she originally attached; but, since the package still has Bob's lock, she can safely post it back to him. On arrival, Bob just has to remove his lock to open the box and receive the gift.
However, without absolute faith in the postal service, all that Bob can be sure of is that he's the only person capable of opening the box he finally receives; there's no guarantee that Alice sent it; just that whoever mailed the locked box subsequently unlocked it. Nor can Alice be sure that Bob ultimately receives the gift.
The Man in the Middle
To see this, let's introduce a third, malicious, character: the dastardly
Mallory, who works at the
sorting office and has his own supply of boxes and keys. Alice sends her locked box to Bob, but Mallory intercepts it. He then does two things: attach a lock to the box and post it back to Alice; and lock an empty box with one of his own locks to send to Bob. Bob finds himself with a locked box, and dutifully attaches a lock, and sends it back to Alice, except Mallory gets it. Alice, meanwhile, has received a box back with a second lock on it, so, assuming it to be Bob's, removes her lock and drops the package back in the post where it finds its way to Mallory.
Our villain now has two boxes- the one from Alice, containing the gift and secured only by one of his own locks; and a doubly-locked empty box. Removing both of his own locks, he takes the gift and mails the empty box, secured by Bob's lock, back to Bob. Bob will recognise the lock as his own, and thus knows that only he can gain access to the contents- but of course, there are no contents to access!
Such a turn of events would of course tip off Bob that something was wrong; but additional deviousness on Mallory's part could render the situation even more dire. Suppose, for instance, that Alice and Bob were using the boxes to share keys so that, in the future, they could just send each other a personally-locked box rather than have to use the three-pass method. By posting his own key instead of the empty box, Mallory would then be able to meddle in all future communication. In effect, Alice and Bob would each have unwitingly set up secure communcation with Mallory, who will be able to examine or alter the contents before relaying it to the intended recipient. Notice also that Mallory is able to achieve all this without ever having to break those unbreakable boxes or pick the unpickable locks.
The Woman in the Middle
However, resilience to man in the middle attacks is a tall order for a cryptosystem. The usual third party, Eve, is simply an eavesdropper; in terms of boxes, she may examine them all she likes, but not make physical alterations (such as Mallory's box-switching tricks). It's not immediately obvious, however, that a mathematical double-lock system will have even this property. This is because the locking procedures must commute- that is, Alice must be able to remove her lock whilst Bob's remains in place. The mathematical essence of a cryptographic process is that it's easy to perform in one direction (locking) but fiendishly difficult to perform in the other direction (unlocking), unless you have an extra piece of information (the key); many such systems will indeed commute. The danger with double-locking is that they commute too well, so that during the you-to-me, me-to-you exchange of encrypted data, Eve gains enough insights to reverse the procedure.
For instance, consider a system based on factorisation. Specifically, suppose that Alice chooses a large prime number M as the message to send to Bob, and picks another large prime x for encryption purposes. Sending M*x to Bob is safe; even if Eve gets her hands on it, it's difficult to retrieve the two prime pieces within a useful time. Bob can then pick a large prime 'lock' of his own, y, and send M*x*y back to Alice. Alice can then remove her lock by dividing through by x, leaving M*y to return to Bob. This is, in isolation, still difficult to retrieve M from - although Bob can do it by dividing through by y - yet during the exchange as a whole Eve has seen M*x, M*y and M*x*y so it's easy for her to variously extract x (Mxy/My) and then M (Mx/x), the message.
Fortunately, there is a commutative encryption system for which the double lock will be secure- or rather a class of such systems, namely those based on discrete logarithm problems, such as elliptic curve cryptography. This gives rise to Massey-Omura encryption.
Massey-Omura encryption
Let G be a
finite abelian group for which computing discrete logarithms is hard; m ∈ G an element encoding the message and N the
cardinality of G. Then Alice can send m to Bob securely as follows:
- Alice computes x, a random integer coprime to N, and sends the element a=mx to Bob (secure by difficulty of DLP).
- Bob computes y, a random integer coprime to N, and returns the element b=ay=mxy
- Alice knows x, so she can compute x-1 (mod N) and hence extract a'=bx-1=mxyx-1=my from b. This can be safely sent back to Bob since it still requires the solution of a DLP to retrieve m.
- Unless you're Bob, who knows y-1 and thus computes (a')y-1 = myy-1=m to read the message.
No combination of a,b or a' is any more helpful in determining m than considered alone, so this system is as secure as the discrete logarithm problem on G.
Thesedays, the double-lock algorithm is of greater historical than practical interest; most modern approaches revolve around public-private key pairs and Diffie-Hellman key exchange. This allows for encryption to manage identity as well as content, and also allows for one-shot computation and communication rather than the to and fro approach of the double-lock.
References
Blake, Seroussi, Smart: Elliptic Curves in Cryptography- LMS Lecture note series.
Savard: A Cryptographic Compendium.