December 2003 - cypherpunks-legacy

fermats theorem. possible urban legend
by Grand Epopt Feotus 17 Dec '03

17 Dec '03

While ona BBS someone brought up something about Fermat's Last THerorem being proven and that renders all crypto broken. After trying to figure out what the hell this person was talking about I figured that he apparently believes that all encyptian schemes are based on large numbers, and since Fermats Theoremn is something like proving that youca find the solution for a^n + b^n = c^n that all of the codes are broken. Now please dont mistake me for someone who has fallen for this, but I am just wondering what the hell this guy is talking about? You're eqipped with a hundred billion nueron brain, that's wired and fired, and it's a reality generating device, but you've got too do it. Free youself ----Tim Leary----

1 0

Re: bumperstickers
by wcs＠anchor.ho.att.com 17 Dec '03

17 Dec '03

> They can have my crypto when they pry it from my cold, dead, keyboard. Or when they listen to the electromagnetic emanations from your live non-TEMPEST keyboard :-)

1 0

Prime Numbers
by Jeremy Cooper 17 Dec '03

17 Dec '03

I found something interesting that I have not proven, but it has not failed yet: The integer N is prime if: 2^N - 2 --------- N is an integer. Don't ask how I found it, I was just fooling around. Now: Is there some way to reverse the formula so we can insert and integer and get a prime number out? Let me know, I am over excited. _ . _ ___ _ . _ ===-|)/\\/|V|/\/\ (_)/_\|_|\_/(_)/_\|_| Stop by for an excursion into the-=== ===-|)||| | |\/\/ mud.crl.com 8888 (_) Virtual Bay Area! -===

6 5

TCMay's posting on zero knowledge, last year
by Matt Thomlinson 17 Dec '03

17 Dec '03

Here's what I grabbed from the list last time this came up.. By the way, this is one of the documents I have up for viewing via www (see .sig). mt Matt Thomlinson University of Washington, Seattle, Washington. phone: (206) 548-9804 Check my home page -- ftp://ftp.u.washington.edu/public/phantom/home.html PGP 2.2 key available via email, or finger phantom(a)hardy.u.washington.edu Date: Wed Apr 7 21:42:08 1993 From: tcmay(a)netcom.com (Timothy C. May) <tcmay/daemon> Subject: MATH: Zero Knowledge Proofs [Since this should also be of interest to the Cypherpunks list, which Ray is/was subscribed to, I am posting this essay to that list.] 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^756839 | Public Key: MailSafe and PGP available.

2 1

New stego prog was "A possibility"
by rarachel＠prism.poly.edu 17 Dec '03

17 Dec '03

Hey guys, I'm in the final throes of applying some cleaning up on a bit of code I wrote a couple of years ago. I'm wondering what would be some good sites to FTP this to? (I'd like to just post it up on here, but since there are non-USA residents on this list, I don't need the NSA to come on knocking on my door as I've bigger things to worry about (like bills, graduating, etc.) Anyhow, a bit about this code: This is a program called White Noise Storm which I wrote out of an inspiration flash (and subsequently the reason I joined this list.) I had left this project to rot until recently when my school finally offered a crypto class, and decided on making this my project. Unfortunatly disaster struck and I had lost the final version of this program a few months ago, having only a buggy, unfinished backup. Suffice to say, I spent all last night infront of my 486 and resurected WNSTORM from the dead, and in doing so added some features which make it a useful program. Someone from MicroSoft had a similar idea, so I thought I'd go public with it before WNSTORM vanished totally. :-) So Ophir Ronen (Rho) <a-ophirr(a)microsoft.com>, here it comes. :-) A brief description of this program is basically an cypher box that takes in a password, a stream of random numbers, a plaintext file, and a window size specification (more on this later.) The program takes in one byte of plaintext, several bytes of random numbers (called a window) of varying size, and then takes an encrypted copy of the plaintext byte and spreads its bits across the random number window. The actual bits and bytes that get replaced in this window depends on the passkey and the previous window. The great and obvious disadvantage to WNSTORM is that the size of the cypher text is several times larger than the plaintext. Another is that this is a private key system, but that's not quite as large a sore point. However, by replacing the random number stream with the low bits of a sound, picture, movie or other noisy data, inserting the plaintext into this noise with WNSTORM, and re-injecting the low bits back into the picture gives us the possibility of an excellent stego system! WNSTORM will also try and statistically fix the bits it changes so that the outgoing cyphertext matches the incoming random noise stream statistically, making a stego sniffer's job much harder... Anyhow since I'll need to clean up both source code and documentation, I thought I'd take this opportunity and announce the program. Oh and Tim, this is what I was talking to you about a long time ago and kept secret. :-)

1 0

Another Anti-Clipper Resolution
by Dave Banisar 17 Dec '03

17 Dec '03

I found this on the Public_Keys forum on Fidonet.. -dave Subject: Clipper/Telephony Big Bro Resolution To: All From: David Treibs Date: 3/26/94 6:07:02 PM ------------------------------------------- The following was passed as a resolution for the Republican convention in Senatorial District 19 of Uvalde county, Texas. I will attempt to get it adopted at the state level also. ENCRYPTION/GOVERNMENT MONITORING (BIG BROTHER IS WATCHING YOU) Whereas, government is increasingly intruding into the private matters of its citizens, And, an example of this intrusion is Clinton's Clipper/Skipjack encryption chip, which would allow the government easy access to all private and corporate electronic communications by telephone, computer, etc., And, a further example is the government's push to force all communications providers to leave a "back door" through which the government could easily monitor all communications, And, it is a trait only of despotic governments to scrutinize the private communications of its citizens, Resolved, we urge that the Clipper/Skipjack scheme be dropped and the Digital Telephony Act killed, that private communications and encryption be allowed to flourish without government "back doors," and we urge our government to give up the idea that we the people are guilty of something and must be monitored. --- Maximus/2 2.01wb * Origin: Frank's Station (1:19/148)

1 0

Re: identity, privacy, & anonymity in cyberspace
by jim＠bilbo.suite.com 17 Dec '03

17 Dec '03

tmp(a)netcom.com writes/asks: > yes, remailers solve the problem of trying to post > messages without identity, but are we sure this is a > `problem' we want to `solve'? If this problem is not solved then all posts must contain a reference to the poster's true identity. Is that what you want, tmp(a)netcom.com? How would it be enforced? Government approved public-key pairs issued at birth? Random identity checkpoints on the Infobahn? A ban on all un-approved cryptography? Peer pressure? > hal argues below that there is `no line dividing the clean > from the unclean' (real name vs. pseudonymous vs. > anonymous etc.). to the contrary it seems to me to be the > case that either `i know who you are' or i don't. what does > it mean for me to `know who you are'? i admit there is no > basic definition, but it does seem to me that should not > prevent us from trying to find one. Instead of asking "who are you?", ask "what are you like?". I don't usually need to know who you are, but in certain contexts it is important to know what you are like. Further, I don't need to know what you are like in all contexts. Identity-based systems approach the "what are you like" question by demanding to know "who you are", and then determining "what you are like" by accessing various and sundry databases. These various and sundry databases are rapidly condensing into a few logical mega-databases. The problem with identity-based systems in which everyone has only a single identity is that it soon becomes very easy for someone to learn more about you than is necessary or desirable. Cross-referencing is the root of all evil! :-) I think much of the technology advocated on this mailing list can enable people to answer the important "what are you like" questions without creating systems that can also be used to pry into your entire life history. > the important goal is `defining what privacy really > means' I agree it is an important goal. > and cypherpunks seem to take the position, `it > means that nobody knows anything about me'. I disagree. I think cypherpunks want to retain (or re-acquire) the ability to control who knows what about them and when and under what contexts. This is a bit different from "nobody knows anything about me". However, I can't speak for all cypherpunks. > our society simply cannot function under this constraint. If by "our society" you mean the society in which we currently live, I'd have to agree. That does *not* mean I believe all possible societies become impossible under this constraint. Actually, I believe "under this constraint" is a strawman (see previous paragraph). > if you continue to insist that `nobody should know who i > am' i fear you will be bypassed by more sophisticated [?] > groups that have a less polarized view of issues of > identity and privacy. and it will ultimately be the least > controversial proposals that will shape the future we > live in. Being a pessimist, I'll have to agree with you here, although for slightly different reasons. I believe that as long as there are income and property taxes, the government will find ways to justify prying into our personal lives. Jim_Miller(a)suite.com

1 0

Re: Prime Numbers
by rjc＠gnu.ai.mit.edu 17 Dec '03

17 Dec '03

Jeremy Cooper writes: > I found something interesting that I have not proven, but it has not > failed yet: > The integer N is prime if: > 2^N - 2 > --------- > N is an integer. This is fermat's little theorem. What you have written basically says 2^N - 2 = 0 (mod N) or 2^(N-1) = 1 (mod N). Note, the converse doesn't apply. If (2^N-2)/N is an integer, N isn't neccessarily prime. For example, take N=561=(3*11*37) For extra credit, prove your hypothesis. ;-) -Ray -- Ray Cromwell | Engineering is the implementation of science; -- -- rjc(a)gnu.ai.mit.edu | politics is the implementation of faith. --

3 2

Crypto, satellites, & China
by paul＠poboy.b17c.ingr.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- A story in the 3/14/94 issue of _Aviation Week_ reports that Hughes and Martin Marietta have satisfied the State Department and will now be able to launch the Optus B3 comsat. All the quotes below are from the article; it didn't have any detail on the cryptostuff. State had held up the launch because the Optus B3 payload included a "sensitive decryption chip". The USG made trade with China subject to the Missile Technology Control Regime (MTCR) after China was suspected of selling missiles to Pakistan. Hughes agreed to remove the chip, which "guards the satellite's steering commands"; once removed, State lifted the export restriction. "By removing the chip, authority for approving the launch was shifted to the Commerce Dept. from an interagency review commission headed by the State Dept. that had far less leeway to act." I never knew that encryption fell under MTCR in addition to ITAR. Presumably any crypto hardware or software which can be used to protect missile or satellite telemetry or commanding can be restricted. If anyone has more details on the MTCR and its application, I'd love to hear it. - -Paul Robichaux - -- Paul Robichaux, KD4JZG | Out the 10Base-T port, through the router, perobich(a)ingr.com | over the leased line, off the bridge, past Intergraph Federal Systems | the firewall... nothing but net. Of course I don't speak for Intergraph. -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLamroCA78To+806NAQEK0wP/SD8692ZaMl71c57dSKAG7vmYVcyvIJi5 CNuWb4u3kL7WlfEtzrZ42Dfx4avgyzcjyoIyBDE5r+7n/nSMnbBGZGYR2OyTBQ5b GaK8RrrdJQoKujEvzR8i+XhtBin2doK5hzBHTY2VpYIexMH34MLZeYNST4nA7ek9 5EGWhbZ5mxw= =avDx -----END PGP SIGNATURE-----

2 2

T-Shirt Shipping Status
by Christian Void 17 Dec '03

17 Dec '03

Most of the shirts have shipped, with the exception of orders containing sizes over XXL. There was a probably with the larger sizes, which has been resolved. Those orders (the last remaining) will be shipped out sometime this week. I apologize for any delays, and the time it took to get this together. It turned out to be a bigger project than originally anticipated. It's too bad I can script a packaging algorithm to handle this, but that's real-life for you. :) If anyone has any questions, comments, gripes, flames, etc, mail me. Christian Void /T71 | "I don't like it, and I'm sorry I | V/M/Research, Inc. cvoid(a)netcom.com | ever had anything to do with it." | P.O. Box 170213 Tel. 1+415-998-0774 | -Erwin Schrodinger (1887-1961) | SF, CA 94117-0213 * PGP v2.3a Public Key Available Via Finger *

1 0