Re: Why is cryptoanarchy irreversible?
At 12:29 AM 11/8/1996, Jim McCoy wrote:
Peter Hendrickson writes: [...]
Get a warrant, search my system, find nothing but a bunch of applications and a collection of risque (but definitely legal) pictures which I exchange with a few friends. You may suspect that when the images are concatenated in a particular way the low-order bits form a stego filesystem but no one will be able to prove it in court.
Are you concatenating these images by hand? If so, the level of entropy is probably low enough to recover the information through brute force methods or you are hiding a very small amount of information.
I hide the relatively small amount of data within a very large amount of data which makes it impossible to find. Data from analog sources, like the "real world" (images, sounds, etc) is noisy. This is a fact of life. Because this data is noisy I can hide information in the noise. As long as the information I am hiding maintains the same statistical properties of noise it is impossible to pull the information out of the data file unless you have the key. If I am paranoid enough I can make this key impossible to discover without a breakthrough in factoring.
Where will you keep your secret key? Remember, when they go through your house they bring 20 young graduates from MIT who are just dying to show how clever they are and save the world at the same time.
This is the essence of steganography and the nature of signal and noise are fundemental principles of information theory.
The concept of noise is not all that well defined, however. There is no way to look at a signal and say "this is all noise." Sometimes physical theories may lead you to believe that it is all noise. That is fine for many applications, but when becomes less convinced of things if the consequences are severe.
If you are not doing it by hand, you own terrorist software and will pay the price.
Ah yes, terrorist programs like cat and perl and operating systems like Linux which contain a loopback filesystem that I can hook a perl interpreter into at compile-time (which is enough for me to rewrite the program from scratch each time if necessary, unless things like math libraries are also outlawed on computers :) I think that the crypto concentration camps are going to be very crowded places.
Can you elaborate on this? I am curious to know exactly what you are going to keep in your head and what goes on the disk. Please post the Perl code that you would type in from scratch every time. Peter Hendrickson ph@netcom.com
As I said in my "Nightmare on Crypto Street" piece, it seems that Peter counters every one of our counterarguments with some variant of "won't matter--they'll have a dozen agents and 20 MIT graduates looking for evidence." Or, "won't matter, the Bill of Rights will be suspended for the duration of the Emergency." Well, it's hard to argue with such points. On a few plausibility points, or on technical points (as with the meaning of "noise," for example), there's still a basis for a debate. At 9:02 AM -0800 11/8/96, Peter Hendrickson wrote:
Where will you keep your secret key? Remember, when they go through your house they bring 20 young graduates from MIT who are just dying to show how clever they are and save the world at the same time.
Unlikely they'll be able to find or marshall 20 MIT grads. Didn't happen when they raided Steve Jackson Games as part of Operation Sun Devil and hauled away all of his equipment. It probably _did_ happen with the raid on the Unabomber's cabin, except probably the numbers of MIT grads were fewer and their specialties were in other areas. Where do you keep your secret key? On your disk. However, one's PGP _passphrase_ is what is really important (though both are important). Without the passphrase, the secret key is worthless. Now of course some people write down their passphrases on Post-It notes, etc., and certainly keystroke capture programs may be running (inadvertently, deliberately, or even via previous blackbag job plants, as many of us have noted over the years). However, a properly memorized passphrase, of sufficient length and entropy to make exhaustive search impractical, and proper "crypto hygiene" will go a long way toward making such raids ineffective. And there are several reports of such raids turning up PGP-encrypted files which the cops and investigators have been unable to crack. PRZ speaks of being asked to help, and some others here on this list have mentioned similar situations. The Church of Scientology has been seeking "PGP experts" to help them read some files they believe may help them get someone punished. Basically, without the passphrase, not much can be done. (I expect the "crypto hygiene" issue to get better, not worse. It is likely that "crypto dongles" and PDAs will soon drop in price enough such that one can store one's private key on a dongle, smartcard, or PDA and enter the passphrase with a keypad built in...this dramatically cuts the risk that a keystroke capture program is being run, or that a TEMPEST van is trying to capture the keystrokes (LCD and low-power CMOS circuitry don't generate a helluva lot of Van Eck radiation :-} .) And there are the familiar low-tech versions of protecting some keying material, such as "rat lines" into neighboring apartments. A few years ago we talked about how hacker-friendly buildings could easily be wired up with fibers and LANs such that files and key material were scattered in multiple sites, with various "dead man switches" to shut off access should a raid occur. Search warrants would of course be problematic (and the Bill of Rights frowns on blanket searches for, say, 40 apartments on the suspicion that a needed file may be on the hard disk of a machine in one of the 40 apartments). Finally, on this point, "perfect forward secrecy" is possible with several crypto protocols (notably, Diffie-Hellman). There is no stored keying material left behind. Adapting this approach for other uses is likely to be more popular in the future. (I certainly agree that text versions of "How to Make Sarin" are always going to be incriminating in a legal case, but crypto is not the main issue.)
This is the essence of steganography and the nature of signal and noise are fundemental principles of information theory.
The concept of noise is not all that well defined, however. There is no way to look at a signal and say "this is all noise." Sometimes physical theories may lead you to believe that it is all noise. That is fine for many applications, but when becomes less convinced of things if the consequences are severe.
Actually, you've got it turned around. What is really hard to do, and what is needed by a prosecutor seeking to prove a case, is to prove "this is *not* noise." As we've talked about for several years, storing and sending lots of noise is a Good Thing. "Yes, FBI Agent Mulder, that is a noise packet I sent." The claim that people will be thrown in prison for storing apparently-random noise on their disks, or even sending it in their writings, is ludicrous. Not so long as the Bill of Rights stands. Given the "Nightmare on Crypto Street" scenario of mass pogroms and suspension of the Constitution, maybe not. But I find this scenario implausible and not really worth worrying about overmuch. --Tim May "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
Mr. May said:
years). However, a properly memorized passphrase, of sufficient length and entropy to make exhaustive search impractical, and proper "crypto hygiene" will go a long way toward making such raids ineffective.
A very basic question then: What _would_ be a passphrase of sufficient length and entropy? I would assume that the phrase "Off we go, into the while blue yonder" would not be sufficient, but what about "0ff they went, in'ta the black viod"? I would guess that either would be difficult to out right guess, but the second would be considerably less likely. Not as unlikely as "KIB&^%(*h89hgv&*hjV6*ibHF&90n", but a hell of a lot easier to remember. It has been several months since I read the PGP users guide, and I don't remember any discussion of that in it, but I could be wrong. Petro, Christopher C. petro@suba.com <prefered for any non-list stuff> snow@smoke.suba.com
Tim May & I had a conversation about this in which Tim posted the great analogy of searching galaxies in the possible passphrase space. The thread covered the question pretty well. Adam (Tim, do you have a copy of your post? I can't think of the right search terms for Altavista) snow wrote: | A very basic question then: | | What _would_ be a passphrase of sufficient length and entropy? | | I would assume that the phrase "Off we go, into the while blue yonder" | would not be sufficient, but what about "0ff they went, in'ta the black viod"? | | I would guess that either would be difficult to out right guess, but the | second would be considerably less likely. Not as unlikely as | "KIB&^%(*h89hgv&*hjV6*ibHF&90n", but a hell of a lot easier to remember. | | It has been several months since I read the PGP users guide, and I don't | remember any discussion of that in it, but I could be wrong. -- "It is seldom that liberty of any kind is lost all at once." -Hume
At 11:15 PM -0500 11/15/96, Adam Shostack wrote:
Tim May & I had a conversation about this in which Tim posted the great analogy of searching galaxies in the possible passphrase space. The thread covered the question pretty well.
Adam
(Tim, do you have a copy of your post? I can't think of the right search terms for Altavista)
The name of my post was "Passwords as Galaxies." Alas, it does not show up in an Alta Vista search, so it's probably not in the few archived periods still available (*). The approximate date was mid-June 1996. I know this from some followup posts I still have. Unfortunately, my increasingly twitchy Macintosh--an architecture that appears to be sinking under the weight of inconsistent versions, extensions, and other such cruftiness--has dropped a lot of chunks of my Eudora archives. My backups may have the missing sections, but I don't have time to sort through them now. Someone else should have it. Mid-June. "Passwords as Galaxies." (* And speaking of the Cypherpunks archives, has anyone heard _anything_ from Todd Masco about progress on his site? His Web page, http://www.hks.net/cpunks/index.html, just reports the same old news: ------------ "March 18, 1996 The cypherpunks and coderpunks pages will be unavailable for the next couple of days as we switch over to a new line. We apologize for any inconvenience this might cause. June 06, 1996 Not to worry, we know the archives are still down. Just a bit longer, Please be patient." -------------- Someone alluded to threats by large newspapers to prosecute Copyright violations (that is, the archive site perpetuates copyright violations, and Web search engines compound the seriousness) as being a reason the archive have not come back up. Anyone know if this is really true? Todd, are you still reading us? --Tim May "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
At 12:49 AM -0800 11/16/96, Lucky Green wrote:
I think it was "Passwords are galaxies in hyperspace". I may be wrong. Either way, this was an excellent tread.
Dale Stimson found it, and sent it to me. It's included below. It dated from June of 1995, not 1996. I don't know why I thought it did. From: tcmay@netcom.com (Timothy C. May) Message-Id: <199506081711.KAA09665@netcom8.netcom.com> Subject: Passwords as Galaxies in Hyperspace To: sandfort@crl.com (Sandy Sandfort) Date: Thu, 8 Jun 1995 10:11:19 -0700 (PDT) Cc: cypherpunks@toad.com In-Reply-To: <Pine.SUN.3.91.950608081241.3725A-100000@crl12.crl.com> from "Sandy Sandfort" at Jun 8, 95 08:41:22 am Sender: owner-cypherpunks@toad.com Sandy Sandfort wrote:
I've never really questioned the statements that knowledgeable C'punks have enunciated about passphrase entropy. I've just accepted the "rules" on faith. I choose long "nonsense" passphrases with quirky spelling, characters and punctuation.
Adam Shostack just gave a good response, based on how programs like "crack" will try various substitutions on names, common phrases, etc. I want to give an explanation that is more "hyperdimensional" (you'll see what I mean in a moment).
The question I have, is "quessability" all that important a consideration? For example, let us say I started out with the following phrase as a "seed":
the quick red fox jumped over the lazy brown dog
To convert it into a passphrase, what if I only changed "dog" to "d0g"? Though it would obviously be easy for me to remember, I don't see how it would be any easier for an attacker to guess this passphrase than it would be if the passphrase were an equally long string of randomly generated characters. The
Because a program can store the most common names and phrases and then generate a whole bunch of one-character or one-word variants. That is, the phrase above can be stored and then perhaps 1000 variants can be tried...missing characters, "blue" instead of "brown," "snazzy" instead of "quick," etc. This sounds like a lot of variants to try, but remember that we're talking about a search space that is 10^75 bytes or higher! Anything that helps reduce this search space is useful.
reason I (I'm sure naively) think this is so, is that to the best of my understanding, passphrases are all or nothing--you have to guess it 100% correctly or it doesn work. Even if an attacker tries my "seed" because it is a common typing practice, it hardly puts him any closer to guessing which one of the zillions of ways I may have modified that phrase, if indeed, I used that phrase at all.
Oh, but it puts him a _lot_ closer!
So I guess what I'm asking is: if my passphrase is very long, and I add at least some randomness, is the fact that my original famous quote might be tried as part of a "Bartlet's attack, all that much of a threat?
Imagine all passwords and passphrases (same thing, actually) occupying a high-dimensional space...I won't get into what the dimensions are here--see any good book on information theory, especially Pierce's "Symbols, Signals and Noise." The "points" in this space are the passwords/phrases. With a old-generation 8-character max on passwords, for example, this space has something like 26^8 = 2 X 10^12 points in it, if only single-case alphabetic characters are used. If both upper- and lower-case characters can be used and standard punctuation marks can be used, the space explodes in size to roughly 75^8 = 10^16 points. In this space, there are "galaxies" or "clusters" of points surrounding such points as "sandy" and "tim." Smart cracking programs will start with thousands or even millions of these points and then explore the "nearby" variants, as these nearby variants are what people will often pick as passwords, thinking they are "outsmarting" the computers! Extending this to 30-character or even 50-character pass _phrases_ has identical math, except the numbers are _much_ larger, and the "universe" is much vaster. Somewhere in that universe is the phrase "the quick red fox.....", surrounded by a large cloud of points a short Hamming distance away: "the quick red fob...," "the quick red fux...," etc. And in that same galaxy, albeit a little furhter away, are the variants on entire _words_. Still further out from the "galactic core" are such phrases as "the quickest red cat...." Searching in these galaxies still beats searching the entire space. In any case, if one is to try searching the entire space, starting in the galaxies makes more sense. (In practice, an entire 10^75 point space will not be searched by brute force, I am sure. And, in practice, I have no idea how far out in the "arms" of the "galaxies" the NSA's supercomputers will venture....) A question one might ask is what gives "shape" to this universe? Why do I say there's a "galaxy" of points surrounding "sandy" or "the quick red fox...."? Why not a galaxy around "g*E@ks)hc"? This gets to the culture-dependent aspects of "randomness" and "entropy." Fact is, just as Sandy thinks starting with "the quick red fox..." or some other easily memorizable phrase is a good strategy, so too will computers. All a matter of entropy. I hope this explanation helps. I'm partial to geometrical and space-oriented descriptions, and reading Pierce's explanation of Shannon's Theorem in terms of n-dimensional spaces was one of the highpoints of my high-school experience, lo those almost 30 years ago. (The n-dimensional model neatly explains a lot of things, including signal-to-noise ratios, the effects of signal power, correlation between signals, and error-correcting codes. Great stuff!) --Tim May -- .......................................................................... Timothy C. May | "I am not now, nor have I ever been, a member of tcmay@netcom.com | a militia group." Corralitos, CA | --Tim May's statement before the 1995 Hearings | of the House Un-American Activities Committee The "Crypto Anarchy" sig will soon return. "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
I think it was "Passwords are galaxies in hyperspace". I may be wrong. Either way, this was an excellent tread. -- Lucky Green <mailto:shamrock@netcom.com> PGP encrypted mail preferred Member JPFO. "America's Aggressive Civil Rights Organization" On Fri, 15 Nov 1996, Timothy C. May wrote:
At 11:15 PM -0500 11/15/96, Adam Shostack wrote:
Tim May & I had a conversation about this in which Tim posted the great analogy of searching galaxies in the possible passphrase space. The thread covered the question pretty well.
Adam
(Tim, do you have a copy of your post? I can't think of the right search terms for Altavista)
The name of my post was "Passwords as Galaxies." Alas, it does not show up in an Alta Vista search, so it's probably not in the few archived periods still available (*).
The approximate date was mid-June 1996. I know this from some followup posts I still have. Unfortunately, my increasingly twitchy Macintosh--an architecture that appears to be sinking under the weight of inconsistent versions, extensions, and other such cruftiness--has dropped a lot of chunks of my Eudora archives. My backups may have the missing sections, but I don't have time to sort through them now.
Someone else should have it. Mid-June. "Passwords as Galaxies."
(* And speaking of the Cypherpunks archives, has anyone heard _anything_ from Todd Masco about progress on his site? His Web page, http://www.hks.net/cpunks/index.html, just reports the same old news:
------------ "March 18, 1996
The cypherpunks and coderpunks pages will be unavailable for the next couple of days as we switch over to a new line. We apologize for any inconvenience this might cause.
June 06, 1996
Not to worry, we know the archives are still down. Just a bit longer, Please be patient." --------------
Someone alluded to threats by large newspapers to prosecute Copyright violations (that is, the archive site perpetuates copyright violations, and Web search engines compound the seriousness) as being a reason the archive have not come back up. Anyone know if this is really true?
Todd, are you still reading us?
--Tim May
"The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
Peter Hendrickson <ph@netcom.com> writes:
I hide the relatively small amount of data within a very large amount of data which makes it impossible to find. Data from analog sources, like the "real world" (images, sounds, etc) is noisy. This is a fact of life. Because this data is noisy I can hide information in the noise. As long as the information I am hiding maintains the same statistical properties of noise it is impossible to pull the information out of the data file unless you have the key. If I am paranoid enough I can make this key impossible to discover without a breakthrough in factoring.
Where will you keep your secret key? Remember, when they go through your house they bring 20 young graduates from MIT who are just dying to show how clever they are and save the world at the same time.
Keep your secret key in your head.
This is the essence of steganography and the nature of signal and noise are fundemental principles of information theory.
The concept of noise is not all that well defined, however. There is no way to look at a signal and say "this is all noise." Sometimes physical theories may lead you to believe that it is all noise. That is fine for many applications, but when becomes less convinced of things if the consequences are severe.
Your plausible deniability has to get quite low before it will stand up as "proof" in court. Your real challenge is keeping your stego programs safe. Boot strapping a stegoed encrypted file system while leaving no stego code lying around isn't that easy.
If you are not doing it by hand, you own terrorist software and will pay the price.
Ah yes, terrorist programs like cat and perl and operating systems like Linux which contain a loopback filesystem that I can hook a perl interpreter into at compile-time (which is enough for me to rewrite the program from scratch each time if necessary, unless things like math libraries are also outlawed on computers :) I think that the crypto concentration camps are going to be very crowded places.
Can you elaborate on this? I am curious to know exactly what you are going to keep in your head and what goes on the disk. Please post the Perl code that you would type in from scratch every time.
My specialty :-) rc4 in C: #define S,t=s[i],s[i]=s[j],s[j]=t /* rc4 key <file */ unsigned char s[256],i,j,t;main(c,v)char**v;{++v;while (s[++i]=i);while(j+=s[i]+(*v)[i%strlen(*v)]S,++i);for( j=0;c=~getchar();putchar(~c^s[t+=s[i]]))j+=s[++i]S;} rc4 in perl: #!/usr/local/bin/perl -0777-- -export-a-crypto-system-sig -RC4-3-lines-PERL @k=unpack('C*',pack('H*',shift));for(@t=@s=0..255){$y=($k[$_%@k]+$s[$x=$_ ]+$y)%256;&S}$x=$y=0;for(unpack('C*',<>)){$x++;$y=($s[$x%=256]+$y)%256; &S;print pack(C,$_^=$s[($s[$x]+$s[$y])%256])}sub S{@s[$x,$y]=@s[$y,$x]} The other problem I see is that if you have a stego file system in an audio file, your disk writes are going look strange. The inaccuracy of disk head placement, is going to ensure that someone with the know how will be able to copy off the last dozen pieces of data you wrote. If they are all the same data with the exception of the LSB, it's goint to look fishy. Solid state storage devices are better. Adam -- print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<> )]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
participants (6)
-
Adam Back -
Adam Shostack -
Lucky Green -
ph＠netcom.com -
snow -
Timothy C. May