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.
participants (5)
-
anonymous-remailer@shell.portal.com -
Bryce -
Hal -
Nathan Loofbourrow -
s1018954@aix2.uottawa.ca