One of the key elements in securing or data and our identities is the use of strong passwords. Using passwords that can’t be guessed—unlike the perennial favorites 123456 or password—helps ensure that hackers and cybercriminals can’t access your computer, mobile device, or websites where you’ve created accounts, and can’t steal your identity to pretend to be you, or empty your bank account.
Simple passwords can be cracked using brute force; this is where an attacker uses tools that try every possible password until the correct one is found. This generally done using a dictionary attack, where an attacker will try known passwords and words until they find the one that unlocks an account. There are databases available on the internet that contain personal names as well as dictionary and slang words, in scores of languages, along with passwords found in data breaches, and more. One such database that I found through a simple web search contains 1.4 billion entries.
But many people use unique, random passwords, such as m3*9V-jh&3W (which I just generated with my password manager), and these passwords are generally not found in databases—unless you use them for multiple websites, and one of those sites has been breached. (This is why you should never reuse the same password for more than one account.) Cracking this sort of password requires much more computing power. Estimates vary, but, as an example, cracking the password above would take a couple hundred thousand years using a standard computer, or a few years using a supercomputer or botnet.
But what will happen when quantum computers become more common? These passwords could be cracked in minutes, or even seconds.
The evolution of computing speed
As computers get faster, tasks of this sort will be easier. It’s hard to compare the speeds of computers over time. My first Mac, a PowerBook 100, had a 16 MHz processor; my current iMac has a 3.6 GHz processor, and that theoretically makes it about 225 times as fast.
In reality, though, raw speed isn’t everything; you need to factor in the increased efficiency of the CPU itself, as well as all the other elements that make computing fast: the disk or SSD, the amount and speed of RAM, and the input/output (I/O) bus that gets data to and from the processors. And with advanced GPUs (graphics processing units) and coprocessors like Apple’s T2 chip, the amount of computing time can be further reduced for certain tasks.
There’s no easy way to reliably measure the difference, but my current iMac is roughly thousands of times as fast as that PowerBook, a huge increase over thirty years.
While this has been an exponential increase in raw speed, all this will change with quantum computing. The speed difference between today’s fastest computers and a future quantum computer is several orders of magnitude. Google’s current quantum computer is 100 million times as fast as any standard computer, and Google claims that its computer achieved “quantum supremacy,” that it took only 200 seconds to perform a task that would require the world’s fastest supercomputer 10,000 years to calculate. (There’s a lot of disagreement in the quantum computing world; IBM claims that this task would only take 2.5 days for a classical computer.)
This is leading to a race to determine whether passwords and encryption can keep up with these new tools. “Quantum computers are believed to be able to solve certain computational problems, such as integer factorization (which underlies RSA encryption), substantially faster than classical computers,” says the Wikipedia article on quantum computing. The field of quantum cryptography is progressing with the goal of using quantum computing to encrypt data, and post-quantum cryptography is examining ways to ensure encryption that can resist the brute-force strength of quantum computers.
The length of passwords is a key element in their security, as is the number of characters available to use for the password. A four-digit PIN, for example, is relatively trivial to crack; there are only 10,000 possibilities (0000 through 9999). Even with a six-digit passcode, there are only 1 million possibilities (000000 through 999999). In both cases, most people tend to use predictable patterns such as dates (birthdates, anniversaries, etc.).
If you add letters onto that six-character password, however, then it becomes much harder to crack. Add symbols and other special characters, and it gets more difficult by several orders of magnitude. Every increase in length exponentially raises the amount of time needed to crack a password.
I’m not very good at math, but this Scientific American article gives some examples. A six-character password using only lowercase letters could take a fraction of a second, but a 12-letter password could take more than 26,000 computing hours. Increase the number of possible characters (by adding uppercase letters, digits, special characters, etc.) to 100, and this could take 27 million computing hours.
Of course, using quantum computing to crack passwords would massively reduce all those lengths of time. Passwords that might be nontrivial to break today could become trivial to break as soon as quantum computers are designed to tackle that specific task.
Key length also matters
While a quantum computer may be able to crack today’s encryption (which often uses a 128- or 256-bit key length), even using a much longer key—which, as with passwords, increases the difficulty exponentially—could still potentially be crackable. One study suggests that encryption using a 2048-bit key could be cracked in 8 hours using a quantum computer.
While 128- and 256-bit encryption keys may be sufficient for now, the reason we don’t often use longer keys is the amount of processing required on the devices doing the encryption and decryption. But as the processing power of standard devices increases, we may eventually see encryption key lengths increase, to try to keep up with the power of potential attackers.
Considering that 128-bit keys were commonly considered “military grade” by the U.S. government way back in the 1990s, and processing technology has come a long way since then, it’s reasonable to assume that most devices nowadays should be able to handle much longer keys and more robust encryption algorithms.
Moore’s law vs. Neven’s law
Moore’s law has long said that computing power doubled every two years, and since it was posited, it has been more or less true. But now Neven’s law suggests that computing power will start growing at a doubly exponential rate. Under Moore’s law, computing power over ten two-year periods would increase from 1 to 1024 (2, 4, 8, 16, 32, etc.); Neven’s law is doubly exponential (2, 4, 16, 256, 65,536, etc.), and it says that increase over ten years would be 1.797693134862315907729305190789e+308, or 2 to the 1024th power, a number so large that it’s hard to comprehend.
Don’t worry about this happening any time soon. Sure, quantum computers are working in labs and research centers, but we’re probably a long way from them becoming common. The real worry is for national security, since nation states may have these computers and use them to try to crack encryption of other countries, or of dissidents. But they may want to use them on their citizens, so using the strongest possible password is still the best approach users can take for now.
As for the future of passwords, new techniques will have to be developed, extending the use of multifactor authentication, using more advanced biometrics (such as Touch ID and Face ID), and other techniques. Perhaps quantum computing will lead to the demise of the password altogether.
How can I learn more?
We discussed quantum computing on episode 159 of the Intego Mac Podcast. Be sure to subscribe to make sure you don’t miss any episodes. You’ll also want to subscribe to our e-mail newsletter and keep an eye here on The Mac Security Blog for the latest Apple security and privacy news.
Image credits (via Google AI Blog): Artist’s rendition of the Sycamore processor mounted in the cryostat (Full Res Version; Forest Stearns, Google AI Quantum Artist in Residence); Photograph of Google’s Sycamore processor (Full Res Version; Erik Lucero, Research Scientist and Lead Production Quantum Hardware).