Nate Lawson: Exploiting Error-Correcting Codes To Patch-Proof Software
Thomas Ptacek | August 22nd, 2007 | Filed Under: Defenses, Uncategorized
Common problem in software protection:
You have a subprogram that checks to make sure no debugger is attached to your code.
Attackers patch the subprogram, or its callers, to avoid the check.
You verify the subprogram and its callsites with a hash.
Attackers patch the verification code, or its callers, to avoid the check.
Repeat ad infinitum.
Nate Lawson has two cool “mesh design” answers for this problem.
The first is “hash and decrypt”. A “check for a condition” is a boolean function. Patching boolean functions is trivial (usually just a one-byte change). Instead of emitting a boolean, make your “check” compute a condition-dependent value, and use it as a key. A sketch:
Instead of a true-false function, write a function that computes a value that depends on the condition. For instance, an antidebugging function might use log-scaled instruction cycle timings.
Collect these measurements and hash them.
Use the hash as an AES key.
Use the key to decrypt and execute the “success” path through your program. If the “check” for the condition failed, the key will be wrong, and the success path won’t execute.
What’s cool about this is that hashes are an inherently strong way of aggregating lots of different measurements (the integrity of program text, stored state, and the results of explicit measurements), and the unlock-and-execute pattern means no simple patch can detour the programs self-checks.
Nate’s next idea, just posted in his blog, thus invalidating his future patent claims, is to use error correcting codes to do the same thing.
Instead of verifying program text by hashing and generating a key, Nate proposes to use Turbo codes to generate parity blocks for security-sensitive functions. Instead of simply calling these functions in the text, programs copy them, apply the parity to correct any “errors” (read: unauthorized patches), and execute.
Clever! Read the post. As always, Nate’s posts are required reading.
Dan Weber
August 22nd, 2007 8:58 amHaving a magic routine return a key based on the subprogram, or anything else (a dongle, a website, a hard drive ID) isn’t really that much better than generating a boolean.
The attacker will run the program in a controlled environment, observe the key being calculated, and then have the routine return that key.
Thomas Ptacek
August 22nd, 2007 9:19 amOnly if the key is static.
Dan Weber
August 22nd, 2007 9:19 amSorry for the double, but…
> Nate’s next idea, just posted in his blog, thus invalidating his future patent claims,
Nate has not yet invalidated any patent claims on this. If your lawyer says he has, you should get a better lawyer.
Dan Weber
August 22nd, 2007 10:53 amSo the “success path” through your program changes the key it itself is encrypted with?
As Nate said, this might work in the realm of computer games where they are, say, a hundred different levels to play, and each distinct level advancement runs the check. You’d have to undo your previous changes to the program before a check happens to get to the next level.
But assuming we’re talking about “important” software: say, a password-checking program. If I want it to ensure that it’s not been tampered with or attached to a debugger, I need to have some finite number of integrity checks occur. An attacker who has access to the running program can just monitor those integrity checks and replace those functions with simple functions that return the right answer. Even if you have 10 of them all checking each other, they have to run in some order.
(You might be able to do some interesting stuff with dual processors, if you could make them each do what you wanted at a certain point in time.)
I suppose you could write some mondo-modular program that downloads encrypted pieces of itself live from the Internet as it is running, if you were really desperate to protect your stuff. But then you might just upload the raw input to the server and let it return the answers.
In the real world, of course, we don’t need perfect; we only need to annoy the best people enough that they don’t bother. (But making something too challenging might just encourage those best people…)
Thomas Ptacek
August 22nd, 2007 11:44 amSorry, I had been awake for about 45 seconds when I wrote the preceding comment (I’m that lame).
The correct response was, “it doesn’t matter if the attacker can decrypt the second-stage code; it matters if the unlocker can”. The point is to express a condition as a 128 bit random number, rather than as a 1 bit condition code based on that number.
Hash-and-decrypt is not a final answer to software protection; it’s a tool used as part of a broader mesh of protections. As you read Nate’s posts, the theme that emerges is tools designed explicitly to increase the cost to an attacker to defeat them, even if the attacker knows how they work.
Most software protection schemes revolve around “gotchas” — secret knowledge that the defenders have. The defenses concentrate on making it hard for attackers to learn the secret knowledge. But once you have it, putting it to use is trivial.
What I like about Nate’s ideas is that even if you know how a hash-and-decrypt scheme works, you have to write significant, stateful, tricky code to exploit it. Yeah, in and of itself, that’s not game-changing. But it adds real cost to attackers, even good attackers, and also reduces the value of a “class break” on the system (instead of a single patch, you have to distribute an “engine” for breaking the title).
Nate
August 22nd, 2007 12:21 pmDan’s right, in the US at least, you have 1 year to file a patent after first publishing the technique. International patents have different requirements so it’s best to file first before publishing. Disclaimer: not legal advice, verify with your lawyer first, etc.
Dan is also right in that if you run the system to the point just before the key is used to decrypt the appropriate next segment and then grab that key, you’ve got it. Or, you can watch the program run and once you see the types of things it is hashing, try to brute-force the rest of the inputs to get the key.
However, both of these attacks assume a bit about what the attacker has already achieved. In the first case, they’ve identified the exact location of the code that does the hashing and have exercised every path of code that is a precursor to decryption. In the old cracker scene, that would be called “100%” (i.e. they played all the levels to be sure it worked). That takes time. In the second, the designer screwed up by hashing too few things. If non-security-related things are being hashed as well, you can create a search space that is too big for brute force.
Think about cracking a word processor with this scheme. Each component (font loading, individual help function, spell check, download new updates, etc.) hashes various things, including the exe in memory and generates a different key to decrypt themselves before execution. How sure as a cracker are you that you found all the checks?
I wrote about hash-and-decrypt back in April though. Any comments on the error correction approach?
Thomas Ptacek
August 22nd, 2007 12:30 pmWell, clearly, if attackers can bring the program right to the point where error correction is about to be applied, they can simply skip over the error correction.
Dan Weber
August 22nd, 2007 3:37 pmI hadn’t been thinking about the use of the keys; I was thinking (for some reason) that the keys would be used immediately after calculation, in which case Something Bad would happen immediately, and it would be a simple matter to rewind.
Of course the keys could be calculated well before they are used, making locating those calculations a bit tougher.
The teams I’ve been on in the real world have done some similar things, depending upon our paranoia and threat model. Good lawyers also turn out to be useful when you find someone swiping your stuff.
Thomas Ptacek
August 22nd, 2007 3:40 pmA threat model we’ve been working in lately has been, “we’d like to offer large cash prizes for winning this game”.
John McDonald
August 23rd, 2007 2:52 pmI’m out of my element here, but it seems like the natural response to the turbo code idea would be to make the ‘crack’ an actual standalone light-weight debugger that uses memory access breakpoints or page protection tricks to hover over the bits you want to patch.
That said, I assume you’d counter such a ‘crack’ with other techniques.
John McDonald
August 23rd, 2007 4:43 pmEr, yeah, I guess you already said that about 10 times. ;> Anyway, if you were willing to go into ring0, I’d imagine some of these ideas (and definitely the techniques in the ‘Previous Work’ section) could be adapted for writing a programmatic, stateful crack that circumvents anti-debug code:
http://www.uninformed.org/?v=7&a=1&t=sumry
Mmm.. kernel drivers from http://www.gamecopyworld.com.
Anyway, even with this level of access to the target program, you could still make it an incredible pain in the ass to crack. At this point, it’s probably worth just coughing up the $35 to register your copy of “My Little Pony 3: Hell is Other People.” :>
Leave a reply