[146910] in cryptography@c2.net mail archive
[Cryptography] Scott Aaaronson: NSA: Possibly breaking US laws,
daemon@ATHENA.MIT.EDU (Eugen Leitl)
Mon Sep 9 09:13:05 2013
X-Original-To: cryptography@metzdowd.com
Date: Mon, 9 Sep 2013 14:40:10 +0200
From: Eugen Leitl <eugen@leitl.org>
To: cypherpunks@al-qaeda.net, info@postbiota.org, zs-p2p@zerostate.is,
cryptography@randombit.net, Cryptography List <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============1843739747380698912==
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature"; boundary="HAv5+T9jbwMPl6Kw"
Content-Disposition: inline
--HAv5+T9jbwMPl6Kw
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
http://www.scottaaronson.com/blog/?p=3D1517
NSA: Possibly breaking US laws, but still bound by laws of computational
complexity
Last week, I got an email from a journalist with the following inquiry. The
recent Snowden revelations, which made public for the first time the US
government=E2=80=99s =E2=80=9Cblack budget,=E2=80=9D contained the followin=
g enigmatic line from the
Director of National Intelligence: =E2=80=9CWe are investing in groundbreak=
ing
cryptanalytic capabilities to defeat adversarial cryptography and exploit
internet traffic.=E2=80=9D So, the journalist wanted to know, what could t=
hese
=E2=80=9Cgroundbreaking=E2=80=9D capabilities be? And in particular, was i=
t possible that
the NSA was buying quantum computers from D-Wave, and using them to run
Shor=E2=80=99s algorithm to break the RSA cryptosystem?
I replied that, yes, that=E2=80=99s =E2=80=9Cpossible,=E2=80=9D but only in=
the same sense that it=E2=80=99s
=E2=80=9Cpossible=E2=80=9D that the NSA is using the Easter Bunny for the s=
ame purpose. (For
one thing, D-Wave themselves have said repeatedly that they have no interest
in Shor=E2=80=99s algorithm or factoring. Admittedly, I guess that=E2=80=
=99s what D-Wave
would say, were they making deals with NSA on the sly! But it=E2=80=99s al=
so what
the Easter Bunny would say.) More generally, I said that if the open
scientific world=E2=80=99s understanding is anywhere close to correct, then=
quantum
computing might someday become a practical threat to cryptographic security,
but it isn=E2=80=99t one yet.
That, of course, raised the extremely interesting question of what
=E2=80=9Cgroundbreaking capabilities=E2=80=9D the Director of National Inte=
lligence was
referring to. I said my personal guess was that, with ~99% probability, he
meant various implementation vulnerabilities and side-channel attacks=E2=80=
=94the
sort of thing that we know has compromised deployed cryptosystems many times
in the past, but where it=E2=80=99s very easy to believe that the NSA is ah=
ead of the
open world. With ~1% probability, I guessed, the NSA made some sort of big
improvement in classical algorithms for factoring, discrete log, or other
number-theoretic problems. (I would=E2=80=99ve guessed even less than 1% p=
robability
for the latter, before the recent breakthrough by Joux solving discrete log
in fields of small characteristic in quasipolynomial time.)
Then, on Thursday, a big New York Times article appeared, based on 50,000 or
so documents that Snowden leaked to the Guardian and that still aren=E2=80=
=99t
public. (See also an important Guardian piece by security expert Bruce
Schneier, and accompanying Q&A.) While a lot remains vague, there might be
more public information right now about current NSA cryptanalytic
capabilities than there=E2=80=99s ever been.
So, how did my uninformed, armchair guesses fare? It=E2=80=99s only halfwa=
y into the
NYT article that we start getting some hints:
The files show that the agency is still stymied by some encryption, as Mr.
Snowden suggested in a question-and-answer session on The Guardian=E2=80=99=
s Web site
in June.
=E2=80=9CProperly implemented strong crypto systems are one of the few thin=
gs that
you can rely on,=E2=80=9D he said, though cautioning that the N.S.A. often =
bypasses
the encryption altogether by targeting the computers at one end or the other
and grabbing text before it is encrypted or after it is decrypted=E2=80=A6
Because strong encryption can be so effective, classified N.S.A. documents
make clear, the agency=E2=80=99s success depends on working with Internet c=
ompanies =E2=80=94
by getting their voluntary collaboration, forcing their cooperation with
court orders or surreptitiously stealing their encryption keys or altering
their software or hardware=E2=80=A6
Simultaneously, the N.S.A. has been deliberately weakening the international
encryption standards adopted by developers. One goal in the agency=E2=80=99=
s 2013
budget request was to =E2=80=9Cinfluence policies, standards and specificat=
ions for
commercial public key technologies,=E2=80=9D the most common encryption met=
hod.
Cryptographers have long suspected that the agency planted vulnerabilities =
in
a standard adopted in 2006 by the National Institute of Standards and
Technology and later by the International Organization for Standardization,
which has 163 countries as members.
Classified N.S.A. memos appear to confirm that the fatal weakness, discover=
ed
by two Microsoft cryptographers in 2007, was engineered by the agency. The
N.S.A. wrote the standard and aggressively pushed it on the international
group, privately calling the effort =E2=80=9Ca challenge in finesse.=E2=80=
=9D
So, in pointing to implementation vulnerabilities as the most likely
possibility for an NSA =E2=80=9Cbreakthrough,=E2=80=9D I might have actuall=
y erred a bit too
far on the side of technological interestingness. It seems that a large pa=
rt
of what the NSA has been doing has simply been strong-arming Internet
companies and standards bodies into giving it backdoors. To put it bluntly:
sure, if it wants to, the NSA can probably read your email. But that isn=
=E2=80=99t
mathematical cryptography=E2=80=99s fault=E2=80=94any more than it would be=
mathematical
crypto=E2=80=99s fault if goons broke into your house and carted away your =
laptop.
On the contrary, properly-implemented, backdoor-less strong crypto is
something that apparently scares the NSA enough that they go to some lengths
to keep it from being widely used.
I should add that, regardless of how NSA collects all the private informati=
on
it does=E2=80=94by =E2=80=9Cbeating crypto in a fair fight=E2=80=9D (!) or,=
more likely, by
exploiting backdoors that it itself installed=E2=80=94the mere fact that it=
collects
so much is of course unsettling enough from a civil-liberties perspective.
So I=E2=80=99m glad that the Snowden revelations have sparked a public deba=
te in the
US about how much surveillance we as a society want (i.e., =E2=80=9Cthe bal=
ance
between preventing 9/11 and preventing Orwell=E2=80=9D), what safeguards ar=
e in place
to prevent abuses, and whether those safeguards actually work. Such a publ=
ic
debate is essential if we=E2=80=99re serious about calling ourselves a demo=
cracy.
At the same time, to me, perhaps the most shocking feature of the Snowden
revelations is just how unshocking they=E2=80=99ve been. So far, I haven=
=E2=80=99t seen
anything that shows the extent of NSA=E2=80=99s surveillance to be greater =
than what
I would=E2=80=99ve considered plausible a priori. Indeed, the following co=
uld serve
as a one-sentence summary of what we=E2=80=99ve learned from Snowden:
Yes, the NSA is, in fact, doing the questionable things that anyone not
living in a cave had long assumed they were doing=E2=80=94that assumption b=
eing so
ingrained in nerd culture that countless jokes are based around it.
(Come to think of it, people living in caves might have been even more
certain that the NSA was doing those things. Maybe that=E2=80=99s why they=
moved to
caves.)
So, rather than dwelling on civil liberties, national security, yadda yadda
yadda, let me move on to discuss the implications of the Snowden revelations
for something that really matters: a 6-year-old storm in theoretical comput=
er
science=E2=80=99s academic teacup. As many readers of this blog might know=
, Neal
Koblitz=E2=80=94a respected mathematician and pioneer of elliptic curve cry=
ptography,
who (from numerous allusions in his writings) appears to have some
connections at the NSA=E2=80=94published a series of scathing articles, in =
the
Notices of the American Mathematical Society and elsewhere, attacking the
theoretical computer science approach to cryptography. Koblitz=E2=80=99s c=
riticisms
were varied and entertainingly-expressed: the computer scientists are too
sloppy, deadline-driven, self-promoting, and corporate-influenced; overly
trusting of so-called =E2=80=9Csecurity proofs=E2=80=9D (a term they should=
n=E2=80=99t even use,
given how many errors and exaggerated claims they make); absurdly overrelia=
nt
on asymptotic analysis; =E2=80=9Cbodacious=E2=80=9D in introducing dubious =
new hardness
assumptions that they then declare to be =E2=80=9Cstandard=E2=80=9D; and wo=
efully out of
touch with cryptographic realities. Koblitz seemed to suggest that, rather
than demanding the security reductions so beloved by theoretical computer
scientists, people would do better to rest the security of their
cryptosystems on two alternative pillars: first, standards set by
organizations like the NSA with actual real-world experience; and second, t=
he
judgments of mathematicians with =E2=80=A6 taste and experience, who can ju=
st see
what=E2=80=99s likely to be vulnerable and what isn=E2=80=99t.
Back in 2007, my mathematician friend Greg Kuperberg pointed out the irony =
to
me: here we had a mathematician, lambasting computer scientists for trying =
to
do for cryptography what mathematics itself has sought to do for everything
since Euclid! That is, when you see an unruly mess of insights, related to
each other in some tangled way, systematize and organize it. Turn the tang=
le
into a hierarchical tree (or dag). Isolate the minimal assumptions (one-way
functions? decisional Diffie-Hellman?) on which each conclusion can be
based, and spell out all the logical steps needed to get from here to
there=E2=80=94even if the steps seem obvious or boring. Any time anyone ha=
s tried to
do that, it=E2=80=99s been easy for the natives of the unruly wilderness to=
laugh at
the systematizing newcomers: the latter often know the terrain less well, a=
nd
take ten times as long to reach conclusions that are ten times less
interesting. And yet, in case after case, the clarity and rigor of the
systematizing approach has eventually won out. So it seems weird for a
mathematician, of all people, to bet against the systematizing approach when
applied to cryptography.
The reason I=E2=80=99m dredging up this old dispute now, is that I think th=
e recent
NSA revelations might put it in a slightly new light. In his article=E2=80=
=94whose
main purpose is to offer practical advice on how to safeguard one=E2=80=99s
communications against eavesdropping by NSA or others=E2=80=94Bruce Schneie=
r offers
the following tip:
Prefer conventional discrete-log-based systems over elliptic-curve systems;
the latter have constants that the NSA influences when they can.
Here Schneier is pointing out a specific issue with ECC, which would be
solved if we could =E2=80=9Cmerely=E2=80=9D ensure that NSA or other intere=
sted parties
weren=E2=80=99t providing input into which elliptic curves to use. But I t=
hink
there=E2=80=99s also a broader issue: that, in cryptography, it=E2=80=99s u=
nwise to trust any
standard because of the prestige, real-world experience, mathematical good
taste, or whatever else of the people or organizations proposing it. What
was long a plausible conjecture=E2=80=94that the NSA covertly influences
cryptographic standards to give itself backdoors, and that
otherwise-inexplicable vulnerabilities in deployed cryptosystems are
sometimes there because the NSA wanted them there=E2=80=94now looks close t=
o an
established fact. In cryptography, then, it=E2=80=99s not just for idle ac=
ademic
reasons that you=E2=80=99d like a publicly-available trail of research pape=
rs and
source code, open to criticism and improvement by anyone, that takes you all
the way from the presumed hardness of an underlying mathematical problem to
the security of your system under whichever class of attacks is relevant to
you.
Schneier=E2=80=99s final piece of advice is this: =E2=80=9CTrust the math. =
Encryption is
your friend.=E2=80=9D
=E2=80=9CTrust the math.=E2=80=9D On that note, here=E2=80=99s a slightly-=
embarrassing confession.
When I=E2=80=99m watching a suspense movie (or a TV show like Homeland), an=
d I reach
one of those nail-biting scenes where the protagonist discovers that
everything she ever believed is a lie, I sometimes mentally recite the proof
of the Karp-Lipton Theorem. It always calms me down. Even if the entire
universe turned out to be a cruel illusion, it would still be the case that
NP =E2=8A=82 P/poly would collapse the polynomial hierarchy, and I can tell=
you
exactly why. It would likewise be the case that you couldn=E2=80=99t break=
the GGM
pseudorandom function without also breaking the underlying pseudorandom
generator on which it=E2=80=99s based. Math could be defined as that which=
can still
be trusted, even when you can=E2=80=99t trust anything else.
This entry was posted on Sunday, September 8th, 2013 at 11:31 am and
is filed under Complexity, Nerd Interest. You can follow any responses to
this entry through the RSS 2.0 feed. You can leave a response, or trackback
=66rom your own site.
24 Responses to =E2=80=9CNSA: Possibly breaking US laws, but still bound by=
laws of
computational complexity=E2=80=9D Aaronson on crypto. Schneier =E2=80=9Cell=
iptic-curve
systems; the latter have constants that the NSA influences when they can.=
=E2=80=9D |
Gordon's shares Says: Comment #1 September 8th, 2013 at 1:22 pm [=E2=80=A6]=
Link.
Trust math, but not NSA mathematicians. [=E2=80=A6]
Douglas Knight Says: Comment #2 September 8th, 2013 at 1:35 pm Could you be
more specific about what you mean by the hypothetical =E2=80=9Cbig improvem=
ent=E2=80=9D on
number theory algorithms that is covered by your 1%?
Do elliptic curve algorithms count? Does an L(1/4) algorithm count, or only
quasi-polynomial? What if they can=E2=80=99t break all instances, but, as h=
as
repeatedly happened, they discovered bad primes or bad exponents that make
particular keys weak? Breaking a random half of all keys is almost as good =
as
breaking all of them. Schneier=E2=80=99s condemnation of ECC seems to requi=
re more
than 1% chance NSA knows something special about ECC.
PS =E2=80=93 David Jao, commenting on Schneier=E2=80=99s blog says that we =
can and do use
cryptography to prevent NSA from meddling with mystery constants. He says
that the ECC standard curves are generated by SHA-1, so to meddle, NSA would
have to break the has function. (But if half of curves are bad, that=E2=80=
=99s easy.)
Anonymous Says:=20
Comment #3 September 8th, 2013 at 1:45 pm
You are making good and interesting points. However, Koblitz also has some
valid criticisms of TCS even if his conclusions are not valid. The
mathematical models we built in TCS are useless if they don=E2=80=99t relat=
e to the
practice and we know many of our standard models are not good enough
approximation of the reality and arguably there isn=E2=80=99t enough effort=
to deal
with these issues. Technical heavy weight lifting is used as the ultimate
criteria for judging the value of research projects inside the community.
Also I think you are exaggerating what most cryptographers expected that NSA
was doing. I have heard several famous crypto experts quite surprised by
these revelations and it has shaken their trust in the government
institutions. I never understood why some people presume that government is=
a
benevolent entity, such beliefs in government institutions seems like
ideology to me.
Daniel Armak Says:=20
Comment #4 September 8th, 2013 at 2:06 pm
You can trust the math itself, and so can Bruce Schneier and a few tens of
thousands of other people. But everyone else who can=E2=80=99t grok the ent=
ire
mathematical arguments for each cryptographical system, or doesn=E2=80=99t =
want to
spend a long time studying it, must trust the word of people like you. And
since the NSA can and does subvert people like you, who do original work and
analyze others=E2=80=99 work and sit on standards committees, not to mentio=
n the
programmers who implement it in code, what are we to do?
Daniel W. Says:=20
Comment #5 September 8th, 2013 at 2:33 pm
In my mind, the best circumstantial evidence that the NSA has not practical=
ly
broken any of the major cryptosystems is the following:, if they had, they
would most likely keep this as a highly guarded secret to be used only
against high value targets rather than as a means of monitoring potential
terrorists. It would most likely be contained within a small circle and not
mentioned in power-point presentations to low-level analysts.
Of course, the above argument may be flawed by assuming the NSA has too high
of a level of competence.
T H Ray Says:=20
Comment #6 September 8th, 2013 at 2:43 pm
Scott,
=E2=80=9D =E2=80=A6 the clarity and rigor of the systematizing approach has=
eventually won
out.=E2=80=9D
No doubt. In Euclid=E2=80=99s time as well as the present, though, it is he=
lpful to
have something to systematize. Making that assumption available and
convenient is what mathematicians do.
Scott Says:=20
Comment #7 September 8th, 2013 at 3:02 pm
Daniel Armak #4:
You can trust the math itself, and so can Bruce Schneier and a few tens of
thousands of other people. But everyone else =E2=80=A6 must trust the word =
of people
like you. You raise an excellent point, which I think applies even more
broadly than you say. For one thing, I merely understand some of the general
ideas: I haven=E2=80=99t gone through every detail of the math used by the =
crypto in
my web browser, and I dare say that most professional cryptographers haven=
=E2=80=99t
either.
For another, the point is much broader than cryptography: how can you trust
quantum mechanics, if you haven=E2=80=99t done the requisite experiments yo=
urself?
The physicists could=E2=80=99ve all been bought off by some anti-realist ca=
bal. :-)
Or how can you trust that the government isn=E2=80=99t putting mind-control=
drugs
into the fruit you buy in the supermarket, etc. etc.
So we=E2=80=99re extremely lucky that science hit on a solution to these pr=
oblems=E2=80=94the
only workable solution, really=E2=80=94back in the 17th century. The soluti=
on is to
open up every question to scrutiny, discussion, and challenge by any
interested person. Assertions gain credibility by surviving public
criticism=E2=80=94and that=E2=80=99s just as true in math as it is in exper=
imental sciences.
I believe many theorems even though I haven=E2=80=99t checked the proofs my=
self,
because I know that if there were an error, then someone else could=E2=80=
=99ve made a
name for themselves by finding it.
Now, for this Popperian dynamic to work, the whole process has to be carried
out in the open: if I thought someone who found a fatal flaw in a proof wou=
ld
only tell their friends, then that doesn=E2=80=99t do me any good. That=E2=
=80=99s why the
dividing line between =E2=80=9Ccrypto as black art=E2=80=9D and =E2=80=9Cmo=
dern crypto=E2=80=9D happened
precisely when new discoveries started being published in the open
literature, rather than being filed in a drawer at NSA or GCHQ.
wolfgang Says:=20
Comment #8 September 8th, 2013 at 3:20 pm
Unfortunately, this xkcd.com/538/ had it right imho.
Scott Says:=20
Comment #9 September 8th, 2013 at 3:20 pm
Daniel W. #5: If the NSA had really broken strong cryptosystems, then why
would they have resorted to so many covert tactics (or, in the case of the
Clipper Chip, overt attempts) to prevent people from using strong crypto,
unless NSA has a backdoor? I suppose it=E2=80=99s all elaborate psychologic=
al
warfare, to prevent us from discovering the fact that these cryptosystems
were broken? And that even Snowden himself is part of the NSA=E2=80=99s mas=
ter plan?
:-)
At least in my book, every time you claim that what looks on its face like
evidence for X, is really evidence for a powerful cabal trying to prevent
everyone from discovering not(X), the plausibility of your theory gets cut =
by
a factor of maybe 50,000. This is directly related to the fact that I don=
=E2=80=99t
believe any conspiracy theories=E2=80=94as in zero, not one.
Scott Says:=20
Comment #10 September 8th, 2013 at 3:32 pm
Douglas Knight #2: Sure, dramatic improvements in elliptic-curve algorithms
would certainly count=E2=80=94as would =E2=80=9Cmerely=E2=80=9D subexponent=
ial algorithms, were the
improvements large enough to threaten key sizes that the academic
cryptographers considered safe.
More broadly, though, you=E2=80=99re entirely right that there=E2=80=99s no=
t a sharp line
between =E2=80=9Cimproved number-theory algorithms=E2=80=9D and =E2=80=9Cim=
plementation
vulnerabilities.=E2=80=9D Often, what=E2=80=99s happened in practice is tha=
t an
implementation vulnerability has opened the way for an attack that still
requires interesting and nontrivial number theory. But I suppose that sort =
of
thing would still belong to the =E2=80=9C99%=E2=80=9D part of my probabilit=
y estimate. In the
=E2=80=9C1%=E2=80=9D part, I really had in mind =E2=80=9Csomething that wou=
ld give theoretical
cryptographers a heart attack=E2=80=9D (like, I dunno, factoring in L(1/10)=
, or
elliptic curve discrete log in quasipolynomial time).
Scott Says:=20
Comment #11 September 8th, 2013 at 5:03 pm
Anonymous #3:
You are making good and interesting points. However, Koblitz also has some
valid criticisms of TCS even if his conclusions are not valid. I completely
agree that Koblitz has some valid criticisms.
However, I=E2=80=99ve read pretty much all of his and Menezes=E2=80=99s ant=
i-TCS screeds, and
to me what he=E2=80=99s doing seems, if you like, too easy to be helpful. K=
oblitz=E2=80=99s
favorite M.O. is to recount various slip-ups by people in the =E2=80=9CGold=
reich
school of crypto=E2=80=9D and laugh at them: =E2=80=9Chaha, they talk about=
=E2=80=98provable
security,=E2=80=99 but there was a bug in their proof! or their security de=
finition
left out an important class of side-channel attacks!=E2=80=9D Then, with ev=
en more
glee, Koblitz relates how the hapless computer scientists put out a new pap=
er
supposedly fixing the problem, but that paper had its own problems, and so
on.
The trouble is, that is indeed what a bunch of incompetent buffoons would
look like, but it=E2=80=99s also what science looks like! :-) Koblitz never=
seems to
want to acknowledge that the end result of the process is better scientific
understanding and more secure cryptosystems than before (even if still not
perfect).
Also, of course, Koblitz almost defiantly refuses to suggest any better
mathematical foundations for cryptography, besides the reduction-based
foundations that were built up over the last 30 years. I.e., it=E2=80=99s n=
ot that
instead of adaptive chosen ciphertext attack, he has a better definition to
propose, or that instead of =E2=80=9Cbodacious=E2=80=9D new hardness assump=
tions, he can give
a single assumption that suffices for everything. Instead, what he appears =
to
want is simply a return to the =E2=80=9Cblack art=E2=80=9D era of cryptogra=
phy, when security
arguments boiled down to =E2=80=9Cwe tried to break it and failed=E2=80=9D =
or =E2=80=9Ctrust us, we
have better mathematical taste than you.=E2=80=9D
The trouble is, I can=E2=80=99t think of a single case in the history of sc=
ience when
mathematical foundations as well-developed as cryptography=E2=80=99s now ar=
e, were
simply abandoned wholesale without better mathematical foundations to repla=
ce
them. So intellectually, Koblitz strikes me as someone who=E2=80=99s throwi=
ng spears
at battle-tanks. Being the excellent marksman that he is, he actually scores
some hits=E2=80=94but the reduction-encrusted battle-tanks are still going =
to win in
the end.
The mathematical models we built in TCS are useless if they don=E2=80=99t r=
elate to
the practice and we know many of our standard models are not good enough
approximation of the reality and arguably there isn=E2=80=99t enough effort=
to deal
with these issues. Would one also say that the mathematical foundations of
topology=E2=80=94open sets, Urysohn=E2=80=99s Lemma, etc.=E2=80=94are usele=
ss if they don=E2=80=99t relate to
the practice of tying and untying knots? I think that=E2=80=99s a pretty cl=
ose
analogy for the relationship between what, say, Goldreich or Goldwasser or
Micali do, and the actual practice of cryptography. In both cases, yes,
there=E2=80=99s some relation between the intellectual foundations on the b=
ottom and
the beautiful ornaments on top, but not surprisingly there are many floors =
in
between. Starting from a one-way function, for example, you first have to
construct a quasi-regular one-way function, then a pseudoentropy generator,
then a pseudorandom generator, then a pseudorandom function, and then maybe
you can start to think about building (say) a rudimentary private-key
cryptosystem or signature scheme.
Also I think you are exaggerating what most cryptographers expected that NSA
was doing. I have heard several famous crypto experts quite surprised by
these revelations and it has shaken their trust in the government
institutions. I never understood why some people presume that government is=
a
benevolent entity, such beliefs in government institutions seems like
ideology to me. My situation is different: I never had any real doubt that
NSA was doing such things; the thing I genuinely don=E2=80=99t know is whet=
her they
have good reasons to be doing them. I consider it conceivable that the NSA
has indeed stopped many terrorist attacks or other international disasters
that we never hear about=E2=80=94in which case, the strongest case in their=
favor
might be stronger than the strongest case that can ever be made publicly. T=
he
fact that President Obama, who=E2=80=99s so reasonable on so many issues, h=
as implied
as much is evidence for that view from my perspective. On the other hand, I
also consider it conceivable that the current eavesdropping regime is purely
a result of the universal tendency of bureaucracies to expand, justify
themselves, and zealously guard their power and privileges. Or it could be
some combination of the two.
For me, though, the deciding consideration is that, even in a fantasy world
where the NSA=E2=80=99s actions had always been 100% justified, I=E2=80=99d=
still want them
to be more accountable to the public than they are now. =E2=80=9CTrust that=
we have
our reasons, even though we can=E2=80=99t tell you what they are=E2=80=9D s=
imply doesn=E2=80=99t work
over the long term in a democracy, even if the trust is justified at any
particular time or in any particular case (and of course, often it hasn=E2=
=80=99t
been).
Anonymous Says:=20
Comment #12 September 8th, 2013 at 8:05 pm
I agree with you that his attitude is not constructive criticism. I would
even go further than you and say it is stupid to forget the science of cryp=
to
and go back to purely engineering art treatment.
Regarding reasonability of what NSA does, NSA and its backers would of cour=
se
claim these tools are useful. To be honest, security was a weak point of
Obama=E2=80=99s campaign, he is not really knowledgeable in these issues an=
d he has
not gone and will not go against his advisers if they tell him these tools
are necessary to fight terrorism. However, as far as I have heard, they have
hard time convincing anyone outside executive branch that these tools have
been as useful as they are claiming. How many major terrorist plots they ha=
ve
been uncovered and prevented using these tools? It seems that they are using
these tools for a very wide range of activities including industrial and
political espionage on foreign governments and companies and gain political
and commercial advantage (what they call US national interests, not just
securing Americans against terrorists). Does anyone really believe that EU =
or
Brazil or liberal NGOs will launch a terrorist attack on US? FBI=E2=80=99s =
actions
against Dr. King is telling how far they would go. They use the fear factor
of a possible terrorist attacks to justify these actions to the public,
however the laws allow them to do whatever they want to and when there are
restrictions (like the fourth amendments) they find ways to circumvents them
(e.g. by colliding with foreign intelligence services like GCHQ to spy on
American citizens) or change the interpretations of those laws. We are very
lucky that many influential Americans in the previous generations had a
negative view of the federal government and wanted to restrict its powers as
much as possible, restrictions which are being removed in practice (partly
because some people want to settle sociopolitical disputes present in the
country using the government=E2=80=99s power). I don=E2=80=99t see why so m=
uch power should
be invested in a single authority with almost no real public supervision and
scrutiny (a role that media was playing to some extent in previous decades
but is coming under heavy pressure from government as Manning, Swartz,
Snowden, =E2=80=A6 cases demonstrate). And even when courts find that someo=
ne in the
government has seriously violated the laws the president forgives them and
they avoid real punishment (as Scoot Libby case demonstrates).
It is not just US government, there is a trend in western liberal
democracies. It is simply unbelievable that the UK security forces used a l=
aw
passed to fight terrorism to hold the partner of a Guardian journalist for 9
hours without a lawyer and without the protection of Miranda rights against
self-incrimination. Anyone who thinks that security forces will only use the
authority and tools they obtain to the limited extent of the original goal
suffers from extreme nativity. They will use any tools in their disposal to
the fullest extent they can to achieve what they perceive to be the goals of
their institution. When they perceive journalists like Greenwald as a threat
to the national interests they use these tools to fight them which includes
intimidating the partner of a journalist using terrorism fighting powers. I
still fund it really hard to believe that we have gone so far in the
direction of an Orwellian society.
What can theoretical computer science offer biology? | Theory, Evolution, a=
nd
Games Group Says:=20
Comment #13 September 9th, 2013 at 2:16 am
[=E2=80=A6] the aid that cstheory can offer to biological understanding. In
yesterday=E2=80=99s post on the NSA and computational complexity, Aaronson =
=E2=80=94 with
attribution to mathematician Greg Kuperberg =E2=80=94 provided the followin=
g [=E2=80=A6]
Paul Beame Says:=20
Comment #14 September 9th, 2013 at 2:45 am
Some of the NSA revelations have been no surprise at all. It was well known
in the 1980=E2=80=B2s, particularly after the publication of The Puzzle Pal=
ace, that
the NSA was tapping all the trans-Atlantic telephone cables; gathering up of
all e-mail to foreign addresses seems like more of the same.
The relationship of the NSA with TCS cryptographers has been pretty shaky. I
recall attending a theory of cryptography workshop at MIT=E2=80=99s Endicot=
t House in
June 1985 with one or two official NSA attendees. At the time, there were o=
ne
or two TCS attendees known to have NSA funding and the NSA people wanted to
recruit more. In announcing their desire to sponsor more TCS cryptographers,
one of the NSA people cast a pall over the meeting by saying: =E2=80=9CIf y=
ou are
interested, just mention it in a phone conversation with one of your friends
and we=E2=80=99ll get back to you.=E2=80=9D This didn=E2=80=99t exactly end=
ear them to anyone.
J Says:=20
Comment #15 September 9th, 2013 at 2:51 am
=E2=80=9CMath could be defined as that which can still be trusted, even whe=
n you
can=E2=80=99t trust anything else=E2=80=9D
Wait till someone shows multiplication and addition have same complexity or
possible Voevodsky=E2=80=99s/Nelson=E2=80=99s worst nightmare comes true
Refer:
http://mathoverflow.net/questions/40920/what-if-current-foundations-of-math=
ematics-are-inconsistent
http://mathoverflow.net/questions/36693/nelsons-program-to-show-inconsisten=
cy-of-zf
Scott Says:=20
Comment #16 September 9th, 2013 at 4:20 am
J #15: Multiplication and addition having the same complexity (and yes, it=
=E2=80=99s
conceivable that there=E2=80=99s a linear-time multiplication algorithm) wo=
uldn=E2=80=99t do
anything whatsoever to undermine my trust in math=E2=80=94why would it?
Also, even if ZF set theory were shown to be inconsistent (and it won=E2=80=
=99t be
:-) ), that wouldn=E2=80=99t do anything whatsoever to undermine my trust i=
n theorems
about (say) finite groups, or low-dimensional topology, or theoretical
computer science=E2=80=94in fact, about anything that doesn=E2=80=99t invol=
ve transfinite
sets. It would =E2=80=9Cmerely=E2=80=9D tell me that there was a need (and,=
of course, an
exciting opportunity) to rethink the foundations. That=E2=80=99s something =
that
already happened 100+ years ago (the renovations causing virtually no damage
to the higher floors), and that could conceivably happen again.
Vitruvius Says:=20
Comment #17 September 9th, 2013 at 4:58 am
I agree, Scott, with your general position that any time one claims that
=E2=80=9Cevidence for x is really evidence for a powerful cabal trying to p=
revent
everyone from discovering not(x)=E2=80=9D one=E2=80=99s credibility drops b=
y an irrecoverably
large factor, and I agree with you that =E2=80=9Cmath can be defined as tha=
t which
can still be trusted, even when you can=E2=80=99t trust anything else=E2=80=
=9D (as you put
it), yet that still begs the question of how we the people decide what to
trust to be valid math.
Similarly, while your suggestion to =E2=80=9Copen up every question to scru=
tiny,
discussion, and challenge by any interested person=E2=80=9D may be necessar=
y in order
to establish public trust, it isn=E2=80=99t sufficient because we still hav=
e the
problem of deciding which such interested persons to trust, and which to
write off as conspiracy theorists in their own right. How do we feasibly
decide, in effect, whether Ehrenhaft is a crackpot (as it were), and whether
=E2=80=9CSnowden himself is part of the NSA=E2=80=99s master plan=E2=80=9D =
(as you playfully alluded
to)?
To that end you may be interested in Why Doesn=E2=80=99t the Public Trust
Scientists?, a lecture by The Right Honourable Professor The Baroness O=E2=
=80=99Neill
of Bengarve, Emeritus Professor of Philosophy at the University of Cambridge
and past Principal of Newnham College, Cambridge, which she presented in 20=
05
as part of the Science Futures series by the San Diego Science and Technolo=
gy
Council=E2=80=99s Center for Ethics in Science and Technology.
Note that while =E2=80=9Cscientists=E2=80=9D are the titular and exemplary =
referent matter in
that lecture, Baroness O=E2=80=99Neill=E2=80=99s talk actually considers a =
range of questions
in regard of public trust, including the roles of professional organization=
s,
trustworthiness (which can=E2=80=99t replace trust because of the quis cust=
odiet
ipsos custodes problem), statutory regulation, post hoc accountability, &c,
which apply more broadly to the matters of public trust in any and every
profession and institution, including politics and the law.
O=E2=80=99Neill argues, if I may be so bold as to suggest a pr=C3=A9cis, th=
at going back
through the 17th century (as you noted) western liberal democracies have
indeed evolved a multipartite methodology that does tend work in practice a=
nd
that may well be the best we can get in principal, though it remains unclear
to me how well we are applying those techniques to matters of state security
in general, and how effectively you folks in the United States of America a=
re
applying those techniques to your vaunted Agency in particular.
Scott Says:=20
Comment #18 September 9th, 2013 at 5:01 am
Paul Beame #14: I=E2=80=99ve actually heard that joke many times, in other =
variants.
(=E2=80=9CInterested in career opportunities at the NSA? Call your mom and =
let her
know!=E2=80=9D) I didn=E2=80=99t know that NSA people themselves used the j=
oke at
conferences, but it doesn=E2=80=99t surprise me at all.
J Says: Comment #19 September 9th, 2013 at 6:39 am =E2=80=9CMultiplication =
and
addition having the same complexity (and yes, it=E2=80=99s conceivable that=
there=E2=80=99s a
linear-time multiplication algorithm) wouldn=E2=80=99t do anything whatsoev=
er to
undermine my trust in math=E2=80=94why would it?=E2=80=9D
I thought I read somewhere that if addition and multiplication turn out to =
be
similar in complexity, then it would imply something is wrong with
mathematics.
On the same vein think of the generalization of scheme theory that Mochizuki
claims to have undertaken to take apart + and x in ring structure.
I would think something fundamentally would have changed in our picture if
they turn to be similar in complexity.
J Says:=20
Comment #20 September 9th, 2013 at 6:47 am
Atleast for computational purposes, the multiplicative group structure and
additive group structure of $\Bbb Z$ seem to be coinciding. This seems wron=
g.
I cannot directly relate to $Z \bmod p$ but this seems to have implication =
to
Discrete Log. An implication for this may not be beyond reach for atleast a
few other rings as well.
Scott Says:=20
Comment #21 September 9th, 2013 at 7:02 am
J #19: Well, we already have a remarkable O(n logn loglogn) multiplication
algorithm (due to F=C3=BCrer, and building on many previous works), and it =
hasn=E2=80=99t
created any problem for the foundations of mathematics that I know about.
Meanwhile, just like for most problems, we currently have no lower bound for
multiplication better than the trivial =CE=A9(n). I suppose I=E2=80=99d gue=
ss that =CE=A9(n
logn) is some sort of barrier, but not with any strength of conviction: if a
linear-time algorithm were discovered, it certainly wouldn=E2=80=99t cause =
me to
doubt the consistency of ZF set theory. :-)
Scott Says:=20
Comment #22 September 9th, 2013 at 7:16 am
Vitruvius #17:
it remains unclear to me =E2=80=A6 how effectively you folks in the United =
States of
America are applying those techniques to your vaunted Agency in particular.
As long as we=E2=80=99re trading mild national barbs, you=E2=80=99re Canadi=
an? You guys do
have the Communications Security Establishment, which according to the NYT
article is one of only four foreign agencies (along with Britain=E2=80=99s,
Australia=E2=80=99s, and New Zealand=E2=80=99s) that =E2=80=9Cknows the ful=
l extent=E2=80=9D of the NSA=E2=80=99s
decoding capabilities and is cleared for its =E2=80=9CBullrun=E2=80=9D prog=
ram. Though I
confess that, when I try to imagine Canada=E2=80=99s CSE, I come up with so=
mething
like the following:
Read this gentleman=E2=80=99s private email? Ooo, nooo, that doesn=E2=80=99=
t sound terribly
polite, eh?
J Says:=20
Comment #23 September 9th, 2013 at 7:21 am
Professor I am well aware of all $n^{1+\epsilon}$ algorithms and Schonage=
=E2=80=99s
$O(n)$ algorithm on multitape machines. I cannot find the reference I am
thinking. It was written by a TCS theorist. I would seriously think that the
standard ring structure in $\Bbb Z$ could be modeled differently. I do not
know if ZF would be affected. However the question of treating x and +
differently for computation purposes compare to mathematical purposes arises
making things murky.
I am not implicating ZF with $O(n)$ algorithms for standard x operations on
the standard structure of $\Bbb Z$. The ZFC comment was a second piece of
mathematical conundrum some reputed folks have raised awareness about for a
need to be more well-grounded and it rang well with your statement on truth
in math as we know it. (Unrelated but bringing in =E2=80=93 $Z$ has been a =
puzzle
before as well =E2=80=93 it is the simplest ring with a spectrum of prime i=
deals
whose dimension is unclear to be interpreted in a standard way)
Scott Says:=20
Comment #24 September 9th, 2013 at 7:23 am
Wolfgang #8:
Unfortunately, this xkcd.com/538/ had it right imho.
YES! I especially liked the mouseover text (=E2=80=9CActual actual reality:=
nobody
cares about his secrets=E2=80=9D).
--HAv5+T9jbwMPl6Kw
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
iQIcBAEBAgAGBQJSLcGqAAoJEPRuNImsiU7FWzkQAIDFhl7LSv2VMOuWpD+o55BN
V8Qh+/F2cd7ZfV0XZLmdCc08tUUGFZlffAuiNn8CanX4eJ4aYOp3uN/VqTznWKop
W4c9pynY+dbAjppbZQ3LrN+eF9RNYE3OMvZx4lDPwCYrMfhr5kmvvfrVfYyfTVlx
82QRWL3SZGhXDkwFW0BYQPRzORaSNSl9dM7JD3tSkvrOV3494+IVFBuIxsLK3OhB
DJUaD/zqYsM7eWJcxrPiSf90aiOQvy72TOeuUaH8/+zBOSCTYYeekkTHK59EltZ0
KxhuaEoFcxCGeg2VzPNR8lt+KCLxemOvdJAwli6wEUOfRByqterVAnSwWZhsDN0c
ScbhR0Qt/xBXcGO16N7/Rbaje5nMO/K8sS2Z3GgL5qSUantx5oaPFivadIVu0A3V
yQcypgtTmkKpyQ2/hgsiqK+JayBgi8+F2pjNT+0cRUBr0Ae/McM/W/70NtikT1Mj
6SsfqbCC8cttKTNco9S7pex7FZod9LmuQWTutXJKKZoG91G1DTpVmDkrG+Sm21C4
hwkaX3E/537ZrIJOMgKsBJnWVW/fuY9ByhkwXSgjSqhoEsLd7gQg3hTHaJi3/d4Q
OGc0BUyVSlYssFIPiZ6PrFnakC1TTLU43spem6yoKL2mqUFu055J0OOZmCiO3Zal
UpzdwfiLUY5/8IBHUje7
=PaDa
-----END PGP SIGNATURE-----
--HAv5+T9jbwMPl6Kw--
--===============1843739747380698912==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============1843739747380698912==--
