Mesh design pattern: hash-and-decrypt

April 9, 2007 ~ Nate Lawson ~ 4 Comments

Hash functions are an excellent way to tie together various parts of a protection mechanism. Our first mesh design pattern, hash-and-decrypt, uses a hash function to derive a key that is then used to decrypt the next stage. Since a cryptographic hash (e.g., SHA-1) is sensitive to a change of even a single bit of input, this pattern provides a strong way to insure the next stage (code, data, more checks) is not accessible unless all the input bits are correct.

Diagram of hashing and then decrypting

For example, consider a game with different levels, each encrypted with a different AES key. The key to decrypt level N+1 can be derived by hashing together data which only is present in RAM after the player has beat level N with an unmodified game (e.g., correct items in inventory, state of treasure chests, map of locations visited, etc.) If an attacker tries to cheat on level N by modifying the game state, they won’t know what items they need to have, may load up their character with items that are impossible to have at that point in the game, or one or more map positions won’t have been marked as visited. In this case, the hash and thus the next level key will be incorrect. Any difference in the hashed data produces an incorrect key and the level cannot be decrypted without the exact key.

In software protection, the focus is on verifying that security checks are intact and running properly. Hash-and-decrypt would cover code and data locations that might be modified by an attacker who is debugging or patching the application in order to reverse engineer it. This includes locations that might be changed by setting breakpoints (i.e., int 3 or Detours-style function hooking, debug registers DR0-3, IDTR a la Red Pill) or self-check functions that may be disabled or paused while analyzing the executable. The encrypted stage N+1 can be parts of the application as well as other self-check functions.

To tie together multiple self-check functions, hash-and-decrypt can also be layered. For example, each self-check function, which monitors one or more different hook points, can iteratively hash a unique seed each time it runs along with the data it observes. The unlock function hashes each self-check’s hash, decrypts, and then executes the protected code. If an attacker pauses one or more of the self-check threads, the hash will be incorrect when the unlock function runs.

To slow down the attacker, invariants that are not security-critical can be included in the hash (“chaff”). For example, the game could hash parts of RAM that are known to be constants or map data. This keeps the hashed addresses from pointing out what’s important. This falls under the category of obfuscation techniques, but is a good example of how each software protection method mutually enforces each other.

Finally, this technique can be implemented in hardware to prevent glitching attacks. In a glitching attack, a pulse is used to disrupt a processor’s execution (usually via the clock line), causing some operation to be performed incorrectly. Attackers can use this to target internal logic and trigger malicious code execution in tamper-resistant devices. To counter this, the internal state (i.e. pipeline registers, address lines, caches, IR) of the processor can be hashed by custom hardware each clock cycle. At the end of each instruction, the final hash is used to unlock the next operation. If a glitch caused the value of any flip-flop in the CPU to be incorrect during any of the intermediate clock cycles, the next operation will not decrypt properly.

Chain, defense-in-depth, and mesh models again

March 29, 2007March 29, 2007 ~ Nate Lawson ~ 1 Comment

Richard Bejtlich recently discussed my posts on the mesh design model. Thomas Ptacek added a post comparing the three terms I’ve described. Since there is still some confusion, let me try to summarize.

Chain: break one of N mechanisms, all equally compromise your system. Example: SSL load-balancers that terminate and then re-encrypt a session. Attack: extract the private key from the load balancer OR the backend server, whichever is easier.

Defense-in-depth: break all N mechanisms (often in order: 1, 2, 3, …) to compromise the system. Example: multiple separately-configure firewalls (i.e. DMZ). Attack: traverse firewall 1, then firewall 2, then access database server.

Mesh: break all N mechanisms at exactly the same time. Sequential, incremental compromise is not possible as it is with a purely defense-in-depth approach. Example: cryptographic key where each bit is independent of all the others. Attack: guess all bits correctly (i.e. brute force).

Each of these models has its strengths and weaknesses and should be used where appropriate. SSH public key authentication is a chain model. The server trusts your public key signature which was generated from a key that you decrypted using your passphrase. This is a useful chain since it’s much easier to remember a passphrase than a 256-byte random string. But it also means the server is equally compromised if you type in your passphrase from a public terminal, use a weak passphrase and the attacker does a dictionary attack on your private key file, or the private key is hijacked from RAM of a persistent SSH connection. That’s a series of risks that I understand and am willing to accept in order to avoid memorizing my DSA key.

Also, defense-in-depth can be used to provide multiple layers of mesh when each layer cannot be interlinked with the others to form a single mesh. For example, the mesh model can be applied to a set of self-checks that my network game client performs on itself to make sure it hasn’t been trojaned. And my server can implement extra interleaved protocol steps (another mesh) to verify that it’s talking to my self-checking game client, and not a generic one that has been swapped in by a cheater. The combination of applying the mesh model in both places is defense-in-depth since both can be attacked independently.

All this semantics isn’t useful without concrete examples. Next, I’ll be providing examples of applying the mesh model to solving common security problems.

Mesh approach versus defense-in-depth

March 28, 2007 ~ Nate Lawson ~ 2 Comments

A commenter suggested by email that the mesh concept in my previous post is very similar to defense-in-depth. While they are similar, there are some critical differences that are especially important when you apply them to software protection.

Defense-in-depth comes from military history where a defender would build a series of positions and then fall back each time the enemy advanced forward through the first positions. This works in security as well. For instance, a web server may be run in a restricted chroot environment so that if the web server is compromised, damage is limited to the files in the restricted directory, not the whole system.

The mesh model, on the other hand, involves a series of interlocking checks and enforcement mechanisms. There is nothing to fall back to because all the defenses are active at the same time, mutually reinforcing each other. This concept is less common than defense-in-depth for network security use due to the difficulty of incorporating it into system designs. However, it is extremely common in cryptography.

A block cipher, say AES, is a good example of a mesh design. Plaintext data is encrypted with a 128-bit key and output as ciphertext. Any good block cipher is designed so that even a 1 bit change in the key or plaintext will result in a 50% chance of a bit flip for each ciphertext bit. This is called the “avalanche effect.” What does this mean for an attacker trying to guess the key by brute force to decrypt the data? If he is incorrect by even 1 bit, on average half the plaintext bits will be incorrect. Another way to state this is that incrementally guessing the bits of an AES key is useless since guessing 127 of the bits correctly still gives you no information about the 128th bit.

An attacker facing a defense-in-depth challenge can break down each wall in order, picking appropriate attacks for each wall. He only has to be smart enough at any one time to compromise the next wall (i.e., O(n) where n is the number of walls). However, for a system designed with the mesh model, the attacker has to compromise all the walls at the same time to compromise the system (i.e., O(2^n)). This is a significant difference in effort.

Of course, the best approach is to use the mesh model plus defense-in-depth. For example, a protocol designer that encrypts data with AES and performs integrity checking with SHA-256 HMAC (instead of an AES CBC MAC) is using defense-in-depth since a flaw in either algorithm or construction is not likely to affect the other.

Building a mesh versus a chain

March 26, 2007 ~ Nate Lawson ~ 5 Comments

When explaining the desired properties of a security system, I often use the metaphor of a mesh versus a chain. A mesh implies many interdependent checks, protection measures, and stopgaps. A chain implies a long sequence of independent checks, each assuming or relying on the results of the others.

With a mesh, it’s clear that if you cut one or more links, your security still holds. With a chain, any time a single link is cut, the whole chain fails. Unfortunately, since it’s easier to design with the chain metaphor, most systems never last when individual assumptions begin to fail. There are surprisingly few systems that are designed with the mesh model, despite it clearly being stronger.

An example of a chain design is SSL accelerators that implement “split termination.” In this system, the server’s private key is moved to a middle box that decrypts the SSL session, load balances it or modifies it in some way, and then re-encrypts the data with the server’s public key and delivers it.

There are a number of weaknesses in this design beyond the obvious one that the data is in the clear while being processed by the SSL appliance. If you keep your private key in an HSM, you’ve just downgraded its security to “stored in flash and RAM of a front-end network device.” Also, now there are two places to compromise the key. Even if both offered equal security but different implementations (i.e., different bugs), you’ve reduced the private key’s security by 50% because an attacker can choose between the two targets based on their bag of exploits. But obviously, they do not offer equal security since most network devices do not include an HSM for cost reasons.

Another weakness is insertion or downgrade attacks. Insertion attacks involve the attacker connecting to the middle box and sending data to the server. The SSL appliance happily encrypts the data and delivers it to the server. If your fraud-prevention software checks for potentially phished connections by checking SSL parameters, the middle box just lied to it about the original level of security. Because the fraud prevention application’s original assumption that the other endpoint is a client was violated, it no longer can say anything meaningful about the client’s SSL connection. A downgrade attack is similar in that SSL v2 (which had trivial flaws) might be allowed on the client side but this wouldn’t show up in the connection on the server side.

The long chain of independent links introduces many potential or actual flaws. Each link has to be checked for each flaw that exists (m * n), and a failure of any link fully compromises the data.

An example of a mesh design is TLS/SSLv3 session key derivation. The two aspects that are particulary nice are the cipher downgrade prevention and combined HMAC algorithm. In SSLv2, the per-session cipher could be downgraded by a man-in-the-middle. When each side advertised its crypto capabilities, he could lie to both, saying that neither one had anything very strong and neither side could detect that this occurred. Each message in the protocol was like a link in the chain, depending on the values of the previous ones without any way to verify the previous messages hadn’t been tampered with.

SSLv3 changed this by making each side hash all the messages it had seen and use the hash as part of the generated session key. If an attacker deleted or modified messages (i.e., to reduce the advertised list of ciphers to the weakest possible), the session key for one or both sides would be incorrect. This would be detected when the Finished message was received and then both would drop the connection or try again.

The hashing primitive used for deriving keys in SSLv3 is a bit strange. It is similar to the modern HMAC construction but uses two separate hash functions, MD5 and SHA-1. At the time, this seemed insane since an attacker would have to perform a pre-image attack (even harder than a collision attack) against the hash function to find a result that would allow him to insert or modify handshake messages. Paul Kocher, the author of SSLv3, chose to use an HMAC that combined two different hash functions so that an attacker would have to find a pre-image for both. This seemed like it was going too far, increasing complexity in an area that was already quite safe. Implementers also complained at having to include two hash functions.

When the collision in MD5 and then an expected collision in SHA-1 appeared a few years ago, it didn’t seem so crazy although SSLv3 would still be secure even if it only used one hash function. I recently asked Paul why he was so focused on hash functions back in 1996 and he said, “I just didn’t trust them. MD5 hadn’t had much scrutiny and SHA-1 was brand new. So I took a conservative approach.” Of course, the genius is in knowing where it is most necessary to apply mesh principles to a design.

Protecting the protection code

March 23, 2007March 23, 2007 ~ Nate Lawson ~ 3 Comments

Now that we’ve prevented casual copying using media binding, the next step is to protect the protection code itself. This is the largest and hardest task in software protection and is typically why most attackers first try to separate the prize (video/audio or software functionality) from the protection code.

The first two techniques we’ll consider are obfuscation and code encryption.

Obfuscation uses non-standard combinations of data/code to make it difficult for an attacker (or attack software) to understand or target specific components of the software in order to compromise them
Encryption uses cryptography (often block ciphers) to prevent the data/code from being analyzed without first obtaining the key necessary to decrypt it

Obfuscation techniques include misleading symbol names, linking code as data segments (or vice versa), jump tables, self-modifying code, randomization of memory allocation, and interrupts/exceptions. The goal is to perform the normal software functionality and protection code in a convoluted way that makes it difficult to understand or reliably modify the program flow. Typically, obfuscation is done at the assembly language level after the main software has been compiled although it can be done at other stages also. This transforms the original program P into P’, which should perform the same functions as P but in a very different way.

Encryption involves pre-processing code/data in the program with a cipher (e.g., AES, RC4) and then adding a routine to perform the decryption before executing or processing the protected data. Encryption with a standard cipher is theoretically much stronger than obfuscation if the attacker does not have the key. However, the key often needs to be stored in the program or transmitted to the program at some point so it can decrypt the data. At that point, the decrypted data or the key can be grabbed by the attacker.

These two techniques are very different, and it’s important to understand why. Obfuscation, if done properly, has the advantage of having no single point of failure. The code/data is always protected during processing until the attacker carefully unwinds the obfuscation. However, it is often slower than straightforward processing, requires manual intervention to design and insert, and is rarely integrated with the rest of the software protection well enough that an attacker can’t just go around it. Encryption offers strong theoretical security, but has a single point of failure: the key. If the key is not present in the software (i.e., a PIN to unlock add-on features), encryption offers very strong protection. However, often weak encryption like XOR is used or the key is not protected very well when stored in the program itself.

The best approach is to combine obfuscation and encryption, along with all the other techniques, offsetting the weaknesses of each with the strengths of the others. For example, the traditional approach to implementing software decryption would be to take a stock C implementation of AES and call it with the key and a flag indicating it should perform decryption.

The weakness here is that the key is stored separately from the decryption routine and thus may be easy to isolate and extract. Since this function is not being used for encryption or with different sets of keys, it makes sense to combine the key and cipher implementation into a single primitive: an obfuscated hard-coded decryption function.

One approach is to take a set of random bijections and combine it with the key and cipher to produce this fixed decryption function. Specifically, each component of the cipher is replaced with an equivalent, randomized function that computes one stage of the decryption using the fixed key. This is possible because block ciphers are composed of a number of small functions (substitute, permute or shuffle around, add key material), run over and over for a number of rounds. As long as each modified function still produces the correct results for the fixed key and variable data, the combination of them will still compute the same result as stock AES. (More details on this technique, called “white-box cryptography,” can be found in these papers on DES and AES.)

Of course, if an attacker can just isolate and enslave this decryption function to recover arbitrary data from the program, it isn’t very effective. That’s why other techniques are needed to tie the decryption function to the entire software protection.

Next, we’ll cover anti-debugging and anti-tampering techniques.