Time to give 1Password 4 for Mac’s Security Audit a whirl

1Password Security AuditIt was bound to happen eventually. A massive Adobe data theft of 130 million customer names, emails, encrypted passwords, source code, and more will enable almost limitless password reuse attacks in the coming weeks.

Suppose you are one of the 130 million people who’s oddly encrypted passwords were among the Adobe password breach. Suppose that you used the same password there as you do for PayPal.

To make matters worse, suppose you actually listed that fact in Adobe’s password hint. Since the malicious attackers dumped the Adobe data online, a quick check of Adobe customer password hints shows that there are more than 700 that say things like “paypal” or “sameaspaypal”. There are more than 20,000 hints referring to “bank”. I will talk about password hints at some other time; my point here is all about password reuse.

Only a fraction of the people who are reusing passwords will make that clear in their password hints. We already know password reuse is common. We also know that criminals do indeed exploit password to steal from people.

I am very tempted to explain all about Adobe’s peculiar method of storing passwords. It’s really a cool story with lots of interesting lessons, and explaining it would involve poorly encrypted pictures of a penguin.

I am also tempted to dive into gory details of the statistical properties of the data, the analysis of which has kept my computer busy for days on end. Likewise, I could rant about Cupid Media’s failure to encrypt or hash passwords for 42 million customers. Or I could talk about privilege escalation and the MacRumors discussion forums breach of 860,000 hashed passwords a week earlier, leading to the capture of all 860,000 hashed passwords.

But it is far more important for me to repeat what we’ve said in many different ways and at many different times: Password reuse—using the same password for different sites and services—is probably the biggest security problem with password behavior.

We want to fix that.

Knowing the right thing to do is easier than doing the right thing

Like most people, you weren’t born using 1Password, it’s something that came to use later in life. Now that you use 1Password, you will (or should) be using the Strong Password Generator when you register for a new website so you get a strong, unique password.

But think back to those dark days when you needed to come up with passwords on your own. You probably picked from a small handful that you had memorized, so now you’re stuck with a bunch of sites and services for which you used the same password.

Security Audit selections

Getting all of those old passwords sorted out is going to be a chore, but it doesn’t have to be done all at once. Best of all, 1Password 4 for Mac can help, thanks to its new Security Audit feature.

Let’s use an analogy: say that Molly (one of my dogs, and not really the cleverest of beasts) has just started using 1Password. She has a few passwords, but not many. Even though she doesn’t know how to push open a door that is already ajar, she can make use of the new Security Audit tool in 1Password for Mac.

In the left sidebar of 1Password 4 for Mac, down toward the bottom, there is a section called “Security Audit”. When Molly clicks (or paws) “Show” next to “Security Audit” she sees a number of audits available. She can select “Weak Passwords”, which will show her all of her items with weak passwords. She can also look at password items that are old. But the selection we are interested in today is “Duplicate Passwords”.

Security Audit: Molly's duplicates

Security Audit in 1Password 4 for Mac, displaying Molly’s duplicate passwords

What Molly sees is that she has two sets of duplicates. One of them is used for two Logins, and the other one is used for four Logins. As we can see, her Adobe.com password of “squirrel” is used for her Barkbook, Treats R Us, Cat Chasers Logins as well.

Molly transfixed by "squirrel"Molly should, of course, go to each of those sites and change her passwords on them. But there are squirrels in the back yard to bark at, and changing all of those passwords may seem overwhelming. So Patty (the cleverer dog in the family) advises Molly to think about which of those Logins are most crucial. Molly can’t tolerate the thought of anyone else getting a treat; so she starts with Treats are Us.

This does mean going to the Treats are Us site and using its password change mechanism. 1Password is smart, but it isn’t quite smart enough to go browsing through the sites to find their password change pages. Molly may decide that her Barkbook Login is also very important, and so will change that one right away as well.

Ideally, Molly should fix all of her weak and duplicate passwords as soon as possible. And as Molly has only a handful of Logins, she could do that. But for those of us who may have a large number of old accounts, it is probably best to check Security Audit and update reused or weak passwords at the most important sites first. Then, updating other passwords a few at a time is an easy way to make all our accounts much more secure.

1Password and The Crypto Wars

Of all of the revelations about the NSA that began in June and continue to this day, the one that has shocked me the most is the fact that the United States National Security Agency has been deliberately inserting weaknesses into security products and even into NIST standards. In light of this, it is fit and proper for anyone who relies on 1Password for their security and privacy to ask whether 1Password has been, or could be, tampered with to deliberately weaken it.

The easy questions

Has 1Password been deliberately weakened?

No.

Have we, AgileBits, ever been asked/compelled/pressured/contacted by any entity asking us to weaken 1Password?

No.

Could we be compelled to weaken 1Password or allow for the weakening of 1Password?

Not without substantial risk that such attempt would become public.

Those questions are the easy ones to answer. The harder question is why you should believe those answers.

Why should you believe us

It is impossible to absolutely prove that our answers to the easy questions above are truthful. But what I can do is provide a number of more verifiable claims, each of which makes it harder for us to lie about any of this. In combination, these should be enough to persuade you that there is no backdoor (deliberate weakness) in 1Password and that it would be very unlikely for one to be introduced.

They can’t gag all of us

We have developers in four separate countries: Canada (AgileBits is a Canadian company), the United States, the United Kingdom, and the Netherlands. The gag orders that accompany National Security Letters in the US would not bind non-US citizens outside of the US. Likewise the Canadian, British, or Dutch analogues to National Security Letters wouldn’t bind US citizens. To compel all of us to betray our customers and principles, they would need to coordinate that legal compulsion in four jurisdictions.

This doesn’t entirely rule out the possibility of such a set of gag orders, but it does make such compelled silence much harder to achieve. This also doesn’t rule out other avenues of attack. In particular, could just one or two people within AgileBits sneak in a backdoor? We’ll talk about that below, but note that the inability to gag so many of us means that a backdoor would have to remain unknown to most of us.

Our lack of data collection is verifiable

Your 1Password data is under your control. Out of the box, 1Password creates a local data file (your “vault”) and sync is disabled. We never have the opportunity to see your Master Password or even your encrypted 1Password data. 1Password not only gives you “end-to-end” encryption, but our overall design means that we are never in a position to turn over or intercept your data. We simply never see it in any form whatsoever.

Furthermore, we never see how you use 1Password. We don’t know what sites you log into, we don’t know how many 1Password items you have. Indeed, we don’t even know whether you use 1Password or not. We offer a soon-to-be-incremented number of data synchronization methods, none of which involve us ever having the opportunity to intercept your data. When 1Password 4 for Mac arrives soon, Wi-Fi sync (currently in testing) will allow you to sync locally, meaning your data never has to leave your local network.

You can monitor 1Password network activity for yourself to confirm that your data, even encrypted, is never sent to us. All of this dramatically reduces where a backdoor could be inserted.  Indeed, it eliminates the otherwise easiest to insert and most difficult to detect backdoors. So an entire range of attacks is already off the table.

As always, this doesn’t rule out all kinds of mischief, but it substantially limits the scope and opportunity for an attack.

Our data format is verifiable

We have been very open about providing the details of the encryption and data format that 1Password uses. Anyone can verify that 1Password does produce the files we say it does. They can also examine whether that over all design is strong.

This doesn’t rule out every kind of sabotage that could be done, but it does rule out a broad range of some of the easiest lines of attack. Because this limits where a weakness could be introduced, it’s harder for a deliberate weakness to be introduced that isn’t noticed by others who can access the source code.

As a consequence of this, everyone with access to the source code knows where to look for possible tampering. This makes it harder for a backdoor to be introduced without it being noticed by many of us. As pointed out above, they can’t gag us all.

Lavabit has set a precedent

One company, Lavabit, has shut itself down rather than comply with betraying their customers. This increases the risk of discovery to those trying to compel developers to introduce weaknesses.

It is impossible to predict how we would react in absence of having the full details of such compulsion in front of us; there are just too many unknowns and too many forms of compulsion. But the very real possibility that we would shut ourselves down (which would be public) rather than sabotage what we do and love should act as some deterrent to those who might wish to compel us to introduce a backdoor.

Only communications tools appear to be targeted

From the most recent revelations, the targets appear to be communication tools and protocols. 1Password is not such a tool. This doesn’t mean that the NSA couldn’t change their focus, but from what we know so far, 1Password is not the kind of thing they are after.

Going around crypto instead of through it

Even if you don’t find any of the individual reasons listed above to be persuasive, they interact powerfully. In combination, they make it much harder to get a weakness into 1Password without taking on large risks of getting caught and failing. Any attacker, including the NSA, will avoid high risk, high cost attacks if there are safer and easier alternatives. I’m therefore confident that the NSA would rather go around 1Password than through it.

Crypto Wars II

In the 1990s, there was a series of debates, pressure, civil disobedience, and cryptographic developments that have come to be known as “The Crypto Wars”. At the heart of this was the US and other governments’ efforts to prevent people from having access to cryptographic tools which those governments couldn’t break. In the end, governments (seemingly) surrendered, in large part because the tools they wished to use to enforce those restrictions (export restrictions, the Clipper Chip) just weren’t going to work.

What the 5 September, 2013 revelations show is that the US government has taken a different tack. The Crypto Wars may never have ended. Instead of explicitly and openly trying to limit the power of the cryptographic tools allowed to the public, they are now surreptitiously sabotaging the tools that we all use. As before, this will be fought on the political front—people telling their representatives that they don’t want hobbled security tools—and on the technological front—building better, stronger, more robust and verifiable systems.

Our role in this as a company is to be transparent about our approach to security while keeping your 1Password data protected.

How long should my passwords be?

1P4 icon“How long should my passwords be?”

A question like this depends on what kinds of password we’re talking about. The requirements for your 1Password Master Password, which you need to be able to remember and type, are very different from passwords you generate using the Strong Password Generator, which you never even have to look at.

The advice here isn’t changed at all by the recent news that the GPU-optimized version of hashcat, a password cracking tool, is no longer limited to attacking 15 character passwords. There seems to be some confusion about what that news means, which I’ll address further below.

Passwords from the Strong Password Generator

Wells Fargo: Your password must be 6 to 14 characters

Let’s start with the passwords created by 1Password’s Strong Password Generator.  Obviously, your password can’t be longer than the maximum length enforced by the website, but let’s leave that aside. Let’s suppose that the site or service you are generating a password for does better than my bank. There are lots of nifty options that you can set in our Strong Password Generator, but in order to keep my examples simple and stick to the most conservative assumptions, I’ll just use examples where we set the Strong Password Generator to create mixed case letters only.

Strong Password GeneratorLet’s take a look at a specific example I’ve set. I’ve set the Strong Password Generator to create a password that is 23 characters long, no digits, no symbols and characters are allowed to repeat.

Oops, did I just show what the Strong Password Generator might look like in the 1Password 4 menubar mini app? Wait, did I also just reveal  there might be a menubar mini app coming in 1Password 4 for Mac? And how did my keyboard get so… porous?

Moving on, the first character can be any one of a the letters “a” through “z” or uppercase “A” through “Z”. That is 52 different possibilities for the first of the 23 positions in this password. The second character can also be any one of those 52 letters. If we limited this password to just being two characters long, that would mean we could have 52 × 52 possible passwords; that’s 2704 possible passwords. A password cracker like hashcat or John the Ripper could rip through all of those in an instant.

At three characters long, we have 52 × 52 × 52 possibilities. That’s 140,608 possibilities, but still a joke of a password. When we get up to about 10 characters long we have 52¹⁰ possibilities, otherwise known as a 17-digit number. That will make high-end, specialized password cracking systems really sweat. Now let’s take a look at my 23 character password, as it has 52²³ possibilities. That number is approximately 2¹³¹, which is bigger than 2¹²⁸. As it happens, I wrote about just how hard it is to guess one of 2¹²⁸ possibilities a while back.

Put simply, if the world’s fasted computer could check a password as quickly as it can add two numbers, and if you had a billion of those computers all guessing passwords, it would take more than a million times the age of the universe to go through all of the 52²³ possibilities from a 23 character password created with 1Password’s Strong Password Generator. Put even more simply: nothing is going to crack a password generated with our Strong Password Generator this way.

Length of a Master Password

Your Master Password should be no longer than you can (teach yourself to) comfortably type. It also needs to be something you can remember. As a consequence, it will never be as strong as a 23 character password generated by 1Password’s Strong Password Generator. Because of this shortcoming of the human brain, we’ve taken taken steps to slow down the cracking rate that tools like hashcat and John the Ripper can achieve against a 1Password data file.

XKCD "I'm so random"

You can make a strong, memorable, and managable Master Password by using a truly random process to select words. Thinking them up yourself is emphatically not random.
So the system I describe in Toward Better Master Passwords involves rolling dice against short words from a list. Please see that article for the description. You can also read about how well these sorts of passwords withstand John the Ripper and hashcat. Note that the recent news about hashcat password limits doesn’t change our previous advice about password length, which is why I’m just referring you to those.

55 Character passwords, oh my!

HashcatSome readers may have heard that ocl-hashcat-plus, a spectacularly fast password cracking tool, is no longer limited to cracking 15 character passwords. It can now handle passwords up to 55 characters. This is a massive change to how hashcat operates. I’m sure it pains Jens Stuebe (AKA atom), hashcat’s developer, to surrender some of the brilliant optimizations that came with the 15 character limit, but as more people start to use passphrases, this was a change he had to make.

It is important to realize what this news does and doesn’t mean. Users of hashcat are now free to try to crack longer passwords. They no longer have to switch to some other tool like, say, John the Ripper or a different edition of hashcat, for going after long passwords. It still takes as much time today for hashcat to try a candidate password as it did last week. Actually, the changes that Jens had to make actually slow hashcat down by about 15%, but that really isn’t significant in determining what sorts of passwords are within reach.

Some people appear to have misunderstood the news. They may have mistakenly thought that the work previously needed to crack a 15 character password will now be able to crack a 55 character password. But that isn’t the case at all. A 25 character password is as strong today as it was before the announcement.

If, however, you use a passphrase that can be found in a book or on Wikipedia, you should change it. As more people – focusing only on password length – start to use such passwords, attackers start crafting their tools to attack them, as you can see from Josh Dustin‘s and Kevin Young‘s presentation at PasswordsCon.

But, of course, actual phrases in a natural language are anything but random.

Password advice should look ahead of the technology

Back in April when I discussed 1Password Master Passwords in light of hashcat’s speed, I studiously did not mention the fact (which I was well aware of) that hashcat was restricted to 15 character or less passwords. I could have said, “just make sure your password is longer than 15 characters and you will be safe from hashcat.” But I did not say that.

John the Ripper

I considered the 15 character restriction in hashcat as a technical, idiosyncratic design choice of one particular tool. It could change any day (as it has) and other tools could exist without that restriction (they do, including both other editions of hashcat and John the Ripper). When devising advice, we need to not limit ourselves to the idiosyncrasies of one particular tool. We need to look at the big picture—not just at what the tools do today, but at would they easily could do tomorrow.

There will still be times when advances in password cracking require an adjustment in what we do. For example, we’ve raised the number of PBKDF2 iterations used in 1Password over the years, and the data format used in 1Password 4 offers even tougher resistance to crackers. But on the whole, we design for the future. As a result, it shouldn’t be surprising when our reaction to some news or other is, “it doesn’t impact 1Password or how people should use it.”

On the NSA, PRISM, and what it means for your 1Password data

PRISM: 'really freaky'.It should come as no surprise that the NSA (United States National Security Agency) has easy access to data that ordinary people store online. Section 215 of the PATRIOT Act (of 2001) and section 702 of FISA (renewed and extended many times over its long history) give the US government the legal authority to gather such data and to keep the fact of gathering that data secret.

What is new is that there are confirmations of the prior suspicions that they are gathering telephony metadata about everyone, even if there is no specific reason to connect those people to a specific investigation, and that they have mechanisms in place to make it quick and easy to obtain data stored with various Internet service providers.

If the US government wants your data stored with Apple or Dropbox, it is easy for them to obtain it with no notification to you that they are doing so. This fact is not news. The laws have long enabled them to do that.

The news is (a) that the NSA and FBI have been collecting data about telephone calls on a large and indiscriminate scale while publicly stating that they weren’t, and (b) that they have mechanisms in place with various service providers, including Apple, to be able to collect data from individuals. The latter, we are now being told, is not indiscriminate; and the actual mechanisms are unclear.

Does this matter for 1Password users?

I think this matters for everyone, but here I will focus only on what this specifically means for 1Password. The latest news really changes little. We have gone from a situation where the government could “easily obtain the data” to one where “it’s so easy that they may have already made a copy.” Looking only at implications for 1Password, this is not anything new. The US government can easily obtain data you may store on iCloud and Dropbox. That just isn’t anything new, and so it isn’t anything new for 1Password.

Nonetheless, this does give us an opportunity to talk both about what data we at AgileBits may have about you and also with how resistant your 1Password data might be to the NSA.

We don’t know who you are, but we love you

We’ve never been asked to turn over data about you. Sure, some of that is because we are a Canadian company, but most importantly is the simple fact that we really don’t have any data to turn over. The easiest way for us to protect your data and data about you is to not have that data in the first place. We can’t reveal or abuse data that we don’t have. You can read the details of the data we do and don’t have.

In summary, we only have information about you that you explicitly provide to us. If you sign up for our Newsletter, we will have your email address. If you purchase from our store directly, then we have the information you provided at time of purchase (though we only retain partial credit card details). If you contact use through support, we have a record of those communications. If you make your purchase of 1Password through Apple’s app stores, we are only given aggregate information (how many people from which countries).

We do not have your 1Password data. We do not know your 1Password Master Password, We don’t even know if you use 1Password. We do not know how many items you have in your data or their type. Our image server (used for Rich Icons in 1Password 4) is set up in a way that we never see the IP addresses of individual requests. That server never gives us information about what is in any individual’s 1Password data.

Quite simply, you don’t have to be concerned about AgileBits gathering information about you. We just don’t have much information in the first place.

How NSA-proof is your 1Password data?

Returning to the (unsurprising) fact that the US government can easily obtain your data from cloud services, we can ask about how resistant the 1Password data formats might be to an attack by the NSA.

As we’ve often said, we designed the data format used in 1Password with the knowledge that some people would have their data stolen. It might get stolen because their computer is stolen or it might get stolen because of a data breach at a service like Dropbox. Either way, we’ve assumed that there would be circumstances where an attacker may get hold of your 1Password data, and so we designed the data formats with encryption to keep your secrets secret.

We can only guess (but make reasonable guesses) about the NSA’s capabilities. We can’t rule out that there might be some flaw in the design of our data format that neither we, nor anyone whose studied it, have found but that the NSA is aware of and able to exploit. Finally, there is the potential use the NSA could make from your 1Password data even without decrypting it.

In judging NSA capabilities, we need to keep in mind that they have a history of discouraging the US government from using systems that the NSA could break. If the NSA could break AES-CBC-128, then they would not be advising US government agencies to use it. Interestingly there is a history of the US and UK governments advising foreign governments to use cryptographic systems derived from Enigma, which the US and UK could break at the time.  But the NSA has (correctly) operated under the assumption that if they have found a way to break something, others will too.

Tweet from @EdwardTufte: PRISM "providers": classic PPT statistical graphic: 13 logos, 10 numbers, 9 bubbles, 1 giant green arrow. #powerpoint

It’s also reasonable to assume that the gap between the kinds of cryptanalytic techniques that the NSA has, and what the academic community has, is not as large as it was in the past. We did see evidence of the NSA (presumably) using a novel technique in Flame. We know that they are ahead, but as the number of people who publicly study cryptanalysis increases, the gap should narrow significantly. It certainly appears that their skills in designing presentation slides are more than a decade behind readily available and documented public techniques.

From these I comfortably operate on the assumption that the actual building blocks (AES, etc) and the constructions (CBC) we use are not broken.

Of course, one area where the NSA has clear, unmatched power is with computing resources. Our estimations of how long it would take a password cracker to guess a Master Password have been based on the kinds of tools that the public password cracking community has available.

A Master Password with the equivalent of 60 bits of entropy is going to be out of the reach of even the most dedicated civilian password cracker, but may be within reach of the NSA.

Cray XMP

There may be non-cryptographic flaws in cryptographic software, including 1Password, that the NSA is able to exploit, and that nobody else knows of. That is, they may know a way to break 1Password’s security without having to break the crypto. Naturally, we work  hard to keep 1Password free of such vulnerabilities, but that is no guarantee that there aren’t some which the NSA is aware of and that we are not.

Finally, if they are collecting massive amounts of data, they may be able to make use of the non-encrypted data within our data formats. Our newest format reduces that particular threat, but it is still possible to see when items were created and modified along with how many items a person has in their 1Password data. Also, item categories (whether something is a Secure Note or a Login or a Credit Card) is not encrypted. As discussed in many places, the Agile Keychain format, which we developed in 2007 and began phasing out with 1Password 4 for iOS in December, leaves Title and Location unencrypted, so it’s similar to a browser bookmark file. However, in the case of an investigation by the NSA, that probably tells them little that they already didn’t have access to.

The right tool for the right task

Security failures often happen when people don’t use the appropriate tool for the task they are trying to achieve. 1Password is extremely good at what it does. It keeps the secrets (passwords in particular) you store within it safe, and makes it easy for you to use those secrets when you need them. This is an extremely important part of your security, and we are very pleased to provide that.

If, however, your goal is to keep your online activity secret from the government, then 1Password can only be a tiny part of what you need to do. As an analogy (and all security analogies ultimately fail; so don’t take this too far), consider a system, say 1Passlock, as providing a very good lock on your house making it impossible for someone to break into it. 1Passlock, however, would do little to prevent someone from learning the location of your house, so you would also need to find something in addition to 1Passlock to conceal your house’s location.

The point of this terrible analogy is that you need to find the right tools for your particular security goals and try to make sure that those tools work together.

Avoiding the cloud

1Password in DropboxOur approach has been to plan and design for the case where your data can be captured from anywhere, whether it is stored on services like iCloud or Dropbox, or not. However, we have learned that a notable number of people don’t agree with storing their data in the cloud at all. There are 1Password users who reject the idea of storing their 1Password data on any system outside of their control no matter how strongly their 1Password data is encrypted.

iCloudWe would like you to have as much control over your own data as possible. This way, it doesn’t matter whether you agree with me about the relative risks of capture from local computers. It should be your choice to make. We have provided a (beta, Mac only) USB Syncher, but we are also exploring other approaches that may work out as better solutions for synchronizing your 1Password data without having to rely on services outside of your control. At this point, I can tell you nothing about the kinds of approaches we are exploring, and I do not yet have a timeline to share.

In conclusion

The latest news does not substantially change the security situation for 1Password. It does, however, focus more attention on the relative safety of your 1Password data when using Dropbox or iCloud to store and synchronize said data.

We anticipate that there will be some creative discussion of this, and so have already created a specific place for this in our forums.

The top 6 worst passwords from the Star Trek universe [Updated]

You would think that, once we master space exploration and how to replicate the perfect cup of Earl Grey, everyone in the future according to Star Trek would understand the necessity for unique, strong passwords.

Unfortunately, you would be wrong. And no, as we’ll see later, biometrics (like voice authentication) don’t seem to help.

As the following evidence from various Star Trek clips shows, some of the passwords used by Starfleet’s finest are weaker than the passwords stolen from the recent Sony and Yahoo hacks. Clearly, these officers could’ve used 1Password.

1. Kirk, Scotty, and Checkov needed our Strong Password Generator

The longest password needed to blow up the Enterprise in Star Trek III is just five characters. My U.S. social security number is longer than that but, fortunately, I’m pretty sure it can’t self destruct anything.

2. It shouldn’t be this easy to eject the warp core

B’Elanna gets points for getting past five characters (yet she loses points for using her own name in her password). But it’s way too easy to strand a ship in the middle of nowhere with a simple “computer!” callout and what is still a weak password.

3. Honestly, who made it this easy to blow up ships

If it was this easy to blow up ships in the 24th century, I’d probably look for abandoned derelicts everywhere I went and do it as a hobby. Those explosions are totally GIF-worthy.

4. Picard’s authorization is so weak, the computer rejects it

Ok, maybe that torn power conduit had something to do with it, but still. If I were the Enterprise computer, I would’ve locked Picard out a long time ago and made him upgrade to a much stronger self destruct password.

5. Chekov’s ship-wide status update password is laughably short

With a password that weak, officers would break into the internal comms every other day and post Burger King-like prank announcements that the Enterprise was switching teams to the Romulans or launching a package delivery service.

6. The password to our shields might as well be 1-2-3-4-5

In Star Trek II: Wrath of Khan, Kirk and Spock are able to remotely shut down the shields of the Starfleet ship Khan “borrowed” by transmitting nothing more than a five-character “prefix code” of 16309.

I know luggage with tougher combinations than that.

Even worse, they looked it up in what seems to be not much more than an Excel spreadsheet of all Starfleet ship prefix codes. What could possibly go wrong?

The clip here doesn’t include the statement of the code. If you want that, skip to around 6:50 in this longer clip. Thanks to Joe Kissell for schooling us on our bad Star Trek passwords.

Honorary mention: Data’s perfect-yet-flawed password

You might think Data created the perfect password that time he went nuts, took over the Enterprise, and mimicked Picard’s voice (hooray for 24th century biometrics!), all in the name of dropping in to say hi to dad. There’s just one problem: he said it out loud for everyone to hear, or at least for the computer to record and tell Picard later.

Did we miss any great moments in bad Star Trek passwords? Let us know on Twitter, Facebook, or our forums!

Use better passwords than Starfleet

Fortunately, the future isn’t written yet. Let’s change your timeline in online security—get 1Password and follow our guides to use our Strong Password Generator on Mac, iOS, and PC so it’s much, much harder to blow up your ship.

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.

 

You have secrets; we don’t. Why our data format is public

1Password 4 for iOS iconThe security of your 1Password data depends on only one secret—your Master Password. It also depends on plenty of things that aren’t secret. For example, 1Password uses the AES encryption algorithm, every detail of which is defined by public standards; your security depends on the security of AES, but there is nothing secret about it.

Another non-secret is the design of our data format, including the Agile Keychain format and the Cloud Keychain Format. Indeed, we have a history of being very open about our data format, and this is good for your security.

Third party apps and 1Password data

Let me jump to the what has prompted this article before returning to the virtues of publicly detailing our data format. Recently there’s been progress on third party tools and applications that can read 1Password data, and there are some important factors to consider about these tools:

  • Third party tools for reading 1Password data do not reflect a “break” in 1Password. They, like 1Password, require your Master Password in order to read your data.
  • We have to advise you to never enter your 1Password Master Password into anything that isn’t 1Password. We aren’t casting aspersions on the integrity or competence of any developers, but we simply can’t advise otherwise.
  • Third party tools are “third party”. Although we may sometimes help them understand the details of our data format, they are entirely independent of AgileBits. The fact that we may maintain a good relationship with them is not an endorsement of what they produce.
  • Third party tools exemplify the fact that there is no data lock in with 1Password.

The existence of third party tools for reading 1Password data has had people ask about the security implications of us being so open about our data format. Our openness is a good thing, and here’s why.

No lock-in

Vendor lock-in, roughly speaking, is when you depend on a particular vendor to be able to use what is already yours. An example that many of us face is with ink for inkjet printers.Most expensive liquid infographic

The manufacturers of various inkjet printers make it very hard for you to purchase ink from any other vendors. Thus, to continue using their printer, you need a supply of their ink. Not only does that get expensive, but if you spent a lot of money on the printer, you need to worry about what might happen if the vendor goes out of business and no longer provides ink. You may not be able to use your printer at all.

I have more than 1500 items in my 1Password data, and it would be absolutely catastrophic if I were to lose access to these. This is, of course, why good backups are essential and why I need a Master Password that I’m not going to forget. “Data availability” is the jargon used for this aspect of data security, and it is one that people often overlook. Years ago, I wrote about the importance of backups in “Keeping your data at your fingertips (Part I)“, then I wrote about being sure you have access to those backups. Now it’s time to talk about part II of that first article: avoiding data lock-in.

Could you lose access to your own password data if we disappeared from the face of the Earth or turned evil? We have no plans to do either, but you should know that even if the worst were to happen to AgileBits, you would still have access to your data. One of the reasons for this is that, once you have purchased a copy of 1Password, you can continue using it forever as long as you have an operating system that supports it. Our (rare) paid upgrades are optional.

The second way we avoid locking you into 1Password is through the ability to export data to a more neutral format. Not all versions are yet where we want them to be with respect to export, and we’re working on that. But there is usually some path, if not always a simple click away, to export your 1Password data.

Enabling third parties prevents lock-in

It’s this third way that we avoid lock-in that is relevant to today’s topic. Our data format design is specified well enough so that people with no connection to AgileBits can write software to be able to handle it. Of course your data remains completely unusable without your Master Password; third party software still needs you to enter your 1Password Master Password.

There are, indeed, at least two projects independent of us, which are developing software that can read 1Password data (once you’ve given them your Master Password.). James Brown (@RogueLazer) has developed some Python libraries which can – given the Master Password – read both the Agile Keychain Format (1Password 2 and 3 for Mac, 1Password for Windows) and the Cloud Keychain Format (1Password 4). Indeed, RogueLazer’s efforts and queries have led to substantial improvements in our documentation. Another project is the very recent release of the tooPasswordapp for iOS. Its developers tell me that they worked straight from our documentation. I should also add that, in its own way, the John the Ripper module for the Agile Keychain data could be called another third party tool.

Without passing any judgement on any third party developers, we have to advise people to never enter their 1Password Master Passwords into anything other than 1Password. I have no reason to doubt the integrity or competence of these third party developers, and RogueLazer’s project is even open-source. But it would be irresponsible for us to do anything other than advise you never to give your 1Password Master Password to anyone or any other application.

So while we can’t endorse those systems, and indeed we have to advise you against using them; their existence is still a Good Thing. They are proof that our openness about our data formats means that you do not have to fear data lock-in.

Kerckhoffs’ Principle: No secrets beyond the key

Auguste KerckhoffsKerckhoffs’ Principle states that you should assume that your adversary knows as much about the system you use as you do. This is why – despite what I may have said on April Fools Day last year – security experts are skeptical of security systems that hide the details of how they operate. They are particularly skeptical of systems that derive their security from keeping the details of how they work secret. I could go on at great length about why openness about the system improves security. Indeed, my first draft of this article did go on at great length. I’ll try to be more concise this time through.

Too Many Secrets

If the security of a system depends on the secrecy of the system (in addition to the secrecy of the key) then that secret is actually a vulnerability.

xkcd code talkers comic

Suppose my two dogs, Patty and Molly, have developed their own security systems. Mr Talk, the neighbor’s cat, wants to break into their systems. Patty has developed hers so that all of the secrecy is in her password. Everything else about the system can be made public. The security of Molly’s system, on the other hand, depends not just on her password, but also on keeping aspects of her system design secret.

Mr Talk will study both systems very carefully. He’s very patient and will pick them apart. As he learns more about Patty’s system, it doesn’t get any weaker. After all, Patty made the details of the system public in the first place. But as Mr Talk learns more about Molly’s system, the weaker it becomes. From Mr Talk’s point of view (that of the attacker), Molly’s system has a vulnerability that is waiting to be discovered through analysis. Indeed, Molly’s system has that vulnerability by its very design.

Public scrutiny

It’s easy to use the Advanced Encryption Standard (AES) algorithm from some standard library in some software and call it secure. AES is certainly strong enough. But unless it is used in the right ways at the right times as part of the right constructions, it would probably be a mistake to call such software secure.

We do believe that we use AES, PBKDF2, HMAC and other technologies in the right ways at the right times in the right constructions. A great deal of care and research went into those sorts of decisions. But the only way for the world to share our confidence is if we document our decisions. Sure, most people aren’t in a position to directly evaluate said decisions, but everyone can take comfort in the fact that there are enough people who can, and do, look at those details.

We’ve been here before, and we’ll be here again

This isn’t the first time Kerckhoffs’ Principle has come up. I specifically discussed it when talking about creating good, strong Master Passwords, when I said that we should use a system for coming up with Master Passwords that doesn’t lose its strength if the attacker knows the system that we used. Kerckhoffs’ Principle also came up (though not by name) in discussion about how 1Password stands up to password cracking tools.

All of this is to say that Kerckhoffs’ Principle runs strong and deep through 20th and 21st century thinking about cryptography. Even if I don’t mention it by name, you should keep an eye out for it.

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

Hashing fast and slow: GPUs and 1Password

The net is atwitter with discussion of Jeremi Gosney’s specially crafted machine with 25 GPUs that can test hundreds of billions of passwords per second using hashcat, a password cracking system. Password crackers, like hashcat, look at the cryptographic hashes of user passwords and repeatedly make guesses to try to find a password that works. 1Password has been designed to resist automated password cracking attempts exactly because we anticipated developments like this.

Don’t get freaked out by the numbers

Windows XPFirst and foremost the reports of 348 billion passwords per second is specifically about passwords stored in the LM format used on Windows XP, exploiting the notorious design flaws and limitations LM hashes. (If you are still running Windows XP; and particularly if you are running NT, 2000 or 2003 domain controllers, please, please upgrade.) The hundreds of billions of  passwords per second reached against those hashes does not mean that passwords stored in other formats can be cracked that quickly.

By the way, this isn’t the only important news about password security to come out this year’s excellent Passwords12 conference. I couldn’t quite make it there this year, but I will talk about other developments from it in coming weeks. Today, all eyes are on GPUs guessing billions of passwords per second.

Slow and Fast Hashing

Typically when a password is “stored” on a system that you log into it is not the password itself, but instead it is a cryptographic hash of the password. I’ve written about some of the ways that password  can be hashed before. HashcatThese can roughly be divided into two categories: slow hashes and fast hashes. Slow hashes are specifically designed to slow down the kinds of attacks we are discussing.

Your 1Password Master Password is processed using the slow hashing system known as PBKDF2. 1Password’s use of PBKDF2 and your use of a good Master Password keep your data resistant from password crackers such as John the Ripper and hashcat if you chose a good Master Password.

Defending against future threats

There are several lessons from this. Gosney’s work does reflect real innovation and a breakthrough, but it isn’t an unexpected breakthrough. People who keep an eye on these things – and we do keep an eye on these things – expected something like this within the next couple of years.

We need to design systems that work against plausible future threats, not just against current threats. This is what we have always tried to do with 1Password.

Lessons and actions

  1. Your 1Password Master Password and your 1Password data remain safe, we designed the Agile Keychain format from the beginning to resist crackers like this. But it is also important for people to select strong, memorable, Master Passwords.
  2. It is more important than ever to have unique passwords for each site and service. As password cracking gets easier, the risks of using the same password on multiple sites increases. This is because if password hashes are stolen from one site, attackers have a better chance of discovering the password from the hash. Once they have that, they can try the same password on other sites.
  3. When using 1Password’s Strong Password Generator, try to create passwords that are at least 20 characters long.

Back to the Future

Gosney slow hash chartI’ve talked (well even boasted, I suppose) about how our earlier design decisions are protecting 1Password users today. But we have to look at what design decisions we make today will do for 1Password users half a decade from now.

Gosney’s machine can also be used against slow hashes, including PBKDF2 passwords. You can read more (and see cool pictures) of the design of Grosney’s hashcatting machine in the conference presentation slides (PDF).

Furthermore PBKDF2 was not designed to specifically impair parallel processing. But because GPUs have unusual and restricted ways of addressing memory, it is possible to design systems that make parallel processing using GPUs slower. This leaves a number of questions that we continue to look at.

  1. Do we need to change anything at all in anticipation of even more powerful machines tuned toward PBKDF2? (We don’t yet Password Based Key Derivation Function diagramhave estimates on how many passwords per second this system could try against a 1Password data file.)
  2. If we do need to change things, when do we need those changes need to be in place?
  3. Should we look at more parallel and GPU resistant alternatives to PBKDF2, such as scrypt?
  4. Should we look at tinkering with options within PBKDF2 to make it more resistant to GPUs working in parallel?

These are not new questions. We are always asking ourselves these and other questions in order to keep your 1Password data secure and protected, both now and in the future.

[Updated 2012-12-06 15:50 UTC. Updated to correctly explain that Gosney's system is not limited to LM hashes. Thanks to Jeremi Grosney, Solar Designer, and others who pointed out my error. I have also taken the opportunity to add more clarifications and links to background throughout.]

Credit card numbers, checksums, and hashes. The story of a robocall scam

Sample Bank of America debit cardAs  Lívia and I were out walking Molly and Patty on Monday evening, I received a telephone call from an unknown number.

I decided to answer the phone anyway, and I was greeted by a recorded voice telling me that my Bank of America debit card beginning with 4217 has been limited and whether I would like to revalidate it.

I don’t have a Bank of America debit card (though I did many years ago), and I know US rules bar most calls that begin with recorded messages, otherwise known as “robocalls.”  I also know that the first few digits of credit card and debit card numbers indicate the card issuer and so are not secret if you know that it is a card issued by a particular bank. It would be easy for a scammer to appear to know my card number. Once I got home, I was able to confirm that 4217 is, indeed, how most Bank of America debit card numbers begin.

Naturally I pressed 1 to “revalidate” my card (not-so-sidenote: you should not try this at home. Indeed, you really should just hang up when you get such calls). I wanted to see how this scam proceeded. At this point I was told a few more details explaining that my card beginning with 4217 needed to be revalidated because of a internal security failure and that I should press 1 to continue. I pressed 1 again.

I was then asked to enter my Bank of America debit card number. Unfortunately, I was not able to construct a number off of the top of my head that would pass their validation check.
While I knew it should begin with 4127 (thanks to the robocall), I did not know at the time that the next two digits should be between 64, 65, or 66 for Bank of America. I did know that the last digit of the sixteen digit number should be calculable from the preceding 15 digits by the Luhn checksum algorithm. But I couldn’t recall the details of the algorithm at the time, and I certainly would not have been able to construct something on the fly quickly enough to enter a “valid” number.

As a consequence, I wasn’t able to get past the “enter your debit card number” step, and so never learned what other information they would ask for, such as my Social Security Number, billing address, or PIN. But it is a safe bet that those would have been requested at some point. Those of course, would have been easier to fabricate as they have no quick validation system.

Checksums

The Luhn checksum is not some super secret security feature, it was a simple system designed to identify errors when exchanging credit card numbers in common use. At best, it can play a minor role in basic security checks to weed out those who just try random numbers.

The system is designed to catch common errors. If one digit of the 15 digits is entered incorrectly the checksum will fail. For example if the correct number is 4217 6601 2345 6784 (here 4 is the checksum) then if the number is given as 4217 6681 2345 6784, where the “0” has been mistyped as an” 8″, the check digit will be 7, and so  4217 6681 2345 6784, with a “4” as the last digit, will not validate.

Some people accidentally type “2435” instead of “2345”, swapping the “3” and the “4”. It happens to the best of us, and it’s another example of the the type of errors the Luhn system can catch.

Not all checksums are cryptographic hashes

1P logo in AESCheck digits of this sort, where the checksum is just one digit long, have properties that make them poorly suited for cryptographic purposes. The most obvious is that they are too small. That is, the check digit can only be one of ten possibilities—0 through 9. Put another way, there is a pretty much a 1 in 10 chance that two numbers will have the same check digit.

When two numbers result in the same checksum, we have a “collision”. If it is feasible to create two numbers that have the same check digit, the system is not collision resistant.

If we also have one number that has a particular checksum then we can easily construct another number that yields the same checksum. So the Luhn algorithm isn’t second-preimage resistant. The difference between collision resistance and second-preimage resistance is subtle. For collision resistance, the problem is “find two numbers whose checksums collide.” For second-preimage resistance, the problem is “here is a number m, now go and find another number that has the same checksum as m.”

It is also the case that if we have a checksum, we can easily construct a number that shares the same checksum. If you give me a checksum of “5”, I can construct a 15 digit number that has 5 as its checksum. That is, it is possible to work backwards from the checksum to an original. Hence, this checksum system is not preimage resistant. Functions that are preimage resistant are sometimes called “one way functions”.

The obvious reason why the Luhn algorithm fails to be preimage resistant, second-preimage resistant, and collision resistant is because it is just one digit. There just isn’t anything you can do when you only have one digit (about 3 bits) with which to work. But there are other reasons as well. I won’t discuss them at all, other than to say that the Luhn algorithm doesn’t have those three properties because it was never designed to.

Resistance is necessary

Cryptographic hash functions, however, are used for more than just checking for accidental errors in data entry or data transmission. This means they do need to be one way functions (preimage resistant); they need to be second-preimage resistant; and they really should be collision resistant.

We’ve discussed how preimage resistance is one of several essential properties of proper treatment of passwords on servers. We’ve also discussed how second-preimage resistance plays a vital role in network security. Over the next few posts I will be talking about how hash functions are used for data integrity checks and specifically for authenticated encryption. Authenticated encryption will play a big role in our next data format.

A fine night for a scam

I am relieved to say that both Patty and Molly did not really mind that I spent the remainder of our walk talking about the nature of the scam; how the criminals’ knowledge of the issuer number on a card can easily fool a target; and, of course, on the difference between checksums and cryptographic hashes. Lívia did not seem quite as complacent as the dogs. “The difference between us, Jeff,” she said, “is that I get really annoyed when something like that happens; but you seem to be really enjoying yourself.”

A few notes about robocalls

Robocalls are a lot like email spam:

  1. The caller ID number is easily counterfeited. You cannot rely on it to trace the source of the call
  2. “Press N to be removed from our list” is a lot like the “unsubscribe” button in email spam. Sure there may the the rare case where it is genuine, but usually it is just used to confirm that the spam/call reaches a real person who, to at least some extent, trusts the message. It’s a great way to get yourself added to more lists

As I write this, the US Federal Trade Commission is hosting a summit on robocalls. There should be more information at that site in coming days and weeks.

Correction October 22, 2012: I incorrectly suggested above that the Luhn algorithm will catch all single transcription errors involving the replacement of one digit with another and all cases where adjacent distinct digits are transposed. I was wrong. The ISBN checksum has these properties, but the Luhn Algorithm used for credit cards does not. The crucial difference revolves around the fact that the ISBN-10 system uses a prime modulus (11), while the Luhn system uses a composite modulus (10). This is also why the check digit for ISBN numbers can sometimes be “X”. The check digit there works out to be a number from 0 through 10, but “X” is used to indicate 10.

I should have spotted this instantly when I looked at the Luhn algorithm, but it required a different path for me to learn of my error. Today is a student holiday in our school district, and so I assigned my daughter the task of proving that the Luhn system will have the properties that I claimed it had. She quickly constructed some counter-examples, where changing an individual digit leads to the same check digit.