root labs rdist

April 9, 2007

Mesh design pattern: hash-and-decrypt

Filed under: Crypto,Hardware,Security,Software protection — Nate Lawson @ 2:00 pm

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.

multicheck.png

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.

4 Comments

  1. > 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.

    This should be covered by the avalanche-criterium for ciphers. Hashing gains no security, I simply prepend the hash-op myself when bruteforcing the needed game-state. No?

    Comment by pepe — April 12, 2007 @ 3:03 pm

  2. I don’t understand how the fact that block ciphers have some of the same criteria as a hash function has any bearing on this. SHA-1 is being used to gather state at various points during operation, from various components. You could construct a hash function using AES as a primitive to get the same function as just using SHA, but why do that?

    Your second point seems to be that you just brute force the input bits of state. If the protection gathers more than 128 bits of data, the naive brute force attack will not produce the necessary key in our lifetime. If you try to identify all the places where it gathers data, you’re back to needing to understand the protection code. If you try to find the key in memory just before it is used to decrypt the next stage, same thing.

    Hash-and-decrypt is a primitive and needs to be used in conjunction with other primitives to prevent simple attacks like the above. The whole point of a mesh design is to have multiple checks which are interdependent and not easy to isolate for attack. I’ll be adding more articles on complementary mechanisms in the future.

    Comment by Nate Lawson — April 12, 2007 @ 3:26 pm

  3. ahhh nice… similar ideas are presented, in a somewhat more “theoretical” manner here. A particularly interesting case is when the encrypted stages i..n+i are “triggered” (decrypted and executed) upon hiting the “right” hash on some external, enviromental input that is somewhere into the “future”, which makes and dynamic analysis quite painful (static analysis already is) because it does not suffice to artificially move the clock forward, you need to mvoe the entire programs state into the future

    Comment by ivan — August 21, 2007 @ 9:32 pm

  4. Thanks for the reference, ivan. There’s a huge hole in defining the various properties of this primitive, and it’s nice to see your paper covers more ground than I did here.

    I have to write another post on this explaining how to obfuscate the process of gathering information for the hash. There are some really tricky things you can do to tie the hashing process to the functioning of the program such that it is hard to isolate which inputs actually have an effect on the output and which are no-ops.

    Comment by Nate Lawson — August 23, 2007 @ 11:11 am


RSS feed for comments on this post.

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 87 other followers