Two of my friends, set in during the week of questions about the same in essence (some in spirit: "And I heard that MD5/SHA-1 been hacked, why do we still use them?") have prompted me to write this article, although the main events described below, there were already more than 3 years ago.
General information (experts - to pass without a doubt)
As you know, cryptographic hash sums differ from usual hash-sums that in addition to the basic properties required of any hash Functions:
- ability to convert the input value (usually text) of any length in the output value of fixed length,
- statistical uniformity of falling output values ??
- good "dispersion" (the difference is approximately half of the bit) output values ??even for small (perhaps only a bit) different input texts;
to cryptographic hash algorithms additional requirements:
- bit output values ??should be far beyond the capabilities of the exhaustive search for modern technology both in processing speed and volume of storage (in practice it - the bit at 128, 160, 256, and a bit)
- There should be no way (much more efficient than an exhaustive search of input values) calculate any pair of input texts, which give the output the same hash value (no matter what) - a successful attack on this requirement is called the "Conflict" hash function;
- There should be no way (much more efficient than an exhaustive search of input values) by the value of the hash function find any input text, which gives the output of the algorithm is a hash - a successful attack on this claim called the "inversion" hash function.
Three of the above requirements to cryptographically hash functions make them in fact in the IDs of fixed length for text files, and generally arbitrary blocks of information. In this case, these identifiers:
- unique on all open space of the modern information society;
- irreversible, that is, do not reveal absolutely nothing about the content of the original document.
This allows you to use a hash function in the tasks:
- verify the integrity of files, archives, assemblies, etc. (Sufficiently trusted to convey to the recipient hash for the file and if any unauthorized changes to the file immediately change its checksum hash sum)
- store passwords in an irreversible form (placed in the repository does not own passwords, and hash sum of the line, for example , the type of "constant (salt)" + "password", which allows disclosure of a hash to keep proper dictionary passphrase secret)
- digital signature of documents (properly installed EDS is not always on the file itself, that first it would be very slow, and secondly, would bear some of the problems with the security of the signature key, and its hash sum, providing exactly the same level of protection from modification).
To date, the overwhelming proportion of applications of hash functions "take on" algorithms MD5, SHA-1, SHA-256, and in our country, and GOST R 34.11-94, which is almost a de facto monopoly in the certified FAPSI / FSB kriptoproduktah. Of course, there are many other lesser-known or common only in narrow communities of algorithms (eg, RIPEMD, TIGER, PANAMA, etc.)
What happened?
For a long time (since mid-1990's) the outgoing generation of cryptographic functions are considered very, very persistent. And although the base and MD5 and SHA-1 on the ideas embodied in the algorithm MD4, which was hacked in early 1990, improvements made in the design phase (namely, increasing the number of passes (rounds) to calculate the hash value and a more thorough study used mathematical operations) have led to the fact that until 2004 the family was considered invulnerable to any kind of attack.
Bombshell was heard August 16, 2004, when a group of Chinese researchers (led by X. Wang) published in open scientific publications server eprint.iacr.org without explanation a couple of real conflict to MD4, MD5, RIPEMD and HAVAL with the only remark that the selection of the input text over them 1 hour 5 minutes. It was a blast. Strong cryptography again turned their attention to the family of «MD5/SHA-1» and of course on the examples in the breakthrough paper. Certain laws have been clarified, and soon built a methodical apparatus for constructing collisions for such ciphers, which during 2004-2006 all improved and achieved to date performance of less than a second on a standard PC to generate a pair of texts creating a conflict. To date, no doubt hacked (but only for the attack class conflict »!) MD4, MD5, RIPEMD, HAVAL, SHA-0.
Since SHA-1 is somewhat different. Somewhat more thought out than MD5 and RIPEMD-160 structure of mathematical transformations restricts best known today in the open circles implementations attack (suggested by the way, the same Chinese) computational complexity 2 ^ 63 operations. This is objectively a lot. Even taking into account the exponential growth of productivity vych.tehniki unlikely selection of at least one conflict will be implemented by one computer in the next twenty years. However, do not forget that there are distributed projects. Healthy ambitions (to get the first artificial collision for SHA-1, by the way is officially a standard kriptoheshirovaniya U.S.) prompted researchers from University of Graz (Austria) run a distributed search on the server boinc.iaik.tugraz.at, optimistic Forecasts expect the first SHA-1 collision in the next 5 years.
Finally, the question that always touched when discussing this technique - vulnerable to this attack if the GOST R 34.11-94? Reply: not. Domestic kriptostandart uses a different scheme of "mixing" of blocks of source code for hashing, so far described techniques for use GOST failed. Best known attacks (which caused a somewhat speculative headlines in the media in 2008) proposed by researchers from the same Graz and improves the selection process of collisions in 2 ^ 23 times. It is based on another principle, and has a computational complexity of the 2 ^ 105 operations, that is incredibly far from reality even for distributed projects, and supercomputers.
Consequences
What do we have "The bottom line?
Crypto algorithms MD4, MD5, SHA-1, RIPEMD, HAVAL uniquely compromised by the attackers generation conflict. However (!) Fortunately, any physically realizable attack on the treatment of hash functions (even for MD4) to date has not been published.
What is the threat?
An attacker has the ability to create two different documents that will have the same hash value (in this case, it is unable to "control" what kind of value is obtained). This means that create a "double" alien to the existing document / text / file he can not. control of the situation it only when it can design and first and second instruments himself.
Can the attacker ...?
- ... Create another file / archive / etc. Who will have the same hash sum as a foreign original, then to replace the original, such as WEB-server or in a repository source / binary codes? None. However, if he is the author of the original file he can create two versions of a file with the same hash sum: innocuous and malicious, give a public study of the innocent, and then at the stage of the spread imperceptibly changed by a malicious version - to check based only on hash function will not notice.
- ... To recover the password client, finding out one way or another of its hash? Definitely not.
- ... Modify a previously created file (your own or someone else), a secure digital signature? None. However, as in the first case, it can initially create two versions of the source file, to sign one of them or give their e-signature on the signature of someone else's digital signature (for example, deposits of instruments or third-party certification of the time of document creation) and then after receiving the signed document transfer unit that is responsible for the signature, the second version of the document and EDS would be correct, which of course is unacceptable. To date, cryptanalysts already shown examples of conflicts of payment orders, differing only by the amount of the payment, as well as conflicts of X.509 certificates with different public keys, however, the same hash-sums, and therefore assure them the same signature certificates. All this makes it unfortunately quite a lot of room for imagination.
How to use today?
- From the well-known long enough hash algorithms to date, no claims to the GOST R 34.11-94 (developer FAPSI, 1995) and TIGER (the developers - cryptography world-famous E. Biham and R. Anderson, 1995).
- A new generation of algorithms, SHA from the American Institute of Standardization NIST (2001-2002 years) has a new numbering SHA-224, SHA-256, SHA-384, SHA-512 (on the bit output values ) and is sometimes combined under the code name SHA-2. Algorithms have a different structure kriptopreobrazovany and while information about attacks on them, neither the first nor the second kind have been reported.
- Not satisfied with the NIST launched in 2007 an open competition for the third generation standard hash SHA-3 (exactly repeats its principles then, as elected in 2000, a new block encryption standard AES) . At the current moment there is only the first phase of the contest, before participating in it admitted 51 algorithm from around the world.
- And finally, in principle, no one forbids you to use to check the two and more vulnerable functions both. Create a couple of documents that would give equal time to each other MD5-sum and identical to each other SHA-1 sum to date is impossible.
|