The Elevator Problem

[Blake Wehlage]

At 02:50 AM 6/3/96 +0000, Deranged Mutant wrote:
>
>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 at unix.asb.com (root at magneto)
>        AB1F4831 1993/05/10 Deranged Mutant <wlkngowl at unix.asb.com>
>Send a message with the subject "send pgp-key" for a copy of my key.
>
>
Its a good thought, I never even thought about it, but it should work.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Blake "Pokey" Wehlage     Gaa- 3.69
<jwilk at iglou.com>         Record- 2-4-4
Age- 13                   Final Standings- 2nd Place (Beat in Championship)
President & Founder:                   
Revolution Software       "I have the fastest glove in the east!"
Profanity Software        "Hackers never stop hacking they just get caught"
VSoft

My life- Rarely eat or sleep, Hack til' 7:00a, goto school, play goalie
til' 5:00p, hack til' 7:00a
Hank Aaron- d:-)!-<   Pope- +<:-)   Santa Claus- *<:-) The Unabrower |:-)

Current Girlfriend(s)- Lindsey Wilcox, Laura Schubring
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~