From: "Deranged Mutant" <WlkngOwl@unix.asb.com>
Date: Mon, 3 Jun 1996 17:48:57 +0800
To: cypherpunks@toad.com
Subject: The Elevator Problem
Message-ID: <199606030719.DAA26321@unix.asb.com>
MIME-Version: 1.0
Content-Type: text/plain



This may be old hat, but an earlier post (around the time the Kocher 
RSA-timing attack came out) to the list asked about the "Elevator 
Problem", where two parties who think they share the same secret want 
to confirm it on an open channel.  I came up with an idea for a 
protocol but never got around to posting it, and dropped off the list 
briefly... so pardon me if this is already touched upon.

Alice and Bob are in a crowded place and want to confirm they share a 
secret.

Each picks a couple of random numbers, b and i.  The secret P is 
hashed i times, something like:

  H_0(P) = H(P,0)               [H can be something like SHA-1...]
  H_i(P) = H(H_i-1(P), i)

They then tell each other bit b of H_i(P).

This is repeated a number of times to make random guessing very 
unlikely.

If all bits match, they agree that they share the secret (we assume 
neither wants to lie but discover if the other knows the secret).

Since this is a mutual protocol, an eavesdropper who listens in 
shouldn't be able to spoof Alice or Bob.  Or maybe Alice and Bob can 
agree never to reuse combinations of b and i anyway (or they can 
append a counter to the secret, so that combinations of b and i never 
give the same values).

Could be useful for implementing as a remote login?


Comments?



Rob.

---
No-frills sig.
Befriend my mail filter by sending a message with the subject "send help"
Key-ID: 5D3F2E99 1996/04/22 wlkngowl@unix.asb.com (root@magneto)
        AB1F4831 1993/05/10 Deranged Mutant <wlkngowl@unix.asb.com>
Send a message with the subject "send pgp-key" for a copy of my key.