December 2003 - cypherpunks-legacy

MATH: Zero Knowledge Proofs
by tcmay＠netcom.com 17 Dec '03

17 Dec '03

[Here is the article on zero knowledge I promised. It was posted to the Cypherpunks list a year ago, on 7 April 1993. There's a great explanation of ZKIPS in terms of "Ali Baba's Cave" that appeared in one of the Crypto Proceedings; I may try to find it and then scan it in. Also, the paper Derek Upham mentioned earlier today was co-authored by Bennett Yee, and I have seen his explanation of ZKIPS posted at least a few times to sci.crypt. Be that as it may, here is _my_ explanation, from a year ago.] Ray Cromwell writes: > Could someone explain zero knowledge proofs and give me an example. I >have taken number theory and abstract algebra so feel free to use equations. > >(I know that zero knowledge proofs are a way of certifying something without >revealing the information you are certifying, but I want to know how they >work mathematically) Zero knowledge interactive proof systems ("ZKIPS") are sometimes called "minimum disclosure proofs" (with some subtle differences) and are exciting and mysterious (at first) methods that lie at the heart of modern cryptology. Here's a simple explanation. Too bad we don't have a blackboard! ALICE AND BOB (some people call them Peggy the Prover and Vic the Verifier) Alice wishes to prove to Bob that she knows some item of knowledge without actually giving Bob any of that knowledge. Let us first imagine that Alice claims she knows a "Hamiltonian cycle" on a particular graph. (For a given set of nodes and arcs linking some of those nodes, a Hamiltonian cycle is one which passes through each node once and only once. You might want to draw some graphs on a sheet of paper and try to find a Hamiltonian cycle for the graphs, to get a feel for the problem.) The particular graph may be "registered" somewhere with Alice's claim that she--and only she, for reasons I'll discuss at the end--knows a Hamiltonian cycle for the graph. In a sense, this is her "proof of identity." To make this example concrete, Alice is using this piece of knowledge as her *password* to get into some system. She presents a map of 50 cities and some set of highways interconnecting them and says "I am who I say I am if and only if I know a Hamiltonian cycle for this graph." The conventional (non zero knowledge) way to convey this knowledge is for Alice to simply *show* the Hamiltonian cycle to Bob. This is how passwords are currently handled. Bob, and anybody else who is spying on the exchange, then knows the "secret," which isn't a secret anymore. (Anybody who saw the exchange, including Sysadmin Bob, could then impersonate her.) ENTER ZERO KNOWLEDGE Alice, instead of showing Bob the Hamiltonian cycle, takes the cities and covers them with something, say, coins. (On a computer, this is all done in software, using the cryptographic protocol called "bit commitment.") Alice scrambles the position of the cities (covered by coins) so as not to allow positional cues. (Most of the 50 cities should have about the same number, ideally exactly the same number, of links to other cities, to ensure that some cities are not "marked" by having some unique number of links. A detail.) Needless to say, she scrambles the cities out of sight of Bob, so he can't figure out which cities are which. However, once she's done with the scrambling, she displays the cities in such a way that she can't *later change*..i.e., she "commits" to the values, using well-known cryptographic methods for this. (If this sounds mysterious, read up on it. It's how "mental poker" and other crypto protocols are handled.) Bob sees 50 cities with links to other cities, but he doesn't have any way of knowing which of the covered cities are which. Nor, I should add, are the links labelled in any way--it wouldn't do to have some links permanently labelled "Route 66" or "Highway 101"! She says to Bob: "Pick one choice. Either you can see a Hamiltonian cycle for this set of covered cities and links, or you can see the cities uncovered." In other words, "Alice cuts, Bob chooses." Bob tosses a coin or chooses randomly somehow and says: "Show me the cities." Alice uncovers all the cities and Bob examines the graph. He sees that Akron is indeed connected to Boise, to Chicago, to Denver, not to Erie, and so on. In short, he confirms that Alice has shown him the original graph. No substitution of another graph was made. Bob, who is suspicious that this person is really who she claims to be, says to Alice: "Ok, big deal! So you anticipated I was going to ask you to show me the cities. Anybody could have gotten Alice's publicly registered graph and just shown it to me. You had a 50-50 chance of guessing which choice I'd make." Alice smugly says to him: "Fine, let's do it again." She scrambles the cities (which are covered) and displays the graph to Bob...50 covered cities and various links between them. She tells Bob to choose again. This time Bob says: "Show me the Hamiltonian cycle." Without uncovering the cities (which would give the secret away, of course), Alice connects the cities together in a legal Hamiltonian cycle. Bob says, "OK, so this time you figured I was going to ask you the opposite of what I did last time and you just substituted some other graph that you happened to know the Hamiltonian cycle of. I have no guarantee the graphs are really the same." Alice, who knows this is just the beginning, says: "Let's do the next round." ...and so it goes.... After 30 rounds, Alice has either produced a legal Hamiltonian cycle or a graph that is the same as (isomorphic to...same cities linked to same other cities) the registered graph in each and every one of the rounds. There are two possibilities: 1. She's an imposter and has guessed correctly *each time* which choice Bob will make, thus allowing her to substitute either another graph altogether (for when Bob wants to see the Hamiltonian cycle) or just the original graph (for when Bob asks to see the cities uncovered to confirm it's the real graph). Remember, if Alice guesses wrong even once, she's caught red-handed. 2. She really is who she claims to be and she really does know a Hamiltonian cycle of the specified graph. The odds of #1 being true drop rapidly as the number of rounds are increased, and after 30 rounds, are only 1 in 2^30, or 1 in a billion. Bob choose to believe that Alice knows the solution. Alice has conveyed to Bob proof that she is in possession of some knowledge without actually revealing any knowledge at all! The proof is "probabilistic." This is the essence of a zero knowledge proof. There's more to it than just this example, of course, but this is the basic idea. SOME DETAILS 1. Could someone else discover the Hamiltonian cycle of Alice's graph? Exhaustive search is the only way to guarantee a solution will be found--the Hamiltonian cycle problem is a famous "NP-complete" combinatorial problem. This is intractable for reasonable numbers of nodes. 50 nodes is intractable. 2. If finding a Hamiltonian cycle is intractable, how the hell did Alice ever find one? She didn't *have* to find one! She started with 50 cities, quickly connected them so that the path went through each city only once and then wrote this path down as her "secret" solution. Then she went back and added the other randomly chosen interconnects to make the complete graph. For this graph, she obviously knows a Hamiltonian cycle, *by construction*. 3. Can Bob reconstruct what the Hamilonian cycle must be by asking for enough rounds to be done? Not generally. Read the papers for details on this, which gets deeply into under what circumstance partial knowledge of the solution gives away the complete solution. 4. Are there other problems that can be used in this same way? Yes, there are many forms. I find the Hamiltonian cycle explanation quite easy to explain to people. (Though usually I can draw pictures, which helps a lot.) 5. How general is the "zero knowledge interactive proof" approach? Anything provable in formal logic is provable in zero knowledge, saith the mathematicians and crypto gurus. Check out the various "Crypto Conference" Proceedings. Hope this helps. -Tim May .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."

1 0

Code review is requested.
by anonymous＠extropia.wimsey.com 17 Dec '03

17 Dec '03

Cypherpunks review code! I have written a hack to allow pgp's random.h and random.c to be used with a hardware random number generator. I have mailed this to a number of U.S. cypherpunks with the request that the hack be distributed widely in the U.S. jim.wenzel(a)grapevine.lrk.ar.us (Jim Wenzel) has chosen to post this hack on alt.security.pgp and it is consequently widely available. The post was titled "Questionable PGP Patch 01". jim.wenzel(a)grapevine.lrk.ar.us (Jim Wenzel) has suggested the possibility that my hack may contain a deliberate bug. I Quote: > >Below is a message that I received concerning a patch for PGP. As the >author did not sign the message and it is from an unknown origin I do >not recommend performing the patch. I post it here primarily so those >of interest can let those of us who are 'technoligically challenged' >know if it is legit or is someone trying to install a 'bug' into PGP. I >have omitted posting the header information in hopes that the original >author will post me. > >********************************************************************* >Forwarded message follows... >*** I DO NOT VOUCH FOR THIS PATCH >*** I DO NOT KNOW WHO THIS PATCH IS FROM >*** (it was sent via an anonymous remailer) >*** I DO NOT SUGGEST USING THIS PATCH >*** <other standard disclaimers as they may be needed> >********************************************************************* > I would like to note that this hack can only be used by those that actually have a hardware RNG. But the code is "IFDEF"ed so that it does not actually enable RNG support unless it is requested to do so by "DEFINE"s. I would like to assure everyone that I did not place any deliberate bugs in my hack. However, jim.wenzel(a)grapevine.lrk.ar.us (Jim Wenzel)'s point is well taken. I may sure that I did not place any deliberate bugs in the hack, but you can not be without careful code review. Also, there is the possibility of bugs caused by programmer error. To address these problems, I would like to request that code oriented Cypherpunks perform a code review of the hack. I have only tested the hack under OS/2 and the MS-DOS program loader. I have already noted the following possibilities for improvement: 1) The versions of the hack that use an operating system IO driver (RANDDRIVER) test that the driver was successfully opened. However if the hack is compiled to directly access a bus hardware RNG thru its IO port (HARDRANDOM) the hack does not do any test to assure that the RNG is actually there. I believe that if you attempt to read a port that is not supported by hardware you always get -1, which is not very random. Thus there is the problem that some one could attempt to use a version of pgp that was originally compiled for a machine with a RNG on a machine without a RNG. If they did this they could inadvertently created very breakable ciphers! Perhaps some enterprising cypherpunk could add code to do minimal randomness checks on the RNG when it is first used, to test that the RNG is actually there. 2) Stichting FREMM Alexanderkade 1 1018 CH Amsterdam The Netherlands sells a RNG that attaches directly to a serial port. Perhaps such a RNG could be used in connection with my hack using the (RANDDRIVER) option and the operating system's interface to the serial port. However I have provided no options for setting the baudrate, flow control options and other parameters that should be set when opening a connection to a serial port. I do not know the proper values for these parameters and I do not have a device to test with. Perhaps some cypherpunk will volunteer to write such code. It should be "IFDEF"ed. Also FOSSIL support for the PC world springs to mind. Such code is always highly operating system dependent. Different code could be written for each operating system supported by PGP for a hardware RNG connected to a serial port. 3) There may be other RNG's in existence which are accessed in a different way, or have different IO drivers. If you have knowledge of such RNG's please post the info to the cypherpunks mailing list. In summary, I would like to request that code oriented cypherpunks do a code review of my hack to support hardware RNG's using random.h and random.c. Results may be posted on the cypherpunks mailing list. Since the hack has been posted to alt.security.pgp, the hack is available globally. Someone outside the U.S. should uudecode the hack and place it on some FTP site somewhere where it can be publicly available. After the code has been reviewed and corrected if necessary, it could be included in the next source code release of PGP. Yours in anonymity XXX

1 0

RE: Code review is requested.
by Pat Farrell 17 Dec '03

17 Dec '03

anonymous(a)extropia.wimsey.com writes: > 3) There may be other RNG's in existence which are accessed in a > different way, or have different IO drivers. If you have knowledge of > such RNG's please post the info to the cypherpunks mailing list. In Cryptosystems Journal, published by Tony S Patti, Volume 2 Number 2 is a description, circuit board layouts, parts list, etc. for Ranger hardware RNG. It produced 6,750 bits per second into the parallel port of a standard PC. The author says that you can build a Ranger for less than $40 worth of parts. Cryptosystyems Journal P.O. Box 188 Newtown PA 18940-0188 I have not seen any reviews of this device, but it has been arround for a while, and may have been covered before I got interested in the field. Pat Pat Farrell Grad Student pfarrell(a)gmu.edu Department of Computer Science George Mason University, Fairfax, VA Public key availble via finger #include <standard.disclaimer>

1 0

Why the second copy of "Zero Knowledge" was sent
by tcmay＠netcom.com 17 Dec '03

17 Dec '03

The second copy of the "Zero Knowledge" article got posted because I used an off-line mailer (my old post being buried in my Eudora mailer archives which I had to search) and uploaded the article when I downloaded my mail, thus missing Matt Thomlinson's earlier posting of my article. Normally I read mail with "elm," for promptness and because I'm online reading News anyway. --Tim -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."

1 0

Zero Knowledge Authentication and StrongBox
by rjc＠gnu.ai.mit.edu 17 Dec '03

17 Dec '03

Derek Upham says: Look at "Strongbox: A System for Self-Securing Programs" by J. D. Tygar and B. S. Yee in the "CMU Computer Science 25th Anniversary Commemorative" proceedings (from 1991). As the paper describes: ``Strongbox uses an authentication protocol derived from Rabin's observation about the square root operation: if one can extract square roots modulo n where n=p*q , p and q primes, then one can factor n . [That should be `if and only if', i.e., finding the square roots is too hard unless you created n in the first place.] Donald Knuth sez in Seminumerical Algorithms p389: "However, the system [SQRT Box] has a fatal flaw. Anyone with access to a SQRT box can easily determine the factors of its N. This not only permits cheating by dishonest employees, or threats of extortion, it also allows people to reveal their p and q, after which they might claim that their "signature" on some transmitted document was a forgery." I don't really get Knuth's comment since the "secret key" (p and q) can be stored in the SQRT Box with a passkey just like PGP stores encrypted secret keys, unless of course Knuth means "given a SQRT box, by feeding it lots of numbers and getting the resulting SQRT, one can determine the factorization of its internal modulus." On the preceding page, Knuth describes RSA and RSA signatures but he doesn't make the same comment that "people could give our their p and q and claim signatures were forged." I usually trust Knuth, so is he wrong, or does he just have something against sqrt(x) mod N cryptosystems? -Ray -- Ray Cromwell | Engineering is the implementation of science; -- -- rjc(a)gnu.ai.mit.edu | politics is the implementation of faith. --

2 1

Fast Personal Recognition
by Ed Switalski 17 Dec '03

17 Dec '03

Attention all Citizen-Units !! Look straight into Big Brother eyes. ------- Forwarded Message University of Cambridge Computer Laboratory SECURITY SEMINAR SPEAKER: John Daugman University of Cambridge DATE: Wednesday 20th April 1994 at 4.15pm PLACE: Babbage Lecture Theatre, New Museums Site TITLE: VISUAL RECOGNITION OF PERSONS BY FAILURE OF STATISTICAL INDEPENDENCE Samples from stochastic signals with sufficient complexity need reveal only very little agreement in order to reject the hypothesis that they arise from independent sources. The failure of a statistical test of independence can thereby serve as a basis for recognising signal sources if they possess enough degrees of freedom. Combinatorial complexity of stochastic detail can lead to similarity metrics having binomial type distributions, and this allows decisions about the identity of signal sources to be made with astronomic confidence levels. I will describe an application of these statistical pattern recognition principles in a system for biometric personal identification that analyses the random texture visible at some distance in the iris of a person's eye. There is little genetic penetrance in the phenotypic description of the iris, beyond colour, form and physiology. Since its detailed morphogenesis depends on the initial conditions in the embryonic mesoderm from which it develops, the iris texture itself is stochastic, if not chaotic. The recognition algorithm demodulates the iris texture with complex valued 2D Gabor wavelets, and coarsely quantises the resulting phasors to build a 256 byte `iris code' whose entropy is roughly 173 bits. Ergodicity and commensurability facilitate extremely rapid comparisons of entire iris codes using 32-bit XOR instructions. Recognition decisions are made by exhaustive database searches at the rate of about 10,000 persons per second. *** *** *** *** *** - ------- End of Blind-Carbon-Copy ------- End of Forwarded Message

1 0

A confused quotation ?
by bart＠netcom.com 17 Dec '03

17 Dec '03

Is this not strange ? Date: Sun, 10 Apr 1994 20:26:23 -0400 From: E-D-U-P-A-G-E <info(a)ivory.educom.edu> ... OPEN SECRET Instead of using mathematical codes to scramble and unscramble messages, Georgia Tech physicists are devising a way of sending a message with electronic noise generated by a flickering laser. By connecting identical lasers over fiber optics, the same random pattern of noise is generated at both the sending and receiving end, and the receiving simply subtracts the noise to uncover the message. (Atlanta Journal-Constitution 4/7/94 E2)

1 0

Dallas Crypt Chip ???
by danisch＠ira.uka.de 17 Dec '03

17 Dec '03

Hi, does anybody know what is the "Dallas Crypto Chip" ? Does it have anything to do with Clipper? thanks Hadmut

1 0

Soda "Keywords" Idiocy
by anonymous＠extropia.wimsey.com 17 Dec '03

17 Dec '03

Uu> Isaac Norby writes: > INTERNET: Isaac.Norby(a)f217.n125.z1.FIDONET.ORG > >>ira shipment of cocaine > >>explosives detonate > -------- Uu> I sent mail to hh(a)soda.berkeley.edu with Subject: remailer-info. I Uu> got some info back that included: > = A note about keywords [This was not in the original info-pack I got back when...] > This remailer inserts keywords into the headers and tailers of all posts and > remails. These headers contain phrases which would probably trigger > automated net monitoring programs, rendering them less effective. This > insertion is completely automatic and certainly does not constitute a > statement of intent by anyone (especially the remailer operator) to do > anything. This is simply idiotic, worse than Hollander's childish admonition not to throw knives. All "keywords" do is light up those readers who do not know what they're about, something that Hollander should explain in the footer if he continues to do this. These keywords ought to be placed WITHIN the remailer disclaimer in order to make sure that readers know where they originated and by whom. Anyway, I won't be using the Soda remailer again. IN

1 0

Re: MacPGP and AOL
by tim werner 17 Dec '03

17 Dec '03

>Date: Sun, 10 Apr 1994 20:33:48 -0400 (EDT) >From: Duncan Frissell <frissell(a)panix.com> >There is no "court case pending against Phil Zimmerman." Neither he nor >his legal counsel have been notified of any action against him. He has >not been named publically in any official papers. He has not been >subpoenaed. There *is* an insvestigation of how PGP was exported (nothing >about its *creation*). Two firms have testified before a Grand Jury. Late last year, in response to a "bulletin" from eff, I sent money to some lawyer (in Colorado, I think) for the Phil Zimmerman defense fund. Was I defrauded? How embarrassing. If I dig out the cancelled check, perhaps someone on the list can tell me more? tw

3 2