Thanks for the engagement and informative responses on this thread. I'd
like to help it remain constructive and informative.
My goal in surfacing this subject is to determine whether or not steps
should be taken to change the algorithms in use in popular cryptographic
products to avoid future compromise. In the course of this message, it
will become clear that I have no qualms with promotion of the practice
of encryption - it's a matter of whether we're promoting use of the
"right" encryption.
Language is important, and I've used the term "classical encryption"
incorrectly and imprecisely. As Maxim pointed out, venerable symmetric
key algorithms (one-time pads, shared secrets) deserve that attribution;
and as Matt Mackall pointed out, it's only crypto algorithms that rely
on integer factorization or discrete logarithms that are theoretically
known to be solvable in polynomial time by a sufficiently "large"
quantum computer (one with enough qubits to model the problem).
http://en.wikipedia.org/wiki/Symmetric-key_algorithm
http://en.wikipedia.org/wiki/Integer_factorization
So I'm just going to abandon that term altogether because it isn't
helpful :)
Implicit in this discussion is an assumption that quantum computers of
sufficient capability can be built, and as Maxim points out that's a big
assumption. Let's avoid getting bogged down here by acknowledging that
the challenges are, well, challenging - but progress has been made on
expanding the number of qubits, extending the distance over which
photons can be entangled, etc. To adapt a turn of phrase by Mr.
Assange, the physics and engineering seem to be smiling on the emergence
of quantum computation.
To further the conversation...
Matt stated:
Shor's algorithm for quantum factoring is a special case. With it,
future large quantum computers may some day be able to break today's
RSA and ECC, the two most popular schemes for public key encryption.
This is true, and outlines the concern it's my intent to document. We've
clarified that quantum computers won't be able to break all encryption.
But it will be able to break the most widely used public-key
algorithms. Here's some context from RSA's website:
http://www.rsa.com/rsalabs/node.asp?id=2222
The RSA system is currently used in a wide variety of products,
platforms, and industries around the world. It is found in many
commercial software products and is planned to be in many more. The
RSA algorithm is built into current operating systems by Microsoft,
Apple, Sun, and Novell. In hardware, the RSA algorithm can be found in
secure telephones, on Ethernet network cards, and on smart cards. In
addition, the algorithm is incorporated into all of the major
protocols for secure Internet communications, including S/MIME (see
Question 5.1.1), SSL (see Question 5.1.2), and S/WAN (see Question
5.1.3). It is also used internally in many institutions, including
branches of the U.S. government, major corporations, national
laboratories, and universities.
At the time of this publication, technology using the RSA algorithm is
licensed by over 700 companies. The estimated installed base of RSA
BSAFE encryption technologies is around 500 million. The majority of
these implementations include use of the RSA algorithm, making it by
far the most widely used public-key cryptosystem in the world.
Matt stated:
The biggest risk is that the secrets you encrypt today with SSL or GPG
might be decrypted by a very rich, patient adversary 20 to 50 years
from now. That risk exists with or without quantum computers and I
very much doubt the NSA and friends see enough code-breaking potential
in quantum computing to be putting serious effort into it.
By no means am I a dedicated researcher into this field, but a search on
"quantum computing NSA" turned up an article from October 2010:
http://www.afcea.org/content/?q=node/2407
...a host of U.S. government agencies is teamed with universities
across the country and internationally to crack the science code that
will make quantum computers viable. Participating federal
organizations include the National Security Agency (NSA), U.S. Army
Research Office (ARO), Defense Advanced Research Projects Agency,
Intelligence Advanced Research Projects Activity, Air Force Office of
Scientific Research, Office of Naval Research, Sandia National
Laboratories, the Department of Energy’s Los Alamos National
Laboratory and the National Institute of Standards and Technology (NIST).
...
[NSA technical director for quantum computing Barry] Barker echoes
that sentiment: “We started working in this field in the mid-1990s.
This was then a purely mathematical conception, and it’s now
progressed to a much more elaborate field of science. We aren’t the
only group to play a role in that, but we’re one of the groups, both
in funding research with universities over the years and doing some of
the research ourselves. We’ve played a substantial role in advancing
this field,” Barker says.
It's worth noting that Shor's Algorithm was first published in 1994.
http://arxiv.org/abs/quant-ph/9508027
Jacob stated:
If you have a specific passage where you feel that we state that
classical encryption is a panacea to the problem of mass surveillance,
I'd hope it is considered in the context of all the social discussion
that has almost nothing to do with cryptography per se.
(In any case, thanks for reading the book, I hope you enjoyed it!)
I very much enjoyed reading the book. It's a timely document, a
snapshot of the zeitgeist, a wide-ranging conversation amongst four
admirable, courageous souls from our time. I learned quite a bit and
have plenty of placemarks for further research, especially to expand my
understanding of the international dimensions of the challenges we
face. I wished I was there drinking whiskey with you, and who knows
maybe we'll get a chance to someday.
Nowhere in the text did any of the participants use the terms "panacea"
or the dreaded "classical encryption" - those are my literary
indiscretions. But the book title wouldn't be admirably resurrecting
the signifier "Cypherpunks" (again, with the literary indiscretions!) if
encryption weren't a primary theme.
So, here's an important quotation, one which I present while emphasizing
that the book is not in the least summarized by it:
...the universe, our physical universe, has that property that makes
it possible for an individual or a group of individuals to reliably,
automatically, even without knowing, encipher something, so that all
the resources and all the political will of the strongest superpower
on earth may not decipher it. And the paths of encipherment between
people can mesh together to create regions free from the coercive
force of the outer state. Free from mass interception. Free from
state control.
In this way, people can oppose their will to that of a fully mobilized
superpower and win. Encryption is an embodiment of the laws of
physics, and it does not listen to the bluster of states, even
transnational surveillance dystopias.
It isn't obvious that the world had to work this way. But somehow the
universe smiles on encryption.
Cryptography is the ultimate form of non-violent direct action.
While nuclear weapons states can exert unlimited violence over even
millions of individuals, strong cryptography means that a state, even
by exercising unlimited violence, cannot violate the intent of
individuals to keep secrets from them.
Strong cryptography can resist an unlimited application of violence.
No amount of coercive force will ever solve a math problem.
But could we take this strange fact about the world and build it up to
be a basic emancipatory building block for the independence of mankind
in the platonic realm of the internet? And as societies merged with
the internet could that liberty then be reflected back into physical
reality to redefine the state?
-- Julian Assange, from the introduction to _Cypherpunks: Freedom and
the Future of the Internet_, p. 5-6.
I think that's some great stuff, some crucial insights from hard-earned
experience - experience which we all must admit is rather unique in this
world. It's important. It's so important, that I'm going to insist
that we get it right.
So, to return to my concern - which I'll narrow even further: if we know
RSA is "the most widely used public-key cryptosystem in the world," and
we know RSA can be broken by a sufficiently large quantum computer using
Shor's Algorithm, and we know there is significant research and
development into building a sufficiently large quantum computer -
shouldn't we help shift dependence upon RSA through our advocacy for
popular encryption?
And if not now, when? Especially when one considers that every stored
RSA-encrypted ciphertext---and we have plenty of reasons to believe that
everything is being stored somewhere---becomes effectively transparent
when that last qubit hovers into place. Well, as soon as the quantum
priests translate the ciphertext onto quantum punch cards...
Let's advocate encryption---for all the reasons well stated by Assange
and company---but let's recommend the "right" encryption.
Now, WTF is "right"? Linguistic indiscretions are even worse :)
gf
--
Gregory Foster || [email protected]
@gregoryfoster <> http://entersection.com/
--
Unsubscribe, change to digest, or change password at:
https://mailman.stanford.edu/mailman/listinfo/liberationtech
