Passwords, Hashes and Dictionary Attacks

Cryptology has been a favorite topic of research for me over the past 10 years. Ever since geometry class, I have been obsessed with mathematics, patterns, and number theory. I enjoy turning one value into a totally different value and back again. That may sound like nonsense, but that is exactly how cryptology (and thus password systems) work.

I am going to go into detail about one of the most popular password storage and verification processes in use on the internet, and in offline systems. This method is called a hash, specifically an MD5 hash. I will also outline 2 of the methods that hackers can use to compromise password.

A big part of password security is never actually storing a password. A password is not stored by itself, meaning in plain text. If your password is ‘evadman’, ‘evadman’ is not stored in a database. Some other representation of the password is stored, and verified against when you log into an application or site.

MD5 Hashes
For example, the defacto standard for passwords is called an MD5 hash. This is a 32 character representation of a string of numbers, letters or other characters. The length is always 32 hexadecimal (0-9 and A-F) characters no matter how long the input is, and the output hash is always the same for the same input. For example, the MD5 hash of an empty string (“”) is d41d8cd98f00b204e9800998ecf8427e. The MD5 hash of “The quick brown fox jumps over the lazy dog” is 9e107d9d372bb6826bd81d3542a419d6. If any character is changed, such as an uppercase letter, extra space, or even a non-printable character such as a tab, the MD5 hash will change. The only thing that won’t change is the length of the hash, which will always be 32 hexadecimal characters.

The input into an MD5 hashing program can be a password (a small string of characters) or something as big as an entire hard drive. That is why sometimes when you go to a download site, they will tell you the hash for the file so you can verify that the file was transferred correctly. If you create a hash on your computer of the file and get a different answer, then the file was corrupted when it was downloaded.

Since an MD5 hash is always the same length, it can be stored conveniently in a database. The database administrator or application owner doesn’t have to set a maximum password length, or store a field of random length, as the output is always exactly 32 characters. For all the program cares, the password can be a paragraph. The output will always be 32 characters long. That is a big ‘selling point’ of an MD5 hash.

These password hashes used to be considered moderately safe for public view because they could not be reversed. For example, walking backwards from 9e107d9d372bb6826bd81d3542a419d6 to “The quick brown fox jumps over the lazy dog” was considered pretty much impossible, because it would take every computer on the planet working for decades to go backwards and turn the hash into the original password. That was a false assumption; methods were found to do that conversion quickly if the password is short enough.

Rainbow Tables
This method is called a “pre-computed dictionary attack” and the data is stored in a device called a “rainbow table”. To GREATLY simplify, if you have a hash, you can look up the original password in the rainbow table. The limitations of this process are of the utmost importance to understand, as the limitations of a rainbow table will tell you what the minimum password length, and characters, should be to best mitigate the risk of your password being broken.

First, a rainbow table is absolutely ginormous. A rainbow table that would work on passwords that are up to 7 numbers or lowercase characters is about 130 GB. Up to 9 numbers and lowercase letters is about 500 GB. The size grows quickly as additional characters are added. Adding a non-numeric character like "#" will expand that to more than 10 TB. That is one of the reasons that it is recommended that you use a non-numeric character in your passwords. The method used for generating the chains that make up a rainbow table takes a boatload of horsepower. This can be decades of computer time, but once they are made, they never need to be made again. Distributed computing can be used to reduce this to a few hours, if not less, for smaller tables.

I will explain a real life example of this method. I was tasked with migrating users from one software platform to another many years ago. The original software used an MD5 hash for a password, and the new software used a different method. This meant that every user would have to reset their password, as the password hash that was stored could not be migrated directly to the new system. The application had more than a quarter million users, so this would stink for them. To mitigate this, I used a rainbow table to reverse the stored password and feed it into the new software. Thus, generate the hash in the new software so the user would not notice a difference. The amazing thing was that I used a very small rainbow table, and was able to reverse more than 98% of the quarter million hashes back into the original password in less than 10 minutes. That points to a gigantic hole in how most users choose passwords, and in the MD5 process as a whole.

On top of that, the passwords that could not be undone also had some interesting patterns. The hash of 32 characters itself means nothing, but when a bunch of the hashes are exactly the same, it means that folks are using the same password. This is surprising considering users are separated by thousands of miles, and have likely never met. I also noticed that the hash from my personal password, which couldn't be undone by the rainbow table, was in use by a few hundred different users. This confused me, because I thought my password would have been secure and random enough. I'm a DBA, so I always pick strong passwords that are very long compared to what I would term a ‘normal’ user.

It turns out that the cause was simpler than I expected. I was migrating an application that had a higher percentage of technical users than a general group. These users were also using strong passwords in greater numbers than a general population. However, a bunch of users were using a password that is fast to type on a keyboard, while also being long enough to deter a rainbow table attack. It appeared a bunch of us had the same cycling of passwords (use one, then change to another, then another, and so on) as I found that some of the other hashes were previous passwords I had used.

That leads to the 2nd type of vulnerability that exists in any password system, not just a MD5 or other hash process. This is called a dictionary attack (sometimes referred to as Brute Force). A dictionary attack means using words in a dictionary and trying them as passwords. Basically, each word is typed (thousands a second if the system allows it) until one works. This wouldn't be a problem for most strong passwords, as they are not actual words in the dictionary. But, sequences of numbers can still be tried, and exist in ‘hacker’ password dictionaries. For example, "q2w3e4r" is the upper left of the keyboard. "753159" is a sequence on the numeric keypad. Neither of these are actual words, but a quick look showed both exist in dictionary attack password lists that hackers can use. I did this same rough password frequency analysis on 3 other systems that have many thousands of users, and came up with roughly the same surprising answers. Different users were using the same passwords across systems that had absolutely nothing to do with each other. It's freaky, but it points to the biggest weak link in a password system: the user and their habits.

Here is something that should make some folks change their passwords. There is almost a 30% chance that your password (yes, the person reading this) is in this list of 30: 123, 1234, 12345, 123456, 666666, 7777777, 12345678, 123456789, password, blogger, qwerty, letmein, test, trustno1, dragon, abc123, 111111, hello, monkey, master, killer, 123123, ncc1701, thx1138, qazwsx, ou812, 8675309. Do you have that as a password to your banking site? What about your email? Welcome to an emerging field called social engineering. Social engineering tactics were used very recently by hackers to destroy the credibility of a firm called HBGary. In fact, HBGary’s CEO stepped down on Tuesday as a result of that attack.

Best Practices
If you use the same password across systems, if one is broken, every system that has that password can also be broken into as well. So here are the rules I suggest you follow for passwords:

• Use different passwords for each system. If you have trouble remembering passwords, at minimum use a different one for your email than everything else. If your email account is broken, that means a hacker can reset your password on almost any site that exists. The new password will be sent to your email, so the hacker will have it.
• Don't bother using an uppercase letter, as almost all rainbow tables include upper case in the table. Use a non-alphanumeric character instead. This means something like "&", "(" or "$". Bonus points for ALT-0160 or something like it.
• Use passwords that are 7 characters long or longer if at all possible. 10 is better, even if the last 3 are spaces or the same character repeated. If remembering long passwords are a problem, repeat the password 2 or 3 times to extend the length. That will defeat a rainbow table, and most dictionary attacks.

• Use a phrase made out of words that is long.  XKCD has a great example here.

• Don't use a password that can be found online.So don't use 'correct horse battery staple'.
• When installing any software application or hardware, always change the default password to something else. Change the password on your router or Access Point; same with database or other programs. It is amazing how many are still the default password, which can be pulled off a support website.

This was just the tip of the iceberg, but hopefully it will assist folks with choosing secure passwords.

Duplciate Images & MD5/SHA Hashes

I was in the middle of backing up some family photos when I discovered that I had multiple copies of the same image in different folders. Not only is this a waste of space, but it can also lead to images getting deleted on accident when you believe you have a copy in another folder, but actually do not.

That begs the question, how in the world do you sort though thousands of photos making sure that you keep one, and only one copy of each? If you haven't renamed the files, you may be able to use the file name to weed though the duplicates, but what if you renamed some of the files, or have duplicate names on files? Now it starts getting a lot more complicated.

There are some commercial products you can buy that will do some of this image verification, but I had much bigger plans. In addition to just removing duplicates, I wanted to be able to add tags to images, verify that images that were backed up did not become corrupted, and a host of other things that I will write about later. To start off with, I just wanted to remove duplicates. I decided to do that though creating a checksum for the file.

Think of a checksum as verification that the file is exactly as it is supposed to be. You will often find checksums on files that are being downloaded so that you can verify that the file received was not corrupted during the transfer, or by a cracker who decided to implant a virus in your download.

There are lots of different types of checksums, 3 of the most popular are CRC32, MD5, and the different SHA functions. The issue with CRC32 is that collisions are very frequent compared to md5 or the SHA hashes. In the way I am using hashes, a collision is when 2 different files create the same hash at the end. Since I will be removing any files with the same hash, a collision would result in the deletion of a file that isn't actually a duplicate.

That leaves out CRC32, but what about MD5 and the SHA functions? MD5 hashes have been used for years (and still used) to store data like passwords for web sites for a bunch of reasons. However, this is bad because MD5 hashes of passwords can be broken using several techniques like plain old brute forcing or though rainbow tables. But how will an MD5 or SHA1 hash do on finding duplicate files? Actually, very well in fact. The probability of a collision for a given MD5 or SHA1 hash is extremely low, however it is not impossible. Here is a great article on the subject. However, generating MD5 or SHA1 hashes of files is a pretty quick operation, so both are viable options.

When you get down to it though, I don't like living with an error rate that I can describe without using decimal notation. So since both MD5 and SHA1 checksums can be generated in a second or two, even on a slow machine, why not generate both for each file? The odds of both a MD5 and SHA1 hash returning identical values for different files is roughly the same as every atom in your body deciding to rearange itself on Mars. That is an error rate I can live with.

Generating all these hashes manually is a crazy proposition. Thankfully, Visual Studio has methods for creating hashes of the most popular types of data though the System.Security.Cryptography namespace. using this, I was able to create a quick function that would generate an MD% or any of the SHA hashes for a given file. That way, I could create a quick script to loop though all the image files and save their critical data to a database. (File location, name, and hashes) Then, it is a simple matter to write a query that returns only unique files, and save those off somewhere while removing the duplicates.

The below VB.NET function called GetHashForFile takes a file location and an enum that represents the hash type to generate. In order to generate both MD5 and SHA1 hashes, just call it twice with different enums. I added the different SHA2 hashes to the function in case someone wishes to generate SHA2 hashes.

The function needs 3 namespaces for references in order to function. These 3 must be added if you have not referenced them already. Add this to the top of your module or code page.

Imports System.IO
Imports System.Text
Imports System.Security.Cryptography

In order to make the function as reusable as possible, an enum was created so that you can't forget which hash types can be created. Add this enum to your code page or module.

 Enum HashType
     MD5 = 1
     SHA1 = 2
     SHA256 = 3
     SHA384 = 4
     SHA512 = 5
 End Enum

Then, add the function itself. the way this is currently written, if there is an error on generating the hash for a file (like trying to hash a file that doesn't exist), an empty string will be returned instead of an error being raised. If you want to raise an error that can be handled in the calling code, uncomment the lines that start with "Err.Raise".

 Public Function GetHashForFile(ByVal Filepath As String, ByVal DataHashStandard As HashType) As String
     'function that can create the most popular hashes.
     'check that file exists.
     If Not My.Computer.FileSystem.FileExists(Filepath) Then
         ' Err.Raise(vbObjectError + 13131, , "File " & Filepath & " does not exist") 'uncomment this line if you want to raise an error instead of return empty string
         Return ""
         Exit Function
     End If

     'declarations
     Dim sb As StringBuilder = New StringBuilder                     'stringbuilder to build the result.
     Dim fs As FileStream = New FileStream(Filepath, FileMode.Open)  'open file
     Dim HashProvider As Object

     Try
         'set the hash type
         If DataHashStandard = HashType.MD5 Then               'md5 hash
             HashProvider = New MD5CryptoServiceProvider
         ElseIf DataHashStandard = HashType.SHA1 Then          'sha128 (sha1) hash
             HashProvider = New SHA1CryptoServiceProvider
         ElseIf DataHashStandard = HashType.SHA256 Then        'sha256 (sha2 256 bit) hash
             HashProvider = New SHA256CryptoServiceProvider
         ElseIf DataHashStandard = HashType.SHA384 Then        'sha384 (sha2 384 bit) hash
             HashProvider = New SHA384CryptoServiceProvider
         ElseIf DataHashStandard = HashType.SHA512 Then        'sha512 (sha2 512 bit) hash
             HashProvider = New SHA512CryptoServiceProvider
         Else
             'close the file opened earlier
             fs.Close()
             fs.Dispose()
             ' Err.Raise(vbObjectError + 13132, , "Data HAsh Standard " & DataHashStandard.tostring & " is not valid") 'uncomment this line if you want to raise an error instead of return empty string
             Return ""
             Exit Function
         End If
         'compute the hash
         Dim hash() As Byte = HashProvider.ComputeHash(fs)

         'done with the file, close it.
         fs.Close()
         fs.Dispose()

         ' turn the byte array into a string
         For Each hex As Byte In hash
             sb.Append(hex.ToString("x2"))
         Next
         'return the result
         Return sb.ToString
     Catch ex As Exception
         'close the file opened earlier
         fs.Close()
         fs.Dispose()
         'Err.Raise(vbObjectError + 13133, , "Data Encryption failed with error " & ex.Message) 'uncomment this line if you want to raise an error instead of return empty string
         Return ""       ' return empty string on error instead of returning error.
         Exit Function
     End Try

 End Function

Once all 3 sections are in a code page or module, you can use the function like this. Replace 'c:\config.sys' with the file name you want to hash.

msgbox(GetHashForFile("c:\config.sys", HashType.MD5)) 'pop messagebox with md5 hash
msgbox(GetHashForFile("c:\config.sys", HashType.SHA1)) 'pop messagebox with SHA1 hash