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
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
* 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"
participants (6)
-
Eric Hughes
-
gnu
-
karn@qualcomm.com
-
khijol!erc@apple.com
-
szabo@netcom.com
-
tcmay@netcom.com