back to article Cisco backs test to help classical crypto outlive quantum computers

Cisco and quantum security outfit Isara reckon they've got at least as far as alpha stage in one problem of the future: securing public key certificates against quantum computers. “Quantum computers will break cryptography” is a popular mass media trope, but the big brains of crypto have been aware of the risk for some time. …

Pascal Monett
Silver badge
Thumb Up

Encryption is complicated enough already

And now they have devised a way to harden it against quantum computing and are even testing it ?

Wow.

For having dabbled my toes in the waters of encryption, I couldn't for the life of me even begin to envision a way of not only creating a robust cipher scheme, but one that can resist being analyzed by a quantum process.

There are some seriously intelligent people on this planet. I hope they succeed as well. That'll put a dent in all the "backdoored encryption" nonsense.

amanfromMars 1
Silver badge

Re: Encryption is complicated enough already and in perfecting systems, totally unnecessary

And now they have devised a way to harden it against quantum computing and are even testing it ?

Wow. .... Pascal Monett

Hi Pascal,

I second your doubt and incredulity and raise the spectre that their thinking of successfully hardening encryption against quantum computing is beautifully and catastrophically delusional.

And, furthermore, that which and/or those who would disagree or agree that such be the current state of ACTive Affairs are to be beta tested to prove provision of protection against quantum computing is not possible or required.

PyLETS
Holmes

Re: Encryption is complicated enough already

Interestingly enough I supervised a student project last year investigating post-quantum cryptography algorithms. It's basically about arithmetic. I'm not a mathematician myself, but the student already had a maths degree so was qualified to look at and compare current proposed post-quantum schemes. My main problem was understanding what she wrote well enough to give a fair mark for her paper. This promises to solve a big problem if quantum computing ever becomes a reality and we don't want to have to patch this issue very hastily as that's likely to leave very many implementation holes we'd rather not create in the first place. So it's a timely area of maths research.

For non-mathematicians, public key cryptography all hinges around a set of numbers on which arithmetic can be performed to make other numbers from them. let's call these numbers by their RSA convention, M,C,E and D . (RSA uses 2 numbers: E and N both as the public key but I'll just call this number E here for simplicity).

The algorithm needs to find a way to transform a randomly generated number: M ( M is for message, but it's actually used to encrypt the real message. It's a random 256 or 128 bit number used as an AES symmetric session key. We use symmetric algorithms for the heavy lifting, and public key algorithms to help protect the symmetric keys ).

We make M into an encrypted number: C, (for cyphertext)

so using a public key: E, we can say:

C = encrypt(M,E)

such that the private key: D can be used to convert C back into M.

M = decrypt(C,D)

If the public and private keys E and D are generated from the same input as a related pair, and knowledge of C and E by an eavesdropper can't be used to obtain M or D and having a large working quantum computer is no help, then the properties of RSA will hold in a post-quantum crypto scheme with the above arithmetic properties.

It's also useful if the scheme works in the opposite direction, so encrypting a hash H of a message into S using private key D can be reversed using the public key E to regenerate the hash, this scheme can be used for message signing and signature verification as well as message encrypting.

S = sign(H,D)

H = verify_signature(S,E)

So we've got 4 functions, each of which takes 2 parameters as input and generates a single output. How we use the inputs and outputs outside of these functions stays the same, it's what's inside the encrypt, decrypt, sign and verify_signature functions which concerns these different post quantum algorithms.

Lee D
Silver badge

Re: Encryption is complicated enough already

Yeah, I'm a mathematician.

I just tried to read the paper on SPHINCS, written by that Dan J Bernstein guy. I can't see the reasoning for something to be post-quantum-safe, to be honest. It's all described as being so, there's lots of proofs and algorithms written around it, but the actual reasoning for why it's post-quantum safe is dubiously obscured or absent.

It seems to hinge on hash-algorithms not being quantum-attackable but I can't see why that's a valid assumption if someone can build a large enough quantum computer. Presumably the number of items that COULD hash down to a tiny single hash are huge, so you don't know what was actually hashed to get that result.** ("A recent result by Song shows that these proofs are still valid for quantum adversaries")

The rest is about eliminating mid-states of the hash calculations - most hashes started with a number, and then each byte of data you incorporate gives you a new hash. You then use that hash to mix in with the next byte, and so on. Presumably "stateless" hashes don't have those intermediary hashes available, but it's not clear how. (I could be really wrong here, but it suggests that you compute a tree of keys for the size of the message you want to encrypt BEFORE you start, and each key is basically a one-time key used only for that particular part of that message. Then you encrypt each byte/word/whatever individually? It kinda makes sense, but I can't see what it adds, so long as the states are kept secret).

Basically, we just need one bad assumption ("Hashes are safe against quantum, while nothing else is") and the whole thing falls apart.

** This is how I analogise quantum computing, it's vastly inaccurate but it gives you the idea. If you are after, say, two large prime numbers that multiply out to a known number (the basis of public-key cryptography), then in traditional computing you have to basically try all the reasonable combinations until you hit the right one, which can take longer than the age of the universe.

In a quantum computer, you build the machine backwards. Here is a machine that multiplies two numbers, you design it to do so. Then you plug in the ANSWER you want. The magic of quantum effects then automatically provides you with the only state that could have possibly resulted in your desired state given the "circuits" you build and the condition you placed on the answer. Instantaneously.

Presumably a quantum computer, because there is only one right answer, is very good at breaking traditional prime-based public-key cryptography, but when it comes to hashes - well, an entire infinity of data sets could hash to the same value (just not EVERY data set), so just working from the hash backwards doesn't work - you don't gain any knowledge about the actual data that was hashed in the first place.

Thus building the core of encryption on thousands and thousands of tiny such hashes, it's possible that it makes the number of possibilities so vast, even with instantaneous discovery of every single one, that it becomes infeasible.

To me, though, if you had a large enough quantum computer, you could easily get those infinities of answer, and perform a known-plain-text attack and similar by pre-loading the circuits to take account of that as well. Much harder, but still theoretically breakable. I wouldn't know how much more complex, but maybe it does make it complex enough that it's infeasible. There's also talk of time-based hashed and other factors, which might well make it more difficult.

Note that all good encryption methods are immune to known-plaintext attacks.

Could be absolute tosh from a physics point of view, but it's an analogy that appears to work.

Milton
Silver badge

Re: Encryption is complicated enough already

If there is a consensus on quantum computing (QC) it is perhaps that just as there are classes of problems that QC ought to be very good at, solving quickly compared to classical computing, there are also classes of problems that QC ought not to be good at. Lee D gives a creditable hint of this in his post.

Cryptographic protocols dependent upon factorisation of large primes are a striking example of the "bounded error, quantum" problems soluble in polynomial time which a QC system is expected to excel at (mathematically, "P-type" problems as distinct from "NP-complete" ones). So straightaway there are reasons to worry that a lot of modern crypto, supposedly tough for classical computers (which would have to spend thousands or millions of years trying to break schemes with non-trivial keys) may be relatively easily broken using QC. It is also notable that the class of problems wherein QC's high error rate is less of a performance inhibitor are theoretically more amenable to quantum solutions.

So it is to be expected that if you're looking for schemes that will be hardened against QC, you look for ones dependent on "NP-complete" problems, preferably where the expected high error rate of QC remains a crucial weakness.

A couple of points to note. It still isn't universally agreed that there is a way to reduce the error rate of QC to the point where it will ever be practically useful for anything much. There are respectable experts who are honestly sceptical. But if Microsoft, as reported recently, succeed in their radically sneaky effort to use majorana particles in a QC system, and are correct that this offers a route to greatly reduced error rates, it makes everything we've spoken of much more urgent. QC might yet be highly effective in cracking many modern encryption schemes. Given the lingering uncertainties about the true difficulty of some candidate NPC problems, pace new math discoveries and techniques, that may yet mean our children grow up in a world bizarrely infested with one-time pads—which, tedious as they are, would, managed properly, resist all efforts to break until the end of time. (And I'd note, perhaps wryly, that it's more possible than ever to transport huge amounts of random data in almost infinitesimally tiny packages.)

However, my personal suspicion is that QC will not be fully effective in breaking decent crypto until new math techniques are developed to support it. (Think of advances in graph theory for an example.) It's a mere hunch, but I think that, in an era where we are frequently discovering unsuspected links and deep similarities between what were previously thought to be entirely distinct branches of mathematics, these will prove to be the "magic sauce" that takes QC from "curiosity" to "miracle worker".

Peter2
Silver badge

Re: Encryption is complicated enough already

For having dabbled my toes in the waters of encryption, I couldn't for the life of me even begin to envision a way of not only creating a robust cipher scheme, but one that can resist being analyzed by a quantum process.

I can come up with an encryption scheme proof against any possible cracking, at least between fixed points such as my branch offices to HQ. It's really quite simple when you think about it. One time keys stored on Multi terrabyte removable media.

Filling a 4TB drive would let you shove ~200GB worth of traffic a (working) day down the link to base and still give you a months worth before needing to securely put a new drive in place with new codes at both offices. Administration would be a pain, but it would be completely uncrackable, even by an evil AI running on a quantum computer.

It is probably the most inelegant solution ever, and it does have a (long) list of problems, but it would have the virtue of being secure against pretty much anything conceivable.

Lee D
Silver badge

Re: Encryption is complicated enough already

Sourcing 4TB of truly random data is probably harder than just stopping a quantum computing attack.

Ian Michael Gumby
Silver badge

@Lee D ... Re: Encryption is complicated enough already

Thus building the core of encryption on thousands and thousands of tiny such hashes, it's possible that it makes the number of possibilities so vast, even with instantaneous discovery of every single one, that it becomes infeasible.

Pretty much.

I think we're at the stage of Quantum computing where its possible to break some encryption so that its possible to steal BTCs from your wallet. Or bank.

Crypto Monad

Re: Encryption is complicated enough already

I don't think the QC stuff is attacking symmetric ciphers anyway; so you could just swap an AES256 key every hour, and then 1MB of one-time pad will last you nearly 4 years.

This works for site-to-site links, and it works for people you might meet in person - e.g. swapping a business card with a one-time pad stored in it, or touching phones to swap one-time pads via NFC.

It's rather harder to use one-time pads for:

(1) encrypting traffic to entities you never meet in person, like amazon.com

(2) signing things (like contracts, instructions to your bank etc)

without involving trusted third parties.

Lee D
Silver badge

Re: Encryption is complicated enough already

I don't think AES is at all safe in a post-quantum world, no matter what keys you choose.

A comment I found from 2013: "The best known theoretical attack is Grover's quantum search algorithm... this allows us to search an unsorted database of n entries in √n operations. As such, AES-256 is medium term secure against a quantum attack, however AES-128 is broken, and AES-192 isn't looking too good. With the advances in computational power (doubling every 18 months, etc.), no set keysize is safe indefinitely."

And that's the worst-case example of just using a QC as nothing more than brute-force on the keys, not even taking advantage of any particular exposed weakness, etc.

A QC will radically change the landscape of encryption forever, because it just works in a very different way. It's not a case of "just increase the keysize" any longer. The solution is IMMEDIATE. The keysize barely matters, it affects only the size of the QC that you need build, not the time to solution. Once someone starts building decent-sized QCs and joining them together you won't be able to make the key large enough to be practical for you to use, while impractical for them to build a machine capable of breaking it instantaneously.

AES is dead in such circumstances. As is pretty much every conventional encryption algorithm. That's why post-quantum cryptography is an entire area of research and relies on things which we have but which we DO NOT yet use in the ways we'd need to to make them post-Q safe. Even ECC cannot escape this and requires reinvention to be valid post-Q.

Think about how it works - it's no longer a case of just "making things laborious" in terms of brute-force. That's gone, in a post-Q world. No amount of brute-force can withstand instantaneous calculation. What works is literally: you get billions of possible answers (hashes used on an enormous scale as an integral part of the basic encryption system which they currently aren't), or you have to build a quantum computer so huge that your adversary can't afford it.

The latter is literally just a matter of time and effort again, though.

Post-Q instantly invalidates all currently deployed encryption methods overnight. They all become nothing more than plaintext, in effect. Now matter how carefully you chose your keys, how big they were, how well you secured them, or what flaws may exist in the algorithm, etc.

Post-Q cryptography has to be a reinvention from first principles, which is why things like SPHINCS just don't have any resemblance to a current encryption system. Currently we USE encryption to build hashes. Post-Q we'll use hashes to build encryption.

Gene Cash
Silver badge

"using post-quantum schemes if machines support them, but falling back to traditional certificate checks if not."

So is this another TLS downgrade attack for the 2030s?

Claptrap314
Bronze badge

One Time Pads are not Magical

To be useful, an encryption scheme requires not just that adversaries be unable to read a message, but that the intended recipient are able. One time pad systems are all about key management.

In a public key system, a potential recipient publicizes a public key, and keeps the private key--private. It is never transmitted. With one time pad, there has to be a communication of the pad between sender and recipient. And how do you secure this channel of communication?

I'm not saying that one time pads are useless. Just limited.

Anonymous Coward
Anonymous Coward

Re: One Time Pads are not Magical

In the case of public key cryptosystems, you still need to be sure that the public key you hold corresponds to the person you want to send to - as opposed to a man-in-the-middle. So it's just another version of the key distribution problem.

The solution today is to let a trusted third party certify the key as belonging to the person you think it does. But there are many such third parties, all of which can certify any key and any identity - the grounds for trusting *all* of them seem to be pretty low.

Brian Miller
Silver badge
Joke

Why did they name it ...

Sphincs? Sure, there's a good reason for it, but if flaws are found, the results will be: Sphincter, diarrhea, and every single related Captain Obvious pun.

Choose project names carefully! :p

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2018