[Cryptography] NSA looking for quantum-computing resistant encryption. How will encryption be affected by quantum computing

[ianG]

On 31/08/2015 15:41 pm, Erik Granger wrote:
> www.engadget.com/2015/08/30/nsa-quantum-resistant-encryption/
> <http://www.engadget.com/2015/08/30/nsa-quantum-resistant-encryption/>
>
> I read this article and as a non-expert in quantum computing, I'm
> wondering what sort of impact quantum computing will have on our
> encryption. Will it just make brute forcing easier, thus requiring
> certificates to have a shorter shelf life? Or is it something more
> worrying? Less worrying?



Here's my summary of the facts & conclusions (?) so far.  As always 
looking for correction.



1.  NSA has mandate to protect USG agencies.  It also has a mission to 
breach everyone (else) but let's ignore that for the moment.

2.  NSA knows more about quantum than anyone else, in the sense that it 
has the budget to know, and has been spending that budget.

3.  (we suspect/agree) NSA is worried about quantum.

4.  NSA guidelines protect out to a 25 years (h/t to Ryan).  So if NSA 
can't rule out a quantum attack in the 25 year++ horizon, then they have 
to protect against a quantum attack.

5.  Current rule of thumb is that a quantum attack reduces the 
bit-strength of an algorithm by the square-root - much like a birthday 
attack.

6.  So in short, take previous minimum strengths (128 baseline, etc) and 
double (to baseline 256, etc).



Commentary,  So, what does this mean for everyone else?  Not a lot.

The reason it doesn't matter is this:  WYTM?  The NSA is mandated to 
protect US government agencies and not the rest of the world.  Following 
the normal approach to threat modelling, they built their list of 
threats, not your list of threats [0].

Their list of threats include a very well funded Chinese / Russian 
attack.  E.g., state of the art, monster-grade quantum supercomputer 
with a billion dollar price tag.  Which is only going to be used against 
the juciest of targets - the USA.  Let's call this the Bletchley Park 
Attack (h/t to Tom).

Our list of threats doesn't include that computer or that government. 
Because, if any government wants our data, they'll spend $1000 to hire a 
local thief, not $1000000000 to deploy their monster machine on mere 
civilians [1].

The NSA, by its own methodology and logic and customer, cannot afford to 
be wrong on this.  Everyone else can afford to wait, and we can also 
afford to be wrong.  Wait and see.  When ordinary people (botnet 
operators) can buy quantum computers that can crack keys, we'll know 
about it.

That's not to say that people won't upgrade.  All the other governments 
and supra-national orgs like IETF will fall into line with NSA's threat 
model because their approach is best practices, not security modelling.

But there's no need, there's no hurry, and if you spend a dime on it, 
you wasted that dime, and the opportunity to spend it on your real threats.



iang



[0] the key flaw in our reasoning is quite old:  using someone else's 
threat model and not realising it's wrong for you.  A common failing. 
Obligatory old post asking, What's your Threat Model?
http://iang.org/ssl/wytm.html

[1] XKCD on Security is a better reference https://xkcd.com/538/