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.

As the title states, would the One Time Pad (OTP) be considered a cryptographic hash function?

share|improve this question
    
And the down vote why? –  Woot4Moo Jan 14 '13 at 18:52
3  
It's a reasonable question. The answer just happens to be 'no'. :-) –  John Deters Jan 14 '13 at 19:12
2  
Reasonable question yes but absence of research probably explains the downvotes –  rath Mar 15 at 9:45
add comment

4 Answers 4

No, OTP would not be considered a cryptographical hash function.

  • OTP takes a key; cryptographical hash functions don't

  • It's generally expected that the output of a hash function be of fixed length, independent of input length. The output of OTP is the same length as the input.

  • Hash functions are deterministic (that is, if you give the same input twice, you get the same output); if your hash-like OTP function uses a new portion of the keystream for every message, than the exact same input will yield different outputs if you call it repeatedly.

share|improve this answer
    
I thought the output of OTP is at a minimum the length of the input, is that not true? –  Woot4Moo Jan 11 '13 at 17:40
    
@Woot4Moo: if you do length padding with your OTP, that may be true. However, OTP will never shorten the message; cryptographical hashes are expected to (if given a large message) –  poncho Jan 11 '13 at 17:45
    
Sure I understand given a large enough message, however it is the case that the output of an OTP function is always different and at least the length of the message for a given input. This does not preclude it from being a cryptographic hash in my opinion. –  Woot4Moo Jan 11 '13 at 17:47
    
@Woot4Moo: OK, in your opinion, what is the definition of a cryptographic hash function, and does OTP meet that definition? Does SHA2 (for example) meet that same definition? –  poncho Jan 11 '13 at 19:18
1  
@RickyDemer: no, eTCR hashes are nondetermanistic; however, the random data that is used for the nondetermanism is included in the hash, or otherwise sent along with the hash (and is hence public); the term 'key' would not appear to apply to that. –  poncho Jan 13 '13 at 17:41
show 4 more comments

Unlike what poncho says, cryptographic hash functions can take keys. And, the cryptographic hash functions' output is not constant (it depends on the security parameter or the size of the key). In many practical examples like SHA-1 or SHA-256, keys are implicit with their sizes fixed and the output size is fixed.

In any case, OTP is an encryption system with perfect secrecy. And it's not possible to realize this in practice (because it requires keys to of same length as message that you are encrypting). However there are schemes that are essentially OTP but use pseudorandom number generators to generate the key that is used to encrypt the message. Those encryption schemes are semantically secure.

One can definitely build a collision-resistent hash function starting from any semantically secure encryption. Look at an introduction to cryptography book for such constructions.

share|improve this answer
4  
Actually, OTP was realized in practice ... there are some use cases where it is quite possible to transport a long key to the communication partner beforehand. Perhaps the most prominent one being the Moscow–Washington hotline. –  Paŭlo Ebermann Jan 12 '13 at 20:45
4  
There is such a thing as keyed hash functions; I consider them a different (albeit related) primitive. As for a cryptographical hash length not being constant, I consider hashes with different security parameters to be different hash functions (e.g. SHA384 and SHA512 are distinct hash functions). In any case, my comment specifically talked about the output length being independent of the input length, not anything else. –  poncho Jan 13 '13 at 21:54
add comment

No.

First, lets agree on what an OTP is. It's a character-by-character replacement function that relies on one key character per cleartext character. An OTP that reuses key material even one time can be broken (see Venona). While it may seem obvious from the name, it's an absolute requirement that the key material be used one and only one time.

Next, let's agree on the properties of a cryptographic hash. A message that is hashed must yield a digest value. It must be infeasible to recover the cleartext value of the message knowing only the digest, it must be infeasible to select a cleartext message that produces a specific digest, and it must be infeasible to produce two cleartext messages that yield the same digest. And, most importantly for this discussion, the algorithm must be deterministic, meaning hashing the same message must yield the same digest value each time it is run given the same message. If this were not true, message digests could not be used for comparing two messages, and hybrid cryptographic functions such as digital signatures would not work.

Therefore, a cryptographic hash function needs to be run more than once to meet its requirements. Yet we know there are security risks running an OTP more than once. Either you reuse the key material for each digest produced and risk compromising the key, or you use new key material for each message hashed and destroy the valuable property of determinism. Because neither of these choices is viable, an OTP is unsuitable for use as a cryptographic hash.

share|improve this answer
    
thoughtful response. But we also know that each digest is not unique in a cryptographic hash, it just has a low chance of collision. –  Woot4Moo Jan 14 '13 at 16:00
    
I removed "unique" from my statement as it's not at all relevant to your question. –  John Deters Jan 14 '13 at 19:29
add comment

OTP is reversible, and so it's useless as a cryptographic hash function. The answer really is that simple.

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.