December 2003 - cypherpunks-legacy

Re: GELP/was:Word List
by Sven 17 Dec '03

17 Dec '03

>That should be a "what" is GELP. It's a type of sea weed. GOAT |__ |--> SVEN: a.k.a. Chris Blanc Internet consulting/Web design [ http://www.loop.com/~sven/ ] Some only sample the dark wine of life's blood...

1 0

Provably "Secure" Crypto (was: IPG Algorithm Broken!)
by Dana W. Albrecht 17 Dec '03

17 Dec '03

Our friend Don Woods seems to have inadvertently sparked what could be a useful and serious discussion regarding "provably secure cryptography." Not to be confused with the usual "unbreakable" snake oil we see peddled so often, I refer to systems for which rigorous mathematical proof that "there are no shortcuts" exists. To my knowledge, no such systems, with the exception of a real one-time pad, exist today. However, I also under the impression that ongoing research on this topic continues. For example, consider the work being done on "Lattice" cryptosystems (see http://jya.com/lattice.htm) "diGriz" is right. Nothing precludes the existence of a cryptographic algorithm for which a rigorous mathematical proof of "security" exists --- where "security" means a provable lower bound on the time required for recovery of the key. Indeed, it seems that finding such an algorithm --- or providing the necessary rigorous proof for a current algorithm --- is a laudable goal of academic cryptographic research. Rigorous proofs of the non-existence of an algorithm are not new. Neither are rigorous proofs that any algorithm which can solve a given problem requires a minimal running time. Or, in an even stronger sense, that a particular known algorithm for a given problem is indeed a (provably) optimal algorithm for that problem. For a (non-cryptographic) example of a proof of the first sort --- that is, that "there exists no algorithm" --- consider the famous "Halting Problem" for Turing machines. (I believe someone else has also mentioned this.) There are many proofs such as this one, often related, though the Halting Problem itself is perhaps the most famous example. For an (again, non-cryptographic) example of a proof of the second sort --- that is, that "any algorithm that solves a given problem requires a minimal running time" --- consider the proof that the "minimal" number of key comparisons in the worst case required to sort a random list of elements for which only an ordering relationship is known is O(nlog(n)). See Knuth, Volume 3, section 5.3. For a simpler example, a standard "binary" search which requires O(log(n)) comparisons to find a given element in the worst case is provably the optimal algorithm for this task. Turning once again to cryptography, there is presumably an "optimal" algorithm for factoring a "general" number in the "worst" case. Of course, known algorithms for factorization seem to regularly improve and no one has even suggested that any current algorithm is (provably) the "optimal" algorithm. Worse case bounds on running time for currently known algorithms can certainly be produced, but no one currently knows if these are the best algorithms. However, just as one can say, "How do you know that tomorrow some brilliant mathematician will not produce a polynomial time factorization algorithm?" one can also say, "How do you know that tomorrow some brilliant mathematician will not provide a rigorous proof that all factorization algorithms --- in the worse case --- require some specified minimal running time?" While the current state of mathematical knowledge suggests that this is not likely to happen anytime soon for the factorization problem, it is encouraging to see work in areas where more rigorous proofs of security are within closer reach. Again, I refer to work on Lattice problems. If the types of rigorous proof regarding "what can't be done" that are known for the Halting Problem, sorting, and searching are available for cryptographic problems, then this is indeed a major (and laudable) advance in cryptography. Obviously, discussion on this topic is unrelated to such security problems as implementation mistakes, fault analysis, outright theft of keys, etc. I hope that I've been careful to explain what I mean by "provably secure" and that it's not interpreted to include these types of attacks. I'm interested in the current state of research (if any) on this topic. Other than what John Young sent to the list some time ago about Lattice stuff --- which is certainly far from prime time --- I've not seen anything else. I also haven't devoted a lot of time to looking. Relevant pieces of the earlier thread are included below. Comments, anyone? Dana W. Albrecht dwa(a)corsair.com ---------------------------------------------------------------------------- Eric Murray <ericm(a)lne.com> writes: > Don Wood <wichita(a)cyberstation.net> writes: > > Do not belive it, it will never happen. It is impossible, and we can > > prove it to your satisfaction. > > No, you can't. It's impossible to prove an algorithim unbreakable. > You can only say that it hasn't been broken yet, but you can't > predict the advances in cryptoanalysis. > > If, in two or three years, no one's broken it then maybe it'll seem > like a reasonably-secure algorithim. Of course when someone does break > it you'll just say "oh, that wasn't the real algorithim" like you did > last time. [ Snip ] > You can't prove a negative. The best IPG could say is that > it can't be broken with current technology. > Next week someone might come up with a new way > to break ciphers that renders the IPG algorithim breakable. > > You point could have been that the same problem exists > for proofs- that next week someone could come up > with a way to prove, for all time, that an algorithim > really IS unbreakable. So, to cover that posibility > I should have said "it's currently impossible to > prove an algorithim unbreakable". :-) ---------------------------------------------------------------------------- "diGriz" anonymously writes: > The good news is that you can prove a negative. For example, it has > been proven that there is no algorithm which can tell in all cases > whether an algorithm will stop. [ Snip ] > The best they can say is what they did say: they have a proof that > their system is unbreakable. What you question, quite reasonably, > is whether they have such a proof. [ Snip ] > Or, more accurately, nobody credible has seen such a proof. But, a > clever person might invent one. ---------------------------------------------------------------------------- The Deviant <deviant(a)pooh-corner.com> writes: > No, he was right. They can't prove that their system is unbreakable. > They _might_ be able to prove that their system hasn't been broken, and > they _might_ be able to prove that it is _unlikely_ that it will be, but > they *CAN NOT* prove that it is unbreakable. This is the nature of > cryptosystems. > > > >The best IPG could say is that > > >it can't be broken with current technology. > > >Next week someone might come up with a new way > > >to break ciphers that renders the IPG algorithim breakable. > > > > The best they can say is what they did say: they have a proof that > > their system is unbreakable. What you question, quite reasonably, > > is whether they have such a proof. > > It is impossible to prove such a thing. It's like saying you have proof > that you have the last car of a certain model ever to be built. Anybody > could come along and build another, and then you don't have the last one. > > > > > >You point could have been that the same problem exists > > >for proofs- that next week someone could come up > > >with a way to prove, for all time, that an algorithim > > >really IS unbreakable. So, to cover that posibility > > >I should have said "it's currently impossible to > > >prove an algorithim unbreakable". :-) > > > > Or, more accurately, nobody credible has seen such a proof. But, a > > clever person might invent one. > > There *IS NO SUCH PROOF*. Just like you can't prove that god created the > universe, or that Oswald shot Kennedy, and so on and so forth. It can't > be proven. It never has been proven, and it never will be proven. People > have new ideas, new algorithms are invented. Someday, somebody will crack > _all_ the cryptosystems that have now been invented. [ Snip ] > diGriz anonymous writes: > > At 6:56 PM 11/23/1996, The Deviant wrote: > > >No, he was right. They can't prove that their system is unbreakable. > > >They _might_ be able to prove that their system hasn't been broken, and > > >they _might_ be able to prove that it is _unlikely_ that it will be, but > > >they *CAN NOT* prove that it is unbreakable. This is the nature of > > >cryptosystems. > > > > Please prove your assertion. > > > > If you can't prove this, and you can't find anybody else who has, why > > should we believe it? > > Prove it? Thats like saying "prove that the sun is bright on a sunny > day". Its completely obvious. If somebody has a new idea on how to > attack their algorithm, it might work. Then the system will have been > broken. You never know when somebody will come up with a new idea, so the > best you can truthfully say is "it hasn't been broken *YET*". As I > remember, this was mentioned in more than one respected crypto book, > including "Applied Cryptography" (Schneier). ---------------------------------------------------------------------------- "diGriz" Anonymously responds: > Page number? > > Perhaps it would be helpful to hear a possible proof. If somebody > were to show that breaking a certain cryptographic algorithm was > NP-complete, many people would find this almost as good as proof that > the algorithm is unbreakable. > > Then if a clever person were to show that the NP-complete problems > were not solvable in any faster way than we presently know how, you > would have proof that a cryptographic algorithm was unbreakable. > > There is no obvious reason why such a proof is not possible. > > diGriz

8 7

Re: IPG Algorith Broken!
by nobody＠cypherpunks.ca 17 Dec '03

17 Dec '03

At 7:10 AM 11/24/1996, The Deviant wrote: >On Sun, 24 Nov 1996, John Anonymous MacDonald wrote: >> At 6:56 PM 11/23/1996, The Deviant wrote: >> >On Sat, 23 Nov 1996, John Anonymous MacDonald wrote: >> >> The good news is that you can prove a negative. For example, it has >> >> been proven that there is no algorithm which can tell in all cases >> >> whether an algorithm will stop. >> > >> >No, he was right. They can't prove that their system is unbreakable. >> >They _might_ be able to prove that their system hasn't been broken, and >> >they _might_ be able to prove that it is _unlikely_ that it will be, but >> >they *CAN NOT* prove that it is unbreakable. This is the nature of >> >cryptosystems. >> >> Please prove your assertion. >> >> If you can't prove this, and you can't find anybody else who has, why >> should we believe it? > >Prove it? Thats like saying "prove that the sun is bright on a sunny >day". Its completely obvious. In other words, you can't prove it. Thought so. >If somebody has a new idea on how to attack their algorithm, it might >work. Then the system will have been broken. You never know when >somebody will come up with a new idea, so the best you can truthfully >say is "it hasn't been broken *YET*". As I remember, this was mentioned >in more than one respected crypto book, including "Applied Cryptography" >(Schneier). Page number? Perhaps it would be helpful to hear a possible proof. If somebody were to show that breaking a certain cryptographic algorithm was NP-complete, many people would find this almost as good as proof that the algorithm is unbreakable. Then if a clever person were to show that the NP-complete problems were not solvable in any faster way than we presently know how, you would have proof that a cryptographic algorithm was unbreakable. There is no obvious reason why such a proof is not possible. diGriz

2 1

Photobuster to beat radar...
by Lynne L. Harrison 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit To: cypherpunks(a)toad.com Date: Sun Nov 24 18:19:39 1996 At URL: http://www.havenofhope.org/photobuster/photob2.html Photobuster is a spin off from a specialty electronics company (Grand Systems) who saw the need for a system to foil the photo radar picture. We realize that people like your selves don't usually speed on purpose and can't afford to pay hundreds of semolies just because you look away from the speedometer from time to time. Our easily installed electronic Photobuster unit is a an electronically triggered device that mounts in the rear window with a satellite unit that mounts at the license plate. It watches the right side of the road for a photo radar setup. If you are driving at speeds in excess of the operators setting on the photo radar, it will attempt to photograph your car. When it does this the Photobuster senses the attempt and triggers a return response rendering the radar photo useless. It has an audible warning and a visual light to let you know each time you save 100 bucks. This unit only triggers if the photo radar attempts to photograph your car. NOTE: Photobuster has nothing covering your plate as is with other filter, poleroid and lenticular optical devices. We are told it is not legal in most areas, to install any kind of plastic cover over the plate, see through or not. ************************************************************ Lynne L. Harrison, Esq. | "The key to life: Poughkeepsie, New York | - Get up; lharrison(a)mhv.net | - Survive; http://www.dueprocess.com | - Go to bed." ************************************************************ -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMpjYDD5A4+Z4Wnt9AQGEiwP+OwSodqT2IMQJIFxf/OPFIr7JSJJY7uWc tBfpskpydWvpcKe49PZMbflNOsTgjuW/MyRXLwu8j/mMIEKqwe7KvYPEVUIHNjx3 by3dLMglaihuObbAViewOTS2mjat2bWtB24cGwHI1/94gc8trLlXS3VTtCQYcnkl Btw1KpGDCek= =pfBU -----END PGP SIGNATURE-----

1 0

Aga is talking to himself
by frantz＠netcom.com 17 Dec '03

17 Dec '03

At 6:15 AM 11/24/96 -0500, aga <aga(a)dhp.com> wrote: >On Sun, 24 Nov 1996, John Anonymous MacDonald wrote: actually the message was from lucifer(a)dhp.com: >> aga <aga(a)dhp.com> writes: ... messages suppressed It looks like our juvenile "friend" is talking to himself. I am truely sorry that he feels a need to harass ladies who have actually made something of their lives. ------------------------------------------------------------------------- Bill Frantz | The lottery is a tax on | Periwinkle -- Consulting (408)356-8506 | those who can't do math. | 16345 Englewood Ave. frantz(a)netcom.com | - Who 1st said this? | Los Gatos, CA 95032, USA

1 0

The American Black Chamber - Yardley - Re: 1996 Codebreakers
by stewarts＠ix.netcom.com 17 Dec '03

17 Dec '03

Adam Shostack <adam(a)homeport.org> wrote: > I just got a review copy of the new (1996) ed. of Kahn's The >Codebreakers from my local used bookstore. Its a little disapointing, >about 20 new pages of material. Kahn states in the forward that all >the new material is in a chapter at the end. ....... > Anyway, copies should be in bookstores soon. If you don't >have a copy already, Kahn is the definitive history book, and is well >worth having. I just got a copy* of the 1981 "The American Black Chamber", by Herbert O. Yardley, with a new (1981) intro by Kahn. ISBN 0-345-29867-5. The original had been published in 1931, went through a couple printings, and sold twice as many copies in Japan as the US. In 1933 the US passed a law banning the publishing of any material that had been published in diplomatic codes, and of course they withheld permission for future printings. Lots of good material on the state of crypto from WWI through the 1920s. Crypto wasn't yet on a mathematical basis, though it was starting to emerge in cryptanalysis. After the World War ended, most of the traffic was cracking diplomatic correspondence, especially for disarmament negotiations. Getting users to take crypto seriously was a problem - most of the US communications during the Spanish-American war used a sort of "rot-1898", and even during the World War, military plans were often broadcast on radio using wimpy codes, causing much damage to both sides. Codes were generally designed by people who didn't have extensive cracking experience, and therefore most new codes were easily cracked as well. Yardley's organization diverted some of its expertise to cracking secret inks, which were extensively used by German spies. Language and cultural differences caused surprising difficulties - there was one person they could find who knew German shorthand systems, and finding Japanese language experience after the war was difficult, since they didn't want to use Japanes immigrants for security reasons and most missionaries wouldn't do military work (both for ethical reasons and because it would lead the Japanese government to crack down on missions to Japan, Korea, and China.) Kahn speculates that the ability to crack Japanese naval codes in WWII was probably enhanced by Yardley's people's work - PURPLE was much stronger than the earlier Japanese diplomatic codes, but the Japanese Navy believed that "This time, it's all right" (cable chief, to foreign minister :-), when it wasn't. Yardley reports at the end of the book that he believed the science of cryptography would die out - AT&T had invented a cypher machine during the war, and had invented one-time pads, and the combination would make code clerks obsolete and codes unbreakable...... Shortly after that, in 1929, the new Secretary of State was shocked to discover that his department was funding eavesdropping. "Gentlemen don't read each others' mail." # Thanks; Bill # Bill Stewart, +1-415-442-2215 stewarts(a)ix.netcom.com # You can get PGP outside the US at ftp.ox.ac.uk # (If this is posted to cypherpunks, I'm currently lurking from fcpunx, # so please Cc: me on replies. Thanks.)

1 0

P.S. on chain letters
by dlv＠bwalk.dm.com 17 Dec '03

17 Dec '03

A week or so ago I was ranting about chain letters and other memes - well, today I came across some well-research Web site hosted by Kenneth Han (Black Unicorn may know him) - check out http://www.gwu.edu/~khan if you care about more analysis of the Craig Sherhorn phenomenon. --- Dr.Dimitri Vulis KOTM Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps

1 0

Recovery after flood
by dlv＠bwalk.dm.com 17 Dec '03

17 Dec '03

I'd appreciate a response from M.Aldrich and anyone else who's into disaster recovery: Someone I know had their (paper) files submerged in water. Now all the papers (most of them xerocopies, some photographs) are stuck together. They are, of course, confidential to some degree. Can someone refer us to someone in the Boston area who could assist in recovering the files? --- Dr.Dimitri Vulis KOTM Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps

3 4

Re: Symantec's claim.
by Alan Olsen 17 Dec '03

17 Dec '03

At 03:45 PM 11/25/96 +0200, cracker(a)icon.co.za wrote: > >In light of recent claims,i would like somebody to clear this up for me. >There seems to be a great deal of conjecture over wether or not the Deeyenda Virus exhists. >Symantec denies it's existence,although i hear differently?? >Greatly appreciate anyone who can shed some light on the subject,even though C-punks list doesnt usually deal with this topic of thought ;) >Anyone come across the pkz300 trojan,if you have it send it please. >A student,a paper,and a possible future career are at stake here,so please dig deep into your >pockets!!!!!! Asking a lot i know! Deeyenda is a hoax. (Very similar to "Good Times" and aimed towards the same audience.) Info on it can be found at: http://www.kumite.com/myths/myth027.htm --- | "Remember: You can't have BSDM without BSD." | |"The moral PGP Diffie taught Zimmermann unites all| Disclaimer: | | mankind free in one-key-steganography-privacy!" | Ignore the man | |`finger -l alano(a)teleport.com` for PGP 2.6.2 key | behind the keyboard.| | http://www.ctrl-alt-del.com/~alan/ |alan(a)ctrl-alt-del.com|

1 0

Sameer R.I.P.
by drose＠AZStarNet.com 17 Dec '03

17 Dec '03

C2 has a nice corporate-style fig leaf on its site. Sameer has decided, it seems, to get out of the anonymity business and pursue other interests. Nice run while it lasted. FYI, Sameer does mention that his recent legal brouhaha had nothing to do with this decision.

4 3