بابک زواری
یک شنبه 13 شهریور 1384, 16:57 عصر
وداع با MD5 این عنوان مقاله ایی که چندی پیش تو یکی از سایتها دیدم
به خوندنش میارزه
One way Hash Functions
The following definitions are taken from the Bruce Schneier's Book: Applied Cryptography Second Edition:
A one-way hash function, H(M), operates on an arbitrary-length pre-image message, M. It returns a fixed-length hash value, h.
h = H(M), where h is of length m
Many functions can take an arbitrary-length input and return an output of fixed length, but one-way hash functions have additional characteristics that make them one-way [1065]:
Given M, it is easy to compute h.
Given h, it is hard to compute M such that H(M)= h.
Given M, it is hard to find another message, M’, such that H(M) = H(M’).
....
In some applications, one-wayness is insufficient; we need an additional requirement called collision-resistance.
It is hard to find two random messages, M and M’, such that H(M) = H(M’).
Hashing function used to password storing
The definition mentioned before, lead to the development of secure password storage.
The use of one way hashing function is the following algorithm:
For Password Storage, request input plain_password from user , then apply a oneway hash function H on plain_password and store it. In code stored_password = H(plain_password)
For password checking, request probe_password from user, apply H on it, and compare with stored_ password, i.e.: check ::= H(probe_password) == stored_password.
This schema it's good as long H is a good and strong hashing function.
Today, MD5 is under heavy attack, the reason is that is used on the GNU implementation of the POSIX function Crypt. In fact, in the site http://passcracking.com/ (http://passcracking.com/) you can find a lot of collisions for this function.
Is PKI also in danger ?
In recents works, three investigators: Lenstra, Wang and Weger, showed that is feasible to build colliding electronic X.509 certificates, using the MD5 collition techniques developed by Wang. You can read their paper at http://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf (http://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf).
This work violates the basic trust principles, underliying PKI (Public Key Infraestructure).
Even more, chinese investigators, has shown an attack to other Hash function: SHA-1, http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf (http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf).
Cracking MD5
The typicall way of collition search, is to use a brute-force algorithm: given a hash value h, for a plain message m, written in an alphabet A, then h = MD5(m), so in brute force collition search, we try every posible combination in alphabet A we find a m' message such as MD5(m') = h. m' can be or not equal to m.
The Rainbow Crack (http://www.darksideprogramming.org/archives/2005/09/the_rainbow_cra.html) uses precalculated tables for intermediates steps on the process, this can accellerate the cracking process. For example, a password of up tu 14 characters, of the this charset: "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx yz0123456789!@#$%^&*()-_+=" can be cracked on few minutes.
Better One Way Hash Functions
Some people suggest to use more complicated applications of MD5, for example, use stored_password = crypt(plain_password + salt). Where key, its a fixed one or the user id, or some other fixed value. This schema is not stronger, can be show, several flaws to this approach,
Other alternatives are:
use a key based hash function
combine algorithms
use other functions
The first one relays on a key, that can be stollen. Combining algorithms is better, but probably only results on more CPU usage that real protection.
Alternatives functions
Use other functions can be a solution, but what criteria use to choose a good one?
The answer is simple, use hash functions with a bigger domain of results. For example, MD5 generates a 128 bits value, so the space of posible resulting values is 2128 in size. By simple logic, if your hash function has an output domain of a size bigger than that, then its a good alternative.
All the followings functions has stronger implementations than MD5
WHIRPOOL (http://en.wikipedia.org/wiki/WHIRLPOOL), generates a 512 bits output, RIPEMD (http://en.wikipedia.org/wiki/RIPEMD-160), uses 160, 128 or 320 bits output, and SHA-2 (http://en.wikipedia.org/wiki/SHA-2), generates 256, 512 bits ouputs.
SHA-2 is available on crypto api, and the Microsof.Net, so I suggest you to use it.
به خوندنش میارزه
One way Hash Functions
The following definitions are taken from the Bruce Schneier's Book: Applied Cryptography Second Edition:
A one-way hash function, H(M), operates on an arbitrary-length pre-image message, M. It returns a fixed-length hash value, h.
h = H(M), where h is of length m
Many functions can take an arbitrary-length input and return an output of fixed length, but one-way hash functions have additional characteristics that make them one-way [1065]:
Given M, it is easy to compute h.
Given h, it is hard to compute M such that H(M)= h.
Given M, it is hard to find another message, M’, such that H(M) = H(M’).
....
In some applications, one-wayness is insufficient; we need an additional requirement called collision-resistance.
It is hard to find two random messages, M and M’, such that H(M) = H(M’).
Hashing function used to password storing
The definition mentioned before, lead to the development of secure password storage.
The use of one way hashing function is the following algorithm:
For Password Storage, request input plain_password from user , then apply a oneway hash function H on plain_password and store it. In code stored_password = H(plain_password)
For password checking, request probe_password from user, apply H on it, and compare with stored_ password, i.e.: check ::= H(probe_password) == stored_password.
This schema it's good as long H is a good and strong hashing function.
Today, MD5 is under heavy attack, the reason is that is used on the GNU implementation of the POSIX function Crypt. In fact, in the site http://passcracking.com/ (http://passcracking.com/) you can find a lot of collisions for this function.
Is PKI also in danger ?
In recents works, three investigators: Lenstra, Wang and Weger, showed that is feasible to build colliding electronic X.509 certificates, using the MD5 collition techniques developed by Wang. You can read their paper at http://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf (http://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf).
This work violates the basic trust principles, underliying PKI (Public Key Infraestructure).
Even more, chinese investigators, has shown an attack to other Hash function: SHA-1, http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf (http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf).
Cracking MD5
The typicall way of collition search, is to use a brute-force algorithm: given a hash value h, for a plain message m, written in an alphabet A, then h = MD5(m), so in brute force collition search, we try every posible combination in alphabet A we find a m' message such as MD5(m') = h. m' can be or not equal to m.
The Rainbow Crack (http://www.darksideprogramming.org/archives/2005/09/the_rainbow_cra.html) uses precalculated tables for intermediates steps on the process, this can accellerate the cracking process. For example, a password of up tu 14 characters, of the this charset: "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx yz0123456789!@#$%^&*()-_+=" can be cracked on few minutes.
Better One Way Hash Functions
Some people suggest to use more complicated applications of MD5, for example, use stored_password = crypt(plain_password + salt). Where key, its a fixed one or the user id, or some other fixed value. This schema is not stronger, can be show, several flaws to this approach,
Other alternatives are:
use a key based hash function
combine algorithms
use other functions
The first one relays on a key, that can be stollen. Combining algorithms is better, but probably only results on more CPU usage that real protection.
Alternatives functions
Use other functions can be a solution, but what criteria use to choose a good one?
The answer is simple, use hash functions with a bigger domain of results. For example, MD5 generates a 128 bits value, so the space of posible resulting values is 2128 in size. By simple logic, if your hash function has an output domain of a size bigger than that, then its a good alternative.
All the followings functions has stronger implementations than MD5
WHIRPOOL (http://en.wikipedia.org/wiki/WHIRLPOOL), generates a 512 bits output, RIPEMD (http://en.wikipedia.org/wiki/RIPEMD-160), uses 160, 128 or 320 bits output, and SHA-2 (http://en.wikipedia.org/wiki/SHA-2), generates 256, 512 bits ouputs.
SHA-2 is available on crypto api, and the Microsof.Net, so I suggest you to use it.