A hash function is a one-way function that allows someone to calculate a fixed-size value (the Hash) based on a message.
- This hash will allow us to make sure that the message was not modified during the transit.
- The receiver can take the message, calculate the hash value and compare with the hash value that was transmitted with the message. If they match: the message was not modified/tampered with.
- This provides Integrity services: the message received was the message send.
- It does not provide authentication: anybody can compute a hash and attach it to the message.
- So, if in addition of integrity services, we want to also provide authentication services, what can we do?
- Goal: we want the sender to create an hash based on the message and some other information that will prove that the legitimate sender is actually the one that create the hash and that the message or hash was not modified in transit.
- These services will be provided by a Message Authentication Code (MAC) AKA Hash Message Authentication Code (HMAC).
- Three popular solutions
- Conventional Encryption. If 2 parties share an encryption key: the sender can encrypt the hash and send it. The receiver then decrypts it and recalculate the message hash. If it matches: it proves that the party that possessed the encryption key created the message and the hash.
- Asymmetric Encryption. Same idea but the sender uses his private key to encrypt the hash. The receiving party uses the sender’s public key to decrypt the hash and verify it.
- Shared Secret Value. Add a “shared secret” to the message, calculate the hash on (message || shared secret) then send message and hash. The receiver can only check the hash if he has the shared secret. Advantage: faster than encryption.
It condenses arbitrary message to fixed size. It is usually assume that the hash function is public and not keyed cf. MAC which is keyed. The hash function is used to detect changes to message. It can also use in various ways with message most often to create a digital signature.
Hash Functions & Digital Signatures:
Hash Function Properties:
The Hash Function produces a fingerprint of some file/message/data
h = H(M)
It condenses a variable-length message M to a fixed-sized fingerprint. It is assumed to be public
Requirements for Hash Functions:
- can be applied to any sized message M
- produces fixed-length output h
- is easy to compute h=H(M) for any message M
- given h is infeasible to find x s.t. H(x)=h
- one-way property
- given x is infeasible to find y s.t. H(y)=H(x)
- weak collision resistance
- is infeasible to find any x,y s.t. H(y)=H(x)
- strong collision resistance