Posts

Large even prime number discovered

You have probably been taught that two is the only even prime number. But today mathematicians at the University of Southern North Dakota at Hoople have discovered a new, large, even prime. It is more than a million digits long and is equal to the value of 3²²³⁷⁵⁶¹+3¹¹¹⁸⁷⁸¹.

Many people are under the erroneous belief that two is the only even prime number, but as Professor Paul Forester explains, “tings get really meshuga vhen numbers get large.” For example, when some number n gets very large, it becomes approximately the same as its successor. Because:

\displaystyle\lim_{n \to \infty} \frac{1}{n} = \frac{1}{n+1}

we can see that n must get closer and closer to n+1 when n is very large. So when numbers are pretty much the same as their neighbors at these large values, the notion of odd and even don’t hold in the traditional sense.

What does this mean for cryptography

First of all, this surprising mathematical discovery has no (immediate) bearing on the security of 1Password, as 1Password does not use the kind of cryptography that depends heavily on the theory of prime numbers. But this might have some implications for cryptography. At the moment, the only immediately visible impact is that it should make some of the slowest cryptographic computations quicker and more efficient.

In some cryptographic systems (though not 1Password), the software must generate large, randomly chosen prime numbers. This is a very time consuming process, and it works by first picking large random numbers, then checking whether they are prime through a series of tests. Almost all software implementations of this will only pick odd numbers by setting the least significant bit of the random number of 1. But this excludes half of the numbers it could pick, thus failing to find any of the even large primes.

Testing for primes

Once a random number is picked in the appropriate range it needs to be tested for primality. Many of the tests result in answers that aren’t quite definitive. Indeed, a number of tests produce results of either “definitely not prime” and “possibly prime” and each of these tests may different amounts of time to run. The general strategy is to run the quickest tests first on your candidate number, and only then run the more expensive tests. If your candidate number passes a sufficient number of those tests, then you can determine with sufficiently high probability that the number really is prime.

There is a way, of course, to definitively test whether a number, N, is prime. And that is to attempt to divide by every prime number less than or equal to the square root of N. But while that approach if definitive, it is simply far too many divisions to actually test.

The prime numbers in cryptography

The prime numbers used in cryptographic systems are typically 1024 bits (about 308 digits) long. Pairs of these are generated and multiplied together to produce 2048 bit (about 616 digit) products. Note that when you multiply, say, a five digit number by a three digit number you usually end up with an eight (five plus three) digit number. This holds when using bits instead of decimal numbers. So the product of two 1024 bit numbers will typically be a 2048 bit number.

Even for 300 digit numbers, which are far, far smaller than the million digit prime announced Saturday, it isn’t feasible to run definitive primality tests in the time we need when picking prime numbers. Indeed, it is probably near the edge of the NSA’s capability to factor 1024 bit products of 512 bit primes. This is why it is no longer recommended to use 1024 bit RSA keys.

A note on key sizes

If I am saying that 1024 bit keys aren’t safe, why does 1Password “only” use 256 bit keys? This is because different kinds of encryption systems have different kinds of keys. Keys used for the AES algorithm are completely random numbers. Guessing the key means trying every single 256 bit key until you find the one that works. That just isn’t possible even for a 128 bit key. But for public key encryption systems, not just any public key will do. Not just any 2048-bit numbers can be an Rivest-Shamir-Adleman (RSA) public key. Instead, it must (essentially) be the product of two 1024-bit prime numbers (which are, in essence, the private key).

I say “essentially” in there because if two prime numbers are p and q, then the actually public key isn’t p times q, pq, but is in fact Φ(p)Φ(q), which works out to (p-1)(q-1) in this case. The Φ function is known of as Euler’s totient function. For quite some time, I believed that there was a mathematician whose name sounded like “Oiler” who worked on similar stuff as the mathematician I’d read about, whose name I pronounced “Yuler”. Along the same lines, it was only when someone read the Little Prince aloud that I realized that the word I’d heard as “yu-neek” was the same as the one that I pronounce “un-ee-cue”. I still think of the Prince as “un-ee-cue in all the world.”

Let’s get back to key sizes. Not every public key system uses the RSA algorithm. The Diffie-Hellman (DH) system uses different mathematics, but has key length requirements similar to RSA. 1024 bits is no longer considered secure against the likes of the NSA. The third kind of public key algorithm in use is based on elliptical curves, and is sometimes called ECDH because it is actually based on the same logic as Diffie-Hellman at its heart, though it works through different mathematical operations. One advantage of ECDH is that it works with much smaller keys. So a 256-bit ECDH key is perfectly reasonable.

What to trust in this article

This article was posted on April 1, 2014. The claim that an even prime number other than two has been found is bogus. The notion of odd and even holds for all integers, no matter how large. The fictitious University of Southern North Dakota at Hoople is the creation of the real Peter Schickele. The fictitious mathematician Paul Forester is my resurrection of the great 20th century mathematician, Pál Erdős. Everything else here is actually meant to be reliable information. Including those bits that are un-ee-cue in all the world.

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

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

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

AES? Keys?

1P logo in AES

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

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

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

Talking about big numbers

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

2128 in words

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

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

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

Searching for keys is harder than digging up bones

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

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

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

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

How long is long?

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

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

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

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

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

The difference between zero and zero is zero

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

It takes a lot of dog food to keep Patty searching

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

The answers to some questions remain TOP SECRET

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

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

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

When Bruce Schneier advises:

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

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

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

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

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

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

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

So why 256 bits now?

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

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

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

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

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

2. Tougher key derivation

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

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

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

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

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

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

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

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

In conclusion

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

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

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

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

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

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

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

 

Authenticated Encryption and how not to get caught chasing a coyote

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

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

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

 Why use a MAC?

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

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

a3b3a8b79c135ff5b9a0aa6f5c304b411f07f90c.

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

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

MACs on encrypted data

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

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

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

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

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

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

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

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

What happened to Molly?

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

Restraining Molly

Doing the two-step until the end of time

Enigma machineIn my discussion of Dropbox’s new two-step authentication, I skimped on the cryptography. Because we had to move quickly, I wanted to focus at the time just on our recommendations, so I told a few fibs about how the way the six digit codes “get” to your phone. Now I want to explain how it really works.

Not only that, but I will sneak in a little introduction to Message Authentication Codes (MAC), which plays a major role in our newest version of the 1Password data format. This topic is also worth revisiting because our new release, 1Password4 for iOS, works well with Dropbox’s two-step verification.

Speaking of, let’s start with Dropbox’s two-step authentication system. I did try to warn readers that I was being less than forthcoming about the full truth when I suggested that a six digit code is sent from Dropbox (or Google) to your phone:

There are also some really cool things about how the protocols for two-factor authentication work, but I will bite my tongue and leave that discussion for another day. What this means, however, is that a great deal of what I say in describing the system below is a pack of lies.

Even my word “protocol” could be confusing, as it might imply some network activity. The magic of the system is that anything using this type of Time-based One Time Password (TOPT) tool will compute the same six digit code at a particular time with the initial set-up secret. Dropbox’s login system will calculate the six digit code on its own; and a tool that you use, such as Google Authenticator, will also calculate the six digit code on its own. No network connection is needed after the first time setup.  In my example below, I’ll use Google Authenticator, but it isn’t the only TOPT tool out there.

Initial set up

When you first set up something like the Google Authenticator you scan in a QR code. It might look something like this:Sample QR code for setting up authenticator

The code contains a label that will typically be “Dropbox:your-email@example.com”, and it contains a secret that is randomly generated and unique for each account. The secret might look like “MQZDKZRZGBRWMMZXMI4TCMZUMYYDKYTC”. Putting this inside of a QR code just saves you a lot of typing. If you don’t have a camera that can be used to scan the code, there is even a link for getting the information that you should type in. Scanning this in is the only time that information will be transmitted (in this case, transmitted via your phone’s camera) from Dropbox to Google Authenticator.

Google Authenticator on your phone will keep a copy of the secret, and so will the Dropbox servers. That shared secret allows both Google Authenticator and Dropbox to calculate the same six digit codes when needed.

Counting on time

When you log into Dropbox with your username and password you will then be prompted for the six digit code if you have enabled two-step verification. You will then open Google Authenticator on your phone and you will see six digits. Those six digits are computed from a combination of the the shared secret and the current time. The current time is the number of seconds since the first instant of 1970. It is rounded down to the nearest half minute. This is why the number changes every thirty seconds.

Dropbox website prompting for security codeWhen you enter the six digit code during Dropbox’s login process, Dropbox will perform the same calculation. It has a copy of the secret that was first shared, and it too knows the current time. If what you enter matches what it has calculated, you’re in.

Your phone will not need any network connection as long as its clock is reasonably accurate. Fun fact: your phone actually makes minor adjustments to its clock pretty much every time it connects to any kind of network that allows it to check a time server on the internet. Today, most networked computers and devices know the current time to within less than one 10th of a second.

Because the code depends on both the time and on the shared secret, we end up with a different code during each 30 second period. This makes it a one time password.

Beyond the end of the world (January 19, 2038)

Ancient eunuchs foretold global catastrophe on January 19, 2038, as their long count calendar comes to an end and starts a new cycle from zero

—Anonymous

Aztec sun stone (replica)

Replica of the Aztec sun stone. This has nothing to to with Unix or Mayan time keeping.

The number of seconds since the very beginning of 1970, known as Unix time, is often maintained in a single variable in the computer’s operating system. When Unix was first designed, this number was stored in 32 bit variable. That means that the number could range from 0 to 232. Zero corresponds to the midnight January 1, 1970 (UTC). So what time does 232 correspond to? That will be 3:14:07 (UTC) on January 19, 2038. Bad things will happen then to computers that still are still using 32 bit integers to store Unix time.

So will Google Authenticator stop working in 2038? No, it should be fine. Even though iOS devices – based on 32-bit ARM chips – do just use 32 bit “long” integers, Google Authentication doesn’t rely on that. It uses NSDate to get Unix time on iOS.

Indeed, the actual standard defining the TOPT states:

The implementation of this algorithm MUST support a time value T larger than a 32-bit integer when it is beyond the year 2038.

Another wrinkle in time

Unix Time really is the number of seconds since the very beginning of 1970, but that number ignores leap seconds. Twisted clockLeap seconds are added (or subtracted) on occasion to account for the fact that the speed of the Earth’s rotation can change slightly due to earthquakes, other seismic activity, and even tidal activity (not only do I get to talk about a calendar system reaching its end and resetting, I get to talk about earthquakes and tidal waves in the same post!). A leap second was added at the end of June 2012, so noon (leap second adjusted) on July 1 was actually only 86399 seconds later (by Unix time) than June 30 instead of 86400 seconds later as you would normally get between two days.

The TOPT standard requires the use of Unix time, which is defined to ignore leap seconds. This way, everyone who follows the standard will be using the same clock and calendar. Also, keep in mind that Unix time isn’t just for Unix-based operating system like OS X, iOS, and Android. Windows has a similarly defined FILETIME, which differs in its start time and that it counts in nanoseconds instead of seconds, but it can be converted to Unix time easily enough for use in the TOPT protocol.

Time to meet MAC

Earlier, I said that the code, or one time password, is computed from the secret key and the time, but not just any old computation will do. For the system to work securely, we need the computation to meet some requirements which include:

  1. It must be easy to calculate the code from the key and the time, but it must be completely unfeasible to calculate the key from the code and the time.
  2. It must be unfeasible to predict without knowledge of the key what the code will be at some particular time even if you have observed what the code is at many other times.
  3. The calculation will always give the same result if given the same key and time (it is a function).

These look similar to some of the requirements we wanted for a good cryptographic hash function. And a cryptographic hash function will play a central role in how this is all done.

This also looks as if we are using a shared secret key to create a digital signature on the time. Digital signatures also involve hash functions. But “digital signature” isn’t really the right term here because those are based off of public/private key systems. With TOTP, we have a shared secret.

In place of a digital signature, we have a Message Authentication Code (MAC). This is not to be confused with “MAC” of “MAC address” that you see as hardware addresses for networking equipment, and certainly not to be confused with “Mac” (Apple’s family of computers) or “mac” (the mackintosh raincoat). Maybe this will help keep things clear:

A lowercase mac, for when you need wet wear
And an all-caps MAC is made by software
You’d be just as cool as the great Ry Cooder
If  you never confound these with a Mac computer

One of the ways to use a cryptographic hash to create a MAC is the HMAC. You will hear more about HMAC in the not-so-distant future.

Keeping time, time, time

One consequence of this sort of system is that it makes the computers’ knowledge of the time part of the security system. This isn’t anything new; this requirement has been part of the Kerberos system for decades. Indeed, one of my first roles in system administration was keeping clocks in sync with each other, specifically for Kerberos.

TARDIS

Unfortunately, this means that if someone can tamper with the time signals a computer receives from outside, then they can do damage to other aspects of security. We need systems to verify that the messages they get about the time are authentic, but the less-than-ideal state of secure time synchronization could be the subject for a new series of rant posts. Fortunately, I’ll spare you.

It is also not clear at this point what forms of time travel this or other security protocols can resist. I believe that there is a research paper in this question somewhere for an adventurous student and a flexible professor.

Six digits from 160 bits

Let’s now put all of these pieces together. Dropbox and Google Authenticator each have the shared secret from when you set up your two-step verification. And each know the correct time at the moment. So when each calculate the HMAC of the current time, using the shared secret as a key, they will calculate the same number. If they use SHA-1 for the hash function (as they do in the current system) the number that they calculate will 160 bits long, or roughly 48 digits. The final step is to compute a 6 digit number from that 160 bit number. But let’s save time and skip those final details.

Time for closing remarks

Dropbox’s two-step authentication is a great thing, and 1Password for iOS now works more smoothly with it. But it does the most good for people who are using weak or re-used passwords to log into Dropbox. Thankfully, 1Password users don’t really need to worry about that problem.

Alan Turing’s contribution can’t be computed

Turing BombeAlan Turing was born a hundred years ago this year and his most important paper was published seventy-six years ago (November 1936). It is close to impossible to overstate the influence that Turing has had on the modern world. It is something well worth celebrating his life throughout this centennial year. Although any celebration must be tempered by reflection on the circumstances of his death, I would very much like to tell him that “it got better.”

Alan Turing: Enigma. Book coverSince others with better knowledge of history than I are writing this year about many aspects of Turing’s life and influence, I’ll discuss something that doesn’t make the rounds often: Alan Turing and randomness. Turing knew a great deal about randomness and talked about what kinds of things can and can’t be computed. If you would like to know why true randomness isn’t “computable”, please read on. Discussion of randomness in 1Password and cryptography will be in a later article.

The Millennium of the Algorithm

I like to call the second millennium “the millennium of the algorithm”.Al-Khwarizmi An algorithm is a finite list of step-by-step instructions that, if followed, will get you a result. When we learned how to add multi-digit numbers in grade school, we learned an algorithm. The same is true for multiplication and division. These algorithms for arithmetic were developed and described by Muḥammad ibn Mūsā al-Khwārizmī in about 825CE and translated to Latin in the 12th century. It is from al-Khwārizmī’s name that we get the word “algorithm”.  We also get the word “algebra” from the title of one of his books.

In the final century of the millennium, Alan Turing found a way to treat algorithms as mathematical objects. This involved inventing a computer programming language and describing a physical machine that it would run on. The particular machine wouldn’t be very practical because Turing needed it to be the simplest thing possible that would compute, in principle, anything that a more complicated physical device could do. It would have been horrendously inefficient if actually built.

LEGO Turing Machine from ecalpemos on Vimeo

The full title of Turing’s 1936 paper is “On computable numbers, with an application to the Entscheidungsproblem“, but I will only be talking about the “On computable numbers”. Although utterly fascinating and the goal of his paper, let’s set aside the Entscheidungsproblem for another post or perhaps a few beers.

Different kinds of numbers

There are lots of numbers between 0 and 1. We call all the numbers in that range real numbers. Among the real numbers are rational numbers (numbers that are a fraction of whole numbers) like 1/3, but there are also numbers that can’t be expressed as fractions of whole numbers, like the square root of 2. This fact about the square root of two was so disturbing to the Pythagoreans view of the universe that they attempted to keep it secret. Legend has it that the person who revealed the secret got tossed overboard and drowned as punishment. Anyway, numbers that can’t be expressed as ratios of whole numbers are called irrational numbers.

It turns out that there are as many even numbers as there are whole numbers. This is because for any whole number that you care to name, I can name an even number that matches it. If you say “33”, I’ll just say “66”. This may seem strange, but if we can find a way to pair up the members of one set (in this case whole numbers) with the members of another set (in this case even numbers), we say the sets are the same size. It actually gives us a useful way to talk about infinities.

Since there are as many whole numbers as even numbers, you might reasonably think at this point that all infinities are the same. You’d be wrong, but it  certainly wouldn’t be unreasonable to have that incorrect intuition. There are, in fact, more real (irrational) numbers than there are rational numbers. The proof of this is one of the most beautiful things ever invented, but I won’t go into it.

So we’ve got a different, bigger infinity of irrational numbers then we have of rational numbers. When a set has as many elements as there are counting numbers, we call that set “countable”. It’s infinite, but we can match up elements to the counting numbers. The counting numbers are countable as are the rational numbers. The set of real numbers, however, is not countable. This means that we cannot pair up each real number with some counting number.

How irrational can we get?

There are different types of irrational numbers. Things like the square root of 2 are called algebraic numbers for reasons I won’t explain. But there are irrational numbers that go beyond, or transcend, the algebraic numbers, and these are called transcendental numbers. The most famous transcendental number is π, the ratio of the circumference of a circle to its diameter. Of course, π has been known about for a very long time, but it was only proved to be transcendental in the 19th century. The trigonometric functions like sine and cosine typically yield transcendental results.

There are algorithms to compute any algebraic numbers (things like the square root of 2) to any precision that we need. There are also algorithms to calculate the kinds of transcendental numbers that we tend to use, like π or the sine of 10.

On Computable Numbers

Imagine a hotel – let’s call in the Hilbert Hotel – that has a countably infinite number of rooms, each of which is big enough for only one guest. Suppose you have every room filled, and a countably infinite number of new guests arrive. You can still fit them all in by having each current guest move to double their current room number. If Alice is staying in room 1, she will move to room 2. Barbara, who has been in room 2, will be moving to room 4. The guest in room 33 will be moving to room 66. After this move, then all of the odd numbered rooms will be vacant, and you can then give out those rooms to your new guest.

If you have an infinite number of guests who would like to stay, and you can find a way to assign each to her own room, then you have countably infinite guests. But if there is no way to give each guest her own room, then you have an uncountable number of guests.

By carefully defining what it means to compute something, Turing found a way to give every possible algorithm a room to itself in the Hilbert’s countably infinite hotel. This means that there are “only” a countable number of algorithms. At the same time, we know that there are uncountably many real numbers. There are real numbers for which there is no algorithm to produce it. Some things are uncomputable.

Annotated Turing book cover

Plenty of irrational numbers are computable. We do have algorithms for computing the square root of 2 or the sine of 50. Turing’s result here (remember, he actually just used all of this as a building block to settle a bigger question in mathematics) tells us, among other things, that that while there are countably infinite things that we can compute, there are uncountable infinite things that we can’t compute. The overwhelming portion of numbers are things that we can’t compute.

Computing Machines

Turing was able to define the notion of “computable” by imagining the most simple device with the most simple of mechanisms that could do everything that we think of as computation. But, there is some confusion about the term “Turing Machine”. Although it can be used to refer to the imaginary physical device described in “On Computable Numbers”, it often refers to a program for that device (Turing called his programs “machines”). There is a special kind of Turing Machine (program) which can read and execute any Turing Machine. We call such programs or systems Universal (Turing) Machine.

One important fact about a Turing Machine (the imaginary device or individual programs) is that it always produced the same result with the same input. The result of each step in an algorithm depends entirely on what it has to work with and the step itself. If an algorithm has a step that adds two digits the results must always be the same given the same starting digits.
Algorithms cannot have steps in them like “flip a coin, if it comes up heads do X, otherwise do Y.” There is no coin flipper inside a Turing Machine.

Pick a number, any number

If we pick a number at random from the real numbers between 0 and 1, it will almost certainly be a non-computable number,Dice as the overwhelming majority of numbers aren’t computable. So can we pick a random number that way? Not with a Turing Machine. Each step in an algorithm should get you to a single specific result based on where you start. True randomness is not computable.

Turing knew that Turing machines could not generate true randomness, and Turing knew a great deal about randomness. His 1934 King’s College (Cambridge) Fellowship Dissertation had been on one of the most fundamental theorems in statistics. His now famous work as a code breaker at Bletchley Park during the second world war involved an innovative application of Bayes’ Rule to cryptanalysis.

Mark IWhen Turing got to play with real early computers for his own academic interests, he knew that if he wanted anything with truly random numbers, it would have to go beyond the computable. He had a hardware random number generated included in the design of the Mark I at Manchester University in 1949. A paper by Martin Campbell-Kelly describes what was almost certainly the first attempt at a hardware random number generator in an electronic computer:

At the request of Turing an instruction to generate a random number from a noise source was provided. Unfortunately, the numbers turned out to be not particularly random, and debugging was difficult because programmes were not repeatable; consequently, the instruction eventually fell into disuse.

The lesson in all of this history and theory is that randomness has been a difficult problem since the very beginnings of computing.

More randomness to come

1Password, like pretty much all cryptographic software, needs cryptographically secure random numbers to do its stuff securely. What it means for a number  to be cryptographically secure, why 1Password needs such numbers, and where it gets those from will be the subject of a future article.

Further reading

If you would like to look to the past then I very strongly recommend Andrew Hodges’ Alan Turing: the enigma as the definitive biography, and for a remarkably accessible yet complete discussion of On Computable Numbers, I enthusiastically recommend Charles Petzold’s The Annotated Turing.

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.

Flames and collisions

Having a Microsoft code signing certificate is the Holy Grail of malware writers. This has now happened.Mikko Hypponen

Unless you are a system administrator for a government institution in or around the Middle East you do not need to worry about Flame infecting your computer. Flame (also known as “Flamer” and “skywiper”) itself is not a security concern except to a very narrow, targeted group. Quite simply you don’t need to worry about being infected by Flame, and antivirus vendors who suggest otherwise may be engaging in fear mongering.

With so few people in danger of Flame, why am I writing about it? Good question. I’m writing about it because one of the methods used in Flame has the potential of undermining a crucial part of computer security. The authors of Flame have the ability to subvert the Windows Update process. Whatever Flame itself does or doesn’t do, the fact that its authors acquired the capability to distribute fake updates to Microsoft Windows is cause for serious concern.

Software updates and chains of trust

I have previously written about how an important part of computer security is ensuring that your software updates come from the right place. You don’t want someone who pretends to be AgileBits giving you malicious updates to 1Password. And you don’t want someone who pretends to be Microsoft giving you malicious Windows Updates. The methods used for digitally signing downloads and updates involves some mathematical magic and a Chain of Trust. In the summer 2011, we saw, in the example of DigiNotar, what can happen when someone finds a way to insert themselves into the chain of trust.

These two articles, “Who do you trust to tell you who to trust?” and “A peek over the Gatekeeper” explain the security infrastructure I’ll be writing about here. You will see terms like Certificate Authority or Man in the Middle attack in this post, but they are more fully explained and illustrated in those other posts.

Putting trust to the flame

Windows Update iconThe authors of Flame have acquired the ability to digitally sign their own updates to Microsoft Windows as if they were (almost) Microsoft. They have been able to create digital signatures in a way that will successfully fool the Windows Update process. Microsoft made a series of mostly innocent blunders in creating some intermediate Certification Authorities that are used by customers to creating individual licenses for a particular product. However, in combination those blunders on something that was not supposed to be part of the critical system turned out the have major consequences.

The details are subtle, and much of what we know comes from announcements by Microsoft about their recent urgent security updates. With the sketchiness of the details and the fluidity of the situation, it is safe to assume that anything I write about the mechanism used to create the bogus signatures will be out of date by the time I actually post this article. A great source for information about this is Matthew Green’s post on his Cryptographic Engineering blog. The technical details of Flame (PDF) itself are coming from research at the Budapest University of Technology and Economics.

Microsoft has issued a security update, which you get via – you guessed it – Windows Update. It is not clear (to me, at this point) whether these updates fix the long term problem or just fix the Flame-specific signatures. In a notice on June 4 they state that the June 3 update was the first of a series of actions in a phased mitigation strategy. So there will be more to come.

But the most interesting thing (to me) in their notice is

The Flame malware used a cryptographic collision attack in combination with the terminal server licensing service certificates to sign code as if it came from Microsoft. [Emphasis added]

And this gives me the opportunity to discuss an important concept in cryptography that I haven’t talked about before.

Hashes and Collisions

In the article about Gatekeeper I talked a bit about some of the mathematical magic behind digital signatures, but I left many pieces out. The digital signature of a file is not actually a signature of the file directly. For a number of technical reasons it is too unwieldily to directly construct a signature of a large chunk of data; the file itself would need to be treated is a single enormous number that is then used as an exponent of some other large number. If the file were just 10 kilobytes, its number would be on the order of 281920 (about 25,000 digits long). We deal with some really big numbers in cryptography, but we would like to just deal with numbers about the size of 2256 (around 77 digits).

To create a digital signature of a file we first need to do is reduce the file (no matter how big it is) to a number in the range we can deal with. We create a cryptographic hash (sometimes called a message digest of a file) and then digitally sign that hash. If a hash function (something that takes all the data in a file and produces a smaller number) is to be useful for digital signatures it must have a number of security properties. The security property we are interested in today is called (strong) collision resistance.

Collision resistance
It must be infeasible to find or create two distinct files that have the same hash.

Any time you have two distinct files with the same hash you have a collision. In principle collisions are inevitable because there are more possible files than there are hashes, after all, the point of the hash to turn a really big chunk of data (a file) into a smaller (though still big) number. Instead the security of hash functions relies on how difficult it is to find or create collisions.

In a recent article, I talked about another security requirement of a cryptographic hash. It must be infeasible to calculate anything about the original file from the hash. That is called pre-image resistance, but today’s topic is collision resistance.

Danger: Collision ahead!

Now let’s look at why collision resistance is important for digital signatures. Collision illustrationSuppose that Patty, one of my dogs, creates two files. One of them says, “Molly is the cleverest and prettiest dog ever, and Molly gets to rule.” The other file that Patty creates says, “Patty will get all of Molly’s dog treats.” Patty, of course, is the clever one. She is able to create these two files so that they produce the same hash. Patty has created these to files in such as way that their hashes collide. Patty asks Molly to digitally sign the “Molly rules” file, and Molly is happy to comply. Molly, using her secret key, creates a signature for the “Molly rules” file. The digital signature is actually a signature of the hash of the file, and so that signature will also work as a signature for the “Patty gets all the treats” file.

Patty will then bring me the “Patty gets all of Molly’s treats” file along with Molly’s signature. I calculate the hash of the file and verify that the hash really is signed using Molly’s secret key. Nobody but Molly knows that secret key, and so I figure that Molly must have signed that file. I give all of Molly’s treats to Patty. Molly may like to collide with Patty on walks, but this is one collision that Molly is not at all happy about.

It’s more than just dog treats that are at stake here. As I described in the Gatekeeper article, it’s not just ordinary files that can be signed (or more correctly, have their hashes signed), but certificates and Certificate Authorities are also just data that can be signed. The signature on a certificate helps our computer determine whether it can trust that certificate. If Molly controls a Certification Authority (CA) Patty can ask Molly’s CA to sign a certificate for Patty that Molly is happy to sign. But if Patty has another, trickier, certificate that produces the same hash as the one that Molly signed, Patty can simply add Molly’s signature to the bogus certificate.

The solution is to make sure that the hash function that is used for signing certificates (or files related to dog treats) is collision resistant. In particular this means that the MD5 hash algorithm should not be used. Unfortunately some of Microsoft’s Certification Authorities use the MD5 hash system. The MD5 hash system is badly broken, and it is very possible to generate collisions.

The downfall of MD5

Cryptographers don’t talk about “impossible” or “possible”; they talk about “feasible” and “infeasible”. An infeasible task usually means something like “if you used all the computing power on Earth now and for the next decades, would still have only a negligible chance of successfully completing the task.” With MD5 we’ve witnessed the progression from “secure” to “weaknesses that are infeasible to exploit” and eventually to “practical exploits” in the space of about 10 years.

MD5 (Message Digest 5) was shown in 1995 to have theoretical weaknesses. From there the history is remarkably interesting (if you are into that sort of thing). There was one group of people who were saying “don’t use MD5 any new software or systems; use SHA1 instead.” There was another group saying that the weaknesses in MD5 don’t pose an actual threat to how it is actually used. By 2005 it became absolutely clear that the weaknesses in MD5 had been expanded and could be leveraged into real attacks, and in 2008 there was a spectacular demonstration to create a rogue Certification Authority. An important side note is that while the advice to use SHA1 instead of MD5 was very good advice in 1995; today that advice is to use SHA2 instead of SHA1.

As we all watched MD5 go from secure to completely broken with respect to collision resistance in the space of ten years, we also saw that its use continued. I think that many of us failed to understand just how easily collisions could be exploited. It was tough to steer a course between people panicking on one side who were saying that anything involving MD5 was tainted and those on the other side who always seemed to think, “sure MD5 has its weaknesses, but those weaknesses don’t affect my application.”

Microsoft using MD5 in 2009

People continued to use MD5 for a number of purposes that they didn’t see as critical. The intermediate certification authority that Microsoft set up for signing Terminal Services licenses was, presumably, thought to be not critical enough to worry about. The worst (they thought) that could happen is that customers could create a few extra licenses for themselves if they went through the effort to create collisions. So as even as late as 2009 Microsoft created CAs that used MD5 as its hashing algorithm. They turned out to be wrong about “the worst that could happen”. Other blunders allowed a weak CA created in 2007 to sign certificates for other CAs.

Using the same trick that Patty pulled on Molly, an attacker could get a signature for an acceptable CA to work on a malicious one. The malicious one could then be used to sign false updates to Windows. Thus, the attacker would have the ability to sign things that would look like legitimate updates to Windows.

Microsoft has recently (June 6) provided more details, which confirm that what I’ve described above did play a role in the creation of the signatures for the bogus updates.

Lessons

Follow early warnings

When we, the technology community, were advised in 1995 to stop relying on MD5 we should have been quicker to make the transition to SHA-1, even though at the time it wasn’t clear how those weaknesses could be exploited. Likewise, we should follow the same warnings about SHA-1 today. We shouldn’t panic every time a theoretical weakness is found, but we should remember that these can often be leveraged in ways we can’t predict.

Hash algorithms are hard. MD5, as you’ve seen deteriorated rapidly. SHA-1 has been shown to be less than ideal (not yet exploitable in practice), and even its replacement, SHA-2 isn’t all we would hope it to be. Cryptographers and the NIST are working on finding a system to become SHA3. If you have a high tolerance for geeks singing out of key, you may wish to sing along to the SHA-3 song.
The refrain is

SHA-2 will soon retire
Because NIST is learning and SHA-1 is burning
SHA-2 will soon retire
No we didn’t light it but tried to fight it.

The trust infrastructure is fragile

There are a large number of Root Certification Authorities and an even larger number of intermediate CAs. As we’ve seen here, the chain of trust can be compromised through some poorly designed CAs. As we saw last summer, in the case of DigiNotar, a Root CA can have their computer systems compromised allowing an attacker to gain accesses to the secret key needed to sign certificates. A third possibility is that the operators of CA may simply go rogue.

Charles Dudley once noted that “everybody complains about the weather, but nobody does anything about it.” The same can be said about the trust infrastructure that so much of our security relies on. Fortunately there are a few talented people who are working on serious proposals that, while they won’t completely fix the system, will mitigate some of the problems. I won’t review them here.

Are governments friends or foes of computer security?

Flame is almost certainly the creation of a “Western intelligence agency”. A few weeks ago, I would have guessed that it was an Israeli creation, but recent news about the creation of Stuxnet leads me to suspect that Flame, like Stuxnet, was primarily created by the United States. Parts of the US government have done and continue to do a great deal of important work in promoting good security. But we now have an example where the government has undermined a crucial part of computer security.

So far the victims of state-sponsored attacks on the certificate trust infrastructure have been in Iran. Last summer the government of Iran used certificates from a compromised Root Certification Authority, DigiNotar, to interest “secure” connections between individuals in Iran and Gmail. Now it looks like like the US (or possibly Israeli) government has been using poorly constructed Microsoft Intermediate CAs to target specific entities in Iran.

The good news, I suppose, is that these governments still had to exploit vulnerabilities instead of, say, compelling Microsoft to sign bogus updates. Of course, we cannot rule out that government agencies asked Microsoft to include those vulnerabilities. I suspect that Microsoft’s errors were innocent because they are the kinds of errors that people and organizations do make, but I can’t entirely rule out the more paranoid interpretation.

Security has a lot of moving parts

Each of the mistakes that Microsoft made were probably harmless on their own. No doubt they were made by different people who weren’t aware of the decisions that others had made. In combination, the mistakes add up to several ways of generating “good” signatures for bad Microsoft Updates, something with potentially catastrophic consequences.

A few closing remarks

Truth and speculation

I have speculated about how Microsoft made the errors that they did, and I have speculated about what the creators of Flame have done with that. What we do know is the bogus certificates for signing Windows Updates were created, and we know what Microsoft has said about it. We know that CAs using MD5 in their digital signatures are vulnerable in the way discussed, and we know that that the bogus certificates were signed by those weak CAs.

As it turns out, some of my initial speculation has been confirmed since I first drafted this. Microsoft has published an outstanding and detailed report of their analysis.

We also have a rapidly changing situation. It shouldn’t be too surprising if much of what I say about the specifics of the case today is out of date by tomorrow. Still, it gave me the chance to talk about hash functions and attacks based on collisions, along with the problems of using MD5 for digital signatures. Furthermore, Patty and Molly are always seeking attention, so they appreciate that I’ve mentioned them here.

Continuing the discussion

If you would like to comment or continue this discussion, please do so in the Flames and Collisions forum topic I’ve created for the purpose.

Updates

This article was out of date before it was finished, and I expected that there would be more news to come. And so to avoid a continues series of updates, I will be adding updates to the forum thread set up for the purpose.

However, the news that came out right after this article was posted is so jaw dropping that I will repeat it here.

The cryptanalytic technique used to create the MD5 collision is new. It isn’t radically different than previous known techniques, but this is using a technique that would have taken a great deal of expertise to develop.

People have always speculated about how far ahead in cryptanalysis agencies like the NSA or GCHQ are compared to what is known by the academic community. The assumption is that the gap has been narrowing over the decades as there is more open work in cryptography done outside of intelligence agencies. We don’t often get data to help pin anything down with our speculation, but this definitely is interesting.

The Ars Technica article linked to above has a terrific diagram outlining the nature of the general technique used to create MD5 collisions.

 

A salt-free diet is bad for your security

I am not giving anyone health advice. Instead, I’m going to use the example of the recent LinkedIn breach to talk about hashes and salt. Not the food, but the cryptology. Before you dive into this article, you should certainly review the practical advice that Kelly has posted first. Also Kelly’s article has more information about the specific incident.

I’m writing for people who saw security people talking about “salt” and want to know more.
You may have seen things like this, that appeared in an article at The Verge.

It’s worth noting that the passwords are stored as unsalted SHA-1 hashes. SHA-1 is a secure algorithm, but is not foolproof. LinkedIn could have made the passwords more secure by ‘salting’ the hashes.

If you would like to know what that means, read on.

What we know

We know that a data set of about 6 million password hashes has been released. We also know that this does include LinkedIn passwords (more on how we know that later). The data made public does not include the usernames (email addresses), but it is almost certain that the people who got this data from LinkedIn have that. By the end of this article, you will understand why people who broke in would release only the hashes.

Hashing passwords

Websites and most login systems hash passwords so that they only have to store the hash and not the password itself. I have been writing about the importance of hash functions for a forthcoming article, but here I will try to keep things simple. A hash function such as SHA-1 converts a password like Password123 to “b2e98ad6f6eb8508dd6a14cfa704bad7f05f6fb1″. A good hash function will make it unfeasible to calculate what the password was if you only know the hash, but the hash function has to make easy to go from the password to the hash.

A hash function always produces the same hash from the same input. It will always convert “Password1″ to that same thing. If both Alice and Bob use Password123, their passwords will be hashed to the same thing.

Let’s put rainbows on the table

Even if Bob and Alice use the same password (and so have the same hash of their passwords) they don’t have to worry about each other. Who they need to worry about is Charlie the Cracker. Charlie may have spent months running software that picks passwords and generates the hashes of those passwords. He will store those millions of passwords and their hashes in a database called a “Rainbow Table.”

A small portion of Charlie’s table may look like this

Password SHA-1 Hash
123456 7c4a8d09ca3762af61e59520943dc26494f8941b
abc123 6367c48dd193d56ea7b0baad25b19455e529f5ee
Password123 b2e98ad6f6eb8508dd6a14cfa704bad7f05f6fb1

(Rainbow tables are structured to allow for more efficient storing and lookup for large databases. They don’t actually look anything like my example.)

When the hashed passwords for millions of accounts are leaked, Charlie can simply look up the hashes from the site and see which ones match what he has in his tables. This way he can instantly discover the passwords for any hash that is in his database.

Of course, if you have been using 1Password’s Strong Password Generator to create your passwords for each site, then it is very unlikely that the hash of your password would be in Charlie’s table. But we know that not everyone does that.

Charlie also has a lot of friends (well, maybe not a lot, but he does have some) who have built up their own tables using different ways of generating passwords. This is why Charlie, who has both the usernames and the hashed passwords, may wish to just circulate the hashes. He is asking his friends to help lookup some of these hashes in their own tables.

I also promised to tell you how we know that the leaked hashes are indeed of LinkedIn passwords. If someone has a strong unique password for their LinkedIn account it is very unlikely that it was ever used elsewhere. So if the hash for that strong and unique password turns up on the leaked list, we can know it is from LinkedIn. This is presumably what Robert Graham did when determined that this is the LinkedIn list.

Salting the hash

More than 30 years ago, people realized the problem of pre-computed lookup tables, and so they developed a solution. The solution was to add some salt to password.

Here is how salting can work. Before the system creates a hash of the password it adds some random stuff (called “salt”) to the beginning of password. Let’s say it adds four characters. So when Alice uses the Password123 the system might add “MqZz” as the salt to the beginning to make the password MqZzPassword123. We then calculate the hash of that more unique password. When storing the hash, we also use store the salt with it. The salt is not secret, it just has to be random. Using this method, the salted hash that would be stored for Alice’s password would be “MqZz1b504173d594fd43c0b2e70022886501f30aee16″.

Bob’s password will get a different random salt, say “fgNZ”, which will make the salted hash of his password “fgNZ2ec6fa506fa9048d231b765559e2f3c79bdee5a1″. This is completely different than Alice’s, and – more importantly – it is completely different from anything Charlie has in his rainbow tables. Charlie can’t just build a table with passwords like Password123, instead he would have to build a table that contained Password123 prefixed by all of the two million possible salts we get using a four character salt.

Beyond salt

Salting is an old technology, yet a surprising number of web services don’t seem to be using it. This is probably because many of the tool kits for building websites didn’t include salting by default. The situation should improve as newer toolkits encourage more secure design, and also as these issues make the news.

But just as we are getting people up to speed with a 30 year old technology, salting may no longer be enough. And mere salting certainly isn’t good for the passwords that require the most security. To defend against determined and resourceful password crackers you should use both strong passwords and a password based key derivation function like
PBKDF2, which 1Password does use when encryption your Master Password.

Cipher of Advanced Encryption Substitution And Rotation

In the rapidly changing world of eternal mathematical truths, we need to innovativize for the sustanation of our competitive advantage. So instead of serving our customer base with the same old encryption algorithms that are used by governments, military, and most of the Internet, we want to provide the world with new, proprietary systems that should clearly set us apart in the marketplace and among the expert community.

With great pleasure, I’d like to introduce our forthcoming encryption system: Cipher of Advanced Encryption Substitution And Rotation (CAESAR).

Rationale for CAESAR

No salt but the finest

Himalayan Rock SaltUsing block equality (described below) largely obviates the problem of obtaining a good salt or nonce in our cryptography. But because we will be transitioning to our new system, there are cases where we still need to find a good salt. Most cryptographic implementations have been written in the C programming language, and so for past decades the fashion as been for C-salt. C-salt, of course, was an improvement on table salt, which entirely failed to discourage the use of tables in cracking passwords.

Times have changed, and C-salt is now passé. Instead people have been discovering the virtues of Himalayan salt. Thus we sent off an expedition to Pakistan, Afghanistan, Nepal, India, and Bhutan to find and bring back the finest and rarest of salts for our encryption recipes. To protect our interests, this salt and its origins must remain secret.

Rotation, modularity, and alphabets

Pretty much all computer ciphers are based on the theory of finite groups. CAESAR is no different. Indeed, despite the fact that we just came up with the system recently, the use of groups and rotation in CAESAR may fairly be said to be precedent setting. Yeah, history can be weird that way.

We are faced with one difficulty in our approach. Our expedition to far off lands described above discovered something that completely shocked us in addition returning with a source of salt. They discovered that not everyone speaks English. Not only did this astonishing discovery lead to our researchers submitting a number of papers to various academic journals (oddly, we have not heard back from them), and caused considerable delays and expense for the expedition itself; it also means that our original rotation would not work as effectively in alphabets that use more than the English letters A through Z.

After careful consideration of this issue, we realized that requiring such people to use English would actually increase their security. They would be using a language that those around them may not be able to read, thus giving them a second layer of encryption. This showed how forward thinking our design was. It automatically provided higher security in some unanticipated cases.

All blocks are equal!

Blockrights designOne of the problem with the kinds of block ciphers is their lack of equality when used in CBC or CTR modes. We, however, want to return the spirit of ECB mode in which all blocks are equal (Credit for this particular insight goes to the people at 0-Day Clothing).

In addition to the fairness issues in support of the notion that all blocks should be treated equally, it must be noted that mathematics is built on the notion of a mathematical function. Ensuring that a given input produces a unique value, turning to something like ECB mode helps restore us to mathematical purity.

Where to from here?

I have provided only a few of the highlights of CAESAR and our new thinking in cryptography. This custom made, bleeding-edge scheme will doubtless place us in a unique position in the security community. Look for more new projects in the future, possibly a year from the date of this article’s publication, April 1. One we are looking at is System of Natural Additive Key Encryption—Overloaded In Layers.