Re: Columbia crypto box
In message [EMAIL PROTECTED], Pete Chown writes: Bill Stewart wrote: These days nobody *has* a better cryptosystem than you do They might have a cheaper one or a faster one, but for ten years the public's been able to get free planet-sized-computer-proof crypto ... I seem to remember that the Nazis said the same thing about Enigma. Even when evidence began to filter back that it had been broken, they ignored it because they were so confident that a break was impossible. It's true that protocol and programming problems account for the huge majority of security holes. The WEP break, though, was one notable exception. They were using an established cryptosystem (RC4) with a planet sized key (128 bits). However, a weakness in RC4 itself let them down. Actually, that's missing the point. Yes, the cryptanalytic attack on RC4, especially as it's used in WEP, was impressive. But that attack was the least important problem with WEP -- the more serious problems were protocol issues. First, there was no key management. This means that loss of a single unit -- a stolen laptop or a disgruntled (ex-)employee would do -- compromises the entire network, since it's impossible to rekey everything at once in an organization of any size. For most real-world deployments, this is the most serious weakness. Furthermore, if there were real key management, the next two problems couldn't have happened. This was clearly avoidable. The second most serious problem was the set of problems documented by Borisov et al. at Berkeley. These mostly relied on the inappropriate use of a stream cipher, especially with too short an IV. Note that if it were possible to rekey before 2^24 packets were sent under any one key, the attacks mostly wouldn't be possible. The cryptanalytic attack did exploit an unforeseen weakness in RC4. But the attack was a related-key attack, and it required a noticeable amount of traffic. If rekeying had taken place, or if the IV were properly mixed with the seed key, there wouldn't have been a problem here. To be sure, Enigma was largely broken because it wasn't being used properly. As you say, protocol issues are the leading cause of crypto holes. (And, as you note, programming bugs account for *far* more real-world security problems.) --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
While I'm not claiming RC4 is strong, the main problem is that WEP misuses it. At I understand it, the recommendation for a long time has been that you either throw away the first 256 bytes of stream key output or use a different key on every message. WEP does neither. TKIP, the new security mode for 802.11 designed for feeble legacy hardware, still uses RC4 but does change keys on every message. Thanks, Donald == Donald E. Eastlake 3rd [EMAIL PROTECTED] 155 Beaver Street +1-508-634-2066(h) +1-508-851-8280(w) Milford, MA 01757 USA [EMAIL PROTECTED] On Sun, 9 Feb 2003, Pete Chown wrote: Date: Sun, 09 Feb 2003 13:51:07 + From: Pete Chown [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: Columbia crypto box Bill Stewart wrote: These days nobody *has* a better cryptosystem than you do They might have a cheaper one or a faster one, but for ten years the public's been able to get free planet-sized-computer-proof crypto ... I seem to remember that the Nazis said the same thing about Enigma. Even when evidence began to filter back that it had been broken, they ignored it because they were so confident that a break was impossible. It's true that protocol and programming problems account for the huge majority of security holes. The WEP break, though, was one notable exception. They were using an established cryptosystem (RC4) with a planet sized key (128 bits). However, a weakness in RC4 itself let them down. ... if you don't like it, you can switch from 3DES and 1024-bit RSA to 5DES and/or 4096-bit RSA. I don't know about 4096-bit, but you should switch to something if you care about security; recent results imply that it may be possible to factor 1024-bit numbers. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
Pete Chown [EMAIL PROTECTED] writes: Bill Stewart wrote: These days nobody *has* a better cryptosystem than you do They might have a cheaper one or a faster one, but for ten years the public's been able to get free planet-sized-computer-proof crypto ... I seem to remember that the Nazis said the same thing about Enigma. Even when evidence began to filter back that it had been broken, they ignored it because they were so confident that a break was impossible. It's true that protocol and programming problems account for the huge majority of security holes. The WEP break, though, was one notable exception. They were using an established cryptosystem (RC4) with a planet sized key (128 bits). However, a weakness in RC4 itself let them down. This isn't 100% true. There were known (less practical but still better than just theoretical) attacks on RC4 as used in WEP even before the RC4 weak key work. WEP was a bad design through and through. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
On Sun, Feb 09, 2003 at 11:34:01PM -0500, Steven M. Bellovin wrote: First, there was no key management. This means that loss of a single unit -- a stolen laptop or a disgruntled (ex-)employee would do -- compromises the entire network, since it's impossible to rekey everything at once in an organization of any size. For most real-world deployments, this is the most serious weakness. Furthermore, if there were real key management, the next two problems couldn't have happened. This was clearly avoidable. Practically, what's the right way to do this? You could do it with a centralized server key that has the ability to broadcast a new shared key to all clients, but then if the server gets compromised you lose control of the entire network (possibly true anyway, for different reasons). From my personal (limited) experience, key management is really hard. I'm curious about potential solutions to this. -- - Adam - Adam Fields, Managing Partner, [EMAIL PROTECTED] Surgam, Inc. is a technology consulting firm with strong background in delivering scalable and robust enterprise web and IT applications. http://www.adamfields.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
On Sun, Feb 09, 2003 at 11:43:55PM -0500, Donald Eastlake 3rd wrote: been that you either throw away the first 256 bytes of stream key output or use a different key on every message. WEP does neither. TKIP, the new You NEVER, EVER, re-use the key for a stream cipher, if you do, you might as well just give up. By re-using the key, I can get plaintext (combinator) plaintext, which is easier to solve than plaintext (combinator) cipherstream. It's one of those things, like re-using a pad. MBM -- Matthew Byng-Maddick [EMAIL PROTECTED] http://colondot.net/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
PET2003 (Mar 26-28) accepted papers
The following papers have been accepted for presentation and publication at the 3rd Privacy Enhancing Technologies workshop, in Dresden Mar 26-28 this year. In addition, there will be several invited talks and/or panels. Please forward this mail to other relevant lists. See http://petworkshop.org/ for more details, including the rapidly approaching deadlines for stipends (February 16 -- available to non-authors too!) and registration (February 20). Mix-networks with Restricted Routes George Danezis Generalising Mixes Claudia Diaz, Andrei Serjantov Modelling Unlinkability Sandra Steinbrecher and Stefan K\opsell Metrics for Traffic Analysis Prevention Richard E. Newman, Ira S. Moskowitz, Paul Syverson, Andrei Serjantov Breaking and Mending Resilient Mix-nets Lan Nguyen, Rei Safavi-Naini Improving Onion Notation Richard Clayton Engineering Privacy in Public: Confounding Face Recognition James Alexander and Jonathan Smith From Privacy Legislation to Interface Design: Implementing Information Privacy in Human-Computer Interactions Andrew S. Patrick, Stephen Kenny Defeating Web Censorship with Untrusted Messenger Discovery Nick Feamster, Magdalena Balazinska, Winston Wang, Hari Balakrishnan, David Karger GAP -- Practical anonymous networking Krista Bennett, Christian Grothoff An Analysis of GNUnet and the Implications for Anonymous, Censorship-Resistant Networks Dennis K\ugler A Component Architecture for Dynamically Managing Privacy Constraints in Personalized Web-based Systems Alfred Kobsa Privacy in Enterprise Identity Federation: Policies for Liberty Single Signon Birgit Pfitzmann From P3P to Data Licenses Yuh-Jzer Joung - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Columbia crypto box
Matthew Byng-Maddick[SMTP:[EMAIL PROTECTED]] writes: On Sun, Feb 09, 2003 at 11:43:55PM -0500, Donald Eastlake 3rd wrote: been that you either throw away the first 256 bytes of stream key output or use a different key on every message. WEP does neither. TKIP, the new You NEVER, EVER, re-use the key for a stream cipher, if you do, you might as well just give up. By re-using the key, I can get plaintext (combinator) plaintext, which is easier to solve than plaintext (combinator) cipherstream. It's one of those things, like re-using a pad. MBM The weird thing about WEP was its choice of cipher. It used RC4, a stream cipher, and re-keyed for every block. . RC4 is not really intended for this application. Today we'd have used a block cipher with varying IVs if neccessary I suspect that RC4 was chosen for other reasons - ease of export, smallness of code, or something like that. It runs fast, but rekeying every block loses most of that advantage. Just my personal musings Peter Trei - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Wireless network key management
(The topic has drifted to the management of keys in a wireless network. Adam responds to Steve's notes about WEP...) Adam Fields [EMAIL PROTECTED] writes: Practically, what's the right way to do this? You could do it with a centralized server key that has the ability to broadcast a new shared key to all clients, but then if the server gets compromised you lose control of the entire network (possibly true anyway, for different reasons). From my personal (limited) experience, key management is really hard. I'm curious about potential solutions to this. Key management is hard, but there is good versus not so good versus horrible. Unchanging fixed WEP keys for everything on a network are bad. If, on the other hand, you use public key techniques or Needham-Schroder KDC based techniques, you can do much better. For example, the average wireless base station only has dozens to at most hundreds of clients. (In practice, they average far fewer, but never mind.) Also, 802.11 enforces that all communication goes through the wireless base station -- there are no mobile-mobile communications in the usual setup. It is thus perfectly reasonable to use different on-air conventional keys with each client, authenticated with a variety of techniques (shared key between base and client, public keys on both sides, Needham-Schroder, etc.), and negotiated by any one of a number of similar variety of techniques (Diffie-Hellman, randomly generated nonce keys replaced at intervals encrypted in a known key, etc.) More to the point, almost all 802.11 traffic carries IP. Therefore, using IPSec to protect traffic between the wireless node and the base station or a router, or even end to end, would not be unreasonable. In that case, key negotiation probably proceeds using IKE or perhaps a successor protocol. In any case, although none of these techniques are perfect, they all eliminate the problem of one key to rule them all, with theft of one mobile handing over the entire net, both from a privacy and an authentication viewpoint. Of course, since WEP is crap anyway, you can break keys even if you don't steal a mobile, but even in principle the mechanism was not particularly good. It isn't any easier to configure than good methods, either. Sure, you need to pre-configure some authentication information to use any of the good methods, but you also need to pre-configure your super-secret WEP key if you use WEP so there is no improvement in ease of configuration by using WEP. -- Perry E. Metzger[EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
In message [EMAIL PROTECTED], bear writ es: It's one of those things, like re-using a pad. Actually, it is re-using a pad, exactly. It's just a pseudorandom pad (stream cipher) instead of a one-time pad. And while WEP had problems, it didn't have that particular problem. New messages with the same key would use a later chunk of the cipherstream pad under WEP. That's not correct. Each packet is encrypted with a key consisting of basekey,IV, where IV is a 24-bit counter. It does not use a later part of the stream; each packet starts from the beginning. Note that with a 24-bit key, plus the difficulty of changing the key, there *will* be reuse. It's compounded because (a) everyone has the same key, so there's lots of traffic; (b) both directions use the same key; and (c) some units, when power-cycled, always start the IV at 0, making collisions in that space more likely. Read the Borisov et al. paper for more details on all of these points and more. --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
Trei, Peter wrote: The weird thing about WEP was its choice of cipher. It used RC4, a stream cipher, and re-keyed for every block. . RC4 is not really intended for this application. Today we'd have used a block cipher with varying IVs if neccessary I suspect that RC4 was chosen for other reasons - ease of export, smallness of code, or something like that. It runs fast, but rekeying every block loses most of that advantage. It's hard to believe that RC4 was chosen for technical reasons. The huge cost of key setup per packet (equivalent to generating 256 bytes of keystream and then throwing it away) should dominate the other potential advantages of RC4. In any case, WEP would clearly look very different if it had been designed by cryptographers, and it almost certainly wouldn't use RC4. Look at CCMP, for instance: it is 802.11i's chosen successor to, and re-design of, WEP. CCMP uses AES, not RC4, and I think that was a smart move. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
In message b295ds$l66$[EMAIL PROTECTED], David Wagner writes: Trei, Peter wrote: The weird thing about WEP was its choice of cipher. It used RC4, a stream cipher, and re-keyed for every block. . RC4 is not really intended for this application. Today we'd have used a block cipher with varying IVs if neccessary I suspect that RC4 was chosen for other reasons - ease of export, smallness of code, or something like that. It runs fast, but rekeying every block loses most of that advantage. It's hard to believe that RC4 was chosen for technical reasons. The huge cost of key setup per packet (equivalent to generating 256 bytes of keystream and then throwing it away) should dominate the other potential advantages of RC4. I'm not sure you're right. While 40-50% of packets are about 40 bytes long -- see http://www.nlanr.net/NA/Learn/packetsizes.html for some older statistics -- most *bytes* are carried by larger packets. From that same site, about 75% of the bytes are carried by packets over 500 bytes long. A quick awk script suggests that given that packet size distribution, the total workload to use WEP-style encryption is about double the number of bytes. The overhead is thus substantial -- but RC4's cost per byte is quite low, so it was probably a net win. Other studies suggest that LAN packet size distribution is somewhat different, with more large packets; that would lower the overhead. Note that the traffic mix on the Internet has shifted since that data was collected. Audio and video files are large, and hence will use more large packets; that again would lower the overhead. What's unclear is to what extent wireless device traffic differs. Given the increasing deployment of 802.11 in the home, I suspect that there's a lot of big files going to wireless endpoints. In any case, WEP would clearly look very different if it had been designed by cryptographers, and it almost certainly wouldn't use RC4. Look at CCMP, for instance: it is 802.11i's chosen successor to, and re-design of, WEP. CCMP uses AES, not RC4, and I think that was a smart move. A block cipher is clearly a better choice here. But there were some rational reasons for selecting RC4 (even though I think that on balance, the choice was very wrong). --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
At 1:26 PM -0800 2/10/03, David Wagner wrote: It's hard to believe that RC4 was chosen for technical reasons. The huge cost of key setup per packet (equivalent to generating 256 bytes of keystream and then throwing it away) should dominate the other potential advantages of RC4. The technical reasons people might chose RC4 for an embedded application like 802.11 WEP include: * Code size so close to zero as to make no never mind. * Intermediate data size so close to zero as to make no never mind. * Fast key setup (Forget tossing the 256 bytes of key stream. The designers weren't crypto engineers. Personally, I'd toss the first 1024.) * Fast encrypt/decrypt. * Commonly used in respected security applications (e.g. SSL). In any case, WEP would clearly look very different if it had been designed by cryptographers, and it almost certainly wouldn't use RC4. Look at CCMP, for instance: it is 802.11i's chosen successor to, and re-design of, WEP. CCMP uses AES, not RC4, and I think that was a smart move. I agree. WEP is what you get when you don't seek public review. Cheers - Bill - Bill Frantz | Due process for all| Periwinkle -- Consulting (408)356-8506 | used to be the Ameican | 16345 Englewood Ave. [EMAIL PROTECTED] | way. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
At 4:29 PM -0800 2/10/03, Steven M. Bellovin wrote: In message v03110705ba6dec92ddb0@[192.168.1.5], Bill Frantz writes: * Fast key setup (Forget tossing the 256 bytes of key stream. The designers weren't crypto engineers. Personally, I'd toss the first 1024.) ... There may be a cryptographically sound reason to discard that much, but it's not without cost. The reason I would discard so much is that when I did some statistics on RC4 output, I kept getting distribution lumps out to about 1024. They made me worry about what someone who knew what were doing could do. Cheers - Bill - Bill Frantz | Due process for all| Periwinkle -- Consulting (408)356-8506 | used to be the Ameican | 16345 Englewood Ave. [EMAIL PROTECTED] | way. | Los Gatos, CA 95032, USA - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
In message v03110708ba6df9a4efb3@[192.168.1.5], Bill Frantz writes: At 4:29 PM -0800 2/10/03, Steven M. Bellovin wrote: In message v03110705ba6dec92ddb0@[192.168.1.5], Bill Frantz writes: * Fast key setup (Forget tossing the 256 bytes of key stream. The designers weren't crypto engineers. Personally, I'd toss the first 1024.) ... There may be a cryptographically sound reason to discard that much, but it's not without cost. The reason I would discard so much is that when I did some statistics on RC4 output, I kept getting distribution lumps out to about 1024. They made me worry about what someone who knew what were doing could do. That's a good reason... (At that point, even with older hardware, AES might be better -- and of course, using a block cipher solves lots of other problems, too...) --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
Bill Frantz writes: * Fast key setup (Forget tossing the 256 bytes of key stream. The designers weren't crypto engineers. Personally, I'd toss the first 1024.) Steven M. Bellovin wrote: There may be a cryptographically sound reason to discard that much, but it's not without cost. Bill Frantz wrote: The reason I would discard so much is that when I did some statistics on RC4 output, I kept getting distribution lumps out to about 1024. They made me worry about what someone who knew what were doing could do. See: Ilya Mironov (Stanford), (Not So) Random Shuffles of RC4 Advances in Cryptology - CRYPTO 2002 Proceedings, ed. by Moti Yung. Springer LNCS 2242, 2002. pp. 304-319. http://crypto.stanford.edu/~mironov/papers/rc4full.pdf Abstract. Most guidelines for implementation of the RC4 stream cipher recommend discarding the first 256 bytes of its output. This recommendation is based on the empirical fact that known attacks can either cryptanalyze RC4 starting at any point, or become harmless after these initial bytes are dumped. The motivation for this paper is to find a conservative estimate for the number of bytes that should be discarded in order to be safe. To this end we propose an idealized model of RC4 and analyze it apply- ing the theory of random shuffes. Based on our analysis of the model we recommend dumping at least 512 bytes. ... 7 Conclusion We identified a weakness in RC4 stemming from an imperfect shuffing algorithm used in the key scheduling phase and the pseudo-random number generator. The weakness is noticeable in the first byte but does not disappear until at least the third or the fourth pass (512 or 768 bytes away from the beginning of the output). ... Our most conservative recommendation ... means that discarding the initial 12 * 256 bytes most likely eliminates the possibility of a strong attack. Dumping several times more than 256 bytes from the output stream (twice or three times this number) appears to be just as reasonable a precaution. We recommend doing so in most applications. - - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
At 06:12 PM 2/10/2003 -0500, Steven M. Bellovin wrote: In any case, WEP would clearly look very different if it had been designed by cryptographers, and it almost certainly wouldn't use RC4. Look at CCMP, for instance: it is 802.11i's chosen successor to, and re-design of, WEP. CCMP uses AES, not RC4, and I think that was a smart move. A block cipher is clearly a better choice here. But there were some rational reasons for selecting RC4 (even though I think that on balance, the choice was very wrong). I agree that on balance, the implementation of RC4 for WEP was very wrong. But by your own numbers (and on the assumption that RC4 generates bytes twice as fast as AES and that the cost of keying is equivalent to generating 256 bytes) RC4 should win, computationally, on packets greater than 256 bytes. More modern stream ciphers such as SOBER-t32, SNOW2.0 and Turing, all of which explicitly support Initialisation Vectors to generate distinct streams, perform much better than AES for a job like this. I happen to have the numbers to hand for a comparison of my implementation of Turing vs. Brian Gladman's highly optimised AES (because the paper is being presented in two weeks at FSE), and computationally speaking Turing overtakes at about 100 bytes and generates bytes about 5 times faster from there on. SNOW2.0 overtakes almost straight away, and generates bytes about 3 times faster (haven't measured that myself, but I believe it). The combination of Turing for encryption and HMAC-SHA-1 for MAC outperforms AES even in OCB mode on my laptop. (Lest anyone ask, no, I'm not suggesting adopting Turing or SNOW2.0... they're too new. And I'm not trying to promote my own cipher particularly. But...) You said: A block cipher is clearly a better choice here. This is almost, for me, the canonical case for a stream cipher. What's clear to you isn't clear to me. Can you elucidate, please? regards, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Columbia crypto box
In message [EMAIL PROTECTED], Paul A.S. Ward writes: Is it really fair to blame WEP for not using AES when AES wasn't around when WEP was being created? Of course they couldn't have used AES. But there are other block ciphers they could have used. They could have used key management. They could have added a MAC. They could have used a longer IV field, with a random starting point mandated by the spec. Or they could have put a big warning on saying this doesn't protect you from very much. --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of Firewalls book) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
