duo-banner

Send in the crowds (to hunt for bugs)

We unequivocally encourage security researchers to poke around 1Password. It is an extremely important part of the process that helps us deliver and maintain a more secure product to everyone. Finding and reporting potential security vulnerabilities is what we should all expect from bug hunters around the world; the hunters and yourself should expect that we address those vulnerabilities promptly.

We have always welcomed security reports that arrive at security@agilebits.com, and over most of the past year we offered a more formal, invitation-only bug bounty program through Bugcrowd. We are pleased to now take that program public: https://bugcrowd.com/agilebits.

op-bugcrowd

Before I get into what the program offers, I’d like to remind you that there is always room to improve the security of any complicated system, 1Password included. As clever as we may think we are, there will be security issues that we miss and different perspectives help reveal them. Software updates that address security issues are part of a healthy product. This, by the way, is why it is important to always keep your systems and software up to date. Even in the complete (and unlikely) absence of software bugs, threats change over time, and defenses should try to stay ahead of the game.

Some words about Bounty

A bug bounty program offers payouts for different sorts of bugs. The first bug bounty that I recall seeing was Donald Knuth’s for the the TeX typesetting system, though I have since learned that he does this for most of his books and programs. It started out with $2.56 (256 US cents) for the first year, and doubled each year after that, reaching a final limit of $327.68.

Check from Donald Knuth made out to Richard Kinch.

A bounty check from Donald Knuth made out to Richard Kinch

Of course given Donald Knuth’s well-deserved fame and reputation, few people cashed the checks they received. Instead, they framed them.

Anyway, enough about me revealing my age. Let’s talk about today’s bug bounty program. There is a community of people who earn a portion of their income from bounties. (Whether or not it is enough for them to sail off to Tahiti or Pitcairn is not something I know.) Over the years they have developed skills and tools and scripts for examining systems. We want them to apply those skills and efforts testing the security of 1Password. Opening up this bug bounty program brings those people and their skills into the process of making 1Password more secure.

Our bounty

Unlike the example of Donald Knuth’s bug bounty, we are only offering payouts for security issues. Of course all bug reports are welcome, we just aren’t promising bounties for them. And because we are promising to pay for bugs, we’ve had to establish a bunch of rules about what counts. These rules help us draw the attention of researchers to the 1Password.com service, and they help us exclude payouts of things that are already known and documented. We don’t want those rules to discourage anyone from bug hunting; they are there to help focus attention on what should be the most fruitful for everyone.

1Password Security white paper cover

Your homework

We think that finding bugs in 1Password will be challenging — 1Password.com is not your typical web service. Our authentication system, for example, is highly unusual and specifically designed so we are never in a position to learn any of our customers’ secrets. Because we use end-to-end encryption, getting hold of user secrets may require breaking not just authentication but also cryptography. Of course, we’re inviting researchers to try out attacks that we haven’t considered to prove us wrong. I expect that successful bug hunters will need to do their homework, all the same.

Now, all that bragging about how challenging I think it’ll be to find serious issues with 1Password isn’t an attempt to stop people from trying — get out there and try! You can get bounty for it, and a thank-you as well. We’re excited to hear a resounding “challenge accepted!” from the research community.

How we help researchers

If there are security bugs, we want to know about them so we can fix them. (I know I keep repeating that point, but not everyone reading this is familiar with why we might invite people to look for security bugs.) We want to help researchers find bugs, because they’re helping us, and everyone who uses 1Password.

To help researchers understand and navigate 1Password (and reduce the amount of time they may need to reverse engineer protocols) we have set up a special 1Password Team that contains a bunch of goodies: internal documentation on our APIs, some specific challenges, and UUIDs and locations of items involved in some of the challenges. So researchers, please come and leave your mark on our Graffiti Wall. (No, not in this web page or the image below, the wall inside the aforementioned team account.)

Secure Note: "The Researchers vault grants read-only access to researchers. If you figure out how to get around read-only access, please put your name in here ..."

With a natural degree of trepidation, I look forward to what might appear there.

The kindness of strangers

A bug bounty program brings in a new group of researchers. And that’s why we’re launching it. We encourage independent research as well. We’re just as open to reports of security issues outside of the bug bounty program as we have always been.

So without further ado, let’s send in the crowds!

Security header

How 1Password calculates password strength

Password strength is a big deal. It is in fact one of the biggest deals. That’s why the Security Audit feature in 1Password pinpoints your weak passwords, so that you can go through and change them at your earliest convenience. But how does the strength meter actually calculate the strength of your password? What makes a password strong or weak? A recent conversation with a user inspired me to write down my thoughts on the subject. If you are going to trust 1Password to generate strong passwords for you, you should know how the strength meter works.

About Those Meters…

For a password strength meter to actually be accurate, it needs to know the system that was used to generate the password. When you generate a password using 1Password, we know that this newly generated password has been generated in a truly random fashion and can accurately calculate the password’s strength. However, when 1Password is evaluating the strength of a password that you have typed in manually, including a password which was generated in a truly random fashion on another device, the strength meter cannot know whether it is looking at a password that was created through a truly random process or created by a human.

Password strength: perfectly good

If our password strength meter sees something like “my dog has a bunch of fleas” or something like “gnat vicuna craving inclose”, it can’t tell that the first was probably made up by a human and that the second may have been generated by something smarter, like our password generator.

Password strength: not so good

Because it doesn’t know how the password was generated, it errs on the side of caution. The strength meter will mark “gnat vicuna craving inclose” (a perfectly good password) the same as it will mark “my dog has a bunch of fleas” (not a good password at all). Both have the same number of letters (27) and both contain only lowercase letters. It’s up to you to know where the password originated. Did it come from our random password generator, or is it something a person made up?

Randomness and Selection Bias

When we speak of “randomness”, we are referring to mechanisms which have been tested and determined to be truly random and not dependent on events which may be repeatable or subject to outside observation. The toss of a fair coin or die is a source of “random input”. The radioactive decay of a substance can be used as “random input”. Our own limited vocabularies and choices of words are not “random input”.

When creating unique, strong, random passwords, what is required is a Cryptographically Secure Pseudorandom Number Generator (CSPRNG) to ensure that no one value or sequence of values will be preferred over all other values. The values from the CSPRNG may then be used to select from some alphabet or word list to create unique, strong, random passwords having the appropriate construction and length.

Selection Bias refers to preferences for specific values over others, whether by using an unfair coin, a loaded die, or a random number generator which does not produce a uniform and unbiased set of values. Inappropriate math performed on valid CSPRNG produced numbers may also lead to biases for certain values in favor of others. A common error is the use of modulo (remaindering) arithmetic which results in smaller values being used preferentially over larger values — there are more instances of values between 0 and 5535 (66 for each value) than between 5536 and 9999 (only 65 for each value) when using modulo-10000 on an unsigned 16-bit CSPRNG generated number.

Password strength: happy synonyms

For human-generated passwords, common causes of selection bias include the use of a small and limited vocabulary (list all of the synonyms for “happy” you don’t use on a regular basis) and reuse of words (“cool”, “okay”) and avoidance of others (“groovy”, “hip”).

Pre-generated word lists avoid this type of selection bias by randomly selecting words which are common enough that the user should be able to spell the word from memory without being biased by personal preferences or regional differences in word choices.

Password Construction and Strength

The format of a password — the rules which are used to select characters or words — influences the strength of a password, but does not limit its possible strength, except to the extent that length limitations may be imposed on the result.

As an extreme example, consider a password that consists only of the letters “H” and “T”, and that you generate by repeatedly flipping a fair coin. If you make this password long enough it can have any strength desired — you only need to keep flipping a fair coin. But “long enough” in this case is actually unreasonably long. If you want a password that is as strong as a 10-character, mixed-case letter and digit password generated by our Strong Password Generator, your “H” and “T” password would have to be 60 characters long!

Memorizable Passwords

Shorter passwords from truly random sources can be stronger than longer passwords from biased sources even if they draw from the same character sets. For example, an 8-character, mixed-case letter and digit password produced by our generator is going to be a much better password than the longer (10-character) “Abcde12345” password that a human might come up with. There is reason to believe that the more “strength requirements” (use a digit, use mixed case, add a special character, etc.) we impose on people, the worse the passwords that they create may get. Part of this has to do with alphabet reduction: users may choose to limit mixed alphanumeric passwords to more alpha and less numeric, or more lowercase and less uppercase.

There is reason to believe that the more “strength requirements” we impose on people, the worse the passwords that they create may get.

For example, the rule “at least 8 characters, 1 uppercase letter and 1 digit” will produce approximately 80 billion (109) passwords (6 lowercase, 1 upper case, 1 digit: (26 * 26 * 26 * 26 * 26 * 26) * 26 * 10, or about 36 bits) if the uppercase letter appears first, followed immediately by a digit. But again, that assumes that the password was created by something that had a good random number generator and knew how to use it, and that the password isn’t simply a capitalized 8-character word with a single vowel replaced by a digit, such as “B3musing” (possibly as few as 14 bits). If the uppercase character and digit are allowed to be in any of the 8 possible positions, that increases the number to approximately 4,500 billion possible passwords (or about 42 bits).

This is a classic example of alphabet reduction where the complete rule should have been expressed as “at least 8 characters, 1 uppercase, 1 lowercase, 1 digit, and the remaining 5 chosen completely at random from the set of uppercase and lowercase letters, and digits”. When this revised rule is used, and a CSPRNG is used to select the characters, the number of possible passwords increases to ((62 * 62 * 62 * 62 * 62) * 26 * 26 * 10 * (8 * 7 * 6)), a total of about 2 million billion possible passwords (or about 50 bits). Each additional alphanumeric character, chosen completely at random by a CSPRNG, adds about 5.9 bits of additional strength.

Truly random length-limited passwords are hard for human beings to generate and memorize because people tend to choose less randomness in favor of greater memorizability. Using 1Password to generate and store passwords ensures that strong, unique, random passwords can be used without worrying about forgetting them.

Memorizable Passphrases

Choosing multiple words from a suitably large dictionary of words may result in stronger passwords even if all of the words appear in dictionaries, are spelled with lowercase letters, and no punctuation is used. Assuming a dictionary size of 20,000 common words (about 14.3 bits per word), chosen entirely at random, all of which are lowercase, the number of possible 4-word passwords increases to 160 million billion (about 57 bits.)

Studies of our ability to easily remember information have shown that we have limits to our ability to memorize seemingly random information, unless we have a useful mnemonic device or the information is grouped in a particular manner. This is why telephone numbers and postal codes tend to be grouped as they are, and why mnemonic devices are popular, such as “My Very Educated Mother Just Served Us Nine Pizzas”.

XKCD

XKCD comic 936 is a perfect example of how easy it may be to memorize the random four-word password “correct horse battery staple”. As our Chief Defender Against the Dark Arts Jeffrey Goldberg will tell you, you may even add your own rules to that password to make it easier to memorize — “Correct! Horse: Battery staple.” Now you have a nice story to help you memorize a strong, random, unique password.

What It Means to You

Our strength meter (along with every other strength meter ever designed) has to guess how the password it is evaluating was created, unless you are actively generating the password in 1Password at that very moment. This means that you may see a big mismatch between “actual” and reported strength for our generated passwords.

The good news is that our password generator does a really good job of generating truly random passwords, so when you generate a secure, random, and unique password with 1Password, you know that it was generated just for you, right there on your device and it is as strong as can be for the length and rules you requested. So, let’s hear it for “paddle shrill sonorant palazzi ravioli” and “8dUaYolTJu82DDG9” — so happy to meet you, secure, random, and unique passwords that you are!

Additional Reading

For a more comprehensive discussion of generated password strength, please read the Geek Edition of our guide to creating better master passwords.

You’ll also find an article in our knowledge base that discusses password strength meters, chicken entrails, and assorted feats of strength.

Security header

More Watchtower, still no watching

1Password WatchtowerThere are some great new features in the 1Password for iOS 6.2 update that hit the App Store last week. One of them is that we’ve added Watchtower (a feature that has been available on Mac and Windows for some time now) to 1Password for iOS.

Watchtower warns you if a site or service has been compromised in a way that would make it a good idea for you to change your password for that site. Watchtower in 1Password looks at the most recent time a password change was recommended for a site and it looks at the time that your password for an item was last modified. If, like Molly (one of my dogs), you haven’t updated your Adobe password since the 2014 breach, you might see something like this:

Watchtower warning in 1Password on iPhone

Molly hasn’t changed her Adobe password since the breach a couple of years back

Preserving your privacy

I want to talk about a far less visible feature of Watchtower: We’ve added Watchtower support in a way that still preserves your privacy. We don’t want to know what sites and services you have in your 1Password vaults, so when 1Password checks to see if one of your Logins is listed in Watchtower, it does not make a query to our servers asking about it.

Enable Watchtower in iOS

Turning on Watchtower in iOS. “Your website information is never transmitted to the 1Password Watchtower service.”

Querying Watchtower without querying you

Our Watchtower people are continually watching reports of site breaches and updating our database of such sites regularly. This is how 1Password knows that a password change is recommended for some site.

The “obvious” way for 1Password on your computer (and now iOS device) to alert you, would be to go through your 1Password items and ask our database on some server about the status of those items. The problem with this “obvious” way of doing things is that it means that any server your copy of 1Password queries would then be able to know your IP address and what sites you have in your 1Password data.

If 1Password on some device were to ask our server, “Do you have Watchtower information about ISecretlyHateStarWars.org?” then our server will know that someone at your Internet address may have a very nasty secret. You certainly wouldn’t like us to know such things about you, and we don’t want to know such things either.

The road less travelled

So we don’t do things the obvious way. Instead, we send the same stripped down version of our Watchtower database to everyone who turns on the feature. You have a local copy of the Watchtower data on your device, and 1Password just checks against that copy of the local data. All we can know (if we chose to log such information) is which IP addresses have enabled Watchtower. We are never in a position to know what sites you have in your 1Password data.

Baked-in privacy

It may take a bit of extra work from us to design Watchtower in a way that preserves your privacy, but we think it is worth it.

Your privacy must be protected by more than mere policy (a set of rules we make on how we behave with respect to data about you); instead, we aim to bake privacy protection into the very structure of what we build. We design 1Password in a way that would make it hard for us to violate your privacy.

You can read more about this approach to privacy in our support article, Private by Design.

mind your ps and qs

When back doors go bad: Mind your Ps and Qs

This is going to be a long and technical article, but the point can be stated more simply:

The kinds of security architectures in which it is easy to insert a back door are typically less secure than the security architectures in which it is hard to insert a back door. The back doors that have been recently been disclosed in Juniper Networks’ ScreenOS firewalls exemplify this point dramatically. It is also possible that the back door technology developed by the NSA is being used by some entity other than the NSA.

Perhaps the Economist put it better in When back doors backfire:

The problem with back doors is that, though they make life easier for spooks, they also make the internet less secure for everyone else. Recent revelations involving Juniper, an American maker of networking hardware and software, vividly demonstrate how. Juniper disclosed in December that a back door, dating to 2012, let anyone with knowledge of it read traffic encrypted by its “virtual private network” software, which is used by companies and government agencies worldwide to connect different offices via the public internet. It is unclear who is responsible, but the flaw may have arisen when one intelligence agency installed a back door which was then secretly modified by another.

Two kinds of back doors

There were two back doors in Juniper’s ScreenOS that were fixed by Juniper, the mundane one and the interesting one. The mundane one was a back door into the authentication system, allowing someone with knowledge of it to simply log in and administer the devices. Back doors in authentication systems are easy to create, and are all too common. This, by the way, is why we try to build 1Password’s security on encryption rather than authentication. As I’ve argued before: Architectures that allow for back doors are bad for security.

The more interesting – and for my soapbox, more instructive – back door is cryptographic. It also presents a greater threat. It allows the holder of the back door secret to decrypt certain kinds of traffic that were supposed to be encrypted by the ScreenOS (VPN) server. The attacker only has to listen to network traffic that is encrypted as far as everyone else is concerned, but she will be able to decrypt that traffic with the knowledge of the back door secret.

Another difference between the two is that the mundane one is a simple password (disguised as debugging code) that is now known to the world and so any unpatched systems can now be logged into by anyone. That secret is now out. The cryptographic back door, on the other hand, is a very different beast. We know it’s there, and we know how it works, but we do not have the key. The secret needed to make use of the back door is still a secret.

I don’t want to suggest that the back door in the ScreenOS authentication system isn’t important. It is very worrisome on its own, given where ScreenOS is deployed. But we all know that it is easy to add a back door to something that is merely protected by authentication (no matter how many authentication factors one has in place).

Politically the questions about how that authentication back door got put into place in such an important product and who may have been using it is huge. But it offers nothing new from a technological point of view.

The cryptographic back door

Oh. I want to work for the NSA! Evil mathematicians just like Professor Moriarty!

—My daughter, upon learning about the Dual EC backdoor

The cryptographic back door key all depends on how something called Q was created. Q is not a number (nor is it a free man), instead it is a point on a special sort of graph. If Q was created randomly then there is no back door key and all is well and good. But if Q was created by adding P (another point on the graph) to itself some large number of times then knowing how many times P was added to itself becomes your back door secret.

You are going to see the equation

Q = dP

many times. Neither Q nor P are secret. But d is secret and it is the back door key.

No doubt you are thinking something like, “well if P and Q aren’t secret, can’t we all figure out what d is by dividing Q by P?” Shouldn’t

d = Q/P

Well, d kinda sorta does equal Q/P, but there just isn’t enough computer power around to perform the relevant calculation. I’ll save that bit of fun math to (much) further below.

Necessary historical background

I’m one of those people who when asked a simple question go into more historical background than many people appreciate. But here it really is necessary. Really.

ScreenOS (and others) used a cryptographic algorithm that was deliberately designed to have a back door that only the United States National Security Agency (NSA) was supposed to know about. The cryptographic algorithm is Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG). I will refer to that simply as “Dual EC” from here on out.

Dual EC was one of four DRBGs specified in NIST SP 800–90A, and leaving the back door aside it is still technically inferior to the other three listed in that document. The standard specified a P and Q but did not explain how they were chosen. In 2007 Dan Shumow and Niels Ferguson of Microsoft showed that if Q was created with something like Q = dP, then whoever had hold of d could decrypt traffic encrypted with Dual_EC.

In 2014, a group of cryptographers presented a great explanation of how knowledge of d can be exploited, and even presented a proof of concept (with their own Q) of doing this.

Back in 2007 nobody (well, nobody who was going to say anything) knew whether or not Q was created so as to have the back door. In September 2013 it became clear from some of the documents revealed by Edward Snowden Dual EC had been designed with the back door. The Wikipedia page on Dual EC has a useful timeline.

How many bad Qs?

For ’tis the sport to have the engineer
Hoist with his own petard
Hamlet Act 3, Scene 4

So far the story I’ve told would merely suggest that Juniper has some explaining to do about why it used a DRBG in the way that it did and why they chose one that was inferior to alternatives and was suspected of being backdoored. Juniper Networks are (sadly) not the only one in that position.

But I’ve only told part of the story. ScreenOS did not use the NIST Q. It used two custom Qs over time, and where they came from and who knows the back door keys associated with those Qs is something we simply don’t know. The back door key associated with the Q from the NIST standard is clearly held by the NSA. But what about the two used (at different times) in ScreenOS?

Juniper explained that they didn’t use the NIST Q in their Dual EC implementation but used a Q that was created randomly. However, they did not provide any proof that it was created randomly. (There are ways to demonstrably create such things randomly.) So we don’t know if that “official Juniper Q” was created in a way to give its creator a back door key. Nor do we know who might hold that key.

But there is a third Q that was, according to Juniper, inserted by parties unknown in 2012. That is someone simply changed the Q that is used in Dual EC in ScreenOS. We can only assume that this third Q is indeed backdoored, as it was something surreptitiously added to the code. We have no idea of who did this.

So even if we take Juniper at their word about their choice of Dual EC and other related design choices, the fact that the chose to use a system that was designed so that it could have a back door means that someone – we don’t know who – has had a back door key for decrypting VPN traffic between NetScreen devices for three years.

I have said it before and I will say it again, systems that are designed to have back doors (even if the back doors aren’t used) are inherently weaker than systems that are designed to make it difficult to have a back door.

Thar be math

The rest of this article tries to explain why it is easy to calculate Q from d and P but hard to calculate d from P and Q. Unless you have a great deal of patience and would like to learn more about the math, you can stop reading here.

Here is a picture of Patty and Morgan enjoying the pleasures of warm blankets on the sofa. Morgan also has no patience for math.

Dogs on couch, not doing math.

Patty and Morgan relaxing on couch. Not doing math.

Hard math, simple math

The actual math isn’t all that complicated, but it does rely on a number of unfamiliar notions. Some of these notions are hard to grasp not because they are complicated, but because they are simple. They are highly abstract. Indeed, you might even have to unlearn some things you know about addition.

I said earlier that even though P and Q are public, we can’t figure out what d is in Q = dP, but someone with d and P can easily construct Q. I’m not going to fully explain all of this, but I’m going to make an attempt to try to help people get a better sense of how something like this might be true. Along the way, I’m going to tell a few lies and omit lots of stuff. I need to lie to stand a reasonable chance of this article being useful to people who don’t already know the math.

One thing I should tell you right away is that P and Q are not numbers, while d is a number. I will get around to explaining what P and Q actually are below, but first we need to understand what it means to add two things together.

I am not going to try to explain how knowledge of d provides a back door. That is something that is difficult enough to explain in the normal case and is even harder given how Dual EC is actually used within ScreenOS. (See Ralf-Philipp Weinmann’s “Some Analysis of the Backdoored Backdoor” for some of those details.)

Instead, I’m focusing on a narrow point, allowing me to go into more depth about something that is central to modern cryptography.

Simple addition

Most of us have a pretty good sense of how addition works. We all pretty much know that the “+” in “3 + 5 = 8” means. We may not be able to define it precisely, but it is a basic concept that we understand. Well mathematicians like to define things precisely and more importantly they like to distill things down to their simplest essence. Let’s see what the essential properties of addition are.

What are we adding?

To define addition we need to talk about what things are going to be added to what things. The expression “3 + blue” doesn’t mean anything because “blue” and “3” are not in the same set of things we might add. We might want to talk about adding colors, and so could reasonably say “red + blue = purple”.

Blue + Red = Purple

Addition can apply to more than just numbers.

Sometimes we add numbers; sometimes we add colors; but we need to have a set of things (numbers perhaps, or maybe colors) that we will be adding.

So let’s call the set of things that we will be adding E for an ensemble of things. When we are adding numbers, “blue” won’t be in E, but when we are adding colors, “blue” may very well be in E. When we are adding colors, 3 won’t be in E but it will be when we are adding whole numbers.

For the addition that most people are used to, there are an infinite number of things in E, but that doesn’t have to be the case. When we add hours to know what time it will be 15 hours after 9 o’clock, we use only 12 (or 24) of course. Remember, we are trying to distill addition down to its essence, so we want it to work both when E has a finite number of things in it as well as when it doesn’t.

Addition offers no escape

If we are adding numbers, we don’t want 3 + 5 to equal “blue”. We want 3 + 5 to result in another number. If we are adding colors, we want the result of addition to be some color.

So we will say that

If a and b are both in E then a + b is also in E.

The fancy name for this is “closure”, or “E is closed under addition”.

You can switch things around

We like addition to work out so that “a + b” will yield the same result as “b + a”, so we say that

If a and b are both in E then a + b = b + a

We say that addition is “commutative”.

Any groupings you want

When you mix blue and red and white, it doesn’t matter if you mix the blue and the red first or the red and the white first. Likewise if you add 3 + 2 + 10, it shouldn’t matter whether you add the 3 and the 2 first or the 2 and the 10 first.

If a, b and c are all in E then (a + b) + c = a + (b + c)

And so we say that addition is “associative”.

We need a way to do nothing.

I have no problem grasping the importance of doing nothing, but not everyone seems to agree with me (Hi boss!). Anyway, we need a way to do nothing with addition.

To put that more mathy, we want E to contain something that behaves like zero. If you add zero to anything, you end up with what you started with.

If a is in E and 0 is the zero element then a + 0 = 0 + a = a

For the color adding analogy, we might add the special color “transparent” as our zero element so that blue + transparent = blue.

The fancy way to talk about zero is to call it “the additive identity”.

Adding it all up

Mathematicians are happy to call anything that meets those four conditions “addition”.

Getting to the points

So we can add numbers and we can add colors. But let’s talk about points on a peculiar geometric shape called an elliptic curve. Here is a portion of an elliptic curve, and it has two points on it, P and Q. (These aren’t the same as P and Q used in Dual EC.)

Elliptic curve

Elliptic curve with points P and Q

There are some interesting properties of these odd sorts of shapes. One of them is that if a (non-vertical) straight line crosses the curve at all, then it will cross it in exactly three places.

For example, if we draw a line that goes through both P and Q then that line will go through the curve at exactly one other point.

Line P,Q on elliptic curve

The first step in adding points P and Q is drawing the line connecting them and seeing where else that line crosses the curve

From that third point where the line crosses the curve we can find the point on the opposite side of the curve by drawing a vertical line up or down (as needed) from that point of intersection:

Addition of P, Q on elliptic curve

Draw a vertical line from where the line between P and Q crosses curve to get point P + Q

Now as strange as it might seem, if we define addition of points on an elliptic curve this way, it will meet all the properties of addition that we want. (I’m leaving out how the zero element is defined, and have constructed my examples so that I can get away with that.)

Repeated addition

Now let is return to the problem we started out with. If Q = dP how come it is easy to calculate Q if we know d and P but not d from Q and P? P and Q are points on the curve, while d is just an ordinary (though very large) number.

Well, we’ve defined what addition means for points, but what does it mean to say, for example, “4P”? “4P” is just shorthand for writing “P + P + P + P”. (Note that we can treat “4P” kind of like multiplication, but only because 4 is an ordinary number and we can just say that it is repeated addition of P. We haven’t defined any way to multiply two points together.)

Let’s work through a small example and try to find where 4P is. The first thing we need to do is add P to itself to get 2P.

We’ve already stepped through how to add two different points, but how do we add P to itself? We take as our line going through P and P to be the tangent line at point P. This is the line that touches point P but does not cross the curve at P:

Tangent at P on elliptic curve

The tangent line at P crosses the curve in exactly one other place.

That line crosses the curve at some other point. And just as we did when we added P and Q earlier, we draw a vertical line through that point of intersection to get our sum:

Adding P+P on elliptic curve

When adding a point to itself, we take the tangent at the point to construct the P,P line

Now we have point P, which we started with, and we also have point P + P, or 2P. So if we want to find 3P we can just add P and 2P together.

P + 2P = 3P on elliptic curve

Add 2P to P to find point 3P on the curve.

This gives us point 3P and we can add 3P and P together to get to our goal of 4P:

P + 3P = 4P on elliptic curve

To get point 4P, we add 3P and P.

A shortcut

It took us three additions to calculate 4P from P. But we could have saved ourselves one of those. We never really needed to calculate 3P. Instead once we had the point 2P we could have just added 2P to itself to get 4P. Because point addition is associative, we can think of 4P as (P + P) + (P + P), which is 2P + 2P.

4P = 2P + 2P on elliptic curve

Adding 2P to itself is another way to get 4P

With this shortcut, we have been able to calculate 4P from P with only two additions: The first addition was adding P + P to get 2P; the second addition was 2P + 2P to get 4P.

The shortcut offers huge savings

When calculating 4P our shortcut saved us only one addition, but the savings get bigger the bigger d is. Suppose we wanted to calculate 25P. The slow way would require 24 additions, but using this shortcut, it would only take us six additions.

  1. 2P = P + P
  2. 4P = 2P + 2P
  3. 8P = 4P + 4P
  4. 16P = 8P + 8P
  5. 24P = 16P + 8P
  6. 25P = 24P + P

So having to only do six of these additions versus 24 by the slow way is a big savings. When the numbers get really big, the savings get much bigger. Suppose we wanted to calculate the result of adding P to itself one billion times. 1000000000P would take almost a billion additions the slow way, but using the short cut we can do it with only about 45 additions.

The number of point additions it takes to calculate dP using this shortcut is roughly proportional to the number of bits in d.

No shortcut to d

So we’ve got a really efficient way to compute Q from d and P, but there is no efficient shortcut for finding d from P and Q. Indeed, this asymmetry between calculating d versus finding d is one of the things that makes elliptic curve cryptography work.

When numbers get big

When we start talking about the huge numbers that cryptographers actually use for these sorts to secrets we get truly massive savings. Those savings are so big that using the shortcut means that we can calculate the result in a fraction of a second, while doing it the slow way would take all of the computers on earth many times the age of the universe to compute.

The number of point additions needed to calculate Q=dP is roughly proportional to the number of bits in d, while the number of additions needed to find d from P and Q using the slow way is roughly d. As d gets big (say a 256-bit number), the difference between d and the number of bits in d is enormous. For a 128 bit number, calculating Q takes less than 256 point additions, but calculating d takes a number so large that I don’t know how to write it out. It would have 77 digits. To get a sense of just how big numbers like that are, take a look at “Guess why we’re moving to 256-bit keys

And if I may introduce more terminology, that asymmetry is an instance of what is called the “Generalized Discrete Logarithm Problem” (GDLP).

What is the GDLP good for?

To give you a hint of how this sort of stuff can be used for keeping secrets, suppose that two of my dogs, Molly and Patty, wish to set up secret communication without Mr. Talk (the neighbor’s cat) listening in. The dogs will need to establish between them a secret key that only they know, but how can they do this if Mr Talk is listening in to their communication?

First Patty and Molly will agree on an elliptic curve and some other non-secret parameters. Among those parameters there will be a starting point, that I will call G. Let’s let Patty pick a secret number that only she knows and we will call that little p. Patty will calculate the point pG. Let’s call the point that Patty calculates big P.

Patty can send P to Molly, but neither Molly nor Mr Talk (who is eavesdropping) will be able to calculate little p, even though they both know G and P. Big P is Patty’s public key, while small p is Patty’s private key.

Molly can do the same. She calculates M = mG, where little m is Molly’s secret, and sends big M to Patty.

Now here is where it gets fun. Patty can calculate point K_p by multiplying M by little p. That is

K_p = pM

Molly can also calculate K_m by multiplying Patty’s public key, P, by Molly’s own secret, m. K_m = mP.

The Ks that both calculate will be the same. This is because point addition is commutative and associative. Remember that M = mG. So

K_p = pM = pmG.

We can look at what Molly calculates from Patty’s public key the same way: P = pG. When we look at what both Molly and Patty calculate with their own secrets and the other’s public point, we get

K_m = mP = mpG = pmG = pM = K_p

Let’s look at each end of that long chain of “=”s, but drop out all of the middle parts.

K_m = K_p

Both Molly and Patty calculate the same secret K even though neither of them have revealed any secret in their communication. And Mr Talk, who has listened to everything Molly and Patty sent to each other, cannot calculate K because there is no feasible way for him to learn either Patty’s secret p or Molly’s secret m.

This is magic with mathematics.

Lies and omissions

There are a lot of things that I left out of the explanation I gave here. And in a few cases I even told a couple of lies to make the explanation simpler. I’m only going to mention some of them here.

  • The shortcut that I described for computing Q from p and D is not the most efficient shortcut, but it is an efficient shortcut that is easiest to explain.
  • There are shortcuts for calculating d, but there are thought to be no efficient non-quantum ones.
  • I have not explained what I mean by “efficient”. (It is a technical term.)
  • I haven’t told you the formulas for doing addition of elliptic curves, I only did it with pictures.
    Text exchange about EC science fair project

    So my daughter texted me a picture of a science fair project she saw. I texted back.

    It looks like someone at my daughter’s high school did a science fair project on finding good algorithms for point doubling. Thus forcing me to reveal just how much of a pushy and intrusive parent I am.

  • To make addition on elliptic curves work as an instance of the GDLP, we need to make it have only a finite amount of elements. That involves, among, other thing, making all of the normal arithmetic in the formulas done modulo some large prime number.
  • I didn’t talk about the additive identity (zero element) for addition on elliptic curves.
  • I never said what “=” means when I defined addition.
  • I kinda sorta misused the terms “public key” and “private key” when applying those terms to ECDHE.
  • I didn’t say anything at all about the existence of additive inverses.
  • The addition of colors analogy stops working if we were to consider additive inverses.
  • I implied that all and only the properties I listed for addition are what is needed for something to be called “addition”. The properties that I listed plus the existence of additive inverses are what is needed for the specific type of addition we need for this cryptography. Addition of numbers requires something more because numbers – unlike points on an elliptic curve or colors – line up in an order.

The after math

I’ve been able to use an example of a rare cryptographic back door to give me the chance to talk about the math of elliptic curves cryptography. But if you are asking what this has to do with AgileBits and our products (after all, we don’t use elliptic curves in our products), then we must return to the original point: If you build a system into which it is easy to add a back door, you shouldn’t be all too surprised when a back door is added. So let’s not build things that way.

I will close with another quote from that Economist article:

Calls for the mandatory inclusion of back doors should therefore be resisted. Their potential use by criminals weakens overall internet security, on which billions of people rely for banking and payments. Their existence also undermines confidence in technology companies and makes it hard for Western governments to criticise authoritarian regimes for interfering with the internet. And their imposition would be futile in any case: high-powered encryption software, with no back doors, is available free online to anyone who wants it.

Podcast header

Jessy on authentication and passwords in premiere of On the Wire podcast

Jessy Irwin On the Wire

On the Wire is a new podcast about the security threats we face and how we can protect ourselves against them. It’s hosted by our friend Dennis Fisher, who was previously behind the podcast at Threatpost.

The new podcast covers such topics as privacy, fraud, and social engineering. It aims to do so in a simple way that’s easy for everyone to understand. A lot of this stuff goes right over my head, which is why I’ve been relying on 1Password to secure my digital life for so long! I’m looking forward to listening to a security-centric podcast that doesn’t make my eyes glaze over.

The first episode of On the Wire is extra special because it features Jessy, our Security Evangelist! Listen to Jessy talk about the state of authentication, passwords, and security education.

To listen to the episode, you can stream it on the On the Wire website.

Security header

1Password and your browsing habits: What we don’t know can’t hurt you

1Password blueprintThere are some things that we would love to know about people who use 1Password. Some of that information would be useful in improving 1Password, some might just be interesting statistics about our users. Here are a few things we might want to know:

  • What sites are among your 1Password data
  • When, how often, and from which IP address you use 1Password to log in to particular websites
  • Which new Logins you save
  • How often and where you fill credit card data

Knowing such things about our customers would help us focus our development efforts on the things that people want to use most. But here is the point of this article: We do not have that information and we have built 1Password so that it would be hard to even collect that information. Our principle of Private By Design means that we don’t know many things. This is for your benefit.

We have no such data

Despite our curiosity and the usefulness of such data, we have designed 1Password so that we can never see that information. We’ve written before about how our security architecture protects your privacy (see Private By Design and the opening sections of our 1Password for Teams white paper [PDF]), but I will highlight some of its points below.

The importance of knowing nothing

One of our design principles is based on the fact that we cannot lose, use, or abuse data that we never have. We believe that you should be in control of your data and that your use of your data is your business. To the extent possible, we have built 1Password in such a way that not only do we not retain data about your use of 1Password, but we make it hard to even obtain such data.  We have also chosen not to include any in-app analytics tools within 1Password.

Some of this is basic security design. Our design principle isn’t radical in theory, but it can be difficult to implement. For example, our underlying data synchronization system would be much simpler if we allowed ourselves to know which sites you are logging in to when you log in to them. But because we do not want to ever know that information, we have had to put in more intricate machinery.

I should also acknowledge that some of our design principle is motivated by cowardice. We do not want our servers and systems to be heavily attacked, so we have designed our systems such that we have little worth stealing. Our cowardice here works to protect your privacy and your security. Cowardice can be a virtue.

Example: We can’t watch from the Watchtower

1Password WatchtowerA relatively simple example of our privacy mechanism is how Watchtower works in 1Password for Mac and Windows. 1Password does not send a query to our server to ask, “Is site X in the Watchtower database? What does it report?” If we had built it that way, our server logs would be able to determine exactly which sites are in your 1Password data. Instead, 1Password fetches all of the information needed by Watchtower on your computer. Every instance of 1Password is fetching the same data file in a way that does not depend on which Logins you have.

Security designs matter

I would like to step back and look at a picture that is perhaps even bigger than the privacy matters discussed here. Please indulge me in my musings.

We are proud of the overall security design of 1Password, and we certainly like to talk about it. Yet very understandably most people are not going to look at the subtleties of the design and its implications. As a consequence, some of the things that we think are the biggest security benefits of 1Password are invisible to users, and so we occasionally hit you with articles like this.

Sometimes our security design makes certain “features” irrelevant and inapplicable. See Authentication v Encryption for a discussion of one such feature. Sometimes, as in the example of Watchtower described above, it means that we have to work harder to put a feature in place than we would have if we’d used a different security design. But even when we have to work harder, we believe that our security design is the better choice. To maintain a privacy-preserving security architecture we are happy to do the extra work.

Security header

How 1Password for Teams protects your secrets

Since this is my first AgileBits byline, allow me to introduce myself. Last month, I joined the awesome security team here at AgileBits. I’m super excited to work with Jeffrey Goldberg, our Chief Defender Against the Dark Arts, and Jessy Irwin, our resident Security Evangelist. I aim to review product security and keep bad things from happening to good people. In addition, I write readable things: I’ve got a number of blog posts on deck that I look forward to sharing with you fine folks.

With pleasantries exchanged, let’s talk about 1Password for Teams, and about how your privacy and the security of your data are of the utmost importance to us. We are able to offer the great new features of 1Password for Teams by providing it as a service. If you are using 1Password but don’t have a 1Password for Teams account, your existing vaults remain unchanged, whether you sync them using Wi-FI, Dropbox or iCloud. While we have made some significant changes to how your data is stored in 1Password for Teams, our commitment to security and privacy has not changed.

How 1Password for Teams keeps your data safe

When we set out to build 1Password for Teams, our first concern was that our cryptography and security be absolutely top notch. I mention them both because they work hand in hand to keep your data secure. We opted for security that is enforced by cryptography instead of software or personnel policy.

Cryptography is what makes your data completely worthless to hackers. It is our cryptography that ensures that even if someone were to hack into our servers they would be able to access nothing more than a bunch of random numbers.

Security is what ensures that there are no back doors or vulnerabilities in the code. Security has to do with the assurance that certain policies are enforced by the operating system. Specifically, that there are no workarounds or back doors into our servers.

Private by Design

We take the “privacy by design” approach because we believe that we can best protect your secrets by not knowing them. It is impossible to lose, use or abuse data one doesn’t possess. Therefore, we designed systems that reduce the amount of sensitive user data we can access or acquire.

Triple-Layer Cake

1Password for Teams stores your encrypted data on our servers, but neither your Master Password nor your Account key is ever sent to our servers over any network. This means that we do not actually have the ability to decrypt your data. That is because decrypting your data requires all three of the following:

If you use 1Password, you are already very familiar with the Master Password and its role in protecting your data. Let’s talk about the other two pieces of the puzzle: the Account Key and the Secure Remote Password.

The purpose of the Account Key is to protect your data from being decrypted by someone who might access or compromise our servers. It ensures that a password-guessing attack against your data is useless: even if an attacker were to correctly guess the Master Password, the vault would not unlock.

The Secure Remote Password (SRP) is a way for both the client and the server to authenticate each other without either revealing any secrets. The SRP encrypts all traffic over the network and verifies the authenticity of the remote server before sending your information over TLS/SSL.

In Math We Trust

These three pieces of information work together to symbiotically protect your data. The Account Key strengthens your Master Password exponentially. And since it never gets sent over the network, it can’t be reset, intercepted, or evaded. In fact, I would be happy to print out a 2D barcode of all of the information in my 1Password for Teams personal vault and tape it to my front door. And if you knew me, you would know that this is a very big deal.

Still have questions? You can read all of the details of how we secure your data and why we made the decisions we did by reading our White Paper (PDF). Please also leave us a comment below or join the conversation in our discussion forums. We love hearing from you!

Shield Security header

When a Leak Isn’t a Leak

Over the weekend Dale Myers wrote a blog post that examined our .agilekeychain format. The post featured a good discussion and analysis of our older data format, but it raised some questions among 1Password users and the wider technology community.

Dale states that he plans to continue using 1Password and has no concerns over the safety of his passwords themselves, but his main concern was how the AgileKeychain handles item URLs. While we widely documented this design decision and shared it publicly, Dale was surprised to find out that we didn’t encrypt URLs within the keychain. We want to reassure users that rely on AgileKeychain that their password data is safe and secure, and take the time to walk through our data formats to explain the issue completely.

AgileKeychain & OPVault Data Formats

Back in 2008, we introduced the AgileKeychain as a way to help our users better synchronize data across platforms and devices. At this time, 1Password had significantly less processing power to draw from for tasks like decryption, and doing something as simple as a login search would cause massive performance issues and battery drain for our users. Given the constraints that we faced at the time, we decided not to encrypt item URLs and Titles (which resembled the same sorts of information that could be found in browser bookmarks).

In December 2012, we introduced a new format that encrypted much more of the metadata. OPVault, our newer and stronger data format, provided authenticated encryption as well as many other improvements for 1Password users.

This format worked well in situations where we didn’t need to worry about backwards compatibility, including iCloud and local storage on iOS and Mac. For Windows, Android, and Dropbox syncing, however, we needed to decide if we should migrate to the new format or provide compatibility with older versions of 1Password.

We decided to take a conservative approach and not automatically migrate everyone over to OPVault because many users depend upon older versions of 1Password and they wouldn’t be able to log into their accounts. We knew we could trust the security of the AgileKeychain to protect confidential user data so we didn’t want to rush into something that would disrupt people’s workflows.

Switching to OPVault

Despite the security of AgileKeychain remaining intact, Dale reminded us that its time to move on. The OPVault format is really great in so many ways and we should start sharing it with as many users as possible.

We’ve already started making changes to use OPVault as the default format. In fact, the latest beta of 1Password for Windows does this already. Similar changes are coming to Mac and iOS soon, and we’re planning on using the new format in Android in the future. Once all of these things are complete, we will add an automatic migration for all 1Password users. For users who would like to switch to OPVault sooner than this, here’s how you can get started immediately:

To avoid losing access to your data, be sure to back up your 1Password data beforehand, and only follow these instructions if you are NOT using any legacy versions of 1Password. If you have any questions or concerns, or would like to migrate but aren’t sure if your version of 1Password is affected, our knowledgebase, forums and support team are here to help.

1Password tips

Quick Tip: iOS 9 Spotlight search and 1Password

Some of the geekiest arguments I’ve ever heard have been over the way people organize apps on their iPhones and iPads. I keep my most heavily used apps on my main screen, then shove almost everything else into folders on my other screens.

The reason I can do this is because of the wonders of Spotlight search. It’s easy for me to search for and launch the app I want to use, so I don’t have to spend my mental energy trying to remember where I’ve put things.

Apple opened up Spotlight to third-party developers like us in iOS 9. My searches are now supercharged! I’ve gotta say, I love being able to find my 1Password items right from my iPhone’s home screen. I enabled Spotlight search in 1Password by going to Settings > General > Enable Spotlight Search. Now I can just pull down, type in part of the item’s title, then tap on its name in the search results. 1Password opens right to that item.

iOS 9 Spotlight search

You might have questions about the new Spotlight search and how it works with 1Password, so I put together some answers for you. If your question isn’t addressed, please let me know; I’ll be sure to update it in response to your feedback.

I’m also curious: what are your favorite iOS 9 features? Let me know in the comments!

Security

Everything you need to know about 1Password and XcodeGhost

Over the past few days, security researchers from Palo Alto Networks discovered that 39 apps infected with malware found their way into the Apple App Store in China. Since the news broke, the malicious apps have been pulled from the App Store— and we’ve had a few questions about what this might mean for 1Password and password managers in general. To put your mind (and your passwords!) at ease, we’re answering some of the most common questions and concerns that iOS users have had about malware, compromised apps, and the security of 1Password.

So wait… what happened? How did this get in the App Store?

It’s kind of a long story, but we’ll make it short. In software development, there are many, many tools that can be used to build an app, and iOS developers rely on a compiler called Xcode as part of that process. A compromised version of that compiler made its way to the web in China, and was downloaded from an untrusted source. In this case, all apps built using the malicious compiler, XcodeGhost, were modified to sneak malicious code into the App Store. Though Apple works to review and screen apps for malware before they reach the App Store, in this case Apple confirmed that the attackers were able to make it through the review process without raising any red flags.

What does this malware do?

In general, most malware is designed to capture personal information and/or user credentials, and send them back home to the attacker who compromised your device. While XcodeGhost does not directly affect the 1Password application, it indirectly affects those who use the application through your device’s clipboard. In a post outlining the malware’s capabilities, senior malware researcher Claud Xaio noted that this particular strain could:

  • Prompt a fake alert dialog to phish user credentials
  • Hijack opening specific URLs based on their scheme, which could allow for exploitation of vulnerabilities in the iOS system or other iOS apps
  • Read and write data in the user’s clipboard, which could be used to read the user’s password if that password is copied from a password management tool.

Additionally, according to one developer’s report, XcodeGhost has already launched phishing attacks to prompt a dialog asking victims to input their iCloud passwords.

Should I be worried? Does this affect me?

There are a few very specific factors that determine whether your device is at risk, but overall, this vulnerability is a rare occurrence for the App Store.

  • At present, this issue mostly affects devices using the Chinese App Store, though researchers have found compromised apps in the Canadian App Store as well.
  • The malware is only in applications built using a compromised code compiler. A list of affected apps can be found on the Palo Alto Networks blog, but security researchers believe that as many as 344 apps may be vulnerable to the attack.

Will 1Password protect my data if an app on my iPhone or iPad has been infected by XcodeGhost?

We have designed 1Password with your privacy in mind at all times. We use strong, reliable encryption and take many, many measures to make our application breach-resistant. Combined, the many layers of security we’ve implemented work together to secure your passwords and protect your most sensitive data— but if your device has been compromised, there’s almost nothing that 1Password can do to defend it. As previously stated in a post on malware by Jeffrey Goldberg, our Chief Defender Against the Dark Arts:

I have said it before, and I’ll say it again: 1Password […] cannot provide complete protection against a compromised operating system. There is a saying […] “Once an attacker has broken into your computer […], it is no longer your computer.” So in principle, there is nothing that 1Password can do to protect you if your computer is compromised.

Eek! My phone is infected with this— what should I do?!

First (and most importantly): don’t panic! There are a few simple things you can do to to return things to normal. If you’re positive that you’re using an app that was affected, here’s what you can do immediately to protect your data:

  1. Delete the compromised app(s) from your phone. If you are uncertain about whether an app has been compromised, it’s okay to delete it out of an abundance of caution.
  2. Change any passwords that you think may have been compromised through your device’s clipboard. Any passwords that you may have accessed through the 1Password extension are safe from this strain of malware, and do not need to be changed.
  3. Avoid redownloading or reinstalling any of the compromised apps until they have been updated. When an update has been released, be sure to download it from a trusted source once the developer has officially confirmed that a new, secure version is ready for you to use. If you’re uncertain of this, you can visit the developer’s site or check with their support team for help.

The XcodeGhost vulnerability doesn’t directly affect 1Password— we have not used the malicious version of Xcode, and the malware it injects into applications was not designed to directly compromise or target our application. Though the malware in compromised apps on any platform has the potential to put any user’s credentials at risk, especially when it can access a device’s clipboard, all technology users benefit from the work security researchers do to find vulnerabilities like this.

If you’ve made it this far down the post and still have questions or concerns, please leave a comment here or start a conversation with us in our discussion forums. You can also reach out to us on Facebook and Twitter.