Hash Lesson Notes
From BenningtonWiki
- hashing, hash value, hash function, hash table
- hashing: creating a nearly unique digital fingerprint (hash value) for given input data
- hash function
- deterministic -- generates the same hash value for the same input data; different hash value guarantees different input
- permutation is a one-to-one mapping of input data to hash
- different input nearly guarantees different hash value; equality of hash values nearly guarantees the same input data; a strong hash function will generate a completely different hash value for even the smallest change in the input data
- error detection
- identification
- grouping; subdividing large domains
- MD5
- message digest algorithm 5
- 128-bit hash value
- used for message integrity checks
- invented by Ronald Rivist of MIT in 1991
- RFC1321.
- small changes in the input result in large unpredictable changes in the hash value
- what you don't want are collisions
- md5, cksum on the command line
- SHA-1
- secure hash algorithm 1
- 160-bit hash value
- openssl sha1 <file>
- cryptography
- preimage attack: find a message that has a given hash value
- collision attack: find two messages that have the same hash value
Suppose Alice wants to trick Bob into signing a fraudulent contract. Alice prepares a fair contract m and a fraudulent one m'. She then finds a number of positions where m can be changed without changing the meaning, such as inserting commas, empty lines, one versus two spaces after a sentence, replacing synonyms, etc. By combining these changes, she can create a huge number of variations on m which are all fair contracts. In a similar manner, she also creates a huge number of variations on the fraudulent contract m'. She then applies the hash function to all these variations until she finds a version of the fair contract and a version of the fraudulent contract which have the same hash value, f(m) = f(m'). She presents the fair version to Bob for signing. After Bob has signed, Alice takes the signature and attaches it to the fraudulent contract. This signature then "proves" that Bob signed the fraudulent contract.
