The Elevator Problem
Deranged Mutant
WlkngOwl at unix.asb.com
Mon Jun 3 02:48:57 PDT 1996
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.
More information about the Testlist
mailing list