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

300px-Hash_table_4_1_1_0_0_1_0_LL.svg.png

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:
  1. Storing passwords: rather than storing a password in a password list, store h(password). Then if the password file is compromised, the passwords are not revealed.
  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".

MD51.png

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

md5-2.png

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.
Finding Unix passwords

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
  • d821c7ad76684789c56f478481208950
  • 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
  • 835bef07a75eb9b6ad98dcc2df9e505d119df46f
  • 40a3b1ef10a5494308eb5fb2bb50103824582d98

References

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.gz
cd evilize-0.1
make
gcc 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
  1. Consider what can be done about these weaknesses. Read: https://crackstation.net/hashing-security.htm
  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
Pngpng 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
Pngpng ARCHPRDonePic.png manage 50.2 K 2014-02-13 - 20:50 JimSkon ARCHPR Dictionary
Pngpng ARCHPRPic.png manage 40.1 K 2014-02-13 - 20:19 JimSkon ARCHPR
Pngpng MD51.png manage 27.9 K 2014-02-14 - 12:48 JimSkon MD5
Pngpng WinRARpic.png manage 45.7 K 2014-02-13 - 20:19 JimSkon WinRAR
Gzgz evilize-0.1.tar.gz manage 28.4 K 2014-02-13 - 20:43 JimSkon evilize
Pngpng md5-2.png manage 38.3 K 2014-02-14 - 12:48 JimSkon MD5
Rarrar secret_photos_Hard.rar manage 1030.9 K 2014-02-13 - 23:24 JimSkon Encrypted Photos Hard
Rarrar secret_photos_easy.rar manage 1030.9 K 2014-02-13 - 23:21 JimSkon Encrypted Photos Easy
Topic revision: r8 - 2014-02-15 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback