Anonymous key exchange

Discussion in 'NZ Computing' started by Lawrence D¹Oliveiro, Feb 2, 2004.

  1. (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?
     
    Lawrence D¹Oliveiro, Feb 2, 2004
    #1
    1. Advertising

  2. Lawrence D¹Oliveiro

    Craig Shore Guest

    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.
     
    Craig Shore, Feb 2, 2004
    #2
    1. Advertising

  3. Lawrence D¹Oliveiro

    Evil Bastard Guest

    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, Feb 3, 2004
    #3
  4. Lawrence D¹Oliveiro

    harry Guest

    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 !!!!!!"
     
    harry, Feb 3, 2004
    #4
  5. Lawrence D¹Oliveiro

    Evil Bastard Guest

    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!
     
    Evil Bastard, Feb 3, 2004
    #5
  6. 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.
     
    Lawrence D¹Oliveiro, Feb 3, 2004
    #6
  7. 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.
     
    Lawrence D¹Oliveiro, Feb 3, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jose Luis

    Exchange 5.5 with Exchange 2000 Cluster problem

    Jose Luis, Feb 13, 2004, in forum: Microsoft Certification
    Replies:
    0
    Views:
    731
    Jose Luis
    Feb 13, 2004
  2. winman
    Replies:
    9
    Views:
    693
    Consultant
    Jul 30, 2003
  3. =?Utf-8?B?am9zdWU=?=
    Replies:
    3
    Views:
    1,009
    =?Utf-8?B?U2xpY2tERFNB?=
    Aug 15, 2007
  4. Juan
    Replies:
    3
    Views:
    2,151
  5. Fraser Scott

    Exchange 2007 or Exchange 2010???

    Fraser Scott, Jul 21, 2009, in forum: Microsoft Certification
    Replies:
    0
    Views:
    1,489
    Fraser Scott
    Jul 21, 2009
Loading...

Share This Page