Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Computer Scientists Develop 'Mathematical Jigsaw Puzzles' To Encrypt Software

samzenpus posted about a year ago | from the looking-for-edges dept.

Software 245

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.'"

Sorry! There are no comments related to the filter you selected.

I Call BS (5, Insightful)

MightyMartian (840721) | about a year ago | (#44443399)

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 (1)

noh8rz10 (2716597) | about a year ago | (#44443415)

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 (4, Insightful)

MightyMartian (840721) | about a year ago | (#44443459)

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 (4, Informative)

0123456 (636235) | about a year ago | (#44443493)

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 (1)

MightyMartian (840721) | about a year ago | (#44443515)

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

Re:I Call BS (1)

ls671 (1122017) | about a year ago | (#44443649)

Cause the game detects it runs in a VM?

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

Re:I Call BS (4, Insightful)

MightyMartian (840721) | about a year ago | (#44443757)

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 (0)

Anonymous Coward | about a year ago | (#44443753)

There are many tricks to detect you're inside a debugger. If the cracker knows the tricks he can bypass them, though (obviously, as otherwise they wouldn't be able to crack games so quickly).

Re:I Call BS (2)

Darinbob (1142669) | about a year ago | (#44443539)

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 (3, Insightful)

MikeBabcock (65886) | about a year ago | (#44443823)

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 (5, Interesting)

Anonymous Coward | about a year ago | (#44443567)

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.

misunderstanding (3, Interesting)

Anonymous Coward | about a year ago | (#44443995)

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:I Call BS (1)

shentino (1139071) | about a year ago | (#44443477)

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.

Attack of the D-K Zombies (0)

Anonymous Coward | about a year ago | (#44443571)

I call BS on the notion that you have already read and digested TFP [iacr.org] and are in a position to make anything close to an informed comment about the methodology proposed. In particular you seem to be completely unaware that your concern about performance penalties is specifically addressed.

Re:Attack of the D-K Zombies (1)

Anubis IV (1279820) | about a year ago | (#44443631)

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

Re:Attack of the D-K Zombies (1)

Anonymous Coward | about a year ago | (#44443705)

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

Re:Attack of the D-K Zombies (0)

Anonymous Coward | about a year ago | (#44443797)

Still doesn't change the fact that there is no way you can fool a debugger but yet still have a functionally useful program.

Re:Attack of the D-K Zombies (1)

Anonymous Coward | about a year ago | (#44443857)

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.

Re:Attack of the D-K Zombies (0)

Anonymous Coward | about a year ago | (#44443889)

Show me the maths? There isn't even a working concept of this. So me a so-called example and I'll tell you what that program is doing and how it works. There is no such thing as a program that does X but can't be observed doing so.

Re:Attack of the D-K Zombies (0)

Anonymous Coward | about a year ago | (#44444007)

sorry for the double posting, but i wanted to put this in opposition to your claim that emulation can 'extract the secret of the original algorithm'

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.

ask the oracle (0)

Anonymous Coward | about a year ago | (#44444065)

now ive thought a little more and basically everything on the continuum, from a complete look-up-table which can describe all functions on the given domain to the constant function, is probably most efficiently described with some form of hash function.

so, by replacing all software with octaves of hash functions :), we retain some involutional or evolutional control ?

as a defense against allowing our 'original algorithm' to be reverse engineered we can even intentionally obfuscate, if there is some purpose, and bulk up the original algorithm arbitrarily. the reverse engineer can never determine if this bulk is actually necessary, or if he would more properly use a look up table which gives no information just like a one time pad. one issue is that most currently used forms of coded forms of algorthms do not include a specification of their proper domain.

for eg. take the code for the gamma function on some universal turing machine, replacing it with an arbitrary or obfuscated code can never retain the infinite generating capability of the original gamma function and also remain obfuscated.

but at how many values do you have to check a function to know if it is actually the gamma function or not?

this may come down to the study of algorithms that use an oracle to classify a given function as say balanced or fixed. if humans are quantum computers then perhaps we use a similar advantageous algorithm to assess other infinite valued functions such as the complete state of a point in hilbert space. might even underlie concepts such as reflection, and identity.

the quantum spin statistics theorem relates the integer or half integer spin, fermions or bosons, and this relates to the two solutions of the quadratic application of the exchange operator.

see david deutsch.

Re:I Call BS (4, Informative)

phantomfive (622387) | about a year ago | (#44443599)

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 (0)

Anonymous Coward | about a year ago | (#44443827)

At what level of granularity is the obfuscation taking place? 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.

Give up. It's futile.

Captcha: alcove

Re:I Call BS (1)

Anonymous Coward | about a year ago | (#44443629)

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 (2)

MightyMartian (840721) | about a year ago | (#44443695)

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

reread it (0)

Anonymous Coward | about a year ago | (#44444073)

The only thing you can do with it is put it together the way that it was meant to interlock

yes an emulator can evaluate the obfuscated algorithm for a fixed input. might as well be a look up table, imho.

unless there is some advantage like size or flexiblility, so replace it with a series of hash tables.

its hash tables all the way down.

Re:I Call BS (1)

tlhIngan (30335) | about a year ago | (#44443651)

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.

Just doesn't work... (1)

TiggertheMad (556308) | about a year ago | (#44443697)

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

Anonymous Coward | about a year ago | (#44443985)

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... (2)

superwiz (655733) | about a year ago | (#44444047)

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:I Call BS (1)

physicsphairy (720718) | about a year ago | (#44443731)

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

Amen, this is a total scam (0)

Anonymous Coward | about a year ago | (#44443803)

We've been hearing this absurdly false claim for decades, now. If it worked, they would gladly prove it, but notice how they don't dare let anyone try it.

Re:I Call BS (1)

Anonymous Coward | about a year ago | (#44443931)

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 (1)

MightyMartian (840721) | about a year ago | (#44444009)

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.

Deciphering != Reverse Engineering (3, Informative)

Dynedain (141758) | about a year ago | (#44443405)

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 (5, Insightful)

wierd_w (1375923) | about a year ago | (#44443501)

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 (1)

MightyMartian (840721) | about a year ago | (#44443533)

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 (1)

wierd_w (1375923) | about a year ago | (#44443601)

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 (0)

Anonymous Coward | about a year ago | (#44443689)

Intel and AMD have both invested a lot in making virtualisation as close to running on a real cpu as they can. They think virtualisation is the next big move in desktop CPUs and are both trying to position themselves as VM-friendly. They're not likely to screw up their investment by going out of their way to make it easy for app vendors to write apps that refuse to run on VMs.

Re:Deciphering != Reverse Engineering (1)

MightyMartian (840721) | about a year ago | (#44443723)

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 (1)

MikeBabcock (65886) | about a year ago | (#44443835)

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 (1)

fuzzyfuzzyfungus (1223518) | about a year ago | (#44443693)

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 (1)

bondsbw (888959) | about a year ago | (#44443725)

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 (0)

Anonymous Coward | about a year ago | (#44443851)

They aim for a cross between Communist China and North Korea. Considering how MPAA works and managed to ruin so many lives already, the internet filters in UK and probably in the works for most of the other countries right now, I'd say this is just another drop in the bucket.

I wonder if maybe I should create my own Android distro, with SELinux and a custom list of applications, all controlled by me for my family and friends to use safely ... Would probably make a good business model 10 years from now.

Re:Deciphering != Reverse Engineering (0)

Anonymous Coward | about a year ago | (#44443903)

Considering the mentions of public key encryption and homomorphic encryption in the actual paper's abstract, I suspect they did a lot more than the trivial self decrypting software trick. Just like you can't get a private key by single stepping and debugging encryption with a public key, and you can't invert a cartographic hash function by debugging it with several inputs, I suspect their system is actually robust in a mathematical perspective as they claim. The utility is limited (its not a DRM solution for all software by any means), but it has many potential uses in security and cryptography.

I don't Think That's The Point (1)

The Real Nem (793299) | about a year ago | (#44443983)

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:Deciphering != Reverse Engineering (0)

Anonymous Coward | about a year ago | (#44443653)

That was my first thought. However, suppose you have a program that is basically an input verifier.

Lets take the example of a program that you input a finger print scan, and a message, and if the finger print approximately matches the reference image (compiled into the software), it signs the message with its private key (also compiled in), otherwise no output.

While it may be possible to do some image hashing threshold encryption trick, thats hard. If you could just leave the darn referance image and private key in the app, compile it and run it through this "software encrypter", that would be much easier.

The idea is very interesting, and if it really works as I think, it could be very useful too.

Re: Deciphering != Reverse Engineering (0)

Anonymous Coward | about a year ago | (#44443935)

Or you could just change a single comparison instruction and skip the check for fingerprint validity.

Re:Deciphering != Reverse Engineering (1)

chizor (108276) | about a year ago | (#44443791)

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 (1)

superwiz (655733) | about a year ago | (#44444031)

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.

so..will the next Stuxnet (1)

Anonymous Coward | about a year ago | (#44443407)

so..the next Stuxnet will be untraceable , cool

Gotta love articles without details (2, Funny)

Anonymous Coward | about a year ago | (#44443409)

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

Re:Gotta love articles without details (1)

MrEricSir (398214) | about a year ago | (#44443611)

You mean a link to the paper [iacr.org] , like the one in the third paragraph of the article?

Re:Gotta love articles without details (1)

sydneyfong (410107) | about a year ago | (#44443713)

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 (1)

Anonymous Coward | about a year ago | (#44443905)

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 (4, Insightful)

technosean (169328) | about a year ago | (#44443417)

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 (2)

MightyMartian (840721) | about a year ago | (#44443441)

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 (1)

ls671 (1122017) | about a year ago | (#44443699)

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 (0)

MikeBabcock (65886) | about a year ago | (#44443837)

You'd be wrong. Virus writers invented self-mutation engines and encryption systems for code long ago and VMs to detect that code became commonplace in AV products. cf. AV test suites where even the best anti-virus software can't detect 100% of known viruses.

Polynomial time (0)

Anonymous Coward | about a year ago | (#44443637)

The paper says:

Improving the Practical Efficiency: While our current obfuscation construction runs in polynomial-time, it is likely too inecient for most practical problems. An important objective is to improve the efficiency for use in practical applications.

In other words, this is currently too slow for almost anybody except virus-writers.

Hurry up, Europe is hungry for your fines (4, Interesting)

c0lo (1497653) | about a year ago | (#44444021)

Sell a program protected like this in Europe [europa.eu] and you may end paying hundreds of millions [forbes.com] :

(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. [...].

make a crackme (2, Insightful)

ZeroNullVoid (886675) | about a year ago | (#44443433)

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.

zOMG I r a 133t haX0r (0)

Anonymous Coward | about a year ago | (#44443505)

If they really think it is so good, then they should put their money where their mouth is. Make it into a crackme.

Yeah agree TOTALLLLLLY! They're choosing instead to show it at a fly-weight pseudo-meeting, the so-called "IEEE Symposium on Foundations of Computer Science." Fraudsters!

Re:zOMG I r a 133t haX0r (0)

Anonymous Coward | about a year ago | (#44443707)

If they really think it is so good, then they should put their money where their mouth is.
Make it into a crackme.

Yeah agree TOTALLLLLLY! They're choosing instead to show it at a fly-weight pseudo-meeting, the so-called "IEEE Symposium on Foundations of Computer Science." Fraudsters!

Meh. Anyone who can talk up their work can present a paper at a conference; all you need to do is convince a couple of referees that what you're doing is interesting. It doesn't tell anyone anything about actual useful results from the system.

Re:zOMG I r a 133t haX0r (-1)

Anonymous Coward | about a year ago | (#44443991)

Meh. Anyone who can talk up their work can present a paper at a conference; all you need to do is convince a couple of referees that what you're doing is interesting.

Yeah like totally. I mean look at that crapolla [iacr.org] , you havta have a PhD in math or somthng just to read it!!!! I'm like, just let me at the code dude. I shove it in my perl byte-code decompiler and like it's source in 10 mins, I rulez!!!

Seems improbable (1)

Anonymous Coward | about a year ago | (#44443437)

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 (3, Insightful)

MightyMartian (840721) | about a year ago | (#44443447)

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 (1)

shentino (1139071) | about a year ago | (#44443487)

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 (0)

Anonymous Coward | about a year ago | (#44443963)

If you cannot hack it, don't buy it.

This simple rule applies to hardware, software and content. It is a great algorithm to ensure freedom.

Re:Seems improbable (1)

Anonymous Coward | about a year ago | (#44443467)

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 (0)

Anonymous Coward | about a year ago | (#44444005)

That will give you certain execution paths through the code. However, there could be large parts of the code you don't observe.

Consider:
If moon phase="waxing gibbous" then call subroutine(worlddomination) ...so you only see the path through worlddomination if you're in the right moon phase.

Could take a very long time to see all the code - and then you have a mess of code traces you need to condense into a program.

And after you do all that, you find that the program is in fact emulating another CPU architecture, which is executing its own program using an unknown machine code...

Performance hit (1)

Pinhedd (1661735) | about a year ago | (#44443443)

and programs will continue to run like it's 1987

A giant step backward for maintainability? (1)

Shavano (2541114) | about a year ago | (#44443457)

Or is there an original unscrambled source code retained somewhere?

Too Slow (1, Interesting)

Anonymous Coward | about a year ago | (#44443475)

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 (1)

MightyMartian (840721) | about a year ago | (#44443499)

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.

ROFL! (0)

sgt scrub (869860) | about a year ago | (#44443489)

iron wall.... hahaha... impossible for.... No please STOP... reverse-engineer HAHAHAHA

Oh my sides. Man that was good. Wait, they are serious? LOL

The program will have to DO something (2)

Sean (422) | about a year ago | (#44443503)

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 (1)

MightyMartian (840721) | about a year ago | (#44443525)

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

The original paper (4, Informative)

HatofPig (904660) | about a year ago | (#44443517)

The original paper is available here [iacr.org] .

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 [iacr.org] | BibTeX Citation [iacr.org]

Virtual Machine. (0)

Roogna (9643) | about a year ago | (#44443521)

Well that fixed that.

If I can see everything, I win, if not, maybe not (1)

davidwr (791652) | about a year ago | (#44443537)

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.

Sloppy code writers will love it (0)

Anonymous Coward | about a year ago | (#44443541)

Great for malware writers and anyone who writes sloppy code. Nobody gets to see how badly they code, and if it doesn't run well, then it's because of all the overhead with the encryption.

And In My Other hand (0)

Anonymous Coward | about a year ago | (#44443577)

There are two choices here. either the government has the key to easily deal with this or they will make it illegal to use.
                    Governments will not permit the exchange of information without observation.

Wish I had thought of this myself (1)

vikingpower (768921) | about a year ago | (#44443657)

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 (-1)

Anonymous Coward | about a year ago | (#44443703)

You SKIMMED it you dumfuk.

Re:Wish I had thought of this myself (1)

vikingpower (768921) | about a year ago | (#44443961)

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

K(Impossible) she's a Possible after all !! (0)

burni2 (1643061) | about a year ago | (#44443709)

A computer program is deterministic (except for machine specific fp round errors) determined to do a certain set of tasks.
Thus my steam powered von-Neumann-Automaton is able to execute the software (with human help) within a certain (normal) amount of time,
so this is only a speed bump too.

And if the mathematical puzzle is so puzzling that the non-mathemations aren't able to solve it,

I'd call the software simply unusable.for 99% of the users.

Any assembly encryption can be broken in 5 minutes (1)

nomaddamon (1783058) | about a year ago | (#44443721)

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

Re:Any assembly encryption can be broken in 5 minu (-1)

Anonymous Coward | about a year ago | (#44443739)

You confuse assembly with machine code you dumfuk! You are a wannabe punk poser!

like DVDs and all the others (1)

raymorris (2726007) | about a year ago | (#44443767)

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.

Another small step? (1)

EzInKy (115248) | about a year ago | (#44443771)

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. (1, Flamebait)

eclectro (227083) | about a year ago | (#44443841)

It's called Forth [wikipedia.org]

Logic Analyzer on CPU pins (0)

Anonymous Coward | about a year ago | (#44443899)

Assuming current processors, the CPU still has to fetch code & data from memory in the clear. Put a logic analyzer on the CPU (or elsewhere) to monitor all address and data lines. Capture it all and then see what code the CPU is executing. Come up with some clever software to derive large portions of functional source code from the capture. Clean it up by hand, and you've successfully reverse engineered it. Am I missing something?

What this means. I think. (5, Interesting)

Animats (122034) | about a year ago | (#44443915)

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 (3, Interesting)

Badge 17 (613974) | about a year ago | (#44443929)

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

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

So this guy completely reinvented... (0)

Anonymous Coward | about a year ago | (#44443965)

spaghetti-code. Thats probably all this is.

Sometimes I just hate researchers (1)

maroberts (15852) | about a year ago | (#44443997)

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

Nice try (1)

superwiz (655733) | about a year ago | (#44444013)

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 [mit.edu]

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? (1)

stephendavion (2872091) | about a year ago | (#44444017)

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

Malware in 3, 2, 1... (2)

Opportunist (166417) | about a year ago | (#44444075)

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.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?