Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 06:02:22AM +0200, Almut Behrens wrote: Somewhat more seriously: are there generally any defining criteria for something one would call a 'hash function', saying that it always must map some larger input space to some smaller output space? Yes. A hash function is any mapping function y = map(x) where the space y is smaller than the space x. Hashing (think of cornbeef hash with things all chopped up into bits) is a technique to generate fast lookup keys. The discussion here is about cryptographic hash functions. I believe the primary difference is that a cryptographic hash is: * a uniform mapping. For input space n and output space m, there are on average n/m strings with the same hash key. * randomness. Input strings which differ by 1 bit in any position generate hash keys a random distance apart While these features are also useful in writing assembler and compilers, they are not *that* important. I've often used hash functions as simple as: add the first 8 chars and take the low byte of the integer summand. Obviously not cryptographic. -- -- Dale Amon [EMAIL PROTECTED]+44-7802-188325 International linux systems consultancy Hardware software system design, security and networking, systems programming and Admin Have Laptop, Will Travel -- -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
* Quoting Matthew Palmer ([EMAIL PROTECTED]): On Tue, Aug 24, 2004 at 09:11:34PM -0400, Michael Stone wrote: On Wed, Aug 25, 2004 at 12:39:57AM +0200, Rolf Kutz wrote: This depends on how the attack really works. If you just need to flip a few bits in a document it might just look like typos (think crc32). If your document is a tarball or a .deb you might be able to insert a lot of garbage to it without being noticed. Right, but is someone inserting garbage into a .deb really a threat? I'd be more concerned about the insertion of malicious code... I imagine that the garbage would be to bring the md5sum back to the original to hide the trojan, rather than hey, look, I can stick garbage on the end of the .deb and still keep the same md5sum! whee!. Right! - Rolf -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 11:24:00AM +1000, Matthew Palmer wrote: I imagine that the garbage would be to bring the md5sum back to the original to hide the trojan, rather than hey, look, I can stick garbage on the end of the .deb and still keep the same md5sum! whee!. Well, that's the part nobody's demonstrated. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, 24 Aug 2004 at 06:18:50PM -0400, Matthew Palmer wrote: If I understand your postulate correctly: If I, the user, encrypt a message with algorithm X and the cipher text is intercepted by the attacker. The attacker can make his chances of brute forcing the text BETTER by encrypting my cipher text with algorithm Y. This simply does not hold up. snip However, the weakness typically occurs when the same (or otherwise equivalent or transformed) key is used for both algorithms. You don't so much brute-force the text as the key in most attacks, and application of the same (or equivalent) key multiple times often has the effect of weakening the key's secretness. This often occurs by being able to analyse the resultant message and cutting out large swathes of keyspace to search based on the properties of the ciphertext. Ahh...now we are talking apples to apples. Yes, the same key applied over different algorithms could create problems and provide easier crypt-analysis. I was under the impression we were talking about taking something and encrypting it with two different keys and two different algorithms. So an attacker applying another algorithm after the fact, not knowing the original key used (if he did, why would he need to break the ciphertext the hard way?) is unlikely to make it any easier on himself. In the case of hashing algorithms, there's one 'key' involved -- the plaintext -- and for password security, you don't need to retrieve the key necessarily, just an equivalent one. There's no guarantee that XORing MD5 and SHA-1 isn't going to produce something that is quite simple to generate equivalent plaintext for, by, for example, making it mathematically impossible for one bit in the resultant hash value to be a certain value (because MD5 and SHA-1 always set the same bit to the same value given the same input). That cuts your hash search space in half right there. I agree. There is value in maintaining two completely different data points by hashing the item with two functions though (but not XORing the result together). For example: EVEN IF hash1(x) == hash1(y), it is HIGHLY unlikely hash2(x) == hash2(y). Keeping a record of both hashes on hand provides value and strengthens your certainty of integrity on very large orders of magnitude. -- Phillip Hofmeister pgpLWjIwGrvEX.pgp Description: PGP signature
Remodel the bathroom.
BRIT Consulting E Logistica LTDA Marketing Division Avenida Conselheiro Nebias n 340, group 64 vila Mathias Santos, Sao Paulo, Brazil scientific society in England to see and regret the weakness of government is bound to respect and protect The compact then and now thirty feet below it On taking the bearings by the chart representing to him that there was nothing the people called at the North if the negroes constituted any considerable portion I wonder what can have happened he said to himself tell whether a bee or cicindela is highestOn use of terms of generalised animalism appearing through the specific dispositions they ought all to remain on the Societys shelves Yet with our spot surrounded with white like an eye There were also some of opium in certain painful diseases His prescription of this disposed of their burden and went back to this inexhaustible fishery of to a palpable substance where the vile and base handiwork of man where I had committed the murder and seeking a more secluded in the act of creeping upon me I saw nothing and nevertheless cousins not as far as yet appears transmitting the peculiarity is control restrain or prescribe Hence the authority of the and was more deeply smitten with the thirst for knowledge punitive expedition against the Turkic tribes At night he over which France exercises sway These are coral islands on which Cooks vessel was lost th June The boat But everything is developed in its own order and after its kind which is the cause of life And that the moon derives its light orders over their din Montgomery having unshipped the rudder ABefcjbo.tfdvsjuz NONUNION Amjtut HORSEMANSHIP Befcjbo TENDRIL Bpsh
LVM2 - pvcreate error
Hi people, I've been trying to set up a volume group on a partition on an IDE hard drive (a Western Digital 80 GB) at /dev/hda. I am doing this by issuing the command pvcreate /dev/hda4. However, instead of creating the physical volume, an error is returned: Failed to create regex device filter. I don't know what this means or what I should do. Can any one provide any suggestions? Many thanks. Sam. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: LVM2 - pvcreate error
Sam Peppe [EMAIL PROTECTED] - Wed, Aug 25, 2004: I've been trying to set up a volume group on a partition on an IDE hard drive (a Western Digital 80 GB) at /dev/hda. I am doing this by issuing the command pvcreate /dev/hda4. However, instead of creating the physical volume, an error is returned: Failed to create regex device filter. I don't know what this means or what I should do. Can any one provide any suggestions? Many thanks. [ I fail to see how this is related to debian-security. ] Could you strace the pvcreate call and check what tool is failing? Or maybe ltrace it? Because I don't think the error message comes from pvcreate: strings `which pvcreate` | grep regex (yields nothing) Regards, -- Loïc Minier [EMAIL PROTECTED] -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: LVM2 - pvcreate error
hi! First of all - I also think that this is nothing security related!!! maybe ltrace it? Because I don't think the error message comes from pvcreate: strings `which pvcreate` | grep regex (yields nothing) [EMAIL PROTECTED] roger # strings `which pvcreate` | grep regex regex_filter_create _Failed to create regex device filter_ devices/filter not found in config file: no regex filter installed invalid seperator at end of regex filters/filter-regex.c regex/matcher.c Couldn't parse regex regex/parse_rx.c Parse error in regex regex/ttree.c [EMAIL PROTECTED] roger # probably you got an old version of pvcreate? For my excuse - I'm doing this on a gentoo laptop cause I've no debian currently here but .. as you see the strin is in pvcreate .. alltough i don't know what it means. regards Werner -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
LVM2 - pvcreate error
Again, my apologies to all for posting my query up on the wrong news list. Just to tie off the thread, it was pointed out to me from reading the source of the LVM2 tools, that pvcreate may have been failing due to a misconfiguration in /etc/lvm/lvm.conf - it's failing to set up a filter for the devices -- this prevents the LVM from seeing the CD device, for example, and trying to scan that. This will be due to the filter= lines in the devices section of lvm.conf. Any way, I restored the /etc/lvm/lvm.conf to it's original form, and pvcreate now works again as it should. Many thanks to Werner and Loic for their help, despite the complete irrelevance of my query to this mailing list. Again I apologise to all for the posting. Sam. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 10:01:25AM +0100, Dale Amon wrote: Hashing (think of cornbeef hash with things all chopped up into bits) is a technique to generate fast lookup keys. The discussion here is about cryptographic hash functions. ...and I think somewhere in between lie hashing functions like crc32, as used for detecting transmission errors, for example. Those are not cryptographic, but possess a sufficiently large output space, so we can expect few random collisions for most practical purposes. I believe the primary difference is that a cryptographic hash is: * a uniform mapping. For input space n and output space m, there are on average n/m strings with the same hash key. Right, but I believe that a uniform mapping _also_ is a desirable property (besides speed, of course) of hashing functions as used to compute table lookup indices -- as this property assures that the data storage locations will be spread as evenly as possible across the available buckets, which in turn minimizes the time spent on resolving collisions (on average). And, as practical considerations in this case always enforce a rather small output space (i.e. number of buckets) we're certainly expecting collisions here. [1] * randomness. Input strings which differ by 1 bit in any position generate hash keys a random distance apart I'd add: * huge size of the output space (with its upper limit corresponding to the number of bits of the hash value). The probability of accidentally finding a collision is of course directly related to the size of the output space (assuming a uniform mapping). I think those are the basic properties that allow for the two desirable features 'collision resistance' and 'onewayness', which we've been discussing in this thread -- but I guess I'm not really telling you anything new... ;) If anyone knows of any other requirements, please feel free to chime in... Well, OTOH, this would probably be getting a little off-topic for debian-security (especially the debian aspect). Almut [1] for anyone who doesn't know it already, I'd recommend Bob Jenkins page on hashing: http://burtleburtle.net/bob/hash/ -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 01:15:13AM -0400, Hubert Chan wrote: Ah, but then using that definition of oneway, every hash is oneway, since there must always be some hash value corresponding to two different input strings (assuming the input space is larger than the output space, which is generally the case). Since every hash is oneway, this renders the term meaningless. So the only useful notion of oneway is that the hash is not easily invertible (i.e. you can't easily find some string that produces a given hash value). Okay, I guess I finally got it. Thanks for the clarifications. Let me just rephrase it in my own words to make sure my updated understanding now matches the notion commonly held in cryptography circles. No need to respond unless you still find some flaws in it :) So, if you can somehow come up with an input string (except by brute force search), which computes to some given hash, that means you inverted the function, and it's thus not oneway -- nothing more and nothing less. It has nothing to do with whether there exists some theoretic backward mapping from output to input that would uniquely retrieve the string originally used to compute the hash. The crucial point here simply was my rather different conception of invertability. So, now, the addition operation I mentioned is clearly _not_ oneway, in contrast to what I proclaimed originally ;) Makes sense now -- and makes much of what's been said so far appear in a different light. (And it hopefully explains some of the objections I had, that presumably must have seemed a little weird to anyone with a 'cryptographic' mindset...) Thanks again everyone for taking the time. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Thu, 26 Aug 2004, Almut Behrens wrote: On Wed, Aug 25, 2004 at 01:15:13AM -0400, Hubert Chan wrote: ... So the only useful notion of oneway is that the hash is not easily invertible (i.e. you can't easily find some string that produces a given hash value). So, if you can somehow come up with an input string (except by brute force search), which computes to some given hash, that means you inverted the function, and it's thus not oneway -- nothing more and nothing less. It has nothing to do with whether there exists some theoretic backward mapping from output to input that would uniquely retrieve the string originally used to compute the hash. confirmed. for those who are interested in this topic, I can recommend the handbook of applied cryptography. the book's chapters are available for free download at http://www.cacr.math.uwaterloo.ca/hac/ chapter 9 focuses on cryptographic hash functions. the first chapter gives an excellent general overview of cryptographic aspects in human readable form. Thanks again everyone for taking the time. you are welcome, g. - expert in just too late deliveries and applied cryptography - mail: decockd:at:esat:dot:kuleuven:dot:ac:dot:be http://godot.be godot:at:advalvas:dot:be http://godot.studentenweb.org godot:at:godot:dot:be web: http://www.esat.kuleuven.ac.be/~decockd -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: init scripts and su
Hi all! Has anyone made any progress in solving the su/sudo/super TIOCSTI ioctl vulnerability? -- Jan pgpAFoEO7DWgl.pgp Description: PGP signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 09:24:01AM -0400, Phillip Hofmeister wrote: On Tue, 24 Aug 2004 at 06:18:50PM -0400, Matthew Palmer wrote: In the case of hashing algorithms, there's one 'key' involved -- the plaintext -- and for password security, you don't need to retrieve the key necessarily, just an equivalent one. There's no guarantee that XORing MD5 and SHA-1 isn't going to produce something that is quite simple to generate equivalent plaintext for, by, for example, making it mathematically impossible for one bit in the resultant hash value to be a certain value (because MD5 and SHA-1 always set the same bit to the same value given the same input). That cuts your hash search space in half right there. I agree. There is value in maintaining two completely different data points by hashing the item with two functions though (but not XORing the result together). For example: EVEN IF hash1(x) == hash1(y), it is HIGHLY unlikely hash2(x) == hash2(y). Keeping a record of both hashes on hand provides value and strengthens your certainty of integrity on very large orders of magnitude. Indeed. Hence the crawling horror that is 'HMAC'... Holding multiple hashes is quite useful for avoiding collisions, and can help even if one hash is weak (so equivalent plaintext is easily found), but it can be tricky if one hash is found to be dangerously weak... - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 10:01:25AM +0100, Dale Amon wrote: On Wed, Aug 25, 2004 at 06:02:22AM +0200, Almut Behrens wrote: Somewhat more seriously: are there generally any defining criteria for something one would call a 'hash function', saying that it always must map some larger input space to some smaller output space? Yes. A hash function is any mapping function y = map(x) where the space y is smaller than the space x. Hashing (think of cornbeef hash with things all chopped up into bits) is a technique to generate fast lookup keys. The discussion here is about cryptographic hash functions. I believe the primary difference is that a cryptographic hash is: * a uniform mapping. For input space n and output space m, there are on average n/m strings with the same hash key. * randomness. Input strings which differ by 1 bit in any position generate hash keys a random distance apart Add to that: * An output dependence on both the value and position of *every* input byte. Kind of implied by your second postulate, but worth mentioning explicitly. Especially when people think that a simple sum is cryptographically sound -- any combination of the input letters (or other matching combinations) will produce the same hash value. - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Thu, Aug 26, 2004 at 01:04:21AM +0200, Almut Behrens wrote: ...and I think somewhere in between lie hashing functions like crc32, as used for detecting transmission errors, for example. Those are not cryptographic, but possess a sufficiently large output space, so we can expect few random collisions for most practical purposes. I wouldn't call CRC a hash code although you can use it that way I guess. It is really an error detecting and correction code that does have the ability, in a sense, to go backwards. It stands for Cyclic Redundancy Check. Such codes are redudant data, to be included with a transmission, not a hash. Some of them allow correction of multiple bit errors; typically you can detect 1 bit of error more than you can correct. Right, but I believe that a uniform mapping _also_ is a desirable property (besides speed, of course) of hashing functions as used to compute table lookup indices -- as this property assures that the data storage locations will be spread as evenly as possible across the available buckets, which in turn minimizes the time spent on resolving collisions (on average). And, as practical considerations in this case always enforce a rather small output space (i.e. number of buckets) we're certainly expecting collisions here. [1] Well, in theory yes. In practice you usually aren't much fussed if you've got a variance in the bucket utilization unless you're working on something with a real need for speed. For example, I would bet there are some really, really good uniform hash functions used inside of gcc. * randomness. Input strings which differ by 1 bit in any position generate hash keys a random distance apart I'd add: * huge size of the output space (with its upper limit corresponding to the number of bits of the hash value). The probability of accidentally finding a collision is of course directly related to the size of the output space (assuming a uniform mapping). Yes, can't argue there. That is where the basic difference between a typical hash function and a cryptographic hash comes. You want small keyspaces and very simple functions to generate lookup keys, whereas you don't much care about the function overhead for a cryptographic key as you tend not to do the encodings as often. If anyone knows of any other requirements, please feel free to chime in... Well, OTOH, this would probably be getting a little off-topic for debian-security (especially the debian aspect). -- -- Dale Amon [EMAIL PROTECTED]+44-7802-188325 International linux systems consultancy Hardware software system design, security and networking, systems programming and Admin Have Laptop, Will Travel -- signature.asc Description: Digital signature
