- cypherpunks-legacy - lists.cpunks.org

Re: The Halting Problem
by tcmay＠netcom.com 13 May '93

13 May '93

>It occurred to me that determining whether a set of random bytes is >actually a crypto message could be reduced to the halting problem. >Given this, it would be theoretically impossible to prove that an >uncrackable message was indeed a crypto message. The revelation here >(for me, anyway) is that if arbitrary crypto were made illegal, the >burden of proof would be on the prosecution which would have to crack >the message (at least partially). > >Paul E. Baclace Sorry I was out today and missed the halting problem debate! Paul's intuition (or perhaps proof) is correct, at least according to a paper Len Adleman wrote some years back, showing this. (I don't have the paper, but I heard Len describe the results at the Crypto '88 Conference. As with most such results, the result probably depends on a very careful statement of what the terms mean, so take my comments as being only indicative of the flavor of the results.) What follows is not from Adleman's talk or paper, but from information theory. The Kolmogorov-Chaitin view of "randomness" is very similar in spirit: how does one know whether a sequence/string is "effectively random" (short definition: effectively random means there is no shorter description of a sequence than itself) or is instead describable by some shorter sequence? Thus the string "31415926535897932384626433" is recognizable to most agents (people, smart programs) as the first 25 digits of pi (however, it *could* be something else, but I won't get into that right now). But the string "67902371045873651853" is probably not recognizable as anything other than this string. Kolmogorov complexity is defined as the length of the shortest programs which can generate (print) the object. Thus, "alternating 1s and Os" is very short, "the digits of pi" is slightly longer, and the digit mentioned above ("679023...") may not have any shorter program than itself. (The famous Berry Paradox enters here: "The shortest not nameable in under ten words." Does this number exist? If so, what is it?) Finding the generating program is very similar to decrypting a message (I suspect there's a way to formalize the equivalence of encryption and Kolmogorov complexity, beyond this admitted hand-waving, but I don't know it offhand). Strings or expressions which "appear" random but which are actually very regular, or easy to describe, with the proper "key" are called "crypto-regular." Encrypted messages are clearly crypto-regular. Cover and Thomas, in "Elements of Information Theory," 1991, write: "One of the consequences of the non-existence of an algorithm for the halting problem is the non-computability of Kolmogorov complexity. The only way to find the shortest program in general is to try all short programs and see which if them can do the job. However, at any time some of the short programs may not have halted and there is no effective (finite mechanical) way to tell whether they will halt or not and what they will print out. Hence, there is no effective way to find the shortest program to print a given string." (By the way, exhaustive search of a keyspace--as someone suggested--is also not enough, as the cryptostring above (""679023...") may result in several syntactically valid English expressions, such as "attack at dawn," "whopper with fries," "robins migrate peripherally." Knowing when to stop further crypanalysis of a message might be called the "crypto halting problem.") Fascinating stuff! (To my current thinking, the core of the universe!) I recommend Gregory Chaitin's "Algorithmic Information Theory" and "Algorithms and Randomness." And the Cover and Thomas book. A (mundane) consequence for cypherpunks is that the sending of any random-looking stuff may be banned, someday. (No doubt it is in many countries, if they bother to look. Sending unreadable stuff is grounds for a visit by the Federales.) And clearly even "real messages," like this one, like Peter Wayner's baseball scores, like GIF images, etc., can have messages attached. If simple cryptanalysis reveals simple English-like messages, Occam's razor suggests a decryption has been made. But it can never be known for sure whether other messages exist. --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: by arrangement

1 0

Re: CALLER ID?
by speth＠cats.UCSC.EDU 13 May '93

13 May '93

Years ago, when I crossed the country with a regular cell-phone, I tried calling another ANI demo at points along the way. The result was just the same, in a couple different calling areas: the demo always read back some strange number with the area code of the place I was in. I figured it must just go out of some line at the cell-site like a regular phone call. I never tried calling the number that was read back though. ________________________________________________________________________________ james speth email for pgp compatible public-key speth(a)cats.ucsc.edu ________________________________________________________________________________ Have you ever had your phones tapped by the government? YOU WILL and the company that'll bring it to you... AT&T

1 0

Re: CALLER ID?
by Satan 13 May '93

13 May '93

> You're confused or you miswrote: 800 number owners pay for your calls, > people with caller ID boxes do not. > > So, do you think that the "privacy protecting 900 number" ($2/min) uses > your number (remember that they DO have it) for privacy junk mailing > purposes? i realize that caller ID box owners are not paying for your call but this system was talking about 800 numbers two things i will grant 1) most 800 numbers are pro-watts or whatever it is and pay just one huge charge a month and dont deal with each bill seperately so they dont get charged for your specific call BUT it is a great way to get marketting stuff ive wroked for companies that do that 2) most peopel dont know that an 800 number isnt anonymous but that goes to educating the public and i really dont think the public cares enough to want to know

2 1

Re: The Halting Problem
by peb＠PROCASE.COM 13 May '93

13 May '93

>From pmetzger(a)lehman.com Wed May 12 15:28:22 1993 >you missed the word "particular". Well, I was considering this an unknown--that is, the cryptoanalyzer does *not* know the particular Turing machine, so it is an arbitrary machine, although the program is finite. That is, I am suggesting a decrypt-machine that is turing-complete, however, as: >From: Marc.Ringuette(a)GS80.SP.CS.CMU.EDU points out: >So for >any encryption method which allows the recipient to verify in polynomial time >that his decryption is the only possible intended message, we know that the >decryption problem is in NP. a practical crypto algorithm must allow decrypt in P time and since NP problems do theoretically halt, then the halting problem is not a blanket defense. The realities Brian.Hawthorne(a)East.Sun.COM mentions are all too real: Anonymous remailers could be effectively broken by requiring tracability (say, they way banks must fill out special forms for any transaction over $10k (which is why Oliver North sent money to the Contras in $9.7k packets)); in the same law, the remailer would be shut down if it did not comply. I think the widespread use of video phones would make steganography easier, however. Paul E. Baclace peb(a)procase.com

1 0

Re: CALLER ID?
by karn＠qualcomm.com 12 May '93

12 May '93

Interesting. As expected, when I called 1-800-235-1414 from a PBX extension here at work, it read back the trunk number, not my actual extension number. The same for a developmental CDMA digital cellphone, since we use PBX-style trunks from our switch. But when I called it from a conventional AMPS (FM) cell phone using Pac Tel Cellular, I also got a number that was different than my mobile's real number. And when I called it back, I got a number-not-valid intercept. Interesting. Apparently one real cellular switch also looks like a PBX as far as ANI goes. I wonder how widespread this is. Anybody with a cell phone on a service other than Pac Bell who is willing to give it a try? Phil

2 1

Re: The Halting Problem
by peb＠PROCASE.COM 12 May '93

12 May '93

>From mab(a)crypto.com Wed May 12 13:26:04 1993 >I don't see how determining that a particular string is an encrypted >message reduces to the halting problem. Consider that the cyphertext is a program for an abstract machine called the cyphercracker which returns TRUE if a message is encoded otherwise FALSE. Such a system for determining message-ness could take an arbitrary amount of cpu time and no amount of static analysis could determine the return value quicker. Paul E. Baclace peb(a)procase.com

3 2

Re: The Halting Problem
by Marc.Ringuette＠GS80.SP.CS.CMU.EDU 12 May '93

12 May '93

peb> It occurred to me that determining whether a set of random bytes is peb> actually a crypto message could be reduced to the halting problem. I think I can prove this can't be done for most kinds of messages. For a wide range of cases we can know trivially that decryption is in NP. The line of reasoning is this: one definition of the class NP is the class of all problems whose solutions can be verified in polynomial time. So for any encryption method which allows the recipient to verify in polynomial time that his decryption is the only possible intended message, we know that the decryption problem is in NP. These conditions are met in the following cases: - Conventional public key encryption - Any cryptosystem with a short key and a space of allowable messages which is sparse enough that there's a low probability of two messages corresponding to the same ciphertext. This includes most cases in which a digital signature or CRC is added to the end of a message. -- Marc Ringuette (mnr(a)cs.cmu.edu)

1 0

Re: The Halting Problem
by Brian.Hawthorne＠East.Sun.COM 12 May '93

12 May '93

> The revelation here > (for me, anyway) is that if arbitrary crypto were made illegal, the > burden of proof would be on the prosecution which would have to crack > the message (at least partially). I believe the burden would actually be on them to crack the message entirely. Otherwise, you are applying arbitrary algorithms to what may be a random stream. If you get something comprehensible out, you have either partially cracked the message, or run into the British Museum problem (AKA 100 monkeys with typewriters).

2 1

The Halting Problem
by peb＠PROCASE.COM 12 May '93

12 May '93

It occurred to me that determining whether a set of random bytes is actually a crypto message could be reduced to the halting problem. Given this, it would be theoretically impossible to prove that an uncrackable message was indeed a crypto message. The revelation here (for me, anyway) is that if arbitrary crypto were made illegal, the burden of proof would be on the prosecution which would have to crack the message (at least partially). Paul E. Baclace peb(a)procase.com

2 1

Re: CALLER ID?
by stig＠netcom.com 12 May '93

12 May '93

> From: Satan <eaeu362(a)orion.oac.uci.edu> > Subject: Re: CALLER ID? > > and besides.. 800 numbers get your phone number the > same way your caller gets your number when you call collect > THEY ARE PAYING FOR THE CALL > they kinda have a right to know what they are paying for > You're confused or you miswrote: 800 number owners pay for your calls, people with caller ID boxes do not. So, do you think that the "privacy protecting 900 number" ($2/min) uses your number (remember that they DO have it) for privacy junk mailing purposes? Stig >> Jonathan Stigelman, stig(a)netcom.com, PGP key on request <<

1 0