From: Hal <hfinney@shell.portal.com>
Date: Mon, 16 Oct 95 13:52:40 PDT
To: cypherpunks@toad.com
Subject: Human ID through insecure channel
Message-ID: <199510162051.NAA03429@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


Here is an example of the Matsumoto/Imai scheme for identifying yourself
via a shared secret over an insecure channel, a system which is simple
enough to be done in your head but which can withstand repeated
observations by an adversary without being broken.

The idea is that there is a challenge and response.  In one example they
give, the challenge is:

28517364

What happens here is that there are two secrets.  The first is which
characters are special in the challenge.  In this example let us assume
that is 1,2,4,6.  The second is a secret response string of the same
length; in this case let it be 3124.  Now what you do is to enter a
response string of the same length as the challenge.  Only the characters
in the same spot as those which held special characters in the challenge
(1,2,4,6) matter, and those four should spell out the secret word 3124.
So a correct challenge and response could be:

*  *  **
28517364
34312124

I have marked the spots in the challenge which use 1,2,4 or 6, and if you
look at the response in those marked spots you have 3124.

This is not too bad, but as more realistic examples the authors suggest
much larger strings.  In the first example the alphabet of characters
would be the lower case letters and the digits 0-9, 36 characters in all.
The challenge string would also be 36 characters long.  Your secret word
would be 18 letters, but the response alphabet is only the binary digits 0
and 1.

So, suppose the special characters are befhjkmnpqtvwz1468, and the secret
word is 011010111010110101.  The secret can be memorized in hex as 1aeb5.
This is not so much to remember, but try applying it in practice.  Here
is a challenge:

5fmp67yez2rnq4wd3uthsg1i8l09bkoavjxc

To create the response, we go across, putting down random 0's and 1's,
until we recognize our special characters.  The first is f, the 2nd
letter.  So we are careful to put down 0 there since that is the first of
our secret word letters.  Then the m is special, so we put down 1; the p
and 6 are special too, so we put down 10.  Then the 7 and y are not
special so we put random characters down there, and so on.  So our
initial response might be:

0011010...

Try coming up with the rest of the response, and see if you think you
could learn to do this by memory.

Another example the authors offer uses a somewhat shorter secret word and
set of special characters, but as a tradeoff the challenge alphabet is 50
characters (upper and lower case letters, say, minus 2 of them), and the
challenge is 50 characters long.  The secret word need be only 10
letters, and the response alphabet is 3 letters, say 0, 1 and 2.  So
suppose the special characters are bruzCEHMOQ, and the secret word is
2012100211.  Here is a challenge:

tJWTEjrkiqxsfmdAelvDIPguonKzFUHXwSaNVcpBQhGybRLMOC

Coming up with the response is left as an exercise for the reader.

Hal