«

(Just working out something for myself here, feel free to follow along.)

Consider the problem of passing something secret between two people who
have never physically met, and cannot physically meet. Call them Alice
and Bob. Say Alice has left some secret documents in a locker somewhere,
and she needs to get the key to Bob. All they've got is each other's
address. However, the postal service is liable to open and inspect
everything sent through the mail if they can physically do so. Alice
can't send the key in a locked box, because then she then has to send
the key to the box to Bob somehow (if Bob can break into the box, then
so can the post office). And she can't hide the key somewhere and send
Bob a letter explaining where to find it, because a spy at the post
office can read the letter too. So how does Alice get the key to Bob?

Surprisingly enough, it can be done.

Alice starts by putting the locker key in a strong box with a latch on
it, and puts a padlock (to which she has the key) on the latch. She
keeps the padlock key in a safe place and sends the locked box to Bob.

Bob doesn't have the key to the padlock, so he can't open the box.
Instead, he adds _another_ padlock (to which he has the key) to the
latch, beside the one that Alice put on, and sends the box back to Alice.

Alice unlocks and removes her padlock. The box is now only secured by
the padlock belonging to Bob. So she posts the box back to Bob.

Bob now has a box which is locked by a padlock to which he has the key.
He opens the box, and voilà--he now has the locker key. And no-one else
at any stage in-between was able to open the box.

There is a similar problem in cryptography. Alice and Bob want to
exchange secret messages, but before they can do that they have to agree
on a secret key for encrypting and decrypting the messages. How can they
do this, if they don't already have a secure channel of communication
between them?

In fact, there is a well-known solution to this, called Diffie-Hellman
key exchange. But I'm not interested in that here, because it works in a
completely different way to the double-padlock protocol used for
transferring the physical key in the example above. So is there a
cryptographic key-exchange protocol that works like the double-padlock
system?

It appears there is, kind of. It's called the Shamir Three-Part
Protocol. First let's define some notation.

Secret-key encryption, in general, is a function E that takes a string
of "plain text" P and turns it into "ciphertext" C according to a key K:

C = E(K, P)

Decryption with the same key reverses the process:

P = D(K, C)

And if you do not have K, even if you know the algorithm, then
possession of the string C does not allow you to (easily) recover P.

The Shamir Three-Part Protocol requires an encryption algorithm that is
_commutative_. That is, multiple encryption/decryption steps with
different keys K1 and K2 can be reordered without affecting the result:

E(K2, (E(K1, P)) = E(K1, E(K2, P))

Note that not every encryption algorithm satisfies this property. But if
you can find one that does, Alice can pass a secret S to Bob thus:

First, Alice chooses (and remembers) a random key KA and encrypts S with
this. She then sends the encrypted string

E(KA, S)

to Bob.

Bob in turn makes up (and remembers) a random key KB, encrypts the
string he received from Alice and sends the result

E(KB, E(KA, S))

back to Alice.

Alice decrypts the result with her previously-generated key KA, giving

D(KA, E(KB, E(KA, S))) = D(KA, E(KA, E(KB, S))) = E(KB, S)

which she sends back to Bob.

Bob now just has to decrypt the result with his previously-generated key
KB, to produce

D(KB, E(KB, S)) = S

And so Bob now has the secret, but (hopefully) no eavesdropper in the
middle has enough information to figure it out. You can see the analogy
between the two encryption steps and the two padlocks, and how the keys
to these are never exchanged or divulged.

One obvious family of encryption algorithms that does satisfy the
required commutativity property for this to work is called stream
encryption. Stream encryption algorithms work by using the encryption
key to produce a pseudorandom stream of bits which is XORed with the
message. (Another name for this family of algorithms is
"pseudo-one-time-pad".) Besides the commutativity of multiple encryption
steps, another interesting property is that the decryption algorithm is
exactly the same as encryption: encrypt the plaintext twice with the
same key, and you get the plaintext back again.

Unfortunately, this symmetry property is the reason why stream
encryption algorithms cannot be used with the Shamir Three-Step
Protocol. To see why, consider the exchange of encrypted data strings
above--remember that everything passed between Alice and Bob could
potentially be copied by an eavesdropper. That means the eavesdropper
has to be assumed to have copies of the following data strings which
were exchanged:

E(KA, S)
E(KB, E(KA, S))
E(KB, S)

If we represent the pseudorandom bit string generated from the key KA as
R(KA) and the one generated from KB as R(KB), and use "^" to denote XOR,
then for the particular case of stream encryption, these become

E(KA, S) = R(KA) ^ S
E(KB, E(KA, S)) = R(KB) ^ R(KA) ^ S
E(KB, S) = R(KB) ^ S

(XOR itself is a commutative and associative operation.) If we XOR the
first and third packets together, we get

E(KA, S) ^ E(KB, S) = R(KA) ^ S ^ R(KB) ^ S
= R(KA) ^ R(KB) ^ S ^ S
= R(KA) ^ R(KB) ^ 0
= R(KA) ^ R(KB)

where "0" denotes a string of zero bits the same length as S. Now, what
happens when we XOR this result with the second string? We get

R(KA) ^ R(KB) ^ E(KB, E(KA, S))
= R(KA) ^ R(KB) ^ R(KB) ^ R(KA) ^ S
= R(KA) ^ R(KA) ^ R(KB) ^ R(KB) ^ S
= 0 ^ 0 ^ S
= S

which means the eavesdropper can easily recover the secret S without any
knowledge of KA or KB! Which is a somewhat fatal flaw in the scheme.

So the question is, is there a suitable encryption algorithm that
renders the Shamir Three-Step Protocol workable?

On Mon, 02 Feb 2004 20:25:32 +1300, Lawrence D¹Oliveiro
<_zealand> wrote:

>Alice starts by putting the locker key in a strong box with a latch on
>it, and puts a padlock (to which she has the key) on the latch. She
>keeps the padlock key in a safe place and sends the locked box to Bob.
>
>Bob doesn't have the key to the padlock, so he can't open the box.
>Instead, he adds _another_ padlock (to which he has the key) to the
>latch, beside the one that Alice put on, and sends the box back to Alice.
>
>Alice unlocks and removes her padlock. The box is now only secured by
>the padlock belonging to Bob. So she posts the box back to Bob.

Why didn't Alice just send the box to Bob with the padlock, then once
Bob confirmed he had the box send the key to him.

It would be no less secure, as there is no real way that Alice can
know that someone else didn't intertcept the box and put their lock on
it and send it back to her.

On Mon, 02 Feb 2004 20:25:32 +1300, Lawrence D¹Oliveiro wrote:

> So the question is, is there a suitable encryption algorithm that
> renders the Shamir Three-Step Protocol workable?

I've struggled with similar myself, and have come to the conclusion that
the only way to avoid MITM (Man-In-The-Middle) attacks is to make recourse
to some 'out of band' communication.

Also that, logically, the quest for an MITM-proof self-contained key
exchange and authentication protocol is almost identical to the quest for
a perpetual-motion machine - unless the machine uses an external energy
source, it's screwed.

My opinion is that no symmetric cipher will defeat against MITM attack,
not even with Shamir.

For instance, with your post office and padlock scenario, there's nothing
to stop a postal worker from grabbing the package, and sticking a post
office padlock on the box and sending it back to Alice. Alice takes off
her padlock and posts the box back to Bob. The postal worker gets the box,
takes off the post office padlock, and gets the key. Then, the postal
worker sends a fake box to Bob containing a post office key and does the
same protocol. In which case, Bob ends up with the post office key, the
postal worker ends up with Alice's key, and can intercept (and modify) all
communication.

In this scenario, the only way out is for Alice to use a brand of padlock
that is monogrammed with her signature, in a way that the postal worker
can't copy. If Bob receives a box that doesn't have this brand of padlock,
with Alice's signature on it, he knows not to trust it. (Or, he knows to
mistrust it, and might pretend to have fallen for it, which might give him
an advantage, ditto for Alice).

Perhaps the most common form of oob communication is to use a
certifying authority (CA) - someone whom Alice and Bob both trust.
As we all know, the CA takes steps to verify Alice and Bob's identity, and
can furnish the electronic equivalent of such rare-brand, monogrammed
padlocks.

In which case, Bob would send the box to his friend Trent, and get back an
unforgeable signal from Trent that the padlock is indeed Alice's.

But there's another way to protect against MITM as well, that I've
seen being used on the Freenet network.

Suppose there is a communication medium over which Alice has complete
control, and ditto for Bob.

For instance, Alice is a sales rep for billboard advertising, and Bob is a
sound recording engineer for a band.

Alice puts up nationwide billboards for a real estate company, and on the
picture of the houses, under the window, there is a small number. After
sending the box to Bob, the number on the billboards is the serial number
of the padlock on the box she has sent.

Ditto for Bob. If he matches up the padlock serial number with the number
on the billboards, he trusts the padlock, and sticks his own padlock on
the box and sends it. Then when he does the mix for the band's latest
single, he manipulates some drum beats and bar counts to spell out a
number, but without undesirable artistic impact. Alice hears the song on
the radio, counts the bars and decodes the number from the
snare/hh/kick/cym beats. She compares this number to the serial number on
the padlock, and decides to trust Bob's padlock.

This method works within Freenet, because that network avoids
human-readable addresses (such as www.somedomain.com), and opts for
gobbledegook addresses (such as SSK@weriuy2438fhfjhweuyw38742fhs), which
are based on hashed content or signatures. It is very difficult for an
attacker to substitute his/her own content at a given address.

This is similar to the CA solution in one respect - the existence of
out-of-band communication which cannot be tampered with by an attacker.

Get some kind of untamperable OOB communication, and you're home free.
Without it, you're a sitting duck.

All this being said, I'm open to being proven wrong (and would actually
love to be - it would make my life easier).

Cheers
EB

Evil Bastard wrote:
Then when he does the mix for the
> band's latest single, he manipulates some drum beats and bar counts
> to spell out a number, but without undesirable artistic impact. Alice
> hears the song on the radio, counts the bars and decodes the number
> from the snare/hh/kick/cym beats.

Thats where it all turns to custard.
grief grief grief
You don't know how much grief
"Are you guys happy with that then ?"
"Can we do the drums again ?"
"Aaaaaaaaaarrrrrrrrghhhhhhhh !!!!!!"

On Tue, 03 Feb 2004 13:50:25 +1300, harry wrote:

> Evil Bastard wrote:
> Then when he does the mix for the
>> band's latest single, he manipulates some drum beats and bar counts
>> to spell out a number, but without undesirable artistic impact. Alice
>> hears the song on the radio, counts the bars and decodes the number
>> from the snare/hh/kick/cym beats.
>
> Thats where it all turns to custard.
> grief grief grief
> You don't know how much grief
> "Are you guys happy with that then ?"
> "Can we do the drums again ?"
> "Aaaaaaaaaarrrrrrrrghhhhhhhh !!!!!!"

Totally missing the point, but thanks for a good laugh of the day!

In article <>,
Craig Shore <> wrote:

>Why didn't Alice just send the box to Bob with the padlock, then once
>Bob confirmed he had the box send the key to him.
>
>It would be no less secure, as there is no real way that Alice can
>know that someone else didn't intertcept the box and put their lock on
>it and send it back to her.

Good point. However the drawback with this is that you can only use a
padlock and its key once, then you have to throw it away. With the
double-padlock system, you can keep reusing the same padlocks.

In article <pan.2004.02.03.00.18.46.859898@127.0.0.1>,
Evil Bastard <postmaster@127.0.0.1> wrote:

>Also that, logically, the quest for an MITM-proof self-contained key
>exchange and authentication protocol is almost identical to the quest for
>a perpetual-motion machine - unless the machine uses an external energy
>source, it's screwed.
>
>My opinion is that no symmetric cipher will defeat against MITM attack,
>not even with Shamir.

Absolutely true. Without any kind of authentication of the identity of
whom you're communicating with, the whole key exchange idea is a waste
of time. This is a criticism of Diffie-Hellman key exchange, too.