# Lab 2

### Hash Dictionary Attacks and hash collisions.

This lab explores Dictionary Attacks against hash and hash collisions.

###### What is a Hash Function?

A hash function is any algorithm that maps data of arbitrary length to data of a fixed length. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes. Recent development of internet payment networks also uses a form of 'hashing' for checksums, and has brought additional attention to the term. (Wikipedia)

###### h(x) = y

A hash function h takes a value x and produces a value y that has the characteristics:

1. it is not possible to reconstruct the input datum x from its hash value h(x) alone. Thus Hash functions are typically not invertible .
2. It is deterministic: when it is invoked twice on identical data (e.g. two strings containing exactly the same characters), the function should produce the same value.
Because the size (number of bits) in x may be greater then the size of h( x), sometimes there two different x's have the same result, called a collision.
###### h(x1) = h(x2) = y where x1 ≠ x2

Above is a hash function that maps names to integers from 0 to 15. There is a collision between keys "John Smith" and "Sandra Dee".

###### Cryptographic uses of hashing:
2. Creating a signature or checksum of some data or message, e.g. h(message) = signature. This signature can later be used to determine of data has been altered, as it's signature will not longer match. This is because in general h(message1) ≠ h(message1).
###### Exploits against hashing

1. Brute force attack: For h(x) = y, numerate all possible values of x, and compute h(x) to see if it equales y.
2. Dictionary attacks: Create a table of more common values of x, along with precomputed values for h(x). Then h(x) can be used as a key to lookup x.
3. Collision Attack: Find two different messages m1 and m2 such that hash(m1) = hash(m2). Then we can provide m2 to a user instead of m1, giving them a different message then was needed or wanted.

### Section 1: Cracking passwords and hashes

In this part of the lab, we crack passwords, i.e. we apply dictionary attacks on the hashes. In most cases this assumes we are familiar with the cryptosystem or hash function used to create the ciphertext or hash, respectively. There will be one case where the hash function will be unknown. Possible targets: crypt (Unix psswords), modified crypt (Blowfish), MD5, NTLM hashes, SHA1 hashes.

A varity of resources are available on the Internet to "invert" hashes, mostly using a dictionary of previously seen values to lookup a likely hash preimage.

For example, use http://www.md5hashgenerator.com/index.php to create a MD5 hash of "mypassword".

Then use http://reverse-hash-lookup.online-domain-tools.com/ to lookup the original value.

### Section 1 Action steps

###### Step 1.1

Use the tools above, or others as discovered, to do the following:

1. For MD5 find 5 passwords in the table
2. For MD5 find 5 passwords not in the table
3. For SH1 find 5 passwords in the table
4. For SH1 find 5 passwords not in the table
5. For unix crypt find 5 passwords in the table
6. For unix crypt find 5 passwords not in the table

### Instructions

• You should use the tools provided in the lab, but are not limited to them. If for some reason you choose not to, please justify your choice. If you wrote scripts or additional code, please include it.
• Your output should demonstrate that you have done the experiments, such as screenshots, Unix typescripts, or logs.
• Your output should be the passwords found, corresponding to their respective hash values or password entries. You should specify in each case how you cracked the password, e.g. by using a Swedish dictionary, applying the rule to substitute 3 for es, etc. As a last resort, a brute-force method may be used (some password crackers use that as a last mode/pass), but then you should specify that this was done.

1.2 Using the tools of your choice, find the password that generated each of the following Unix crypt hash entries in /etc/passwd::

• root:4Zjs8LUSjnFLc
• laurajay:YcaQoQJyOVXLA
• Olivia:Frca7e/5TTLH2
• john:NrrN.A7iPEVys
• neo:Qxw8mUWuWCUic
1.3. Finding a preimage to an MD5 hash Using the tools of your choice, find the probable origin text for the following MD5 hashes:
• 827ccb0eea8a706c4c34a16891f84e7b
• a2bb8f3be1a2f664b601127a6d20226e
• 141cd94a3c322acb8155b0f3e80f87f6
• c6c8eff088b420521abe3f4f6b4b81ae
• b8764b9ac5b83fdbf63040efd1833d3e (hard, 13 characters, alpha)
1.4 Finding a preimage to a SHA-1 hash Using the tools of your choice, find the probable origin text for the following SHA-1 hashes:
• 650c54b0db3e8ba97c436d0a243ed9888ffc84cb
• cb387e58a794ab1ae5385a2ab12a8df56b89330d
• d2d066371475dee7a2d496ca34a3ab08485cfaf6
• 40a3b1ef10a5494308eb5fb2bb50103824582d98

### Section 2: Hash collisions

There are lots of examples of hash collisions on the internet. You can find some good example in here and here.
We provide some tools that can find two different files with same hash. You can use them to create your own files have hash-collisions.

First, we provide three tools to generate/verify MD5.

• MD5 Hash Generator - an online MD5 generater that can generate MD5 hash code for string.
• MD5 Check Utility 2.31(Windows) - a tools can generate or verify MD5 hash code for specific file. You can find this tools in the folder named "tools".
• MD5(Mac OS X) - create and compare MD5 checksums on Mac OX 10.
If you use OSX or Linux, there is an easier to compute the MD5 hash code. Use the command `md5` of OpenSSL , you can get a MD5 for specific file. For example:
`openssl md5 test.txt`

Now, you can create your own hash-collided files using the tools we provided here.

evilize-0.1.tar.gz: evilize

First you will need to disable compiler optimization for the build to world. in he "Makefile" make the following change:

`CFLAGS=-O3 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"\${MD5COLL_VERSION}\" -DVERSION=\"\${VERSION}\"`
to:
`CFLAGS=-O0 -Wall -DSTDC_HEADERS -g -DMD5COLL_VERSION=\"\${MD5COLL_VERSION}\" -DVERSION=\"\${VERSION}\"`

Evilize 0.1(evilize-0.1.tar.gz) can create pairs of executable files with the same MD5 hash. To use this tool, you have to compile it first:
`tar zxf evilize-0.1.tar.gzcd evilize-0.1makegcc hello-erase.c goodevil.o -o hello-erase`
You can write your own c program to generate good and bad behaviors in this step. Then, get your initial vector by executing this command:
`./evilize hello-erase -i`
Now, you can create your MD5 collision by this command:
`./md5coll 0x23d3e487 0x3e3ea619 0xc7bdd6fa 0x2d0271e7 > init.txt`
Note here you must replace the vector on the command line with your own. By now, you can create a pair of good and evil programs by running:
`./evilize hello-erase -c init.txt -g good -e evil`
You get a good executable file and a bad executable file with same MD5 hash code. Now you can run the two program to act different behaviors and compare the MD5 hash code by the MD5 Check Utility 2.31. Detailed instruction for this tool can be find in README file.

###### Section 2 Actions Steps:
1. Complete the included steps using evilize above, including a screen capture of your working programs. Modify the program in some unique manner amusing to you.
2. Question: Describe, in detail, a scenario where such a tool could be used to compromise or attack a system or network.
3. Find, and list, at least 3 other tools that exploit hash collisions. Two examples are selfextract.zip and web_version1.zip. Notes on using
4. For each of the exploits in the previous item, describe a how they can be used to compromise or attack a system or network.
5. Turn in everything (including screenshots) in a single .DOC file on Moodle.

###### Final questions
2. Explain how "salting" works to make use of hashing more secure.
3. Are there any weaknesses with salting? Explain.

### Tools:

Topic attachments
I Attachment Action Size Date Who Comment
png 300px-Hash_table_4_1_1_0_0_1_0_LL.svg.png manage 8.4 K 2014-02-14 - 11:50 JimSkon Hash Functions
png ARCHPRDonePic.png manage 50.2 K 2014-02-13 - 20:50 JimSkon ARCHPR Dictionary
png ARCHPRPic.png manage 40.1 K 2014-02-13 - 20:19 JimSkon ARCHPR
png MD51.png manage 27.9 K 2014-02-14 - 12:48 JimSkon MD5
png WinRARpic.png manage 45.7 K 2014-02-13 - 20:19 JimSkon WinRAR
gz evilize-0.1.tar.gz manage 28.4 K 2014-02-13 - 20:43 JimSkon evilize
png md5-2.png manage 38.3 K 2014-02-14 - 12:48 JimSkon MD5
rar secret_photos_Hard.rar manage 1030.9 K 2014-02-13 - 23:24 JimSkon Encrypted Photos Hard
rar secret_photos_easy.rar manage 1030.9 K 2014-02-13 - 23:21 JimSkon Encrypted Photos Easy
Topic revision: r8 - 2014-02-15 - JimSkon

TWiki

* Webs

Copyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback