multi-linear jigsaw

A breakthrough in cryptography could thwart a favorite attack of hackers

July 30, 2013
July 30, 2013

Microsoft, Apple, and every maker of mobile and desktop apps on the planet all have a problem: The moment they issue a security “patch,” or an update to their software designed to plug a hole that could be exploited by hackers, those same hackers work feverishly to reverse-engineer that patch in order to figure out what vulnerability it’s designed to stop. Armed with that knowledge, malicious hackers can then attack whatever PCs, servers or mobile phones have yet to update their software with the new patch.

“It can take days or months for a patch to reach most of the vulnerable machines,” says Amit Sahai, a professor of computer science at UCLA. And while this wasn’t specifically the problem Sahai set out to solve when he embarked on his latest research in cryptography, it’s one of the many potential implications of the ground-breaking work he and his team have just unveiled.

What Sahai and a team of researchers at UCLA, IBM Research, and UT-Austin have created is a method for encrypting software and running it in that encrypted state. In the past, researchers have known that it’s possible to encrypt messages (this is how all secure communication on the web, bank transactions, etc. work) but it was not known whether or not it was possible to encrypt software in a way that it could still run even without being decrypted. Sahai’s “mathematical jigsaw puzzle” approach accomplishes this and, he says, adds a whole new class of protectable secret to the world of cryptography.

“The basic scientific question here is, what type of things can have secrets?” says Sahai. “People can have secrets—if you don’t tell me something, that’s a secret. And if you encrypt a message, that’s a secret. But can a piece of software have a secret? Can you have a computer agent that goes from one computer to another computer, that is just code, that moves around with its own secrets? Is that even possible?”

Sahai’s software creates what he describes as a “multilinear jigsaw puzzle” that makes any attempts to reverse engineer the software return nothing but nonsense. Regular software can be fed into the system, and the resulting jumbled code can be run on any computer. Sahai and colleagues’ peer-reviewed paper on their research will be presented at a meeting of computer scientists in October. Collaborators included Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai and Brent Waters.

Previous research has attempted to obfuscate the code of software to make it more difficult to reverse-engineer, but these efforts could only slow down, not stop, an attacker. Sahai’s method results in software that would take “hundreds of years” to decrypt so that it could be reverse-engineered.

Sahai notes that encrypting software patches is just one of many potential applications for his work, which he describes as very basic science. “This is not something we thought of as being possible before, and we’re only starting to understand some of the implications it might have.”

Top News

Powered by WordPress.com VIP
Follow

Get every new post delivered to your Inbox.

Join 26,401 other followers