Posts

Do you know where your software comes from? Gatekeeper will help

Mountain LionYou trust us to provide you tools that keeps some of your very valuable secrets safe. Part of that trust means that, when you install or update 1Password or Knox, you know the app you are getting comes from us. After all, if a bad guy produces a modified version of 1Password, it could do bad things. So far there have been no such modified versions “out there” and we want to keep it that way. In addition to all of the things that we do to ensure that you get the genuine article, Apple is working to make it even easier to keep your Mac free of malicious software.

Apple has just announced that Mountain Lion (to be released in the summer of 2012) will include something called Gatekeeper. This is a core OS X feature that I and others have been anticipating for a while. (surprisingly, almost all of its components are actually built into the latest version of Lion). Roughly speaking, Gatekeeper will allow you to control which apps to run depending on where the software comes from.

The question then is: how does your Mac know where your software comes from?

The Magic of Digital Signatures

I would love nothing more than to explain the mathematics behind digital signatures. But for today’s purposes, let’s just say it is magic (even when you know the math, it feels like magic). When you connect over HTTPS to a secure website, that website proves who it is because it knows a particular secret (called a “private key” or “secret key”). The corresponding “public key” is not kept secret.

The magic is that the website doesn’t have to reveal the secret to prove that it knows it.

Evilgrade

Evilgrade Interface

Instead your computer system can use the non-secret public key to construct a mathematical puzzle that only someone who knows the secret key can solve; anyone with the public key can check that the solution to the puzzle is correct, but they can’t figure out what the secret key is. This can prevent someone hijacking the download process with a tool like evilgrade.

In the same way that a secure website can prove who it is without revealing any secrets, a digital signature on a file (or a group of files) can prove who made it. If someone makes even the smallest change to the signed file, the signature won’t verify.

Three Kinds of Apps

Applications that you install through the Mac App Store (MAS) are all digitally signed this way. But for years, Apple has been encouraging developers to digitally sign applications even if they aren’t sold through the MAS. So on your Mac today there are probably three kinds of applications:

  1. Those that came from the MAS
  2. Signed applications that did not come through the MAS
  3. Applications that aren’t signed

Gatekeeper will allow you to decide which of these categories of applications may run on your machine.

If you are running 1Password 3.9, then that came signed through the MAS. But if you are running 1Password 3.8 or Knox 2 from our website, they are still signed by us and will fall into the second category.

Verifying a signature today

When you install an application from the Mac App Store, the installation process checks the signature. It won’t install the app if it isn’t signed or if the signature doesn’t verify (which is more likely to happen through a damaged download than through a malicious attack, but both can happen). When you update the non-MAS version of 1Password, our updater runs a code signing signature verification as one of the three checks we use to ensure that you are getting the genuine 1Password from us. For those who are curious, our other two verification mechanisms are (1) fetching from a secure web server and verifying the server signature, and (2) checking a cryptographic checksum for the download which we fetch from a separate secure server.

But suppose you wanted to check the version of 1Password that you currently are running. All of those behind-the-scenes checks on the download and installation processes won’t help you do that. Well, the way to check now is hard, which involves running a complicated command in a Terminal window. Here it is for the non-MAS version of 1Password

codesign -vvv -R="identifier ws.agile and anchor trusted" \
/Applications/1Password.app

The output should be something like

/Applications/1Password.app: valid on disk
/Applications/1Password.app: satisfies its Designated Requirement
/Applications/1Password.app: explicit requirement satisfied

Clearly we don’t expect users to run these sorts of commands.

codesign in Terminal

We have been using Apple’s code signing mechanism for years because we wanted to be able to direct concerned users to this kind of command if they specifically ask. We’ve also been using it for additional security in our own updater. But another reason that we’ve been doing this for a while is because we’ve been anticipating either Gatekeeper or something similar.

Verifying a signature tomorrow

Gatekeeper will perform the codesign verification when an application is launched. This adds a great level of additional security beyond verifying the download source when the application is downloaded and installed.

A mathematically valid signature is the easy part

Apple Developer IDThe mathematics (the magic) makes all of the above simple. The hard part of Gatekeeper is the trustworthiness of the signatures. I can sit at a my computer and create a public/private key pair that says that it belongs to Alan Turing. Since Turing has been dead for more than half a century, few people would think that it actually belongs to that great mathematician and codebreaker. But what if I picked the name of a trusted person or institution that is around today?

The answer is that some trusted third party digitally signs my public key after verifying it belongs to who it says it belongs to. I’ve discussed how this system works (and how it can break down) when it comes to web server certificates, so I won’t repeat that here; the concepts are all the same. In the case of codesigning certificates for Mac developers, Apple does that checking and signing.

We changed our name a while back, so at some point before Gatekeeper is in common use, we will have to update our codesigning certificate identifier from “ws.agile” to “com.agilebits”. But for the time being, when you see “ws.agile” as the entity behind the digital signature on 1Password and Knox, you should know that that is us.

Other than getting a new certificate with our new name, we have been ready and waiting for years to get on board with the new security provided by Gatekeeper.

[Update: As of 1Password 3.8.19 Beta 1, 1Password is now signed with our new Apple Developer ID, AgileBits Inc.]

AES Encryption isn't Cracked


An otherwise excellent article over at The Inquirer has a very unfortunate title: AES encryption is cracked. AES is the Advanced Encryption Standard and is at the heart of so much encryption used today by governments, militaries, banks, and all of us. It is used by 1Password and less directly by Knox for Mac. It is the work horse of modern cryptography, and modern computer chips even have components built is to allow AES to be used efficiently. If AES were to be found weakened in any meaningful way, it would be very bad news for a lot of people.

Before I get into what has happened, I’d like to quote from the research paper itself: “As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

And quoting the Inquirer’s interview with Andrey Bogdanov, one of the researchers, we learn

“To put this into perspective: on a trillion machines, that each could test a billion keys per second, it would take more than two billion years to recover an AES-128 key,” the Leuven University researcher added. “Because of these huge complexities, the attack has no practical implications on the security of user data.” Andrey Bogdanov told The INQUIRER that a “practical” AES crack is still far off but added that the work uncovered more about the standard than was known before.

“Indeed, we are even not close to a practical break of AES at the moment.”

What’s the news

I’ve been trying to work through the actual paper and presentation slides by Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger who were visiting Microsoft Research when they developed this. And although this research is far from having any practical influence on the use of AES it is actually fairly big news.

Cryptographers use the word “broken” in a very special way. If an attack on an algorithm can be computed with fewer computations than is required to check every single possible key, then the system is “broken”. Even if the improvement in the number of computations is negligible (as in this case) and even if other resources needed to get that small advantage are outrageously huge (again as in this case) it still gets called “broken”. But in this very specialized sense of the word “broken” the new research represents the first break of the full AES. It also displays the power of a technique developed earlier by the authors.

Impracticality #1: Impossible amounts of data

The authors calculate the best attack using their technique on AES with a 128 bit key requires storing 288 bits of data. That works out to about 38 trillion terabytes of data. Although estimates are hard to pin down, this is more than all the data stored on all the computers on the planet.

Impracticality #2: All for a two-bit gain

The number of encryptions that have to be performed to recover a 128 bit AES key is 2126.1 instead of the 2128 encryptions it would take to try all of the possible keys. This is a very small gain, as a 126-bit key (instead of 128-bits) would still take billions of years.

Impracticality #3: Lots of known plaintext needed

I may be misreading the research, but I believe that to discover an AES key, an attacker needs an enormous amount of known plaintext. That is, the attacker needs to already have a huge amount of information in both decrypted and encrypted form. I don’t know exactly how “huge” this will be, but I expect it to be far larger than any data anyone would or could encrypt using 1Password. I’m speculating here until I get a better grasp of things. Indeed, the amount is almost certainly related to the amount of data needed in “Impracticality #1″.

So this all doesn’t represent any threat to the practical use of AES for any purpose it is used for. An unfeasible amount of data needs to be stored in order to gain an insignificant improvement over just trying every key. But what it does do is highlight features of AES that make it subject to this kind of attack. Whether attacks based on this ever become any kind of real threat, we can bet that successors of AES will incorporate mechanisms to thwart them.

Where’s the meat? It’s in the middle

From here on out, I will try to explain some of what I understand from the new attack. There is much that I don’t understand of this, but I will give a broad outline and then wave my hands a bit. This part gets very technical, and I won’t be the slightest bit hurt if you stop reading here.

You may have heard of 3DES (Triple DES) which was used in many places before AES was settled upon as a replacement. The old Data Encryption Standard (DES) uses 56 bit keys. By the time we got into the 1980s it was absolutely clear that 56 bits was no longer enough for a key size. One could imagine (as many people did) taking two DES keys and just encrypting your data twice, first with one DES key and then taking that output and encrypting that with the second DES key. This, you might think, would get you the strength of a 112 bit key. It doesn’t.

It turns out that if you have an sample plaintext and ciphertext pair what you can do is try everyone one of the 256 possible keys on the plaintext and also try everyone of the possible keys on the ciphertext as well. You will then find that there is an overlap of results. Some things that the plaintext encrypts into with one key will be the same as what the ciphertext decrypts into. This will give you (pretty much) the two 56 bit keys. This looking for where the output of one can meet up with the input of the other leads to this being called a “meet-in-the-middle” attack (not to be confused with a “man-in-the-middle” attack which is something else entirely). Note that in doing this, we “only” had to work through 256 keys twice. That is the same as working through 257 once. So double encrypting with DES only improved the security by one bit. This is why to get 112 bit strength out of DES we need to go through it three times, and so even though it allows for double the number of key bits, it is actually Triple DES.

Meet-in-the-middle diagram

Now back to AES. Ciphers like AES go through multiple rounds of scrambling and manipulating the data. They also have various internal states as they process a block of data with a key. If we find an internal variable that allows us to break the encipherment into two halves then it is possible to do a meet-in-the-middle attack on that. AES, along with every modern cipher, is designed with this in mind. It is designed with enough rounds and interactions among them so that a standard meet-in-the-middle attack will not be quicker than simply trying every key.

Instead of doing the traditional meet-in-the-middle attack, the new attack constructs entities that group internal states, potential keys which complement each other in specific ways, and ciphertext into what they call “bicliques”. By using these more abstract entities instead of an intermediate variable, the attack can avoid some of the limitations on meet-in-the-middle attacks and be effective over a greater number of rounds. By carefully selecting which potential keys go into which biclique, some computation can be reduced by avoiding any duplication of effort. I still haven’t managed to understand, even in overview, how and why these bicliques do what they do, so I can’t say much more.

Thanks for joining me

If you’ve read this far (including the last section) then I thank you for joining me through my process of trying to understand this new attack on AES. Even though it has no practical implications, I find this stuff oddly fascinating. If you’ve just skipped right to the bottom (not an unreasonable thing to do at all) then let me say again everyone who has studied this, including the authors of the attack, state that this has no implications whatsoever for the practical use of AES.