Maksim Kabakou - Fotolia
How NIST is preparing to defend against quantum attacks
The NSA has begun the transition from ECC to new algorithms to resist quantum attacks. Learn about the threat posed by quantum computing from expert Michael Cobb.
A simplified interpretation of Moore's Law is that the overall processing power of computers will double every two years -- and will lead to quantum computing.
Although many experts believe physical and economic limitations are finally beginning to slow down this rate of progression, the incredible increase in computing power over the last 50 years has meant that cryptographic algorithms once considered secure have had to be retired and replaced. As this continues to happen and quantum computers gain more of a foothold, it will open up systems to quantum attacks.
The data encryption standard, MD5 and SHA-1 were all popular hash algorithms but are all now considered weak, and the successor to SHA-2, SHA-3, has already been published. Two cryptographic algorithms that have been in use for several years and that are still considered secure are Rivest-Shamir-Adleman (RSA) and elliptic-curve cryptography (ECC). They are both asymmetric -- public key -- cryptosystems that are used extensively in the protocols that enable secure communication over the internet and other networks.
The effectiveness of public key cryptosystems depends on a kind of trapdoor mathematical problem. RSA uses integer factorization. It's easy to pick two large prime numbers, multiply them and know what the product is, but there's no easy way to figure out which two prime numbers were multiplied in order to produce a product. These types of problems are time-consuming to solve, but they are usually faster than trying all the possible keys by brute force.
The overall strength of an encryption algorithm is measured in terms of breakability -- meaning how difficult it would be for an attacker to break it. The approved security strengths for federal applications are 112, 128, 192 and 256 bits. Previously, 80 bits was allowed, but this has since been found to be insecure.
According to cryptographer Burt Kaliski of RSA Laboratories, a 112-bit key search today on a $10 million machine would take about 30 billion years, and even in 2030 -- 18 generations of improvement from now -- it would still take over 100,000 years.
Key length is also an important factor in determining encryption strength. For example, RSA claims that 2048-bit keys are sufficient until 2030, but an RSA key length of 3072 bits should be used if security is required beyond then.
What quantum computing means for cryptography
The imminent arrival of high-speed parallel computers based on quantum mechanics has many security experts concerned that these algorithms will need to be retired earlier than Moore's Law would have predicted in order to avoid quantum attacks. According to the NSA, "A sufficiently large quantum computer, if built, would be capable of undermining all widely-deployed public key algorithms used for key establishment and digital signatures."
The reason for this is that quantum computers are extremely good at solving mathematical problems like integer factorization and the algebraic structure of elliptic curves over finite fields used in ECC. They can process information in parallel as opposed to sequentially, and multiple possible answers can be considered in any given computation. Interestingly, quantum computing techniques are thought to be much less effective against symmetric algorithms than current public key algorithms provided a sufficiently large key size is used.
RSA and ECC have served us well, but NIST has decided the time has come to begin preparing critical IT systems so that they can resist quantum attacks. It has initiated a process to solicit, evaluate and standardize one or more quantum-resistant public key cryptographic algorithms.
One current option is lattice-based cryptography. Lattice-based primitives have already been successfully plugged into the Transport Layer Security and Internet Key Exchange protocols. This means that all the important security protocols can be made safe from quantum attacks by substituting vulnerable problems with problems that are hard for quantum computers to solve, using just a couple of extra kilobytes of data per communication session.
Quantum computing is going to have a profound effect on today's security infrastructure, as it requires changes in the fundamental design of today's public key cryptography. Enterprises need to consider how they will tackle the security implications sooner rather than later, particularly when it comes to data that needs to be stored for long periods of time.
The NSA has begun the process of transitioning from ECC to new algorithms that are resistant to attacks by quantum computers and recommends that anyone using ECC move to the larger 384-bit curve for all classified information until there is an accepted, standardized suite of commercial public key algorithms that are not vulnerable to quantum attacks.
