Posts

Understanding Sharing

1Password 4.2 for iOS has been released with a really nifty sharing feature. This allows you to conveniently share items with other people and keep them updated. Before getting into the details, it is important to know that the data is well encrypted within 1Password, but it is not encrypted when it is not in 1Password. In other words: share over secure channels and be sure you can trust your recipients. More on that later.

The overview

share-transparentIn 1Password 4.2 for iOS you can share an item (a Login, a Credit Card, or anything else in 1Password) by tapping on the share icon. You can then share the item by Mail or by Message. The recipient will just have to tap on the link in the message or email to easily import or update the item into their own 1Password keychain. It’s remarkably easy and convenient. It’s great for families, whose members need to share certain Logins and other 1Password items.

Just be sure to share with care. When you send one of these messages, anyone with copy of 1Password can import the item into their own library. So you will need to find a “secure channel” that is sufficiently secure for your needs. More on this, and so many other things, in the somewhat roundabout article below.

Even dogs can learn to share

Login for NewBarkTimes

Patty (one of my dogs) and Molly (the other) have a subscription to the New Bark Times.Patty set up the account and put the Login Password into 1Password. She uses it when she wants to read up on the latest techniques of how to steal the human food without getting caught. Molly – as a member of the same household – is also entitled to read the online edition. She likes to sniff the comics, which are mostly just depictions of dead squirrels. They are funny because the squirrels are dead.

Ways of sharing

So how do Molly and Patty share the Login information for the New Bark Times? I’m going to run through some sharing options, starting with the most cumbersome and finishing with the most convenient.  You can jump ahead to the section on using the new feature in 1Password 4.2 for iOS, but it is easier to understand what is going on and find what works for you if you follow along.

(Pass)word of mouth

Patty can simply tell Molly the password, and Molly can use that information to create an entry into 1Password. Note that Patty telling Molly the password and account details while they are both hiding under the bed constitutes “sharing over a secure channel”. They do so where Mr Talk (my neighbor’s cat) can’t listen in.

The advantage of this method is that it is the most secure. It is easier to arrange a secure channel for whispering something into someone’s ear than for transferring a data file with sensitive information. At least it’s easier for members of the same pack or household.

Any time Patty updates the information, she’ll have to tell Molly, who in turn, will have to edit her data. Likewise if Molly makes changes, Patty will have to manually (“pawually”?) edit her own 1Password data.   Wouldn’t it be nice to avoid all of those manual edits?

1PIF, two PIF

Before they got their paws on 1Password 4.2, Molly and Patty had worked out another way to share the New Bark Times Login. They didn’t like all of the manual editing, so they managed to share the Login by exporting and importing a 1PIF (“1Password Interchange File”) file with that Login. 1PIF files can be imported and exported to and from 1Password on Mac and Windows.

Patty would select the item and  use  File > Export Selected …  >  1Password Interchange File from the menubar. All Molly needs to do is import that 1PIF into her 1Password data, and not worry about manual editing.

1PIF files are not encrypted, so Patty and Molly need to use a secure channel to exchange them if they don’t want Mr Talk getting that data. They might use some file sharing over their local network, and they should remember to securely erase the 1PIF after it is done.

Sharing updates: Unique in all the world

There is another nice features about using 1PIFs this way. Every item created by 1Password has a Universally Unique Identifier (UUID). If Patty and Molly each create their own separate Logins for the New Bark Times, they will have different UUIDs even if their content is identical. But if Patty creates the item and exports it as a 1PIF for Molly to import, they will end up having the same UUID.

Here is where the magic comes in. If you import an item with a UUID of something that already exists in your data, 1Password updates the existing item instead of just creating a new one in your keychain (I’ll save the explanation for how we make sure that the UUIDs really are unique as a birthday present). If Molly modifies the New Bark Times Login, she can export it it for Patty to import, which will update the item in Patty’s keychain.

1Password 4 makes sharing even more convenient

Exporting and importing 1PIFs is fine as far as it goes for 1Password 3 for Mac and 1Password for Windows, but until now, 1Password for iOS didn’t have an import or export mechanism.

1Password 4.2 for iOS gained just such a sharing system, and it is extremely convenient.

Sharing a Login by MessageWhen Patty looks at the Login item in 1Password for iOS, she can tap the Share icon, then select “Message” or “Mail”. After that she should select “Message Login” or “Mail Login”.  These options share the 1Password item in a form that isn’t fit for humans (or dogs) to read. Instead, it uses an obfuscated format that your recipient can easily import into 1Password.

But note again, even though it isn’t designed for humans to read, its contents are still exposed to anyone, including the nefarious Mr Talk, who has access to 1Password. This is another reminder that Patty and Molly need to find a secure channel for sharing 1Password items.

The alternative Mail and Message format, “Mail/Message Clear Text”, puts the Login’s details in a human readable format. And it’s not just Logins that can be mailed or messaged. You can Mail Software Licenses, Message Credit Cards. Almost everything in 1Password can be shared this way; attachments are the only thing that don’t make the trip.

NewBarkTimes-import2When Molly receives the email or the message, all she needs to do is tap on the included link. At right, you can see what this looks like if the Login was sent by Mail.

The import will add a new item if the received item has a UUID that isn’t already in the recipient’s keychain. All Molly needs to do is approve the import of the new Login.NewBarkTimes-import1

Sometime later, Patty may update the item. She might add in a Note to the Login with the answer to a security question (Q: “Favorite pet”, A: “Me”).  Though of course, Patty should know not to give predictable answers to security questions, either.

NewBarkTimes-import3

After Patty has made some changes, she can just send the item to Molly again.

This time, 1Password will see that an item with the same UUID already exists in Molly’s data, so it will prompt Molly to see if she wants to update the item. Molly, of course, can also make changes and send the updated item to Patty.

This makes it really easy for Patty and Molly to share these items between their iOS devices via iMessage, which can provide a sufficiently secure channel for most purposes.

Finding a secure channel

As with 1Password’s other sharing methods (including word of mouth), Patty and Molly need to make sure that they have a secure channel. That is, they need to know that the message is going to the right person (don’t accidentally send it to Mr Talk); they need to know that it is coming from the right person; they need to know that nobody can listen in on the channel; and they need to know that nobody can tamper with the channel.

iMessage probably provides a secure enough channel for most people for most cases, though it may not be sufficient if you are trying to keep secrets from Apple or from law enforcement agencies. Even if you don’t anticipate attacks from those sources, there are a few cautions:

  1. It’s not always clear when a message will be sent by iMessage or via the much less secure SMS. Unfortunately, we haven’t (yet) found a way to make it clear from within 1Password when a message is going out over iMessage or not.
  2. It is often a bit too easy to accidentally send a message to the wrong recipient. So please take care that you really are sending it to the correct address.
  3. After a message or email has been sent and received, you should look at ways to delete the messages. For email, this is particularly difficult to do thoroughly, as most email servers create backups.

Molly and Patty might be willing to use one channel for sending their New Bark Times Login that they wouldn’t be willing to use for sending their First Bank of Canis Major Login. These are choices that only Patty and Molly can make for themselves.

Guess why we’re moving to 256-bit AES keys

1Password 4 for iOS icon1Password is moving to using 256-bit AES keys instead of 128-bit keys. We already started this within the browser extensions in the summer of 2011, and the new Cloud Keychain Format also uses 256-bit keys.

Why do you think we are making this move? If your answer is because AES 256 is stronger than AES 128, you’d be wrong. There is a technical sense in which AES 256 is enormously stronger than AES 128, but in every sense that actually matters for security there is no difference. Let me explain.

AES? Keys?

1P logo in AES

AES (the Advanced Encryption Standard) is a fundamental building block of the encryption within 1Password and most everything else that uses encryption in the modern world. It takes a key and some data (plaintext) as input and transforms that data into something that looks entirely random (ciphertext). The only way to get meaning out of the ciphertext is to use AES and the same key to transform it back into the plaintext. A key is just a number, and AES can work with keys of three different sizes, 128 bits, 192 bits, and 256 bits.

AES, by the way, is always a 128-bit cipher operating on 128-bit chunks of data (blocks) at a time; so when I use expressions like “AES256″ or “256-bit AES” in what follows, I’m just talking about key size.

If you’ve been curious about why 1Password didn’t jump on the 256-bit key bandwagon earlier or why we seem to be doing so now, read on. Even if those particular questions never crossed your mind, this article may give you some insight into what sorts of things go into security choices.

Talking about big numbers

The numbers that we need to talk about are just too big to write out normally. When we are dealing with numbers like 65536, I can opt whether to express it as “65536” or “216“, depending on what is most useful in the context. And maybe when dealing with a number like 232 I can say things like “4.3 billion”.

2128 in words

“three hundred forty undecillion, two hundred eighty-two decillion, three hundred sixty-six nonillion, nine hundred twenty octillion, nine hundred thirty-eight septillion, four hundred sixty-three sextillion, four hundred sixty-three quintillion, three hundred seventy-four quadrillion, six hundred seven trillion, four hundred thirty-one billion, seven hundred sixty-eight million, two hundred eleven thousand, four hundred fifty-six”

But the numbers we deal with in cryptography are so big that I have to write them in exponential form. The number of possible keys that a 128-bit key allows is just too enormous to write otherwise. Sure, I could write out 2128 in words with the help of a numbers to words converter, but it is neither informative nor manageable. Nor would it be useful for me to write out the number in decimal, as it would be 39 digits long.

And one more thing about writing numbers in words: when I do so here, I will be using the US English, short scale, conventions; “billion” means 109, not 1012.

Searching for keys is harder than digging up bones

Molly (one of my dogs) doesn’t really enjoy dog toys that much, but she will certainly not allow Patty (the other dog) to play with any toys. Molly, then, steals and hide Patty’s toys. Suppose that Molly has a possible 2128 sniff-proof hiding places she can hide them in. Also suppose that Patty knows about all of those hiding places, but she doesn’t know which one Molly has used. Patty might try to look in each one until she finds her toys. Searching each and every one of those 2128 hiding places until she finds the one with the toy is what we’ll call a brute force attack.

1/2 X 2^{128} = 2^{127} On average, Patty will find the right one after searching about half way through all of the hiding places. This means that, on average, she’ll have to try 2127 hiding places before she finds her toys. If you thought it was going to be 264, pause for a moment. In fact, 2128 divided by 2 is 2127. Each additional power of two doubles the number, so halving the number means just taking one off of the exponent.

Molly might imagine that, to be extra secure instead of using “only” 2128 possible hiding places, she might use 2256 possible hiding places. 2256 is enormously bigger than 2128. Hugely bigger. Unimaginably bigger. Mind-boggingly bigger, though to be honest, the number 2 is enough to boggle Molly’s mind. In fact, 2256 is 2128 times bigger than 2128.

Now, I just said that moving to  2256 hiding spaces makes the number of places that Patty would need to search unbelievably, enormously, mind-bogglingly bigger. But Molly would be wrong to think that this made it more secure. Why? Because searching through “only” 2128 hiding spaces is already so mind-bogglingly, amazingly and unimaginably hard that there is no gain in making it harder.

How long is long?

Cray XMPPatty is a very fast dog – well, at least in her youth she was. Even today, over short distances, she can outrun Molly, who is ten years her junior. So let’s imagine that Patty could search hiding spaces as quickly as a super computer can add two numbers. Actually, let’s suppose that she gets together with a billion other dogs, each of which can search a hiding place as quickly as it takes a super computer to add two numbers. Working at this unimaginable speed, these billion super fast dogs working under Patty’s direction might be able to search 250 hiding spaces per second, which is about one quadrillion hiding spaces per second. There are about 31557600 seconds per year, so working like a billion super computers, Patty with her friends could check about 275, or 10 septillion, hiding places per year.

NASA-universe-timelineAt that rate it would take 253 years (10 quadrillion years) to work through half of the 2128 hiding spaces. If we take the universe to be about 15 billion years old, then the amount of time it would take Patty, working faster than the combined power of a billion super computers, would be more than 600,000 times the age of the universe.

In case my analogy has gone too far astray, I’m estimating that, as an extremely fast estimate, all of the computing power on Earth turned to trying AES keys couldn’t check more than 275 keys per year (and really that is a very very high estimate). At that rate, it would take more than half a million times the age of the universe to go through half of the 2128 possible AES keys.

Now, single-minded Molly, who will spend an entire day barking at a squirrel up a tree, may think that half a million universes ages isn’t too long to wait. But nobody else would even consider trying such a brute force attack. Patty is a clever dog, and so she wouldn’t even consider trying a brute force attack on 2128 hiding spaces.

Patty might try other attacks. She might figure that Molly didn’t pick the hiding place in a truly random fashion, and so Patty might know which sorts of places to search first. Or Patty might try to secretly follow Molly to the hiding place. Or maybe there is a way that Patty can trick Molly into bringing her the toys. Those are the kinds of attacks that Molly needs to defend against. But she gains nothing by increasing the number of possible hiding places, because even if Patty had all of the resources on Earth searching Molly’s hiding places, Patty couldn’t even make a dent before the universe comes to an end.

The difference between zero and zero is zero

The chances of Patty and all of her super fast friends finding Molly’s hiding spot is as close to zero as we could possibly want. Let’s call Patty’s chances in this case ϵ1 (epsilon 1), a really small number.  If Molly uses 2256 possible hiding spaces instead of 2128, the chances of Patty and her friends finding the one with the toys is another number as close to zero as we could possible want. We’ll call these chances  ϵ2 (epsilon 2). Sure, ϵ2 is many times smaller than ϵ1, but both ϵ1 and ϵ2 are already as close to zero as we could possibly want. Molly’s practical security gain in using the larger number of hiding spaces is pretty much the difference between ϵ1 and ϵ2. That difference, for all meaningful purposes, is zero.

It takes a lot of dog food to keep Patty searching

Boltzmann tombstone src: http://www.engr.ucsb.edu/~shell/che210a/We all know that dogs like to eat. And we all know that computers consume electricity. As it happens, computation (and inspecting hiding places) has to consume energy. It’s actually the destruction (or overwriting) of information that necessarily consumes energy, but that happens when Patty forgets about a previous hiding place so she can think about the next one. If Patty and her friends could move on to checking a new possible key using the absolute theoretical minimum energy for a single computation, 2.85 × 10-21 J, she and her pack of billion super fast (and now unfathomablely  efficient) of dogs would require about  1/100th of the total amount of energy humanity uses in a year to work through half of the 2128 hiding spaces.

The answers to some questions remain TOP SECRET

Central Security ServicesI have tried to explain all this to Molly countless times, but she just stares blankly as if to ask, “Well, then why does the US government require 256-bit AES keys for TOP SECRET material?”  Actually, all Molly says with her stares is, “Huh?”. I tend to read a bit more into these than is really there. My only answer to her is that it is the same reason that she likes being blow dried after a bath on her left side, but hates it on her right side. Some things, in the mind of Molly and in government, remain a mystery.

I have some reasonably charitable speculation for why those requirements are there, but it remains speculation, and we can continue that discussion in our discussion forums.

Are 256-bit keys less secure than 128-bit keys?

When Bruce Schneier advises:

[F]or new applications I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the [foreseeable] future. But if you’re already using AES-256, there’s no reason to change.

people need to pay attention. But paying attention and evaluating doesn’t always mean agreeing.

Briefly, there is a long-known problem with how AES deals with 256-bit AES keys. (Of course in this business a “long-known problem” means about 10 years old.) AES does multiple rounds of transforming each chunk of data, and it uses different portions of the key in these different rounds. The specification for which portions of the key get used when is called the “key schedule”. The key schedule for 256-bit keys is not as well designed as the key schedule for 128-bit keys. And in recent years there has been substantial progress in turning those design problems into potential attacks on AES 256. This is the basis for Bruce Schneier’s advice on key choice.

One of the two reasons why I reject Schneier’s advice is that the issue with the AES 256-bit key schedule only opens up the possibility of a related key attack. Related key attacks depend on things being encrypted with keys that are related to each other in specific ways. Imagine if a system encrypts some stuff with a key, k1 and encrypts some other stuff with a different key, k2. The attacker doesn’t know what either k1 or k2 are, but she does know the difference between those two keys are.  If knowing the relationship between keys (without knowing the keys) gives the attacker some advantage in discovering the keys or decrypting material encrypted with those keys, then we have a related key attack.

Aircrack-ng logo. src: http://www.aircrack-ng.org/

When cryptographic systems are properly designed, related key attacks should not be relevant because good crypto systems shouldn’t use or create related keys. Cryptographers worry about related key attacks on AES because they know that some systems will be poorly designed, so it is still important to build ciphers that aren’t vulnerable to related key attacks. A spectacular case of using related keys with a cipher (RC4) for which related key attacks were easy was probably the design WEP WiFi encryption standard. This is one of several reasons why it is possible to discover a WEP Wi-Fi key after just a few minutes (though remember: Just because it’s easy doesn’t mean it is right or legal).

Each and every encryption key used in 1Password is selected independently using a cryptographically appropriate random number generator. This means that there is no way for an attacker to know of any relationship among keys used or generated by 1Password. There is no relationship among keys.

So why 256 bits now?

I hope I’ve persuaded you that 256-bit AES does not reduce any meaningful threat. Essentially it reduces the chance of a successful brute force attack from effectively zero to effectively zero.

So why are we moving to 256-bit AES keys?

1. There is no longer any reason not to move to 256-bit keys

61Password data needed to be encrypted and decrypted on first generation iPhones. Lots of encryption operations using 256-bit keys would have been slow and would drained batteries faster. On desktop computers, we were able to move to 256-bit keys within our 1Password browser extension. But for our principal data format – the one that is used across platforms – we needed to consider the minimal hardware it would run on.

1Password 4 for iOS requires iOS version 6 (which includes development features that allows for our awesome new Web Mode). This means all the devices 1Password 4 will run on are sufficiently powerful that we no longer need to be concerned about performance issues with 256-bit keys.  The performance concerns that we had in the past—both speed and power consumption—are no longer a concern today.

2. Tougher key derivation

This one is subtle. And I’d like to thank Solar Designer of the Openwall Project for drawing my attention to this. It turns out that a side effect of using 256-bit keys in 1Password can make things even harder for automated Master Password guessing programs, not because such keys are harder to attack, but through a more convoluted chain. Don’t worry if you find this section confusing.

1Password uses PBKDF2 to slow down password crackers that could be used to automate guessing your Master Password if someone gets hold of your data. PBKDF2 is a Key Derivation Function – a system that churns your Master Password into a number that can be used as an encryption key. With our new Cloud Keychain Format, we use PBKDF2 to turn your Master Password into two 256-bit keys. One is an HMAC key, used for an integrity check on the data; and the other is a key used to actually decrypt the master key. To derive that total of 512-bits from your Master Password, 1Password uses HMAC-SHA512 within PBKDF2 in the Cloud Keychain format.

Password cracking systems, like hashcat, can speed up their operations by using GPUs (Graphic Processing Units) which can perform some kinds of computations blindingly fast, but there are some computation artifacts of SHA-512 that make this harder on GPUs. Solar Designer mentions this in his discussion of the future of password hashing (slide 35 and elsewhere).

I did warn you at the beginning of this section that this particular reason is convoluted and subtle. The short version is that a side-effect of using 256-bit AES keys is that it makes PBKDF2 more effective in certain circumstances.

3. People (and Molly) feel better about 256-bit keys

In which I threaten to shoot someone for using the expression "military grade 256-bit AES"If Molly feels that 128-bit keys aren’t sufficiently secure, she may incorrectly reject systems that use 128-bit keys instead of 256-bit keys. In doing so, she may make choices that actually weaken her security overall. I might not agree with her reasoning, but we do have to recognize that her feelings do matter to her choices. And I certainly want to keep Molly secure. So if by offering 256-bit keys we enable Molly to make better security choices (even if for the wrong reasons), that is a good thing.

As long as there is no reason not to use 256-bit AES keys, it makes sense to use them. We have now reached the point where there is no harm in using 256-bit keys, and so the reassurance that comes with using them is worthwhile.

Now, security is a tough business. And tough people in a tough business can talk tough. When I threatened to shoot somebody if we used the expression “military grade” to describe our use of 256-bit AES keys, I wasn’t expecting that I’d have to shoot the guy who signs the checks. But a promise is a promise. So, Dave Teare, the gauntlet is down. Water pistols at dawn!

In conclusion

If there is any overall lesson here, beyond explaining why we’ve made the choices we have about key size for 1Password, it’s that seemingly simple questions about security and cryptography rarely have simple answers and explanations. On the one hand, we want people to understand what goes on under the hood and the thinking that goes into various design elements; but we also want to make it easy for people to behave securely without requiring that they understand what’s going on at the deeper levels.

A quantum of bits [Update: March 20, 2013]

I reached out to the cryptographic community for any insight into Molly’s question about why the NSA insists that TOP SECRET material be encrypted using 256-bit keys. The answer came from Steven Bellovin of Columbia University:

@jpgoldberg @marshray Just heard that during the AES competition, NSA said in the open meetings it was for defense against quantum computing

Quantum computers, if they are every made practical, will be able to do amazing things. They will certainly change how we design cryptographic systems. It’s not that quantum computers will be faster or more powerful. Indeed, in some very important respects they will be less powerful than current computers. But there are some things that they will be able to do in less “time”.  I put “time” in scare quotes because it has a different meaning in this context from the ordinary use of the word. Oh, what a big difference it is. In this context it means the number of distinct steps an algorithm must take in performing some computation.

Searching through 2128 keys (on a classical, non-quantum, computer) takes a number of steps that is proportional to 2128. But for a quantum computer it takes a number of steps proportional to the square root of that number, 264. If a quantum computer is ever built capable of performing that task, we don’t know how the actual speed of each individual step will compare to those of current computers, but the NSA is taking no chances. Something with the effective strength of a 64-bit key isn’t strong enough. A 256-bit key against a quantum brute force attack would have the effective strength of a 128 bit key against a classical brute force attack.

I very much doubt that we will see a quantum computer actually capable of handing such things within the next thirty years. But if the past is any guide, my predictions about the future should be taken with a large grain of salt.

 

Authenticated Encryption and how not to get caught chasing a coyote

Enigma machineI introduced HMAC (Hash-based Message Authentication Code) through the back door when talking about the Time-based One Time Password (TOTP) of Dropbox’s two-step verification. But TOTP is actually a peculiar way to use HMAC. Let’s explore what what Message Authentication Codes (MACs) are normally used for and why they play such an important role in the future of 1Password. If you guessed that MACs are for authenticating messages, you’re on the right track.

In a sense (but this is a lie), you can think of MACs as kind of like encrypting things that aren’t secret.  The recipient doesn’t decrypt the data, instead the recipient verifies that it really was the data sent by the sender and that the data hasn’t been tampered with. MACs work with the sender and the recipient both sharing a secret key. (This is the key difference between MACs and digital signatures. With MACs, the sender and the recipient share the same secret key.)

Only someone with knowledge of the secret MAC key could have created the MAC for some data, and (unlike the case of digital signatures) only someone with knowledge of the secret MAC key can verify that the MAC is valid for the data.

 Why use a MAC?

Suppose my dog Patty (the clever one) leaves a warning for Molly (a simple dog) that says, “There’s a coyote in the back yard”. The message isn’t secret. Neither Patty nor Molly care who reads it. But now suppose that the neighbor’s cat, Mr Talk, in his attempt to get rid of Molly, changes the message to “There’s a squirrel in the back yard”. HMAC diagram This would not be good news for Molly, who would blindly run behind the house, chase a squirrel up a tree and then bark at it for the next thirty minutes. Coyotes, however, do not climb trees; and so Molly would have an entirely different experience if she tried the same action against a coyote.

To avoid tampering with the message, and to prevent Mr Talk from sending a counterfeit message in Patty’s name, Patty and Molly can share a secret key which is used to create a MAC of the message. Suppose that Patty and Molly, ignoring earlier advice on creating passwords, have secretly agreed on the key (well, a password from which a key is derived)—”Kitty Smells”—for their MACs. When Patty constructs the message, she will calculate the MAC (and if she is using HMAC with SHA1 as the hashing algorithm) with ‘Kitty Smells’ as the password, the HMAC should come out as:

a3b3a8b79c135ff5b9a0aa6f5c304b411f07f90c.

Patty will leave the message, “There’s a coyote behind the house”. along with the MAC.  When Molly sees a message, she should verify the MAC before even looking at the contents of the message."There's a squirrel in the back yard" Forged document with HMAC If Mr Talk has changed the message to say “squirrel” instead of “coyote,” the MACs won’t match up. Mr Talk cannot create a valid MAC because he doesn’t know the shared secret password used to create the secret key that Molly and Patty have.

Sadly, Mr Talk’s trick will still work.Molly transfixed by "squirrel" That is because as soon as Molly encounters the word “squirrel” she will react. All thoughts of verifying the MAC will be pushed out of her brain, which will now be entirely occupied by the single thought, “squirrel”. Indeed, if I were reading this aloud, Molly would have run out the back in blind excitement.  This is why it is very important to not even look at the contents of a message before verifying its authenticity.

MACs on encrypted data

In this example, the original message isn’t secret and so didn’t need to be encrypted. But with authenticated encryption, we first encrypt the message with an encryption key and then compute a MAC of the encrypted text using an authentication key. Just as it was important for Molly to not do anything with the message until she verified the MAC, it is vital that we don’t try to decrypt an encrypted message before verifying the MAC. This system is called “Encrypt-then-MAC”, but the emphasis should be put on the other end of the process. I like calling it “Verify-then-decrypt”.

A scheme like Encrypt-then-MAC that both encrypts a message and provides authentication (proof of who it came from) is called “authenticated encryption”. Encrypt-then-MAC isn’t the only secure authenticated encryption scheme out there, but it is the one that we use in the 1Password 4 Cloud Keychain format.

It’s already encrypted with a shared secret. Why verify?

You might think that there is no reason to authenticate encrypted data. After all, the data was encrypted with a secret key, so if you can decrypt the message with that secret key, then you know it only could have been encrypted by someone with knowledge of the secret key. Many people have thought that, but they were wrong.

Suppose that Molly sends an encrypted message to Patty, but doesn’t use authenticated encryption. Now when Patty gets a message from Molly she decrypts it. If the decrypted message is garbled in a specific way, Patty tells Molly that it didn’t decrypt properly and that Molly should send it again. If it isn’t garbled in a particular way, Patty will just let Molly know she got the message.

Padding oracleMr Talk can listen to this exchange between Patty and Molly. Without the secret encryption key, Mr Talk won’t be able to figure out what is in the message that Molly sent to Patty. But now suppose that Mr Talk is able to send encrypted messages (seemingly from Molly) to Patty. Mr Talk can send Patty modified forms of the message that Molly sent and find out whether Patty got a garbled message when she decrypted it. Mr Talk makes small changes to the original encrypted message to create a bunch of new slightly different encrypted messages. By finding out which ones are garbled and which ones aren’t, Mr Talk can actually decrypt the original message. This is a type of “Chosen Ciphertext Attack (CCA)”. It is called this because the attacker is able to choose ciphertext for the recipient to attempt to decrypt.

Now, the particular attack that Mr Talk used depends on the precise details of how Patty determines whether a message was garbled. That means changing those details can defend against this particular attack. Those who are familiar with all of this will know that I’m talking about the “padding oracle attack”, and will know that it can be defended against by using different padding or using a different encryption mode. But such a defense only addresses this particular attack. Is there a way to defend against all CCAs, even those that haven’t been invented yet?

The good news is that it is possible to defend against all Chosen Ciphertext Attacks. The way to do that is to properly use authenticated encryption. Padding or other “oracles” are not a particular threat to 1Password, as there is no back-and-forth exchange in normal operation. These sorts of attacks are practical when there is an automated oracle on the network or in a specific device that will attempt to decrypt ciphertext on demand. In 1Password, there is no opportunity for an attacker to set up the kind of dialogue needed for this kind of attack.  But we also know that theoretical weaknesses have a habit of turning into exploitable weakness over time. So we look ahead, and build authenticated encryption into 1Password now.

What happened to Molly?

I am pleased to say that no harm came to Molly or the coyote.  She was on her leash, and you can see in this staged and contrived photo that I was – just barely – able to restrain her from running to her doom after a coyote. However, our attempts to teach her that she must verify messages before she does any other processing of said messages have not gone well.

Restraining Molly