mental cryptography

-----BEGIN PGP SIGNED MESSAGE-----

As we know, security is always relative to a threat model.  For example, most 
cryptographic protocols today will not protect their users against the cloning 
attack I described earlier, nor more mundanely, against video surveilence of 
your computing space.  What can you do if you ARE worried about such attacks?

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 sure better algorithms can be found for this purpose if mental 
cryptography is made explicit as a design goal.  Perhaps it should be?

 - the Mad Scientist in the Middle

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMH7l+9IjPOsOWLIJAQEwDwP7BB6ZlEoYVoOFYtzNDcF4XpCKs71GyASC
TiwCf+donWycN9SiJHApyXXbnuppGiEyAQYMBGkSLMyIwPMcE4v6CSt2DkpbPjkF
XauZy4rqDNljV2pk7PldbPOHDow9wOeoSF2S/luKAoHx5aJWVQrE5SKIgwY2xWfx
DYhjte2v9Jc=
=88be
-----END PGP SIGNATURE-----

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

hfinney@shell.portal.com writes:
 > 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.

The article, by T. Matsumoto and H. Imai, was in Eurocrypt '91, which
is published as vol. 547 of "Lecture notes in computer science".

The only followup article I could find was:
C.-H. Wang, T. Hwang, and J.-J. Tsai, "On the Matsumoto and Imai's
[sic] human identification scheme." (LNCS 921, 1995)

 > >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.

It may be that the approach is off anyway. Credit cards have only
signature verification -- if the salesperson bothers -- because stolen
cards are reported. You don't need a strong authentication technique
if a stolen card is easy to cancel.

Of course, perhaps this encourages someone to steal your card and
incapacitate you before you can report it. That's why we have
PINs... so that someone can steal your card, threaten you until you
reveal your PIN, and then incapacitate you... Hmm...

Even with a weak PIN system for authentication, you can always provide
a "duress" PIN, right?

nathan

-----BEGIN PGP SIGNED MESSAGE-----

 Nathan Loofbourrow <loofbour@cis.ohio-state.edu>
> 
> Of course, perhaps this encourages someone to steal your card and
> incapacitate you before you can report it. That's why we have
> PINs... so that someone can steal your card, threaten you until you
> reveal your PIN, and then incapacitate you... Hmm...
> 
> Even with a weak PIN system for authentication, you can always provide
> a "duress" PIN, right?


I can think of two purposes for "duress codes":  1.   To yield 
little loot to the thief, thus leaving more of it in your possession
and discouraging theft.  2.  To summon help in the form of physical
force.


The first use is susceptible to the "give me more or I cut off your
little finger" approach.  So we are again faced with the great
importance of a good police force.


Let us not forget about the value of such when constructing our future
visions.


Bryce
signatures follow


            "To strive, to seek, to find and not to yield."   
    <a href="http://ugrad-www.cs.colorado.edu/~wilcoxb/Niche.html">

                          bryce@colorado.edu                   </a>

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Auto-signed under Unix with 'BAP' Easy-PGP v1.01

iQCVAwUBMILxb/WZSllhfG25AQFiSwP/YgjCyQG/VfMKg8ervnnirEYxaqTdcTXW
AuDmDhVMrtP0J5kr1/7bZVDTY8wNrkptzBM9K8P9TFyhxEZnJZWEfW8PXR2Q28cC
nlUgF5PlWBqlPgnA6mZPbGQD8Fef+en4s1Rh1/9OxTxS3kFy1a3gMdkiR5iSKTVR
S9gGz3HBHNg=
=CmKt
-----END PGP SIGNATURE-----

Scott Brickner writes:
 > Nathan Loofbourrow writes:
 > >It may be that the approach is off anyway. Credit cards have only
 > >signature verification -- if the salesperson bothers -- because stolen
 > >cards are reported. You don't need a strong authentication technique
 > >if a stolen card is easy to cancel.
 > 
 > The card's easy to cancel, but the cash ain't.  Credit cards are
 > cleared with the issuer.  Digital cash with smart cards acting as
 > transaction observers don't need this.  The thief need only transfer
 > the cash from the stolen card to his own, just like he does with
 > regular cash.

Er, um, right.

Well, then, perhaps on-line systems need to consider cash
revocation in case of theft. Actually, this is a no-brainer: just
exchange the cash for some new coin, and the old stuff goes
invalid. Admittedly, this means a footrace for the mugger and the
victim, so I guess the mugger is encouraged to knock you out cold.

Maybe you just shouldn't carry too much cash with you. Gee, that
sounds like good advice even without digital protocols.

 > >Even with a weak PIN system for authentication, you can always provide
 > >a "duress" PIN, right?
 > 
 > Sounds like a better choice.

Duress PINs liberally sprinkled through the keyspace also drop the
efficacy of brute-force PIN search for the thief.

nathan

On Tue, 17 Oct 1995, Nathan Loofbourrow wrote:

> Well, then, perhaps on-line systems need to consider cash
> revocation in case of theft. Actually, this is a no-brainer: just
> exchange the cash for some new coin, and the old stuff goes
> invalid. Admittedly, this means a footrace for the mugger and the
> victim, so I guess the mugger is encouraged to knock you out cold.
 (snip)
> Duress PINs liberally sprinkled through the keyspace also drop the
> efficacy of brute-force PIN search for the thief.
> 
Besides (if you *really* want to be paranoid) you'd still have still have 
that cash on your hard drive and several other smart cards. Assuming you 
record which cash you put onto which smartcard onto your database or 
whatever, you'd exchange the stolen cash with the bank before brute force 
would succeed. Mugger still gets stuck with a duress code.

Either you have an automated paranoia setup that constantly changes 
your net worth into new currency (rejuvenating your cash against aging 
by factoring) or yeah, it really is better for the mugger to get rid of you. 
This also protects against the chinese lottery attacks some people on the 
list are trying to set up (assuming it really is ubiquitous by then).
It really might become a lottery with ecas. Factor PINs (assuming they're
small enough) and make real money.

This could easily be part of an automated trading program of the kind 
used by stock brokers. You'd probably use it anyway if the currency market 
were totally digital (low, if not no transaction fees) to compensate for 
currency fluctuations. Private currencies might be very volatile. Hell, if any 
of this succeeds, government currencies would be extremely volatile. 

Gold might start looking good again. (though platinum's better, almost all 
the world's platinum's in South Africa and odds are no one's gonna find any new
sources. Anyone know if I'm totally wrong? I'm no economist.)

(waiting to see if ala.usmc.mil is going to send more bouncemail)

On Tue, 17 Oct 1995, Nathan Loofbourrow wrote:

> Duress PINs liberally sprinkled through the keyspace also drop the
> efficacy of brute-force PIN search for the thief.
Was there an actual protocol for doing this? (probabilistic maybe?)
Don't remember Schneier doing anything beyond just mentionning it. (ok I 
can't find the page number either, so I can't really complain).

Nathan Loofbourrow writes:
 > C.-H. Wang, T. Hwang, and J.-J. Tsai, "On the Matsumoto and Imai's
 > [sic] human identification scheme." (LNCS 921, 1995)

Uh, silly me, that happens to be the EUROCRYPT '95 proceedings.

Boy, and isn't it fun to receive all the bounce messages from every
post to cypherpunks?

nathan

On Sat, 14 Oct 1995, Nathan Loofbourrow wrote:

> Nathan Loofbourrow writes:

> Boy, and isn't it fun to receive all the bounce messages from every
> post to cypherpunks?
Ok, who wants to sic a PI on this Jason P. Jones tentacle or call his local
morgue to see if he's alive enough to delete his mailbox?

A testament to too many high-volume mailing lists.