Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

As far as I understand, AES is believed to be extremely secure. (I have read somewhere that it would certainly not be broken in the next 20 years, but I am still not sure if the author was serious.)

DES is still not so bad for an old cypher, and 3DES is still used (maybe not so much, but at least I see 3DES in about:config in Firefox).

It looks like (good) block cyphers are trusted by the crypto community.

OTOH, many problems with cryptographic hash functions are discovered.

From the point of view of the non-crypto-specialist: hashing functions and symmetric cyphers are the really same thing: a "random" function (with different inputs and output).

So, why not use just AES for hashing? This seems the obvious things to do to get the strong safety of AES for hashing. As a bonus, could hardware implementations of AES help?

Is there a simple explanation of the real difference between hash functions and symmetric cyphers?

share|improve this question

5 Answers 5

up vote 42 down vote accepted

A block cipher has a key; the secrecy of the key is what the cipher security builds on. On the other hand, a hash function has no key at all, and there is no "secret data" on which security of the hash function is to be built.

A block cipher is reversible: if you know the key, you can decrypt what was encrypted. Technically, for a given key, a block cipher is a permutation of the space of possible block values. Hash functions are meant to be non-reversible, and they are not permutations in any way.

A block cipher operates on fixed-sized blocks (128-bit blocks for AES), both for input and output. A hash function has a fixed-sized output, but should accept arbitrarily large inputs.

So block ciphers and hash functions are really different animals; rather than trying to differentiate them, it is easier to see what they have in common: namely, that the people who know how to design a block cipher are also reasonably good at designing hash functions, because the analysis mathematical tools are similar (quite a lot of linear algebra and boolean functions, really).

Let's go for more formal definitions:

A block cipher is a family of permutations selected by a key. We consider the space B of n-bit blocks for some fixed value of n; the size of B is then 2n. Keys are values from a space K, usually another space of sequences of m bits (m is not necessarily equal to n). A key k selects a permutation among the 2n! possible permutations of B.

A block cipher is deemed secure as long as it is computationally indistinguishable from a permutation which has been chosen uniformly and randomly among the 2n! possible permutations. To model that, imagine a situation where an attacker is given access to two black box, one implementing the block cipher with a key that the attacker does not know, and the other being a truly random permutation. The goal of the attacker is to tell which is which. He can have each box encrypt or decrypt whatever data he wishes. On possible attack is to try all possible keys (there are 2m such keys) only one is found, which yields the same values than one of the boxes; this has average cost 2m-1 invocations of the cipher. A secure block cipher is one such that this generic attack is the best possible attack.

The AES is defined over 128-bit blocks (n = 128) and 128-, 192- and 256-bit keys.

A hash function is a single, fully defined, computable function which takes as input bit sequences of arbitrary length, and outputs values of a fixed length r (e.g. r = 256 bits for SHA-256). There is no key, no family of function, just a unique function which anybody can compute.

A hash function h is deemed secure if:

  • It is computationally infeasible to find preimages: given a r-bit value x, it is not feasible to find m such that h(m) = x.
  • It is computationally infeasible to find second preimages: given m, it is not feasible to find m' distinct from m, such that h(m) = h(m').
  • It is computationally infeasible to find collisions: it is not feasible to find m and m', distinct from each other, such that h(m) = h(m').

There are generic attacks which can find preimages, second preimages or collisions, with costs, respectively, 2r, 2r, and 2r/2. So actual security can be reached only if r is large enough so that 2r/2 is an overwhelmingly huge cost. In practice, this means that r = 128 (a 128-bit hash function such as MD5) is not enough.

In an informal way, it is good if the hash function "looks like" it has been chosen randomly and uniformly among the possible functions which accept the same inputs. But this is an ill-defined property since we are talking about a unique function (probabilities are always implicitly about averages and repeated experiences; you cannot really have probabilities with one single function). Also, being a random function is not exactly the same as being resistant to collisions and preimages; this is the debate over the Random Oracle Model.


Nevertheless, it is possible to build a hash function out of a block cipher. This is what the Merkle-Damgård construction does. This entails using the input message as the key of the block cipher; so the block cipher is not used at all as it was meant to be. With AES, this proves disappointing:

  • It results in a hash function with a 128-bit output, which is too small for security against technology available in 2011.
  • The security of the hash function then relies on the absence of related-key attacks on the block cipher. Related-key attacks do not really have any practical significance on a block cipher when used for encryption; hence, AES was not designed to resist such attacks, and, indeed, AES has a few weaknesses in that respect -- not a worry for encryption, but a big worry if AES is to be used in a Merkle-Damgård construction.
  • The performance will not be good.

The Whirlpool hash function is a design which builds on a block cipher inspired from the AES -- not the real one. That block cipher has a much improved (and heavier) key schedule, which resists related-key attacks and makes it usable as the core of a hash function. Also, that block cipher works on 512-bit blocks, not 128-bit blocks. Whirlpool is believed secure. Whirlpool is known to be very slow, so nobody uses it.

Some more recent hash function designs have attempted to reuse parts of the AES -- to be precise, to use an internal operation which maps well on the AES-NI instructions which recent Intel and AMD processors feature. See for instance ECHO and SHAvite-3; these two functions both received quite a bit of exposure as part of the SHA-3 competition and are believed "reasonably secure". There are very fast on recent Intel and AMD processors. On other weaker architectures, were hash function performance has some chance to actually matter, these functions are quite slow.

There are other constructions which can make a hash function out of a block cipher, e.g. the one used in Skein; but they also tend to require larger blocks than what the AES is defined over.

Summary: not only are block ciphers and hash functions quite different; but the idea of building a hash function out of the AES turns out to be of questionable validity. It is not easy, and the limited AES block size is the main hindrance.

share|improve this answer
    
Re: related keys. Does this mean that another AES key must always be a new random number? What about using K, K+1, K+2... –  curiousguy Oct 12 '11 at 5:52
2  
@curiousguy: I would advise against it, not only because of related keys, but also because it makes relatively little sense to use a new key if the new key can be deduced from the previous one. –  Thomas Pornin Oct 12 '11 at 11:31
    
Being chosen randomly and uniformly "is an ill-defined property since we are talking about a unique function" Would it make more sense if every hash function was keyed? –  curiousguy Oct 30 '11 at 16:50
    
@curiousguy: it makes sense for a large family of functions, where you can talk of "averages". For keyed functions (e.g. HMAC), you can view the key as "selecting" one function in such a family. At that point, you can work over the notion of distinguishing a function from that family, and another random function. SHA-256 is easy to distinguish from any other function since it returns the same values as SHA-256: there is only one SHA-256. –  Thomas Pornin Oct 30 '11 at 17:01

The basic answer is that they are different types of algorithms. AES is a symmetric key algorithm. You can't use it in the same role as RSA (a public key algorithm), or SHA-256 (a hashing algorithm). They are different systems designed with very different properties and weaknesses.

Yet, I paused and though seriously about this idea to explain it besides just saying, "It's this way." After all, a hash in the universal sense is a repeatable representation of data in a fixed or reduced size. AES can provide that via CBC mode. Yet, there are more properties to a secure hash than simple reduction.

A secure hashing algorithm is a one-way system. AES encrypts and decrypts the same way (symmetric cipher), and you can make a 1-1 mapping for each block what will happen with a given key. Unless the data is chained and thus lossy, you can simply decrypt the AES "hash" to the source data.

One can't reasonably reverse a SHA process other than to just try different input data. For the reasons that you can't use SHA-x to encrypt something, you can't use AES to hash something.

share|improve this answer
    
"you can't use SHA-x to encrypt something" Could you use: E[n] = SHA-x(k + n) ^ m[n] (m the message, E the encrypted message, k the key)? –  curiousguy Oct 30 '11 at 16:58
1  
@curiousguy A cryptographic hash function is a regular hash function with certain extra properties for a specific purpose. Perhaps understanding the generic meaning of a hash function will help you to understand why the answer is no: en.wikipedia.org/wiki/Hash_function –  Jeff Ferland Oct 30 '11 at 22:47
    
With a random oracle, wouldn't it work? –  curiousguy Oct 31 '11 at 17:15
1  
@-JeffFerland I don't really get your argument. What @curousguy suggested is a CTR mode like construction, that should be a secure streamcipher if the hash function is good. –  CodesInChaos Apr 2 '12 at 21:01

Is there a simple explanation of the real difference between hash functions and symmetric cyphers?

  • A cipher is reversible, a hash function is not
  • The length of the output of a cipher depends on the length of the input; a hash function produces the same length output regardless of the input
  • A single bit change anywhere in a cryptographic hash function produces a cascading (dramatic) change in the hash output. As a rule, this is not true for ciphers.
  • A cipher requires a key, a hash does not

The design and purpose of the two are fundamentally different and they are not interchangeable.

share|improve this answer
    
"A cipher is reversible" That a POV; from another POV: can you guess the key from cypher-text? "A cipher requires a key, a hash does not" That's a good one. It seems that "hash does not have a key" is what makes hashing more difficult than encryption. –  curiousguy Apr 3 '12 at 6:17
2  
@curiousguy: no POV about it; ciphers are two-way, hashes are one-way. Under no circumstances can a hash be reversed because it throws away information during the hashing process, whereas ciphers do not. Ciphers require a key to operate, but the data is retained. With a hash, the data is irreversibly destroyed. A hash function is something like "count the number of vowels." You simply can't take the number of vowels and derive what the original paragraph said. That information is lost. –  tylerl Apr 3 '12 at 8:51
    
"no POV about it" Your "POV" is that you want the clear-text from the cypher-text. My "POV" is that I want the key from clear-text and cypher-text. My intuition was that most used cyphers implement one-way function. (Thomas explained my intuition really well.) –  curiousguy Apr 3 '12 at 11:53
    
It is not unheard-of for ciphers and hashes to share some common algorithmic thread. A perfect example is Threefish (successor to twofish and blowfish) which was created as a component of the Skein hash function. But while a cipher must retain enough information to reproduce the original result as necessary, a hash does not. –  tylerl Sep 16 '12 at 7:34

You can basically turn any block cipher into a hash function using Merkle-Damgard-construction and you can basically turn any hash function into a block cipher using Feistel-networks if you define the Feistel function F in the following way.

F(half_block, round_key) = hash(concatenate(half_block, round_key))

But it's quite inefficient (takes long to compute), since F is already expensive to compute (it's an iterative algorithm using e. g. 80 internal "rounds" in case of SHA-512) and for the Feistel structure, F itself is iterated multiple times. Say you have a 20-stage Feistel network with an 80-round round function F, you perform 1600 SHA-2 "rounds" per block. It also leads to rather large block sizes (double the size of the hash function's output), e. g. 1024-bit block cipher if you were to use SHA-512 as the hash function.

But practically speaking, it's not neccessarily "insecure". It's just that readily available "block ciphers" (rather pseudorandom permutations - not permutation as in permutation of bits/bytes, but permutation in the sense of bijective mapping between "all possible input blocks" and "all possible output blocks") are far more efficient, more widely used and therefore more thoroughly analyzed for the properties of being good pseudorandom permutations. If you have computational power to waste, use SHA-512 in a Feistel network as a block cipher. Chances are at least it won't be less secure than AES (provided you add a good key schedule for deriving the "round keys"), however it will take lots of CPU cycles to process a block.

share|improve this answer

One example of using AES in a hashing application is CMAC-AES, a Cipher-Based MAC, a message authentication code or hash, that relies on the AES-128 cipher. It is standardized by NIST in Special Publication 800-38B. It is considered a mode of AES (or TDEA for which it is also approved). The decryption function is not used and cannot be used to restore the input message from the MAC value even if the key is subsequently discovered. Of course, compromising the AES key will compromise the authentication value of previously generated MACs, but it does not enable recovery of the clear text of any input messages.

Importantly,

CMAC, like any well-designed MAC algorithm, provides stronger assurance of data integrity than a checksum or an error detecting code. The verification of a checksum or an error detecting code is designed to detect only accidental modifications of the data, while CMAC is designed to detect intentional, unauthorized modifications of the data, as well as accidental modifications.

See http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf

CMAC meets the requirements of a secure hash function:

  • CMAC is not reversible
  • CMAC produces a fixed length output from an input of any length
  • CMAC produces a cascading change in its output for a single bit change in its input
  • The key may be public if the purpose is to hash the input or to verify the integrity but not the source of the input. Though if this is your purpose, there are hash algorithms better suited to those purposes.

CMAC may be appropriate for information systems in which an approved block cipher is more readily available than an approved hash function.

share|improve this answer
    
MAC algorithms and hash functions are not the same. That a MAC can be constructed on AES is quite true, but also orthogonal to the question. –  Xander Oct 7 at 3:32
    
The original question is why AES is not used to create secure hash. I have supplied a standard reference to how AES can be used for secure hashing and that it is approved for use in FIPS compliant systems. That is not orthogonal but rather answers the asker's question directly. –  M. Abel Oct 8 at 7:11
    
No, you gave a reference to a MAC function, not a hash function. If the difference is not clear, please read this answer: What's the difference between MAC vs hash? –  Xander Oct 8 at 13:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.