New stuff with Envelope Mail
I've done a bunch more work on Envelope Mail, as always, the latest info is at - http://gawth.com/bram/envelope_mail/ New is actual code, complete with test code. Plans are next to write a patch for BoboMail implementing the dummy version of the crypto API. I could use immediate help on the following things - A logo - I'm incapable of graphic design A non-dummy version of the crypto API - the dummy one makes it excruciatingly clear how the real one should work and gives a strong indication of how it might be implemented. I'd make the 'real' one myself, but, you know, you're not supposed to do that, and I'm trying to play nice, despite the crypto community being remarkably unhelpful in this regard. -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
Re: sniff tool that can crack SSL?
On Fri, 5 Jan 2001, Alex Alten wrote: I guess things would get real interesting if the private key to a trusted intermediate or root certificate authority got stolen and published. It might take a while to update all the browsers out there to not accept it as a valid signer of server certificates. Yeah, lots of web sites would start signing their own certificates because they'd see no reason to fork over the $700 or whatever it is to Verisign, then Verisign would start threatening to sue all of them for violating trade secrets and copyright on the root key. Ironically, it probably wouldn't have any effect on security whatsoever - you can MITM web sites just fine anyway and just make client connections unencrypted, hardly anyone would notice. The real security behind credit card transactions is in the difficulty of cashing in on a whole bunch of credit card numbers anonymously. -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
More Envelope Mail stuff
A bunch more stuff done to the Envelope Mail page, including - - Made separaate page of the encapsulated crypto problem, it's now at a state where academic cryptographers should be able to easily help out. - Created examples page - lots of little cleanups Check it out at http://gawth.com/bram/envelope_mail/ -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
Envelope Mail
I've set up a home page for Envelope Mail, and included feedback which I got from my last post (thanks everybody!) It's at - http://gawth.com/bram/envelope_mail/ Any and all additional feedback and offers to help would be much appreciated. In particular, it could use a logo :-) -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
Re: The problem with SSH2
On Wed, 27 Dec 2000, Theodore Y. Ts'o wrote: From: Bram Cohen [EMAIL PROTECTED] The problem is that if someone performs MITM on you, you get a warning saying 'I don't know who this is warning warning warning blah blah blah, would you like to give up connecting or just hope it isn't really a problem?' Of course, most people choose to hope the problem goes away - I've done this several times myself, sysadmins often forget to copy ssh keys between machines. In the first place, it only happens the first time you contact a particular host. It gets shown every time the host machine changes it's key, which has happened several times to me, on several unrelated machines, often without advance warning. In no cases was it actually a MITM attack. In the second, the message is a tad bit stronger than that. Maybe it should mention that if you ignore that message you could wind up having the same fate as Wil E. Coyote. In the third place, if you're using RSA authentication (which is far more convenient since you don't have to keep typing your password), the effects of a MITM attack are much reduced. Hardly anyone ever does that. Whether they *should* is irrelevant, they *don't*. Do note that SRP is patented technology. A claim has been made that it is has been freely licensed by Stanford. However, I haven't seen the letter myself, and it's not clear what the terms of the patent license are. I think the patent either hasn't been granted or has just recently been granted. My impression speaking to Tom Wu is that he is mainly interested in making the technology freely available, but it's probably best he comments on that. The fact that the SRP home page doesn't disclose that the fact that it is patented, and the author has in the past tried very hard to get people to use it without disclosing the patent status has always left a bad taste in my mouth, but your mileage and personal ethical standards (and some might say pet peeves, I grant that) may vary. I'm inclined to assume he's tried to promulgate it mostly because it's better technology. My personal recommendation to any such Linux distributors would be to get any kind of patent license agreement in signed, ink-on-paper first I think that would be an exceedingly overly cautious, one might even say wimpy, approach, especially if all that's included is the password file format and not the tools which use it. Failing that, it *really* isn't that hard to use shell scripts to rdist /etc/ssh/ssh_known_hosts files between all of your local machines. Anything involving shell scripts is just plain unacceptably hard to use for 99% of all computer users, and not worth the effort for most of the remaining myself included. -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
Re: IBM press release - encryption and authentication
On 14 Dec 2000, Nikita Borisov wrote: I think, though, that the "parallelization-friendliness" of the result is much more interesting than being able to encrypt and MAC at the same time. Encrypt and MAC together are pretty useful too - it can result in a factor of two improvement in speed on a single CPU system. There's an improved version of the IBM mode at http://csrc.nist.gov/encryption/aes/modes/ in the 'OCB mode' paper. Clearly, it's a good idea to wait for new developments to stop happening to use the new modes. -Bram Cohen "Markets can remain irrational longer than you can remain solvent" -- John Maynard Keynes
Re: IBM press release - encryption and authentication
On Sun, 10 Dec 2000, Rich Salz wrote: No word, of course, on how the thing actually works, or whether they intend to patent it. Not so. Search your nearest IETF internet-drafts repository for draft-jutla-ietf-ipsec-esp-iapm-00.txt I was complaining about the total lack of technical detail in the press release specifically. Thanks for the pointer. -Bram Cohen
Re: IBM press release - encryption and authentication
On Sun, 10 Dec 2000, Rodney Thayer wrote: P.s, when he spoke at Stanford I asked about patents and he said it was patented, and he said NIST is trying to get them to put it in the public domain. There are slides for it online at http://csrc.nist.gov/encryption/aes/modes/slides-jutla/index.htm it's not hard to figure it out just from the slides - there are actually two methods given, one which requires an extra lg(n) encryptions and one which requires two extra encryptions but has a bunch of modular arithmetic. Rijndael is so fast I suspect the second one might not prove all that useful. It really does, as advertized, offer MAC for almost no overhead, and parallelization for free. It would be a shame for these modes to not get used because of stupid patent bullshit. -Bram Cohen (who thinks doing the xors as a gray code instead of binary countup was a nice touch.)
Re: UK Sunday Times: Steal the face right off your head
On Mon, 11 Dec 2000, Ben Laurie wrote: "R. A. Hettinga" wrote: In South Africa, where fingerprint security has been introduced at some experimental prisons, inmates recently tried to cut off the hands of their guards to enter protected gates. What did I tell ya? The US military is switching over to biometrics, including fingerprints and cornea scans. One of the reasons they decided to do the switch is that newer technologies ensure that the item in front of the scanner is in fact alive :) -Bram Cohen
Re: migration paradigm (was: Is PGP broken?)
On Tue, 5 Dec 2000, David Honig wrote: Is there a reason not to use AES block cipher in a hashing mode if you need a secure digest of some data? Hashing modes of block ciphers require a re-key for every block, and hence are really, really slow. -Bram Cohen
Re: IBM press release - encryption and authentication
On Thu, 7 Dec 2000, P.J. Ponder wrote: from: http://www.ibm.com/news/2000/11/30.phtml IBM develops algorithm that encrypts and authenticates simultaneously No word, of course, on how the thing actually works, or whether they intend to patent it. A note to the clueful about it being 'parellelizable' - almost all crypto stuff can be parallelized by putting different tasks on different processors, since the vast majority of crypto applications have multiple tasks on a server going on at once. Parallelism works well for things which require little interaction, and not at all for things which require a lot. -Bram Cohen [Parallelism is NOT a trivial property. The maximum data rate you can sustain depends a lot on whether or not an algorithm can be implemented in parallel in hardware. Some algorithms, like various keyed hashes, have bad properties in this regard. Claiming this isn't important is just not correct -- for many applications it is. --Perry]
Re: IBM press release - encryption and authentication
On Sun, 10 Dec 2000, Paulo S. L. M. Barreto wrote: A description of Jutla's mode of operation is available from NIST's AES site. And yes, IBM has filed patent for it. Note to cryptographers of the world - there are two reasons to patent an algorithm - 1) to keep anyone else from patenting it and release it into the public domain. 2) to keep anyone from using it If you're not doing 1, you're doing 2. -Bram Cohen
Re: /. Yahoo delivers encrypted email
On Mon, 4 Dec 2000 [EMAIL PROTECTED] wrote: Yahoo's new system works like this: Once a message is composed, it travels, unencrypted, to Yahoo, So feel no fear in sending anything you wouldn't mind being read before it's encrypted? I'm surprised AOL isn't offering this "security feature" as well ... I feel safer already :~) To be fair, Yahoo handles so much mail that the CPU power necessary to start SSL sessions for all of them gets pretty expensive. They'll probably start doing end-to-end encryption when the prices of that drop lower, Moore's law and all that. -Bram Cohen
Re: migration paradigm (was: Is PGP broken?)
On Mon, 4 Dec 2000, William Allen Simpson wrote: We could use the excuse of AES implementation to foster a move to a new common denominator. AES is silly without an equivalently good secure hash function, which we don't have right now. [SHA-2 looks pretty good. What's your problem with it? --Perry] We already have too many common denominators. I'm waiting for something to stop looking like an experiment to actually start advocating use of a particular crypto application. -Bram Cohen
Re: migration paradigm (was: Is PGP broken?)
On Mon, 4 Dec 2000, Bram Cohen wrote: [SHA-2 looks pretty good. What's your problem with it? --Perry] It's slow. It's fast enough for most applications, but then again so is 3DES - either you care about speed or you don't, and if you do, SHA2 just doesn't rank up there with Rijndael. -Bram Cohen
RE: Is PGP broken?
On Mon, 4 Dec 2000, Ian Brown wrote: Come to think of it, there are some tricky issues with regards to crypto on mailing lists, it might make sense to have a X-crypto-originator [EMAIL PROTECTED] line in the headers to specify that the crypto information contained in that piece of mail applies to the address [EMAIL PROTECTED] - otherwise there's no clear way of unraveling all the possible mixes of from, to, and reply-to headers which could possibly be sent to a mailing list. The recipient would probably ignore the mail headers and use the userID(s) in the public key certificate included in the message. To clarify - I think doing things based on PGP userIDs is unworkable, and would like to do everything based on email addresses. -Bram Cohen
Re: Is PGP broken?
On Wed, 29 Nov 2000, Ian BROWN wrote: Bram Cohen wrote: What we really need is a system which just stops passive attacks. The best idea I've come up with so far is for all outgoing messages to have a public key attached, and if you have the public key of an email address you're sending to you use it Indeed -- this is one of the current advantages of S/MIME over OpenPGP. Absolutely no reason why any PGP implementation shouldn't do it. This also allows you to do perfect forward secrecy: generate new short-life encryption key pairs for each message, sign the public key with your longer-lived signature key, and include it in your message for the reply. See http://www.ietf.org/internet-drafts/draft-brown-pgp-pfs-01.txt for an attempt by Adam Back, Ben Laurie and myself to standardise this and other PFS techniques for OpenPGP. Good to know someone's done work along these lines. A problem with including a public key with every plaintext message is that it isn't very discreet - actually looks kind of ugly in some peoples's email clients. This could be changed by making a header line saying something like X-accepts-crypto, and have other mailers only send their keys to addresses they've formerly gotten mail with that header line from. Come to think of it, there are some tricky issues with regards to crypto on mailing lists, it might make sense to have a X-crypto-originator [EMAIL PROTECTED] line in the headers to specify that the crypto information contained in that piece of mail applies to the address [EMAIL PROTECTED] - otherwise there's no clear way of unraveling all the possible mixes of from, to, and reply-to headers which could possibly be sent to a mailing list. -Bram Cohen
Re: Is PGP broken?
On Sun, 3 Dec 2000, Ben Laurie wrote: Bram Cohen wrote: Come to think of it, there are some tricky issues with regards to crypto on mailing lists, it might make sense to have a X-crypto-originator [EMAIL PROTECTED] line in the headers to specify that the crypto information contained in that piece of mail applies to the address [EMAIL PROTECTED] - otherwise there's no clear way of unraveling all the possible mixes of from, to, and reply-to headers which could possibly be sent to a mailing list. Umm. PGP keys are largely self-identifying, at least in this case. It wouldn't really matter how the short-lived key arrived, the fact that its signatory is the guy you are about to email is the interesting thing. Who cares who delivered it to you, or how? If I recieve mail from a mailing list, it potentially might have info about both how to encrypt mail sent to the sender, and how to encrypt mail sent to the list - it really should be able to include both, and specify which is which. -Bram Cohen [Personally, I'm not sure it is worthwhile worrying about how to encrypt mail to a large mailing list -- a secret known by more than a couple of people is never secret for long. Signatures on list mail are another matter. --Perry]
Re: Is PGP broken?
On Tue, 28 Nov 2000, Russell Nelson wrote: Is it just me, or is PGP broken? I don't mean any particular version of PGP -- I mean the fact that there are multiple versions of PGP which generate incompatible cryptography. I'd say that's an accurate assesment. Presuming that I'm right, is anyone attempting to fix PGP? Not that I've heard of. Not to mention anything about PGP keyservers, or the utter and complete absence of anybody doing point-source PGP signing. Yeah, the whole system looks none too scaleable. What we really need is a system which just stops passive attacks. The best idea I've come up with so far is for all outgoing messages to have a public key attached, and if you have the public key of an email address you're sending to you use it. If you receive a different public key than one you saw before, you overwrite the old one. This doesn't stop active attacks at all, but would be very easy to use. The worst that could really happen is that I lose my key info, construct new stuff, and next time Russ sends me mail I respond 'sorry, but I lost my old private key, please send that last message again'. The only real gotcha is that the first message is unencrypted, and that's not a big deal, especially when you know about it and always send a 'checking to make sure I got your address right' message to start things off. -Bram Cohen
Re: Schneier: Why Digital Signatures are not Signatures (was Re: CRYPTO-GRAM, November 15, 2000)
On Thu, 16 Nov 2000, John David Galt wrote: As the US banking system (and especially the bank clearinghouses controlled by the Federal Reserve system) has gone electronic, all the banks I know of have stopped bothering to verify the signatures on checks, and similarly those on credit- and debit-card drafts. Getting them to start using digital signatures would be a big improvement over the current wide-open situation. True, although a simpler (albeit less secure) measure would be to increase the length of the tracking number so that it's unguessable (it may already be that way - if so, never mind.) -Bram Cohen
Re: Rijndael among the weakest of the AES candidates
On 2 Oct 2000, lcs Mixmaster Remailer wrote: Pure cipher strength actually played very little role in the selection. All the ciphers were judged adequately strong. Rijndael's main advantages were in practical implementation issues, plus resistance to various hardware failures. Rijndael has attacks on 6 or 7 out of the 10 rounds for 128 bits keys; 7 out of 12 rounds for 192 bit keys; and 7, 8 or 9 out of 14 rounds for 256 bit keys (Rijndael uses more rounds for larger keys). The attacks against larger numbers of rounds require prohibitive levels of work. For those whose primary interest in AES is high security, the emphasis might have been placed elsewhere. Rather than choosing a cipher with merely an "adequate" level of security, they would prefer that the choice had been made from among those ciphers judged highest in security: MARS, Twofish and Serpent. Choosing from among these ciphers by similar criteria of efficiency would probably have led to Twofish. According to the NIST report, Rijndael's creators came up with an attack against 6 rounds, and viewed that as not terribly worrisome. The existence of a very impractical attack against 7 rounds hardly changes things much, especially in light of Rijndael being very simple and hence relatively easy to analyze. -Bram Cohen
Re: Oh for a decently encrypted mobile phone...
On Thu, 14 Sep 2000, Enzo Michelangeli wrote: http://www.the-times.co.uk/news/pages/sti/2000/09/10/stinwenws01007.html SOLDIERS are having to use insecure mobile phones to communicate in battlefield exercises because, they say, the army's radio communications system is so unreliable. Senior commanders be-lieve that the reliability of mobile phones outweighs the increased risk of conversations being intercepted. Wouldn't it be ironic if they resort to buying a bunch of stariums ... -Bram Cohen [That would require that Stariums actually appear on the market at some point. --Perry]
Re: Comcast@Home bans VPNs
On Thu, 24 Aug 2000, Phil Karn wrote: I've been saying for some time that we need a IP-over-SSL tunneling protocol standard. ISPs would *never* dare block TCP port 443, since as we all know the only important Internet application is to let people buy stuff online... You can tunnel PPP over SSH ... -Bram Cohen
The difficulty of making non-hashable tokens
At, I believe, the cypherpunks physical meeting before last I gave a technique for making tokens which can be compared but not canonicalized. Rather than try to define this precisely, which is rather hard to follow, I'll give my (broken) technique, and explain what's wrong with it. A common prime p is universally settled on. To generate a token, Alice picks some random values b and c and constructs the ordered pair (c^b (mod p), b (mod p-1)). Every time she wants to use it again, she picks some random value r and brings the first number to the r power and multiplies the second number by r. To compare two tokens (c^b, b) and (d^e, e), she computes (c^b)^e and (d^e)^b and compares them - they'll be the same if and only if c and d are equal. The problem with that scheme (and I'm a little embarassed for not having seen this immediately) is that it's possible to compute 1/b (mod p-1) and compute c^b to that power, resulting in c, which can of course be hashed. I've been trying to come up with a fixed version and cannot for the life of me find one. I'm inclined at this point to conjecture that it's impossible, which makes it by far the most plausible-sounding yet probably impossible cryptographic primitive I know of. If anybody can come up with a non-hashable tokens technique I'll be very impressed. If anybody can find a proof that there is none I'll be even more impressed (since proving things impossible seems to be out of the reach of complexity theory these days.) Just thought I'd throw that out. Had to vent. Not being able to find one is getting on my nerves. -Bram Cohen
Re: The difficulty of making non-hashable tokens
To clarify what I mean by 'non-hashable token' - There is a format for
identifiers, and a function for 'scrambling' them, so that they look very
different, but there's a function which can accurately compare two
identifiers ('tokens') regardless of how scrambled they are. By
'non-hashable' I mean that given a set of n tokens, there should be no
algorithm for determining if there's a pair of identical ones better than
doing all n^2 - n comparisons.
An example motivation: Say you have a very large database of user logins,
and you would like for users to be able to give you their history and for
you to verify it, but you're worried about an attacker getting access to
your database and analyzing it. What you do then is you give each user an
unhashable token as an identifier, and whenever you store login records
you store a login date and a scrambled version of the login id. Then, if
someone wants to demonstrate their login history they send you the dates
and their id and you can verify it, but analyzing the database as a whole
requires a lot of work.
Well, so that's not a particularly strong motivation, but hopefully it
clarifies.
-Bram Cohen
Re: A non-parellelizable form of hashcash
On 26 Mar 2000, David A. Wagner wrote: Your technique appears to be a more complicated -- but closely related -- variant of the construction given in the following paper: ``Time-lock puzzles and timed-release Crypto'', R. Rivest, A. Shamir, and D. Wagner, MIT LCS tech report TR-684, February 1996. http://www.cs.berkeley.edu/~daw/papers/timelock.ps Yep, that it is. I'm a little embarassed for not having already known about that one. I'm not sure if there is any reason to prefer either scheme over the other on security grounds. If the two have equivalent security, then the simplicity of the RSW construction looks appealing. Any thoughts on the two schemes' relationship? I figured out the simpler construction, but for some reason thought it was insecure, so I came up with the more complicated one. I suspect that there are the equivalent of chosen plaintext and ciphertext attacks against the simpler scheme - that is, if Alice acts as an oracle for computing a^(2^b), then Bob can find p and q. This would imply that the more complicated technique is (marginally) more secure. There's no obvious way of factoring n using the oracle though. Other than that, they look about the same - there wouldn't be any noticeable difference in performance between the two algorithms. Mostly I just find the mess which the expansion of f(x)^2 - 2 becomes after a few iterations very comforting. -Bram Cohen
A recurrence relation question
This isn't obviously crypto-related, but I'll explain if there's a simple solution. Given that f(x+1) = f(x) * f(x) + c, does anybody know how to express f(x) in closed form? -Bram Cohen
Re: A non-parellelizable form of hashcash
It turns out my memory of what it's difficult to find square roots modulo was wrong. The fixed version is below. Alice wants to force Bob to do w 'units' of computation in such a way that he can't do the computation in parallel and she can verify the result expending relatively little resources. Alice first picks primes p and q, both congruent to 3 mod 4, and finds their product, N. She will be able to reuse N any number of times so long as she keeps p and q secret. For a specific challenge, Alice picks secret value s, less than N. She then computes s + 1/s (mod N) and sends it and N to Bob. Bob can't compute s because that would involve taking a square root modulo N, which is just as difficult as factoring N. Alice's challenge to Bob is to compute f(w), where f(n+1) = (f(n))^2 - 2 (mod N) and f(0) = s + 1/s (mod N) She can compute f(w) quickly using the formula f(n) = s^(2^n) + 1/(s^(2^n)) (mod N) which can be easily verified using induction. To compute s^(2^n) (mod N) quickly, Alice first finds it's value mod p and mod q. To find s^(2^n) mod p, she first computes e = 2^n (mod p-1) and then computes s^e (mod p), which is equal to s^(2^n) (mod p) because of the basic number theory theorem s^(p-1) = 1 (mod p) Not only does this method prevent Bob from doing parallel computation, it allows Alice to control very precisely the amount of work he must perform. Public key techniques always feel guided by an unseen hand. There is clearly an underlying theory we have yet to discover. -Bram Cohen
Looking for a cryptographic primitive
Does anybody know of a field in which a + b and a * b can be computed quickly but (and this is important) it's computationally intractable to compute the additive inverse of a? I need it for a technique I'm working on. -Bram [Bram: All fields of n elements are isomorphic to all other fields of n elements, and in any of the fields I'm familiar with, it is trivial to compute an additive (or multiplicative) inverse. Given this, I suspect what you want to do is rather hard -- you would have to conceal the isomorphism to, say, GF(n) somehow. Any readers have any other insights here? --Perry]
Re: Looking for a cryptographic primitive
On Thu, 9 Mar 2000, bram wrote: Does anybody know of a field in which a + b and a * b can be computed quickly but (and this is important) it's computationally intractable to compute the additive inverse of a? [Bram: All fields of n elements are isomorphic to all other fields of n elements I'm not using the additive or multiplicative identity, maybe eleminating the requirement for those increases the number of mathematical structures available? -Bram
Re: [PGP]: PGP 6.5.2 Random Number Generator (RNG) support
[This is getting tiresome. Unless someone has something *new* to say, this is the end of the thread. --pm] On 3 Feb 2000, lcs Mixmaster Remailer wrote: On Wed, 2 Feb 2000, Martin Minow wrote: http://www.cryptography.com/intelRNG.pdf. The one problem I have with the RNG, based on my reading of the analysis, is that programmers cannot access the "raw" bitstream, only the stream after the "digital post-processing" that converts the bitstream into a stream of balanced 1 and 0 bits. Why do you want this? The post-processing is a simple Von Neumann bias remover that looks for 0-1 and 1-0 transitions (actually slightly more complex, looking at triplets of bits rather than pairs, but the same idea). Call me a conspiracy theorist if you will, but a test which reveals some internal structure to a system gives me a much more warm and fuzzy feeling than one which simply concludes 'It seems to work perfectly.' It may be silly, but I tend to think people are much less likely to fake the former than the latter. The benefit you would gain from being able to see this biased data must be balanced against the harm that will result from some people accidentally using it in the belief that it is secure. Don't tell the kids about contraception either. It'll make them fuck like bunnies. The work on the studying the output of Intel's RNG has only had accessed to the post-processed output, plus I believe a file directly from Intel which was claimed to be unprocessed output. Yeah ... right. The post-processed output was processed via the Von Neumann bias remover, and that's the way the data comes off the chip. It is entirely appropriate to analyze such output in looking at the quality of the randomness produced by the chip. From http://www.cryptography.com/intelRNG.pdf quote For this review, Cryptography Research performed a series of tests and evaluated the results of experiments performed by Intel. Raw data and design specifications for the analysis were provided by Intel. /quote Does anybody know if Cryptography Research is re-running those tests on data from an actual chip now? It's not like publishing a spec magically makes all the tests which should be done with it happen, libertarian precepts to the contrary. If Intel wants people to trust them, they should quit acting like they're covering for bad engineering. So, what would satisfy you? Kocher has published the theory of the device, but that's not good enough. What more do you need? I'd like for the theory to be published with Intel's name on it, not Kocher's, which someone else pointed out hasn't happened yet. Short of this level of monitoring, it is impossible to be sure that the chip in your computer is free of backdoors (and even then you have to worry about somebody sneaking into your house and swapping CPU boards on you). Face it: no matter what they do, people are going to bitch, just like they do at every other crypto or security company in the industry. There's no satisfying some people. Ad hominen attacks and claims of unfalsifiability being reasonable aside, there is something which would make me happy. Chip manufacturers reverse-engineer each other's stuff all the time. I'd like one of Intel's competitors to publically state 'We took apart a Pentium III and it's RNG really works the way Intel says.' -Bram
Re: [PGP]: PGP 6.5.2 Random Number Generator (RNG) support
On Wed, 2 Feb 2000, Martin Minow wrote: http://www.cryptography.com/intelRNG.pdf. The one problem I have with the RNG, based on my reading of the analysis, is that programmers cannot access the "raw" bitstream, only the stream after the "digital post-processing" that converts the bitstream into a stream of balanced 1 and 0 bits. It not only does that, it hashes the thing using sha-1. For all we know, the thing might be producing unacceptably small amounts of entropy for crypto purposes but large enough amounts that it hardly ever repeats. The work on the studying the output of Intel's RNG has only had accessed to the post-processed output, plus I believe a file directly from Intel which was claimed to be unprocessed output. Yeah ... right. If Intel wants people to trust them, they should quit acting like they're coving for bad engineering. -Bram
Re: legal status of RC4
First off, anybody could make a cipher called 'RC7'. RC7 isn't trademarked, and 'RC' as a prefix isn't either. It's the same reason why we have an MP4 unrelated to MP3, and why Intel makes Pentiums instead of 586's. I'm a little confused about what exactly constitutes 'causing customer confusion' with regards to using the term RC4. If I publish something clearly labelled 'Bram's crypto library' and list RC4 as one of the ciphers supported, there's no implication of anything coming from RSA, it comes from Bram. There's always the trademark dilution claim, although my understanding is that only applies to 'famous' trademarks, which RC4 clearly isn't, and the proper legalese response to a claim of dilution can be roughly translated into plain english as 'blow me'. -Bram
Re: Blue Spike and Digital Watermarking with Giovanni
On Sat, 15 Jan 2000, Eugene Leitl wrote: Joe Sixpack also doesn't believe that color laser copiers leave an unique signature on each copy, allowing you to trace the copy to an individual device. Nevertheless these are there, and can be evaluated if need arises. (Just try distributing a few xeroxed $100 bills, and time how long it takes until the feds knock on your door). Do you have a reference for that? [There have been SO many articles on this recently, including a long thread on RISKS: the summary being that it is absolutely true. --Perry] -Bram
Re: DeCSS Court Hearing Report
On Tue, 4 Jan 2000, Ray Hirschfeld wrote: Date: Mon, 3 Jan 2000 18:43:52 -0800 (PST) From: bram [EMAIL PROTECTED] I'm a little confused. Are you saying that as of October it will be legal to do any amount of reverse-engineering, publishing, and writing to APIs you want without violating the original author's copyright? Does that mean that, say, Bsafe will have the rug yanked out from under it by allowing alternate non-infringing implementations? No, October 28, 2000 is when the act of circumventing an effective technological measure becomes a violation (with exceptions for fair use, crypto research, reverse engineering, law enforcement, etc.). Until then it is legal under the new copyright law. Circumvention for interoperability purposes is already permitted, but not as broadly as you state. Specifically, is it, and will it be, legal to create an alternate implementation of an API you didn't write? This may be re-opening an old can of worms, but I couldn't help but notice the extreme looseness of the encryption research exemption - (1) Definitions. - For purposes of this subsection - (A) the term ''encryption research'' means activities necessary to identify and analyze flaws and vulnerabilities of encryption technologies applied to copyrighted works, if these activities are conducted to advance the state of knowledge in the field of encryption technology or to assist in the development of encryption products; and (B) the term ''encryption technology'' means the scrambling and descrambling of information using mathematical formulas or algorithms. Does breaking a proprietary algorithm 'advance the state of knowledge in the field of encryption technology'? Is breaking protocols, with no breaking of algorithms (as happened to ICQ) covered under (B)? Is it illegal to point out that a product sends a challenge/response of some trivial secret message before sending everything cleartext, since that neither deals with the scrambling of information using mathematical formulas or advances the state of encryption technology? -Bram
Re: DeCSS Court Hearing Report
On Mon, 3 Jan 2000, Ray Hirschfeld wrote: Date: Wed, 29 Dec 1999 20:06:32 -0800 From: Lucky Green [EMAIL PROTECTED] but it appears that an argument based on copyright would have been a better approach. I conjecture they did it this way because the prohibition against circumventing effective technological measures that was added to U.S. copyright law in October 1998 (as part of the Digital Millennium Copyright Act, which implemented the WIPO Copyright Treaty) does not take effect until October 28, 2000. Cf. Title 17, Chapter 12. The section against trafficking in devices seems like it might apply, though, and doesn't seem to be subject to the two-year delay. But reverse engineering for interoperability purposes is explicitly permitted, and making information so obtained available to others for interoperability purposes also does not constitute infringement under the new law (cf. Sec. 1201 (f) (3)). I'm a little confused. Are you saying that as of October it will be legal to do any amount of reverse-engineering, publishing, and writing to APIs you want without violating the original author's copyright? Does that mean that, say, Bsafe will have the rug yanked out from under it by allowing alternate non-infringing implementations? (Doesn't the RSA patent expire in October as well? That's a mighty funny coincidence ... for anyone other than RSA, anyhow.) -Bram
Re: PGP on an e-commerce site
On Mon, 3 Jan 2000, Dave Del Torto wrote: Here the plot thickens: If the only two sigs on the key at CDNOW are the key-owner's sig and David's, then the ability of any CDNOW customer to trust the key's security is based on David's "trustability quotient" as well as the ability of CDNOW to prevent spoofing of its webpages. Giving CDNOW the benefit of the doubt in this case, this means that David has become the defacto PGP Certificate Authority for CDNOW, which implies more liability than he's probably willing to take on personally, so it may be that he's a CDNOW employee and therefore has some legal protections (one hopes it's in his contract). Does it? I'm skeptical as to whether there's ever been a strong legal opinion written on this matter, so it's unclear what a court would say if someone tried to sue someone else who's PGP signature they relied on. I would hope that a court would rule that with the absence of clear legal wording in a 'signature' which is really just a technical artifact, it should be treated as rumor. Lack of clear legal meaning is a definite weakness of current public key systems. It may seem boring and tedious to work out detailed legal meanings of what all the public key technical artifacts mean, but unless those artifacts refer to specific meanings themselves, a court will make them up later, and will probably make them up in a way which the original authors (meaning you) aren't happy with. -Bram
Re: Semantic Forests, from CWD (fwd)
Maybe I'm just dense, but what's with the emphasis on phone conversations? Voice processing is flaky at best, and computationally expensive regardless. Faxes, on the other hand, can be OCR'ed easily, and email is in plaintext to begin with. -Bram
Re: ECHELON Watch
On 16 Nov 1999, Perry E. Metzger wrote: ACLU today launched a new web site www.echelonwatch.org, which is designed to focus public attention on the threats to civil liberties which are posed by the massive international communications surveillance program sometimes known by the code name ECHELON. The attached release gives more details on the site. I find the phrasing of this site curious - the impression that I got from the last cypherpunks meeting is that echelon is mostly used for industrial/government espionage - the number of reports it generates (two a day if my memory servers) are just too small to say much about individuals. Besides, violating individual rights is the FBI's job. -Bram
Re: Flannery on Cayley-Purser/RSA
On Thu, 11 Nov 1999, Jim Gillogly wrote: Wei Dai writes: Is CP completely broken, or is there some variant of it that is still unbroken? It's completely broken. So what on earth was that claim of mathematically showing it was as strong as RSA about? If breaking it doesn't result in a break of RSA, it must have been of the typical voodoo hand-waving flavor. That's not to denigrate Flannery's work: she started from the assumption that the algorithm she'd been handed to work on was O.K. and did some good work optimizing its implementation. That doesn't make the algorithm any more useful. -Bram
Re: Almost-Everywhere Superiority for Quantum Computing
On Sun, 17 Oct 1999, Russell Nelson wrote: Okay, then can I ask a silly question (I prefer to contribute good answers, but in this case hopefully the question is good enough)? If quantum computers make brute-force cryptanalysis tasks easier, don't they also make brute-force cryptographic tasks easier as well? Put another way, is there something special about quantum computers that is different from Intel's next process shrink? That is, apart from the havoc it plays with key lifetime expectations? I very strongly suspect that if the encrypter and decrypter are given the same oracle, then the encrypter can always force the decrypter to have to use vastly more operation of the oracle to do break a cipher than are required to encrypt it, even with essentially normal key lengths. I don't know of any attempts to create ciphers which rely on quantum computation for efficient encryption which are strong against quantum decryption techniques, although I'll bet you could get the right people to speculate about it. -Bram
Re: Ecash without a mint, or - making anonymous payments practical
On Mon, 27 Sep 1999 [EMAIL PROTECTED] wrote: One small final comment: physical cash is not really anonymous (bills have serial numbers, and certainly coins may contain secret marks. Why? I believe at least part of the reason is to make heists difficult - Places which have loads of nice new bills almost always have them with sequential serial numbers. There have been many cases of a huge heist getting pulled off successfully and then the robbers were unable to dispose of the cash they got because it was too easy to trace. -Bram
Re: Ecash without a mint
On Mon, 20 Sep 1999, Adam Back wrote: - is the ZK proof interactive? If so this would place communication restrictions on spending -- payer and payee would need to be simultaneously online. Interactive ZK proofs can be made non-interactive by generating an encoding of the information offered by the prover, and using the bits of the secure hash of that as the challenges by the provee. -Bram
Re: Summary re: /dev/random
On Mon, 2 Aug 1999 [EMAIL PROTECTED] wrote: Linux's /dev/random uses a very different design, in that it uses a large pool to store the entropy. As long as you have enough entropy (i.e., you don't overdraw on the pool's entropy), /dev/random isn't relying on the cryptographic properties as much as Yarrow does. The problem is that the one bit of entropy for one bit of output rule creates the potential for lots of denial of service attacks where the entropy gets used up. There is no application which needs that amount of entropy. John Kelsey put it pretty well earlier this thread: Suppose God, in a fit of budget-consciouness, decides to get rid of all this wasteful hardware for generating random numbers that are necessary for quantum mechanics, and instead replaces them with a PRNG with a 256-bit seed. In this case, all hardware noise sources are ultimately tapping into this same seed and PRNG. How will you, or anyone, tell the difference? Most people don't know the fine-grained distinction between /dev/random and /dev/urandom. In fact, I'll bet most developers don't even know that /dev/urandom exists. As a result, lots of programs which require very large amounts of random numbers suck data out of /dev/random, creating a very large potential for unknown numbers of present and future problems. This entire class of problems can be eliminated completely by altering /dev/random to only block at bootup until it has enough entropy (or not at all if there was some stored on disk) and thereafter to spit out data as soon as it's requested. The complete threat model for RNG's, admittedly, has a number of attacks which seem very impractical under current circumstances, but since those attacks can be completely eliminated now prudence indicates doing so. That way, when circumstances arise in which one of those attacks is practical, we can make a little academic note which nobody cares about for it, rather than having to deal with a disaster. The other reason for changing the way /dev/random currently works is that the long output version of RIPEMD160 would make it just plain faster, since it would halve the amount of hashing done per byte of output. The goal is to make it so that any time someone wants random numbers they can go to /dev/random, with no required studying of entropy and threat models and all that yadda yadda yadda which most developers will rightfully recoil from getting into when all they want is a few random bytes. -Bram
Re: Proposal (was Summary re: /dev/random)
On Sun, 1 Aug 1999, Sandy Harris wrote: The question, then is how best to make it into a two-stage design. Mainly, choose a block cipher and modify the hashing to suit. No, block ciphers are weak against related-key attacks, which happen all over the place in the threat model on SRNGs. The only real problem with the algorithm Yarrow uses is that it doesn't rehash the internal state after every chunk of output, which is sort of like using a hash algorithm as an encryption algorithm. The way to fix that completely is to rehash the internal pool state after every output and use different hash algorithms for the internal hashing and the output derivation. Since RIPEMD-160 has a version with an output twice as long, it would make sense to use that for output derivation (a significant performance win, since it halves the amount of hashing which has to be done.) and SHA-1 for internal mixing. I think the 160 bit safety involved in both SHA-1 and RIPEMD-160 will continue to be excessive for many years to come, so there's no reason to worry about it being 'too small'. -Bram
Re: Summary re: /dev/random
On Mon, 2 Aug 1999, Anonymous wrote: Disagree. /dev/random in cryptographic mode should be adequate as long as the machine is secured. If the machine is attacked to grab PRNG state the attacker can probably weaken the code. No, /dev/random's propensity to block can be unacceptable, especially for machines which don't have a source of entropy available. If the gateway machine is vulnerable to attacks which get root access, that is a serious weakness, but no work on the RNG can fix it. If not, then any decent cryptographically strong PRNG is fully adequate. No one has shown any value whatsoever for large entropy pools in this circumstance. Right now, everything which collects entropy has to be run as root or in the kernal, which is uncomfortable from a security standpoint. I disagree that bad entropy attacks are unrealistic - if a machine is running several different sources of entropy, getting information from god knows what source, it's quite possible one of them could be made by external forces to start spewing controlled data into the pool, and if you have a machine which, for example, is running a web server which isn't being hit by anyone but the attacker, and that web server is the only thing reading data out of /dev/random, suddenly an attack looks quite possible. This is especially true for possible future sources of entropy where, for example, some sysadmin might figure 'I'll just spew the traffic logs into /dev/random, it's the only source of randomness I have, and it's pretty random.' As things stand, that would leave the system much more wide-open than it would have to be. Yarrow does not use a block cipher. In PRNG mode, it is simply an iterated SHA-1 hash, with the hash output provided as the RNG output. It hashes a 20-byte seed, then hashes the previous 20 bytes of output to get the new 20 bytes of output. Every so often it updates the seed to be a new hash output value. That isn't quite accurate, but the basic point is that Yarrow is based on a hash algorithm as a primitive, and any hash algorithm could be substituted in there. Further work on figuring out what core trickery should be at the heart of the randomness source is unnecessary, especially since other work on the same problem has come up with essentially the same algorithm. Continue discussions on cryptography list, focussing on the hardest problem: acquiring and estimating entropy. This may be the hardest problem, but it is not the most important one, especially not for FreeS/WAN use. Mis-estimates of entropy are not crucial for this purpose. FreeS/WAN does not need "true" entropy and the current design of /dev/random does a soft fallback from true RNG to pseudo RNG, which is perfect for FreeS/WAN. No, this is actually the biggest gaping hole in the entire system - if the randomness source starts spewing after only getting 40 bits of entropy then it's wide open to attack, regardless of how much whitening it does on the output. The iterative guessing attack is being overstated here in terms of its practical significance. The root privileges which are necessary to snoop the RNG state will also allow for more malicious actions that completely compromise security. The way to diddle with RNG state is to mess with it's sources, not by directly looking inside the state. Attacks of that form, even if they aren't 'practical' now, could easily become practical in the future. -Bram
Re: depleting the random number generator
On Sun, 25 Jul 1999, John Kelsey wrote: Has anyone looked at this from a cryptanalytic point of view? I think there are chosen-input attacks available if you do this in the straightforward way. That is, if I get control over some of your inputs, I may be able to alternate looking at your outputs and sending in new inputs, and mount an attack that isn't possible at all against RC4 as it's normally used. (This comes out of conversations with Jon Callas, Dave Wagner, and Niels Ferguson, from a time when I considered designing a Yarrow-variant using RC4 as the underlying engine.) I thought about building SRNG's from several different cryptographic primitives, and came to the conclusion that the chosen-entropy attacks force it to be based on a secure hash. Since the design I figured out looks very much like yarrow, we probably had thoughts along the same lines. This isn't a bad idea, but I'd be careful about assuming that those times hold much entropy. After all, a given piece of code which has thirty calls to the PRNG probably runs in about the same amount of time every time, barring disk or network I/O. A lot of things include less entropy than one might assume. For example, keystrokes contain essentially no entropy based on what letter was hit, and the number of bits of entropy their timing includes is approximately the logarithm of the number of time ticks since the last keystroke. (which means, interestingly enough, that you can get faster entropy harvesting by having a more precise clock.) -Bram
Re: depleting the random number generator
On Mon, 26 Jul 1999, James A. Donald wrote: Oh dear! This suggestion worries me. Is it reasonable to expect this arrangement to be secure against e.g. chosen-entropy attacks? Yes: If the attacker knows exactly when the packets arrive (which he cannot) this cannot give him any additional knowledge about the state. The threat model for yarrow and other SRNG's is that the attacker can not only tell when entropy is coming in, but control it's contents as well. The idea is to build something which only fails if the attacker both knows the state of the pool at some point and manages to control all attempted reseedings. -Bram
Re: depleting the random number generator
On Mon, 19 Jul 1999, Ben Laurie wrote: The brief summary of the above is that it's possible to simply replace /dev/random with something which doesn't deplete entropy and the problem will go away. And yes, it is possible to do that in a secure manner. So what you are saying is that you'd be happy to run your server forever on an inital charge of 128 bits of entropy and no more randomness ever? Really? Well, I simplified a bit - it's a good idea to mix in more entropy whenever it's available just for good measure, and pool it to be introduced in large enough chunks to prevent continuation attacks, but the short answer is yes. -Bram
Re: depleting the random number generator
On Sat, 17 Jul 1999, Eugene Leitl wrote: Does anybody know how cellular automata perform re cryptographically solid random number generators? They can crank out a lot of integers with a minimum investment in instructions executed. Most of the fancy reseedable PRNG schemes people have come up with are based on using secure hashes. -Bram
Re: depleting the random number generator
On Sun, 18 Jul 1999, Bill Stewart wrote: /dev/urandom will give you pseudo-random bits if it's run out of entropy, so you've got the security risks inherent in that. As David Honig points out, you can't avoid those alternatives, Yes you can, if there's a 'pool' of entropy in memory which contains a cryptographycally large number of bits and it's both mixed and extracted from in a cryptographically secure way then the need for constant reseeding is eliminated, although it's still helpful. The paper on Yarrow explains the threat model pretty well - http://www.counterpane.com/yarrow.html so if you need the high quality randomness, you need hardware randomizers. Those are helpful as well, but should still never be used in the raw - their entropy output should be estimated conservatively and fed into a reseedable PRNG. -Bram
Re: Word needed for Entropy
On Sat, 26 Jun 1999, Carl Ellison wrote: I've been guilty of sloppy use of English, occasionally, and one such sloppiness that I run into occasionally is with the word "entropy" for cryptographic purposes. What we need is a word or very short phrase to capture the full phrase: "the conditional entropy of a measurement given all the information about the measurement that an attacker is expected to acquire, under the threat model for which the present use is being designed." I just say 'entropy' - it's generally obvious that I mean it in a cryptographic sense, rather than a physics sense. -Bram
Re: obtaining FIPS-140a
On Fri, 14 May 1999, Adam Back wrote: Anyone who has done this have a feel for how much work and cost is involved in obtaining FIPS-140a? Are there samples of successful applicant's submitted documentation available? Is this what you mean? http://www.itl.nist.gov/div897/pubs/fip140-1.htm -Bram (altavista is your friend)
Re: Using crypto to solve a part of the DNS/TM mess
On Tue, 2 Mar 1999, Bill Stewart wrote: You can trivially run a namespace under a 2nd-level domain name, e.g. new-name-format.namegods.com orfoo.dyn.ml.org - to cite a real example without having to disrupt the worldwide naming system. Is there some way you could gaurantee for the world that you wouldn't change your mind about the rules of such a thing and become dictator? Some of the small-country name registries have used ambiguity-resolving name-spaces, which had forms like www.1234.interesting-name.com.zz where multiple participants who wanted interesting-name.com.zz each got a number, and the page www.interesting-name.com.zz had some indication of which company named interesting-name was which. Yuck. I agree with the person who made comments about .to that there's no particular reason why trademark law should apply to domain names - there's no particular expectation on the part of the general public that foo.com will correspond to the company foo, and putting up a web site at foo.com which claims to be from company foo is no different from impersonating foo from another domain name. (whitehouse.com seems relevant here) I was told recently that if you have access to domain name servers you can in practice create temporary domains using unclaimed domain names - there's no particular punishment process for doing so, sites of that kind are just removed eventually. Does anybody know if/how it's possible to get domain names in the now defunct .su ? Do you have to be grandfathered in? Is there a chance that just unilaterally grabbing one might work? -Bram (Thinking he should get a domain in .to - that WIPO DNS paper looked kinda scary)
Re: quantum cryptanalysis
On Fri, 5 Feb 1999, John Kelsey wrote: Anyway, there's a fair amount of crypto that would keep working even if all public-key methods became breakable. Not only symmetric cryptography, but variations on Merkle's puzzles (Bob Jenkins was discussing a bunch of mechanisms for this a couple years ago on sci.crypt; I think Maurer had a paper on a bunch of these methods in the last few years, as well.) There's also quantum key distribution. In place of signatures, there are a bunch of one-time signature schemes, using Merkle's hash tree idea to great effect to basically give you the ability to sign many documents (hundreds or thousands) from one `public key,' based only on using a collision-resistant hash function. I have a theory that no matter what computing machine is available, as long as the same machine is available to both the encrypter and the cracker, the cracker wins (barring non-turing complete machinery, of course.) For example, say that there was an oracle which you could ask 'Does this turing machine ever halt?' (quantum cryptography can't do that.) A cracker with such a machine could trivially crack any code encrypted using standard methods with a published algorithm. If, however, the encrypter also had such a machine, he could devise an encryption algorithm which required queries to the oracle to work, and as long as the algorithm required, say, quadratically many queries to the oracle to encrypt but exponentially many queries to the oracle to crack, the encrypter wins. No, I don't have any clue how an algorithm like that might work. -Bram
Re: quantum cryptanalysis
On Fri, 5 Feb 1999, bram wrote: I have a theory that no matter what computing machine is available, as long as the same machine is available to both the encrypter and the cracker, the cracker wins (barring non-turing complete machinery, of course.) Jim Gillogly pointed out that I misspoke - I meant to say 'the encrypter wins' -Bram
Re: FBI secret police
On Thu, 18 Nov 1999, Robert Hettinga wrote: William Allen Simpson wrote: "Sources whose identities are concealed herein have furnished reliable information in the past except when otherwise noted." Gentlefolk, we have a stool pigeon in the roost, whose interests are contrary to the interests of the IETF and the Internet as a whole. It is a male. And he is regularly reporting IETF member activities for secret investigation. Beware. Or maybe it's just someone who reads published IETF literature. It's not like the IETF keeps it's activities all that secret. -Bram
