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."

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."
> 
> 
> 
> 
>

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."

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`