Apocalypse

 Read the attached Quantum Crypto file.  What risks does this scenario pose?  How would you address this risk?  What areas of an organization and potentially affected by a cryptographic apocalypse? What about technical concerns and so on? 

The

Quantum Break

is Coming
Will You Be Ready?

• Date of Presentaion

• Presenter’s Name

• Presenter’s Title

• Presenter’s Email Address

1

Slide Information Based on:

•

What is Quantum Computing?

• How Long Till Quantum Computing Breaks Public Key

Crypto?

• How to

Prepare

Today’s Presentation

❖ A single particle can be two different things in two different places at

the same time

❖ In a series of ordered actions, a single event can be both “first” or “last”

❖ Fuzzy entanglement

• Two distant objects can be tied to each other so that when one

moves it instantly changes the other, and we don’t know why

• Viewing or measuring something now can change what it did in the

past

• Teleportation is absolutely possible

❖ Answers may be in another universe

Quick Strange Quantum Facts

“Those who are not shocked when they first come across

quantum theory cannot possibly have understood it.”

Niels Bohr, Quantum Physicist and 1922 Nobel Prize Winner

“Any sufficiently advanced technology is indistinguishable

from magic.”

Arthur C. Clarke, sci-fi author

Summary

❖ Soon quantum computers are likely to break most traditional public key

crypto and every secret it protects

• Ex: RSA, DH, ECC, ElGamal, PKI, digital certificates, digital

signatures, TLS, HTTPS, VPNs, WiFi protection, smartcards, HSMs,

crypto-currencies, two-factor authentication which relies on digital

certificates (e.g. FIDO keys, Google security keys, etc.), etc.

Quantum Break

What Is Quantum Computing?

Traditional

Computers

• Traditional computers are binary

• Each bit can be 1 or 0, negative or positive charge, on or off

• Each bit can only be one thing at one time

What is Quantum Computing?

Quantum
Computers

❖ First theorized in 1959 by Richard Feynman

❖ A quantum bit (qubit or qbit or qb) – a qubit can be read as two states (0

and 1) AT THE SAME TIME

• 1qb=2bits, 2qb=4bits, 3qb=8bits…

What is Quantum Computing?

Quantum
Computers

❖ If we were calculating all the possible combinations on a chessboard

❖ 2^64

❖ and each option was represented by a grain of rice

❖ Then the number of grains of rice would be as high as Mount Everest

What is Quantum Computing?

X =

Quantum
Computers

❖ To bruteforce factor a 4096-bit prime number equation would take more

than the known atoms in the universe

❖ There are more than 125 million atoms in the period at the end of this

sentence.

❖ Suppose you had a million pennies for every star in the universe, and there

are 100 billion stars in each of the 10 trillion galaxies of our universe, you

still would have only enough pennies to represent 1 percent of the possible

numbers a 4096-bit number could be, much less figure out the two larger

prime numbers that were used to create it.

❖ Conventional computers cannot do it

❖ Quantum computers can likely do it in minutes

What is Quantum Computing?

Quantum
Computers

• 1998 – First working quantum computer, 2-qubits

• 2000 – 5- and 7-qubit computers

• 2005 – 8-qubit computer

• 2006 – 12-qubit computer

• 2007 – 28-qubit computer

• 2012 – 84-qubit computer

• 2015 – 1000-qubit computer

• 2016 – Google develops quantum computer

• 2017 – 2048-qubit computer

• 2017 – IBM, Microsoft, announces quantum computers

• 2018 – Several quantum microprocessors available

• 2019 – Likely over 100 quantum computers available

What is Quantum Computing?

Real
Quantum
Computers

What is Quantum Computing?

Types of
Quantum

Computers

Not All Qubits Are Alike

❖ Many different methods: superconducting (-460F temps), trapped ion,

Majorana fermion, etc.

• Each method has advantages and disadvantages

❖ Right now, the quantum computers with the highest number of qubits, like

1000+, are called annealing, which aren’t great at breaking crypto

❖ Over 100 separate teams working on their own quantum computers

❖ Universal gate quantum is better at breaking crypto, but so far have a

smaller number of stable qubits

• 72 qubits as of Sept. 2018

What is Quantum Computing?

Quantum
Computers

We Need More Stable Qubits

❖ Stable qubits are very hard to make (right now)

• Without the right conditions, they lose their needed quantum properties

very quickly (decoherence)

• Merely “observing” qubits makes them change

❖ Need them stable long enough to complete a task and be able to observe

outcome

❖ Most of today’s qubits need “error correcting” or “stabilization” or be

“controllable” to work, which requires many more qubits than just the ones

doing the work

❖ The number of stable, controllable qubits is increasing over time

• But right now even those make a mistake once every 200 actions

• May need 1000 or a 1,000,000 error correcting qubits for every 1 stable qubit

What is Quantum Computing?

Quantum
Computers

Today we have:

The richest nations, dozens of companies, spending tens of billions of dollars

on quantum computing:

• Quantum microprocessors

• Cloud-connected quantum computers you can play with

• Quantum key distribution

• Quantum random number generators

• Quantum programming languages, development kits, compilers

• Quantum networking

• Quantum cryptography

What is Quantum Computing?

Quantum
Computers

Quantum Supremacy

Point in time when quantum computers can solve problems that traditional

binary computers cannot

Means:

• Faster at some types of problems

and/or

• More capable at some types of problems

• Need at least 49 “perfect” qubits, and probably a lot more

• We are either there already, or very near

• IBM, Google, and China says we are less than 1 year away

What is Quantum Computing?

Quantum
Computers

What Will Quantum Computers Give Us?

• New understanding of physics and our universe

• Solve complicated math quickly

• Give us incredible precision (military, weather, traffic mgmt.)

• New medicines, better solar cells, new chemicals

• True artificial intelligence

• Things we cannot imagine right now

What is Quantum Computing?

Quantum
Computers
What Will Quantum Computers Give Us?

❖ Break most traditional public key crypto and every secret it protects

• Any algorithm who’s security relies on one of three hard mathematical

problems: the integer factorization problem, the discrete logarithm

problem or the elliptic-curve discrete logarithm problem

• Ex: RSA, DH, ECC, ElGamal, PKI, digital certificates, digital

signatures, TLS, HTTPS, VPNs, HSMs, smartcards, WiFi protection,

crypto-currencies, two-factor authentication which relies on digital
certificates (e.g. FIDO keys, Google security keys, etc.), etc.

❖ New “unbreakable” encryption

What is Quantum Computing?

Quantum
Break

❖ A prime number is any whole number after 1 that can only be divided by

itself or one and get a whole number

• 2,3,5,7,11,13,17,23,29,31, and so on

❖ Most traditional public key crypto (e.g. RSA, Diffie-Hellman, etc.) is based on

the work effort needed to factor large prime number equations

• p * q = n

• p and q are prime numbers, n is a public key, can be very hard to

figure out p and q

• Simple Ex: What two prime numbers when multiplied together equal 15?

• Answer: 3 x 5 = 15

When Will Quantum Break Public Key Crypto?

Quantum
Break

Another Simple Example

• p*q=187, what’s p and q?

• Answer: p and q = 17 and 11

• p*q= 84773093, what’s p and q?

• Answer: p and q = 9539 and 8887

When Will Quantum Break Public Key Crypto?

Quantum
Break
Another Simple Example

• Now assume N is a prime number 2048-bits long

• Traditional computers are not good at figuring out N

• Takes more guesses than all atoms in the known universe

When Will Quantum Break Public Key Crypto?

How Long Till Quantum Computing
Breaks Public Key Cryptography?

Quantum
Break

Prime Factoring Speed

❖ As of Sept. 2018, the largest known successful factored primes is RSA-768

(by traditional computers)

• Took 4 years and the equivalent of almost 2000 years of computing on a

single core 2.2 GHz AMD Opteron

• RSA-2048 would take billions of years using every traditional computer

and resource in existence

❖ Quantum computers can break encryption algorithms that rely upon the work

effort needed to factor equations involving large prime numbers

❖ Quantum computers with 4099 stable qubits, can crack a 2048-bit key in 100

seconds

• We have 72-stable or more qubits today

When Will Quantum Break Public Key Crypto?

Quantum
Break

How Quantum Computers Do It

Shor’s Algorithm (1994)

❖ Start by creating all the possible answers for N=p*q all at once

(superposition of states)

• Quantum Quick:

Classical speed- 2^2048 calculations, one at time per CPU

Quantum – 2^2048 calculations done all at once

❖ Transform answers so that most likely correct answers (p & q) easy to

see above all others

When Will Quantum Break Public Key Crypto?

Quantum
Break

Bottom Line

❖ Many quantum physicists think we’ll have enough stable qubits within

5 years (if it’s not already done) to break public crypto which uses the

large prime factoring work effort for protection

• Dr. Mark Jackson of Cambridge Quantum Computing thinks 5

years or less, maybe 2-3 years

❖ But who really knows??

When Will Quantum Break Public Key Crypto?

Quantum
Break
Bottom Line

In 2016, NIST/NSA, “NOW” is the time to prepare

https://cryptome.org/2016/01/CNSA-Suite-and-Quantum-Computing-FAQ

When Will Quantum Break Public Key Crypto?

How You Can Prepare for the
Quantum Break

Scenarios

What do the different possible break

scenarios look like?

Preparing for Quantum Break

Timing

Break Scenarios

• It’s already happened but we don’t know about

• It’s going to happen in the next few years

• It’s going to happen after the next few years

• It’s never going to happen

I would not put my money on the last one.

Preparing for Quantum Break

Who?
Cost?

Break Scenarios

• Stays in the realm of nation-states for a long-time

• Gets picked up by monied groups and competitors

• Available in cloud form for cheap

• Past crypto breaks went from the realm of millions of dollars to accomplish

to tens of thousands of dollars in just a few years

• Interested parties are likely storing encrypted communications for future

breaks already

Preparing for Quantum Break

Will We Be
Prepared?

Break Scenarios

❖ If we are lucky, the quantum break prep proceeds like the global SHA1 to

SHA2 migration (slower than we liked, but orderly, and ahead of the worst

problems)

❖ Might happen faster than companies and vendors are prepared

• NSA said to move to post-quantum in Jan. 2016, what have you or any

of your vendors or partners done?

❖ Likely to be a mix of prepared and not prepared when time comes

Preparing for Quantum Break

Prepare

Preparing

❖ Education (this slide deck and keeping up on advances)

• Your company, your vendors, your third parties

❖ Take a data protection inventory – what secrets really need to be protected,

and for how long? Which are at risk from quantum break?

❖ Use/Be moving toward quantum-resistant crypto, where and when possible

❖ Pressure your vendors over quantum break preparation

❖ At least demand crypto-agility

❖ Prevent eavesdropping on very high-value data

Preparing for Quantum Break

Prepare

Post-Quantum Progression

Preparing for Quantum Break

Prepare

Post-Quantum Protections

Symmetric encryption is not as vulnerable

❖ AES is still good

• Double your key size and you should be fine

• 128-bit is bare minimum (weakly quantum-resistant)

• 192-bit is better, 256-bit even better, 512-bit very resistant

❖ SNOW 3G

• Word-based synchronous stream cipher

Unfortunately, traditional public key crypto is used to protect the transmission of

plaintext symmetric keys most of the time

Preparing for Quantum Break

Prepare
Post-Quantum Protections

Quantum-Resistant Hashes

❖ SHA2/SHA3

❖ 256-bit and larger hash sizes

❖ Lamport signatures

❖ Merkle Signature Scheme

• Merkle trees

• XMSS (Extended Merkle Signature Scheme)

❖ SPHINCS+

• Used with SHAKE256, SHA-256, and Haraka

❖ Picnic Signature Algorithm

• Demonstrated by Microsoft in PKI to protect HSMs

Preparing for Quantum Break

Prepare

Quantum-Resistant Cipher Types

• Lattice-based

• Multivariate-based

• Code-based

• Hash-based

• Zero Knowledge Proof

• Isogeny-based

• See https://en.wikipedia.org/wiki/Post-quantum_cryptography

Unfortunately, almost none are generally available

Preparing for Quantum Break

Prepare

Post-Quantum Crypto – NIST 2nd Round PQC Selections

Preparing for Quantum Break

Prepare
Post-Quantum Protections

Use quantum-based ciphers and components, including

❖ Quantum Random Number Generator

• Verifiably and guaranteed random

• Many existing ones

• Online one at https://qrng.anu.edu.au/

❖ Quantum Key Distribution (QKD)

❖ Quantum Encryption

• Perfectly secure in theory

• If anyone observes the data, you’ll know

Preparing for Quantum Break

Prepare

Post-Quantum Protections – Possible Performance Issues

Some quantum-resistant asymmetric ciphers require larger key sizes, but all

take longer in operations

Preparing for Quantum Break

*All figures in bytes unless stated as b=bits or K=kilobits

Comparison: RSA 2048-bit has 256-byte public key and signatures

Prepare
Post-Quantum Protections

Open Quantum Safe Project (https://openquantumsafe.org/)

• Group dedicated to helping to implement post-quantum crypto

• Open source C-library (liboqs) to implement some post-quantum ciphers

• API

• Testing and benchmarking

• Forked quantum-resistant versions of OpenSSL and OpenSSH

Preparing for Quantum Break

Prepare
Post-Quantum Protections

Enable Perfect Forward Secrecy Where Possible

• Generates random (public) encryption keys per session for the purposes of

key agreement

• Means that the compromise of one key and/or message cannot

immediately/easily lead to the compromise of others

• Can be enabled in Kerberos, HTTPS, OpenSSL, some public key crypto

algorithms

Preparing for Quantum Break

Lessons

• Quantum computers are likely to break traditional public key crypto “soon”

• You can start preparing now

• Don’t just wait for quantum supremacy to be announced without a solid,

thoughtful, plan in place

Key Take Aways

Info

• https://www.amazon.com/Cryptography-Apocalypse-Preparing-

Quantum-Computing/dp/1119618193

• Appendix at end of book lists dozens of sources

• https://en.wikipedia.org/wiki/Quantum_computing

• Go to Youtube and search on “quantum”

• Pick a few videos

• Go to Amazon and search on “quantum”

• Pick a few videos and maybe a book or two

More Learning

Resources

» Learn More at www.KnowBe4.com/Resources «

Thank You!

Roger A. Grimes
roger@banneretcs.com

Twitter: @rogeragrimes

LinkedIn: https://www.linkedin.com/in/rogeragrimes/