Subject: RSA touts DIY certificates - msg#00087

Previous Message by Date: click to view message preview

Re: Shortcut digital signature verification failure

Bill Frantz wrote: >If there is a digital signature algorithm which has the property that most >invalid signatures can be detected with a small amount of processing, then >I can force the attacker to start expending his CPU to present signatures >which will cause my server to expend it's CPU. My 800MHz PIII can do about 2800 512-bit RSA verifies per second. Dan Bernstein has a signature algorithm where verification is significantly faster still [1], and his ideas could probably be used to quickly reject most invalid signatures with even better efficiency. One of the nicest ideas from his work is easy to describe. In plain RSA, s is a valid signature on m if H(m) = s^3 (mod n). Now suppose we ask the signer to also supply an integer k such that 0 <= s^3 - kn < n; clearly this can't hurt security, as k can be publicly computed from s. Then the recipient can efficiently verify the validity of the claimed signature (t,k) on m as follows: verify that 0 <= s^3 - kn < n; then secretly pick a random 31-bit prime p, compute t' = s^3 mod p, n' = n mod p, k' = k mod p, h' = H(m) mod p, and verify that t' - k'n' = h' (mod p). This requires a few reductions and multiplications modulo a 31-bit number, and thus is faster than verifying the RSA signature directly (the latter requires a few reductions and multiplications modulo a 512-bit number). Moreover, if the prime is chosen randomly, the probability that an adversary can forge a signature that passes this screening test is something like 2^-26 or so. In short, invalid signatures can be detected quickly with very high probability. [1] D. J. Bernstein. ``A secure public-key signature system with extremely fast verification.'' http://cr.yp.to/papers.html#sigs --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxxxxxxx

Next Message by Date: click to view message preview

Book Review: Peter Wayner's "Translucent Databases"

Obvious All Along Robert Hettinga Translucent Databases By Peter Wayner Flyzone Press, 2002 ISBN 0-9675844-1-8 Through many popular books and articles in the New York Times, Peter Wayner has done more to promote the field of applied financial cryptography, and in particular open source financial cryptography, than any other author writing today. His new book, Translucent Databases, from Flyzone Press, is no exception. Translucent Databases has all the hallmarks of Wayner's books: clear, easy to read exposition of the main issues, why they're important, and, in his technical books, excellently documented code written for the most popular platforms for the technology in question. This book in particular should be an instant classic because like all great books, it takes what should be a very simple idea, encrypted databases, and expands it to some amazing conclusions. For a long time now, I've been interested in what I call the geodesic economy, where all information, including information controlling financial assets, is fractally "surfacted", like so much grease in soapy dishwater, as far out into the edges of a ubiquitous internetwork as Moore's Law will allow, using financial cryptography protocols to secure transactions and markets on a nominally insecure, but ubiquitous, public internetwork. People who are familiar with my thinking about such things over the past 8 years will see quite quickly why I think Peter's new book is so important. Transparent databases represent a way not only to link the batch-settled, book-entry debit-for-credit world of modern financial operations with a more simply founded, but much more sophisticated world which uses cryptographic tokens representing control of various financial and real assets. They also show us how to actually account for those tokens in such a fashion that every financial actor in that market, man or machine, can trust that their bearer certificates are authentic ones, and done in such a fashion that a given token retains its cryptographic integrity, including the functionally anonymous characteristics that made it so cheap to use in the first place. The singular feature of Wayner's translucent databases is that, like internet bearer transactions themselves, the cryptography securing data in them can happen in the client, and not a centrally vulnerable server. More to the point, by using data stored in this fashion, the data can be dispersed as far out in the network as... well, Moore's Law allows, in extremely fast and lightweight files, and, instead of creating summaries of data for reports, the data can be polled for as close to its source as possible, instantaneously, in realtime, instead of being rolled up into increasingly larger batch-processed summaries taking weeks, sometimes months, to produce and audit. There are obvious implications for my own particular hobby-horses, like anonymous but accurate double spend databases for bearer transactions, where only a simple blinded m-of-n cryptographic hash of a given promise to pay is necessary to prevent the duplication of that promise to more than one person at a time. However, for the rest of us :-), Wayner also points to a whole host of much less esoteric applications in the lots of the usual places where absolute privacy and extremely authentic information, is at a premium. Examples for military, medical, and anti-rape databases, for accounting systems and securities transactions, and even for internet poker -- the paradigm of completely untrusted parties cooperating for what each player hopes will be his own, preferably cash, benefit -- are all presented in clear writing and running code. There has been a lot of lip-service in the privacy community about "owning" your own data. Unfortunately, by involving the state at all, these "advocates" almost always favor inadvertently Draconian political solutions to the problem presented by the ubiquity of database technology and it's otherwise beneficial presence in our lives. They usually present this nonsense as a "sacrifice" for the "greater good" that would make Hayek's Road to Serfdom look like Lilac Sunday at the local arboretum. In Translucent Databases, Wayner shows, in precise detail, with code, how to solve that problem, without trusting lawyers, much less guys with guns. Though quite a short read, the scope of the book itself is quite considerable. Wayner starts from simple hashes of data to merely obscure it, through various kinds of encryption, quantization of data, and even accounting with encrypted data using what amounts to virtual cumulative crossfoots like the kind you would see on all good accounting reports. In so doing, Wayner explains, quite simply, something that people like Eric Hughes made great, complicated hay out of years ago with gangling theories of encrypted "open" books. Ultimately, Wayner really does end up where a lot of us think databases will be someday, particularly in finance: repositories of data accessible only by digital bearer tokens using various blind signature protocols, neatly, and quite literally, "dis-integrating" the ability of databases to be used against us as a tool of totalitarianism, exemplified most recently by Simpson Garfinkel in his book Database Nation, and, oddly enough, not because someone or other wants to strike a blow against the empire, but simply because it's safer -- and cheaper -- to do that way. Every database programmer should have a copy of this simple and elegant book on his reference bookshelf. Particularly if he cares about the integrity of his data, the liability to the database's owner should information be misappropriated, and, not least, about freedom itself in a world of ubiquitous, and, frankly, necessary, stored detail: details about practically every person on earth, their property and finances, and, ultimately, everything they do. Translucent Databases presents a simple, frankly beautiful, solution to David Brin's world of ubiquitous surveillance, one not requiring, as Brin seems to want, "trust" of state force-monopolists, much less their lawyers and apparatchiks. In fact, it's such an elegant solution that, as Schopenhauer liked to say about the public acceptance of important new ideas, soon enough, people will say it was obvious all along. ------- Robert Hettinga is founder of IBUC, the Internet Bearer Underwriting Corporation, which will, hopefully, someday, :-), use translucent databases full of internet bearer certificates to reduce transaction costs by three orders of magnitude. -- ----------------- R. A. Hettinga <mailto: rah@xxxxxxxx> The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire' --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxxxxxxx

Previous Message by Thread: click to view message preview

Followup: [RE: DOJ proposes US data-rentention law.]

Two points: 1. According to Poulson, the DOJ proposal never discussed just what would be logged. Poulson compared it to the European Big Brother legislation, which required storage to Web browsing histories and email header data. 2. After I posted the same info to /. http://slashdot.org/articles/02/06/19/1724216.shtml?tid=103 (I'm the 'Anonymous Coward' in this case), Kevin updated his article. The new version may be found at: http://online.securityfocus.com/news/489 The relevant portions read: - start quote - U.S. Denies Data Retention Plans The Justice Department disputes claims that Internet service providers could be forced to spy on their customers as part of the U.S. strategy for securing cyberspace. By Kevin Poulsen, Jun 19 2002 12:24PM [...] But a Justice Department source said Wednesday that data retention is mentioned in the strategy only as an industry concern -- ISPs and telecom companies oppose the costly idea -- and does not reflect any plan by the department or the White House to push for a U.S. law. [...] - end quote - Peter Trei > ---------- > From: David G. Koontz[SMTP:koontz@xxxxxxxxxxxxx] > Sent: Thursday, June 20, 2002 10:57 AM > To: cypherpunks@xxxxxxx > Cc: 'cryptography@xxxxxxxxxxxxxxxxx'; 'cypherpunks@xxxxxxx' > Subject: Re: DOJ proposes US data-rentention law. > > Trei, Peter wrote: > > - start quote - > > > > Cyber Security Plan Contemplates U.S. Data Retention Law > > http://online.securityfocus.com/news/486 > > > > Internet service providers may be forced into wholesale spying > > on their customers as part of the White House's strategy for > > securing cyberspace. > > > > By Kevin Poulsen, Jun 18 2002 3:46PM > > > > An early draft of the White House's National Strategy to Secure > > Cyberspace envisions the same kind of mandatory customer data > > collection and retention by U.S. Internet service providers as was > > recently enacted in Europe, according to sources who have reviewed > > portions of the plan. > > > > In recent weeks, the administration has begun doling out bits and > > pieces of a draft of the strategy to technology industry members > > and advocacy groups. A federal data retention law is suggested > > briefly in a section drafted in part by the U.S. Justice Department. > > > > If the U.S. wasn't in an undeclared 'war', this would be considered > an unfunded mandate. Does anyone realize the cost involved? Think > of all the spam that needs to be recorded for posterity. ISPs don't > currently record the type of information that this is talking about. > What customer data backup is being performed by ISPs is by and large > done by disk mirroring and is not kept permanently. > > I did a bit of back of the envelope calculation and the cost in the > U.S. approaches half a billion dollars a year in additional backup > costs a year without any CALEA type impact to make it easy for law > enforcment to do data mining. The estimate could easily be low by a > factor of 5-10. AOL of course would be hit by 40 percent of this > though, not to mention a nice tax on MSN. Call it ten cents a day > per customer in fee increases to record all that spam for review by > big brother. I feel safer already. > > Whats next, censorship? > --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxxxxxxx

Next Message by Thread: click to view message preview

Book Review: Peter Wayner's "Translucent Databases"

Obvious All Along Robert Hettinga Translucent Databases By Peter Wayner Flyzone Press, 2002 ISBN 0-9675844-1-8 Through many popular books and articles in the New York Times, Peter Wayner has done more to promote the field of applied financial cryptography, and in particular open source financial cryptography, than any other author writing today. His new book, Translucent Databases, from Flyzone Press, is no exception. Translucent Databases has all the hallmarks of Wayner's books: clear, easy to read exposition of the main issues, why they're important, and, in his technical books, excellently documented code written for the most popular platforms for the technology in question. This book in particular should be an instant classic because like all great books, it takes what should be a very simple idea, encrypted databases, and expands it to some amazing conclusions. For a long time now, I've been interested in what I call the geodesic economy, where all information, including information controlling financial assets, is fractally "surfacted", like so much grease in soapy dishwater, as far out into the edges of a ubiquitous internetwork as Moore's Law will allow, using financial cryptography protocols to secure transactions and markets on a nominally insecure, but ubiquitous, public internetwork. People who are familiar with my thinking about such things over the past 8 years will see quite quickly why I think Peter's new book is so important. Transparent databases represent a way not only to link the batch-settled, book-entry debit-for-credit world of modern financial operations with a more simply founded, but much more sophisticated world which uses cryptographic tokens representing control of various financial and real assets. They also show us how to actually account for those tokens in such a fashion that every financial actor in that market, man or machine, can trust that their bearer certificates are authentic ones, and done in such a fashion that a given token retains its cryptographic integrity, including the functionally anonymous characteristics that made it so cheap to use in the first place. The singular feature of Wayner's translucent databases is that, like internet bearer transactions themselves, the cryptography securing data in them can happen in the client, and not a centrally vulnerable server. More to the point, by using data stored in this fashion, the data can be dispersed as far out in the network as... well, Moore's Law allows, in extremely fast and lightweight files, and, instead of creating summaries of data for reports, the data can be polled for as close to its source as possible, instantaneously, in realtime, instead of being rolled up into increasingly larger batch-processed summaries taking weeks, sometimes months, to produce and audit. There are obvious implications for my own particular hobby-horses, like anonymous but accurate double spend databases for bearer transactions, where only a simple blinded m-of-n cryptographic hash of a given promise to pay is necessary to prevent the duplication of that promise to more than one person at a time. However, for the rest of us :-), Wayner also points to a whole host of much less esoteric applications in the lots of the usual places where absolute privacy and extremely authentic information, is at a premium. Examples for military, medical, and anti-rape databases, for accounting systems and securities transactions, and even for internet poker -- the paradigm of completely untrusted parties cooperating for what each player hopes will be his own, preferably cash, benefit -- are all presented in clear writing and running code. There has been a lot of lip-service in the privacy community about "owning" your own data. Unfortunately, by involving the state at all, these "advocates" almost always favor inadvertently Draconian political solutions to the problem presented by the ubiquity of database technology and it's otherwise beneficial presence in our lives. They usually present this nonsense as a "sacrifice" for the "greater good" that would make Hayek's Road to Serfdom look like Lilac Sunday at the local arboretum. In Translucent Databases, Wayner shows, in precise detail, with code, how to solve that problem, without trusting lawyers, much less guys with guns. Though quite a short read, the scope of the book itself is quite considerable. Wayner starts from simple hashes of data to merely obscure it, through various kinds of encryption, quantization of data, and even accounting with encrypted data using what amounts to virtual cumulative crossfoots like the kind you would see on all good accounting reports. In so doing, Wayner explains, quite simply, something that people like Eric Hughes made great, complicated hay out of years ago with gangling theories of encrypted "open" books. Ultimately, Wayner really does end up where a lot of us think databases will be someday, particularly in finance: repositories of data accessible only by digital bearer tokens using various blind signature protocols, neatly, and quite literally, "dis-integrating" the ability of databases to be used against us as a tool of totalitarianism, exemplified most recently by Simpson Garfinkel in his book Database Nation, and, oddly enough, not because someone or other wants to strike a blow against the empire, but simply because it's safer -- and cheaper -- to do that way. Every database programmer should have a copy of this simple and elegant book on his reference bookshelf. Particularly if he cares about the integrity of his data, the liability to the database's owner should information be misappropriated, and, not least, about freedom itself in a world of ubiquitous, and, frankly, necessary, stored detail: details about practically every person on earth, their property and finances, and, ultimately, everything they do. Translucent Databases presents a simple, frankly beautiful, solution to David Brin's world of ubiquitous surveillance, one not requiring, as Brin seems to want, "trust" of state force-monopolists, much less their lawyers and apparatchiks. In fact, it's such an elegant solution that, as Schopenhauer liked to say about the public acceptance of important new ideas, soon enough, people will say it was obvious all along. ------- Robert Hettinga is founder of IBUC, the Internet Bearer Underwriting Corporation, which will, hopefully, someday, :-), use translucent databases full of internet bearer certificates to reduce transaction costs by three orders of magnitude. -- ----------------- R. A. Hettinga <mailto: rah@xxxxxxxx> The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire' --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@xxxxxxxxxxxxxxxxx