-2
$\begingroup$

We already have quantum computing, but when quantum computing becomes commercially available there is a problem for many but not all encryption algorithm.

The One-Time-Pad or OTP is the one and only true mathematical unbreakable encryption scheme because it provides entropic security. The question is if OTP will provide protection when a quantum computer is used to do cryptanalysis.

Let’s look into this example:

AES256 is still considered to be unbroken. Although there are attacks against AES, like the biclique attack, it is still considered hard enough. Biclique does not immediately melt away AES. The problem with AES is more in usage. For instance, creating a key and never change it for years or use a key generating protocol that makes keys predictable. If someone would generate a key from a time string, this would result in a dreadful situation where theoretical security is very high but practical security is broken. In normal life, this happens all the time. So not the algorithm it self is broken but the circumstances where it was used in. OTP could protect against these cases because it is using a new unique cipher stream for each message. The key cannot leak because there is simply no key. The structure cannot be broken because there is simply no structure.

Now let’s look into the properties and conditions of OTP. I will split some obvious conditions to deal with them separately. Let’s call them the Ox-Conditions for short:

Condition 1: The key stream must be truly random.
Condition 2: The random key stream should be free of anomalies 
Condition 3: The random key stream must be unpredictable.
Condition 4: The key distribution must be proven secure
Condition 5: If any deterministic algorithm is used, it should not be possible to influence the output.

Condition 1 means you must have a True Number Generator (TRNG). That sounds more difficult than it is in fact. You could build one using light, heath, or a semiconductor that will produce certified noise but it will never be NIST certified. (But that is obviously not what you want) If it is truly random, or not, can be measured and certified.

If you have certified noise you are still not done. It’s random, anything can happen. On a very bad day, you could have a cipher stream like ”00 00 00 00 00 FF FF FF FF FF” just by sheer coincidence. That could ruin your secrecy, your day and even your life if you are a spy depending on it. Condition 2 states that you must monitor anomalies and if that happens and handle it.

Condition 3 is even more important than condition 1 and 2. You could have perfect random noise certified and with a golden label on it but if it is still predictable it will blast your security into oblivion. This happens for instance when “perfect noise” is looped. Gambling machines in Casino’s use this trick. Some gambling machines have been cracked because a smart guy found out about the loop in the random pattern. You should always generate your own random keystream. No one should give it to you. The Google number generator or ERNIE may be producing certified random noise for sure, but who gets which random noise? If random noise is known by a second party, it is predictable and this leads to a full security compromise. Remember that it is always your noise and your noise only.

Condition 4 is where the real trouble begins. Large quantities of keystream data must securely be distributed to the client who than deciphers the message. It is possible to build an application with 1Gb of pre-shared keystream data but it is highly impractical. We have the holy grail of quantum resistance but it is not used because of this very unpractical condition. This is the major disadvantage the perfect OTP has.

Now we are talking about the real problem.

Because condition 4 is so impractical, software developers use something that is called: “scaled entropy”. And that is where all trouble starts. If I have a function f(x) that has a very chaotic behavior like elliptic curves, I could turn the chaotic result into a hash and use that hash as a keystream. The value x is then producing a large bunch of “noise”. The key value of x must be shared with the client and he gets the same noise and can decrypt the message. Of course, this is far from any real random generator and violating condition 1. The value x could be 256-bit key. It will produce a matrix of noise in a deterministic way and cryptanalysis might not even be able to detect any flaws in it. But besides condition 1 it also fails condition 3, it is predictable because an attacker might have a clue on what input values are used and when. FinalCrypt likely does something similar. I have no clue how they generate random noise but it is probably a function.

If new noise for OTP keystream data is sent by quantum entanglement to both participants, it would pass condition 4. This is not a very practical nor very cost-effective way at all since equipment to generate entangled particles requires Lithium niobate and highly sophisticated equipment. But I can assure you that OTP will be used in exactly this way in the near future when this will be commercially available because the power of OTP is irreplaceable.

Now we come to condition 5. If 2 participants want to use OTP and need to have the same keystream, they need to have something deterministic that produces the same keystream. Two synchronized real number of generators would be best. But since God alone plays with entropy, this is not something we could easily establish….. A function is the next best thing most people can come up with. NSA’s elliptic curve based “random” generator cheerfully fails condition 5 like all other pseudo number generators. Luckily crypto community understands this and won’t tolerate this again.

The availability of OTP is of great importance for our future. Because without OTP we are back at AES. There is nothing wrong with AES itself, but there is something wrong with keeping an AES key for some time. Hardware could leak parts of this key by use of a side channel. Then the strong AES encryption becomes weak to be cracked. Please understand that these side channels are undetectable and that is exactly why people fear using the Huawei equipment. Think of a very well hidden side channel by swapping IP packets in a specific order or by introducing transmission errors that will be corrected anyway by CRC mechanisms. This is the power of OTP. Hardware side channels become futile.

For this reason, it is important that we construct algorithms that meet condition 5. The primary question asked here is:

Will OTP provide quantum resistance under 5 conditions? And what algorithm can be used to meet condition 5?

================= UPDATE =======================

Thank you for all answers in the first place! Here a small update:

If condition 5 is met, then it is a stream cipher, not OTP. This question has been asked exactly for this reason on this forum.

Many have been thinking about this question for a long time. If a stream cipher excludes OTP, then products like FinalCrypt (see finalcrypt.org) would not exist. What Finalcrypt seems to do is to use some kind of stream cipher (or block cipher). But it is using random noise for each single file you encrypt. Yes, that also means that you have the same size of key stream data as encrypted files. So is it both, a stream cipher and OTP? According to Finalcrypt: yes. Would it obey or break condition 5? That is hard to tell because it is not clear how the cipher stream is created.

I don’t want to zoom in on this product. I want the theoretical discussion. Can there be a source of noise that is random and endless? And can this same key stream be used at both communication participants? This cannot be a function for obvious reasons. And it can not be a pseudo number generator.

This question is surprisingly difficult and requires out of the box thinking because many implementations do not meet condition 5 or 3. But does this disqualify them all? A wrong example is the NSA number generator that has a know elliptic curve with know points P and Q. (my favorite explanation here) This breaks condition 5 and also 3. This method, and all others like it, do NOT stand the test. If there is a method it should be indisputable clear that all conditions are met. Tamper free and beyond any doubt.

It might be possible that that these is no mathematical solution to it but may be a combined physical / mathematical solution or even more disciplines. Before asking this question, quite some investigation was done. I’m not expecting an of the shelf answer but I will respect everyone’s answer.

$\endgroup$
3
  • 5
    $\begingroup$ Condition 5 means you are not using OTP $\endgroup$
    – bmm6o
    Aug 14 '20 at 0:40
  • $\begingroup$ I think your question is about whether stream ciphers are/can be quantum resistant, but there's so much more in here it's hard to tell. Are AES, NIST, Huawei, NSA, etc, really relevant to the question? $\endgroup$
    – bmm6o
    Aug 14 '20 at 15:55
  • $\begingroup$ Interesting. Condition 5 is not directly excluding OTC. Many others have been contemplating to get that fitted. If you have any idea how this could work, please share your thoughts. $\endgroup$
    – Ox-Fox
    Sep 4 '20 at 20:50
7
$\begingroup$

That sounds more difficult than it is in fact. You could build one using light, heath, or a semiconductor that will produce certified noise but it will never be NIST certified. (But that is obviously not what you want) If it is truly random, or not, can be measured and certified.

Having a "true random number generator" from just hardware is actually very hard, usually, some kind of whitening needs to be applied at the very least. Otherwise, there may be a lot of entropy in your random numbers, but the distribution may well be off.

Even NIST doesn't specify methods to certify TRNGs.

On a very bad day you could have a cipher stream like ”00 00 00 00 00 FF FF FF FF FF” just by sheer coincidence. That could ruin your secrecy.

That's 80 bits of data, and there are a lot of patterns that "don't look random". Fishing those out is pretty tricky, and if the ciphertext doesn't look random, then the attacker still has to guess why this is the case. Monitoring the RNG is of course a good idea, but this kind of pattern matching is probably not.

But I can assure you that OTP will be used on exactly this way in the near future when this will be commercially available because the power of OTP is irreplaceable.

I don't think this is the case. Currently, symmetric-key cryptography seems strong enough to withstand QC. The real problem is with key management for symmetric cryptography. Quantum entanglement seems to only make this part harder.

Calling OTP "irreplaceable" is of course bunk - we're currently using a lot of cryptography without perfect security and we're getting along fine thank you.

If 2 participants want to use OTP and need to have the same keystream, they need to have something deterministic that produces the same keystream. Two synchronized real numbers of generators would be best.

You are simply describing a stream cipher. Nothing more, nothing less.

Please understand that these side channels are undetectable and that is exactly why people fear using the Huawei equipment.

This is an unsubstantiated claim that has nothing to do with your question.

Will OTP provide quantum resistance under 5 conditions? And what algorithm can be used to meet condition 5?

No, because you are not describing an OTP at all, you're describing a stream cipher. Many stream ciphers are considered secure, but others are not even when facing classical-cryptanalysis (RC4, A5/1, etc.). Many others that are considered secure in a classical are expected to only face Grover's algorithm. In that case, a 256-bit key will still provide 128-bit security (in the worst-case scenario).

An OTP, as a theoretical construct, remains secure. QC cannot undo perfect security. If it could, it would not be perfect.

$\endgroup$
1
  • $\begingroup$ thank you for answering. Pattern matching or filtering is not the intention of condition 2. It is more monitoring of the frequency distribution and variance. It is interesting to see that very odd cases happen from time to time. The noise is discarded in that case. $\endgroup$
    – Ox-Fox
    Aug 17 '20 at 12:25
2
$\begingroup$

As explained in comment and the other answer, "If any deterministic algorithm is used" as in the question's condition 5, then the cryptosystem is not a One Time Pad, it is a cipher; a stream cipher if the encryption is by XOR with a keystream independent of the plaintext.

And when we use a cipher, we loose the unconditional security of the OTP. That's facing both classical and quantum computers.

The question is tagged AES, and I'll assume a stream cipher based on AES, such as AES-CTR. When correctly implemented, that's believed resistant against classical computers with a security level equal to the key width (128, 192 or 256-bit), when the amount of ciphertext remain well below the square root of the number of possible blocks, that is $\sqrt{2^{128}}=2^{64}$ blocks (thus many exbibytes).

Resistance to hypothetical quantum computers usable for cryptanalysis (Cryptographically Relevant Quantum Computer in NSA terminology) may require sticking to the higher key size, 256-bit, because Grover's algorithm could allow breaking $n$-bit crypto with $2^{n/2}$ effort.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.