Re: PGP flaw found by Czech firm allows dig sig to be forged
A "vulnerability" that requires the opponent to have write access to your private key in order to exploit? Okay. What was PGP's threat model again? I'd have sworn that this was squarely outside it. Probably. Do you need only write access? What does that do for smart cards - if anything? -David
Re: Recommendations for Cypherpunks Books
On Mon, 22 Jan 2001, Bill Stewart wrote: "Trouble and Her Friends" has some good treatment of cryptographically protected subcultures, though that's more as redeeming-social-value for a book that's written for genre. Yes, that had been nagging at me. I haven't read it in years so didn't want to speak up and find that I'd confused it with some other book...but I remember it being really good. Etizoni is a very technical boy. Unfortunately, his value system led him to invent "Fair Cryptography" (that's "fair" as in "Fair Trade", not "fair" as in "actually fair to anybody" :-), which covers a couple of variants on key escrow. Hmm. So this explains all those papers on "fair cryptosystems." Well, at least one paper (and patent!) by Micali... -David
Re: Consensus Actions in Cipherspace?
On Fri, 12 Jan 2001, Ray Dillinger wrote: Are there any good general cryptographic protocols for groups taking group actions by formal consensus or voting rules? There are distributed signing protocols which could go partway towards meeting this goal. For some details, you can look at the IBM project on "Proactive Security" http://www.hrl.il.ibm.com/Proactive/ They've implemented some of the protocols involved; there's a paper in ACM CCS 5 I think which gives the API for their "Proactive Security Toolkit." Java 1.1 implementation of distributed DSA signatures. Unfortunately, the web page, which advertises a download for 8/99, seems to be out of date. http://www.hrl.il.ibm.com/Proactive/project.html Now, if you could get your hands on this, then you could do what you want by having each voter hold a share of the distributed secret key. The voters agree amongst themselves however on what orders to sign, and then execute distributed key signing to sign an order. The robot doesn't do anything unless it receives a valid signed order. -David
Re: Anarchy Eroded: Project Efnext
On Tue, 2 Jan 2001, Steve Schear wrote: Uh, right. Let us know when you have working code. It shouldn't be very hard to bridge Usenet and Mojo Nation. If memory serves, there is a project underway to do "usenet-on-freenet." -David
Re: Anarchy Eroded: Project Efnext
On Sat, 30 Dec 2000, Eric Cordian wrote: A typical citizen-unit will quickly trade a large amount of privacy for a small amount of convenience. Sheeple-shearing is never so successful as when it's "voluntary." Then it seems imperative to find ways to acheive both convenience and privacy... -David
Re: That 70's Crypto Show (Re: Dude! It's wired!)
On Tue, 26 Dec 2000, Tim May wrote:
Has there really been much progress in the last ten years? I remember
the flurry of ground-breaking work in the mid-80s, and it was much in
the air at the first "Crypto Conference" I attended in 1988 (also the
last such conference I attended, for various reasons).
Some things come to mind:
1) Efficient realizations of provably secure cryptosystems.
- Optimal Asymmetric Encryption Padding (OAEP) 1994
Bellare and Rogaway show a way to do secure RSA encryption
without falling victim to any of the nasty padding attacks
found by Coppersmith, Hastad, and others.
- Probabilistic Signature Scheme (PSS) 1996
How to properly pad your signatures. Again Bellare and Rogaway.
Both OAEP and PSS rely on the so-called "random oracle assumption"
which needs its own message to explain. Suffice to say that if
you buy that assumption, you end up with schemes which are
99% as efficient as the "naive" way of doing things.
Of course, there *were* padding methods arround before
OAEP and PSS. Recent events have shown that some of them
weren't a good idea - in particular the padding in
the old PKCS #1 1.5 standard has come in for a beating.
More recently, people have come up with methods which don't
need the "random oracle assumption" (Cramer and Shoup most
notedly), but they're still not as efficient as OAEP and PSS.
This is a big deal because it opens the way for
"practice-oriented provable security" -- all that beautiful
theory people were excited about in 1988 makes its way into
real products.
2) Commercialization and availability of SSL/TLS
Ten years ago, we didn't have a good engineering-level spec for
a protocol to encrypt streams. Now, three or four iterations of
SSL later, we do. Plus the www.openssl.org effort makes this
easy to use - some random undergrad can knock together an
SSL-enabled application in a short time.
Now that we're *finally* going to get some good documentation
in the form of Eric Rescorla's book, maybe more people will
take advantage of OpenSSL...
In addition, the failures of SSL 1.0 and 2.0 (should have)
taught us about what Not To Do when designing protocols.
Like "protect your protocol negotiation"...
3) Differential Cryptanlysis, Linear Cryptanalysis, Block
Cipher Design
Not particularly cypherpunkish or protocol-ish, but needs
mentioning. Academic cryptographers rediscover NSA techniques
and start us on the path to an AES competition. Look also at
the analysis of Skipjack and how it was determined that 16 rounds
were "just enough" -- we could not have done that in 1988 or 1990,
I think. Although I should really leave that determination
to someone with more experience in that area than I have.
4) Practical and Theoretical advances in Digital Cash
Today, I can go pick up the -lucre library - either version,
or Magic Money and produce a "Pretty Good Digital Cash"
enabled application. There's still no reason on earth why I
should do so, alas, but I can. Also now the Mojo Nation stuff
may take off. To this you may add the various smart card and
digital cash experiments and projects which went on.
Stefan Brands' techniques take the old "credential without
identity" idea and make it practical and flexible. Plus his thesis
and advocacy for an alternative to a hierarchical PKI will be
useful in heading off the advent of "digital driver's licenses."
None of these are as fundamental as creating the first real definition of
security for a cryptosystem or as ground-breaking. But they follow up on
those first efforts and make it easier to do what we want with
cryptography.
Something I expected to have happened long ago was the
encapsulization of these protocols into building blocks into
libraries/classes/reusable objects that could be bolted together by
those building systems. ("Let's take EncryptStream and throw in
EscrowService and then add ObliviousTransfer...").
There have been two major problems, as far as I see, which have held this
up. First, the theory has not always been cooperative. Second, despite the
myriad of amazing special protocols which have appeared over the years,
we have only a few core protocols which people seem to want badly enough
to justify moving from the CRYPTO paper to the engineering stage. You can
point the finger at patents, too, if you like - but they may have helped
as well as hurt (I'll explain why in a bit).
When I say "the theory has not always been cooperative," I mean such
things as the fact that zero-knowledge proofs are not zero-knowledge
Re: That 70's Crypto Show (Remailers, science and engineering)
On Fri, 29 Dec 2000, Greg Broiles wrote: But - several, if not many times - the security we've achieved has been broken, because of implementation errors on the part of creators, installers, or users. That's right - that's part of the fact that cryptographic engineering (as opposed to "cryptographic science") is still in its infancy. This is the downside of the current approach, which focuses on getting the protocol right first, and only later considers the "real world." Bruce Schneier had another way of putting it - something along the lines of "The math is perfect, the hardware is so-so, the software is a mess, and the people are awful!" (not an exact quote, but I remember it from one of his DEF CON speeches). That being said, there is some benefit to considering the protocols in an ideal, polite model - because in the past we haven't even been able to get security in *that* model. So in some sense this is a case of "publishing what we can prove." It's only comparatively recently that we've had protocols which we can prove secure, even in weak models -- the first real definitions of security from Yao, Goldwasser and Micali, and probably others weren't until the early to mid 1980s. Truly practical cryptosystems which meet these definitions of security didn't arrive until the 1990s. (Some would argue that they still aren't here - Bellare and Rogaway's Optimal Asymmetric Encryption Padding (OAEP) satisfies a strong definition of security, but only if you buy the "random oracle assumption.") Now on the "science" side we can and should extend the model to deal with more of the real world. You might find the recent paper I posted a link to by Canetti interesting - he sets out to deal with an asynchronous network with active adversaries. I didn't see torture included yet, but maybe next version. Birgit Pfitzmann and Michael Waidner are considering something called "reactive systems" which may also yield results. http://citeseer.nj.nec.com/297161.html On the engineering side -- well, there's a long way to go. Ross Anderson has a new book coming out which may help a little bit. http://www.cl.cam.ac.uk/~rja14/book.html The fact remains that I don't think we have enough experience implementing protocols beyond encryption and signatures. At least not on a wide scale. Take digital cash and voting protocols as an example. Digital cash has been implemented and re-implemented several times. It's even had a "live" test or two. But how many people have managed to buy something tangible with it? and how does that compare to the amount cleared by credit cards? Electronic voting seems to be on the upswing - at least with votehere.com and the recent election debacle hanging over our heads. Still, who has implemented, tested, and deployed a truly large-scale voting system based on cryptographic protocols? The one which comes to mind is the MIT system built on the FOO protocol - and while that *works* (modulo operator error), that's only a few thousand undergrads. It's at times like this that I wish I knew more about formal verification of protocols... Consider the computing power assembled for the DES or RC5 cracks, instead applied to dictionary attacks versus a PGP keyring, or SSH keyfile. How long until the average user's passphrase is recovered? If the passphrase is in the dictionary, nearly no time at all. Some take this to mean that now we should write passphrases down, and use the opportunity to pick long random ones unlikely to be in any dictionary... -David
Re: Anarchy Eroded: Project Efnext
On Sat, 30 Dec 2000, Eric Cordian wrote: Unknown to much of the Internet, there is a plan brewing to "upgrade" Efnet, the primary IRC network, to something called "Efnext." Server software is being rewritten and tested. Efnet server admins have been contacted and promises to move to the new network during a "transition period" exacted. People who won't play ball have been identified, and plans to delink them and not connect them to the new regime fabricated. Something I don't see much of on the efxnet page - "why?" This is in the FAQ: "EFNext is the name of a project geared towards making IRC a more stable, uniform, chat environment." and they say "introductory document coming soon." I still don't know why this is happening (I don't hang out on EFnet). What do the efxnet people give as their reasons for a new IRC network? -David
Re: That 70's Crypto Show (Remailers, science and engineering)
On Wed, 27 Dec 2000, Bill Stewart wrote: fewer talks on new stuff people are doing and more on some commercial business (maybe or maybe not run by cypherpunks) doing their product or non-technical talks by EFF lawyer types. 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). 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. 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! Even after "everyone" knows that you can do, say, cryptographic voting, there's still the question of "who's going to pay for it?" That question seems to have found a partial answer with the Internet/Web/"e-commerce" frenzy. The thing is, that is *new*, only 4 or 5 years old. Before, you could go out and say "I want to go commercialize neat protocol X," and good luck to you...today, you might get funding. Until you get that funding, you can't start the engineering work that's required to take a protocol from the "cool CRYPTO paper" stage to the "real world product." 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. 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. Cool. Are the proceedings on line anywhere? (Or is it only for people who know the secret keys...) The 2nd and 3rd are, via Springer-Verlag LINK service. Tables of contents are free; you should be able to recover the papers from their authors' home pages (use Google!). If you can't find something, e-mail me. Page for past proceedings: http://chacs.nrl.navy.mil/IHW2001/past-workshops.html Page for IHW 2001: http://chacs.nrl.navy.mil/IHW2001/ Unfortunately, the TOC for the first IHW is not online, nor do the papers seem to be available. You can extract the papers from Petitcolas' bibliography at http://www.cl.cam.ac.uk/users/fapp2/steganography/bibliography/index.html and may be able to get some of the papers that way. I note a previous message from Hal Finney which has some links as well http://www.inet-one.com/cypherpunks/dir.1997.05.15-1997.05.21/msg00298.html (I haven't tried them) I should state up front that the workshops are a little heavy on watermarking papers, which may not be of too much interest to cypherpunks. The papers on breaking watermarks, on the other hand, may be of more interest. :-) 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] 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...) -David
Re: That 70's Crypto Show (Remailers, science and engineering)
On Wed, 27 Dec 2000, Bill Stewart wrote: There's some hope. There was a workshop on "Design Issues in Anonymity and Unobservability" this past summer which brought people together to talk about these issues. The Info Hiding Workshops are still going strong. With luck, this year's IHW may have a paper on reputations in it... Cool. Are the proceedings on line anywhere? (Or is it only for people who know the secret keys...) Uh, it just occurs to me that I may have misread you. The Design Issues in Anonymity and Unobservability is currently being turned into Springer-Verlag LNCS 2009. So the proceedings aren't online as a whole yet (indeed, we just submitted our final final draft two weeks ago). You can find a list of papers at http://www.icsi.berkeley.edu/~hannes/wsprogram.html our paper is at http://www.freehaven.net/doc/berk/freehaven-berk.ps and searching for authors' home pages or e-mail may reveal other papers. -David
Re: Dude! It's wired!
On Sun, 24 Dec 2000, Eric Cordian wrote: Perhaps next year will be better. I'm almost begining to feel that Cryptology has achieved the status of a "Mature Science." It's my impression that mature sciences don't have the same kind of foundational or engineering problems cryptography does. We still see surprises about what a "definition of security" should be, even in the public-key setting where people have investigated such things for nearly 20 years. Plus even when we figure that out, we'll still have to deal with the fact that the models used in theoretical crypto don't deal with some of the attacks possible in real life -- timing and power analysis come to mind. As does the van Someren and Shamir trick for finding keys because they look "too random." To say nothing of the nasty fact that passphrases, and therefore keys based on them, aren't random at all. Which does not play nice with models which assume keys are picked randomly. It may be true that this year was a lull in "interesting" cryptographic research (I don't know if that's quite true), but it doesn't seem to be because too many problems are solved. Rather, there are lots of open problems left which no one seems to know how to solve... -David
Re: That 70's Crypto Show (Re: Dude! It's wired!)
On Mon, 25 Dec 2000, Tim May wrote:
Some of the foundations are, of course, "mature"...and not very
exciting. The core of mathematical crypto is hardly frontier
mathematics. (Yeah, I suppose Dave and Eric and a few others could
make a case that there's some connection with the proof of Fermat's
Last Theorem, stuff about elliptic functions, etc. But we all know
I don't think I'd go that far. As far as I'm concerned, elliptic curves
are just another group to do Diffie-Hellman friends in. What I'd call
the "core" of mathematical crypto is the work that Goldreich, Goldwasser,
Micali, et. al. have been doing over the past fifteen years -- trying to
rough out just what kind of assumptions are necessary and sufficient to
give us the kind of cryptography we want.
That being said, almost none of it works without those pesky one-way
functions. or trapdoor one-way functions. and we have too few examples of
either.
that such connections are tenuous. Most of crypto still is built
around good old number theory, basically what has been known for
dozens of years, even centuries. Euler would not have had a problem
understanding RSA.)
That's true, and in some sense it's a good thing - we have some confidence
that these problems are hard because "Euler worked on them." (On the other
hand, Euler didn't have the ability to experiment today's mathematicians
do). In another sense, it's a bad thing, because the number of one-way
functions we have is so small. To say nothing of trapdoor one-way
functions...
The "far out" stuff of reputations, multi-player games, digital
money, etc., is much less-grounded in theory. More interdisciplinary,
more "fuzzy," more prone to hand-waving. Doesn't mean this this isn't
the interesting area, just means it's not as "foundational" as math
areas are. Reductionists who seek the rigor of a pure science often
end up throwing out what's interesting.
So I have noticed. (and so I have to caution myself against every day).
By academic coverage I mean researchers studying weaknesses in
various kinds of data havens, digital currencies, reputation systems,
etc., in the same way that the "Crypto Conference" folks looked at
various ciphers. (And specific digital currency systems, for example.)
Reminds me of the reaction I got when I asked some friends about
doing a term project on mix-nets.
"So, has there been any recent academic work on this?"
There's some hope. There was a workshop on "Design Issues in Anonymity and
Unobservability" this past summer which brought people together to talk
about these issues. The Info Hiding Workshops are still going strong.
With luck, this year's IHW may have a paper on reputations in it...
This year's ACM CCS conference had two papers of special interest.
The "Hordes" paper, _A protocol for anonymous communication over the
Internet_ by Clay Shields and Brian Neil Levine, gives a definition of
anonymity which seems convincing.
Then the paper by Franklin and Durfee on "Distribution Chain Security"
discusses the problems of dealing with contracts in a distribution chain.
They have to balance the rights of buyers, sellers, and various middlemen
- and develop some cute cryptographic tricks to do it. Obfuscated
contracts, zero-knowledge proofs, and special "contract certifiers" make
an appearance. It wouldn't surprise me if this ended up having application
beyond the content distribution network scenario they propose.
Crypto systems, using a mix of crypto tools, is only slowly taking
off. In fact, the focus keeps moving back to simple encryption,
depressingly enough!
Depressingly enough, we keep finding that the focus *needs* to move back
to simple encryption. Birgit Pfitzmann published a paper in the 1980s on
"How To Break the Direct-RSA Implementation of MIXes." Today, nearly
fifteen years later, we still don't know "really" what we need from
an encryption system for MIXes; David Hopwood has some good thoughts,
but we're not done yet.
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.
(And, as I have been saying for close to 10 years, the
insurance
industry will be a driver of new approaches. Newer safes were bought
not because store and bank owners were "educated" about security (the
precise analogy to security today), but because insurance premiums
were lessened with better safes. Discounted present value, DPV,
speaks louder than all of the moralizing and lecturing.)
This may have to wait until liability issues in general for software are
straightened out, won't it?
More than that, if the "tragedy of the commons" really happens for
Gnutella and Napster and friends, then people will look for ways to avert
it. Maybe it won't happen ("The Cornucopia of the Commons"), but if
it does, reputation systems might see some sudden
Re: china-taiwan and limits of state action
On Sat, 23 Dec 2000, Alex Shirado wrote: David, You have a simple view of China-Taiwan relations, but you are more of a computer specialist than an Asia one, so your deficiency is quite forgivable. I suspected as much. The problem with this is that I saw the "individual action indistinguishable from state action" quickly and have been having a hard time thinking past it. I'm sure that the picture is much more nuanced than what I have... There are actually other "cyber-war" examples which come to mind where it wasn't clear whether an "attack" was the result of a state action or just some crackers. One such was when NATO's web site was defaced; there was a quote to the effect of "Now the war is fought on all fronts" which made the rounds. The quote is interesting first because it places defacing a web site on the same level as firing bullets at people. Next because I'm not sure if it was clear who exactly defaced the site. Recently I've heard that Israel and neighboring Arab countries are going back and forth. For instance http://www.all.net/intel/mid-east/10-26-2000-art1.html http://www.meib.org/articles/0011_me2.htm I recently heard a story about policeman in Taiwan who is close to retiring. When he was asked what he planned to do when he retires, he said that he wanted to go back to the Mainland. To the outsider, this would seem strange, but it would be hard to believe that Taiwan and China do not have a workable and effective MO. I suppose the closest the U.S. has had to this was the Cold War. We did have some kind of MO with the USSR, but we didn't (don't) share the same kind of common heritage that China and Taiwan do. Someone who responded to your post stated that it is far more likely that China would be the aggressor in a cross-strait spat. Now, where the Taiwan-China working MO might break down would be when individuals act. In a way, hacking is the attack of the powerless: it allows geeks like us to launch an assault when we cannot afford tactical weapons. So it is wrong to think that angry Taiwanese would hesitate from waving the red in front of the bull. Yes - what seems interesting is that cracking makes offense as "democratic" as defense. That is, anyone with a weapon can defend their home and territory. That's what a militia is supposed to be, after all. (of course, given the massive inequality in weapons available to armies and available to private citizens, the militia may not last long...) But the local militia usually can't unilaterally launch an attack on some foreign country. (Well, maybe those on the border; the film "Canadian Bacon" comes to mind). A minor nitpick - it seems strange to say that we are "powerless" and then note how we can launch an assault. Maybe it would be better to say that this gives us a different kind of power or "redefines power." As you state, there is no cyberterror treaty governing how information regarding attacks is treated. Many of us take for granted that other informal arrangements govern how this information is treated. If we think about it at all. Perhaps you're living in a country where more people remember other countries exist. :-) In any case, I find it interesting to see the resistance to the current proposed cyber-crime treaty http://www.gilc.org/privacy/coe-letter-1000.html which rests on notions of human rights and so on. Values I agree with. At the same time, this seems to place the signing organizations "against" the Israelis, Chinese, or others who may find that current informal arrangements aren't enough. The questions you ask are valid. Indeed, they are some of the reasons why this listserve exists. You are asking core questions as to how we should treat state activity and personal responsibility. When you find the answers, let me know ; ) That's why I'm posting here, after all. Thanks, -David
have we had any cyber-terrorist attacks in the U.S.?
I can think of two terrorist attacks on U.S. soil without too much difficulty: the World Trade Center and Oklahoma City. In both cases, computers and "internet" loosely defined played a minor organizational role. McVeigh used AOL, and the Trade Center bombers had some plans on a floppy disk. Have we had any instance of "cyber terrorism" -- you know, the kind of awful scenario which most people reading this could cook up without too much difficulty. or is the question not well formed since if it was a successful attack, we wouldn't know? -David
Re: china-taiwan and limits of state action
On Fri, 22 Dec 2000, Richard Crisp wrote: I think the attacks are far more likely to be launched by the Mainland folks against the Taiwanese rather than the other way around. The mainlanders want to destabilize Taiwan. Taiwan likes a stable mainland, because so many What intrigues me about this conflict is that it seems possible for ordinary citizens to have the same kind of access to attack that the state does. So speaking of "the mainlanders" or "Taiwan likes" may be misplaced. Of course, most private citizens won't be able to do much with it, but there may be some who will. I agree with you with respect to the mainland and Taiwanese governments, though. -David
Re: Reading list
On Thu, 19 Oct 2000, Alan Olsen wrote: I also recommend a list of books that piss people off while reading. Things like "The ICSA Guide to Cryptography". (The most pro-GAK crypto book I have ever read. I keep it as a reminder of which libraries and products to avoid.) I've only had occasion to flip through this in a bookstore. I remember thinking that it could have used another 2 or 3 re-edits. Also that its treatment of semantic security and probabilistic encryption was pretty bad. Must have missed the pro-GAK stuff. I think one of the books which made me wonder "what the hell" was _The Frozen Republic_ in the last part -- the author argues that separation of powers is an outmoded and silly concept, our government can't act fast enough, and wouldn't we be better off with a British style system for doing things which didn't have all these checks and balances? With due respect to British readers, I think the RIP act shows one of the reasons why we would not be better off. Not that our own equivalent isn't far behind; haven't there been murmurs for a while about making "the use of cryptography in committing a crime" a separate crime? :-\ -david
Re: why should it be trusted?
On Tue, 17 Oct 2000, Jordan Dimov wrote: Could a factoring breakthrough happen to convert this exptime problem to polynomial time? Maybe. I said as much. Is it likely? See discussions on progress toward proving factoring to be NP-hard (it hasn't been proved to be such, though it is suspected to be so, i.e., that there will never be "easy" methods of factoring arbitrary large numbers). Geee... Since when are problems "proven" to be NP-hard?? Go back to your favorite undergrad institution and take a course on computational complexity again. Um, "NP-hard" just means that it's polynomial time reducible to any problem in NP (or perhaps the other way around, I always get the directions mixed up). It is fairly straightforward to show this - you exhibit a reduction to another problem you already know to be NP-hard. The "original" such problem is bounded halting : given a TM description M, an input x, and a polynomial bound p(n), does M halt on input x in p(length(x)) time? The famous theorem of Cook consists exactly of a reduction relating SATISFIABILITY and bounded halting. That's annoying. But once it's done you can give reductions to SATISFIABILITY instead. See Garey Johnson's book for more examples. Put another way, showing a problem is NP-hard doesn't actually show that it is "hard." It just shows that the problem is no easier than any problem in the class NP. It could still be the case that P = NP, in which case there is a rash of suicides in the crypto world... At the same time, it is believed unlikely that factoring is NP-hard. This is because "factoring" (the function problem 'find the factors of n'; not sure exactly how to formalize as a decision problem) is in NP intersect coNP. If factoring is NP-hard, then NP = coNP. This is believed to not be the case (but of course not proven). In addition, it's not at all clear how you could solve arbitrary SAT instances given an oracle for factoring. Try it and see. You don't appear to be familiar with the literature. I suggest you do some reading. Yeah, right. And you are familiar. He has the outline right, if not all the details. -David
Re: Where are the crypt source blackboards?
On Tue, 19 Sep 2000, Gary Jeffers wrote: source lines. I don't remember seeing any such on Cypherpunks and the little I've checked out on Coderpunks I haven't seen any there either. do people have code which they want to post? personally, the prohibition wouldn't affect me much. but most of my crypto source code issues are problems with using OpenSSL (I'm an OpenSSL newbie, sad to say, and trying to change that). there are other places to look for help with that... what I'd expect to be posted here or to coderpunks would be discussions of the right techniques and so on to use when developing crypto applications. sometimes with code as an illustration. and we do have that, c.f. discussions on wagner blinding, recipient hiding signatures, and so on. just not so much of it because, well, coming up with this stuff takes a fair amount of time. at least for me. so it is not as prevalent as the latest phil/pol musings. -david
Re: StoN, Diffie-Hellman, other junk..
On Thu, 7 Sep 2000, Asymmetric wrote: Now, my main question about D/H is quite simple.. what is considered a "good" size for the prime and primitive used, in bits? Obviously something somewhat large, but how large is large enough? 64bits? Less or more? I can't find much information on this anywhere, and my copy of Applied Cryptography (2nd ed.) while covering D/H in detail, doesn't even mention this. The modulus should be rather large -- something like 512 or 1024 bits. With 64 bits, someone can use Pollard's method to find discrete logs in roughly 2^32 trials, which is Bad. Taking discrete logs for larger primes requires a variant of the number field sieve; the largest announced modulus for which I'm aware of this being done is 300-400 bits, but it hasn't received as much attention as factoring. I think www.cryptosavvy.com has some key length recommendations. You might also check the April RSA Data Security Bulletin for Bob Silverman's dispute of their model. The storage problem he mentions is actually worse for discrete logs; while the vectors involved in the final step of factoring are 0-1, the vectors in the final stage of discrete log finding have full-size group elements and are therefore harder to store and manipulate. The size of the generator is a different issue. I don't see any reason why a small size generator would hurt...but I haven't thought about it very much. Note that you need the factors of p-1 in order to test if something's a generator, which means you may want to look into Maurer or Mihailescu's methods for prime generation. (Mihailescu has a paper on the subject aimed at implementors at http://www.inf.ethz.ch/~mihailes/papers/primgen.ps ) Delphi and has any libraries like this already, I'd much appreciate hearing about them.. or even some a web resource or paper Real Book (tm) resource that explains in abstract terms how to go about something like this would be appreciated. It was after my time, but the AP Computer Science curriculum now has a BigInteger library as its "case study." :-) A web search turned up http://www.efg2.com/lab/library/Delphi/MathFunctions/Cryptography.htm which has, among other things, a Pascal header for the Gnu MP library. -David
Re: ZKS: how EXACTLY does this protect privacy?
On Tue, 11 Jul 2000, Kevin Elliott wrote: least in the case of ZKS, I've never heard of Privada) are publicly known, and considered strong by most, if not all, cryptographers. The algorithms are publically known. the source isn't. although I personally am less annoyed by that than some recent posts to the list. Not sure if that's what the original poster meant or not, of course. As to the rest and the economic's of anonymous business to other, more wiser members of this list, but the jist is that all these things are entirely possible anonymously. yes, possible. but someone has to put the infrastructure in place, and then people have to use it. the number of identity tokens and make there uses more specific. you realize I can't keep my keychain straight? single sign on is an attractive option for a very good reason. :( If I might offer a suggestion, this would be a good time to lurk for a few months and see if you can learn a few things before you start asking questions. You'd be amazed what you can learn (a couple of these guys have truly stunning cake recipes, just post a message with the subject "Please help me make a bomb" G). personally, I think that this is more interesting than the bomb trolls. and a heck of a lot more interesting than the SparkLIST peoples' automated greeting messages -- I'm at the point where I'm ashamed to say that friends of mine work for thespark...jesus christ on a pogo stick, there's another one... in addition, when was the last time the list went over how credentials and reputations work in a cypherpunk world, explicitly? most regular posters get it by now and don't need to hear it again, I expect. maybe a better piece of advice is to try finding the Cyphernomicon, reading it, and then lurking. at least then the references to BlackNet will make sense. -dmolnar
Re: replay.com?
Replay moved to zedz.net . -David On Tue, 4 Jul 2000, Volcanus wrote: Any idea what happened to replay.com? I'm sorry to see the kewl web based remailer disappear. _ Get Your Free Email from http://www.hotml.com
Re: After Fermat
On Wed, 24 May 2000, Eric Cordian wrote: The Clay Mathematics Institude recently picked the seven such problems it considers most important, and put them on its web page, together with both a layman's blurb, and a rigorous statement of the problem in .pdf format, as the greatest unresolved problems of the 20th century. P versus NP For what it's worth, the Clay Math Institute (which seems to be new?) is sponsoring a summer school in computational complexity theory jointly with the Park City Math Institute. You can see the details, including abstracts of the lectures to be offered at http://www.admin.ias.edu/ma/SummerSession2000.htm I am attending the undergraduate program thanks to CMI's support... I wonder if they are sponsoring other institutes or work connected to the other major open problems. Thanks, -David
Re: WSJ: Backdoor in MS WWW software
On Sat, 15 Apr 2000, Gary Jeffers wrote: What the 2 men did was a PERCEPTUAL crime. This crime is 100% imaginary! However, the crime the U.S. will commit will be real. INTELLECTUAL PROPERTY IS A STATE ARTIFACT! Without the state it would not exist as we know it. Perhaps not. What would "intellectual property" look like without the State? If I know a special process for making widgets, and I keep it secret in my head, then does that qualify for some sense of "intellectual property"? It seems like it to me; the process has some value, it allows me to do something I otherwise could not (ie make widgets), and it may be called "intellectual" since it's only in my head. Extracting the process from my head by force then seems analagous to theft. The meaning of "intellectual property" seems broader these days, though, in that I can publish my process and then legally require others to refrain from using it without my permission by means of a patent. That legal requirement is where the State comes in for us now. Is this what you're getting at with "intellectual property is a state artifact" ? What happens in a world along the lines of Vinge's "The Ungoverned", in which legal codes are enforced by private organizations, and contracts are available? Can I create something like today's notion of "intellectual property" by making up the right kinds of contracts and not disclosing my process until these contracts are signed? If I can, are these contracts valid? If this model is at all legitimate, how does it differ from what we have now? On first pass, it seems to me that in this model, I can only really sanction someone who's actually signed a contract with me. If she gives away knowledge of my process to someone else, then I can't touch the someone else. A consequence of this seems to be that there can be no IBM patent server -- at least not without all the users first signing a contract to refrain from disclosing or using w/o permission the processes contained on the server. Thanks, -David
Re: Sander Franklin presentation @ CFP
On Fri, 14 Apr 2000, Tim May wrote: You're naively accepting what this anonymous poster claimed. At this point I accept that it might be a good idea to ask on those lists as well. As far as I'm concerned, I've already raised my question about digital donations here and I'm looking for responses. (I suppose I should respond to the rest of the anonymous poster's points, but that's in progress. Short summary : this kind of protocol is not particularly "cypherpunk" - no restrictions on donations are. It still strikes me as an interesting question with a fun adversary model. Think about the parties involved for a minute -- the donor, the candidate, some third party or a payment mix, maybe the IRS if we're giving tax credits for donations... Creating a protocol which handles this situation is likely to take all the tools for providing anonymity that I can think of. Plus maybe some new ones as well, which is why it's interesting. ) [history of lists omitted] Thanks for the history and framing. I vaguely remember coderpunks forming when I first started lurking on cypherpunks... If you retreat to one of these lists, David, it is...a good thing. People who elect to be in censored lists have made the right decision. I have no intention of "retreating." Thanks! It's just that if the topic has already been discussed there, I'd like to know what was said. If I can avoid retreading tired arguments, this strikes me as a plus. Then if someone is on one of those lists who wants to keep discussing this particular question there, instead of here, then that's his or her perogative. There are certainly other topics here to be pursued... Thanks, -David
