That 70's Crypto Show (Remailers, science and engineering)

[Tim May]

At 3:56 AM -0500 12/28/00, dmolnar wrote:
>
>I'm in the midddle of composing a reply to Tim's message (which is getting
>bigger every time I sit down to finish it, ominously enough).

Sounds good to me!

>One of the
>points that has popped into my mind so far is that while we've had
>academic crypto research since the 80s, thanks to Rivest, Shamir, Aldeman,
>Diffie, Hellman, and others willing to defy the NSA, we have _not_ had a
>similar tradition of commercial cryptography - or at least, not a
>tradition of companies obtaining money for cryptographic *protocols* as
>opposed to ciphers.

Probably the most basic motivation Eric Hughes and I had for calling 
together a bunch of Bay Area folks in '92 was because, in a 3-day 
series of talks we'd had earlier in the spring, we concluded that a 
lot of academic crypto was ripe for conversion into "building blocks."

(Building blocks, protocols, modules, libraries...)

Well, we were half-right.

>
>It seems to me that it took a long while for people to even recognize that
>there was more to cryptography than secrecy. Maybe it happened quickly in
>academia, but it doesn't seem to have filtered out quickly (and then
>there's still the chilling effect from export controls). This is one of
>the reasons why the early Cypherpunk work is so damn important -- it
>showed the amazing, powerful things you can do given cryptography and a
>little cleverness, and it did so to a (comparatively) wide audience!

Thanks. It was an amazing time. It was clear that "uncoerced 
transactions" would be possible by combining "untraceable 
communications" (mixes, remailers, pseudonyms) and "untraceable 
payments" (pure Chaumian digicash). And that all manner of related 
things would come from this.

Frankly, the early work on Magic Money (by Pr0ductCypher) _could_ 
have been the extended to give a Pretty Good Digital Cash, at least 
for experimental markets, but it wasn't.

And as David notes, the commercial sector was focused on fairly 
mundane straight crypto.

>...
>Before Tim jumps on me, yes, I know there were early electronic markets,
>and yes, electronic trading was around before the Web. Yes, these could
>have been viable markets for digital cash, fair exchange protocols,
>whatever. Even electronic voting could and did get started earlier
>(though not using cryptographic techniques AFAIK) I do not dispute
>this! It simply seems to me that the climate today has the possibility of
>demand for such protocols (and more) on a wider scale than previously.

I won't jump on you. Those early electronic markets, like Phil 
Salin's "AmIX" (American Information Exchange) were failures. AmIX 
desperately needed the Web, or at least free connect time. (We 
pioneers were paying $12 an hour, or somesuch, IIRC, to dial in to 
Palo Alto. This was circa 1990.)

The Extropians list even ran "reputation markets" as a viable 
experiment, circa 1993-94. Some guy in Utah, IIRC, implemented it in 
Perl. (Precursors to Firefly and suchlike.)

But it took the Web to create a proper substrate.



>
>>  of crypto out of math and CS areas and into engineering.
>>  Mojo Nation, for example, is partly interesting because it's not just
>>  Yet Another Encrypted Music Sharing Product - it's mixing the
>>  crypto with economic models in ways that are intellectually complex,
>>  even if they're somewhat at the hand-waving level
>>  rather than highly precise.
>
>Maybe it will force smart people to move the mix from the hand-waving
>level to something highly precise. Insh'allah.

I hear the focus of Mojo Nation is shifting from "better living 
through piracy," to something more mundane involving deals to deliver 
video content. If so, much of the motivation to be absolutely robust 
will go away. Sad, if true.

(Mojo folks feel free to jump in to set me straight...)


>
>>  >On the other hand, we can oppose this to the fact that we
>>  >have a bunch of remailers, and they seem to work.
>>  >They may be unreliable, but no one seems
>>  >to have used padding flaws to break a remailer, as far as we know.
>  >
>>  Arrgh!  Dave, just because nobody's known to have broken them
>>  doesn't mean that nobody's succeeded in breaking them
>>  (without us knowing they've succeeded),
>
>[snip a well-deserved beating]

I think Bill was a bit harsh. There are some _economic_ issues 
involved, as usual. So long as the "value of what is being sent 
through remailers" is LESS THAN "the cost of subverting remailers," 
they will tend not to be subverted.

There is an interesting trade-off in three dimensions between "value 
of material" and "cost to send it" and "bandwidth/latency." A 
remailer network is pretty good at sending small packets (e-mails) 
through N hops, where N can be quite large, so long as a latency of ~ 
hours is acceptable, which it usually is. And at very low cost. 
However, sending Web page queries and responses through is another 
matter. ZKS believes that "untraceable surfing" is an important 
business model...and for this sort of app they need PipeNet-like 
bandwidth. And so on. I wish e-mail allowed us to draw pictures.

IMO, any analysis of breaking mixes should be heavily-centered around 
economic analysis. This is not as heretical as it sounds. Game theory 
of both main flavors--matrix game theory of the Von 
Neuman/Morgenstern/Nash type and combinatorial game theory of the 
Conway/Berlenkamp/Guy type--often involves payoffs, costs, and other 
economic issues. IMO, there is no reason crypto cannot easily co-opt 
such approaches. At the most trivial level, work factor is a 
fundamentally economic issue. For mix-nets and other Cypherpunkish 
things, economic analysis is everything.

>
>Well, this is what I get for trying to moderate myself. Everything you say
>is correct - of course. I actually agree with you! I mentioned this
>because I wanted to avoid playing the part of a "theoretical Cassandra,"
>which is something I do too often. (In fact, if I'm not mistaken, that's
>part of what Tim's response about different adversary models attempts to
>speak to - the fact that traditional cryptographic models assume a
>maximally powerful adversary, while we might want a finer grained
>hierarchy of adversaries and their effects...)

Yes, as noted above.

Pure crypto is often treated as a pure math exercise, akin to finding 
"existence" proofs of the sort we see standard problems (travelling 
salesman, Hamiltonian cycle, etc.).

But crypto is really more of an N-party game, with Alice and Bob (and 
maybe others) making moves and countermoves. (This is one reason many 
such games are in an important sense "harder" than being merely 
NP-complete.)

The moves and countermoves, and the hidden knowledge (*), are similar 
to the evolutionary process of building and attacking castles and 
other fortifications. Siege engines, better walls, traps, moats, 
economic isolation, etc.

(* A standard assumption--it probably has a name that I have 
forgotten--is that the attacker of a cipher has complete knowledge 
except for the key. That is, he can take the cipher back to his lab 
and attack it with everything he's got except for the key itself. 
This is sort of the Basic Modern Assumption. Security through 
obscurity is deprecated (because, practically, it falls long before 
the other attacks). However, even in crypto we find things like 
"tamper-responding systems," which alter the equation: there is now a 
cost in attacking such a system, as the adversay _knows_ the attack 
is occuring and may take steps in response. Again, N-party games.)

Pardon this rambling above. I expect Dave and Bill and some others 
know where this is going. Really, this is a call for a "new paradigm" 
in crypto. More later.


--Tim May
-- 
Timothy C. May         tcmay at got.net        Corralitos, California
Political: Co-founder Cypherpunks/crypto anarchy/Cyphernomicon
Technical: physics/soft errors/Smalltalk/Squeak/agents/games/Go
Personal: b.1951/UCSB/Intel '74-'86/retired/investor/motorcycles/guns