Monday, August 22. 2005
Some more background information about SHA1
As the article some days ago about SHA1 got a lot of interest, I thought I'll write some more background info about this, especially for people thinking that collisions aren't a big problem.
Cryptographic hash functions are functions where you can put a string of any length and get a fixed-size result. E. g. with SHA1, you get 160 bit, with MD5 128 bit. The hash-function has to fulfill some requirements:
- It should be hard to get two strings with the same hash (collision-resistant).
- It should be hard to get a string to a given hash (one-way-function).
To be more precise: In an optimal case, hard means that it shouldn't be possible with all hardware on earth in the timeframe that your cryptography needs to be secure. Some examples where cryptographic hashes are used are shadown-passwords, digital signatures or verification of file downloads.
Cryptographic hash functions are functions where you can put a string of any length and get a fixed-size result. E. g. with SHA1, you get 160 bit, with MD5 128 bit. The hash-function has to fulfill some requirements:
- It should be hard to get two strings with the same hash (collision-resistant).
- It should be hard to get a string to a given hash (one-way-function).
To be more precise: In an optimal case, hard means that it shouldn't be possible with all hardware on earth in the timeframe that your cryptography needs to be secure. Some examples where cryptographic hashes are used are shadown-passwords, digital signatures or verification of file downloads.
Now, for several hash-functions we have collisions (SHA0, RIPEMD, MD4, MD5). The most interesting is probably MD5, because it's still widely used. For SHA1, we don't have collisions yet, but the results from some chinese cryptographers say that it would be possible to create such collisions within a reasonable complexity. Due to the structure of all those hash-functions, if you have one collision, you can easily create more collisions. That means once you have collisions, you are able to create different useful different documents (by adding data to places where it's ignored) with the same hash (Here is an example, two Postscript-files with the same MD5-hash). This is important for possible attacks.
Now, I hear from many people that collisions are not that big problem, as long as you cannot find another valid string to a given hash (so-called preimage attack). I'll now describe a scenario where collisions are definitely a problem:
Let's assume you are using the famous Gentoo Linux distribution. Let's also assume that you are a careful user and are checking PGP-Signatures on the Manifests (as long as they are available, but that's another thing). Eve is evil and wants to hack your computer. Eve is also a well-known kernel-hacker and creating the ev-kernel-patchset.
Eve knows that you are using her patchset. She prepares the latest version of her patch, one usual version and one version with a backdoor implemented, both with the same MD5-hash (as Gentoo still uses MD5 for digests and Manifests). She uploads the usual version to her ftp and some Gentoo-Dev will pick it up and add it to the tree. Now, Eve is in the network where you are (probably on some computer congress), knows your MAC-Adress and uses arpspoofing to let your portage download her crafted patchset.
Your portage will check and see that it's the right MD5-sum and install it. You have the backdoor on your PC.
While there are a couple of more urgent security problems with portage, especially that a large number of packages are not pgp-signed at all and portage doesn't check those signatures by default. But it was only an example on a well-known system to show that collisions can be used to implement attacks in reality.
This is one reason why I think that all MD5 and SHA1-usage should be replaced as soon as possible. The other thing that should make us nervous: Cryptography should always be looking forward. We don't know how hard preimage attacks are, but the collisions probably show that those hashes aren't as secure as they should be. So we should expect the worst and maybe some cryptographers somewhere already have results that we don't know of.
Asking for alternatives: I'm not a cryptographer myself, so I can only repeat what others told me. The SHA-256 and SHA-512 functions are still secure. They are probably not as secure as they should be, because slightly modified variants of them already have problems. Beside the MD/RIPEMD/SHA-functions, which are all based on the same principles, we have two alternatives yet: Whirlpool and Tiger. They are both probably not as well analyzed as the SHA-functions.
I assume for low-security applications, using SHA-256 is a good idea. If you rely on very high security, you should probably use a combination of SHA-256, Whirlpool and Tiger.
For programmers out there: The mhash library gives you access to all common hash-functions from various programming languages.
Artikel von Rüdiger Weis in der CCC-Datenschleuder
Now, I hear from many people that collisions are not that big problem, as long as you cannot find another valid string to a given hash (so-called preimage attack). I'll now describe a scenario where collisions are definitely a problem:
Let's assume you are using the famous Gentoo Linux distribution. Let's also assume that you are a careful user and are checking PGP-Signatures on the Manifests (as long as they are available, but that's another thing). Eve is evil and wants to hack your computer. Eve is also a well-known kernel-hacker and creating the ev-kernel-patchset.
Eve knows that you are using her patchset. She prepares the latest version of her patch, one usual version and one version with a backdoor implemented, both with the same MD5-hash (as Gentoo still uses MD5 for digests and Manifests). She uploads the usual version to her ftp and some Gentoo-Dev will pick it up and add it to the tree. Now, Eve is in the network where you are (probably on some computer congress), knows your MAC-Adress and uses arpspoofing to let your portage download her crafted patchset.
Your portage will check and see that it's the right MD5-sum and install it. You have the backdoor on your PC.
While there are a couple of more urgent security problems with portage, especially that a large number of packages are not pgp-signed at all and portage doesn't check those signatures by default. But it was only an example on a well-known system to show that collisions can be used to implement attacks in reality.
This is one reason why I think that all MD5 and SHA1-usage should be replaced as soon as possible. The other thing that should make us nervous: Cryptography should always be looking forward. We don't know how hard preimage attacks are, but the collisions probably show that those hashes aren't as secure as they should be. So we should expect the worst and maybe some cryptographers somewhere already have results that we don't know of.
Asking for alternatives: I'm not a cryptographer myself, so I can only repeat what others told me. The SHA-256 and SHA-512 functions are still secure. They are probably not as secure as they should be, because slightly modified variants of them already have problems. Beside the MD/RIPEMD/SHA-functions, which are all based on the same principles, we have two alternatives yet: Whirlpool and Tiger. They are both probably not as well analyzed as the SHA-functions.
I assume for low-security applications, using SHA-256 is a good idea. If you rely on very high security, you should probably use a combination of SHA-256, Whirlpool and Tiger.
For programmers out there: The mhash library gives you access to all common hash-functions from various programming languages.
Artikel von Rüdiger Weis in der CCC-Datenschleuder
Posted by Hanno Böck
in Code, Cryptography, English, Gentoo, Linux
at
00:30
| Comments (0)
| Trackback (1)
Todo mundo tiene, en la actualidad, por lo menos un PC y ahora es raro que nada más se tenga uno, es muy probable que se tenga una Laptop para esos trabajos que te quieres llevar a casa o seguir trabaja...
Tracked: Aug 22, 16:20