Re: mental cryptography

[Hal <hfinney@shell.portal.com>]

The Mad Scientist in the Middle writes via anonymous-remailer@shell.portal.com:

>The answer is doing cryptography in your head.  Well not quite, since many 
>cryptographic operations are very computing intensive, and not everyone can do 
>1000 bit mental modular exponention in a reasonable amount of time.  But if 
>you have a piece of secure hardware that you can trust to do some of these 
>operations for you, then all you need is a secure communications channel to 
>this piece of hardware.  

>There may be other ways, but I suggest that you establish a common key with 
>your crypto server ahead of time, and then simply encrypt all your 
>communications using a symmetric algorithm.  RC4 may be a reasonable choice, 
>since the operations are simple and easy to remember, but you need to keep 
>track of a 255-byte state.  WAKE is probably better.  Although it uses a large 
>key table, you only have to memorize it once, after which the only state that 
>is changing is four 32-bit registers.

I am not familiar with WAKE but I doubt that you could literally hold 128
bits in your head and manipulate them.

This is a problem which I have wondered about for some time.  Presumably
if we went to a digital cash world we would use smart cards to buy
things, but how do we make sure that nobody steals and uses our smart
cards?  Just typing in a PIN doesn't seem very safe to me, especially if
the card doesn't have a keypad built in and you're using a keypad in the
card reader as is often the case today.  Even with a pad on the card you
have to worry about eavesdroppers.

Biometric ID's (fingerprints, and Senator Feinstein's retina scans that
she wants to put on our national ID cards) have been proposed to solve
this but they are expensive and unreliable right now.  An information
based solution would be best if it were possible.

I have read one paper which attempts to solve this problem, called "Human
Identification through Insecure Channel".  Unfortunately my papers are in
a mess right now so I don't have the reference handy.  It was by some
Japnese researchers, published in one of the proceedings books.  I
believe a follow-on paper was published within the last year or two which
had some improvements or corrections to their algorithm.  Sorry to be so
vague, I'll try to dig out more info over the weekend.

Basically they used a challenge-response system which was intended to
be simple enough that people could do it in their heads.  The card
would display a random challenge string, some characters of which were
special to the user and others which he would ignore.  He would then
input a response string, where it didn't matter what corresponded to
the "ignore" slots, but in the special slots he had to produce certain
symbols corresponding to the other symbols, with the rules changing as
you move along.  The intention was that even by capturing and analyzing a
great many challenge-response pairs you couldn't create a response to a
challenge you hadn't seen before.

I coded this up, and frankly, I couldn't do the required manipulations in
my head, at least not without taking a very, very long time, and thinking
very carefully.  Maybe it would get easier with practice, I don't know.
But my overall feeling was that this would be at the limits of human
capability even for fairly bright people.  (OTOH I suppose learning to
read and write might seem pretty tough if you'd never done it.  Maybe
the 1st grade classes of the future will spend months training the kids
on how to use these kinds of algorithms.)

>I am sure better algorithms can be found for this purpose if mental 
>cryptography is made explicit as a design goal.  Perhaps it should be?

It's a hard problem to solve in general because you have only a human
mind to do the identification algorithm but you have computers to try to
break it.  But I would like to see the problem get more attention.

Hal