Computer Scientists Develop 'Mathematical Jigsaw Puzzles' To Encrypt Software

another random user writes "The claim here is that the encrypted software can be executed, but not reverse-engineered. To quote from the article: 'UCLA computer science professor Amit Sahai and a team of researchers have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it. According to Sahai, previously developed techniques for obfuscation presented only a "speed bump," forcing an attacker to spend some effort, perhaps a few days, trying to reverse-engineer the software. The new system, he said, puts up an "iron wall," making it impossible for an adversary to reverse-engineer the software without solving mathematical problems that take hundreds of years to work out on today's computers — a game-change in the field of cryptography.'"

Comments

I Call BS

[MightyMartian]

I'm sure they can further obfuscate the actual code, but at the end of the day the processor is going to have to run machine code, and one way or the other you can tap the processor's activity to read the "decrypted" code. Beyond that, I imagine the performance penalties involved will be monstrous. Even normal obfuscation techniques have pretty heavy penalties.

Re:I Call BS

[noh8rz10]

the reason it's called "jigsaw" is because they leave large chunks untouched, and they run without overhead. it's the jaggy lines that need to be resolved, but the burden is less than you think. is it better than macrovision? i say yes.

Re:I Call BS

[MightyMartian]

Unless the software can magically tlel that it's running in a debugger or a sandbox and refuse to execute, it's activity; from stack activity to system calls to memory allocations can be traced.

Re:I Call BS

[shentino]

TPM could put a stop to that by requiring auditing of voltages.

MS already requires this of PVP drivers for vista and will revoke them if you allow copyrighted content to leak.

Re:I Call BS

[0123456]

When I was writing Windows device drivers, we so, really loved stupid games that detected a debugger and refused to run.

Fortunately most developers stopped doing that once they realised that their customers would have to wait for bug-fixes until they'd reported it to us and then we'd contacted the developers and they'd sent us a special version without the retarded code that stopped us debugging the problem.

Re:I Call BS

[MightyMartian]

I see no reason you can't use a VM to accomplish the same damned thing.

Re:I Call BS

[Darinbob]

You slice off the top of the chip and probe it. Sure it's expensive, but the people this level of security is intended for have the resources.

Re:I Call BS

[Anonymous Coward]

Jigsawing is not encryption, it's splitting things up into shared object libraries (.dll's) that the linker then has to "reassemble" as the program is loaded into memory where it is executable ie the program counter can be pointed at it and let run. No the best obsfuscation I have yet seen is X86 assembler and even that doesn't run without a ton of overhead but... disassemblers exist for it. /. is right to scoff A) the write up is contradictory B) the article makes no sense because in order to run the code the processor has to solve the puzzle so you just stick it in an emulator and hit record. C) this looks like a school and or corporate overlords hyping an unpublished paper which many of us recognize as one way peer reviewers are pressured into signing off on snake oil D) who claims that this is the first attempt at obsfuscating code? This thing: http://www.ioccc.org/ is on it's 22nd year.

Re:I Call BS

[phantomfive]

The title is wrong. It's not talking about encrypting the software, it's talking about obfuscating the software. They put the compiled code through a function that obfuscates it thoroughly. Their function is complex enough that de-obfuscating the code (that is, returning it to the original form) would be computationally expensive. The paper also talks about encryption, but that is a different part of the paper.

Which isn't to say you can't look at some variable in RAM, realize it is the boolean for 'authorized,' and then overwrite it. So it's essentially a complex obfuscation technique, which may or may not be useful. (That is my understanding of the article and abstract, if I am wrong please correct me).

Re:I Call BS

[Anonymous Coward]

I particularly liked this part:

""The real innovation that we have here is a way of transforming software into a kind of mathematical jigsaw puzzle," Sahai said. "What we're giving you is just math, just numbers, or a sequence of numbers. But it lives in this mathematical structure so that these individual pieces, these sequences of numbers, can only be combined with other numbers in very specified ways.

"You can inspect everything, you can turn it upside-down, you can look at it from different angles and you still won't have any idea what it's doing," he added. "The only thing you can do with it is put it together the way that it was meant to interlock. If you tried to do anything else — like if you tried to bash this piece and put it in some other way — you'd just end up with garbage."

And this is a Computer Scientist? Are they sure they haven't accidentally hired the actor who played Charles Epps in "Numb3rs"?

At some point this program will have to be executed by the CPU, but somehow even a disassembler would throw up its hands and declare defeat when presented with this "encrypted" code. In other news, Mr Sahai's found a way to turn your grocery list into a set of numbers that will make it impossible for anyone else to see what you want to buy. All they can do is turn it over to the clerk and watch in awe as he fills your bags.

Re:I Call BS

[ls671]

Cause the game detects it runs in a VM?

http://communities.vmware.com/thread/273480?start=0&tstart=0

Re:I Call BS

[tlhIngan]

I'm sure they can further obfuscate the actual code, but at the end of the day the processor is going to have to run machine code, and one way or the other you can tap the processor's activity to read the "decrypted" code. Beyond that, I imagine the performance penalties involved will be monstrous. Even normal obfuscation techniques have pretty heavy penalties.

Not really. I've seen memory encryption units that ensure that all data hitting memory is encrypted, and it's possible to have the startup code also encrypted in flash and decrypted internally.

Basically every modern processor (or SoC) has an onboard hardware cryptographic accellerator, and most SoCs have the ability to hard-program in a key to one-time-programmable memory. Once programmed, the lock bit is blown and the key cannot be read by the processor anymore. On bootup, the crypto accellerator transfers the key from OTP to its internal locked down key cache and the processor running internal boot code then fetches the first bootloader from flash storage, decrypts it to internal SRAM and runs it. That first bootloader then initializes SDRAM, starts the memory encryption, then loads the encrypted second bootloader from flash, decrypts it, then writes it to encrypted SDRAM and then runs it.

The SDRAM controller maybe has a few extra cycles of latency at the high clock speed (so it doesn't affect the actual RAM timing) with encryption on, so the encryption overhead is hidden by the memory access latency.

The reading of encrypted bootloaders maybe makes it a tiny bit slower since the data has to be shoveled through the crypto accellerator, but not by much.

Tapping the bus on a modern SoC is practically impossible, as well given the way those chips are fabbed. In fact, it's not often a bus anymore, but a packetized switch.

Re:I Call BS

[MightyMartian]

Yeah, but once they add the GUI interface using VB, it'll be uncrackable!

Re:I Call BS

[physicsphairy]

"at the end of the day the processor is going to have to run machine code, and one way or the other you can tap the processor's activity to read the "decrypted" code"

Sure, and one way to reconstruct the program is to provide it every possible input and map the outputs. For that matter, one way to reconstruct the program is simply to load it up, see what it does, and code your own version that does the same thing.

But the question is how deeply you can inspect the algorithms based on what you see happening in the processor, and what I believe they are claiming is that they take the algorithms and reimplement them in such a way that, while they do what they were written to do, they do it in a new complicated way which cannot be analyzed to deduce the original simple way upon which it was based.

Re:I Call BS

[MightyMartian]

That's because VMs really don't try to hide themselves from the guest. While it might be pretty hard to build a VM that did a good enough job to essentially fool software attempting to identify whether its physical or virtualized hardware that it's running on, we have the source for a number of VMs (ie. KVM and Xen) and if this kind of obfuscated software started showing up on the market, I'm sure there would be a much greater push to make a rock solid virtualized environment that mimicked physical hardware with much more fidelity.

Re:I Call BS

[MikeBabcock]

This exactly -- virus writers have been at the forefront of code that hides and obfuscates itself and VM type systems were developed to essentially run the code to determine its effects without actually running the code.

So long as the code can be executed, it can be reverse-engineered.

Re:I Call BS

[Anonymous Coward]

The idea is to obfuscate the machine code. You run the program, and it does the right thing, but in a mindbogglingly complex way that gives you no information about what it will do on the next input. Looking at the machine code doesn't help, because the algorithm is too complicated to understand.

The performance penalties are another matter entirely.

Re:I Call BS

[MightyMartian]

In other words it's going to do malloc() a big pile of memory, then throw the actual code all over the place, linked together with a helluva lot of jmps and indexes to keep track of them. Yes, I'm sure if every second or third clock cycle is spent leaping over the process's malloced space to fetch the next instruction or the next byte from the symbol table, it may be too complex to actually decompile to reproduce a reasonable representation of the original source code. But as others have pointed out, that level of disassembly isn't necessary for some level of reverse engineering, where you may only be looking for certain things like encryption keys or entry points to insert your own code. In other words, some degree of useful reverse engineering doesn't require reproducing a complete asm file.

But really, if half the byte code is jmps, then any claim that it would run at anything like an unscrambled program is BS. I think what we're talking about here is a program that, as a physical set of binaries and libraries, may be busted up in various complicated ways, but that via the bootstrap process will be reassembled in some sort of sensible order so that your standard operating system and hardware isn't taxed bumping program counters around in mad ways.

If ultimately that's what it is, well one can still presumably map access to kernel and userland objects like system calls, device drivers, shared memory and the like. Yes the byte code may be an insane mess, but if it's going to run the same way more than once, the patterns of its execution are going to show up in how it accesses its resources.

Now if you're talking about software that basically does all its own input output and talks directly to the hardware (in other words, it's basically an operating system in and of itself), then I can see the advantage. Match with some TPM scheme and it would be very hard to the point of possibly being all but impossible to sniff out what it's doing. That's the situation we're at to some degree with UEFI and similar protected bootloaders, and I'm it would be extended to this paradigm so that at every chain of app downloading, installation and execution the ability to get your hands on the executable and the kernel and general system state would be insanely difficult.

Re:I Call BS

[Dunbal]

Yup, it's the basic principle of reverse-engineering anything. If your CPU can read it, then you can read it.

Re:I Call BS

[gigaherz]

No, you have an unnamed function with unnamed parameters that takes a series of unknown numbers, and returns another unknown number.

The idea of obfuscation is that it makes the job hard to make those unknowns known, so that you can name the unnamed.

I didn't read the article, but it looks to me like at some point, the code is going to call some OS API functions, or call the UI library, or similar. And you can always start the naming from there. But of course if the WHOLE PROGRAM is obfuscated, so that the inputs are the command-line parameters and user interaction events, and the output parameters are the results and the display calls, and everything is such a mess that even the CPU doesn't really know what it's doing (really bad thing performance-wise), then it may be impractical to figure it out. Not impossible though.

Re:I Call BS

[Half-pint HAL]

Not exactly. Reverse engineering starts with the analysis of a running program with the goal of obtaining enough data about the locations of executable code vs data, major variable locations/identifiers etc to allow you to start running automated disassembly of the total code. All you can get out of a run-time analysis is a specific execution path, which does not embody the full code.

Now yes, "if your CPU can read it, then you can read it", but unfortunately in this situation, your CPU can only read it in certain circumstances, so you'll only be able to read it in those same circumtances: execution or simulated execution, leading back to the situation where you're stuck looking at traces of specific executions...

Re:I Call BS

[greg1104]

You can make the algorithm as complex as you'd like, but at the end of the day, you have an input and output(s). You may decide to take a long time to get there, but at the end of the day, I know what you did when the code ran.

This is referred to as "black-box" reverse engineering in the paper. You know what the code did for one input. And if you injected every possible input to the program, at the end you'd have worked out a complete specifications for the function. But how long will that take? It's not always "the end of the day". For functions with a wide range of inputs, it could take the life of the universe to map them all unless you know what you're looking for in advance.

Right now, obfuscation approaches for software usually have some small chocking point to attack. It might be an encryption wrapper around the main binary. Bust that with a debugger, you can get to unobfuscated code for the main system, and then really start to work your way through the program.

But if you have to fight this every step of the way, where all you do is inject inputs and get an output to figure out what the program does, it will take you forever to reverse engineer things. That's the claim of the paper. The code itself is so obfuscated that you can't read it straight and understand it, ever. It looks like random junk. All you can do is run it with an input and see what comes back, and from that reverse engineer what it does. Assemble enough of those and you can see how the program really works. But that black box teardown process--determining possible inputs, injecting them, collecting outputs, and then deriving the function behavior--is time intensive enough that it may not be practical to actually do it anymore. You don't learn anything from reversing any component that speeds handling the next; you have to attack them all like this.

There's a great line from the seminal paper on this subjectOn the (Im)possibility of Obfuscating Programs: "Any programmer knows that total unintelligibility is the natural state of computer programs (and one must work hard in order to keep a program from deteriorating into this state)" Extracting meaning from source code, being able to predict what some lines of code will do, it's hard. Ideally you'll just be able to read the code, make sense of it, and then reverse from there. Most systems that are thoroughly cracked have some sections where it's hard, but once you get those the remaining code is straightforward to read. And in fact, it's impossible to make something where you cannot reverse it. The question though is how long it will take.

If no sense is ever made of the code, you can only apply the "black-box" reverse engineering, where you inject inputs, watch outputs, and from there determine what the code does. You can't prevent that, but you can make the box so big that such work is impossible to do. That's what this technique tries to accomplish. You never find an easy part to the code you can read; all you ever find are ones where you have to map every input into an output to figure out what the code does.

Re:I Call BS

[Half-pint HAL]

...then it may be impractical to figure it out. Not impossible though.

Everything in cryptography relies on the impracticality of brute-force attacks, which are never impossible. That's why we talk about security in terms of hundreds of years.

Re:I Call BS

[IamTheRealMike]

And this is a Computer Scientist? Are they sure they haven't accidentally hired the actor who played Charles Epps in "Numb3rs"?

At some point this program will have to be executed by the CPU, but somehow even a disassembler would throw up its hands and declare defeat when presented with this "encrypted" code. In other news, Mr Sahai's found a way to turn your grocery list into a set of numbers that will make it impossible for anyone else to see what you want to buy. All they can do is turn it over to the clerk and watch in awe as he fills your bags.

I can assure you that Amit Sahai is not only a computer scientist but a highly respected cryptographer. The reason the explanation is so garbled is he tried to dumb down cutting edge mathematics for the purpose of a press release.

The code is encrypted in such a form that it is never decrypted into CPU instructions. Every operation the program does is a form of mathematical transformation. Yes, it's got a lot of overhead (probably impractical at the moment). The grocery analogy is a lot closer than you might imagine.

Re:I Call BS

[solidraven]

That's why you use virtualisation software to begin with when doing this sort of stuff. Then you can simply access anything without the software knowing about it. Memory isolation works both ways in terms of security.

Re:I Call BS

[msobkow]

I know a fellow who worked on a system that would take IBM 360 machine code, convert it into graph format, and re-engineer it as C/C++ code. They made a killing on Y2K, because so many companies didn't have the source code for some of their software any more.

So yes, I call BS as well. Computationally complex, yes, as graph theory often is. But far from impossible to reverse engineer.

If it can execute, it can be reverse engineered. Only the most obtuse and purposefully warped hand-written assembler can even approach the ability to hide an algorithm from deep inspection, and even that can be largely overcome by applying graph theory to restructure the code graphs.

Re:I Call BS

[HJED]

But surely you only need to useful component of the algorithm, there is only going to be a certain range of useful inputs.

Re:I Call BS

[msobkow]

You can contact professor Thomas Dean at Queen's University in Kingston for details of how such graph theory applies -- he was involved with the development of this reverse engineering tool.

Re:I Call BS

[Dunbal]

No, if you really really want to, you can get the data from the hardware bus. Faster than farting around in someone's obfuscated software That's the way some consoles and blue ray were broken, if I recall. And of course it only takes one person to figure out the algorithm for encryption and publish it, and the lock is broken for everyone on the planet.

Re:I Call BS

[solidraven]

Yeah, but the real problem I see with this method is that once you found an entry point and a set of conditions to one specific "tile of the jigsaw" you might be able to build up an entire tree of solutions quite quickly and solve it. It obviously requires some intelligence, hundreds of years is a brute force, but nobody said you can't use a smart attack vector on this one either. And the moment you have a point you can latch onto most obfuscation techniques tend to fail quite quickly. At least if they do not wish to cause a huge performance penalty judging form the things I've encountered. Combine it with hardware probing and I think you could get a pretty good case against this method if no additional obfuscation methods are used; Combining it with random junk and conventional scrambling could lead to a serious headache though.

Re:I Call BS

[jhol13]

I do not think this the aim. The aim is to hide the "high level" algorith so that you cannot find it out. The obfuscation seems to be done by transforming the source, not binary.

This way if you have some "interesting" high level algorithm (to solve some real life problem) you can make reverse-engineering it not only a tad hard, but extremely difficult. For example, suppose I can solve NP in polynomial time. You can see from the virtual machine traces how one case of the problem is solved, but you cannot get solution (algorithm) to solve all cases.

Re:I Call BS

[rgbatduke]

Even better than the grocery list is Searle's Chinese Room. A man sits in a sealed room. He doesn't speak or read chinese, but every now and then somebody pokes a slip of paper in under the door with some Chinese on it. The man picks it up and goes to a vast filing cabinet, matches the symbols on the paper, and pulls out a paper with other symbols on it which he pushes out the door. In this way the entire room can act like a "speaker of Chinese" even though the man in the room doesn't recognize a word of it:

http://en.wikipedia.org/wiki/Chinese_room

The interesting question is whether or not one can LEARN Chinese if one is the man in the room by monitoring the messages. And this, in turn, is a matter of information theory and complexity -- to be able to learn Chinese by monitoring a flow of symbols like this utterly without context might well be very, very difficult. The cabinet drawers, after all, might have not a single message in them but a stack of messages of similar form but equivalent meaning, shuffled. The man might have to look up the drawer to open not just on the basis of the current message but on the basis of the last ten, or hundred, messages. The drawers themselves might periodically rearrange themselves so that the man has to constantly do a tedious calculation in order to determine the current location of the right drawer in order to get the current top of stack message on the basis of the last twenty exchanges.

Now imagine that the actual conversation isn't one such room, it is thirty, or fifty, or five hundred. The first man gets the input message, goes to a drawer and gets a response, but that is not the REAL response, it is just a message to the man in the second room. That man looks up a message for the third room, etc, and it is only the man in the last room that looks up the actual response and returns it.

One can imagine lots of crypto-class transformations one can insert into the lookup process -- each man can use e.g. a one way hash of the message they receive (known to the sender as well) to permute the cabinet drawers after each response; the next message even with the same "content" might then be directions to a completely different drawer. Even a comparatively few rooms filled with many constantly whirling drawers would make it pretty hard to learn Chinese, especially the Chinese associated with rarely used drawers or contexts. And learning it at all would require SOME ability to connect at least the input and output symbols with actual contexts. Even if one mapped the location and content of every drawer and reverse engineered the entire algorithm for doing the shuffling, one still has to assemble the result into a full semantic map. Not easy, although as noted not impossible.

rgb

Re:I Call BS

[Kielistic]

I suppose it depends on your reason for obfuscating. I would imagine a lot of the buzz about this is from people interested in copy-protection but I don't think this would help. Limited input-output there; easy to trace the execution path. Complex mathematical functions maybe? (compression and the like) Again, the CPU has to perform that math- just watch it.

Software cannot be hashed and run. By definition this process is reversible. I wouldn't put too much money on having it be impossible to crack.

Re:I Call BS

[AJH16]

If I'm reading the abstract correctly, the secret of this process is that they actually obfuscate the operation. They combine the desired function that needs to occur with a key that isn't easily reversible and when applied through a function, produces the desired output. Since the key is instrumental in determining the actual result of the function, without knowing the original intent behind the key (which requires breaking the asymmetric nature of the key) you can't determine what the actual calculation done to obtain the result was.

I'd be interested to know more about how they accomplished this, but such cryptosystems have long been a goal in the field and have been improving. They also have practical applications in providing cloud based data processing where information can be submitted in an encrypted state and the result can be produced by performing an operation on the encrypted value which produces a properly encrypted and correct answer without having to possess the decryption key. It is a very fascinating field to say the least.

Re:I Call BS

[dywolf]

precisely. its the exact same concept behind why movie and music DRM will always fail: at some point as has to become a signal the tv/speaker can play. and as soon as it does, its "plaintext" (for lack of better word) and can be seen.

Re:I Call BS

[SLi]

Yeah, like the range of useful inputs for a C compiler.

Re:I Call BS

[Dracolytch]

Unless a "useful input" is an encryption key.... That you don't have. And the output is another encryption key actually used to decrypt something. Now you have neither they key nor the algorithm used to generate a child key. All encryption is crackable given enough time, but if this works as advertised, it will add to that time.

Re:I Call BS

[Megane]

The other day I took apart an old HD-DVD player (I wanted the Toslink transmitter out of it for a MythTV box I'm working on) and noticed that they ran a bead of epoxy around the edges of certain chips. Mostly it was RAM and Flash chips, and they even remembered to epoxy the unused pads of a dual-padded chip location. I was amused that they also epoxied around the Realtek ethernet chip.

Re:I Call BS

[r33per]

I call it luck (H. Solo).

Re:I Call BS

[Megane]

Back in the late '80s, I had lots of fun cracking copy protection on games that ran on the Mac. (Yes, there actually were games for the Mac, but I had usually more fun just breaking the copy protection.) My motivation was that I had a 2 megabyte RAM upgrade, which back in those days meant running a 1.5M ram disk (super fast!) and I wanted to keep it running as long as possible with a debugger installed. (Most copy protection code outright killed a debugger, rather than just detecting it.)

They were usually nested in layers like a matryoshka doll... break one layer, decrypt it, update the executable with the decrypted code (which there was always space for since the old decryption was no longer needed, and they never used compression), then move on to the next layer. As long as I had the original disk with the "special" intentionally bad sector, it was just a matter of enough time and enough work. My motto was "If I can boot it, I can crack it."

Most were obviously done by adding a copy protection wrapper to the code, and by the time the real program started, it didn't know a thing. There was one game called Strategic Conquest (an Empire variant) which had a check that supposedly set it to play at level 17 (you could normally select level 1-15, which affected the computer's production rates), but I didn't have much trouble finding that.

So basically I agree that this is BS. Without an external secret (like a dongle) that encrypts the code, or an operating system that conspires to prevent you from reverse-engineering the code, the "you can't run me" decision at some point can be subverted, even if it requires manually unwrapping multiple layers of crap to get there.

Re:I Call BS

[cdrudge]

The title is wrong. It's not talking about encrypting the software, it's talking about obfuscating the software. They put the compiled code through a function that obfuscates it thoroughly. Their function is complex enough that de-obfuscating the code (that is, returning it to the original form) would be computationally expensive.

At a fundamental level, isn't encryption just a mathematical obfuscation?

Re:I Call BS

[phantomfive]

That's an interesting way of looking at it. I feel like there's something different, but I'm not sure what.......

Re:I Call BS

[Anonymous Coward]

I remember making and using a "virtual machine debugger" cracktool in about 1997, basically emulating the processor it was run on, for precisely this reason.

Terrible performance, worse interface, awful driver support, used a ton of memory at the time, you couldn't be connected to the network, and it wasn't spread around much to keep it secret (I didn't give it to more than about 10 people, no longer have a copy myself and honestly don't mourn its passing). But you could live-monitor things that wouldn't run under SoftIce and would otherwise have to try to deadlist in IDA. You could even rewind the code execution path because it kept a rolling history, and analyse it: not a feature I recall seeing in its competitors.

Peanuts compared to OllyDbg or modern IDA Pro, and it wouldn't run on modern computers, but it made very, very short work of copy protections at the time.

Re:I Call BS

[TemporalBeing]

The code is encrypted in such a form that it is never decrypted into CPU instructions. Every operation the program does is a form of mathematical transformation. Yes, it's got a lot of overhead (probably impractical at the moment)

Then the program is never run, only the decryption of it. Even then, a smart cracker can obtain the original code through simple means. For the user to actually use the program it has to at some point be run on the CPU; even if they figured out how to direct it to a DSP present on all computers, you can still trace the DSP using virtualized environments and it'll be pretty obvious very quickly that that is what is being done early in the instruction cycles.

Sorry, but it's BS.

Re:I Call BS

[TemporalBeing]

I'm sure they can further obfuscate the actual code, but at the end of the day the processor is going to have to run machine code, and one way or the other you can tap the processor's activity to read the "decrypted" code. Beyond that, I imagine the performance penalties involved will be monstrous. Even normal obfuscation techniques have pretty heavy penalties.

Not really. I've seen memory encryption units that ensure that all data hitting memory is encrypted, and it's possible to have the startup code also encrypted in flash and decrypted internally.

All you need is an appropriate virtual environment - VMware, etc. - and you're set to capture the decrypted data. Even TPM can't get around that if you emulate the TPM chip sufficiently. At worse, you end up with something like the Bochs Pentium Emulator that emulates every single instruction and all hardware - e.g you can run x86 code on a non-x86 processor, at a high cost of performance, but the software running on it couldn't tell it was in a virtual environment.

Re:I Call BS

[narcc]

Naw, that's only useful if you want to track an IP address.

Re:I Call BS

[Anonymous Coward]

I was working in one small company, that obfuscated data - it rotated bits based on graph theory(actually that was first time I realized, that uni was teaching theoretical stuff that could be used practically), so NO - reverse engineering in classical way was not possible, unless you were ready to slow down processor and analyze data behind every tick - there was no boolean data - there was nothing to analyze - you could get data only when function required it, because all data was chaos of bits - moving every tick and different bytes at different speeds, so you could not analyze even data types - forget about it, because smart people thought about that 15 years ago - your thinking is 30 years old at least...

They made product that used USB dongles(also virtual) to protect software - I had not seen any cracks for this softwares anywhere, so it was and still IS working, I assume theoretically you could reengineer, but in RL - sorry - no, and last time I checked couple of years ago - their product still was not cracked and it does not require much to make more complex graph, but decoding, analyzing and reengineering would take same(or actually much more) time that to build software with the same functionality, so the main goal was reached :)

Before you call it BS, are you aware what is Graph Theory in action? These include not only static graphs, that could describe for example - C/C++ code, but also living processes with iterative(or cyclic) steps - youabsolutely has no idea about nightmare decoding data, that would have different graph for each data segment(4, 8 or 16 bits large), cycling it through iterations of changes? I will cite slashdot again to understand why it is not BS: "without solving mathematical problems that take hundreds of years to work out on today's computers". Cryptography was really added unnecessarily - there is no cryptography needed at all.

Deciphering != Reverse Engineering

[Dynedain]

Deciphering/Decrypting is not the same thing as Reverse Engineering.

Reverse Engineering is duplicating the functionality without seeing the source code. That should still be possible if you have the ability to run the program.

Re:Deciphering != Reverse Engineering

[wierd_w]

One way around this (for reverse engineering) would simply be to run it inside a VM with a built in stack trace debugger, like Bochs.

You can peek at the raw instructions percolating through the VM's emulated CPU that way. The application itself is then the decryption key, since the system has to be able to run the application.

PITA, but I don't see how this is anything more than just a "bigger" speedbump, at least as far as disassembly goes. Now, making said decryption require nasty bits of hardware to thwart using a VM, and clinging tightly to treacherous computing with a TPM and a hardware hypervisor on top of this? That's more dicey.

The question here is... why do this? Is preventing Cracker Jack from the warez scene from simply disabling your "authenticity checks" so horrifically important? That's the major application for this that I really see, besides making epically horrific malware. (Though if you ask me, they are both the same thing.)

Seriously, other than making personal computing become something from communist russia, what is the benefit of this?

Re:Deciphering != Reverse Engineering

[MightyMartian]

Yes, the only way this works is with hardware to back it up. But if we're back to effectively using some sort of dongle to execute, well that road has been well-traveled as well.

Re:Deciphering != Reverse Engineering

[wierd_w]

I was thinking more along the lines of "special processor instructions", that make use of quirks of real silicon. Given how intel and amd both have taken to cramming lots of extra devices onto the die, a small "inside the CPU" black box designed for this very application would do the trick just fine, and would likewise ensure its presence on modern rigs.

A virtual machine halting execution would be detected by the running software, because it wouldn't get the proper responses from said black box. You'd have to uncap the cpu, and watch with very specialist equipment.

I am thinking a small asynchronous secondary processor.

Re:Deciphering != Reverse Engineering

[fuzzyfuzzyfungus]

Seriously, other than making personal computing become something from communist russia, what is the benefit of this?

Wait, isn't that considered to be feature enough?

Re:Deciphering != Reverse Engineering

[MightyMartian]

Yup, and if you can run the code, no matter how obfuscated. in a controlled environment like a virtual machine, no matter how complicated it may be, its interaction with the virtualized hardware is going to be observable. I guess you could start writing software that sniffs out that it's in a VM, either by looking for paravirtualization or simply for looking for some subset of bugs or limits in the virtualized hardware that one wouldn't find on actual physical hardware, but that's just the better mouse trap vs. the smarter mouse. Besides, other than in very specialized applications, why would anyone invest in general use software that can only run on certain machines.

Re:Deciphering != Reverse Engineering

[bondsbw]

Seriously, other than making personal computing become something from communist russia, what is the benefit of this?

Security. One major benefit of obfuscation is making it much more difficult to find local data store encryption keys, service endpoints, etc. It makes it harder to find bugs/exploits such as SQL injection.

Remember that not all attacks are aimed at the software in general. Many, many attacks on medical/banking/government systems are aimed at finding specific data on specific computers, and the attacker isn't running it on a VM. These attacks rely on perhaps a trojan or backdoor. The harder it is to build such an attack, the better.

Re:Deciphering != Reverse Engineering

[chizor]

one case in which reverse engineering will not succeed is if the program is obfuscated in order to conceal a newly developed algorithm.

Re:Deciphering != Reverse Engineering

[MikeBabcock]

Hardware that can't be emulated you mean.

Even high grade encryption hardware that refuses to allow debugging can be emulated, if slowly, once you have keys.

Re:Deciphering != Reverse Engineering

[superwiz]

Obfuscation is woefully poor way to stop decomposition. Any program is a graph. Any program analysis tool will traverse obfuscated code just as easily as it will traverse an non-obfuscated one. In fact, it won't even know the difference between obfuscated and non-obfuscated code. Obfuscation only stops eyeballing analysis. But if eyeballing is the only tool you use, you are an amateur. You might be a very adroit amateur, but the difference between an adroit amateur and a decent professional is that the professional will handle much greater complexity with a yawn.

Re:Deciphering != Reverse Engineering

[Lonewolf666]

I think there is some confusion about concepts in your post.

SQL injection relies on sloppy programming where the developer forgot to sanitize the input. Obfuscating the code probably won't help as the hackers don't need to see it, they just try to dump their malicious SQL code into some input field.

A trojan or backdoor is by definition something created by the original developer of the software. He can, of course, put his malicious code in before obfuscation.

Re:Deciphering != Reverse Engineering

[AK Marc]

How can a CPU execute code when it doesn't know what that code is?

Re:Deciphering != Reverse Engineering

[IamTheRealMike]

Yes, it is robust. I read the paper a few days ago.

All these comments about how you can "just look at the CPU instructions" are made by people who haven't been following developments in the field. The program never gets decrypted into CPU instructions. Heck, it was never even compiled into CPU instructions in the first place. It gets compiled into a form of boolean circuit, a mathematical equivalent of an electronic circuit that is composed of AND, NOT, OR, XOR gates and wires between them. Then that circuit is itself again transformed into a series of matrices and at that point I hit the limit of what I could understand without needing to read some of the cited papers.

This is a very, very complicated technique that builds upon decades of cryptographic research. If they say it's secure in the cryptographic sense, I think it's very likely to be so.

Re:Deciphering != Reverse Engineering

[pjt33]

The thing is that "secure in the cryptographic sense" means "provably secure against a defined threat model", and the threat model may not be relevant to real world applications. My understanding of their proof of security is that the threat model is black-box evaluation, which doesn't seem very relevant to real obfuscation.

Re:Deciphering != Reverse Engineering

[bondsbw]

No, I meant SQL injection.

Obfuscation can help reduce the chances of finding an exploitable route for SQL injection. If I am trying to break a complex piece of software, and the field that is susceptible to SQL injection is guarded by dozens of conditions, then it may be easier to decompile the program and attempt to find SQL strings with concatenation and then see where they are are not being sanitized.

And of course I'm not talking about building the software with a trojan/backdoor. I'm talking about a way in which an attacker gets access to your machine. At that point, the attacker still may not have root/administrator access, but may be able to read the software file in question. That's why obfuscation is important, it is another layer of obscurity in case enough real security measures are broken.

Re:Deciphering != Reverse Engineering

[NoImNotNineVolt]

So is the program never executed?

My understanding of computers is better than my understanding of cryptography. As far as I know, a CPU can only fetch an instruction and then execute it. If this program never gets decrypted into CPU instructions, then it can't really be a part of this fetch/execute cycle. Does this research only apply to stuff that runs on an FPGA, not a CPU?

Re:Deciphering != Reverse Engineering

[bondsbw]

If using the keys is possible then extracting the keys are possible.

Using this line of thought, we should get rid of computer cryptography. After all, it's possible to crack any cryptographic system, just very unlikely.

You may not like storing keys in code... I certainly don't like it either... but sometimes the requirements are non-negotiable. What you do then is make it as secure as possible, and if obfuscation helps, then we use it.

Re:Deciphering != Reverse Engineering

[SLi]

Consider an (non-JITing) interpreter. The interpreter is a standard piece of software, which is not obfuscated. The program being interpreted can be obfuscated, and no part of it will ever be run directly on the CPU - every machine instruction that runs is part of the interpreter.

Re:Deciphering != Reverse Engineering

[IamTheRealMike]

If you're talking about things like protecting copyrighted games then no, it's not particularly relevant, because you're typically trying to bind to some physical medium like a CD and obfuscation can only hide what you're doing to a certain extent.

However it's very interesting as a building block for other schemes. Functional encryption in particular will be very powerful, but probably not until 10 years from now. It's really an entirely new paradigm, as revolutionary as the invention of public key crypto itself (which also started out unusably slow).

Re:Deciphering != Reverse Engineering

[NoImNotNineVolt]

While I grant that in this scenario, you won't be able to easily recover the original high-level interpreted language code, you'll still be able to see the equivalent machine code that the interpreter executes. In the end, you'll have the same thing that any disassembler would provide: a sequence of opcodes that describes the program you're investigating, no? I don't see how this differs materially from running any ordinary non-obfuscated [stripped symbol] compiled C++ binary through a disassembler. No, it won't get you back to the original C++ source, but it will still provide full insight into the operation of the program.

Re:Deciphering != Reverse Engineering

[NoImNotNineVolt]

That's my point. It's time consuming, but the summary claims "take hundreds of years to work out on today's computers". It's been done before in the past, and computers haven't been around for hundreds of years. There's a difference between improved obfuscation techniques and real cryptography. You can't decrypt something just by studying it a byte at a time, whereas this obfuscation technique does in fact seem vulnerable to just such an approach.

Re:Deciphering != Reverse Engineering

[ultranova]

Consider an (non-JITing) interpreter. The interpreter is a standard piece of software, which is not obfuscated. The program being interpreted can be obfuscated, and no part of it will ever be run directly on the CPU - every machine instruction that runs is part of the interpreter.

Consider your browser. It has a Javascript interpreter, which executes the scripts downloaded from the Web. Notice how the CPU usage goes up when it encounters a particularly bad page? It's because the Javascript is, in fact, executing on the CPU, even if it rides atop several layers of abstraction.

Re:Deciphering != Reverse Engineering

[SLi]

Well, that's exactly the new thing here. You can think it this way:

The program being interpreted is a black box function, taking in an encrypted state and outputting an action to execute and the resulting encrypted state (this is accomplished using homomorphic encryption). The state can include things like values for variables, but it also includes the program counter. What the interpreter does is it loops this function over and over, at each step executing the action it outputs. Because you cannot observe the state (as you never have it in decrypted form), you cannot deduce anything beyond the actions.

Note that any program can be expressed in this form: Essentially, in a conventional processor the black box boolean function you are executing is the function from a state to the next state (to the next instruction or next clock cycle, however you wish to view it).

As to how it's possible to keep the state and the computed function secret, that's the thing done using homomorphic encryption, and nobody claimed that to be easy, but there's no reason why it should be theoretically impossible, and it in fact turns out to be possible. The thing is, you *do* have the state, including the program counter, but it's only available to you in a form which you cannot read.

so..will the next Stuxnet

[Anonymous Coward]

so..the next Stuxnet will be untraceable , cool

Gotta love articles without details

[Anonymous Coward]

Clearly the journalist had no idea what they were writing about.

Re:Gotta love articles without details

[MrEricSir]

You mean a link to the paper, like the one in the third paragraph of the article?

Re:Gotta love articles without details

[sydneyfong]

When you get to that, then it's the GP turn to have no idea what the article is writing about.

I took a glance at it. Probably don't really understand it unless I spend a week or two seriously reading it thoroughly and its cited articles...

Re:Gotta love articles without details

[Anonymous Coward]

They did it to the article it self, I couldn't reverse engineer it!

I don't understand how what the CPU sees can't be seen by anyone else? If the instructions are executed in crazy order the result will be crazy with near 100% certainty, so instructions will have to be executed in a specific order to get the specific result. This stream of instructions is all one needs to reverse engineer it regardless of how clever the obfuscation is.

There is a reference in the article to "certain class of non-obfuscateable" circuits. I think they mean the class of programs which can have their instructions executed in some random order without affecting the output. If this is what they meant, I think that set is a very small set, and may be not worth all this bother.

Victory for virus writers

[technosean]

Who gains from this? Most of all? Virus writers.

Perhaps the real solution is to have the OS never execute code looking anything like this.

Re:Victory for virus writers

[MightyMartian]

Heh. No fucking shit. It would be a malware writer's holy grail; software that has no identifiable signature.

I still think it's BS, at least on any kind of processor or operating system we're running now.

Re:Victory for virus writers

[ls671]

Heh. No fucking shit. It would be a malware writer's holy grail; software that has no identifiable signature.

I don't think anti-virus software needs to understand, reverse-engineer or decipher a virus program in order to identify its signature. That's not how it works. That's why there is false positives with programs that do not do what the anti-virus software thinks it does.

Re:Victory for virus writers

[Opportunist]

As long as the code is always identical, you're right. It is likely, though, that this machine is able to produce vastly different results from minuscle changes in code, resulting in a very easy way to generate an arbitrary amount of copies of your virus code that doesn't look anything like the others to a scanner.

Re:Victory for virus writers

[TheLink]

100% AV/malware detection is arguably harder than solving the halting problem - since it's not certain you're given the full program and its inputs ;). In practice malware is not so obfuscated and while it seems to be a losing battle, I don't have to outrun the "bear", I just have to outrun the average user...

That said it would be safer if OS makers solved it by better sandboxing and better sandboxing infra/UI. Sandboxing is like "solving" the halting problem by setting a time limit.

In fact you're still in a better position even if you allow the program itself to request/suggest the limits upfront for its sandbox. Because if the program asks for too much you know it's up to no good.

Halting problem analogy: if a program asks for a time limit of infinity you know it might not halt (it could still halt) whereas if it asks for a time limit of 60 seconds whether it halts or not is immaterial since the OS is going to limit it to a max of 60 seconds ;).

3rd parties could audit the sandbox request templates and sign them, so you could lock down a machine as much as you want or not at all. You could set up a machine so that Aunt May could install any harmless software (no access to private data, network, etc), or any software signed by a trusted party.

Re:Victory for virus writers

[ls671]

It is likely, though, that this machine is able to produce vastly different results from minuscle changes in code

I guess it could produce different results with no change in the code but then again, virus writers already have similar tools at their disposal to avoid detection.

make a crackme

[ZeroNullVoid]

If they really think it is so good, then they should put their money where their mouth is.
Make it into a crackme, issue a large award for solving it.
Post it online. I give it a few weeks max, if that.
And who is to say it can't still be manipulated once running?
Think of the performance cost.

Either way, I have no faith in an article with little details.

Re:make a crackme

[SLi]

Even not being new to Slashdot, I'm completely baffled by your talk about "an article with little details", considering it links to the paper that will be presented in a conference that has all the details you would want.

Seems improbable

[Anonymous Coward]

I can't imagine any circumstance where an execution trace could not be used to reconstruct the original behavior of the code, no matter how obfuscated it is.

Re:Seems improbable

[MightyMartian]

Yup. At the end of the day, if this is at all useful and the hardware and OSs out there now, it;s still going to have to execute, and if it executes, you can run it through a debugger and watch it.

Re:Seems improbable

[Anonymous Coward]

I can't imagine any circumstance where an execution trace could not be used to reconstruct the original behavior of the code, no matter how obfuscated it is.

This difference in ability to imagine is merely one among a number of characteristics by which you can be distinguished from a UCLA computer science professor.

Re:Seems improbable

[shentino]

Not on a protected OS you can't.

I imagine that if this is implemented it will be patented much like Blu-ray, and the only way to get a license is to swallow the DRM.

Re: Seems improbable

[wierd_w]

Some VMs have "save state" features.

Let's say we have a program that branches many times, as you describe above. The VM is controlled with a script. On the first pass, it looks for and records all instruction branches on the first program run along with the data compared against for each branch to execute, then reloads the saved state at initial program load, and begins systematically walking and triggering code.

On each pass, it spits out what the CPU did, with what inputs.

Since it is a given that new paths that weren't walked before will have yet more banches, the duty list of paths to walk needs to be amendable at runtime.

It may take a very long time to walk out all of the paths and completely map all code logic, but that then becomes something you turn on and then wander off to go eat a sandwich for. Most packages that will use this kind of obfuscation are going to be small, and the number of paths quite limited. However, very large monolithic executables are going to run into issues on how long it takes to fully map them. At that point, one just needs to ask themselves if they really need to fully map the obfuscated code, or if just certain well-used paths are good enough.

Re:Seems improbable

[SLi]

And how easy do you think watching in a debugger an interpreter execute a program is, even if nothing there is obfuscated?

Here, the interpreter is not obfuscated. You do not need to run it in a debugger, you can read the source code. But the program being interpreted is such that you can only deduce what it does to an input by running it on that input, and you gain no additional information of its workings.

Performance hit

[Pinhedd]

and programs will continue to run like it's 1987

A giant step backward for maintainability?

[__aaltlg1547]

Or is there an original unscrambled source code retained somewhere?

Too Slow

[Anonymous Coward]

From page 7 of the paper: "While our current obfuscation construction runs in polynomialtime, it is likely too inefficient for most practical problems. An important objective is to improve the efficiency for use in practical applications"

Re:Too Slow

[MightyMartian]

If crappy performance is no obstacle, I'm sure you could produce compiled code that is insanely obfuscated. Still, as I said elsewhere, if you can execute it, it can be executed in a debugger and you can watch what it does, and even if it's doing mad long jumps all over its allocated memory, you're going to be able to trace execution. It will betray its functionality.

Re:Too Slow

[Opportunist]

As if that has ever been a concern of software makers. "Our Software runs too slowly? Well, get a better machine, your ancient 1 year old crate of course cannot run our superspecialawesome piece of artificially deoptimized code".

The program will have to DO something

[Sean]

Call the kernel to access files, sockets, etc.

Also unless the developer is super 31337 and likes to write everything I expect shares library calls too.

By watching calls to those interfaces we can figure out what it does.

Re:The program will have to DO something

[MightyMartian]

Even if all the libraries are statically compiled, it's still going to be making system calls. Yes, it's behavior could be very hard to determine, but unless it's a standalone operating system that runs entirely on its own, it's going to be traceable. Even then, one could still run it in a VM. Perhaps harder to get useful information out of, but still...

Re:The program will have to DO something

[TheLink]

It could be a custom/modified cryptographic hash used to verify and create signatures. In which case it won't make that many syscalls.

Reverse engineering something like that will be hard if its obfuscated.

If you can't reverse engineer it you can't make a compatible version without breaking copyright by copying the hash module as is.

The original paper

[HatofPig]

The original paper is available here.

Cryptology ePrint Archive: Report 2013/451

Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits

Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters

Abstract: In this work, we study indistinguishability obfuscation and functional encryption for general circuits:

Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.

- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

Category / Keywords: public-key cryptography / Obfuscation, Functional Encryption, Multilinear Maps

Date: received 20 Jul 2013, last revised 21 Jul 2013

Contact author: amitsahai at gmail com

Available format(s): PDF | BibTeX Citation

Re:The original paper

[IamTheRealMike]

I already read the paper some days ago when it was first uploaded to the IACR pre-print archives. Yes, the paper is the one being referred to. It's a very interesting result, although not really impactful at the moment for things like game DRM.

The confusion arises from terminology. The technique applies (presently) to pure functions. You can write those functions in, for example, a subset of C because there exist compilers that transform such programs into boolean circuits, and circuit form is what they obfuscate. However it's rather rare to find examples of useful programs that are actually pure functions (compilers themselves being the most obvious one). Most programs have state, rather complex state at that.

Now there was also recently a paper that showed a way to build garbled circuits that had read/write access to a form of memory. If the two techniques can be combined then you're starting to see progress towards "real" obfuscation as used in industry.

If I can see everything, I win, if not, maybe not

[davidwr]

If the goal is to make it impractical for someone WITHOUT the ability to monitor the computer including the CPU "from the inside" they may be on to something.

If I can monitor the system at a level of detail where I understand what each "step" does, then I can just put the pieces together and I'll know what's going on. If I'm a debugger that can monitor the CPU and the rest of the system in a way that isn't visible to the code I'm trying to snoop on, it's pretty much game over, I win.

Here's where it gets interesting:

If two computers are collaborating on a task and I have debugger-access to one but I see the other as a "black box" you could design a system in which the fact that I have perfect knowledge of what is going on in computer A doesn't give me a huge amount of insight into what task the two computers are collaborating on and how they are doing it.

Re:Attack of the D-K Zombies

[Anubis IV]

So long as we're able to see the instructions being given to the processor (hint: we pretty much always can), you can reverse engineer the code. Performance penalties or not, the entire thing is pointless if it doesn't achieve what it's set out to do, and you don't have to be an expert in this area to see the hole that's big enough to steer a panamax-class cargo carrier through. Despite that, the problem went wholly unaddressed in the summary and I'm not seeing any comments here indicating otherwise, which means that the article isn't worth consideration except if I have some time to kill (I don't).

Wish I had thought of this myself

[vikingpower]

I just scanned the original paper, reserving its detailed lecture for another moment. But it is one of those things that make me think: "Damn ! Wish I had thought of this myself..."

Re:Wish I had thought of this myself

[vikingpower]

This reply is typical of a growing percentage of replies on /. : abuse & insults, under the cloak of Cowardness and Anonymity. Well done, I am impressed by how you immediately detected my grammatical error.

I regret to inform you, though, that the correct word for what you speculate me to be is dumbfuck

Re:Wish I had thought of this myself

[andy.ruddock]

At dictionary.com,

1. to glance at or over or read hastily: to scan a page.

And even if you had been correct, it was an unnecessarily harsh comment, but do please feel free to hide behind the mantle of the Anonymous Coward.

Just doesn't work...

[TiggertheMad]

Yeah I agree, there is something fundamentally wrong with the claims being made. If I have byte code, I can rebuild loops and conditionals with a decompiler. Sure, I don't have comments or var names, but those can be guessed or worked out in something less than 'several hundred years'.

Suppose you build something that throws in a lot of crazy random jmp calls to make this harder, and I cant be bothered to re-construct a program I want to steal. At some point a single Boolean decision hits the call stack that says, 'Is the app unlocked, yes or no?', and that conditional jmp can be replaced so it is cracked. Unless this guy has come up with a super magic method to keep me out of my own computer, I can crack whatever crackpot protection scheme he cooks up.

DRM doesn't work, on a theoretical level, because you cannot keep people from having access to the data at every single point in the delivery chain. Code is just data. So......QUACK QUACK QUACK.

Re:Just doesn't work...

[Anonymous Coward]

Suppose you build something that throws in a lot of crazy random jmp calls to make this harder, and I cant be bothered to re-construct a program I want to steal. At some point a single Boolean decision hits the call stack that says, 'Is the app unlocked, yes or no?', and that conditional jmp can be replaced so it is cracked.

Not necessarily.

Here's an example: You give the program some input (which includes the security key, as well as the input you're actually interested in). The program then does a whole bunch of computations! It crunches numbers and writes values in memory and in every register. By this point your original input is hopelessly munged. Now there's a conditional. If the conditional is false, the program says "I'm not unlocked" and fails. If it is true, it takes some of the values from memory and writes them to the screen with the message "This is the answer."

Great, so all you have to do is replace that conditional so it always evaluates to true, no? When you actually do this, the program happily writes an answer to the screen every time. The only problem is, if you provided an invalid security key at the beginning, the answer it writes is complete nonsense. You see, it's secretly already tested the security key, and if it was wrong, the answer ends up being wrong too.

Then you go back to try to figure out where it checked the security key. The problem is, it didn't do it in a transparent way. Instead, the security key and the user input are actually all mixed together in the algorithm. For example, the first thing it does is to take the last 32 bits of the security key and add that to the first 32 bits of the user input. Every step in the algorithm is like this, with the input and security key hopelessly mixed together, but it somehow works. That's the obfuscation.

As a result, your approach is stymied, unless you can actually understand how the algorithm works and disentangle the input from the security key.

Re:Just doesn't work...

[superwiz]

You are missing the point of code being data. What it means in this context is that there is a duality between functions and the data they operate on. In other words, you can think of data as operating on the code instead of code operating on data. So your data becomes your maps (in the mathematical sense of the word map) and your functions become the mapped objects.

Re:Just doesn't work...

[greg1104]

You're focused on a crack of one function in this sort of program. Given enough time, it is always possible to map all the inputs and outputs of a function, and therefore replace it with another that does the same thing--but with a change like a crack installed. The question, though, is how much time will it take?

There's not an easy to spot boolean on the line here; we're past when idiots built these things now. Let's say the output from the DRM checker is a 1024 bit key that unlocks the next function in the chain. It works right now; run it again and pseudo-random behavior means you'll get a different one. Saving the key itself will do you no good. To crack the program, you need to figure out how the DRM checker creates these 1024 keys from its inputs.

If that code is obfuscated enough, the only way to reverse engineer it is to use a "black box" approach. You inject all possible inputs, observe outputs, and then you know what the function does. The claim of the paper is that their way of constructing these functions means mapping all of the inputs and outputs well enough to duplicate the function can be made arbitrarily hard. Yes, you can do it. But if there are enough layers that all have to be carefully unwrapped function at a time, mapping all inputs and resulting outputs, that the time to do the work can be made a lot longer than people expect now.

Re:Just doesn't work...

[epine]

Great, so all you have to do is replace that conditional so it always evaluates to true, no? When you actually do this, the program happily writes an answer to the screen every time. The only problem is, if you provided an invalid security key at the beginning, the answer it writes is complete nonsense. You see, it's secretly already tested the security key, and if it was wrong, the answer ends up being wrong too.

I implemented exactly this circa 1990 to protect a small database of disambiguation rules structured as a hash table. A random value obtained from the security dongle was intermixed into the hash function and hash check condition. This was not done once for each possible lookup as defined in a conventional database. It was done once for each feasible answer for each possible lookup. The code had a statistical model of feasible answers. For some queries the number of feasible answers was excessive (too many dongle interactions) so we created a heuristic that was correct 99% of the time and set aside the 1% for a second pass with an additional data structure. If the dongle wasn't present the set of feasible answers was incorrectly narrowed with the expected statistical distribution. The members of that distribution, however, were entirely wrong.

We built up more complex queries from smaller queries. We were actually building a tree where every path in the tree was a valid answer and the majority of leaf nodes were at depths 2-4. That we hit a leaf node was a bit of metadata from the hash table lookup, which would be wrong if the dongle wasn't installed.

How about a quick forward description. Start with an alphabet of 50 symbols and construct the tree of all strings of length one to six. Every node in the tree has a flag about whether that node terminates a valid string and some additional bits about the correct orthography of the string as expressed in the user input, when typed. Your database is a subtree of this tree with about 100,000 strings (problems were so much smaller 25 years ago) along with a couple of bits of metadata per leaf. It's pretty sparse compared to the 15 billion possible leaf nodes.

The database subtree is actually constructed by elimination. One dongle assisted hash probe tells you whether a descending edge from your current vertex leads to a non-empty subtree (further solutions with your current path in the tree as a proper prefix). In addition, the user input defines another subtree of everything that could possibly matter to the conversion being performed. What you are computing is the intersection of these two subtrees: the tree corresponding to the task at hand and the tree corresponding to all solutions possible. Because the hash table was decomposed on the principles of minimum description length, when the dongle was absent (or corrupted) you still get an answer with much of the expected statistical distribution.

Except for one thing. The hash check was imperfect and you would get some false positives. We set up the rate of false positives so that the set of false positives grew exponentially as you descended to deeper levels. We knew from the statistical structure of the user input that few elements of this phantom solution set would interact negativity in practice even though the phantom set vastly out-numbered the legitimate set. Further, if one tried to enumerate the tree exhaustively using an incorrect dongle hash function, the tree you would reconstruct had no depth limit. It grew exponentially in size forever. We knew there was a depth limit when correctly probed, but this was nowhere expressed in our program code. In fact, this could be used to reverse engineer the correct hash function: only the correct hash function enumerates to a finite set of 100,000 subtrees. Just iterate over the set of all possible hash functions, in some well-structured enumeration order, until you discover this condition. Bingo, you're done.

Not all of the phantom space was harmless

Re:Just doesn't work...

[epine]

One extra detail: the alphabet of 50 characters was the effective entropy over a much larger space of symbols. I described the tree in entropy space, because that is the what mattered to its performance profile. The naive view is that the symbol set contained 8000 symbols and that four character strings could be selected from a set of 8000^4 members.

I ignored this detail because conventional reverse engineering would very quickly determine that we only go to the hash table for a much smaller nucleus of the problem space. That filter was a couple of pages of code. Nothing major, but not trivial to guess without some appropriate expertise.

Re:Just doesn't work...

[rgbatduke]

Wow, beautiful reply. The bottom line message for me was that it was a one-off, in a sense security by obscurity (or, as you put it, by expensive obfuscation), and that to make it work you had to hand code it at a key point in a suitable application. And it doesn't make functional reverse engineering more difficult (seeing what the application does and trying to duplicate it functionally), it just makes disassembling the code into semantically meaningful functional units that can similarly work together to accomplish the desired work considerably more difficult, for a value of considerably intended to discourage people who lack NSA-class resources and nothing better to do.

After all, even the use of the term "dongle" in your reply is telling -- none of this stuff has much of a lifetime. It isn't about making it impossible, it is about making it too difficult to accomplish (probably) without a big at-risk investment during the limited lifetime that the program has value, that dongles or parallel ports to attach them to exist, that a real competitor hasn't eaten your lunch in by simply producing a better program to do the same thing.

I also enjoyed your remarks on patents and emergent obviousness. However, I would note that in the case of many, many great ideas, they are obvious after somebody has the burst of insight and explains them. The entire structure of physical science comes to mind. While anybody could have invented calculus at any time over several thousand years, nobody did until Newton and/or Liebnitz did. Afterwards, sure, it is obvious, I can derive calculus in a few lines of work and then it is just a tedious matter of working out all of the completely inevitable consequences (not all of which are easy, at least until they are done and added to the list of no-longer-difficult obvious stuff). I still think that unique solutions to expensive problems deserve patent protection even though AFTER they are revealed people look at it and go "Gee, that's obvious, I could have done that."

So why didn't they?

Perhaps because it was not, in fact, all that obvious until the obvious solution was pointed out?

rgb

Re:Just doesn't work...

[mrego]

Either all code is actually functional, or it isn't. If it all is, then only the order of execution is obfuscated. If it all is not, then the obfuscation also comes from having a lot of extra code or monkey-puzzle which seems like the appropriate Ted Sturgeon word that comes to mind. (But you don't have to execute these sentences in this order.)

Re:Just doesn't work...

[TiggertheMad]

As a result, your approach is stymied, unless you can actually understand how the algorithm works and disentangle the input from the security key.

But I can look at they byte code and see exactly what is being done at each step of the process. I can read the buffers. Basically, you are just replacing 'if (password_correct == true)' with 'if (password_hash & xff0a key_buff[x0012] * get_hash_rotation(user.id))' or something similar. obfuscation != security.

Re:Just doesn't work...

[TiggertheMad]

First, that was a very interesting post about your project. Thanks for taking the time to talk about it.

If I were to take a crack at breaking your elaborate security precautions, I would take a look at your dongle. Ultimately, anytime you are using a hardware key in software, you are just creating a second vector of attack or shifting the weak point in your software security from software to hardware. Your random seeds aren't likely as random as you think, as true RNG is kind of a tricky business.

In the end, either my machine can or cannot understand your code. If it can, it can be hacked.

Re:Attack of the D-K Zombies

[Anonymous Coward]

[T]he article isn't worth consideration except if I have some time to kill (I don't).

TL;DR therefore you are able to dismiss it out of hand. Gotcha.

I'm not seeing any comments here indicating otherwise

Now why do you think might that be? I believe you are telling the truth. You really haven't looked at the actual paper.

Any assembly encryption can be broken in 5 minutes

[nomaddamon]

You run the executable...
You ask kernel to stop executing it...
You dump the memory...
Voila - you have the unencrypted executable...
This process, including writing the tools for it, will take a person who knows what hes doing around 5 minutes... (if the program is large, it might take longer due to disk write speeds)...

Yes, they can obfuscate the assembly, but it still will be the assembly - perfectly human readable.
It might be pain to reverse engineer the whole program, but it can be done. But in most cases I've seen the hacker doesn't want to reverse engineer the whole program, he just wants to alter it a little / extract some crucial information from it (i.e. private keys). Obfuscation doesn't make this harder at all - You find some interesting OS level calls (i.e. socket creation - you cant obfuscate that...) and using debugger/stack traces/assembly/hooks you poke around a bit to find the part that is interesting to you...

From security point of view, assembly encryption (no matter how good it is) is comparable to covering your house with packing paper to prevent thieves from entering...

like DVDs and all the others

[raymorris]

encryption used for DVDs was believed to be unbreakable, until it was broken. How many companies have released encryption schemes, for DRM or otherwise and it gets cracked within hours of actual release. more than once Microsoft encryption has been cracked before its official release.

    Though I haven't studied this particular one, my general impression is that it was not designed by cryptography experts and then vetted the way well known cryptographic algorithms are vetted by other experts.

Re:like DVDs and all the others

[Meneth]

Aye, it's easy to construct an encryption scheme that you yourself can't break.

Re:like DVDs and all the others

[IamTheRealMike]

Actually the encryption itself on these schemes was not broken. Rather, player emulators became good enough that the industry could not revoke hacked players fast enough to keep up.

Another small step?

[EzInKy]

Eventually those who don't understand maths will be freed of being slaves to those that do. Could this be the first step?

This actually has a name.

[eclectro]

It's called Forth

Re:Attack of the D-K Zombies

[Anonymous Coward]

Still doesn't change the fact ...

You assume it's a fact. When I was reading science at university (late 70s/early 80s) a fact one of my lecturers impressed upon us was that it would never be possible for computers ever to decipher handwriting or even in anything other than rigorously standardised print, because we all wrote letter ever so slight differently.

The claim here is that there is a way to fool a decompiler and still have a functionally useful program. And the paper will show you how. You can refute it all of course, all you need do is to show us the maths.

What this means. I think.

[Animats]

This is fascinating, but hard to understand. It's not clear how broad a result this is.

This seems to apply to "circuits", which are loop-free arrangements of AND, OR and NOT gates. These take in some bit string with a fixed number of bits and emit another bit string with a fixed (but possibly different) number of bits. Many computations can be encoded into this form, but the "circuits" are typically very deep, since this is sort of like loop unwinding. Although this seems kind of limited, you could, for example, make a reasonably sized "circuit" to compute DES, which is a static pattern of Boolean operations.

"Obfuscation" here means taking in some "circuit" and producing a bit for bit equivalent "circuit" from which little information can be extracted. The obfuscated circuit may be (will be?) more complex than the original, because additional logic has been inserted in a somewhat random way.

The contribution in this paper seems to be that this might be useful for "functional encryption". This is where you have some values, such as A and B, which are encrypted and are to be protected, but the result of some function f(A,B) is not protected. The idea is to have an implementation of f which combines the decryption and the desired function, an implementation which cannot be reverse engineered to return decrypted versions of A or B. While this has been suggested as a possible feature for databases, it's hard to apply to useful functions, and so far, it's mostly a research idea there. It's been suggested for some complex access control schemes involving mutual mistrust, but that too is a research topic.

Anyway, this doesn't mean you're going to be able to run your big executable program through some kind of magic obfuscator that will prevent someone from figuring out how it works. Not yet, anyway.

Other aspects of the paper - health data

[Badge 17]

I can't really comment on the slashdot summary, but take a look at the actual abstract: http://eprint.iacr.org/2013/451

"In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually."

In other words, it seems that their technique allows you to encrypt some secret data, then (provably) only release the result of some arbitrary function of that data. It sounds like this means you could (in principle) release health data in encrypted form, then allow researchers to study some ensemble properties of it by giving out the appropriate keys. This aspect of it certainly seems pretty cool.

I don't Think That's The Point

[The Real Nem]

You don't need to emulate the hardware to see a program's output, you can just look at your screen. There is little point in hiding the output of a program from the user who's running it so I don't see that as the point (if one cannot observe the output of a program, it is of little utility).

Which instructions a given program executes depends on the inputs to said program. For any given input, most programs only execute a tiny portion of their code. Therefore, in order to completely reverse engineer a program, you would have to observe the output for all possible inputs. This is almost certainly intractable for any sufficiently complex program. Suppose you wrote a program to iterate over all possible inputs observing the output of each input; things get interesting if you liken this to the halting problem.

Re:I don't Think That's The Point

[wierd_w]

Agreed, for each nested brach, complexity increases at LEAST geometrically. (A branch always has at least 2 paths.) However, one may not NEED to know *all* branches.

Say for instance, the behavior you want to modify (we will assume you are a cracker making a memory poking drm defeat patch) is rigidly defined in where it gets called from (by this, I mean what code branches spawn the check). You don't really need to look at the other execution paths, just the ones that trigger the drm check, or better still, the check routine itself that gets called. Having execution jump all over the damned place instead of having it be nice and orderly in memory is basically the "spaghetti code" problem. Its just a bunch of jumps, with (*apparently) no rational scheme behind them.

The program itself needs to reliably know where to jump to, and what (*random) addresses to read and write to. Making a "complex" program be able to have a new "scatter" pattern on each fresh execution still requires a fixed entrypoint to decide which scatter pattern to use, and what data to poke after the scattering so that the code can still execute. This presents a point of attack. It also runs foul of the same complexity problem it attempts to present to the cracker; the more potential scatter patterns, the larger the scattering routine, the harder it is for it to poke all the right spots after the scattering to update all the jump instruction and data read/write addresses. Especially if it attemps to scatter its own data as well.

This is because such scattering has to be done intelligently, otherwise performance of execution will drop like a lead brick on jupiter. Say for instance, it does really dumb scattering, and scatters data for a 64bit unsigned integer as 8 addresses, each of 1 byte length, in a seemingly random jumble in the allocated memory image. Instead of 1 64bit linear read, or 2 sequential 32bit reads, it has to do 8 random 8 bit reads, AND process jump instructions injected by the scrambler, before it can actually perform the computation with that integer. The more complex the program scrambled, and the more complex the scrambler used, the greater the performance penalty will be. This places a hard upper bound on the hardness this approach can give the cracker.

misunderstanding

[Anonymous Coward]

either you misunderstand or i do, but my understanding was that this system allows a function to be expressed so that the code will only execute with certain parameters, hence the function can only compute certain evaluations (lets say one for simplicity) of the original function, and the true function can be hidden. so that the function evaluated for other parameters cannot be computed with this expression.

basically a really complex way of designing a look up table ?

now as you say, you can never hide the value of the function evaluated at the parameters for allowable parameters, because you can stick it in an emulator but the emulator tells you nothing more about the function and so you might as well just 'run' the whole procedure cause you cant extract anything other than the answer, to the function evaluated at a predetermined set of values.

this is achieved by making the original universal (or with domain expanded over the single or fixed set or parameters) algorithm into the 'jigsaw' that will only assemble with the particular parameters which are 'allowed', as these parameters direct the fitting of the jigsaw.

so can the jigsaw be fit with the 'allowed' parameters and still evaluate the original algorithm for different values? i believe the point of the algorithm is to achieve the same result as a look up table, and if it doesnt do it more efficiently then there is no point to the algorithm.

Re:misunderstanding

[Teancum]

The problem is that those parameters and bounds checkers must also be in the software, hence it still can be identified and reverse engineered.

It still gets to the issue that if software can execute, it can be reverse engineered. It may be more complex than sticking a Java .jar file into a decompiler (quite easy to do), but you still need to have *something* read that software in order to operate.

Hardware enforced encryption, in other words something built into the CPU itself, is a bit harder to work with but even that can be reverse engineered. It just takes moving deeper into the system.

Frankly this kind of arms race for hiding software was something I thought was long dead, but I guess I'm mistaken on that too. It is futile as you spend far more time as a developer trying to come up with more interesting puzzles for those who want to reverse engineer your work. if anything, it becomes an intellectual game unto itself where you are just feeding would-be hackers with fun and a challenge. I completely agree with the GP post that called this whole thing BS, other than it just obfuscates everything to another level.

For any software worth running at all, it is worth hiring a team of software engineers to reverse engineer that software to figure out how things were done. If you want to protect your software from duplication, it is by far easier to simply use a team of lawyers and fight over copyright infringement instead. Either that or simply out-innovate your competition... which means you have your developers doing stuff they are really good at doing and don't bother wasting your resources on obfuscation crap like this.

Sometimes I just hate researchers

[maroberts]

You just know that some crack DRM whore like UBISoft will incorporate this as part of their next game release.

Nice try

[superwiz]

But UCLA doesn't get to claim the credit. MIT was first to present homomorphic encryption: http://web.mit.edu/newsoffice/2013/algorithm-solves-homomorphic-encryption-problem-0610.html

Roughly speaking, homomorphism is a map which preservers the properties pertinent to a category. Now think of data as acting on code instead of code acting on data. Since "acting" is a mapping, acting in a homomorphic way would produce program results which are equivalent but without the decrypting step.

is it helpful?

[stephendavion]

can any explain how exactly this will be helpful ....

Hurry up, Europe is hungry for your fines

[c0lo]

Sell a program protected like this in Europe and you may end paying hundreds of millions:

(14) A person having a right to use a computer program should not be prevented from performing acts necessary to observe, study or test the functioning of the program, provided that those acts do not infringe the copyright in the program.

(15) [...]Nevertheless, circumstances may exist when such a reproduction of the code and translation of its form are indispensable to obtain the necessary information to achieve the interoperability of an independently created program with other programs.
It has therefore to be considered that, in these limited circumstances only, performance of the acts of reproduction and translation by or on behalf of a person having a right to use a copy of the program is legitimate and compatible with fair practice and must therefore be deemed not to require the authorisation of the rightholder. An objective of this exception is to make it possible to connect all components of a computer system, including those of different manufacturers, so that they can work together. [...].

Re:Hurry up, Europe is hungry for your fines

[Impy the Impiuos Imp]

But you're not being prevented from observing the functionality of the program. Indeed, this design presumes it.

Re:Hurry up, Europe is hungry for your fines

[IamTheRealMike]

Your story about paying fines is not related to your first link at all. That's quite deceptive, I must say.

Re:Hurry up, Europe is hungry for your fines

[c0lo]

But you're not being prevented from observing the functionality of the program. Indeed, this design presumes it.

Except the directive uses the functioning not the functionality. Indeed, for the purpose of integration, one absolutely needs the how it does details (i.e. functioning) rather than the what it does (functionality).

Re:Hurry up, Europe is hungry for your fines

[c0lo]

Your story about paying fines is not related to your first link at all.

My story about fines demonstrates Europe is not shy to impose them, even on more unsubstantial grounds.

That's quite deceptive, I must say.

My apologies, but I'm afraid your compulsion (of saying something) is not quite my fault.

Malware in 3, 2, 1...

[Opportunist]

Remember, kids, everything that can be applied for good can be applied for ill. And code that is impossible to decipher and analyze is the holy grail of malware.

Re:zOMG I r a 133t haX0r

[Opportunist]

Well, DUH!

Be honest. Imagine you have something like that. Where would you present it?

At a tech conference, where techs are present who can't throw money at you but can crack it?
Or at a management conference where the second part of the above statement is inverted?

Re:Attack of the D-K Zombies

[TheLink]

OK as an example what if you have worked out a way to transform an arbitrary program in to a huge bunch of "if else", goto statements with "magic numbers" or worse (e.g.
setaddress(mod(magic1+sha256memoizer(magic2+parm1+parm2+...),dataend))=parm3;
linenumber=mod(magic3+sha256memoizer(magic4+parm5+parm6+...),maxlines);
goto linenumber;
) and some stores and loads so that it's still equivalent and does the same thing but just a bit slower. So when you disassemble it - it's still a big mess that makes it hard to figure out or "improve" - which is the whole purpose of at least some code obfuscation.

So perhaps this bunch have figured out how to do something like this (and maybe better).

Or maybe they're just converting the program to encrypted perl and then compiling it to run on a custom vm ;). Just because you can see the final instructions doesn't mean you'd be much closer to figuring out the code.

For example if someone made a new cryptographic hash function and obfuscates it in one of the ways I mentioned. Would it really be so easy to reverse engineer it, just by seeing the instructions given to the processor? I don't think it would be so simple. More so if you need to reverse engineer it to the extent that you can write a detailed enough description and specification so that someone else could create a clean room implementation.

Encrypting the algorithm, not the code?

[Kazoo the Clown]

It sounds like what they are trying to do here is to refactor the algorythm such that f(x)=y produces the same answer but it's not practical to modify because the new function is mathematically scrambled-- the effect of each component of the code is so obscured that it's not so easy to tell how it contributes to the results. It's like using a neural net to implement your solution, the contribution of each neural node to the overall result can be significantly obscure. Won't stop someone from stealing the algorythm as is, but hacking it to produce an alternate result set will be out of the question, as long as they can't just build a truth table of inputs to outputs...

Re:Attack of the D-K Zombies

[Dunbal]

I call BS on the notion that my CPU is smarter than me. Article claims that it takes "hundreds of years" to break this. Obviously then it must take the program "hundreds of years" to run. Otherwise the CPU is using a short-cut. All I have to do is figure out what the short cut is (hint: figure out what the CPU is doing, where it got its instructions from) and it's cracked. If your computer can run it, you can figure it out. It's that simple.

Re:ROFL!

[Dunbal]

I give it a month before someone cracks it.

So....

[zwarte piet]

Where can we buy/download the package?

Re:Attack of the D-K Zombies

[Half-pint HAL]

So long as we're able to see the instructions being given to the processor (hint: we pretty much always can), you can reverse engineer the code.

True. As long as you are able to follow every possible path of execution of the code. Which puts us in the realms of "theoretically possible, but unfeasible in practice".

How do we normally reverse engineer code? We run the code through a debugger/logger to identify contiguous areas of code and data, and to highlight common destination points for branch conditions and data addresses frequently read from/written to. That information is used to inform the automated stages of disassembly. Probablistic models see something that looks like a branch to a common destination, and assume that it is one. They see what looks like a write to a common destination and assume it is one. Encrypt your addresses and hash them to appear different and the hints are removed from the object code, and only identifiable during execution or simulated execution, which brings us back to unfeasible-in-practice exhaustive execution.

Re:Attack of the D-K Zombies

[Half-pint HAL]

I call BS on the notion that my CPU is smarter than me. Article claims that it takes "hundreds of years" to break this. Obviously then it must take the program "hundreds of years" to run. Otherwise the CPU is using a short-cut. All I have to do is figure out what the short cut is (hint: figure out what the CPU is doing, where it got its instructions from) and it's cracked. If your computer can run it, you can figure it out. It's that simple.

By this argument, PGP, RSA et al must be worthless too, because if it takes hundreds of years to break a 256-bit cypher it must take hundreds of years to run a 256-bit cypher. You know, if your computer can run it, you can figure it out.

I hope you can see the flaw in your argument now.

Re:Attack of the D-K Zombies

[somersault]

You're claiming to be able to reverse engineer an entire cookbook just by chemically analysing a cookie from one recipe in that book. You'd have to make every single recipe in the book and analyse it before you had a complete representation of all the recipes.

Re:Attack of the D-K Zombies

[gl4ss]

yeah well release a working proof and make 5 billions.

I'm not shitting you, if you can really do even a simple proof of concept that does that then you could bag a lot of money next week.

I can accept that you could do it this system so that it will spit out right answers for right predetermined inputs but nothing else, and even then you could see it do it's thing with that input while it might not provide you the outputs for other inputs, but that's pointless as a program for most any uses a computer program has, except as for hiding data.

it's an extraordinary claim so it needs quite ordinary proof: a regular fucking program that implements the method. conceptually the method should work with any language anyways, so might just as well be in basic.

Re:Attack of the D-K Zombies

[Anonymous Coward]

The obivious difference between the obfuscated code and an an PGP-Message is that in the PGP case you need a key to decrypt it.
Unless they have a secret key baked into the CPU there is no advantage for the CPU whatsoever ...

Re:Attack of the D-K Zombies

[Half-pint HAL]

How is this different? The public key for a machine-readable PGP message isn't "baked into the CPU", but that doesn't make PGP trivially easy to break -- far from it.

Re:Prior Art

[vikingpower]

I do see major difference. The patent you cite is based upon DES, the authors' work is not, as they develop their own encoding technique, on the basis of multilinear maps. Moreover, in the patent you cite it is assumed that one function can have n outputs, whereas in the authors' work, each function has only 1 output. I am still going over both the original peer-reviewed paper and the US patent you cite. The latter seems too amateuristic to be taken seriously by any corporation willing to implement an obfuscator, whereas the authors of this paper are researchers renowned in their field.

Poor RTFA

[ThePhilips]

RTFA is shallow on details, but it sounds very much like the "phantom" self-mutating MS-DOS viruses from the later 90. (The ones which forced anti-virus vendors to effectively implement a debugger/a interpreter for the code to detect the malicious code not by the look but by the actual work it does.)

Otherwise, the main problems with such intrusive obfuscations is that code is never 100% bug free and bugs sometimes trigger undefined/unspecified behaviors. It might work before obfuscation - but would break (in unexplainable, obfuscated fashion) afterwards. (Ditto after system updates.)

Remionds me of some older compression software

[MWagman]

Back in the days OS's ran off of floppies (Amiga OS for example) there were programs that would compress an executable to save space. This made me think of that using encryption instead. Now in that case on 7Mhz machines. The speed of decompression in that case was close to the time saved by loading less data from the floppy drive. Now with Ghz of speed instead of Mhz and it needing to be run once, I am not convinced the speed loss would be that great. However with VM's and the like it's too easy to stop and look at the executable that way - nothing can stop that.

Re:Attack of the D-K Zombies

[Dunbal]

Besides, the NSA is holding all the keys anyway lol.

Re:Attack of the D-K Zombies

[stdarg]

No, what you're describing is looking at a finished product and inferring the process of how it was created. That's very difficult.

What GP is referring to is watching someone follow the recipe (without seeing the recipe itself), and then inferring the recipe. Much easier.

Re:Attack of the D-K Zombies

[stdarg]

By GP's argument, for the CPU to decrypt the message so quickly, it must be using a shortcut. In your example, the shortcut is that the CPU knows the secret key.

Do you honestly think that someone watching the CPU decrypt the message can't access the message themselves? http://en.wikipedia.org/wiki/DeCSS

This is poorly described, but is a breakthrough

[Wierdy1024]

Normally obfuscation is bad in cryptography - it means that the system is theoretically broken, but that the way to break it is quite well hidden.

This refers to cryptographically secure obfuscation. This is an entirely new field, and hasn't been possible till now. This paper doesn't prove how to do it, but proves that it is possible for a certain subset of operations.

Basicly it boils down to the fact it is possible to make a computer program that, for a given set of inputs a) generates a set of outputs b) in such a way that it wouldn't be possible to modify the program to make it generate a particular output without doing an exhaustive search (ie. try every possible input).

It's similar in principle to a "designer" hash algorithm - ie. I can choose the output for a given input, but after compilation it will not be possible to find out the mapping without knowing the input.

This type of algorithm could enable things people hate (DRM), but also many other new fields of computing, in particular doing computation on untrusted processors.

Re:Attack of the D-K Zombies

[Kielistic]

The difference is that I can very easily decrypt PGP myself which is why people are saying these claims aren't true.

I'll bet

[Iridium_Hack]

It runs slower.

Re:Attack of the D-K Zombies

[SQLGuru]

In the case of PGP / RSA / etc, but short cut is the key. If the CPU can decrypt the message, it has the decryption key.....and therefore, you can obtain the key and have the same shortcut.....and thus, decrypt the message in a lot less than "years".

The problem you present is trying to break encryption without the shortcut.....or trying to put together the jigsaw by looking at the backs.

Re:Logic Analyzer on CPU pins

[Morpf]

Yes, for example caches. ;) I think one would more likely run this software on a vm and log syscalls, maybe even inspect registers.

Yay Progress!

[Sloppy]

Finally. People have been asking for years for software to become even harder to maintain and debug. For too long, we have tolerated too-high quality and reliability, too-low prices, and projects completing absurdly ahead of deadline. I'm glad to see that someone is finally doing something about it.

Unnecessary?

[ilsaloving]

All you have to do is outsource your project to India. The code you'll get back will be virtually indecipherable already.

Re:Attack of the D-K Zombies

[Half-pint HAL]

You might want to think about that again. That I can decrypt a specific message using a public key doesn't mean I have full unfettered access to the cryptosystem. You have to think of execution as communicating withe the program, and therefore think of the version the program executed as a chain of non-independant messages, and I can only decrypt them in the context established by earlier ones.

Either that, or some anonymous coward on slashdot has once again managed to see the "obvious" flaw in rigorously-researched and peer-reviewed cutting-edge advanced information theory that a bunch of mutiple-PhDs have been studying in-depth for years...

Re:Attack of the D-K Zombies

[Half-pint HAL]

But we're not trying to "decrypt a message", but to "break the cipher".

Re:Attack of the D-K Zombies

[Half-pint HAL]

"decrypt" != "break encryption"

Re:Attack of the D-K Zombies

[pipatron]

You only need to trace whatever you're interested in. If someone releases a revolutionary video coder encrypted with this algorithm, you run it through your tracer, record (and compress!) the raw instruction stream, and you'll have the actual algorithm that the CPU is executing. You're not going to decode all possible failure modes, nor any code that isn't actually executed, but you will get the algorithm that just encoded your video. The compression might even get you individual subroutines..

But it won't be pretty. :)

Well

[GigaBurglar]

I can see the advantages but I can also see great disadvantages - mainly copyrights and being locked out of your own system.

Eyes Rooling Upward

[LifesABeach]

Great! Another genius harvested from a dead culture screaming, "eureka!" OK, without wining, how is this going to:
fix my tractor?
food?
cure some, currently, uncurable illness?
put a new roof on my home?
clothing?

No comment? I figured as much.

Numbers to think about

[John Allsup]

Number of (behaviorally distinct) programs possible in X Kb of machine code.  Number of intelligibly represented programs using a comparable amount of source code in a typical C like language.  I suspect the former is much greater than the latter, and this can be exploited for the purpose of creating a program that works but is hard to reverse engineer.

Another thing to think about is various notions of approximation.  If only a small number of inputs to a function are actually used, and this set of inputs can be mathematically determined, then the function can be replaced with something weird which gives the right output on desired inputs but various other stuff for other inputs.  If an attacker cannot determine the actual inputs used, the function when analysed will look confusing.

Re:Attack of the D-K Zombies

[TemporalBeing]

OK as an example what if you have worked out a way to transform an arbitrary program in to a huge bunch of "if else", goto statements with "magic numbers" or worse (e.g. setaddress(mod(magic1+sha256memoizer(magic2+parm1+parm2+...),dataend))=parm3; linenumber=mod(magic3+sha256memoizer(magic4+parm5+parm6+...),maxlines); goto linenumber; ) and some stores and loads so that it's still equivalent and does the same thing but just a bit slower. So when you disassemble it - it's still a big mess that makes it hard to figure out or "improve" - which is the whole purpose of at least some code obfuscation.

All this means is that someone will then write a program that will work with a virtualized environment (e.g VMware, VirtualBox, etc) - may be even a device driver that snoops memory - that will be able to capture the run of the program and recypher it to the original, non-obfuscated code during run-time. They'll then use that in order to reverse engineer the program, reapply the cypher and continue on their merry way of hacking the software in the way the TFA's author is trying to prevent.

Now, given the amount of time it would take for the obfuscated program to run in the manner you are speaking, the aforementioned cracking software probably has plenty of CPU cycles to figure out each step and generate an intercept function to overcome the jigsaw obfuscation.

In then end, it just means the cracking tools become better.

Very limited scope...

[slew]

Just skimmed the paper...

The scope of this is very limited. It applies primarily to functions that encapsulate a secret (not a general piece of code). From reading the paper, it appears that the goal is to attempt to frustrate folks that that want to disassemble software routines to look for small secrets buried in the code.

Example: Let's say you have a function that decrypts a message from a server with a key and you want to say embed that code in javascript. You don't, however, want someone figure out the key by just looking at the javascript, you want it to be a black box.

This technique allegedly can obfuscate the code so that it is just as hard to figure out how the secret is used as it is to infer the secret from sending in values and building a lookup table. Of course you could just cut-out the obfuscated code and use it as an oracle (because you can still run it), but it continues to effectively hide the secret as best as possible.

As I understand it, the basic techique is to create a function (from a class of functions with certain properties) that cuts the input domain into a large number sets and for each set finds a cheap multi-linear function that maps the correct output values for that small set of the input values but is don't care for the rest of the input values. The "trick" is that the class functions that cut the input domain are not fixed, but depend on the input so it is a hard problem to figure out which maps are used without just searching them all. Thus every obfucation instance of a function that encapsulates the same secret could look different and still compute the same result, or conversely, encapsulate different secrets, yet look very similar, but produce the correct result.

The downside of course is that small multi-linear functions aren't the best implementation for actual encryption functions. For example, something very simple like 128-bit AES, might be considered a function with 2^128 entry 128bit table. Unless I'm mistaken, it will be very hard to chop up a 2^128 bit table using their method (even the authors concede the fact that thier construction isn't efficient enough for practical problems).

However, they make a "bold" assertion, that they can apply their technique to stuff like crippleware by obfuscating the function that enables/disables various program features. I'll go out on a limb and say most folks that hack stuff like that don't bother to figure out ways to turn on/off features, but just go for attempting to bypass calls to such a function or disable the function altogether.

The other "bold" assertion they make is that it might be used by software vendors to deploy a patch without tipping off the black-hats about the nature of the vunerablity before all systems can be patched. This is wishful thinking as functions are generally not vunerable (since they by definiton have no-side effects), but procedures (the function-like modules that render side-effects) are the modules that tend to have the bugs. This technique of theirs really only applies to functions, not procedures so it's hard to see how this would help in many circumstances.

Re:Attack of the D-K Zombies

[TheLink]

that will be able to capture the run of the program and recypher it to the original, non-obfuscated code during run-time.

Assuming "full" obfuscation if you do that you'd only capture the "program" for generating that one hash alone - one input and its corresponding output. The path would be different for different data/inputs. For a 256 bit hash you'd have to run it 2^256 times.

Of course there might not be full obfuscation. But I see no evidence so far that full obfuscation would be impossible or that difficult. Maybe someone could prove it impractical.

Re:Attack of the D-K Zombies

[TemporalBeing]

that will be able to capture the run of the program and recypher it to the original, non-obfuscated code during run-time.

Assuming "full" obfuscation if you do that you'd only capture the "program" for generating that one hash alone - one input and its corresponding output. The path would be different for different data/inputs. For a 256 bit hash you'd have to run it 2^256 times.

Of course there might not be full obfuscation. But I see no evidence so far that full obfuscation would be impossible or that difficult. Maybe someone could prove it impractical.

If the point is to merely obfuscate the program and not allow the user to actually run it, then yes you'd be right. That would also be pretty useless.

If the point is to run the program, then you are wrong as the program that must be run must at some point pass through the CPU to do its function. A capture program would be capturing the data as well, and would be able to note what portions of memory were being read/written/manipulated as well, so you'd also capture the any changes that temporarily decoded a section of memory, then executed that block before re-encoding it.

What you reference only works for encrypt/decrypt. However, between those two points something else has to happen - a portion of the real program has to run. The cracking program only needs to decipher where the boundaries between the encryption/decryption are so as to capture the exposed real program while it is operating - which has to happen for the user to actually be able to use the program, and monitoring the CPU instructions and cache would prove to be a very effective and efficient way to do it - e.g. they may be relying on tricks in the CPU to mask instructions before running them - e.g. XOR/AND/NOT etc - whereby it stays in the CPU cache only - however, even that is fully capturable by the kind of program/cracking I'm specifying be run in conjuction with a virtualized environment.

In other words, as I and many others have pointed out, as long as the program - not the obfuscator - actually has to run through some kind of execution unit, it can be captured. If it doesn't, then it's no better than putting a program into a ZIP file and saying is obfuscated.

Re:Attack of the D-K Zombies

[Kielistic]

That's an entirely useless statement in this context. If the intention is to keep the data out of the hands of the end user then it doesn't matter if they decrypt "as the designer intended" and snoop the data or if they break the encryption algorithm. There is still a failure in the process.

Re:Attack of the D-K Zombies

[TheLink]

You seem to be assuming a naive method of obfuscation. In theory you can obfuscate a program so there is no single "exposed real program" with just a few possible paths. There would be an exposed obfuscated program with say 2^256 possible different paths depending on your inputs.

Capturing one run will give you a different sequence of instructions from capturing another run, and each run the instructions you capture will only work for a particular set of inputs and state.

If you are copying the entire obfuscated program to support those 2^256 different paths you're not reverse engineering it.

To give an example to help make it clearer imagine converting a function to one that has zillions of "if then else" statements. The path and sequence of instructions will be different depending on what the parameters and state are. Figuring out the "real" source function from those statements would be tricky if it is a nontrivial function.

A real obfuscated program probably won't have zillions of statements - it's just an example to try to help you understand.

As for saying it only works of encrypt/decrypt, such obfuscation in conjunction with copyright law is good enough for preventing unauthorized 3rd party clients/software from interoperating with your products. If the only way they can create or verify signed messages to/from your services/other software is by copying your obfuscated signing module then they breach copyright law.

Maybe some countries have laws making it illegal to do such obfuscation to prevent interoperability, but not all of them.

Re:Attack of the D-K Zombies

[TemporalBeing]

As for saying it only works of encrypt/decrypt, such obfuscation in conjunction with copyright law is good enough for preventing unauthorized 3rd party clients/software from interoperating with your products. If the only way they can create or verify signed messages to/from your services/other software is by copying your obfuscated signing module then they breach copyright law.

Interoperability is a recognized reason by US Copyright Law for reverse engineering, no matter how much obfuscation or encyprtion is done.