Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

(Already asked the same question on stackoverflow but I was told to better ask here. http://stackoverflow.com/questions/17527192/one-time-pad-with-dh-and-cryptographic-hash-function)

I know: Never do your own crypto.

But this question is just theoretical.

Assume you do a Diffie-Hellman Key Exchange with a server to produce a shared secret $x$. Then use a cryptographic hash function like SHA3 to generate a pseudorandom bitstream like this:

$$p_i = \operatorname{SHA3}(x||p_{i-1}).$$

To encrypt $i$th packet of data, labelled $m_i$, compute

$$c_i = m_i \oplus p_i.$$

I realize that the key stream for a OTP must be completely random to ensure perfect secrecy, but would this scheme at least be as hard to break as the underlying hash function or Diffie-Hellman?

In my opinion, it should be, but I'm new to cryptography.

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice. By including $x$ in every $p_i$ an attacker has to break (not only find a collision) the first sent packet in order to decrypt the rest of the session, breaking any other packet will most likely be a collision and not give away the needed $x$, only the content of this packet. Also, breaking any packet requires at least plaintext knowledge but it gives you only this particular hash, not the previous/next hashes.

share|improve this question
    
If the key stream is not completely random, it is not called OTP, but a stream cipher. –  Henrick Hellström Jul 8 '13 at 16:18
3  
Take a look at this and this –  rath Jul 8 '13 at 22:11
add comment

2 Answers

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice.

This construction, like all stream ciphers, will cycle and produce the same key stream.

All that has to happen is $p_i$ has to equal any of the previously observed output blocks and we'll have a cycle.

If the hash is $n$-bits wide then we can expect this to occur after approximately $2^{n/2}$ blocks by the birthday paradox. The precise size of the cycle will vary from key to key.

This is kind of a problem. Some keys could have much smaller cycles than others. At its extreme, SHA-3 could have a fixed point where by SHA-3(x) = x. The cycle length would thus be one if we were unlucky enough to hit upon this value. Note that fixed points like this can absolutely occur under the random oracle model, although it is rather unlikely.

You can fix this by introducing a counter in to your state update function. Each input to the hash would be unique.

Under the random oracle model, the oracle would choose an $n$-bit hash output uniformly at random for each iteration of the state update function. This is because it never sees the same input message twice; the oracle never gets the chance to return a previously seen state.

In theory, you'd now be back to perfect secrecy. The oracle is now flipping fair coins for each bit of the message, which is analogous to the set-up we see the in the OTP.

This is just an academic point though. Obviously, in reality no hash is a random oracle. The security just reduces to the security of the underlying hash.

share|improve this answer
add comment

You've just invented your own stream cipher. Rather than trying to make sure it is secure, it is better to use a stream cipher that is already known, such as AES-CTR or AES-GCM (which adds an authentication tag). Also note that stream ciphers based on secure hash functions are relatively slow compared to most stream ciphers.

share|improve this answer
add comment

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.