Cryptographic Hash Functions

Can symmetric cryptography meet the requirements of the Biba model, based on the data integrity checks and proper authentication?

The answer is "yes," but in a very inefficient way. Recall the practical authentication example with the UNIX (well, Linux in our case) password encryption flaw when DES in ECB is used. Of course, any of the feedback modes or 128-bit block ciphers can be used instead of DES, with the obvious performance penalties. However, in our example, MD5 scales very well. This part of the chapter is devoted to ciphers like MD5, known as cryptographic hash functions. A cryptographic hash function is an algorithm that takes a message of custom length and produces a fixed-length output, called a fingerprint or message digest. Cryptographic hash functions are also called one-way functions, because they are designed in such a way that obtaining the original plaintext is nearly impossible and truly computationally unfeasible (in theory, anyway).

A good example of practical one-way function use is packet integrity preservation. Traditional insecure packet or frame checksums are usually calculated as the bit length of a protocol data unit (PDU) divided by a prime number. A cracker can modify the data inside of the packet and easily adjust the checksum to match the new packet content. With a cryptographic hash function substituting the checksum, such a task is simply impossible as long as the hash function is strong and correctly implemented. Many packets will pass until the cracker eventually gets the job done and, most likely by that time the packet's protocol will become obsolete. An example of such improvement is Michael (MIC) in TKIP, which replaces a traditional CRC-32-style integrity check vector (ICV) used by WEP. Michael is not exactly a one-way hash; it is closer to the hash-based message authentication codes (HMACs), which we review later.

The design of a strong cryptographic hash function depends on the size of its output (the larger, the better, but using huge data fingerprints is impractical) and avoiding collisions. A collision is a condition in which you can find two different strings of data (messages) that produce the same hash function output: if x != x', hash(x) = hash(x'). If a collision is possible, then x can be successfully replaced by x', and a whole class of attacks on the function, called birthday attacks, becomes possible. Birthday attacks are based on a well-known statistical problem known as the birthday paradox. You need an estimated 253 people in the room for the chance to be greater than even that one of them shares your birthday. However, you need only 23 people in the room for the chance to be greater than even that at least two of them share the same birthday. That is because with only 23 people in the room, there are still 253 different pairs of people present!

How does one brute-force a hash function? By taking various data (usually a dictionary), hashing it with the same function, and diffing the result with the hash you brute-force until you get the same hash. If you have to brute-force 2^x messages, but find two messages that hash to the same value, you have to brute-force 2^x/2 messages, a huge difference!