Schneier on Security

Clive Robinson • July 7, 2022 2:03 AM

@ Jedward, SpaceLifeForm, ALL,

Why do we need a quantum resistant algorithm?

It is “algorithms” plural not singular.

But importantly it’s ONLY to replace those algorithms that are based on what are currently ASSUMED to be hard mathmatical problems of factoring large numbers and finding the discrete logarithms logarithm. Some of these effected algorithms are DH, RSA, DSA, and ECDH which often get lumped under “asymetric algorithms” that are also used in “Public Key” systems.

For “key negotiation” or “key transfer” for traditional “block ciphers” like AES. Also “Digital Signitures” the most common but mostly unseen use for is “code signing” of “Patches and updates” to fix security vulnerabilities in existing code bases. Also increasingly to “Secure the Digital Supply Chain” which is rife with proven classes of critical vulnarabilities.

The problem is that a new assumption came along in the mid 1980’s when it was theoreticaly proved that there were “Quantum Algorithms” in existance that would make an exponential increase in certain types of computing. This was done by Physist David Deutsch FRS, from Oxford University in the UK.

His pioneering work founded the field of quantum computation, by his formulating not just a description for a quantum Turing machine, but as well as specifying an algorithm designed to run on a quantum computer that would make that exponential speed up.

So just under fourty years ago an assumption became “theoreticaly possible” with the only assumption left being “Could it be made practically possible?”.

But… there was an issue then that still exists today, which is “Quantum Computers”(QC) are no faster than Classical Computers”(CC) in many general purpose algorithms.

Which begs the question,

“So why even build Quantum Computers?”

Well you could say it was Netscape’s fault. They came along and took the ideas of the RSA public key algorithm and built the prototype “Secure HTTP” which we now know as “https://…” or SSL. Which enabled the nascent Internet and curiosity upon it that was the “World Wide Web”(W3) to be able to handle financial transactions securely. Thus turning W3 into a “Market Place” for every crook, shyster, banker, financier, and psychopath with any ability, to fill the “old bottles” of existing crimes with the “new wine” of fast flowing money across international borders and out of a legal jurisdiction thus make them not prosecutable. Yup “Home Banking” in the late 1990’s was “crime central”… Later, traditional purchasing markets developed with the likes of Amazon getting in to take “The first to market takes all” prize.

SSL was now the integeral part of billions of transactions and it was theoretically very vulnerable to “Shor’s Algorithm” in it’s “Key Exchange/Transfer/Negotiation Mechanisms” but not in the data encryption algorithms that was only weakened by “Grover’s Algorithm”.

So the idea of QC for attacks against RSA and later “Eliptic Curve”(EC) became very very attractive to crooks, criminals and their bedfellows the SigInt and other “Intelligence Community”(IC).

But also to physicists and even biologists looking for Nobel prizes and mathmaticians looking for their equivalent…

So… if QC becomes practical then nearly all “consumer” used crypto becomes vulnerable (but traditional Diplomatic and Military crypto does not)

So people finally started getting twitchy and the idea of “Post-Quantum Cryptography”(PQC) came about. That is to find replacment algorithms to do “Key exchange” and “Digital Signing” without the underlying mathematical problems of “factorization” and “discrete logarithms”.

Because it is ASSUMED that it will be easy for future quantum computers to solve because of Shor’s algorithm, which renders existing Web Usage, and Code Signing unsafe because the RSA, DSA, DH, and ECDH algorithims within them would be unsafe should Quantum Computing become a practical reality.

All because we’ve not been able to solve “the secure channel” problem needed to establish a “root of trust” / “shared secret” underlying all cryptography used in the protection of information for the three most basic tasks,

1, Communications
2, Storage
3, Processing.

So on the assumption that Quantum Computing and the algorithms we have come up with so far will not be the end of the trail, this PQC issue will be gone through again in the not to distant future, maybe only a quater to half a century at most.

With regards,

I thought ot was said somewhere that existing algorithms were resistant to quantum decryption for any reasonable time frame.

Resistant but not immune, Grover’s Algorithm does effect symetric crypto like block ciphers, but not to anywhere near the effect Shor’s Algorithm has on asymetric algorithms based on “factorization” and “discrete logarithms”.

But… mankind is an inquisitive and inventive omnivore and we beaver on at a quite alarming rate. Neither Shor’s or Grover’s algorithms are the “Be all and end all” of QC algorithms, so all we can realy say is,

“Keep a weather eye on this space”

Because a lot of current PQC ideas and algorithms are based on lattice systems, and there were one or two quite alarming shocks came up in NIST PQC event, which might be why there is no “One Ring” contender in sight.

I hope that helps a little.

Clive Robinson • July 7, 2022 2:34 PM

@ Winter,

“As Gert-Jan already explained, quantum computing is coming, in a decade, or two decades, and changing the cryptographic infrastructure takes time, a lot of time. Also, everything that is communicated today is stored wholesale for later decryption.”

Three statments.

Whilst the last is mostly true for digital consumer communications operated by “the voters” in some parts of the world, other communications are not recorded.

Also not all parts of the world poses the equipment to store these communications… As I occasionaly point out things only happen “If the laws of physics alow”. But… We should also note “If the excess resources are available” etc.

This does however leave quite a lot of “Wriggle Room” for the thoughtful or inventive mind. Even what feels like the most oppressive surveillance is not omnipotent or omnipresent.

The second point of all “things take time” is one of those universal constants with what often feels like near infinite variability. Thus the “How long is a piece of string?” question, that is more frequently an expression of exasperation.

But the first statment that “quantum computing is coming” at any time let alone within two decades, is shall we say “open” so is currently an assumption.

We know there are things that “theory allows” but “practically disdains”. Such as the ability to travel at the speed of light, we know the minimum energy required but currently not how to atain or control it for realistic masses in human terms.

To be realistic we have to acknowledge that whilst quantum computing is possible at a small scale, the ability to scale it to useful levels may well be constrained by limits we can not currently cross or may ever be able to.

To see why this might be, consider the issue of “Signal to Noise” at some point the signal level becomes comparable to the mean level of noise in any specified bandwidth. At this point the signal level is of the same magnitude and sumed with what is very probably “random” noise. The signal is effectively indeterminate at this point, to recover it requires a change in the ratio of signal to noise which usually carries penalties such as decreasing bandwidth in some way, often requiring an exponential rise in difficulty, time or both.

Thus the question arises of if attacks on cryptographic systems will be even close to practical beyond “toy” systems not just with the technology we currebtly posses but technology that we can build.

So a second question arises of “Are we throwing the baby out with the bath water”. That is chucking away what we currently have in exchange for something untested and having what are hidden weaknesses (rainbow).

Thus using both in hybrid systems not one or the other would be prudent behaviour…

It’s certainly the way I would consider moving in prefrence to the either or option.

Clive Robinson • July 8, 2022 6:59 AM

@ SpaceLifeForm,

Maybe the scam to come will be marketing PQC compatible routers.

And much else besides… Should we ask that eternal question,

“Is PQC the new IoT?”

With regards,

Explain to me why the network kit should even know what TLS algorithm is being used (pre or post quantum) and why should it even care?

That is a “Draw up a chair and get comfy” question.

As I’ve mentioned before there is a line at one end “basic components” at the other “complex systems”. At the basic component end you have “zero security” at the complex systems end “high level security” (but not 100% security).

But, that line usefull as it is, has another associated with security which is “cost” in terms of resources used or being used.

Thus “security” is a composite of multiple constituent parts that effectively interreact, in different ways at different times.

The logical conclusion is that “security” is not innate but a construct that has to be built into systems, importantly that the systems have to be beyond a certain degree of complexity and resources to give security.

That is each bar of a cage does not offer security, nor do all the bars required to build a cage give security. It is only when the bars are held in a complex pattern is the cage formed as a system, that then gives security.

So “no” no base component parts need have knowledge of security, but at some point when the system they are built into reaches an appropriate level of complexity does security become meaningfull.

Clive Robinson • July 9, 2022 8:11 AM

@ Winter, SpaceLifeForm, ALL,

Look for repeating three letter combinations…

You could but take a look agian at,

SL = 1f0c100c6310150d
CR = 002037342f202020

The first CR is 00 which means it is the same letter and case as in the –supposadly– unknown SL.

But then you see four 20 which means the letters are the same but the case is different.

So five of eight pieces known in some way simply due to ASCII structure.

But what does that gain you?

Well, if you assume that the 12—345 are the same letter in each word a fast unix commandline search on a dictionary list will probably give you a very very short list of matching pattern words.

But can you learn more from,

37342f

The answer is of course yes.

They are all over 20 which means they are of different cases. Most probbally lower case in the second word. So a quick conversion by subbing 20 gives,

17 14 0f

And a conversion to decimal

23 20 15

Gives you a spacing within the alphabet between the coresponding letters in the words.

At which point you have very probably found the two words without being given the hint @SLF gave…

As they used to say in the UK insurance advert,

“Simples”

You could have used similar knowledge to break the other two words or having got the third fast back to them.

There are reasons why you should never send “true plaintext” or “probable plaintext” under a One Time Pad, because from a practical perspective you badly break the “equiprobable” rule which is the OTP’s only strength.

Remember it’s not only KeyText that has statistics such as unicity distance, but so does “plaintext” that has not had it’s “statistics flattened”.

As demonstrated above you do not need to know the KeyText to break OTPs that are not used correctly.

Essentially this is what they did with project VENONA.

Clive Robinson • July 10, 2022 4:57 AM

@ SpaceLifeForm, ALL,

Historically the two basic encryption steps were,

1, Substitution
2, Permutation

The idea being with substitution you could change the very basic “known” letters to “unknown” letters. However as in the Enigma “Plug Board” if employed in a static way across any body of text it’s security is minimal as “counting letter frequency” gives the translation table away very quickly.

Likewise with permutation the idea being to break up contact frequency thus change the sparce bigrams and trigram frequencies. Whilst harder to come up with a translation table over a body of text when used invariently fairly trivial methods were known.

The idea in the early 20th century was to do simple substitution and permutation as a pair of operations over and over such that things were not invariant across a body of text thus the complexity built up with each application.

In essence this is what you are describing.

However there is a form of “stream cipher” sometimes called a “book cipher” where the “key stream” is infact a “text stream” read out from the book from an agreed starting position.

In essence such a book code is not a plaintext mixed with a random keystream like an OTP, but two plaintexts mixed.

This is the same result you get from using an OTP twice, by mixing the two ciphertext streams, the keystream gets nulled out and all you are left with is two mixed plaintexts for which there are known methods of attack.

That said, I know that as recently as back in the early 1980’s, it was felt by some that you could improve the keystream generated by mixing four textstreams together.

Two basic methods were implied…

The first being four entirely seperate and unrelated book textstreams, preferably not even in the same language. This had usage issues needing four agreed start points and considerably increased risk of error jumping from book to book. But also Operational Security (OpSec) issues of carrying four sufficiently large books around is not “normal behaviour” even for “traveling salesmen”.

The second was in effect a “lagged Fibonacci Generator” solution, where by you used a single book textstream and selected four characters at fixed offsets with regards to each other as you incremented the start point.

So using the paragraph above with lag points of 1,2,3,5 we would get the fitst three keystream characters as the mixes of,

{Thee}
{hesc}
{eseo}

From which it can be seen that there is a “low pass filter” or “integrator” issue. Yes it flattens the statistics, but in reality the change is small.

In fact to see why this can be such a bad idea, there is a fast averaging algorithm, where you only do one subtract, one add to a running count and increment a pointer in a circular buffer.

So with a buffer [ABCDE],

On “New” input,

1, Inc pointer P (to point at A)
2, RunCount = RunCount – P[A]
3, P[A] = New
4, RunCount = RunCount + P[A]
5, Output = RunCount

From examination it quickly becomes clear,

1, How to implement a fast low tap count Fibonacci generator.
2, How little things change in each output.
3, Increasing the number of taps does not realy change very much (as only one value in the circular buffer changes at any time).

The lessons being that using a Lagged Fibonacci Generator has to be done with care and adding more taps reduces the potential change % at each step to in effect 1/n where n is the number of changing taps.

But what does this have to do with “compression” well, rather than look at the absolute output values of the Lagged Fibonacci Generator look at them as output to output differences or “deltas” it’s not difficult to see that the averaging process reduces the maximum change range for each delta down. Thus it acts like a compressor of the sort often found in CODECs and similar.

Which means the alleged entropy in the keystream is reduced and can be considerably so if that tap points used are not selected with care. The same is true of all compression it reduces the “key search space” at each step.

So whilst compression is usually “good on plaintext” as it flattens the statistics, it is “bad on keytext” as by flattening the statistics it reduces the key search space.

So… When you reuse a stream cipher key stream it cancels out, leaving two plaintext streams mixed together. If both are effectively compressed plaintext you can open up a whole can of worms you did not know was there because of the lowpass / integrating effect compression has.