Crypto Protocols are Hard to Analyze

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.

Tim May: 
> Crypto protocols are _hard_ to analyze! 

Agreed, alas.

> I'm currently trying to analyze a digital cash "coupon" system proposed by
> Nick Szabo,

Whoa nelly!  "S&H greenstamps" and another recent idea I've bounced
off Tim refer to a LEGAL "protocol".  S&H greenstamps are
"coupons" that can be used to "win" a wide variety of items from
several participating companies; they are not just coupons good for 
discount on a specific item or the products & services of a specific 
company ("Disney Dollars").  S&H greenstamps got into some legal hot 
water for being too close to a privately issued currency, but 
nevertheless they are still around.  S&H greenstamps make a good legal 
"edge case".

From an object-oriented point of view, "E-greenstamps" inherit
digital cash and add legal structure.  Here I am assuming that 
E-greenstamps or other business/legal manifestations of digital cash can 
be implemented with Chaum's protocol, providing "Pretty Good Digital 
Cash" in the cryptographic sense.   The "Chaum off the shelf" 
assumption.  If there are holes in Chaum's scheme, or major problems 
with implementing it in software, I'd like to hear more, but "S&H 
greenstamps" concept doesn't address software security issues.

> "premature productization"?)

I think it's good to discuss business and legal issues -- cf.
the excellent thread on methods of converting physical to/from digital
cash.  If we think the work ends with implementing a 
good cryptographic protocol, we are sadly mistaken.  Perhaps that's 
where the work of "cypherpunks" ends, but I have a broader vision of
crypto-anarchy that covers the legal, business, and in general
social issues as well.  Any group that wants to seriously
deploy cryptography in the real world has to discuss these as well.
And indeed we do -- does PGP infringe on patents, is it proper
for a remailer operater to read or record what goes through his system, 
etc.  

Crypto-anarchy will really take off when the (real, spendable) money
starts flowing.   Thus we should examine a wide variety of business
concepts.  The "speculative business plan" is a great way to do this.
Of course cypherpunks are mostly hackers, and we will 
concentrate on the hacking -- but before crypto-anarchy emerges,
the legal and business problems (eg not driving off customers with
complex or "shady" operations) also have to be solved.  

We do need to be more clear on when we are talking about cryptographic 
protocols ("digital cash"), legal structures ("S&H greenstamps"), and 
business concepts ("commercial remailer"). 

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

I'd love to see some digicash papers on soda.  I also agree on the
need for standardizing terminology in the field of cryptography
and related protocols for remailers, digital cash, etc.  Your
concept of a "Protocol Compiler" to enable testing of new
concepts for anon remailers, digicash, etc. is intriguing. 
We have already started a "tricks database" with the Word Perfect
crypto-cracker on soda; we need to expand that.

Alas, there may be strong incentive for businesses to put hype
before strong crypto substance.  In response, we need to pursue 
the following two activities -- eventually, perhaps creating a separate 
organization for each:

* A "cracker's guild" to break weak cryptography and publicize
the cryptanalysis algorithms (cf. the Word Perfect crypto cracker),
forcing the weak crypto off the market.  For example, if 
NetCash was deployed this organization would crack it.  This
organization might be funded anonymously by those selling strong 
crypto (who have an incentive to debunk their competitor's hype).

* A formal Crypto Auditing Agency that would verify the algorithms
and protocols were secure, without revealing trade secrets.
My next statement may cause hisses & boos, but I think the recent
Crypto-Auditing of Clipper by Denning and other eminent 
cryptologists will be a model widely applied in the commercial
computer security business.   The auditors should be 
able to examine the source and run the programs without revealing
trade secrets.

Nick Szabo				szabo@netcom.com

> * A "cracker's guild" to break weak cryptography and publicize
> the cryptanalysis algorithms (cf. the Word Perfect crypto cracker),
> forcing the weak crypto off the market.  For example, if 
> NetCash was deployed this organization would crack it.  This
> organization might be funded anonymously by those selling strong 
> crypto (who have an incentive to debunk their competitor's hype).

The person who built the standard "network license manager" for Unix
(flexlm) has offered us cypherpunks access to the protocol if we'll
try to crack it.

> * A formal Crypto Auditing Agency that would verify the algorithms
> and protocols were secure, without revealing trade secrets.
> My next statement may cause hisses & boos, but I think the recent
> Crypto-Auditing of Clipper by Denning and other eminent 
> cryptologists will be a model widely applied in the commercial
> computer security business.   The auditors should be 
> able to examine the source and run the programs without revealing
> trade secrets.

The auditing may indeed be duplicated.  By marketing departments, and for
the same reason as the Denning auditing -- marketing.  Solely.

There is no way that the selected group of people could crack a 
half-reasonable cryptosystem in a few weeks.  Real Cryptanalysts spend
months and years working on cracking cryptosystems, and none of the
panelists was a Real Cryptanalyst.  We had all the details of DES,
and it took 15 years to make a dent in it.

But they fooled you -- and maybe a lot of other people -- so there *is*
a function for such review panels.  Sponsoring one is a way to convince
innocent spectators who don't know better.  Marketing.

	John
	Marketing Dept, Cygnus Support

>There is no way that the selected group of people could crack a 
>half-reasonable cryptosystem in a few weeks.  Real Cryptanalysts spend
>months and years working on cracking cryptosystems, and none of the
>panelists was a Real Cryptanalyst.  We had all the details of DES,
>and it took 15 years to make a dent in it.

I knew one of the panelists, Ernie Brickell, when we were both at
Bellcore.  Of the five, he's probably the only one with claim to the
term Real Cryptanalyst, as we usually define the term (someone with a
proven track record in cracking real cryptosystems.)  He is generally
credited with putting the final nail into the coffin of the knapsack
public-key cryptosystem.  I was very disappointed when I heard that he
had agreed to let himself be used for such a crass political purpose
as the Clipper Committee.

Other than this minor point, your statement is absolutely correct.
The best known Real Cryptanalyst in civilian life, Adi Shamir, wasn't
involved, and even he took fifteen years to make the first dent in
DES.

Phil

> There is no way that the selected group of people could crack a 
> half-reasonable cryptosystem in a few weeks.  Real Cryptanalysts spend
> months and years working on cracking cryptosystems, and none of the
> panelists was a Real Cryptanalyst.  We had all the details of DES,
> and it took 15 years to make a dent in it.

That's one of the strongest points in favor of crypto in wartime, for example.
The usefulness of a cryptosystem is not just a function of its resistance to
attack, it is also a function of how long it *has* to resist attack.  For
example, if the Nazis had broken a message regarding D-Day, encrypted with
a cipher in such a way that if the message were compromised it wouldn't
compromise the system itself, it wouldn't matter when they broke it, as long
as it was after June 4, 1944.  After that time, it's useless, and many
messages during tactical operations have an effective lifetime of days, if
not hours.
-- 
Ed Carp, N7EKG			erc@apple.com			510/659-9560
                            anon-0001@khijol.uucp
If you want magic, let go of your armor.  Magic is so much stronger than
steel!        -- Richard Bach, "The Bridge Across Forever"

In the interests of keeping the volume of postings down, I'll say only
a few words about Nick Szabo's many good points:

> > I'm currently trying to analyze a digital cash "coupon" system proposed by
> > Nick Szabo,
> 
> Whoa nelly!  "S&H greenstamps" and another recent idea I've bounced
> off Tim refer to a LEGAL "protocol".  S&H greenstamps are
> "coupons" that can be used to "win" a wide variety of items from
> several participating companies; they are not just coupons good for 
> discount on a specific item or the products & services of a specific 
> company ("Disney Dollars").  S&H greenstamps got into some legal hot 
> water for being too close to a privately issued currency, but 
> nevertheless they are still around.  S&H greenstamps make a good legal 
> "edge case".

I certainly consider "legal" issues to be part of the larger protocol,
inasmuch as banks, credit unions, etc., must obey all sorts of laws.
And there are IRS reporting "protocols," and so on. 

Part of my point was that calling things "Green Stamps" (not a slur on
Nick's idea) does not exempt them, nor does it even really mean they
are not money. Whether Green Stamps, coupons, digital bearer bonds,
"Get Out of Jail Free Cards," whatever, are "money" or not is a
complicated issue, which I can't go into here (1. No space, 2. I'm not
an expert, 3. The _names_ alone are not enough to tell.).

Eric Hughes investigated digital money from a legal point of view (for
example, the funny messages printed on your checks, like "Pay to
the order of," have actual, real meanings). I'm sure Eric, Duncan
Frisell, Sandy Sandfort, Perry Metzger, etc., can elaborate.

Part of the energy barrier we face, or soon will, is that crypto money
has had none (or very little) of the centuries of evolution--successes
and failures--that ordinary money has had. There may be clever ways to
make some forms of digital money essentially be isomorphic to actual
money--the stuff the world is used to, that is--and hence ride the
coat tails of the world's current system. But these will be
complicated, adding to the difficulty of analyzing new protocols for
crytographic, legal, fiduciary, and social acceptability.

> >From an object-oriented point of view, "E-greenstamps" inherit
> digital cash and add legal structure.  Here I am assuming that 
> E-greenstamps or other business/legal manifestations of digital cash can 
> be implemented with Chaum's protocol, providing "Pretty Good Digital 
> Cash" in the cryptographic sense.   The "Chaum off the shelf" 
> assumption.  If there are holes in Chaum's scheme, or major problems 
> with implementing it in software, I'd like to hear more, but "S&H 
> greenstamps" concept doesn't address software security issues.

Well, Chaum and his students have various specialized protocols, that
is, they reduce the complexity by mainly targeting one particular type
of system (toll roads, or digital cash for shops to redeem, whatever).
The "difficulty of analyzing protocols" issue.

Where Nick's idea fits it, how it might be spoofed by shopkeepers,
what prevents forgery, etc., are some of the many issues.

By the way, the latest (August) issue of "Mother Jones" has an article
on a small town in New England (I think) which has their own barter
dollars. We talked about barter dollars, and the Italian experiment
some time back, about a year or so ago, when the List was just getting
started.

Let me point out that the IRS takes a dim view of barter transactions
that are denominated in things other than dollars. 

> cash.  If we think the work ends with implementing a 
> good cryptographic protocol, we are sadly mistaken.  Perhaps that's 
> where the work of "cypherpunks" ends, but I have a broader vision of
> crypto-anarchy that covers the legal, business, and in general
> social issues as well.  Any group that wants to seriously
> deploy cryptography in the real world has to discuss these as well.

Agreed. Which is yet another reason to better formalize our reasoning
about complex protocols. The metaphors are too vague.

> We do need to be more clear on when we are talking about cryptographic 
> protocols ("digital cash"), legal structures ("S&H greenstamps"), and 
> business concepts ("commercial remailer"). 

The lines that separate them are tenuous. I agree it would be nice to
try to identify some truly basic "cryptographic primitives," and even
have them available in libraries (secret sharing, bit committment,
n-out-of-m voting, etc.). (But this is a tall order, as most of these
schemes have been written about, but are not available in software.)

> I'd love to see some digicash papers on soda.  I also agree on the

They're best left scattered amongst the "Crypto" Proceedings, for
reasons I've mentioned (briefly: 1. Hard to OCR them, 2. Anyone doing
work in this area _must_ have access to the Proceedings, if only to
track down the various referenced papers, 3. Too many papers on soda
could expose it to legal action (copyright), 4. The printed papers are
easier to read, anyway.).


> * A "cracker's guild" to break weak cryptography and publicize
...
> * A formal Crypto Auditing Agency that would verify the algorithms
> and protocols were secure, without revealing trade secrets.

Any Cypherpunks are of course free to do these things, but I won't
hold my breath waiting. These things take a lot of time. And the
Cypherpunks group just is in no position to "decide" on a strategy and
then somehow "assign" staff to these projects. So, it won't get done
this way.

(That's also why a "Cypherpunk chip" is farfetched....too much work.)

This is not because Cypherpunks are lazy or unfocussed, but because
Cypherpunks is a group of volunteers, all with their own goals and pet
projects. 

-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: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.

>Eric Hughes investigated digital money from a legal point of view [...]

Indeed.  It's a mess.

No matter how you do it, it seems, real corporations will have to be
involved, which means business plans, etc.  Not a low entry barrier,
unfortunately.  If you hold money for someone else, you'd better be a
corporation in order to limit liability.  And if you hold money for
someone else, you're either entirely within the regulated bank
environment or so close to its edge that your territory could be
included at any time.

It appears the easiest way to get digital money going is to be the
bank--a fully legitimate, above board, fully qualified financial
institution.  Fortunately, one doesn't have to be exactly a bank, in
the legal sense.  Other institutions are available, such as credit
unions, mutual savings banks, and S&L's--these are the so-called
thrift institutions.  These tend to have reduced regulatory burden in
exchange for limited power to transact.  

Eric