Assignment Series #A3 Hash functions

1. introduction

This challenge will discuss important aspects of hash functions and related attacks. We use hash functions as a base to proof integrity of communications or files but hashes are also often used to avoid storage of passwords in web application databases or the Active Directory. It is important to understand how hashes work in order to provide solid guidance for implementation or judge whether a hash is applied the right way.

1. Hash functions create fixed length representations from arbitrary length inputs. When we usually call
   something a hash we are loosely referring to what academia is calling the "image". Study a basic hash
   function chart, its labels, all inputs, outputs and processes.
2. What are hash functions good for. List five use cases or typical applications.
3. With hash functions come three important properties: collision resistance, pre-image resistance and
   second pre-image resistance. Describe the three and give hints on which is the easiest to exploit.
4. Assuming we have a perfect hash function that produces 128-bit output (Same size as with MD5). How
   resistant is the said function against collisions. Can you calculate the computational effort and would
   this be sufficient protection nowadays? See Crypto Intro and How to Break It.pdf, Slide 49
5. If we need a secure hash function to assure proper integrity protection for the next decade. What would
   be minimal size for a good function? Check https://www.keylength.com/ and argue your assumptions
   and recommendation.

2. Answers

1. «A hashfunction maps a large dataset to smallerdataset.»

2. Use cases for hashes:

• Compare two files for equality
• Verify the integrity of a file after it has been transferred from one place to another
• In some situations, an encrypted file may be designed to never change the file size nor the last modification date and time
• Passwords (One-way function)
• Cryptography (Digital Signatures)

3. Collision resistance is the property of a hash function that it is computationally infeasible to find two colliding inputs

   Preimage resistance is the property of a hash function that it is hard to invert, that is, given an element in the range of a hash function, it should be computationally infeasible to find an input that maps to that element.

   Second preimage resistance is the property of a hash function that it is computationally infeasible to find any second input that has the same output as a given input. This property is related to preimage resistance and one-wayness

   Exploiting weak collision resistance: If we are able to create two inputs that generate the same hash, digital signature become suspect

   Exploiting weak preimage resistance: If we are able to "work backwards" from a hash and create some text that produces the same hash, we can use this to beat hashed passwords. We won’t ever know the actual input data that was used, but that doesn’t matter.

   Exploiting second weak preimage resistance: As with preimage resistance, we want to fool somebody into authenticating our data as genuine, and we’d most likely use this when trying to introduce a corrupted software distribution.

4. Some very bright researchers in China presented a paper, Collisions for Hash Functions MD4,
   MD5, HAVAL-128 and RIPEMD, at the Crypto 2004 conference in August 2004, and it’s shaken
   up the security world considerably. This was some outstanding cryptography research.

   They have found ways to reliably generate collisions in four hash functions much faster than brute-force time, and in one case (MD4, which is admittedly obsolete), with a hand calculation. This has been a stunning development.

   These are all of the "we control both inputs" type – the first of our three kinds of collisions – and it holds the most promise in the compromise of digital signatures where the bad guy can create two contradictory documents and pull a switcheroo later.

   We’ve heard there are already tools emerging that can reliably generate collision-pairs in "reasonable" amounts of CPU time, and with just a bit of searching found one example for MD5:

   

5. Should be at least 256 bits, better 512

PDF Report:
hash_functions#1