From: hfinney@shell.portal.com (Hal Finney)
Date: Thu, 18 Nov 93 08:56:30 PST
To: wex@media.mit.edu
Subject: Re:  hohocon
Message-ID: <9311181655.AA08484@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


Regarding the issue of telnet'ing through an insecure system:

A general solution to this problem is to have the system you are attaching
to engage in some dialog with you to establish your identity.  However, the
dialog must be such that even if it is monitored by the system you are
going through, that will not allow them to later claim to be you.

This is the same basic problem as entering a PIN for a credit or debit
card in an environment where the PIN can be seen or recorded.  If someone
sees your PIN they can steal your ATM card (or dcash card, in the future)
and access your money.

Cryptographic solutions involve zero-knowledge proof systems but they are
too complicated to work in your head.  For the hohocon case you could have
a calculator programmed with some one-way function (DES is available for
the HP48); the remote system could generate a challenge number and you
would use your calculator to DES-encrypt it with a fixed secret key, then
type the result in, and the remote system would check it.  This would
not help the hohocon people because next time they tried to log in as
you the challenge number would be different.

There was a paper in the Eurocrypt 91 proceedings called "Human Identification
Through Insecure Channel" which attempted to address this problem.  The
authors proposed a system which was supposed to be simple enough that you
could work the response in your head, but which would be complex enough
that eavesdroppers would not be able to figure it out, even after seeing
many examples.

The idea was that the remote system would issue a challenge as a string
of letters or digits: 1982043765.  You will give a response of the same
length, but only certain positions matter.  Those positions are identified
by one of two secret words that you memorize.  Suppose the first secret
is 1246.  You will produce a response which embeds the 2nd secret word
in the positions where 1,2,4, and 6 appear.  Suppose the 2nd secret word
is 3124.  Your response, written below the challenge, would be:

1982043765
3421223142
-  - -  -

Only the marked positions matter; the others are random.

This sounds simple enough, but the problem is that for true security
the authors require a much longer string with a much larger set of
characters, 40 or 50 characters long.  I tried implementing their
algorithm, without even memorizing the secrets, just writing them down
(they had to be about 10 letters long), and entering in a reponse given
a challenge, and I couldn't do it.  It was extremely difficult to locate
the checked positions and put in the next letter.  It took forever to
do it, and I kept making mistakes.

Maybe with practice it would get easier.  Or, perhaps the technique would
still be useful with a smaller question size to provide less security but
still more than you would get without it.

It would be interesting to see if other people come up with approaches
to solve this problem.  I really don't think that protecting my smart
card with a 6-digit PIN is going to be adequate.

Hal Finney
hfinney@shell.portal.com