5
$\begingroup$

Something about encryption and hashing has always bothered me.

Given a cryptographically secure hash function $H$, I can produce an arbitrarily long key from any seed $s$ by recursively applying $H$ to the seed $(s, H(s), H(H(s)), ...)$. Then I can XOR the resulting array with any plaintext $x$ to produce my ciphertext.

Similarly, given an encryption function $E$, I can produce a hash of any input $x$ by simply encrypting each block of $x$ with itself, and then XORing the results together.

So why, then, do we use different functions for hashing and crypto (say, SHA-256 vs. AES)? If one of them is secure, shouldn't it work for the other purpose too?

$\endgroup$
  • $\begingroup$ Note that SHA-256 internally uses a block cipher of 256 bit input/output, and 512 bit of key. It then sends the message to be hashed as key and uses "+" as feedback function from output to input.. $\endgroup$ – Ruggero May 6 '16 at 12:01
  • $\begingroup$ The particular construction of a stream cipher from a hash function that you propose is not actually secure. For example, if the adversary knew the first block of the plaintext, she could learn $s$ and then compute the rest of the key stream. (That said, there are ways to construct pseudorandom generators from collision-resistant hash functions, and there are even very efficient constructions if $H$ is modeled as a random oracle). I recommend the Katz and Lindell textbook as a place to start reading about the relationships between these notions. $\endgroup$ – Adam Smith May 7 '16 at 1:44
  • $\begingroup$ @Adam: yeah, I noticed it myself afterwards but just left it, since I'm pretty sure it's possible to make it work and I didn't put much thought into my particular scheme. Thanks though. $\endgroup$ – Mehrdad May 7 '16 at 2:07
  • $\begingroup$ Related (PRNG vs. cipher): Why are there so many stream ciphers out there and even ongoing research? $\endgroup$ – otus May 7 '16 at 5:54
9
$\begingroup$

You are correct: The 'workhorses' or primitives of cryptography, hash functions and block ciphers, can be used in such a way that they accomplish each others tasks: A hash function can be used to generate a key stream just as a stream cipher or block cipher in CTR mode (see e.g. Salsa20). And a block cipher can be transformed into a hash function (e.g. a Davies–Meyer compression function inside the Merkle–Damgård construction).

So why use different functions? Well, hash functions are not as versatile as block ciphers for the purpose of encryption - you can't do CBC mode with a hash function, for example. And block ciphers are generally not as well suited to the task of hashing as a purpose built compression function - they tend to have smaller blocks and relatively slow key schedules (or key schedules which are not secure when the attacker can control all the inputs). For efficiency's sake, it is easier to design a really strong and fast block cipher and a separate really strong and fast hash function than it is to design a single function which is really strong and fast in both capacities.

P.S. The hash function constructed from a block cipher you describe in your question is not cryptographically secure - you can find a collision merely by re-ordering the blocks of the message.

$\endgroup$
  • $\begingroup$ To be honest I don't understand why anyone uses CBC in the first place. If you think you need it, aren't you basically admitting that your crypto is insecure? I don't know whether this deserves to be a separate question, but it does play into my question... $\endgroup$ – Mehrdad May 6 '16 at 18:31
  • $\begingroup$ @Mehrdad - CBC is just as provably secure as CTR. Using CBC doesn't admit any insecurity as far as I know. But CBC was just an example - many modes are only possible with a block cipher and can't be performed with a hash function (e.g. OCB, to pick a more 'modern', fancy Authenticated Encryption mode). $\endgroup$ – J.D. May 6 '16 at 21:12
  • $\begingroup$ What I meant was, I don't see any benefit to chaining together encrypted blocks except for making it harder for an attacker to decrypt blocks in parallel -- which, to me, implies that you're admitting the crypto is insecure, otherwise this would be pointless. I'm not aware of all the variety of modes, though... I'll look into them, thanks. $\endgroup$ – Mehrdad May 6 '16 at 21:15
  • $\begingroup$ @Mehrdad, CBC does not make it harder to decrypt in parallel. It does have some advantages if you cannot expand the ciphertext with an IV and authentication tag (e.g. full disk encryption). $\endgroup$ – otus May 7 '16 at 6:02
4
$\begingroup$

J.D.'s answer explains why you might want a block cipher in addition to a hash function. TL;DR: versatility.

Stream ciphers, however, are not very versatile – at least synchronous stream ciphers are not. Yet they have not been replaced by hash functions. Why?

Partly because they have been replaced by block ciphers instead (AES CTR, specifically), but also because of their speed. Hashes have been designed to quickly process input and to produce a constant width output. They like long inputs, which let them amortize padding and other overhead. Encryption requires a long output as well and most hash functions are not very fast for that.


Similarly, given an encryption function $E$, I can produce a hash of any input $x$ by simply encrypting each block of $x$ with itself, and then XORing the results together.

This is not secure. A XOR allows you to change order, producing collisions and second preimages for anything longer than one block.

(It is also more like a MAC than a hash, since you need a key.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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