back to article NIST readies 'post-quantum' crypto competition

Your mission, should you choose to accept it, is to help the National Institute of Standards and Technology (NIST) defend cryptography against the onslaught of quantum computers. It hasn't happened yet, but it's pretty widely agreed that quantum computers pose a significant risk to cryptography. All that's needed is either a …

Anonymous Coward

The Hype surrounding Quantum Computing reminds one of this:

https://en.wikipedia.org/wiki/Extraordinary_Popular_Delusions_and_the_Madness_of_Crowds

5
3
Anonymous Coward

Re: The Hype surrounding Quantum Computing reminds one of this:

Way, hello there mister NSA agent. How's been work lately? Still posting drivel on public boards, I see?

0
5
Silver badge
Coat

Re: The Hype surrounding Quantum Computing reminds one of this:

I can't wait for my own quantum code cracker, powered by cold fusion of course.

7
1
Silver badge
Pint

Re: The Hype surrounding Quantum Computing reminds one of this:

I've just ordered up a cartridge of Quantum Computer Paste for my 3D Printer.

It should arrive just after the cartridge of Flying Car Paste that I'd order last year finally arrives.

2
0
Anonymous Coward

Easy, leave decrypted every n character, no matter how much quantum processing you throw at it, it's never going to get the right decryption because in part there isn't any.

0
5
Paris Hilton

Really? You're quite Shor the people designing the algo for the QC will be ignorant of your cunning plan?

3
0
Anonymous Coward

What about before encryption switching languages every sentence? Inserting a random word every n words? Reversing the entire string? Splitting the string into equal parts then reversing each one independently? Using Google translate to transverse 5 languages ensuring the reverse translate matches the original string?

I think you're looking at the crypto only, this is out of the box thinking. Machines are only as clever as we make them but in essence they are dumb so if the person programming hasn't thought of the many ways you can harden the encryption then they are doomed to fail.

1
7
Anonymous Coward

Not as "out of the box" as you seem to think. What you're describing is a sort of crude, clumsy, weak pre-encipherment. Instead of the crude, clumsy, Heath Robinson crap you suggest, why not just use a different modern cipher for your pre-encryption obfuscation? Why not pick something widely believed to be secure in its own right and designed to produce ciphertext which is demonstrably statistically/cryptographically indistinguishable from random data? Something which has withstood decades of analysis itself. Then encipher its statistically/cryptographically pseudorandom output using a different cipher and unrelated key. Just as Truecrypt used to do... Before it was harried into oblivion. There's been some interesting work done in proving the worth of such approaches and how they compound, useful in the light of offputting thought experiments like "evil ciphers" ...and which might go some way to explain what happened to TC.

Better than entrusting your "secret" in plaintext to the interwebs and Google Translate, wouldn't you agree?

6
0
Anonymous Coward

Maybe I didn't explain myself, what I am suggesting is that if you have an algorithm that can process millions of combinations simultaneously to crack the cipher then wouldn't that be rendered useless if the original information made no sense unless you knew what to do with it after you had removed the encryption and how would the algorithm determine it had decrypted something if it didn't know what it was decrypting as the output wouldn't match the expectation. I suppose I'm also asking why we solely rely on math to encrypt rather using random ideas as well to create encrypted data, surely that would be more difficult to break and yes google is a bad idea but they do no evil...

0
5

The trouble with 'random' ideas . .

is that they are no use for the frequent, reliable transfer of information. Although what you are suggesting would probably work very nicely for a single communication, or set of communications, with a known other (who knows what tricks you are pulling) it would not work as a widely available communications system where standards have to be created, agreed to, implemented and therefore become common knowledge and easily reversed.

The reason we rely on maths is because it provides a known method for reducing structured information into essentially random data together with a key that can be shown to be breakable only by the application of 'n' clock cycles and that 'n' can be adjusted to whatever level of security you require (bugs and implementation errors excepted).

6
0
fnj

@AC:

Just as Truecrypt used to do... Before it was harried into oblivion.

Oblivion: the act or process of dying out; complete annihilation or extinction.

Truecrypt is not dead or forgotten. The source code still exists and still compiles just fine, and it is just as effective as it ever was.

1
0

Even easier.

Dont use electronic signals as a means of secure communication.

I propose a peer to peer smoke signal network with a layer of semaphore for security.

3
0
Go

Re: Even easier.

How about carrier pigeons? There's a n app RFC for that.

1
0
Anonymous Coward

Re: Even easier.

The problem with pigeons is you can shoot them down and eat them. You cant shoot down and eat a smoke signal.

If you insist on avian based messaging though...I posit that we should train seagulls to shit in QR code patterns on car bonnets.

0
0

I find it heartening . .

. . that before an encryption apocalypse is upon us there are already several avenues of investigation open because mathematicians (I assume) 'wasted' their time with developing branches of Number Theory that most people would look at and say, "What's the use of that?".

Anyone responsible for science funding should take lessons from these sort of developments.

5
0

Re: I find it heartening . .

"No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years." -- G. H. Hardy

Sadly, even the best mathematicians sometimes get things very wrong.

5
0

Re: I find it heartening . .

To be fair it has been 'quite a few' if not yet 'many years'.

1
0
Anonymous Coward

Re: I find it heartening . .

Relativity is used by GPS satellites to compensate for the difference in velocity between the satellite and the ground based observer. And militaries have loved GPS navigation for years.

1
0

Re: I find it heartening . .

It has been about 75 years since Hardy said that.

2
0
Silver badge
Pint

Re: I find it heartening . .

AC "Relativity is used by GPS satellites... ...militaries have loved GPS..."

There's a story that the earliest GPS satellites had a remote controlled 'Relativity Switch', because the military decision makers didn't quite trust the Einsteinian Physics.

If it's true, then it makes the point opposite of what you made. Which is funny.

2
0
Anonymous Coward

Re: I find it heartening . .

Funny, but not opposite. If it's true, then sentient geeks bearing relativity provided the bumpkins with their make-it-work switch.. so yes, relativity *is* useful to warmongering morons: It's the "on" switch for their ICBM guidance system

1
0

Re: I find it heartening . .

before an encryption apocalypse is upon us there are already several avenues of investigation open because mathematicians (I assume) 'wasted' their time

Much of the research directly relevant to post-quantum cryptography was done after quantum computing was conceived. After all, we've known Shor's and Grover's algorithms for two decades now.

Lattice-based PQC algorithms like NTRU are of similar vintage. As the article notes, McEliece (one of a family of PQC algorithms based on error-correcting codes) is even older (almost four decades); but it was invented as a cryptosystem, i.e. as a piece of applied mathematics.

It is nice to know that, broadly speaking, cryptography has found applications for number theory and some other once-abstract branches of mathematics - not because there's anything wrong with pure mathematics, but because it's an interesting and unexpected consequence. But it's more true of conventional cryptography than of QC.

2
0
Anonymous Coward

One time pad

Perhaps one-time-pad's time has come?

For many years, storage sizes have been growing exponentially while the costs drop. You could cheaply make individual business cards with 4GB of random numbers and exchange them with everyone you meet; for site-to-site links you can have a 1TB hard drive at each end.

You could use these random numbers as AES-256 keys, or for really sensitive stuff encrypt the message directly with the pad.

No quantum crypto is going to break that.

1
3
Anonymous Coward

Re: One time pad

But if you keep re-using the same data off the card it's not a one-time pad?

4
1

Re: One time pad

Obviously you would need some system to make sure the keys are only used once. To start with, the cards you hand out would have to be unique (while you keep a copy of each). Each would contain two separate blocks of key data, one for sending and one for receiving.

It still might not be super practical, but the basic idea is sound, say 4GB is good for an awful lot of emails.

2
0
Silver badge
Pint

Re: One time pad

It's an obvious idea. I posted the same basic concept before (about six months ago, and likely previous to that...). I have no idea why anyone should downvote it. It's common sense that it could be made to work. Cheers.

Zener diodes, transistors, ring oscillators and such ...as sources of noise It seems obvious that such noise should be packaged up into 1kB blocks, and then written to pairs of multi-TB SSDs for physical distribution. The hardware would look like a HDD duplicating machine. 'Several TB of One-Time Pad should be enough for anyone.'

http://forums.theregister.co.uk/forum/2/2015/11/12/big_bang_left_us_with_a_perfect_random_number_generator/

0
0
Silver badge
Pint

Re: One time pad

AC "But if you keep re-using the same data off the card it's not a one-time pad?"

The solution is in the name. It's a "One Time Pad".

After using a block of randomness, securely erase it at each end.

Your objection is ridiculous. One shouldn't have to explicitly rebut such trivialities.

0
1

Re: One time pad

Sigh.

Every crypto article gets this response.

OTPs are symmetric encryption. Symmetric encryption does not give a rat's ass about quantum cryptanalysis. QC only provides at best a quadratic improvement in the size of the inner loop when breaking a symmetric key. Doubling the key size removes that advantage.

OTPs are largely useless in practice, because you need a secure channel to transmit as much information as you plan to encrypt. If you have that secure channel, then just use it to send your messages.

2
0
Silver badge
Pint

Re: One time pad

MW "If you have that secure channel, then just use it to send your messages."

There's a concept called 'The Axis of Time'.

Those that ignore it can fail to think clearly.

Alice and Bob can meet (at some point in time), probably in Vienna, have amazing sex, and organize their pair of multi-TB One Time Pads. They they can bid a tearful farewell, and Bob heads off on his mission. Then (at all following points in time) they use the One Time Pads. Seeing as how the OTPs are huge, they'll last for years.

I shouldn't have to explain this.

1
0
Silver badge

But wouldn't the 'quantum resistant algorithms' be resistant and non-resistant at the same time?

Anyway, the point of one time pads is that that you use each and every one of them only once, ever. So if you can make as many one time pads as you'll ever need, based on a truely random generator, and don't ever re-use them, well...

1
0
Anonymous Coward

And isn't another 'problem' with one-time pads . .

. .apart from their 'one time'-ness getting the pad, securely, to the entity that you are trying to communicate with securely?

2
0
Silver badge
Pint

Re: And isn't another 'problem' with one-time pads . .

AC: "...getting the pad, securely, to [Bob]..."

With multi-TB OTPs, that's a 'One Time' problem.

This is in the context of spying, not online banking.

Bob can pick it up from Alice.

I've contemplated an algorithm to refill OTPs (below), but it's been downvoted so it must be infeasible. I guess that the Downvote button is too small to contain the details of the flaw.

1
0
Anonymous Coward

NIST is being prudent

It will take years to properly vet suitable PQC suites and they are worried about matters decades from now.

Betting on QC is truly a mug's game. Personally, I think ECC has years of life (and world+dog is moving towards it) and that the NSA's recent about-face is more politics than anything else (e.g. http://cacr.uwaterloo.ca/~ajmeneze/publications/pqc.pdf ).

1
1

Re: NIST is being prudent

Sometimes stuff can arrive sooner than you think - and betting that it won't would be much more of a mug's game than putting in a little ground work in preparation.

3
0

Re: NIST is being prudent

Personally, I think ECC has years of life (and world+dog is moving towards it)

Almost certainly.

and that the NSA's recent about-face is more politics than anything else (e.g. http://cacr.uwaterloo.ca/~ajmeneze/publications/pqc.pdf ).

There are many possibilities. FUD is definitely one. But let's assume the NSA is privy to a non-NOBUS attack (i.e., one they think someone who isn't the NSA could discover) against ECC. If it's a QC attack, then it will be a long time before it's economical to apply it to traffic that isn't very valuable to the attacker. Even if it's a conventional attack, the economics may not make it worth attacking generic HTTPS traffic and the like.

2
0
Silver badge
Pint

"Sometimes stuff can arrive sooner than you think..."

The rule of thumb is...

Everyone always overestimates human progress in the short term.

And everyone always underestimates human human progress in the long term.

The transition point is *about* 50 years.

0
0
Silver badge
Pint

Quantum Communications

It's been described as 'untappable'.

If so, use that. Send the secret data in the clear.

Nothing for the TLAs to decrypt.

0
0

Re: Quantum Communications

It's not economically feasible to set up quantum-communication links among all the computers in the world.

For one thing, some of them use wireless connections.

1
1
Silver badge
Pint

Re: Quantum Communications

It's a long-term thing. The Gantt chart still has some 'Magic Happens Here' elements.

PS: It's a comment, not an NSF Grant Proposal.

0
0
Silver badge
Pint

One Time Pads

TB of good noise physically delivered on media.

Securely erase each block after use.

0
1
Silver badge
Pint

Recursive One Time Pads

My instinct tells me that it should be possible to securely communicate replacement One Time Pad noise, so Alice can refill Bob's slowly depleting One Time Pad, within a message.

E.g. 2 kb transmission, carrying 1 kb of message text (encrypted) AND another 1 kb of replacement noise (encrypted), both encrypted using the same 1 kb of One Time Pad. The new nose is noise; so you can reuse the One Time Pad in this case.

But I'm not sure. It might be a house of cards. It might violate conservation of entropy. It might prove to consume as many bits as are transmitted.

But I suspect it's feasible.

0
1
Silver badge
Pint

Re: Recursive One Time Pads

One downvote (so far).

Any explicit rebuttal on why it wouldn't work?

Other examples to think about (same concept):

E.g. 1 kb of replacement bit-wise noise (encrypted, new block of One Time Pad), but encrypted using the same-old same-old 1 kb of One Time Pad used to send all the new blocks of One Time Pad. The new noise is bit-wise noise; so you can endless reuse the One Time Pad when sending more good bit-wise noise.

E.g. One secret bit = 'X' (0 or 1). Used to XOR-encrypt an endless bit stream of noise. The noise is either inverted or it's not inverted. Can you ever guess 'X'? I don't think so. One bit OTP. Same thing.

Rebuttals very welcome.

0
0
Silver badge
Pint

Chaos

The endless bifurcation of the trivial Chaos equations provide a rich source of deterministic noise.

This one: https://en.wikipedia.org/wiki/Bifurcation_diagram

There's gotta be some new cryptography algorithm in there somewhere.

Infinitely close to r = 4.

1
0

Commentard suggestions

ow ow ow ow ow

The goggles do nothing.

(I wonder: if the Reg ran a story on, say, brain surgery, would we get world+dog here explaining why the surgeons are doing it wrong?)

1
1
Silver badge
Pint

Re: Commentard suggestions

@Michael Wojcik "... brain surgery, why the surgeons are doing it wrong?..."

Your objection is effectively an 'Appeal to Authority' argument, which is....uninteresting.

0
0

McEliece probably not the leading contender

The problem with McEliece is key size. 1 MB keys are a bit awkward.

Europe seems to be leaning toward a variant of NTRU that's not patent-encumbered. Key sizes aren't great for the NTRU lattice problems either, though.

Personally I think Ring-LWE looks like the best candidate at the moment. Proven to reduce to a believed-hard problem, so unless someone shows P=NP or something equally drastic (FTL travel, decryption by unicorn magic, etc), it looks secure. And key sizes and performance are within the practical range.

For symmetric crypto, PQC is straightforward. Longer key and digest sizes do the trick. No algorithm in BQP can achieve better than quadratic improvement in number of iterations for breaking a symmetric key, and that's assuming iterations on a QC are as fast as on a conventional machine, which is very unlikely.

AES specifically will probably need to be tweaked, because its faulty key schedule means you can't just make the key longer and get an equivalent improvement in strength. The article's wrong about that. Similarly, we're not so sure that SHA-2's digest can be made larger arbitrarily without compromising the hash. We're not certain about SHA-3 either, but it was designed to produce larger digests, so it's probably the better candidate there.

1
0

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

Forums

Biting the hand that feeds IT © 1998–2017