Which of the following cryptographic attacks tries to find two input strings of a hash function that produce the same hash result?

Hashing Algorithms

Hashing algorithms are just as abundant as encryption algorithms, but there are a few that are used more often than others. Some common hashing algorithms include MD5, SHA-1, SHA-2, NTLM, and LANMAN.

MD5: This is the fifth version of the Message Digest algorithm. MD5 creates 128-bit outputs. MD5 was a very commonly used hashing algorithm. That was until weaknesses in the algorithm started to surface. Most of these weaknesses manifested themselves as collisions. Because of this, MD5 began to be phased out.

SHA-1: This is the second version of the Secure Hash Algorithm standard, SHA-0 being the first. SHA-1 creates 160-bit outputs. SHA-1 is one of the main algorithms that began to replace MD5, after vulnerabilities were found. SHA-1 gained widespread use and acceptance. SHA-1 was actually designated as a FIPS 140 compliant hashing algorithm.

SHA-2: This is actually a suite of hashing algorithms. The suite contains SHA-224, SHA-256, SHA-384, and SHA-512. Each algorithm is represented by the length of its output. SHA-2 algorithms are more secure than SHA-1 algorithms, but SHA-2 has not gained widespread use.

LANMAN: Microsoft LANMAN is the Microsoft LAN Manager hashing algorithm. LANMAN was used by legacy Windows systems to store passwords. LANMAN used DES algorithms to create the hash. The problem is that LANMAN's implementation of the DES algorithm isn't very secure, and therefore, LANMAN is susceptible to brute force attacks. LANMAN password hashes can actually be cracked in just a few hours. Microsoft no longer uses LANMAN as the default storage mechanism. It is available, but is no longer turned on by default.

NTLM: This is the NT LAN Manager algorithm. The NTLM algorithm is used for password hashing during authentication. It is the successor of the LANMAN algorithm. NTLM was followed with NTLMv2. NTLMv2 uses an HMAC-MD5 algorithm for hashing.

Working with Hashing Algorithms

Even though encryption is important for protecting data, sometimes it is important to be able to prove that no one has modified the data. This you can do with hashing algorithms. A hash is a one-way function that transforms data in such a way that, given a hash result (sometimes called a digest), it is computationally infeasible to produce the original message. Besides being one-way, hash functions have some other basic properties:

They take an input of any length and produce an output of a fixed length.

They should be efficient and fast to compute.

They should be computationally infeasible to invert.

They should be strongly collision free.

A hash function takes input of any length and produces a fixed-length string. That means that you can use hashes on something as small as a password or as large as an entire document. The hashing algorithms the .NET Framework provides are very efficient and fast, making them useful for many applications. The most important property of hash functions is the size of the hash. A larger hash makes it more difficult to invert the function, and it ensures that the function is collision free.

Because hash functions have a fixed output but unlimited inputs, multiple values can produce the same hash. However, because there are so many possible hash values, it is extremely difficult to find two inputs that do produce hashes that match. For that reason, hashes are like a fingerprint for the original data. If the data changes, the fingerprint will no longer match, and it is unlikely that any other useful data will produce the same fingerprint. Therefore, you can store these small fingerprints, or hashes, to later verify your data's integrity.

Another common use for a hash is for someone to demonstrate knowledge of a piece of information without actually disclosing that information. For example, to prove you know a password, you could send the actual password, or you could produce and send the hash of that password.This is useful for Web site authentication, because the server does not have to store the actual password—it needs only the hash.

The .NET Framework supports the hashing algorithms shown in Table 4.3.

Table 4.3. Hashing Algorithms Available in the .NET Framework

The MD5 algorithm, defined in RFC 1321, is probably the most well-known and widely used hash function. It is the fastest of all the .NET hashing algorithms, but it uses a smaller 128-bit hash value, making it the most vulnerable to attack over the long term. MD5 has been shown to have some partial collisions and is not likely to be able to withstand future attacks as hardware capabilities increase. Nevertheless, for now it the most commonly used hashing algorithm.

SHA is an algorithm designed by the National Security Agency (NSA) and published by NIST as FIPS PUB 180. Designed for use with the Digital Signature Standard (DSS), SHA produces a 160-bit hash value.

The original SHA specification published in 1993 was shortly withdrawn by the NSA and superceded by the revised FIPS PUB 180-1, commonly referred to as SHA-1.The NSA's reason for withdrawing the original specification was to correct a flaw in the original algorithm that reduced its cryptographic security. However, the NSA never gave details of this flaw, prompting researchers to closely examine both algorithms. Because of this close scrutiny, SHA-1 is widely considered to be quite secure.

The NIST has since published three variants of SHA-1 that produce larger hashes: SHA-256, SHA-384, and SHA-512. Although with the larger hash sizes these algorithms should be more secure, they have not undergone as much analysis as SHA-1. Nevertheless, the hash length is important to protect from brute-force and birthday attacks.

Hacking the Code …

Verifying Integrity

You can use hashes to verify integrity, but many developers use them incorrectly, undoing their effectiveness. For example, many Web sites allow you to download a file as well as the MD5 checksum for that file. They do this so that you can verify the integrity of the file, but you are downloading the checksum from the same location and over the same connection as the file itself. If you don't trust the file enough to actually need to verify the hash, how can you trust the hash that came from the same location? If someone is able to modify the file, they could just as easily compute and save a new hash.

TIP

To verify the integrity of file downloads, many Web sites provide an MD5 sum as well as a PGP signature of the sum. The MD5 sum verifies integrity, and the PGP signature proves that the MD5 sum is authentic.

Hashes are useful if you keep them private to verify data such as a cookie. For example, suppose you write a cookie to the client's browser and store the hash of that cookie in your database. When the client returns that cookie at a later time, you can compute the hash and compare that to the one stored in the database to verify that it has not changed. Since ASP.NET stores session and authentication tokens entirely in the cookie and not on the server, it computes a hash of the cookie data and encrypts both the data and the hash. This encrypted result is encoded and saved in a cookie on the client side. When the client returns the cookie data, the server decrypts the string and verifies the hash. In this way, ASP.NET protects the hash and protects the privacy of the data.

Another way to make hashes more secure is to use a keyed hash algorithm. Keyed hashes are similar to regular hashes except that the hash is based on a secret key. To verify the hash or to create a fake hash, you need to know that key. The .NET Framework provides two keyed hashing algorithms:

▪

HMACSHA1 This function produces a hash-based message authentication code based on the SHA-1 hashing algorithm. HMACSHA1 combines the original message and the secret key and uses SHA-1 to create a hash. It then combines that hash again with the secret key and creates a second SHA-1 hash. Like SHA-1, the HMACSHA1 algorithm produces a 160-bit hash.

▪

MACTripleDES This algorithm uses TripleDES to encrypt the message, discarding all but the final 64 bits of the ciphertext.

With keyed hashing algorithms, you can send the hash with the data, but you must keep the key secret. Note that this method does have limitations similar to the key exchange issues of symmetric cryptography. Figures 4.17 and 4.18 demonstrate using the HMACSHA1 function.

Figure 4.17. Keyed Hashing Using HMACSHA1: C#

Figure 4.18. Keyed Hashing Using HMACSHA1: VB.NET

Hashing Passwords

Another important use for hashes is storing passwords. As described in Chapter 1, you should not store actual passwords in your database. Using hashing algorithms, you can store the hash and use that to authenticate the user. Because it is highly unlikely that two passwords would produce the same hash, you can compare the stored hash with a hash of the password submitted by the user. If the two match, you can be sure that the user has the correct password.

Protecting passwords with hashes has some unique problems. First, although hashes are not reversible, they are crackable using a brute-force method. You cannot produce the password from the hash, but you can create hashes of millions of passwords until you find one that matches. For this reason, the hash's strength isn't based so much on the key length of the hashing algorithm, but on the length of the password itself. And because passwords have such low entropy, are predictable, and are often too short, this usually is not a difficult task.

Another problem with hashes is that the same data will always produce the same hash. This can be a problem if someone ever obtains the hashes, because they can use a precomputed dictionary of hashes to instantly discover common passwords. To prevent this situation, we can add a salt to the password to ensure a different hash each time. The salt should be a large random number uniquely generated for that purpose. You do not need to keep the salt private, so you can save the salt with the hash itself.

When you use a salt, there are as many possible hashes for any given piece of data as there are bits in the salt. Of course, if the intruder has access to the hashes, they also have access to the salts, but the key here is to force the attacker to compute each hash individually and not gain any benefit from passwords he or she has already cracked. Figures 4.19 and 4.20 show hashing algorithms that include salts.

Figure 4.19. Hashing with a Salt: C#

Figure 4.20. Hashing with a Salt: VB.NET

You might think that a salt is similar to an IV. In fact, it is essentially the same technique that accomplishes the same purpose. Note that it is also similar in function to a keyed hash algorithm, and a keyed function such as HMACSHA1 is an excellent replacement for the code in Figure 4.20. To use a keyed hash, simply use the salt in place of the key, and otherwise follow the sample code in Figure 4.19.

III.B. MD5

The MD5 hashing algorithm (RFC 1321) was designed in 1992 by Ron Rivest as an improved version of MD4. It is an unkeyed hash with an output of 128 bits. The message to be hashed is processed by MD5 in 512-bit blocks. The message is first padded so that its length is a multiple of 512 bits. Four 32-bit chaining variables are initialized to (hex): cv1=0x01234567, cv2=0x89abcdef, cv3=0xfedcba98, and cv4=0x76543210. For each message block, four rounds of the main loop are performed for a total of 64 operations (16 operations per round). The message block of 512 bits is further divided into 16 sub-blocks of 32 bits each. The chaining variables (cv1, cv2, cv3, cv4) are copied into round variables (rv1, rv2, rv3, rv4), respectively. For every operation, there is a nonlinear function on three of the four round variables. The result (R1) is added to a constant, the remaining round variable, and a 32-bit sub-block of the message to give R2. This new result (R2) is rotated to the right a variable number of bits and added to one of the round variables. R2 also replaces one of the round variables. The round variables (rv1, rv2, rv3, rv4) are then added to the chaining variables (cv1, cv2, cv3, cv4), respectively. The main loop is repeated until all message blocks have been processed after which the chaining variables are concatenated to give the 128-bit MD5 hash.

The hash of the ASCII text “MD5” using the MD5 algorithm is: 0x7f138a09169b250e9dcb378140907378 Changing the last bit in “MD5” from a 1 to a 0 results in the ASCII text “MD4.” Even a 1-bit change creates a totally different hash. Using MD5 on the text “MD4” results in the hash: 0x59b6d1f8ea235402832256aa62415fe0

Although no collisions have been found in MD5 itself, collisions have been found by den Boer and Bosselaers in the MD5 compression function. Therefore, it is generally recommended that a different hashing algorithm, such as SHA-1, be used.

1 SHA-256 or SHA-2

SHA stands for secure hashing algorithm. SHA-1 and SHA-256 are two different versions of that algorithm. They differ in both constructions and in bit-length of the signature. SHA-1 is a 160-bit hash and SHA-256 generates an almost-unique 256-bit (32-byte) signature for a text. SHA-256 is one of the successor and strongest hash functions to SHA-1. It is not much more complex to code than SHA-1 and has not yet been compromised in any way [1]. The pictorial representation of SHA-256 is as shown in Fig. 2.

Oracle’s Password Hashing Algorithm

Oracle had a lot of options when they decided on a password hashing algorithm. Their designers made the decision that a simple hash of a user’s password was too weak and would be susceptible to dictionary attacks where the attacker calculates a hash for each word in a dictionary and then compares that hash with the value stored in the SYS.USE1K$ table. In order to add a layer of complexity, Oracle chose a keyed hash, where a secret value called a key is used as part of the hash calculation. Keeping the key secret was critical to the security of the hash algorithm, but keeping secrets is a difficult proposition in any software package. Oracle ended up designing their own hash algorithm based on the Data Encryption Standard (DES). It’s likely that they considered a home-grown hashing algorithm to be more secure than an industry standard one, because the algorithm was to be kept secret. Security through obscurity is never a good thing, and it did not take long for both the hashing algorithm and the secret key to be discovered and disclosed to the public.

Oracle’s password hashing algorithm is fairly simple. Start by concatenating the username with the password, then convert the resulting string to uppercase. Next, convert the string to double-byte characters (American Standard Code for Information Interchange [ASCII] is converted by simply setting the high order byte to 0) and add padding (bytes of 0’s) until the string’s length is a multiple of 8 bytes. Encrypt the string with Triple Data Encryption Standard (3DES) using a fixed key in CBC mode. Take the final 8 bytes of encrypted text and use it as a key to encrypt the whole encrypted string again using 3DES in CBC mode. The password hash is the final 8 bytes of the resulting string, converted to printable hexadecimal format.

Tip

When Oracle releases 11 g, they will make an important change in the databases authentication system and thus to this algorithm. The database will be configured by default to enforce case sensitivity on passwords. No longer will the database convert each password to upper-case before running it through the password hashing algorithm. This allows users to add a significant amount of complexity to their passwords by mixing upper- and lowercase characters, but more importantly, vastly increases the effort required for an attacker to brute force their way into the database. In order to facilitate backwards compatibility, Oracle will include a configuration setting to disable this new feature and remove case sensitivity on passwords.

We strongly suggest that you do not disable this new security feature. Almost every other computer system that people interact with already enforces case sensitivity on passwords. In fact, most Oracle users presume that their passwords are already case sensitive and type their password in with the same case each time they log in. It will be a minor shift at most to have a whole organization remembering to input their password in the proper case, so take advantage of the situation and allow Oracle to help you improve the password security in your databases.

Types of Hashing Algorithms

There are multiple types of hashing algorithms, but the most common are Message Digest 5 (MD5) and Secure Hashing Algorithm (SHA) 1 and 2. The slightest change in the data will result in a dramatic difference in the resulting hash values. Let’s hash a short phrase to demonstrate what happens with only a minor change. For this exercise we’ll use part of the book title.

Phrase: Introduction to Information Security

MD5 hash value: d23e 5dd1 fe50 59f5 5e33 ed09 e0eb fd2f

Now let’s make one small alteration, changing the “t” in “to” from lowercase to uppercase:

Phrase: Introduction To Information Security MD5 hash value: 0b92 f23e 8b5b 548a aade bd1b 40fa e2a3

Note the complete change in the resulting hash values. Here they are stacked for an easier comparison:

d23e 5dd1 fe50 59f5 5e33 ed09 e0eb fd2f 0b92 f23e 8b5b 548a aade bd1b 40fa e2a3

As you can see, small changes make a big difference. If you would like to try this yourself, it is easy to do. For example, go to www.wolframalpha.com and enter the hash function you would like to use (MD5, SHA1, etc.), followed by a space and then the phrase.

Hashing

How do we know our clone is an exact duplicate of the evidence drive? The answer comes in the form of a hash value. A hash is a unique value generated by a cryptographic hashing algorithm. Hash values (functions) are used in a variety of ways, including cryptography and evidence integrity. A hash value is commonly referred to as a “digital fingerprint” or “digital DNA.” Any change to the hard drive, even by a single bit, will result in a radically different hash value. Therefore, any tampering or manipulation of the evidence is readily detectable.

Hashing example

Let’s hash a short phrase to demonstrate what happens with only a minor change. Apologies up front to any Baltimore or Cleveland fans. For this exercise, we’ll use SHA1.

Phrase: Go Steelers!

SHA1: c924 4cac 47b3 4335 5aed 06f3 cc85 ea82 885f 9f3e

Now let’s make one small alteration, changing the “S” from upper case to lower case. When we rehash, we get this:

Phrase: Go steelers!

SHA1: 1a10 ffd1 db12 c88f 88e6 b070 561f 6124 f632 26ec

Note the drastic change in the resulting hash values. Here they are stacked for an easier comparison:

c924 4cac 47b3 4335 5aed 06f3 cc85 ea82 885f 9f3e

1a10 ffd1 db12 c88f 88e6 b070 561f 6124 f632 26ec

As you can see, small changes make a big difference. If you’d like to try this yourself, it’s easy to do. Go to http://www.wolframalpha.com and enter the hash function you would like to use (MD5, SHA1, etc.), followed by a space and then the phrase Go Steelers( (See Figure 4.4.)

Figure 4.4. WolframAlpha results.

One-way hashing algorithms’ basic characteristics

1.

The one-way hashing algorithm takes a stream of binary data as input; this could be a password, a file, an image of a hard drive, an image of a solid state drive, a network packet, 1’s and 0’s from a digital recording, or basically any continuous digital input.

The algorithm produces a message digest which is a compact representation of the binary data that was received as input.

It is infeasible to determine the binary input that generated the digest with only the digest. In other words, it is not possible to reverse the process using the digest to recover the stream of binary data that created it.

It is infeasible to create a new binary input that will generate a given message digest.

Changing a single bit of the binary input data will generate a unique message digest.

Finally, it is infeasible to find two unique arbitrary streams of binary data that produce the same digest.

Chain of Custody

In addition to the use of integrity hashing algorithms and checksums, another means to help express the reliability of evidence is by maintaining chain of custody documentation. Chain of custody requires that once evidence is acquired, full documentation be maintained regarding the who, what, when and where related to the handling of said evidence. Initials and/or signatures on the chain of custody form indicate that the signers attest to the accuracy of the information concerning their role noted on the chain of custody form.

The goal is to show that throughout the evidence lifecycle it is both known and documented how the evidence was handled. This also supports evidence integrity: no reasonable potential exists for another party to have altered the evidence. Figure 2.6 shows an evidence bag, which may be used to document the chain of custody for small items, such as disk drives.

While neither integrity checksums nor a chain of custody form is required in order for evidence to be admissible in a court of law, they both support the reliability of digital evidence. Use of integrity checksums and chain of custody by forensics investigators is best practice. An example chain of custody form can be seen in Figure 2.7.