From: tcmay@netcom.com (Timothy C. May)
Date: Wed, 18 Aug 93 13:40:43 PDT
To: Cypherpunks@toad.com
Subject: Crypto Protocols are Hard to Analyze
Message-ID: <9308182038.AA05720@netcom.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



Fellow Cypherdroids,

Crypto protocols are _hard_ to analyze! Speaking for myself, keeping the
many combinations and permutations of crypto terms, channels, spoofing
scenarios, and whatnot, straight is very confusing.

This should be no great revelation to any of you who've tried to closely
follow the protocols for digital cash (coins, coupons, certificates of
deposit, blinded notes, and even "S&H Green Stamps"). Analyzing and finding
flaws (often subtle) in cryptographic and digital money protocols is
time-consuming.

I'm currently trying to analyze a digital cash "coupon" system proposed by
Nick Szabo, and Hal Finney last night posted his initial analysis of the
"NetCash" scheme proposed recently. And the physical Cypherpunks meetings
have recently been dominated by fairly gory details ("gory" means highly
detailed and potentially confusing) of such new proposed systems as "Twain
(tm)," an anonymous remailer (and its associated pieces, like "Clemens
(tm)"...don't ask me to explain, as I got lost in the process!), and
"Digital Silk Road (tm)" (and its own associated pieces, "Joule (tm),"
"INDRA (tm)," etc.).

(Sidenote: I get worried when so many new protocols are already being given
names and being, to various degrees, "productized." Could this be a case of
"premature productization"?)

And anyone who looks at the "Advances in Cryptology-CRYPTO 'xx" books, the
books where the main crypto results are published (along with "EuroCrypt,"
"AusCrypt," and "AsiaCrypt"...mostly all published by Springer-Verlag in
their silver-grey paperback series), will quickly see the explosion of
complex protocols.


What's the connection with Cypherpunks?

After all, we all know this stuff is complex, so what's the big deal?

I argue that a group such as ours, devoted to actually exploring and
perhaps deploying modern crypto ideas, should try to *do something* about
the combinatorial explosion of concepts, terms, and confusing protocols.

It has been said about AI that 90% of the work is currently just
reinvention of terms of yore, with new ideas mainly being rehashes of
things invented 10 or 20 years earlier. My fear is that "digital money," to
name just one example, is showing the same sort of thing, with lots of new
terms for basic ideas, lots of complicated protocols which are (admittedly)
hard to analyze (to try to break, to try to spoof, to "game against"). Many
of these complex protocols simply _won't_ get analyzed in enough detail, if
only because there aren't enough of us to do the analyses.

(The obvious danger of _not_ analyzing a digital money scheme in enough
detail, with enough paranoid motivation, is that it gets deployed and then
broken by someone who knows how to break it--someone who has studied a
similar problem and knows the points of weakness, someone who is just
lucky, whatever. This could wipe out the developers, sow mistrust amongst
the Cypherpunks/crypto community, etc.)

Evidence that "protocols are hard to analyze" lies in the fact that only
recently has basic public-key crypto begun to spread...and there are still
lots of folks looking for weaknesses in PGP, for example. Almost nothing
using more recent protocols has shown up....no "Pretty Good Digital Cash,"
not "Pretty Good Digital Timestamping," etc. (Though our own remailers,
while very far from even Chaum's 1981 system, are interesting. Let's just
not think of them as "cryptographic" in any sense...they rely almost
totally on simple trust, a major cryptographic no-no.)

More complicated protocols, like the "Dining Cryptographers Problem"
(Chaum's paper on this should still be in the "soda" archives), are just a
_piece_ of what's needed for our longterm Cypherpunks future (which I
choose to call "crypto anarchy"), and yet analysis of it consumes
_hundreds_ of pages (see, for example, the Jurgen Bos Ph.D. thesis I
distributed a year ago at the first Cypherpunks meeting.)

Am I proposing anything constructive here?

First, I am not proposing limiting the universe of discourse on this List
in any way. Folks will always be free to say whatever they like, to use
whatever terms they wish. Second, I'm not pushing a particular agenda...at
least I hope I am not.

Here are some suggestions, some things to mull over.

1. Our archive site of papers and books is not available to many of the
folks attempting to develop new protocols. To pick one example: digital
money in all its various forms. The several proposals for digital cash
(digital postage, NetCash, S&H green stamps, Cayman Islands deposits, etc.)
are sometimes repeats of work done years ago--and shown to be flawed in
major ways. 

Workers in this field should of course plan to acquire _all_ of the
relevant papers, and probably should be at this year's "Crypto" conference
(too late now). There just is no excuse for trying to "reinvent the wheel"
when folks who are working full-time on something have already tilled the
field (to mix some metaphors). It may be true that gifted amateurs can
sometimes discover something the experts have not (after all, our fellow
Cypherpunk Whit Diffie was in some sense a "gifted amateur" in the mid-70s,
when nearly all "serious" cryptologists worked for the NSA), but it happens
fairly rarely. 

We need to encourage serious workers to obtain and read all of the
previously published material (the "Information Liberation Front," from
which little has been heard lately, can only scan and OCR a tiny fraction
of the papers that are relevant, and even then can't reasonably handle
equations and mathematical arguments).

2. We should agree on some terms, somehow, so that we're using a *common
language* and not wasting huge amounts of time trying to deduce what Alice
means by "return receipt" versus what Bob means when he uses the same term.
(For example, Eric Messick calls his things "onions," suggesting multiple
layers of "return postage guaranteed" envelopes. This may be a great idea,
and even a great name (which we may all be using in 5 years), but it is
potentially confusing, I think you'll agree.)


(Formal crypto papers often use their own terminology, and those of us who
read the papers have to convert from, say, "blobs" (a Chaum/Brassard term),
to the terms favored by others. A few "Schelling points" for terms have
appeared, usually with some groundbreaking or widely read paper, but
cryptologists continue to reinvent their own terms, sometimes because they
haven't understood the work of others, sometimes because of "NIH.")

3. The lack of a FAQ is not really the issue, as the issues I'm talking
about here go somewhat deeper than nearly any FAQ will ever go. Possibly a
much-expanded "Glossary" (also in the "soda" archives) could be used to
ensure more of us are using the standard terms.

4. I recommend we _not_ spend a lot of time at Cypherpunks meetings on
detailed protocols, as these are notoriously hard for people to follow,
except in broad outlines. People "space out" on the details and teh devil's
in the details. 

Rather, more detailed written papers are the best way, I think, to convey
complicated ideas. Written papers force the writers to more carefully state
their assumptions, their reliance on previous works, and to then more
carefully work through their line of reasoning. Readers who are interested
can then work through the papers in as much detail as they wish. Sometimes
it takes many hours to work through a protocol. For example, I must've
spent 10 hours going through Chaum's DC-Net paper, drawing pictures, going
back to his 1981 paper on "mixes," and generally reading and rereading.
(Then I spent even more time explaining it in a series of essays to the
Extropians mailing list, before this list existed.)

5. Eric Hughes and I toyed with the idea of creating a "protocol analysis
language," or at least a toolkit for describing and diagramming protocols
(inspired by the Chaum-school "triangle" diagrams, which place the
"Customer," the "Shop," and the "Bank" in a triangle and then analyze who
knows what, where the bits flow, who can prove what, etc.).

Here's just the most basic and initial look at such a diagram:


                   Customer
                   /      \
                  /        \           (I won't add all the other stuff)
                 /          \
               Shop---------Bank


(The "nouns" then have channels, actions ("verbs"), etc. associated with
them. The digital money protocols are themselves complicated, involving
"bit commitment," "blinding," and the like. And then there are the
complications of any of these entities attempting to "break" the system, to
steal money, to spend a digital token more than is authorized, to trace the
flow of money, etc. Collusion, spoofing, etc. It gets confusing very fast.)


Nothing has so far come of this idea, but it seems to me to be a shame that
we're just drawing chicken marks on paper or on whiteboards (and losing
most of the audience along the way, at least in terms of the all-important
details). Complicated protocols--and the digital money constellation of
ideas is just one--demand more powerful tools. 

(Speculatively, what I would someday hope to see is a kind of "Protocol
Compiler," with functional specs (possibly written in a very higl-level
language) transformed/rewritten to the best set of protocols available. The
building blocks would be various forms of encryption, of reputations, of
blinding, and so on. Each of the building blocks could be analyzed
separately and improved upon....and probably bought from specialized
developers. I know of no work along these lines, though. But I would not be
at all surprised to find that some groups are doing something like
this--the combinatorial explosion of possibilities makes hand-analysis
problematic.)

Well, enough for now. Let me know what you think.

With lots of new ideas for digital cash, remailers, mixes, digital betting
schemes, coupons, postage, data havens, digital voting, and all the rest,
we'll soon be drowning in protocols none of us have the time--or specific
expertise--to analyze.

Right now the crypto enthusiasts and amateurs are still stuck at the
"Here's my idea for a new cipher...can you break it?" level, not even
having reached the level of proposing new public key systems. We are
beginning to see proposals on the Net for new digital money systems
(NetCash being the most recent example). Over the next several years, there
may be an explosion of these new proposals. Analyzing and quickly debunking
them (when they need debunking, as most do...I am not saying this in a
disdainful way, just noting reality....nothing is gained by the adoption of
weak schemes) will be a challenge.

Perhaps one Cypherpunks goal could be to maintain a publicly accessible
database (in hypertext, even, using the World Wide Web or similar) of
published techniques, of how to break or spoof them, of tips and tricks,
and so on. (Yes, I am interested in working on something like this.)

Best wishes,


-Tim May


--
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@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
Note: I put time and money into writing this posting. I hope you enjoy it.