[Cryptography] A thought about backdoors and quantuum-resistant encryption

Phillip Hallam-Baker phill at hallambaker.com
Fri Aug 28 14:28:47 EDT 2015


On Fri, Aug 28, 2015 at 1:04 PM, Theodore Ts'o <tytso at mit.edu> wrote:

> I don't know if this is possible, because I don't know enough about
> quantuum computing, and I don't know enough a about "quantuum
> resistant encryption".
>
> Suppose quantuum computing is a thing, and suppose NSA^H^H^H NIST
> supplies us with a quantuum-resistant encryption algorithm.  Would it
> be possible to create an encryption algorithm which is resistant to
> quantuum computing --- except for someone with a quantuum computer
> *AND* knowledge of some secret quantuum state stored in a quantuum
> computer only available to the NSA.
>
> Even more, would it be possible to create such a thing in such a way
> that NSA^H^H^H NIST could introduce non-transparently in such a way
> that the public world *thinks* that that the encryption algorithm
> against all quantuum computers, but in fact there is a trapdoor that
> only the NSA could utilize --- but no one knows this?
>
> Of course, people wouldn't have to use the new quantuum resistant
> encryption algorithms, but if quantuum computer were a thing, they
> would be screwed if they kept on using AES, so the NSA would be quite
> happy with that outcome.
>
> And of course, if it was introduced non-transparently, then China and
> Russia and Iran would be able to demand that a backdoor be engineered
> for them, because no one would know that the backdoor existed.  And if
> someone future Snowden leaks this, all of the current fear-mongering
> from James Comey and Keith Alexander would help prepare the ground in
> case it does leak.  (Or maybe they plan to introduce this
> transparently, if they've learned their lesson from the Snowden
> disclosures.)
>
> All of this is premised by the hypothesis that it is possible to
> create quantuum-resistant encryption system for everyone but NSA, and
> preferably (for the NSA) in such a way that it's not possible to
> modify the encryption system so that backdoor can't be removed or
> changed so that China and Russia could have their own
> quantuum-backdoored encryption algorithm, and force companies who want
> to do business in those countries to use their alternate-backdoored
> encryption.   Is this possible?
>

It is certainly possible to design a protocol that has effective
countermeasures to prevent this.

Consider the problem from the attacker's point of view. A public key
encryption scheme has three sets of parameters:

Private Key  K
Public Key    P
Shared parameters. S

A crypto system is QM secure if someone with a quantum computer cannot
obtain the private key or decrypt messages using the Public key and shared
public parameters using a QC.

What you are suggesting here is a backdoor in the shared parameters such
that these are chosen so that the attacker has leverage but other users of
the system are not. In effect we have a second public key crypto system
built into the shared parameters and the attacker has generated these
shared parameters as some function of a master secret X so that S = f(X).

Call this type of system 'backdoor QM insecure'.

Note that X has to be sufficiently large that the system is still secure if
the attacker doesn't know it. Otherwise this isn't a cipher with a hidden
NSA backdoor, it is a cipher that has a set of weak keys that enable an
attack method known to the attacker and not anyone else.

Call this system 'unknown attack QM insecure'

While it is certainly possible to imagine that a function f(X) might exist,
it is fairly clear that from this point on, any and all parameters used in
any standard for public key cryptography must be rigid so that an attacker
cannot choose a set that provides them with a backdoor. MD4 introduced the
notion of using parameters taken from an arithmetic function (e, pi, etc).
The CFRG is looking at fast primes.


So yes there is a risk here but we already have an effective control: rigid
parameters.

According to my source, the relevant NSA doctrine is NOBUS 'nobody but us'.
So they might peddle an unknown attack QM insecure system like they did
with Dual_ECRNG, but unknown attack would leave US IT systems vulnerable to
attack by China, Russia, etc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150828/79292402/attachment.html>


More information about the cryptography mailing list