Re: apt 0.6 and how it does *not* solve the problem
On Mon, Aug 23, 2004 at 01:03:54AM +0200, martin f krafft wrote: So if I wanted to attack 80% of all Debian machines all over the world, I would try to compromise one of the 1000 keys, thereby getting write access to the incoming queue. Then, I could NMU a package and upload a trojaned version, best one that waits a year before activating, just to make sure I actually hit stable. What about a --paranoid option, which makes apt warn on several (slightly) suspicious changes: - NMUs - changes of maintainership - new maintainers (not maintaners new to debian, but maintainers I didn't implicitly trust before by having installed one of their packages) To make the last point more useful, one could add a concept of secondary signatures, and ask developers to review and certify packages of other developers. This could potentially reduce the number of developers one has to trust for a given installation. To give some numbers: On my laptop, which runs sid, and some packages from experimental, I have 1332 installed packages by 407 different maintainers. Not counting NMUs and ignoring groups of people (eg. Debian GCC maintainers), I'd be only vulnerable if one of these 407 keys are compromised. But 331 of these 407 maintainers have less than 5 packages installed on my computer, and 189 have only one. I guess this number could be vastly reduced by secondary signatures, bringing the number of people I'd have to trust down to, perhaps, 100-200. While this is still a large number, it's much better than 1000. (BTW I didn't verify this number - do we really have 1000 developers by now?) Please don't consider this as a proposal - it's just a spontanous idea, which may not be feasible. But then, perhaps it has some potential, so I wanted to share it. Jan -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: apt 0.6 and how it does *not* solve the problem
also sprach Thomas Bushnell BSG [EMAIL PROTECTED] [2004.08.24.0312 +0200]: But how does this false sense cause a problem? For example, if users regularly scanned all the source code on their system, and this would cause them to stop doing so, then the false sense would be a problem! I see that I am a little off with the false sense of security. I just had many a user tell me that package signatures solves all problems and insures that no trojans can be distributed. And this is a belief that I think needs to be addressed at the same time as introducing package signatures. Please don't speak of the issue. There are many issues, True enough. and why I object to your do nothing proposal, as that it seems to me that you are saying we should solve any of these issues until we can solve them all. This attitude is facilitated by treating it as the issue, which isn't solved (in your mind) unless it is solved in its entirety. Also, true. Instead, think about it as many different issues. We can solve one of them, and thus make progress, without necessarily having solved every one. I mainly wanted to bring the issue up for disucssion. Unfortunately, I am really unable these days to instantiate countermeasures. The logical conclusion from your arguments is that we should actually remove the ssh package from Debian! How so? -- Please do not CC me when replying to lists; I read them! .''`. martin f. krafft [EMAIL PROTECTED] : :' :proud Debian developer, admin, and user `. `'` `- Debian - when you have better things to do than fixing a system Invalid/expired PGP subkeys? Use subkeys.pgp.net as keyserver! signature.asc Description: Digital signature
MD5 collisions found - alternative?
Hi, Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: http://eprint.iacr.org/2004/199.pdf http://www.freedom-to-tinker.com/archives/000664.html http://www.unixwiz.net/techtips/iguide-crypto-hashes.html My question is: Is there an easy way to make my debian sid installation use something else (better) than md5 for various things? Namely SHA-1 with some longer output in PAM. Thanks, Robert -- http://deepblue.sk/~r0b0/web/ PGP fingerprint: FEB3 D653 F918 8B07 83B1 E4BD A3ED B11E 1DD5 ACD7 signature.asc Description: OpenPGP digital signature
Abwesenheit
Abwesenheit Sehr geehrte Damen und Herren, ich bin in der Zeit vom 21. August bis zum 9. September im Urlaub. In dieser Zeit können Sie sich an Herrn Zander wenden. Telefon 0391 544 56 70 Mit freundlichen Grüßen Sebastian Hennebrüder Leitung eCommerce - Internet --- Grass GmbH, eCommerce - Internet Allee-Center Ernst-Reuter-Allee 5 39104 Magdeburg Germany National Telefon 0391 / 54456 76 Fax 0391 / 54456 - 78 International Telefon ++49 391 / 54456 76 Fax ++49 391 / 54456 - 78 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
hi, it is true that collisions have been found in md5 (and a lot of other hash functions of that `family', cfr. the links you mention). this means that the hash functions should certainly no longer be used in applications relying on the collision-resistance of the hash function, e.g., everything where md5withRsa is used should be replaced (note that md5 was considered deprecated already mid-nineties), but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... cu, 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 On Tue, 24 Aug 2004, Robert Trebula wrote: Hi, Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: http://eprint.iacr.org/2004/199.pdf http://www.freedom-to-tinker.com/archives/000664.html http://www.unixwiz.net/techtips/iguide-crypto-hashes.html My question is: Is there an easy way to make my debian sid installation use something else (better) than md5 for various things? Namely SHA-1 with some longer output in PAM. Thanks, Robert -- http://deepblue.sk/~r0b0/web/ PGP fingerprint: FEB3 D653 F918 8B07 83B1 E4BD A3ED B11E 1DD5 ACD7 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 01:13:43PM +0300, Robert Trebula wrote: Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: That is expected--a hashing algorithm will always have collisions if the number of inputs is greater than the output space. As for your question, the answer depends on what you are using md5 for. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 07:36:36AM -0400, Michael Stone wrote: That is expected--a hashing algorithm will always have collisions if the number of inputs is greater than the output space. As for your question, This seems to be different. Look at the URLs from the OP. pgpDz6ryj9TpL.pgp Description: PGP signature
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: it is true that collisions have been found in md5 (and a lot of other hash functions of that `family', cfr. the links you mention). Collisions have been found? Collisions were always. Every hashing algorithm makes collisions... that's just natural. They found way to generate two input values that makes the same hash. That's still long way before they can generate input having hash of another input. regards fEnIo ps. could you please stop toppost? -- _ Bartosz Fenski | mailto:[EMAIL PROTECTED] | pgp:0x13fefc40 | IRC:fEnIo _|_|_ 32-050 Skawina - Glowackiego 3/15 - w. malopolskie - Polska (0 0) phone:+48602383548 | Slackware - the weakest link ooO--(_)--Ooo http://skawina.eu.org | JID:[EMAIL PROTECTED] | RLU:172001 signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 01:51:57PM +0200, Jan Minar wrote: Look at the URLs from the OP. I'd seen them before he posted. It doesn't change what I said. The possibility of md5 collisions has always been present. What we have now is a confirmed collision. Ok. There's no indication of how the collision was generated, so it's not clear that you can generate a collision for arbitrary data, or that you can generate a valid string with a colliding value, or that you can generate data to match an arbitrary hash value. So the question remains, what are you using md5 for? This definately requires some more research, but that should be done in a deliberate fashion rather than running around chicken-little style shouting a collision has been found. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
Robert Trebula wrote: Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: http://eprint.iacr.org/2004/199.pdf http://www.freedom-to-tinker.com/archives/000664.html http://www.unixwiz.net/techtips/iguide-crypto-hashes.html My question is: Is there an easy way to make my debian sid installation use something else (better) than md5 for various things? Namely SHA-1 with some longer output in PAM. I think cryptanalysts have 'cracked' pretty much all of them, though with practically prohibitive costs of cracking them (eg, 2^50 for SHA-0). http://www.mail-archive.com/[EMAIL PROTECTED]/msg02554.html http://www.freedom-to-tinker.com/archives/000661.html However, a 2^50 chance, as opposed to the ideal 2^160 still strikes me as pretty good chances. Maybe I'm just not paranoid enough to be a cryptographer ;-). My personal thought is that you could make the hash more secure simply by running md5 and SHA1 (maybe pepper on another one for good luck) across a single stream at the same time, and simply xor the resultant hashes together. You could pretty much add up the cost of the attacks against the keys. An exploration of this approach has just been uploaded to CPAN as Digest::SV1. It's at; http://search.cpan.org/dist/Digest-SV1 Sam. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
Bartosz Fenski aka fEnIo wrote: Collisions have been found? Collisions were always. Every hashing algorithm makes collisions... that's just natural. They found way to generate two input values that makes the same hash. That's still long way before they can generate input having hash of another input. That's exactly what they did - found two matching values using substantially less than the square root of the key space of iterations. They reckoned ~~2^50 iterations to find a matching block for a given SHA-0 checksum. With some heavy duty FPGA's you can build circuits to crack that space pretty quickly, today, with enough money. ie, they found an algorithm and beat the birthday paradox by a few orders of magnitude. Sam. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On 24 Aug 2004, Robert Trebula wrote: Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: http://eprint.iacr.org/2004/199.pdf http://www.freedom-to-tinker.com/archives/000664.html http://www.unixwiz.net/techtips/iguide-crypto-hashes.html My question is: Is there an easy way to make my debian sid installation use something else (better) than md5 for various things? Namely SHA-1 with some longer output in PAM. The SHA family have also been found to be weaker than expected also, so it looks like both common crypto hash sets are on somewhat shaky ground at the moment. The best current answer is probably to wait a month or two as the dust settles and the crypto community, especially through the IETF, move forward with recommendations about where we go from here. Jumping half-prepared to some other hash opens the door to a second costly migration if your hash of choice turns out to be the wrong one. ;) Also, while there are issues with those hash algorithms, I don't think they are quite bad enough that there is a significant *immediate* risk to my systems; the cost of breaking in through the detected collisions is lower than the risk of a bad password, etc. Daniel -- In protocol design, perfection has been reached not when there is nothing left to add, but when there is nothing left to take away. -- RFC 1925 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On 24 Aug 2004, Sam Vilain wrote: Robert Trebula wrote: Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: [...] I think cryptanalysts have 'cracked' pretty much all of them, though with practically prohibitive costs of cracking them (eg, 2^50 for SHA-0). [...] My personal thought is that you could make the hash more secure simply by running md5 and SHA1 (maybe pepper on another one for good luck) across a single stream at the same time, and simply xor the resultant hashes together. You could pretty much add up the cost of the attacks against the keys. Be aware that this sort of technique multi-encryption technique can lead to significant exposures when applied to traditional crypto; it can produce results that allow a vastly simpler attack on the protected information. I would not put my name to a recommendation about how to make a cryptographic product or protocol more secure unless I had sufficient background in the area to know the full implications of my recommended actions. Regards, Daniel -- If a joke is worth telling, it's worth telling once. -- Ollie MacNoonan -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: apt 0.6 and how it does *not* solve the problem
martin f krafft [EMAIL PROTECTED] writes: The logical conclusion from your arguments is that we should actually remove the ssh package from Debian! How so? If we shouldn't sign and check signatures because there are still ways of subverting one's ssh binary, then we shouldn't even distribute ssh binaries. Doesn't such distribution cause a false sense of security? -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: sshd: Logging illegal users
On Fri, 20 Aug 2004 02:26:17 -0600, Will Aoki wrote: Set LogLevel VERBOSE in /etc/ssh/sshd_config LogLevel is already set to VERBOSE. But even with LogLevel DEBUG the invalid usernames are not logged. :-( I tested that on three different machines running Debian/woody. It works for me on all of my machines running woody, including a fresh installation I did last week. I just figured out that when setting UsePrivilegeSeparation to no in sshd_config, also sshd on Debian/woody logs sshd[xxx]: Failed auth-method for illegal user user from xxx.xxx.xxx.xxx port x ssh2 But with PrivilegeSeparation turned on, the username is not logged. However, sshd from Debian/sarge also logs the illegal usernames with PrivilegeSeparation turned on. So I wonder if you do not use PrivilegeSeparation on your woody installations? - Thomas -- PGP: 2047Bit RSA, ID 0x668E601D - Encrypted mail welcome! -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: sshd: Logging illegal users
On Thu, 19 Aug 2004 11:52:51 +0300 (EEST), Martin Fluch wrote: Do you really want to log those illegal user names? If you do so, you would run into danger to log passwords in plain text as well, when you accidently enter the password when ssh asks you for the user name... I'm aware of that, but there are situations when logging the usernames is quite interesting. For example, if there is an increase in ssh scanning like over the last weeks, it is nice to put a machine on the net which offers no other services (kind of a honeypot) and see what usernames the attackers are trying. - Thomas -- PGP: 2047Bit RSA, ID 0x668E601D - Encrypted mail welcome! -- 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 10:50:38AM -0400, Daniel Pittman wrote: Be aware that this sort of technique multi-encryption technique can lead to significant exposures when applied to traditional crypto; it can produce results that allow a vastly simpler attack on the protected information. I would not put my name to a recommendation about how to make a cryptographic product or protocol more secure unless I had sufficient background in the area to know the full implications of my recommended actions. 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. -- Phillip Hofmeister -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: apt 0.6 and how it does *not* solve the problem
also sprach Thomas Bushnell BSG [EMAIL PROTECTED] [2004.08.24.1840 +0200]: If we shouldn't sign and check signatures because there are still ways of subverting one's ssh binary, then we shouldn't even distribute ssh binaries. Doesn't such distribution cause a false sense of security? Yeah well, I guess it does all boil down to attack vectors... PS: Please don't CC me. -- Please do not CC me when replying to lists; I read them! .''`. martin f. krafft [EMAIL PROTECTED] : :' :proud Debian developer, admin, and user `. `'` `- Debian - when you have better things to do than fixing a system Invalid/expired PGP subkeys? Use subkeys.pgp.net as keyserver! signature.asc Description: Digital signature
Re: get notice of sec update if package is on hold
Am Monday, 23. August 2004 19:38 schrieb PaulNM: Just a note: I have 149 emails in my deb-sec-announce folder. The earliest is dated 12/30/2003, and the latest is 8/18/2004. Security announce is NOT a high volume list, if that's your concern. PaulNM High volume is not my concern and of course I am subscribed to debian-security-announce. I came across this issue because I patched a package, recompiled it and installed it via dpkg. After that apt-get upgrade wanted to replace my shiny patched package, which is not what I want. Thus I put it on hold. I also got a daily apt-get update apt-get upgrade -f script running on every machine. It only downloads new packages and mails the results to me so I can do the real upgrade. But If a package is on hold, I don't get notice of it any more. I think I have to change my daily update script and make it look somewhere else in the system, like Thomas Stemler pointed out. Just following deb-sec-announce is not automatic enough for me. The debian systems I administer know better which packages are installed on them and can tell me what should be done. Please correct me if I am wrong or give me advice how I could do it better. Thanks. Timo -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: (...) but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... not sure I understand -- so, if someone would like to explain this aspect to the non-cryptographist, please go ahead :) I always thought that the oneway-feature is not particularly relevant when verifying passwords... In other words, if you can find (within a reasonable amount of time) any input string that produces the same given digest, then any password verification system will let you in, independently of whether you ever get to know the original password... In that case, I believe, you'd even have less constraints to satisfy, than when trying to find a collision for a message digest used to verify the integrity of some executable, for example (to protect against trojans, etc.). In the latter case, a large portion of the input would have to be identical (so the trojan will essentially do the same thing as the real program). This means you're only left with some smaller fraction of the binary to fiddle with in an attempt to yield the same message digest for both program versions (compensating for the modifications you made to the code). I'd suspect that the reduced degrees of freedom in the latter case would make it harder to find an appropriate collision. Or am I completely on the wrong track? Just wondering... Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 08:22:54PM +0200, Almut Behrens wrote: I always thought that the oneway-feature is not particularly relevant when verifying passwords... In other words, if you can find (within a reasonable amount of time) any input string that produces the same given digest, then any password verification system will let you in, independently of whether you ever get to know the original password... Right. But since we know basically nothing about how the collision was generated we don't know if there's a way to find a message that has a given md5 hash value. IOW, the mechanism to generate the collision may only work with certain carefully chosen input data. Until more details are given it's all speculation. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
MD5 crack and passwords
It is not always enough or required to find something that has the right hash value. With windows a modified client can authentication just by knowing the hash value (and there is no salt). [Windows does not use MD5, but that is beside the point.] What I have implemented on the web requires knowledge of a RSA private key, like NIS+. The normal way to get this is to compute MD5 of the password and salt, and use this to decrypt the server's encrypted version. Using an inverse MD5 genie to attack this scheme seems a little silly. You do not need to be authenticating over an insecure network to implement this but it helps :-) It is perhaps worth noting that the two public byte sequences are *very* similar, so it might be possible to do this trick within the limits of a trojanised binary. Without more information nobody can say. -- 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, Almut Behrens wrote: On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: (...) but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... not sure I understand -- so, if someone would like to explain this aspect to the non-cryptographist, please go ahead :) a cryptographic hash function, such as md5, sha1, ripemd-160, to name the most commonly used cryptographic hash functions are constructed to have at least the following properties: 1. it is hard to find two distinct inputs to the hash function, say x and y, so that hash(x) equals hash(y) 2. they are one-way, i.e., it is hard to find the value x given hash(x) note that these properties have nothing to do with encryption mechanisms. that is a complete other business. for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. for digital signature schemes, we need the first property: if I have someone sign a document, say A, the document itself is not signed, but the hash of that document. if a hash function which is not collision-resistant is used in an application where that property matters, the attack scenario goes as follows: if I know there are two documents, say B and C, which hash to the same hash value, i.e., hash(B) = hash(C), and I have you sign hash(B), you have also produced a digital signature on document C. the meaning of `the hash function is not collision-resistant' is this: I know these documents B and C exist, and they are more or less easy to find. if the hash function were collision-resistant, I know they exist, but they are *not* easy to find. the attacks described in the paper referred to in the original post do give examples of different inputs which hash to the same output. for some of the hash algorithms that have been broken, this requires *very* limited resources. the authors refer to `calculations by hand' ];- the exact procedure to find these inputs does not really matter: showing the existance of even a single pair of inputs is sufficient to show the hash function is not collision-resistant, and that is what the authors did, i.e., full stop. therefore, the broken hash functions should not be used for schemes where the collision-resistance is important. all this means that these functions can still be used for applications if one only needs the one-way property of the function, e.g., to hash passwords. does this clarify things a bit more? :)) Almut - 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: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote: On Tue, 24 Aug 2004, Almut Behrens wrote: On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: (...) but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... not sure I understand -- so, if someone would like to explain this aspect to the non-cryptographist, please go ahead :) a cryptographic hash function, such as md5, sha1, ripemd-160, to name the most commonly used cryptographic hash functions are constructed to have at least the following properties: 1. it is hard to find two distinct inputs to the hash function, say x and y, so that hash(x) equals hash(y) 2. they are one-way, i.e., it is hard to find the value x given hash(x) just to make sure we're using the same terminology: 1. is what I'd consider collision resistance, whereas the oneway aspect (2.) refers to the difficulty of retrieving the original string (x above) used in computing the hash in the first place. for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. but that's property 1 then (i.e. collision resistance), isn't it? And that's essentially what I was trying to point out, as I don't think that, WRT password verification, you'll ever need to know the original x. It's completely sufficient to find some other password y, z, or whatever, such that hash(some_password) == stored_hash where the stored/given hash has originally been computed as hash(x). Thus, I'd still say it's not the oneway aspect that matters here, but rather the collision resistance of the hash function... Of course, as Mike has already pointed out, it's a completely different story whether you can find _any_ collision (for an arbitray hash value), or a collision for some _given_ cryptographic hash value. Otherwise, I hardly have any objections to what you wrote :) does this clarify things a bit more? :)) not so sure... :) -- i.e. I don't really see a huge conceptual difference between two 'passwords' or 'documents' hashing to the same value... Also, here again, as I tried to point out in my previous post, I'd say that with finding passwords, you have more degrees of freedom. All that matters is that their hashes are identical, when you want to get access -- the string itself is totally irrelevant. While with signing documents, you'd probably have some very specific message in mind (at least not some random string) that you'd like to fake as originating from someone else. Thanks, Almut -- 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, Almut Behrens wrote: On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote: On Tue, 24 Aug 2004, Almut Behrens wrote: On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: (...) but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... a cryptographic hash function, such as md5, sha1, ripemd-160, to name the most commonly used cryptographic hash functions, are constructed to have at least the following properties: 1. it is hard to find two distinct inputs to the hash function, say x and y, so that hash(x) equals hash(y) 2. they are one-way, i.e., it is hard to find the value x given hash(x) just to make sure we're using the same terminology: 1. is what I'd consider collision resistance, whereas the oneway aspect (2.) refers to the difficulty of retrieving the original string (x above) used in computing the hash in the first place. confirmed. for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. but that's property 1 then (i.e. collision resistance), isn't it? not exactly the same, but it is true that the two properties are somehow related: if you can find a z so that hash(z) equals hash(x), and x and z are different, then you have found a collision, if not, you have inverted the hash function. being able to invert a hash function clearly means that the function is not collision-resistant, but finding collisions does not mean that the hash function is not one-way :) summarizing: an attack relying on the collision-resistance takes as input two values x and y and results in an output hash(x) which equals hash(y), but an attack on the one-way property of the hash function takes as input hash(x) and produces an output z so that hash(z) equals hash(x). this is quite different, isn't it? :) And that's essentially what I was trying to point out, as I don't think that, WRT password verification, you'll ever need to know the original x. It's completely sufficient to find some other password y, z, or whatever, such that hash(some_password) == stored_hash where the stored/given hash has originally been computed as hash(x). this is true, but this relies on the one-way property of the hash function, not on its collision-resistance: in userid/password verification schemes, one is given an output of the hash function, namely hash(password), and even if there were a collision for the hash function, chances are slim that the password equals the particular input which produces the collision... the attack scenario is different... Thus, I'd still say it's not the oneway aspect that matters here, but rather the collision resistance of the hash function... Of course, as Mike has already pointed out, it's a completely different story whether you can find _any_ collision (for an arbitray hash value), or a collision for some _given_ cryptographic hash value. Otherwise, I hardly have any objections to what you wrote :) does this clarify things a bit more? :)) not so sure... :) -- i.e. I don't really see a huge conceptual difference between two 'passwords' or 'documents' hashing to the same value... there is a difference: the passwords are not directly fed to the hash function. they are first encoded/expanded to make them of the proper size (i.e., 512 bits) for the hash function. in what I said/wrote, `document' one might read `input block for the hash function' ];-) the attacks described in the papers referred to in the original post deal with input blocks which are crafted to produce a collision, and these input blocks can be preceded by any number of `document' content, so the attacks do not really apply to password-based schemes, but they do on documents... cu, g. Thanks, Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED] -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: get notice of sec update if package is on hold
Timo == Timo Veith [EMAIL PROTECTED] writes: [...] Timo High volume is not my concern and of course I am subscribed to Timo debian-security-announce. I came across this issue because I Timo patched a package, recompiled it and installed it via dpkg. After Timo that apt-get upgrade wanted to replace my shiny patched package, Timo which is not what I want. Thus I put it on hold. When you patch and recompile a package, you should bump up the version number slightly by editing the debian/changelog file and adding a new entry. Then it won't bother you about wanting to upgrade. -- Hubert Chan [EMAIL PROTECTED] - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 12:20:24PM -0400, Phillip Hofmeister wrote: On Tue, 24 Aug 2004 at 10:50:38AM -0400, Daniel Pittman wrote: Be aware that this sort of technique multi-encryption technique can lead to significant exposures when applied to traditional crypto; it can produce results that allow a vastly simpler attack on the protected information. I would not put my name to a recommendation about how to make a cryptographic product or protocol more secure unless I had sufficient background in the area to know the full implications of my recommended actions. 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. For random values of X and Y, you are correct, there is no reason to assume that you will get an easier time of it. However, there are plenty of examples where (for instance) applying the same algorithm N times does not produce N times the security, or even the same level of security. The same adverse interaction occurs when you mix different algorithms. 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. 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. It's those sorts of tricky interactions (which aren't immediately obvious) which I'm sure led Daniel to warn of the dangers of simplistic security upgrades. - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 12:44:43AM +1000, Daniel Pittman wrote: Also, while there are issues with those hash algorithms, I don't think they are quite bad enough that there is a significant *immediate* risk to my systems; the cost of breaking in through the detected collisions is lower than the risk of a bad password, etc. I think you meant s/cost/risk/ there. And I thoroughly agree -- it still appears to be far easier to brute-force check the poor-password-space than it is to reverse-generate an equivalent plaintext given a random MD5 hash. - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
* Quoting Almut Behrens ([EMAIL PROTECTED]): On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote: a cryptographic hash function, such as md5, sha1, ripemd-160, to name the most commonly used cryptographic hash functions are constructed to have at least the following properties: 1. it is hard to find two distinct inputs to the hash function, say x and y, so that hash(x) equals hash(y) 2. they are one-way, i.e., it is hard to find the value x given hash(x) just to make sure we're using the same terminology: 1. is what I'd consider collision resistance, whereas the oneway aspect (2.) refers to the difficulty of retrieving the original string (x above) used in computing the hash in the first place. ACK. for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. but that's property 1 then (i.e. collision resistance), isn't it? And that's essentially what I was trying to point out, as I don't think that, WRT password verification, you'll ever need to know the original x. It's completely sufficient to find some other password y, z, or whatever, such that hash(some_password) == stored_hash where the stored/given hash has originally been computed as hash(x). Thus, I'd still say it's not the oneway aspect that matters here, but rather the collision resistance of the hash function... If you can calculate the password from the hash it would be a flaw in the one way funktion. If you can calculate a collision from the hash and the known password, that would be a lack off collision resistance. Of course, as Mike has already pointed out, it's a completely different story whether you can find _any_ collision (for an arbitray hash value), or a collision for some _given_ cryptographic hash value. The difference between a hash for a signature and a hash for a password is that you know the plain text in the first case. does this clarify things a bit more? :)) not so sure... :) -- i.e. I don't really see a huge conceptual difference between two 'passwords' or 'documents' hashing to the same value... See above. Also, here again, as I tried to point out in my previous post, I'd say that with finding passwords, you have more degrees of freedom. All But less knowledge. that matters is that their hashes are identical, when you want to get access -- the string itself is totally irrelevant. While with signing It has to meet certain criterias like being printable characters and having a certain length, but it doesn't have to have a meaning. documents, you'd probably have some very specific message in mind (at least not some random string) that you'd like to fake as originating from someone else. 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. - 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 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... Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
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!. - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On 25 Aug 2004, Matthew Palmer wrote: On Tue, Aug 24, 2004 at 12:20:24PM -0400, Phillip Hofmeister wrote: On Tue, 24 Aug 2004 at 10:50:38AM -0400, Daniel Pittman wrote: Be aware that this sort of technique multi-encryption technique can lead to significant exposures when applied to traditional crypto; it can produce results that allow a vastly simpler attack on the protected information. I would not put my name to a recommendation about how to make a cryptographic product or protocol more secure unless I had sufficient background in the area to know the full implications of my recommended actions. 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. For random values of X and Y, you are correct, there is no reason to assume that you will get an easier time of it. However, there are plenty of examples where (for instance) applying the same algorithm N times does not produce N times the security, or even the same level of security. The same adverse interaction occurs when you mix different algorithms. [...] It's those sorts of tricky interactions (which aren't immediately obvious) which I'm sure led Daniel to warn of the dangers of simplistic security upgrades. Matt is entirely correct in his statements - this is *precisely* the issue that I am concerned with. I cannot say that SHA1(f) xor MD5(f) is weaker or stronger than either of those two on their own, because I don't know cryptographic algorithm design well enough. It is very hard to design a good cryptographic algorithm, though, and even harder to build a useful cryptographic system around a good algorithm. To quote from memory, unless you happen to be Bruce Schneier you probably can't design a secure cryptographic system on the back of a napkin, and you are almost certainly better off not trying. :) Regards, Daniel -- Crying loud, you're crawling on the floor Just a beautiful baby, You're nothing more -- Switchblade Symphony, _Clown_ -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote: for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. but that's property 1 then (i.e. collision resistance), isn't it? not exactly the same, but it is true that the two properties are somehow related: if you can find a z so that hash(z) equals hash(x), and x and z are different, then you have found a collision, if not, you have inverted the hash function. I totally agree so far. being able to invert a hash function clearly means that the function is not collision-resistant, does it? (presuming that retrieving that x from hash(x) is not considered 'finding a collision' -- there might not necessarily exist another input value with the same hash, after all) On a related note, as hash functions typically are many-to-one type of mappings, how can they ever be inverted anyway? summarizing: an attack relying on the collision-resistance takes as input two values x and y and results in an output hash(x) which equals hash(y), but an attack on the one-way property of the hash function takes as input hash(x) and produces an output z so that hash(z) equals hash(x). this is quite different, isn't it? :) hmm, well, I guess that's where our notions/terminology start to differ slightly... The main difference I see there is in the intent of the attacks, not so much in the property they're trying a attack (or the lack of a property the attack tries to exploit). The first type aims at finding some y for some given x, so that their hashes do not differ, but it's irrelevant what the specific hash value is. The second type starts from some given hash(x), and tries to find some z that yields the same hash (as in the password cracking case). But both types of attacks are based on the existence of collisions. Only trying to find that very x that originally produced hash(x) would be an attack on the one-way property, IMHO. I don't quite see why the second attack must have anything to do with the function being one-way or not: even if the function was perfectly one-way, but not collision-resistant, you might still find that z (z is not necessarily the inverse of hash(x) after all -- at least not as I understand the term... :) Let me just use a trivial example - the simple addition operation - to elaborate on my notions of 'onewayness' and 'collision resistance': When we add 2+3, we get 5. Great. :) That sum kind of represents the 'hash' or checksum. This operation is clearly not reversible (i.e. when only being given the 5, you can never tell for sure whether 2+3, 1+4, -13+18, etc. were being added up). Thus, it's 'oneway', as I understand the term. But it's more than trivial to come up with many, many pairs of input values adding up to the same sum. That's essentially what I thought is called 'finding a collision' -- leaving it entirely open whether this can generally be done for some given hash (sum), or only for some prior unknown hash... Anyhow, as open as my definitions currently are, just as open am I to adjust them as required :) I guess we're basically all having the same concepts in the back of our minds. We're just using different terminology (or the same terminology in different ways) to talk about them -- which is always an unfailing recipe for causing confusion... Almut -- 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 12:39:57AM +0200, Rolf Kutz wrote: If you can calculate a collision from the hash and the known password, that would be a lack off collision resistance. Is knowing the password really a prerequisite? I'd have said that if you can find a collision at all, or calculate a collision for a given hash, that would be lack of collision resistance... The difference between a hash for a signature and a hash for a password is that you know the plain text in the first case. Sure. But does it really make such a difference for finding a collision, if you know the plaintext, rather than its hash? The latter can always be computed trivially in the usual forward fashion. (Just asking out of curiosity, not to argue in any direction whatsoever...) documents, you'd probably have some very specific message in mind (at least not some random string) that you'd like to fake as originating from someone else. 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. I agree, in general. OTOH, if you have something like a tar.gz file, I'd presume it's rather challenging to make some change to the content being packaged in such a way that both tar.gz's still have the same md5, same size -- and unpack without error. And even more challenging, if that change is supposed to achieve a certain predefined effect... ;) Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 11:01:58PM +0200, Moritz Schulte wrote: (...) But if your hash function is pretty good in respect to collision-resistance but is not one-way (being similar to a 1:1 mapping between hash input and hash output), you could simply apply the inverse function to your hash output and are already done. If that was possible for md5, it would be an ingenius compression algorithm, as you could sqeeze several hundred Megs or more into 128 bits, and still be able to retrieve the original data... ;) 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? I'm thinking of something like the following: a trivial, reversible 1:1 mapping would be to simply rotate every ASCII value in a string by some N (e.g. 1-2, 2-3, ..., 255-1). That procedure would fit the above mentioned properties, in that it's perfectly reversible, and also pretty collision-resistant -- at least, from the top of my head, I couldn't think of any reason why there should be any two inputs mapping to the same output. But I don't think that that'd be considered a hash function... (BTW, I'm not making any claims whatsoever about its usefulness in the context of computing checksums, so please don't get me wrong there.) Anyway, it's 6 a.m. here, and I got to get some sleep now... so, I won't pester you any further :) Thanks everyone for the input! Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
Almut == Almut Behrens [EMAIL PROTECTED] writes: Almut On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote: [...] Danny being able to invert a hash function clearly means that the Danny function is not collision-resistant, Almut does it? (presuming that retrieving that x from hash(x) is not Almut considered 'finding a collision' -- there might not necessarily Almut exist another input value with the same hash, after all) But there must exist some hash value that is mapped from multiple inputs. And most likely, most hash values would be mapped from multiple inputs. Of course finding a collision still involves some luck, but not nearly as much as if you didn't have an inverse. Basically, if you take a random string, hash it, and take the inverse, the odds are pretty low that the inverse is the same as the original string. If you repeat multiple times with different random initial strings, you'll be very unlucky to have to do that for a long time. Almut On a related note, as hash functions typically are many-to-one Almut type of mappings, how can they ever be inverted anyway? I assume it to mean: find any string for which the hash value is the same as the given hash value. The string does not have to be the same as the original. (Of course, any hash function is invertible by using brute force. So when Danny says being able to invert a hash function, there's an implicit efficiently or easily in there.) [...] Almut Let me just use a trivial example - the simple addition operation Almut - to elaborate on my notions of 'onewayness' and 'collision Almut resistance': When we add 2+3, we get 5. Great. :) That sum kind Almut of represents the 'hash' or checksum. This operation is clearly Almut not reversible (i.e. when only being given the 5, you can never Almut tell for sure whether 2+3, 1+4, -13+18, etc. were being added Almut up). Thus, it's 'oneway', as I understand the term. 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). -- Hubert Chan [EMAIL PROTECTED] - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of unsubscribe. Trouble? Contact [EMAIL PROTECTED]
