Dr. Moses Liskov (00:02):

That label, the Crown Jewel of Cryptography, was right there in the title of the Quanta magazine article, and it definitely contributed, I think, to a lot of excitement around the topic, but it was actually a phrase that was put out there by a cryptographer who recognized the power of this stuff and the power of this stuff, and it’s very powerful in the sense of its theoretical implications. Indistinguishability Obfuscation, it gives you this ability to hide details of programs in such a way that you can really accomplish a lot of different types of things with it.

Brinley Macnamara (host) (00:40):

Hello and welcome to MITRE’s Tech Futures Podcast. I’m your host, Brinley Macnamara. At MITRE, we offer a unique vantage point and objective insights that we share in the public interest. And in this podcast series, we showcase emerging technologies that will affect the government and our nation in the future.

Brinley Macnamara (host) (00:59):

Today, I’m going to tell you about Dr. Moses Liskov’s research into the impact of a recent breakthrough that is quietly ushered in a new age of cryptography, also known as Indistinguishability Obfuscation, or iO for short. But before we begin, I want to say a huge thank you to Dr. Kris Rosfjord, the Tech Futures Innovation Area Leader in MITRE’s Research and Development program. This episode would not have happened without her support. Now, without further ado, I bring you MITRE’s Tech Futures Podcast episode number 10.

Brinley Macnamara (host) (01:43):

Before we dive deeper into the implications of the so-called crown jewel of cryptography, I want to take a step back and explain how iO compares to more intuitive cryptographic concepts that you’ve probably heard of such as encryption. All right. So, time for a little cryptography 101, and the first order of business is to explain the difference between encryption, a technology that is critical for securing everything from your Google searches to the cat pictures on your phone, and obfuscation, a lesser known technique for making the code that comprises your favorite apps, games, and websites difficult to reverse-engineer.

Brinley Macnamara (host) (02:21):

Let’s start with encryption. Encryption is a way of enabling a sender of a secret message to transform said message so that it’s indecipherable to anyone except the intended recipient who possesses a key to unlock, i.e., decrypt said message. On the other hand, obfuscation is a way of enabling a sender to garble a secret message so that everyone including its intended recipient will have a harder time reading it. But who on earth would be crazy enough to want to garble a secret message so that can be distributed to everyone while simultaneously making it harder for its intended recipient to read? Well, pretty much every company in the proprietary software business whose survival depends on their source code being usable, while simultaneously hard for even the craftiest of potential IP thefts to reverse-engineer.

Dr. Stan Barr (03:14):

Why do we want to protect algorithms? Companies that invest in creating a novel algorithm, or they have some novel intellectual property that they want to protect.

Brinley Macnamara (host) (03:27):

That’s Dr. Stan Barr talking. He’s a Senior Principal Cyber Researcher in MITRE Labs.

Dr. Stan Barr (03:32):

Or maybe they want to make it easy to share like a demo version of something where they want to just keep most of the code in place so that if you decide to try before you buy, you get some limited set of options, and then when you register the license key, you get the rest of them, right? They don’t want to have to rebundle and reinstall and delete all the old stuff. They’d like to make that as simple as possible.

Brinley Macnamara (host) (03:58):

But it turns out that the types of obfuscation that are commonly used today to protect against IP theft are way less good at hiding secrets than our triedest-and-truest methods of encryption. For example, breaking the well known RSA encryption algorithm using a classical computer would take even the smartest and most well funded hacker many, many times longer than a human lifetime. So, you can be rest assured that the encrypted cat pictures on your phone are safe.

Brinley Macnamara (host) (04:24):

Conversely, a skilled hacker could very well reverse-engineer an obfuscated piece of software in a matter of days, if not hours. And that brings us to another key distinction, the type of obfuscation that acts as a mere speed bump for an attacker, versus the type of obfuscation that is guaranteed to stop an attacker dead in their tracks.

Dr. Moses Liskov (04:48):

A form of obfuscation that is particularly good for introducing the subject is obfuscated C.

Brinley Macnamara (host) (04:55):

That’s Dr. Moses Liskov talking. He’s a Principal Cybersecurity Researcher in MITRE Labs.

Dr. Moses Liskov (05:00):

… which is this wonderful rich field where some very, very clever programmers make code that you can look at, and you won’t have any idea that this is actually code, and you have no idea what it does if you’re just a regular, ordinary human, but the tricks that they’re using are not necessarily meant to trick someone who’s really expert in what those techniques are. It just looks confusing and looks confusing is not what real obfuscation, not the cryptographic obfuscation. That’s not what it’s going for.

Brinley Macnamara (host) (05:33):

So, while making code look confusing may make it slightly more time consuming for an attacker to ungarble, this conventional way of obfuscating code is inherently breakable. In other words, there is a 100% chance that this type of obfuscated code could be reverse-engineered should it fall into the hands of a sophisticated enough attacker. Conversely, what makes a cryptographic form of obfuscation so special is that it is impossible to ungarble it. More specifically, a group of super smart cryptographers at UCLA and the University of Washington recently came up with a mathematical proof showing that Indistinguishability Obfuscation is a strong enough form of obfuscation such that it would take way longer than a human lifetime to ungarble code that has been obfuscated using iO.

Brinley Macnamara (host) (06:17):

Unfortunately, Indistinguishability Obfuscation doesn’t come with an easy to visualize analog. Luckily, with the help of Dr. Liskov as well as some lecture videos from the iO proof authors, Drs. Jain, Lin, and Sahai, I was able to pull together a pretty podcast-friendly definition. Indistinguishability Obfuscation is a special type of computer program that takes another computer program as an input and outputs a fully functional obfuscated version of that input program. And the thing that makes the iO compiler so cryptographically special is that it must satisfy the property of indistinguishability. That is, for any two programs, let’s call them P1 and P2, that are equivalent in their inputs and outputs but may differ in their implementations, the obfuscated version of P1 cannot be distinguished from the obfuscated version of P2. Thus, the indistinguishability obfuscator will hide the differing implementations of P1 and P2 so long as these programs are functionally equivalent.

Brinley Macnamara (host) (07:20):

All right. That is as proofy as we’re going to get in this podcast, I promise, but if you’re now asking yourself, how can an obfuscator that makes two nearly identical programs indistinguishable have any practical usefulness whatsoever? Well, the short answer is that iO’s counterintuitiveness doesn’t stop it from being strong enough to hide our most precious digital secrets. In fact, iO is so powerful that the proof of its existence has opened the door for a whole host of interesting applications, which one of the authors of the groundbreaking iO proof, Dr. Amit Sahai, has dubbed Obfustopia. I asked Dr. Stan Barr about which cyber threats the Obfustopia could do away with.

Dr. Stan Barr (08:11):

It seems to be a time-honored tradition among bad guys, right? Patch Tuesday, where patches come out, the next thing we know is that adversaries are scouring what changed in the patch and are trying to figure out how to subvert, first, vulnerable systems that don’t have the patch, and then, sometimes patching software is inherently dangerous itself especially when you’re under a time crunch, where there is a vulnerability that you’re trying to fix. Sometimes you don’t make the best modifications to the software and that you introduce new errors in the same place that you were just fixing. So, just changing a patch, just changing and putting a software patch, which is pretty much the same as putting some spackle on the wall. Everyone can figure out where that spackle is and sort of look, dig a hole underneath it, or look at what the spackle looks like there. All of a sudden, you are highlighting what’s going on and where it is. That gives an adversary a great place to focus on.

Brinley Macnamara (host) (09:18):

But in Obfustopia, an attacker will have no way of distinguishing between two pieces of functional equivalent software, such as one with a vulnerability and one with a vulnerability squashing patch. Guess this means hackers in Obfustopia will be taking more Tuesdays off. And if you’re now asking yourself, when will iO kick in so that we, the benevolent software users, can take a day off from keeping up with the constant drum of update notifications?? To answer this question, we have to turn back to Dr. Liskov to understand what it takes to actually build an indistinguishability obfuscator.

Dr. Moses Liskov (09:55):

This is not to say this is the only way possible to create iO, but basically, what all the papers to date have done is they’ve basically broken it down into two steps. One step is starting with a circuit, you turn it into something called a matrix branching program…

Brinley Macnamara (host) (10:10):

A circuit, by the way, is just a method that cryptographers like to use to represent computer programs in their proofs. And for the purposes of this podcast, all you need to know is whenever you hear circuit, think computer program.

Dr. Moses Liskov (10:22):

… which is a particular form of computation that’s not very efficiently represented. Then, you do a cryptographic construction in order to take your matrix branching program and obfuscate it. It turns out that when you look at all these papers, basically, they all do the same … Almost all do exactly the same thing for that first part. The second part is where they vary. That’s where they have to introduce their new, interesting novel assumptions, their new clever constructions, and it’s that part of it that was really solved in a different way by this Jain, Lin, Sahai paper that caused them to get this level of attention, but it’s the first side really that makes iO very inefficient.

Brinley Macnamara (host) (11:12):

With this inefficiency problem in mind, I asked Dr. Liskov about how much computational resources would be required to apply Indistinguishability Obfuscation to a common task that classical computers perform on a regular basis.

Dr. Moses Liskov (11:26):

So this has to come down by like 118 or so orders of magnitude. 118 orders of magnitude before it would be considered merely extremely inefficient.

Brinley Macnamara (host) (11:40):

That’s incredible.

Dr. Moses Liskov (11:41):

It is, right? It’s just, it’s totally nuts, how big that is. I came up with this analogy. Even if we had a one gigahertz processor for every particle in the known universe running constantly 224 days a week, 24 hours a day, seven days a week, 365 days a year, it would take approximately 366 billion trillion times the age of the universe to compute enough cycles to output one of these matrix branching programs. So, it’s incomprehensible how big these numbers are. It just sounds like numbers on a page after a certain point.

Dr. Moses Liskov (12:19):

Now, on the other hand, this Ananth et al method of using, creating matrix branching programs in a different way, the calculation there comes up much, much better. It’s more like 1.88 times 10 to the 16, which is on the order of maybe 200,000 terabytes of data, so this is obviously impractical and probably impractical for years and years and years, but you can sort of imagine a future where you might be willing to have messages of that kind of size.

Brinley Macnamara (host) (12:51):

I asked Dr. George Roelke, MITRE’s Innovation Area Leader for Cyber about what the return on investment is for funding investigations into technologies that will be, as Dr. Liskov said, extremely computationally impractical in the near term.

Dr. George Roelke (13:06):

There really are sponsored connections in the idea of protecting intellectual property or the anti-tamper problem for government systems, where we are trying to protect sensitive technologies from reverse-engineering and compromise. If something like iO was to become practical, there would be immediate applications, but the challenges in something like that of, and as Moses found out, I think is, and during the research for the paper was that the progress that is made sometimes is just very narrowly tailored or makes certain assumptions that don’t hold in the real world are against those real mission problems that we have.

Dr. George Roelke (13:46):

So one of the values of looking into areas like this, even though it does seem to be very speculative, is it allows us to understand the risks and understand the potential opportunities and how technology is evolving, but we’ve gained a lot from it. We know not to make a high risk, big project as an investment if that probability of success is going to be really low.

Brinley Macnamara (host) (14:07):

I asked Dr. Roelke about when is a good time to take a second look at these types of technologies.

Dr. George Roelke (14:12):

So I think I always say continuously, and we look for evidence of breakthroughs, I think. Sometimes they’ll be journal articles published, or there’ll be something that shows up in Wired magazine, or a lot of the trade publications, summarizing recent journal articles. Sometimes, things will come to us that way. There’ll be somebody at MITRE who’s interested in an area and we’ll see some evidence of a new paper. That might be a sign that it is a time to take a deeper look and reassess whether or not those things have applicability.

Brinley Macnamara (host) (14:42):

Just out of curiosity, how often do these types of breakthroughs occur in the cryptographic community?

Dr. Moses Liskov (14:47):

One of the things that makes it so difficult to answer a question like that is that, how do you know when the world has changed, right? Someone publishes a paper, and the only difference between the day after they publish the paper and the day before is that some people read this paper, and maybe they were like, “Oh, that’s cool.” That’s the difference on day one, but when a breakthrough of this kind of magnitude happens, ultimately, the world gets transformed in amazing ways like the Diffie-Hellman paper, the RSA paper that showed us how to do public-key cryptography in the first place. Those things impacted our world to an enormous degree and people could look at the paper, and they could tell right away that something important had happened there, right, but that is sort of the hallmark of a real breakthrough is you don’t know how important it is at the time. Only time will really tell.

Brinley Macnamara (host) (15:56):

This show was written by me. It was produced and edited by myself and my co-host, Eliza Mace, Dr. Kris Rosfjord, and Dr. Heath Farris. Our guests were Dr. Moses Liskov, Dr. Stan Barr, and Dr. George Roelke. The music in this episode was brought to you by Howard Harper-Barnes, Ooyy, Sarah the Instrumentalist, Issue AB, and Truvio. We’d like to give a special thanks to Dr. Kris Rosfjord, the Technology Futures Innovation Area Leader, for all her support. Tune in next season as we tackle space health, imitation learning, and…. How will our sponsors’ applied cryptography needs change within the next 20 years?

Dr. George Roelke (16:35):

Quantum computing and the challenges that the cryptography community is going to have in maintaining security and developing new algorithms that will be robust against practical quantum computers, if and when they become practical. We don’t know exactly kind of when that will be, but we do know it’s coming.

Brinley Macnamara (host) (16:55):

Copyright 2022. MITRE PRS # 22-0462, February 8th, 2022. MITRE: solving problems for a safer world.