Let's harden Internet crypto so quantum computers can't crack it

In case someone manages to make a general purpose quantum computer one day, a group of IETF authors have put forward a proposal to harden Internet key exchange. It's a handy reminder that in spite of a stream of headlines telling us that quantum computers will break cryptography, there's a substantial amount of research going …

[Duncan Macdonald]

Possible deadly flaw - compromised software

For a closed source implementation (eq most Windows programs) there is a danger that a deliberately weakened random number generator is used. If the public/private key pair is generated with only 32 bits of randomness instead of 2048 or 4096 then breaking would be easy for the NSA. This would not be easily apparent to the users of such compromised software as all the key exchange protocols would proceed as normal.

Note such a flaw could already have been placed in IE/Edge at the request of the NSA and there would nothing to indicate the problem to users. (Make 96 bits of the 128 bit AES encryption key depend on the other 32 bits and the NSA has an easy decryption job.)

[Mark 65]

Re: Possible deadly flaw - compromised software

One more reason to use open source software then?

I'm also pretty sure that researchers would be able to check whether the key generator / random number generator in IE/Edge is producing shite. It's not like there wouldn't be many eyes (more than just the 5 usuals) looking at this aspect.

[Ian Michael Gumby]

@ Mark 65 Re: Possible deadly flaw - compromised software

Actually no.

There are other ways to increase randomness.

Imagine using the random number to find a seek position in to a file of random noise. Then a second number to get its length. And then take a hash for your random value.

Now tell me how a quantum computer can break that since they lack the actual random noise file.

It may not be the fastest, but it will do the job

[Anonymous Coward]

Re: @ Mark 65 Possible deadly flaw - compromised software

One of the assumptions of intelligence is that you assume your opponent has perfect intelligence. Thus they'd have the noise file as well. The proposed solution here is far better than your approach. Nice one, though.

[Milton]

Re: @ Mark 65 Possible deadly flaw - compromised software

Can't speak for the US but in Blighty, Army training for officers makes the point that overestimating your enemy can be as dangerous as underestimating him. So despite my point about the revival of OTP, the truth is that you should adopt the cheapest and easiest encryption scheme commensurate with (a) the current importance, sensitivity, riskiness etc of the data, and (b) an eye to how long this actually matters. But—beware of your adversary's ability to draw inferences.

At its simplest, it's not just about today's security, it's about your strategic or tactical planning horizon. The proposed trajectory for your new ICBM test firing ceases to be a worthwhile secret 40 minutes after takeoff. The list of deep cover spies working at the highest levels of Russian politics should be secured for at least a century, to avoid future reprisals against their families. And so on. (Or in an extreme case, the plans for the F-35 should have really weak encryption, in the hope the Russians and Chinese will copy it and end up with planes as bad as ours.)

Of course, per "inferences" above, the "perfect intelligence" issue can catch you even if your adversary cannot decrypt your messages. If he can see senders and recipients, file sizes, times, station IDs etc, he may be able to make worthwhile inferences merely from traffic patterns ... does Airbase D always change its observed readiness level within 12 hours of a short message from Station B, and does this always occur after a longer message from A via C? It's a beautifully multi-faceted problem ....

[Ian Michael Gumby]

@Milton Re: @ Mark 65 Possible deadly flaw - compromised software

Using your army training.

The concept is to generate a single use pub/pri key as the initial wrapper for the counter party to send you a random secret.

Then you can further use the shared secret...

Simple concept.

The issue being raised was that the random secret wasn't so random.

But if you have a random noise file, changing the offset in to the file will increase the randomness instead of sharing the same file each time. If you were to then change the length of the seed and hash it using a strong algo (e.g. SHA-2) you will have a fairly unique number of a fixed length that is well ... more random and harder to find over time.

Note: If I use the same secret over and over and only generate a new pub/pri key, then its possible to break it w a powerful enough quantum computer. If the secret is not the same... then you will have a bit harder time, now wouldn't you?

Does that make sense?

[amanfromMars 1]

Re: Flawed Assumptions in Deficit of Better Beta IntelAIgents

Howdy, Jack of Shadows,

Realising would be opponents and wannabe competition are of another and always less than perfect intelligence easily renders a different intelligence leaps years ahead of all current developments and perfect enough for pioneer use to deliver plans and outcomes to be practically almighty and virtually safe from discovery and malicious manipulation.

And such renders the likes of a UKGBNIGCHQ/USANSA as just an expensive quango and most ineffectual ponzi operation/Massively Assuring Deceptions scheme/Secret Information Scam. And that is always catastrophically an abnormally spontaneous self-defeating reality phorm of malicious manipulation for maladministrations.

[Ian Michael Gumby]

Yo! Zalazny wantabe ... Re: @ Mark 65 Possible deadly flaw - compromised software

One of the assumptions of intelligence is that you assume your opponent has perfect intelligence. Thus they'd have the noise file as well. The proposed solution here is far better than your approach. Nice one, though.

Love your lit reference to a fantasy/fiction character that can never die...

But you missed the point.

No. Perfect intelligence would be that they have the same random noise sample. Thus if you use a less than random number generator, it would be possible to generate a series of pairs of random numbers (offset and length) and could then generate the same hash that you use. (Assuming that they also know which hash you are using.)

But the attacker doesn't have your random noise file, nor do they know which hash algo you're using. So they can't easily find your seed. Which is the point.

Note: I was responding to a fellow commentard who believes that FOSS is better than a proprietary solution. Which in this case isn't true. I just created a simple way to generate a secure random number that would be very difficult to break. The whole example was how to get a more random number or seed for your encryption algo than one from simply using a random number generator which you may find to be less than random...

[Anonymous Coward]

Re: Yo! Zalazny wantabe ... @ Mark 65 Possible deadly flaw - compromised software

Gotcha. I still love it as an implementation which is where "nice one" came from. I'm just used to the Schneier blog when I wander in these waters. They set a rather high level on the topic.

[Milton]

Re: @ Mark 65 Possible deadly flaw - compromised software

Forgive me, but your example implies that the "file of random noise" is the key. In which case it is a one-time pad. If it is *truly* random, not PRNG, no further hashing or randomisation is necessary.

As with all OTP schemes, everything then distils to:

1. Is the OTP truly random?

2. How will you distribute the keys?

3. How can you do #2 and be 100% certain no illicit copies are made?

4. How do you prevent everyone using the OTPs from witlessly or accidentally encrypting two or more messages with the same OTP and thereby blowing a hole in your security?

OTP is being adopted rapidly by certain governments for critical data exchange (many lightly laden couriers with fingernail-size data chips ready to be swallowed), but the problem of ensuring that a key in transit isn't compromised remains a thorny one.

OTP may yet be the only inviolably secure system for the future, but not until someone figures out a foolproof way to detect whether an OTP data source has been copied (or ensure it destroys itself if copied).

[Ian Michael Gumby]

@Milton ... Re: @ Mark 65 Possible deadly flaw - compromised software

WHOA!

You misunderstood my comment.

From the article:

The brief explanation of such a key encapsulation mechanism (KEM) is: “the initiator randomly generates a random, ephemeral public and private key pair, and sends the public key to the responder in QSKEi payload. <u>The responder generates a random entity, encrypts it using the received public key, and sends the encrypted quantity to the initiator in QSKEr payload. </u>The initiator decrypts the encrypted payload using the private key. After this point of the exchange, both initiator and responder have the same random entity from which the quantum-safe shared secret (QSSS) is derived.”

The issue that was being raised was that the lack of randomness in the responder's payload.

Yes you are correct. All I would want is a random start point in to the noise file. Yes, even though the file of random noise is random, I wanted to add more randomness by offsetting the starting point in to the file.

Most people download a random noise file than try to generate one themselves. (There are actually web sites that sell random files. )

So if I have a 8KB random noise file, I could randomly set the offset such that I can generate multiple sets of 4K or 8K strings that are less likely to be repeatedly sent to the counter party.

I don't need to do the hash, however the hash would be smaller than the 8K file and would be faster.

The key to this is that the pub/pri key is being generated on the fly and is used one time (implied) and then you're sharing a random secret back. The implication is that the random secret is also one time. Thus sending the same random 8K secret would reduce its effectiveness. By randomly changing the starting point would increase the 'randomness' in the process. If you take a random length and hash, you would increase the randomness with a potentially long enough value that changes each time.

Does that make sense?

[Anonymous Coward]

Re: @ Mark 65 Possible deadly flaw - compromised software

The quantum computer does not need the noise file. With sufficient quantum bits, you just search the entire search space for a "key". OK, I over simplified there, but still...

If it is used as a one time pad, then yes, one time pads are theoretically impossible to compromise. However, how do you share the one time pad? Any method of sharing it publicly (over the internet) could be attacked by the quantum computer algorithm.

So I assume the "ethereal" part is making the switch in one time pads quicker than the quantum computer can break them? I've no idea how that stop historical decryption (brute force and waiting a long time to get a result), but it could help stop real time decryption.

[Ian Michael Gumby]

@ Technical Ben ... Re: @ Mark 65 Possible deadly flaw - compromised software

Ok.. you've kinda missed the point.

The article suggest that you generate a one time use pub/private key that you send the public key to the other side. They then create a certain random secret and they use the public key to encrypt their response holding the key.

This has nothing to do with the quantum computer except that the quantum computer is trying to break your encryption. Because this pub/priv key is a one time use, its harder for the quantum computer to break it. And then you have the randomized shared secret. The random noise file is something that makes it harder to break than just taking a stream off the random number generator which may or may not be as random as you would hope. I take it a step further and then say take a random number and use that to find an offset in to the file.

The issue was that if the randomized secret wasn't completely random, it would be easier to break.

And you are correct. The whole point of this is to make it impossible to break the keys in subjective real time or in any short order. If you want to make it more difficult, set up a rolling encryption that does this every so often making it more difficult to listen in.

That's the best you can do.

[cbars]

Re: @ Technical Ben ... @ Mark 65 Possible deadly flaw - compromised software

Mr Gumby...

You've suggested that you can produce randomness by using a random file. A portion of which randomly selected using two - other random numbers, then hashing the result to use as your key.

So... using a random number of random length, and then applying a function to reduce the randomness... as a source of randomness?

Despite the fact that I fail to see how your magic random numbers (the three of them) are produced.; your system fails to address how to communicate such a (weakened) key without eavesdropping. That's the point, and you're just saying words, then suggesting security - by - obscurity as a defence.

I don't like the number of posts you've made, especially because they're all (edit: removed expletive) gibberish. Learn university level maths (and what rhetorical tautology is), research basic cryptography, then read this article again. Then go read the (edit: again, sorry) RFC, then go read the publicly available research papers and come back and specifically explain yourself.

[Adam 1]

Re: @ Mark 65 Possible deadly flaw - compromised software

> Imagine using the random number to find a seek position in to a file of random noise. Then a second number to get its length. And then take a hash for your random value.

It is worth considering how random your random noise file is given the scenario of a compromised RNG.

> Now tell me how a quantum computer can break that since they lack the actual random noise file.

Is your RNG that picks the starting point and length still compromised?

Take a look at Shor's Algorithm to see the problem that quantum computers carrier for classic encryption techniques. I'm short, AES and DH rely on the fact that factorisation of the product of two massive prime numbers is a lot more expensive than their multiplication was. If you break that assumption then pretty much all current crypto fails.

[Adam 1]

Re: Possible deadly flaw - compromised software

> I'm also pretty sure that researchers would be able to check whether the key generator / random number generator in IE/Edge is producing shite.

Whilst my hat contains significantly reduced quantities of tin foil than Duncan's, proving that a RNG is producing unpredictable outputs is a really hard problem unless the attacker does a particularly bad job at it.

For example, the basic random number functions used for non cryptographic purposes (eg. Dice rolls in a game) will almost certainly be seeded by the system clock. That is perfectly fine, the series will stand up to scrutiny, however from a crypto point of view it would be terrible to use because an attacker would be able to narrow down the initial seed value to a (relatively speaking) miniscule search space.

There is also a bit of history of TLAs pushing compromised RNG allowing them a way to break it at will.

Ironically it is in quantum phenomena that we also find the solution to create a true RNG. For example a single photon will either reflect from or pass through a semi transparent mirror, so suitably placed detectors can be used to determine a random bitstream from a photon source. Entanglement can also be used to prove that a message hasn't been observed in transit, so quantum computing is both a blessing and a curse to crypto.

[Anonymous Coward]

Re: Possible deadly flaw - compromised software

Sure, also in MacOS, iOS, Android, ChromeOS, any Linux distro and application from a US company you didn't compile yourself after checking the code...

[Lee D]

Re: Possible deadly flaw - compromised software

The "random noise file" doesn't defend against the attack described - just deliberately not using the full random capabilities available.

Closed source security software is a misnomer. You have no way to analyse what a program is doing, or whether it's not waiting for some flag in the code to be activated (haven't NSA-named variables been found in Windows before now?). Until that point, it just does thing normally, afterwards it does what it likes and isn't being watched.

If you want any semblance of security, you must encrypt yourself using software you trust. Then you can send the resulting message over any computer, connection or service that you want, because only the intended recipients will be able to read it.

But relying on the OS for security is probably not a good idea at all. However, it also has access to all of memory for the entirety of a program's runtime. That means it's game over anyway.

If you want to be "secure" against a well-funded hostile adversary, securing information that that adversary wants (e.g. terrorist-related info etc.), you can't do things on a general purpose, closed-source OS. That's just ridiculous to even suggest.

And more and more stuff is being done in hardware - from AES acceleration and beyond, even on the Z14 mainframe that had an article yesterday. You have *no idea* if that's being done properly. You don't even know if it's using random numbers at all.

And for a long while, Debian was using certificates with both very limited Diffie-Hellman parameters and low value exponents in the keys chosen. So even open-source isn't safe, because nobody is really looking for such things.

And at the end of the day, your data needs to be accessible and you don't memorise 4096-bit keys. Your encryption strength is then only as secure as your access to the machine anyway and most hacks occur through privilege escalation of a process already allowed access to the encrypted data (e.g. database interfaces!).

This kind of encryption really secures only communication in transit, but we confuse it for encryption of all kinds of things. And I don't really believe there are many casual hackers out there sniffing raw packets off the Internet and then breaking the AES streams, even in government. Still our biggest problem is the software used to secure the system, by far. Because while you still have websites that don't hash and salt your password with a decent algorithm, and then never store your original password, and then run off-the-shelf webstores or CMS software, your data always going to be at risk.

It's much easier to compromise one of the endpoints that to bother to try to break an encrypted communication. And any encrypted data saved to disk is only as secure as the weakest credential used to access it (e.g. your network token, your fingerprint - STUPID! -, your memorisable boot password, etc.).

[Paul Crawford]

Re: Possible deadly flaw - compromised software

"And more and more stuff is being done in hardware"

Of which you have no insight into. Not just the AES-acceleration but some using the "random number" generator in the Intel chips. Even if said number generator was genuinely random, how sure are we that Intel has not got some undocumented instruction that gets recent values (or keys for AES)?

Also the whole dodgy "management engine" issue that runs above your OS and may be Internet-accessible.

So yes, it is almost certainly easier to compromise the end-points than to actually break the in-transit encryption.

[Peter2]

Re: Possible deadly flaw - compromised software

One more reason to use open source software then?

Honestly, I think that most if not all encryption programs are probably compromised anyway, as the heads of GHCQ have seemed pretty unconcerned when questioned by parliment about terrorists moving to using encryption. That leaves the options being that:-

1) Encryption is compromised in some form at the moment.

2) The head of GHCQ was both incompetent and poorly breifed.

Which is more likely depends on your point of view. Personally, I feel that the chances of encryption products being secure against government level effort are (imo) likely to be mathematically indistinguishable from zero because the GCHQ staff are highly motivated, quite knowledgable and working on problems full time with numbers of high caliber staff that (for instance) Open SSL can only dream of with their one staff member and ten volunteers.

The heartbleed bug should have once and forever removed any illusion about open source encryption being absolutely perfect.

[Paul Crawford]

Re: Possible deadly flaw - compromised software

"1) Encryption is compromised in some form at the moment.

2) The head of GHCQ was both incompetent and poorly briefed."

I doubt it, far more likely are:

3) Metadata on who is talking is more valuable for threat detection

4) Compromising most phones/PCs is easy as piss for them (just look how well WannCrypt spread, etc, using an exploit their mates at the NSA were hoarding) and yields the plain text with ease

[Anonymous Coward]

Re: Possible deadly flaw - compromised software

@AC "Sure, also in MacOS, iOS, Android, ChromeOS, any Linux distro and application from a US company you didn't compile yourself after checking the code..."

Sucks, that.

Just remember though, the f.i.v.e. eyes is a part of the n.i.n.e. eyes, and the n.i.n.e. eyes are also a part of the f.o.u.r.t.e.e.n. eyes.

Keep an eye on what goes in and out of _your_ network - a good place to start...

[Anonymous Coward]

Re: Possible deadly flaw - compromised software

Nobbled random number generation isn't a flaw in the algorithm but in its implementation/operation, much in the same way that current crypto methods have been weakened through poor implementation/operation (e.g. Debian/OpenSSL in 2008). So nothing new in your comment about an article that is defining a new approach to addressing the issue of integer factorisation by quantum computers. That said, crypto implementation/operation should be at the forefront of anyone's mind who has to ensure security.

[Cem Ayin]

Re: Possible deadly flaw - compromised software

"For a closed source implementation (eq most Windows programs) there is a danger that a deliberately weakened random number generator is used."

The very same problem exists for FOSS-code, even assuming it has been thoroughly audited. Consult the search engine of your least mistrust about "Reflections on Trusting Trust". As for the countermeasure proposed by Wheeler I'm not sure about its practicality in real life, given the various nondeterministic bits of compiler output; in any case it is (A) a rather involved procedure and (B) it would miss trusting-trust-style attacks targeting other system binaries or those performed at the firm- or hardware level.

[Adam 1]

Re: Possible deadly flaw - compromised software

> For a closed source implementation (eq most Windows programs) there is a danger that a deliberately weakened random number generator is used.

It isn't just closed source with that risk by the way. The fact that such a vulnerability sat there compromising every generated random number on Debian for so many years* without anyone noticing is testament to that. It's also a pretty damn good lesson in 'comment your code if you're doing something that looks a bit unusual'. A simple explanatory comment would have stopped the 2008 'fix' being implemented.

* I don't personally believe this vulnerability was deliberately introduced.

[Anonymous Coward]

Not just to protect stored communications

It takes a long time for software to be updated, especially in embedded devices. Some may never be updated. How much stuff out there is still using vulnerable OpenSSL implementations, for example? If you want systems designed in 2018 to be safe when they're still running in 2028, you need to protect against the capabilities your adversaries may have in 2028.

[Sorry that handle is already taken.]

Re: Not just to protect stored communications

And also if you want your encrypted private correspondence from 2018 to remain private come 2028...

[Ian Michael Gumby]

@DougS Re: Not just to protect stored communications

Actually no.

First, if you're storing data in an encrypted format, you need to be able to decrypt the data for use. So you would be better off decrypting and then encrypting the data over time with newer methods.

Keep in mind that there's a cost to the decrypting that you incur when you want to use the data. ;-)

At the same time... the data will lose value over time.

Think about this... 70+ years after WW II, what is the operational value of deciphering the Japanese or German codes?

Encryption should be strong enough to protect the data as long as the value of the data exceeds the cost of the encryption. Keep in mind that you will also have protections around the data which reduces access to the data in the first place.

[Anonymous Coward]

Re: @DougS Not just to protect stored communications

How can you decrypt and re-encrypt over time if you aren't updating the system that uses the old encryption? My whole point about designing it for 2028 is "what happens if in 2028 you are still using something you bought in 2018 and has not been updated for a long time or maybe never".

You'd rather be using encryption that is still secure (or has the best odds of still being secure) in 2028, than something that is fine for classical computers but will be broken by quantum computers.

[amanfromMars 1]

And Now ....... Exotic Erotic Emanations for and from Global Operating Devices

Secret message received, decoded and fully understood, RC. The Available Virtually Impregnable Force is now at least squared for Supply of Energies with Alien Powers into Great Games Plays to XSSXXXX :-)

Nice to see El Reg leading herds rather than just following up on packs and reporting on pacts and feeble acts.

Evolutionary Revolutionary Progress ...... but not as Systems Admins were expecting it with AI and IT in Creative Command and Cyber Control of Computers and Communications?!.

[amanfromMars 1]

Re: And Now ....... Exotic Erotic Emanations for and from Global Operating Devices

And here is indisputable news of leading serial losers not currently au fait with Alien Sources with Virtually Available Impregnable Forces to XSSXXXX? ..... http://www.zerohedge.com/news/2017-07-19/us-military-establishment-study-admits-american-empire-collapsing

Or are you as an ostrich and in an arrogant and ignorant state of denial?

[John Smith 19]

Neat idea. Obviously depends on the qualtiy of the "random" generator

But side steps the problem of distributing the one time pad.

That's always the trouble, since you can't use the medium for distribution as it's already compromised.

I suspect more work is needed, but it sounds like a start, if you want your privacy to be protected in the long term.

For privacy purposes the real issue remains the routing data, and how to encrypt that, but I have no idea how to make that work.

[Anonymous Coward]

Re: Neat idea. Obviously depends on the qualtiy of the "random" generator

Public/private key mixing seems to overcome this. And there seem to be methods available mathematically that are hard to compute both normally/generally and with quantum computing

Quantum computers are not magic, just use a different type of method to attack a mathematical problem. They are really slow at some types of problems/searches. So you could slow them down, though as with any encryption, if it can be made, it can be unmade. :P

[Ian Michael Gumby]

@Technical Ben Re: Neat idea. Obviously depends on the qualtiy of the "random" generator

Exactly.

So you generate your one time use pub/pri key (Assume a reasonable length of 8096 bits ) and then use that to wrap around the shared secret.

The spy would have to capture all packets being sent in the stream and then try to break the decryption by first finding the initial pub/pri key and then trying to determine the shared secret.

Now if you have a rolling encryption where the shared secret changes frequently... or rather frequent enough... your messages will be very, very difficult to crack and it couldn't happen in subjective real time.

So you can encrypt streams well enough that current and next gen(s) quantum computers could not easily crack your stuff.

[David Roberts]

Public key?

Isn't one of the main features of a public key that it is globally visible and so can be authenticated by a trusted global resource such as a signed certificate?

This seems to be using asymetric key pairs but there is no mention of how each end authenticates the identity of the other.

Unless one half of the asymetric key pair is encrypted using non quantum existing technology?

[Anonymous Coward]

Re: Public key?

Hi David

The IKE_SA_INIT exchange is quantum resistant (using the QSKE). This is the 1st handshake. The second handshake (IKE_AUTH) is the authentication exchange. IKE_AUTH will generally use digital signatures (PKI) for scalability, but can use a pre-shared-key or even EAP.

As the IKE_AUTH exchange checks attributes from the IKE_SA_INIT, if someone can break the IKE_SA_INIT then they could also break the IKE_AUTH. Hence we can assume that this is secure.

Hope that helps

[John Mangan]

I've got a question..

.. and this seems like a good place to ask it with the assembled knowledge.

I've often wondered how a computer cracking an encrypted message knows it has been successful. I mean if a human decrypted a message that said 'Meet next Tuesday at 4:00" then they will recognise that as valid English and conclude that the decryption has been successful. Similarly a human may recognise map co-ordinates or German or whatever. But how does a computer 'know'? And if someone has used ROT13 before employed the full brute force of AES-256 how would the computer recognise the decrypted text as correct?

Anyone know.

[Anonymous Coward]

Re: I've got a question..

Hi John

For this draft it's protecting IPsec, so generally ESP traffic. This will have a known header (check RFC4303) and an inner payload. So you try your brute force and if you decrypt the 1st few bytes of the payload and it looks like something known (e.g GRE/IP header traffic), you're cooking.

For AES-256 the sun will probably burn out prior to you getting lucky :-)

[Anonymous Coward]

Re: I've got a question..

Correlation I guess. While any data set can be translated to any other, there is only one way to translate it to a specific data set. When your one specific way matches twice, or more to a "valid" result, then correlation strongly suggests you have found the key.

So, if you decrypt "egg" in one message "bacon" in the next and "sandwich" in the third, good chance it's right, and someone just ordered an egg and bacon sandwich. But if you get "egg" in one "panda" in the second and "dfjiovdjodvjio" in the third, well, it's probably not right... or a very intelligent panda wanting egg sandwiches just sneezed while typing.

[John Mangan]

Re: I've got a question..

I can see that's how a human would do it but it doesn't seem so clear how a computer would, with no a priori knowledge of the contents, manage that correlation.

[ated19]

single use pub/pri key

The concept is to generate a single use pub/pri key as the initial wrapper for the counter party to send you a random secret.