Computer Scientists Achieve 'Crown Jewel' of Cryptography (quantamagazine.org) 69
A cryptographic master tool called indistinguishability obfuscation has for years seemed too good to be true. Three researchers have figured out that it can work. Erica Klarreich, reporting for Quanta Magazine: In 2018, Aayush Jain, a graduate student at the University of California, Los Angeles, traveled to Japan to give a talk about a powerful cryptographic tool he and his colleagues were developing. As he detailed the team's approach to indistinguishability obfuscation (iO for short), one audience member raised his hand in bewilderment. "But I thought iO doesn't exist?" he said. At the time, such skepticism was widespread. Indistinguishability obfuscation, if it could be built, would be able to hide not just collections of data but the inner workings of a computer program itself, creating a sort of cryptographic master tool from which nearly every other cryptographic protocol could be built. It is "one cryptographic primitive to rule them all," said Boaz Barak of Harvard University. But to many computer scientists, this very power made iO seem too good to be true. Computer scientists set forth candidate versions of iO starting in 2013. But the intense excitement these constructions generated gradually fizzled out, as other researchers figured out how to break their security. As the attacks piled up, "you could see a lot of negative vibes," said Yuval Ishai of the Technion in Haifa, Israel. Researchers wondered, he said, "Who will win: the makers or the breakers?" "There were the people who were the zealots, and they believed in [iO] and kept working on it," said Shafi Goldwasser, director of the Simons Institute for the Theory of Computing at the University of California, Berkeley. But as the years went by, she said, "there was less and less of those people."
Now, Jain -- together with Huijia Lin of the University of Washington and Amit Sahai, Jain's adviser at UCLA -- has planted a flag for the makers. In a paper posted online on August 18, the three researchers show for the first time how to build indistinguishability obfuscation using only "standard" security assumptions. All cryptographic protocols rest on assumptions -- some, such as the famous RSA algorithm, depend on the widely held belief that standard computers will never be able to quickly factor the product of two large prime numbers. A cryptographic protocol is only as secure as its assumptions, and previous attempts at iO were built on untested and ultimately shaky foundations. The new protocol, by contrast, depends on security assumptions that have been widely used and studied in the past. "Barring a really surprising development, these assumptions will stand," Ishai said. While the protocol is far from ready to be deployed in real-world applications, from a theoretical standpoint it provides an instant way to build an array of cryptographic tools that were previously out of reach. For instance, it enables the creation of "deniable" encryption, in which you can plausibly convince an attacker that you sent an entirely different message from the one you really sent, and "functional" encryption, in which you can give chosen users different levels of access to perform computations using your data. The new result should definitively silence the iO skeptics, Ishai said. "Now there will no longer be any doubts about the existence of indistinguishability obfuscation," he said. "It seems like a happy end."
Now, Jain -- together with Huijia Lin of the University of Washington and Amit Sahai, Jain's adviser at UCLA -- has planted a flag for the makers. In a paper posted online on August 18, the three researchers show for the first time how to build indistinguishability obfuscation using only "standard" security assumptions. All cryptographic protocols rest on assumptions -- some, such as the famous RSA algorithm, depend on the widely held belief that standard computers will never be able to quickly factor the product of two large prime numbers. A cryptographic protocol is only as secure as its assumptions, and previous attempts at iO were built on untested and ultimately shaky foundations. The new protocol, by contrast, depends on security assumptions that have been widely used and studied in the past. "Barring a really surprising development, these assumptions will stand," Ishai said. While the protocol is far from ready to be deployed in real-world applications, from a theoretical standpoint it provides an instant way to build an array of cryptographic tools that were previously out of reach. For instance, it enables the creation of "deniable" encryption, in which you can plausibly convince an attacker that you sent an entirely different message from the one you really sent, and "functional" encryption, in which you can give chosen users different levels of access to perform computations using your data. The new result should definitively silence the iO skeptics, Ishai said. "Now there will no longer be any doubts about the existence of indistinguishability obfuscation," he said. "It seems like a happy end."
I want it to be true, but I give two years, tops. (Score:4, Interesting)
"Barring a really surprising development, these assumptions will stand," Ishai said.
Honestly, it sounds like this is quite some arrogance. I mean, they've taken a fundamentally different approach to this and it's impressive in itself. But the industry is littered with stuff like this. I give it two years, maximum. I mean, shit it's 2020 - the poster child for Really Surprising Developments.
Re: (Score:2)
At first blush this sounds like a good thing, but just like most other stuff, the first and only way it will be used is to weaponize computers and gadgets against their owners. I don't want apps on my devices that I cannot see and control what they are doing. I won't run a device that tells me what to do instead of the other way around.
Re: (Score:2)
It _could_ also be used to protect data from unwelcome intrusion by federal authorities. Keeping a "second set of books" is a very old habit of many fiscal companies, especially when organized criminals or governments demand tribute or taxation.
Re: I want it to be true, but I give two years, to (Score:2)
"It _could_ also be used to protect data from unwelcome intrusion by federal authorities"
Unjailbreakable devices for the owners, back door/keys/whatever for the feds to gain access.
You are talking as if corporations are on our side, and would never sell us out to the scary 3 letter agencies.
Re: (Score:2)
> I won't run a device that tells me what to do
You still use paper maps for navigation? Weird flex, but okay...
Re: (Score:3)
indistinguishability obfuscation (Score:2)
English isn't my first language, you insensitive clod!
On a more serious note, is the terminology purposely chosen to be fully descriptive to those in the know (I'm assuming a lot here, bear with me) but in light of the field of application, be completely cryptic and undecipherable to all outsiders?
Re:indistinguishability obfuscation (Score:4, Funny)
English isn't my first language, you insensitive clod!
On a more serious note, is the terminology purposely chosen to be fully descriptive to those in the know (I'm assuming a lot here, bear with me) but in light of the field of application, be completely cryptic and undecipherable to all outsiders?
English is my first language. It doesn't help.
Re: (Score:3)
English isn't my first language, you insensitive clod!
On a more serious note, is the terminology purposely chosen to be fully descriptive to those in the know (I'm assuming a lot here, bear with me) but in light of the field of application, be completely cryptic and undecipherable to all outsiders?
Try distinguishably de-obfuscating it. It's really clear and well written.
Somewhat descriptive (Score:5, Informative)
It's somewhat descriptive, in my view. Indistinguishability is a concept used all the time in cryptography, a daily-use tool.
Security proofs / guarantees often follow the form "the attacker can't distinguish between this tool and randomness/this other thing where the attacker osngicen the ability to ___. Once indistinguishability has been proven, other theorems mean it's useful properties. Those theorems require that indistinguishability be proven first.
A simple example would be this. Assume I give you these two things:
Fjdjeyeoyksurofyowuyxhfus
Lehfkrgdoyjxgiryrohkafjwgd
One of those is my encrypted password. The other is completely random gibberish. If there is no way an attacker can distinguish between the encrypted password vs random gibberish, that implies the encryption is "good" (for certain formal definitions of good).
We have indistinguishability under chosen plaintext attack (IND-CPA) - the attacker chooses the plaintext and gets it encrypted. Indistinguishability under chosen ciphertext attack (IND-CCA) is when the attacker can choose an encrypted value, etc.
Indistinguishable obfuscation means we can encrypt a set of bytes that the public can execute as a set of instructions, a program. They can use it, see the inputs and outputs. So for example maybe the program does "let me in". However, no attacker can distinguish between my program that does that vs any other implementation - they can't tell HOW your program works. They can only see the results. The program is obfuscated in such a way that it is indistinguishable from another function / program that gives the same output, given the same input.
If you can do that, you can make indistinguishable instructions that generate shared secret keys and all kinds of other interesting things.
However, it has been proven that there can be no iO that does $X, for several values of $X. Which leads to belief that perhaps there can be no iO at all.
That's proven for certain operations by logic like the following:
If we had an iO that does $X, we could call that "iOX". ...
If we had iOX, we could use it to make a function called foo that does
If we had foo, we could use it to distinguish different instances of iOX
That is, if we had an unbreakable iOX, we could use it to break iOX. Therefore there can be no unbreakable iOX.
Re: (Score:1)
Okay, I believe that I follow you. If this true then we get some interesting wrinkles, but crown jewel?
If an attacker has anything that he/she/it believes contains a password (no matter what it looks like) then the attacker will use his/her/its cracking tool(s).
Where does indistinguishability obfuscation significantly increase the time/effort/cost to crack?
(Also, remember that the sender & intended receiver must have enough info. to communicate. The intended receiver does not need to know exactly how th
Re: (Score:2)
Yeah general iO would be a really big deal. But I think it's been proven that there can be no general iO. So this would be some special case of iO. Which may or may not be a huge deal.
> then the attacker will use his/her/its cracking tool(s).
Suppose the attacker is using their tools against a completely random string that is unrelated to my password. They'll not get any useful information from a random string of course.
Indistinguishability means that using the same tools against my encrypted password
Re: (Score:2)
I actually have a very weak example of indistinguishability, which is indistinguishability from random noise. Here are two better, stronger examples.
Assume that you, the attacker pick two passwords. I encrypt one of them t and tell you that the encrypted form is:
Lehfkrgdoyjxgiryrohkafjwgd
Consider if even though you know your passwords (the plaintext), you can't tell which of those two passwords I have encryptesd. That's indistinguishability under chosen plaintext. The attacker chose the password, yet aft
Re: (Score:2)
If we had foo, we could use it to distinguish different instances of iOX
We could?
I think I need a worked example to follow this logic chain.
Re: (Score:2)
I believe this paper has a couple of proofs. :)
I have four other papers I have to read this week, so I'm not in the mood to actually read this own today - I have enough darn papers to read.
Limits on the Power of Indistinguishability Obfuscation
and Functional Encryption
Gilad Asharov & Gil Segev
Re: Somewhat descriptive (Score:2)
Re: (Score:2)
I've never heard the term before, but it was immediately obvious to me what it meant. However, it was already a familiar concept especially related to RF communications.
Re: (Score:2)
aRTeeNLCH asked:
On a more serious note, is the terminology purposely chosen to be fully descriptive to those in the know (I'm assuming a lot here, bear with me) but in light of the field of application, be completely cryptic and undecipherable to all outsiders?
You mean "like jargon terms in every specialized field?"
Because, yes, it's exactly that ...
Re: indistinguishability obfuscation (Score:2)
Re: (Score:2)
eeNLCH geeksplained:
Jargon is just coincidentally unclear to those outside of the field, it's just used for briefness and exactness amongst insiders.
Yes - and no. In engineering and scientific fields, that's mostly true, as it is for jargon in many other, less-technical fields.
It was medicine, in particular, I had in mind when I posted my admittedly-cynical reply. Just as one for-instance, let me point out that physicians use "micturition" for what you and I would call "urination." You'll note that both terms have precisely the same number of syllables, so there's no "briefness" advantage to their use of the more obscure term. Nor is
Re: indistinguishability obfuscation (Score:2)
Re: (Score:2)
aRTeeNLCH conceded:
Agreed, I didn't think of it but in the medical field they user a lot of terms that are intended to mask what's being said. I just came across a container with some kind of skin product, which boosted about "urea" as one of the ingredients. Horse pee.
To be strictly accurate, urea is a chemical that is found in pretty much every mammal's urine, including mine and thine. And it's used in a host of processes [wikipedia.org] that produce all kinds of useful and valuable products (fertilizers, for instance). The fact that the cosmetics industry also uses it is not urea's fault!
;-)
The topic here was related to engineering science, which is why I thought it funny that cryptographers encrypt their terms...
"Ironic," is the way I'd put it, but yeah ...
Re: indistinguishability obfuscation (Score:2)
OK so does this mean (Score:3, Funny)
Re: (Score:1)
Only when you use it twice.
Re: (Score:3)
Only when you use it twice.
Yeah, when I want something really secure something I run ROT13 twice and but just to confuse everyone I run the second operation in reverse...;)
Re: (Score:2)
ROT13 does work?
No. ROT13, like DES, has been broken for a long time now. The fix with both is to run them multiple times, to wit: 3DES and ROT26.
Sorry but can we end this sloppy language trend (Score:1)
"Less and less people" is for when you weigh a large pile of them by the kilogram.
Detail is important in cryptography, programming, and natural language.
Re:Sorry but can we end this sloppy language trend (Score:5, Informative)
English has used 'less' for countable nouns for as long as it existed. The idea that there must be a rigid 'less' vs 'fewer' distinction originates in a letter Roger Baker wrote in 1770 about his personal preference under some circumstances, which was then misinterpreted as a hard rule for all circumstances. English has used 'less' for countable nouns even as far back as Old English (over a millennia before Baker was born).
In other words, to use a computer security analogy, insisting on a hard 'less' vs 'fewer' rule is much like insisting that every hard drive *needs* to be wiped with a 35-pass Gutmann method (and saying that anything less than 35 passes is sloppy); it betrays a fundamental misunderstanding of both history and practical usage.
Re: (Score:2)
I assumed he just meant they were losing weight.
Re: Sorry but can we end this sloppy language tren (Score:1)
Not so fast (Score:5, Informative)
Cryptographer here (as in, PhD from a respectable institution, not a Bitcoin nut). The paper (if correct, I haven't checked the details) only achieves sub-exponentially secure indistinguishability obfuscation (iO). This is still a noteworthy achievement (RSA, for example, is also "only" sub-exponentially secure and still it is widely used) but I would say a little bit too early to claim that iO is real. What would be needed is:
- from a theoretical standpoint, an exponential security result (this would be super interesting IMHO)
- from a practical standpoint, a result with "small" complexity constants (the famous "big O notation")
Just to clarify: if your cryptographic scheme is "n bits" secure but has a complexity (running time) of n^100000000, from a theoretical standpoint it is more interesting than a scheme which is also secure "n bits" secure with a running time of 2^(n/100000000). But from a practical standpoint, the first scheme is useless, while the second one has a lot of applicability.
And to clarify the meaning of iO: it is a Big Beast. If you can build efficient iO then you really have the Holy Grail to do basically *anything* in cryptographic terms. Like, even absurd things, such as "uncrackable software protection" and so on. From a theoretical standpoint, it would be just slightly less interesting than a P=NP proof. Too good to be true, and this is why many cryptographers think it is actually not possible.
But time will tell.
Re: (Score:2)
The article is heavy on the us vs. them human interest stuff and light on description of what indistinguishability obfuscation actually is. Can you clarify? The Wikipedia article is really short but suggests it's a procedure to scramble a program so that it functions, but the details of its functioning are too expensive to recover.
Re:Not so fast (Score:5, Informative)
Author of parent post here. Well, iO is a technique to "obfuscate" a program, so you can run it but not "decompile" it. This is a very high level explanation, but the details are trickier than this.
The first problem is: how do you even define "obfuscate"? This is the main issue in modern cryptography: give a precise, formal definition of the security property you want to achieve. It is often far for trivial, and for the general field of "cryptographic obfuscation" in particular it was unclear for a long period how to define what you really want to achieve.
Let's say you have a program A. You do not have the source code of A, but you can query A on any input you like and get the results. This is a so-called "black-box" model: basically you can only "know" an object by its input/output behavior. Ideally, you would like a notion of obfuscation that says that A and Obf(A) (where Obf is your "obfuscator" compiler) cannot be distinguished by observing their input/output behavior. This notion is called "black-box obfuscation" and turns out to be impossible, like, mathematically unachievable. Can you do something better than this?
The first paper on the definition of iO in 2013 started the race. The idea is the following: instead of requesting that A and Obf(A) must be indistinguishable, now you ask "a bit less": you just ask that Obf(A) and Obf(B) must be indistinguishable, for any A and B programs with the same input/output behavior (but not necessarily the same program, for example A might be more efficient than B).
This has some interesting implications. To begin with, it implies that an iO obfuscation of a "fast" program A cannot be more efficient than the iO obfuscation of "the SLOWEST program that behaves like A". Which in turns implies that either: 1) your iO obfuscator is also a super-efficient optimizer; or 2) that your iO obfuscator makes the fastest program slow as hell. As you can imagine, 1) is very unlikely, this is why, if iO is possible at all, the performance hit would be horrible, probably even worse than Fully Homomorphic Encryption.
The plus side is that iO is incredibly powerful. It has been proved that an iO obfuscator can be used as a building block to achieve all sort of useful cryptographic schemes with incredible applications in privacy and security.
The authors of the paper mentioned in the submission now say they finally show how to achieve iO with "standard" cryptographic tools. Personally I am skeptical about iO, and I think that either there is a flaw in the paper, or the result has been blown out of proprotions (like, there is some caveat). Regardless, interesting times ahead.
Re: (Score:2)
you have a fever indeed, because on your second post you forgot to switch anonymous ;-)
Re: (Score:2)
Obfuscating the code is fine but at some point I would assume it'll need to be de-obfuscated/crypted to cleartext/IL/ASM or similar to be run. Surely then exploits in the hardware or a badly-configured environment would lead to this being true? Meaning this is rendered to the same level of pretty much everything else?
Re: (Score:2)
Considering that I can easily write a bubble sort that brute forces a random N body problem after each string exchange (or worse), it seems that the least efficient case will always take longer than the universe has left, suggesting iO simply cannot have a practical application if it can exist at all.
Re: (Score:2)
Thanks, that was great.
Re: (Score:2)
Just what the world needs, perfect DRM (Score:5, Insightful)
That's what "indistinguishability obfuscation" means: a program you can execute but cannot understand. Pretty much the primary use of such a thing would be to encrypt movies for Disney+.
Re: (Score:1)
You could make unhackable games, by encrypting the core logic. You might even be able to dispense with massive central servers for MMOs. You'd have an encrypted program receiving encrypted commands from the network, and returning encrypted replies. So if there are 12 players in an area, one of them acts as a server. If that server goes down or can't handle the traffic, the player's machines decide among themselves who will take over. Periodically save player progress to the game developer's computer to prev
Re: (Score:2)
Nope. All these things are hackable at the interface level.
Re: (Score:2)
Re: (Score:2)
Game hacking does not require physical access. No cheat-software coder does a real code analysis of the run-time system. At best, they look at some specific parts, but usually it is all on interface level.
Re: (Score:1)
That's what "indistinguishability obfuscation" means: a program you can execute but cannot understand.
Sounds like they just described perl.
Re: (Score:2)
You spelt LISP wrong.
Quite a bit more than that (Score:2)
It's quite a bit more than that. Yes, DRM uses encryption - it's not the only thing that uses encryption.
Virtually anything that uses encryption would be aided by iO, if general iO were feasible. Yes the definition talks in terms of programs or instructions, but remember that "program" might very well be a tiny one that generates a shared secret key. It can do ANYTHING that a computer can do. So here "program" very much doesn't mean "desktop application", a more descriptive term would be "function", where
Re: (Score:2)
No, the primary use for such a thing is to run things in the cloud without handing over your crown jewels to Amazon and Mickeysoft.
Re: (Score:1)
Good thing is that as long as the information needs to reach into our brains trough our eyes/ears, we can intercept and store it.
A simple way would be to use a camera and a microphone in front of a screen/speaker playing the authorized media (like the VCD pirates in the late 90s/early 00s).
A better way would be to capture the decoded information on the way to the analogue speakers and the actual screen pannel (in the case of a TV).
All you would need is a fast enough FPGA with enough IOs and logic cells to
Assumptions (Score:4, Funny)
The new protocol, by contrast, depends on security assumptions that have been widely used and studied in the past.
Did they test against this one [xkcd.com]?
Re:Assumptions (Score:4, Interesting)
Actually, in a way they did. It could enable deniability encrypt. That is, the data could look like it's not encrypted at all, or encrypted with a different message than you really used, while to all intents and purposes This isn't just throwing in a bunch of random files as decoys or chaff.
"Darn, we used the drugs and the wrench until he gave us his password, but there's no bitcoin on the laptop, just a database of his beanie baby collection!"
Remember, a lot of attacks on some algorithms is watching what the computer does while encrypting or decrypting. The branches it takes deduced by the delays due to cache fetches and so forth.
Re: (Score:3)
Re: (Score:1)
Unfortunately, if it works for the attackers intended use, it doesn't matter if you gave them the fake secret...
This is not very useful (Score:2)
Probably the reason I have never heard of it, despite following crypto research for 30 years now. The problem is this: Even if you can obfuscate the code, that rarely provides any advantage. First, what are you going to hide? Second, who will be stupid enough to run such a thing? And third, in basically all practical cases, observing interface behavior is quite enough. There is also the question how much this will cost you in performance.
So, no "crown jewel", just a somewhat interesting theoretical result.
Re:This is not very useful (Score:4, Informative)
It's a crown jewel for theoretical reasons, in that you can derive other crypto tools from this tool. In other words, iO can be used as a primitive. Practicality is something that happens later.
Re: (Score:2)
Practicality is something that happens later.
Sometimes. Mostly not.
Sounds like One Time Pads (Score:2)
Nitrokeys, then (Score:2)
I wouldn't have anything to spy on if I was going to a terrible enemy territory (there are far worse than China IMHO), but if I was, as concerns deniability I'd just take my open-source-open-hardware Nitrokey.
I have a relatively old 'storage' model, which features both a 'normal' encrypted volume whose pass I'd give once I see the wrench, and a manner of adding an untractable volume as long as the normal one isn't full (it's located in the unused memory). The same, open software unlock both or just announce
Setec Astronomy (Score:2)
Indistinguishability obfuscation (Score:3)
Well, you've definitely obfuscated whatever that is. It's pretty clear the submitter doesn't understand this, because there's no cogent summary of what it is. I don't understand it either, but I'd like to. The summary should at least take the first steps in that direction.
Sounds like they've (Score:2)
finally found a use for LISP.
Is this even useful? (Score:2)
From the article:
For example, suppose you have a program that carries out some task related to your bank account, but the program contains your unencrypted password, making you vulnerable to anyone who gets hold of the program. Then — as long as there is some program out there that could perform the same task while keeping your password hidden — an indistinguishability obfuscator will be strong enough to successfully mask the password.
If this is the most useful example they could come up with, this special case of iO seems problematic (or maybe even useless). Because you cannot produce another "some program" that calls the same bank APIs but doesn't use private authentication info. If you could, that other program would be used instead and obfuscation would not be needed. So this technique can only obfuscate secrets that shouldn't be in the code anyway--and a smart compiler will already remove unused data.
One time pad (Score:2)
I guess one time pad was not allowed to compete?
(decrypt the above message and it will change your life!)
sdsclub (Score:1)