Gutmann: operating under the radar
http://www.computerworld.co.nz/news.nsf/PrintDoc/3F25D67E47980786CC256E6C007EE7D2?OpenDocumentpub=Computerworld Computerworld NZ Tuesday, 6 April, 2004 Gutmann: operating under the radar Paul Brislen, Auckland He describes himself as a professional paranoid, but cryptography expert Peter Gutmann (pictured) is quite willing to buy products online using his credit card and advocates writing down passwords on a piece of paper. Gutmann, a developer, author, speaker and honorary researcher at Auckland University's computer science department, realises that the password advice might seem to fly in the face of reason. Think about it. If you've written down your complicated password on a piece of paper someone would have to break into your house to get it to then break into your online account. That's not likely when the crooks are sitting in Eastern Europe. Conversely, he says having one user name and password for all accounts is perhaps the worst thing a user can do. That way if one account is compromised then effectively all of them could be. Gutmann is world-renowned for his work on security architecture and is in demand on the IT security speaking circuit. His PhD thesis has been released as an academic text book (Cryptographic security architecture: design and verification) and he has at least two more in the pipeline. That one's very much an academic book. The next one is more straightforward and is more about my take on different security issues. Gutmann's role at Auckland University doesn't pay anything but it allows him to do what he likes. His income is derived from one of those products nobody's ever heard of but which many of us use - Cryptlib. Cryptlib is in embedded products such as ATM machines and print servers, for authenticating user rights to a particular printer. It's widely used but invisible. Basically it's a general purpose tool used inside applications so most people don't even know it's there. Gutmann says this is the best approach to issues like email encryption - make it happen automatically. PGP has been around for over a decade and has a tiny market share still. Cryptlib, by comparison, is marketed by health software developer Orion Systems. There are plenty of cool people using it but if I tell you who they are they'll kill me, says Gutmann, only half joking. Gutmann didn't set out to be a cryptographer. I was working in data compression but you really can't make much of a difference there. I sort of drifted into cryptography. Gutmann says his approach isn't one of maths-intensive algorithms. There's very little maths involved. Basically that part of it's secure these days. It costs too much in terms of time and effort to break the code to make it worthwhile. I work on the stuff around that to make sure that's defensible. Gutmann offers the example of public keys. What's the point of securing your system with the most up-to-date encryption technology if you email someone your key in an insecure manner? Gutmann likes to quote cryptographer Bruce Schneier on the subject. Basically he says it's like putting a large iron stake in the ground in your front garden and hoping the burglar will run into it. It's the rest of the garden that matters as well. So Gutmann isn't worried that if he's too good at his job he'll do himself out of a career. As long as there are computers we'll need security people. -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases
Dobbertin's 1996 collision demonstration is another good reason not to use md5, but is obviously hasn't gotten the open source community or Apple to stop. Whether my attack will be any more successful in effecting change remains to be seen. Publishing SHA1 hashes in parallel with md5 seems like such an inexpensive thing to do, but one should never underestimate cryptographic inertia. For the record, I first published my attack on Perry Metzger's cryptography list in February, 2002. Arnold Reinhold At 5:56 PM -0400 4/4/04, Don Davis wrote: hi, mr. reinhold -- there's stronger reason than the ones you cite, to distrust md5 as a message-digest. see these old sci.crypt threads, and the google-search below, for discussions of hans dobbertin's 1996 crack of md5: http://tinyurl.com/2ox7g http://tinyurl.com/3x446 http://google.com/search?q=dobbertin+md5num=30 btw, in a phone conversation, dobbertin emphasized to me that his attack only works when md5 is used as a message-digest; it doesn't work when md5 is used with a key to prepare a MAC. he also mentioned that while sha-1 may be vulnerable to an attack of a similar style (because sha-1 is similar in struc- ture to md5), he himself was forbiddden by german law to work to cryptanalyze sha-1, because he worked at that time for the german federal security service, and so wasn't allowed to attack the USG's standard ciphers. now he's at ruhr university (in bochum), but i don't know whether he's more of a free agent. - don davis, boston To: [EMAIL PROTECTED] From: Arnold G. Reinhold [EMAIL PROTECTED] Subject: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases Sender: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] List-Id: Macintosh Cryptography mac_crypto.vmeng.com List-Archive: http://www.vmeng.com/pipermail/mac_crypto/ Date: Sun, 4 Apr 2004 06:17:55 -0500 The cryptographic hash function MD5 has long been used to authenticate software packages, particularly in the Linux/Unix/open source community. This has carried over to Apple's OS-X. The MD5 hash of an entire package is calculated and its value is transmitted separately from the package. Users who download the package compute the hash of the copy they received and match that value against the original. ... - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases
--- begin forwarded text From: Nicko van Someren [EMAIL PROTECTED] Subject: Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases To: [EMAIL PROTECTED] Sender: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] List-Id: Macintosh Cryptography mac_crypto.vmeng.com List-Post: mailto:[EMAIL PROTECTED] List-Help: mailto:[EMAIL PROTECTED] List-Subscribe: http://www.vmeng.com/mailman/listinfo/mac_crypto, mailto:[EMAIL PROTECTED] List-Archive: http://www.vmeng.com/pipermail/mac_crypto/ Date: Mon, 5 Apr 2004 16:51:56 +0100 On 4 Apr 2004, at 12:17, Arnold G. Reinhold wrote: ... A safer attack would be for the agent to insert an apparently innocent modification to the package, with the modification selected so that the MD5 hash of the package with the malicious code matches the hash of the officially released package. Since the attacker (or whomever he is working for) controls the malicious code, calculating the value of this modification is subject to a meet-in-the-middle attack and presents presents a 64-bit problem. Solving such a problem is within the means of a well-funded attacker today* and will become easier in the future. The modification could be designed to get past code reviews in a number of ways. For example, 64 low order bits in a JPEG icon might be altered. The agent would have to make the last modification to the software package prior to release and perhaps send a final pre-release version of the package to someone on the outside who does the collision calculation, but those are hardly insurmountable hurdles. In situations where new releases are relatively frequent, it may suffice for this attack to succeed only occasionally, allowing periodic entry into selected systems to recover private keys, for example. The attacker merely submits modifications late in the release cycle and if his happens to be last then the full attack is mounted. While I agree that it is somewhat lax of Apple to be using MD5 for checking its updates it's far from clear to me that an attack of the sort described above would ever be practical. The problem is that the while there are methods for finding has collisions by brute force, not only do they require a work factor around the size of the square root of the output space, and a large amount of storage, but the work factor is multiplied by a factor linear in the size of the data that follows the part of the message that you can manipulate. When all you are doing is trying to find a single collision on the hash function (or perhaps trying to forge a matching pair of small key exchange messages) this can be made quite small but when it comes to breaking a package distribution system it is much harder. Consider that the real package is represented by M, the subtly modified version is M1 and the bogus package is represented by M2. Each of these has some high resolution TIFF image T that we can get away with tweaking into T1 and T2. We probably don't have control where this image comes out in the package because the file ordering is deterministic. The package can be broken down into three parts: the bit before the tweakable part, the tweakable image and the bit after that: M = M1a | T | M1b M1 = M1a | T1 | M1b M2 = M2a | T2 | M2b For the purposes of finding a collision we can pre-compute the hash blocks of M1a and M2a but we can't do the same for M1b and M2b. This means if L(x) is the function for the number of hash blocks in message x then the cost of finding a hash collision in our packages is L(T1|M1b) + L(T2|M2b) times harder than just finding a simple collision by brute force. In MD5 the blocks are 64 bytes, so for every 1K in M1b the process of finding a collision gets 16 times harder. Finding a collision in SHA1 is about 2^16 times harder than finding a collision in MD5, so unless you find something that you can alter without it being noticed in the last 2MB of the package then this sort of forgery is actually going to be harder than finding a simple hash collision in SHA1! In practice you'll probably find something that you can alter in the last few hundred KB but still the raw processing cost will be a few orders of magnitude harder than a simple hash collision problem. Furthermore, since you have to process the tail of the message any specialised hardware for doing this will have a hard time doing it's processing in a usefully pipelined fashion and will need access to large amounts of very fast RAM to store the tail of the message, and this will also cost you another order of magnitude or so. Of course none of this is an argument for not using SHA1. All of these complexities apply just as well to SHA1, meaning that forging packages checked with SHA1 will be four or five orders of magnitude harder than finding a single simple SHA1 collision. On the other hand, it tells you that the prospect of any successful hash collision attack on Apple's packages are still some way
Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases
--- begin forwarded text To: [EMAIL PROTECTED] From: Vinnie Moscaritolo [EMAIL PROTECTED] Subject: Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases Sender: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] List-Id: Macintosh Cryptography mac_crypto.vmeng.com List-Post: mailto:[EMAIL PROTECTED] List-Help: mailto:[EMAIL PROTECTED] List-Subscribe: http://www.vmeng.com/mailman/listinfo/mac_crypto, mailto:[EMAIL PROTECTED] List-Archive: http://www.vmeng.com/pipermail/mac_crypto/ Date: Mon, 5 Apr 2004 08:10:26 -0800 one more thing for all it's worth.. MD5 is not a FIPS-140-2 approved algorithm. http://csrc.nist.gov/cryptval/ this would technically prevent osx from being used in any Federal or Mil environment. Apple will eventually have to address this concern. At 6:17 AM -0500 4/4/04, Arnold G. Reinhold wrote: The cryptographic hash function MD5 has long been used to authenticate software packages, particularly in the Linux/Unix/open source community. This has carried over to Apple's OS-X. The MD5 hash of an entire package is calculated and its value is transmitted separately from the package. Users who download the package compute the hash of the copy they received and match that value against the original. -- Vinnie Moscaritolo ITCB-IMSH PGP: 3F903472C3AF622D5D918D9BD8B100090B3EF042 --- When the pin is pulled, Mr. Grenade is not our friend. - USMC training bulletin. ___ mac_crypto mailing list [EMAIL PROTECTED] http://www.vmeng.com/mailman/listinfo/mac_crypto --- end forwarded text -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases
The attacks by Dobbertin on MD5 only allow to find collisions in the compression function, not the whole MD5 hash. But it is a sign that something might be fishy about MD5. MD5 output is 128 bits. There are two types of collision finding attacks that can be applied. In the first you are given a hash value y = H(x), for some x, and try to find a different input x' that hashes to the same output: H(x) = H(x') = y. This relates to 2nd-preimage resistance. This can be done on MD5 in 2^128 work factor. The other attack is to find to arbitrary inputs x, x' such that H(x) = H(x'). This relates to collision resistance. This can be done with good probability in 2^64 work factor. Now, the problem of having a malicious source code hash to the same value as good/valid source code seems to be related more to the former, that is you have some code that is checked-in, that gives some hash value Y, and you want to find a different code (malicious one) that hashes to the same value. You might be able to play with the valid code as well, giving you more flexibility for the search of a collision, but you can't play to much without having this noticed by other developers. I think that there are many other problems that are more of concern. For example hacking a web site (or mirror site) that contains code for download, and changing the code along with the hash value of the code, or preventing a developer from inserting some kind of trap door or Trojan. But if you are given the choice between using MD5 and SHA1, I'd prefer SHA1, but I wouldn't be concerned with someone using MD5 isntead of SHA1 for the time being. In other words, if I were to do a risk analysis, I would identify the use of MD5 instead of SHA1 as one of the major risks. --Anton - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
[Publicity-list] DIMACS Tutorial on Social Choice and Computer Science
* DIMACS Tutorial on Social Choice and Computer Science May 10 - 14, 2004 DIMACS Center, Rutgers University, Piscataway, NJ Organizers: Kevin Chang, University of Illinois, [EMAIL PROTECTED] Michel Regenwetter, University of Illinois, [EMAIL PROTECTED] Presented under the auspices of the Special Focus on Computation and the Socio-Economic Sciences. The theory of social choice and voting has had a long history in the social sciences, dating back to early work of Condorcet and others in the 18th century. Some modern issues facing the theory of social choice relate heavily to computer science. Often we need to determine preferences for an individual or group, while maintaining accuracy, fairness and security, sometimes with only limited information and/or computational power. This tutorial will consider computer science and social science issues in insuring the best choices given limited information and computation. It will build on early work on computational complexity of computing the winner of an election in. Moreover, we are also seeing voting/social choice issues arising in strictly computer science applications such as database and information retrieval, Internet search and meta-search, and collaborative filtering. The tutorial will also consider such applications. The tutorial will present an introduction to the concepts and models of individual preference or utility as well as social choice theory and introduce participants to a variety of modern computational issues and computer science applications. The following is a tentative list of topics: * Introduction to Voting Theory: History and Procedures. * Computational Complexity of Social Choice Procedures. * Mathematical Representations of Preference and Utility. * Ranking and Preference in Computer Science: Models and Semantics. * Rank-based Top-k Query Algorithms in Database Search. * Voting and Security: An introduction to the use of error-resilient, waitless methods of voting analysis. * Collaborative Filtering in Information Retrieval. * Internet Search and Meta-Search. * Behavioral Social Choice Theory. * Voting over the Internet. ** Participation: Talks for this workshop are by invitation only. ** Workshop Program: Monday, May 10, 2004 8:15 - 8:45 Registration and Breakfast 8:45 - 9:00 Welcome and Opening Remarks Fred Roberts, DIMACS Director Kevin Chang and Michel Regenwetter, Organizers 9:00 - 9:50 Introduction to Voting Theory: History and Procedures Arnold Urken, Stevens Institute of Technology 9:50 - 10:05 Break 10:05 - 10:55 Introduction to Voting Theory: History and Procedures (continued) Arnold Urken, Stevens Institute of Technology 10:55 - 11:10 Break 11:10 - 12:00 Introduction to Voting Theory: History and Procedures (continued) Arnold Urken, Stevens Institute of Technology 12:00 - 1:30 Lunch - DIMACS Lounge 1:30 - 2:20 Mathematical Representations of Preference and Utility Michel Regenwetter, University of Illinois at Urbana-Champaign 2:20 - 2:35 Break 2:35 - 3:25 Mathematical Representations of Preference and Utility (continued) Michel Regenwetter, University of Illinois at Urbana-Champaign 3:25 - 3:40 Break 3:40 - 4:30 Mathematical Representations of Preference and Utility (continued) Michel Regenwetter, University of Illinois at Urbana-Champaign Tuesday, May 11, 2004 8:30 - 9:00 Registration and Breakfast 9:00 - 9:50 Voting and Security Arnold Urken, Stevens Institute of Technology 9:50 - 10:05 Break 10:05 - 10:55 Voting and Security (continued) Arnold Urken, Stevens Institute of Technology 10:55 - 11:10 Break 11:10 - 12:00 Voting and Security (continued) Arnold Urken, Stevens Institute of Technology 12:00 - 1:30 Lunch - DIMACS Lounge 1:30 - 2:20 Computational Complexity of Social Choice Procedures Craig Tovey, Georgia Institute of Technology 2:20 - 2:35 Break 2:35 - 3:25 Computational Complexity of Social Choice Procedures (continued) Craig Tovey, Georgia Institute of Technology 3:25 - 3:40 Break 3:40 - 4:30 Computational Complexity of Social Choice Procedures (continued) Craig Tovey, Georgia Institute of Technology Wednesday, May 12, 2004 8:30 - 9:00 Registration and Breakfast 9:00 - 9:50 Ranking and Preference in Computer Science: Models and Semantics Kevin Chang, University of Illinois at Urbana-Champaign 9:50 - 10:05 Break 10:05 - 10:55 Ranking and Preference in Computer Science: Models
Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases
At 4:51 PM +0100 4/5/04, Nicko van Someren wrote: ... While I agree that it is somewhat lax of Apple to be using MD5 for checking its updates it's far from clear to me that an attack of the sort described above would ever be practical. The problem is that the while there are methods for finding has collisions by brute force, not only do they require a work factor around the size of the square root of the output space, and a large amount of storage, but the work factor is multiplied by a factor linear in the size of the data that follows the part of the message that you can manipulate. When all you are doing is trying to find a single collision on the hash function (or perhaps trying to forge a matching pair of small key exchange messages) this can be made quite small but when it comes to breaking a package distribution system it is much harder. Consider that the real package is represented by M, the subtly modified version is M1 and the bogus package is represented by M2. Each of these has some high resolution TIFF image T that we can get away with tweaking into T1 and T2. We probably don't have control where this image comes out in the package because the file ordering is deterministic. The file ordering may be deterministic, but someone who is well versed in the configuration control and release engineering process might well be able to have a chosen file placed at the end of of the package. The method for getting stuff at the end needn't be perfect. The attacker can keep trying until he succeeds. The package can be broken down into three parts: the bit before the tweakable part, the tweakable image and the bit after that: M = M1a | T | M1b M1 = M1a | T1 | M1b M2 = M2a | T2 | M2b For the purposes of finding a collision we can pre-compute the hash blocks of M1a and M2a but we can't do the same for M1b and M2b. This means if L(x) is the function for the number of hash blocks in message x then the cost of finding a hash collision in our packages is L(T1|M1b) + L(T2|M2b) times harder than just finding a simple collision by brute force. In MD5 the blocks are 64 bytes, so for every 1K in M1b the process of finding a collision gets 16 times harder. Finding a collision in SHA1 is about 2^16 times harder than finding a collision in MD5, so unless you find something that you can alter without it being noticed in the last 2MB of the package then this sort of forgery is actually going to be harder than finding a simple hash collision in SHA1! In practice you'll probably find something that you can alter in the last few hundred KB but still the raw processing cost will be a few orders of magnitude harder than a simple hash collision problem. Furthermore, since you have to process the tail of the message any specialised hardware for doing this will have a hard time doing it's processing in a usefully pipelined fashion and will need access to large amounts of very fast RAM to store the tail of the message, and this will also cost you another order of magnitude or so. Having a tail 2 MB or longer may make the processing time comparable to finding an SHA1 collision, but it is still a 64-bit problem and thus requires far less memory than finding an SHA1 collision. I am not saying that my attack is easy, but that it is feasible for a large organization and very dangerous and stealthy if it succeeds. History has shown, over and over and over again, the folly of ignoring cryptographic attacks that are theoretically possible but seem too hard to implement. On the other hand, defending against my attack certainly is easy, just publish an SHA1 (or stronger) hash alongside the MD5 hash. Arnold Reinhold - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Mixmaster RFC
Hello, I'm preparing to submit draft -02 of the revised Mixmaster Protocol Specification. If you have any comments, or have previously contributed and have not been acknowledged, please let me know as soon as possible by sending mail to [EMAIL PROTECTED] The last published version is here: http://www.ietf.org/internet-drafts/draft-sassaman-mixmaster-00.txt The current working version of the I-D is here: https://source.mixmaster.anonymizer.com/svn/mixmaster/trunk/Docs/draft- sassaman-mixmaster-XX.txt (Please comment on the latter). Thanks, Len - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
