- cypherpunks - lists.cpunks.org

[cryptography] ProPublica's Jeff Larson on the NSA Crypto Story and Another View
by Eugen Leitl 11 Sep '13

11 Sep '13

----- Forwarded message from John Young <jya(a)pipeline.com> ----- Date: Tue, 10 Sep 2013 14:38:01 -0400 From: John Young <jya(a)pipeline.com> To: cryptography(a)randombit.net, cyperhpunks(a)cpunks.org, cryptome(a)freelists.org Subject: [cryptography] ProPublica's Jeff Larson on the NSA Crypto Story and Another View X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9 ProPublica's Jeff Larson on the NSA Crypto Story http://source.mozillaopennews.org/en-US/articles/propublicas-jeff-larson-ns… Describes two months of digging through the Snowden documents, using search tool Intella, finding code words, looking for references to those, scrambling to understand and explain the technology to experts and the public, traveling between New York and London, thrill of working with NYT, Guardian and others. Claims extraordinary security was laid on to protect the material. But doesn't say what it was or is. Pretty good gritty back story compared to the burnished fronts. Hard to tell if it is a front story as well due to admission of withholding materials. Nothing said about consulting with USG or HMG. Here's a much less polite viewpoint: http://ohtarzie.wordpress.com/2013/09/10/fuck-the-guardian-take-your-drip-a… _______________________________________________ cryptography mailing list cryptography(a)randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5

1 0

generating noisy samples at a high rate with RTLSDR
by Eugen Leitl 10 Sep '13

10 Sep '13

Just remembered another cheap option for generating a lot of noisy samples: http://sdr.osmocom.org/trac/wiki/rtl-sdr Especially, with wideband RF noise source.

2 2

Re: [guardian-dev] OpenPGP Keychain 2.1 with new API
by Eugen Leitl 10 Sep '13

10 Sep '13

----- Forwarded message from David Holl <david(a)ad5ey.net> ----- Date: Tue, 10 Sep 2013 12:29:17 -0400 From: David Holl <david(a)ad5ey.net> To: Natanael <natanael.l(a)gmail.com> Cc: k-9-dev(a)googlegroups.com, guardian-dev <guardian-dev(a)lists.mayfirst.org> Subject: Re: [guardian-dev] OpenPGP Keychain 2.1 with new API -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 On Tue, Sep 10, 2013 at 05:44:33PM +0200, Natanael wrote: > While mentioning smartcards, the Yubikey Neo seems to have an > OpenPGP smartcard mode (that needs to manually actiated in > firmware), could that work with this app? I would hope so. Does the Neo claim to be compatible with the open specification? http://g10code.com/docs/openpgp-card-2.0.pdf > Then you'd always have a hardware protected keypair (if you don't > lose your Yubikey), so even rootkits can't get your private key. Exactly! :) Rootkits or compromised firmware... And even if a compromised device does cache my pin and use my card (while briefly inserted), I hope to be alerted of any illicit accesses courtessy of the signature counter built into the card. There seem to be at least 3 potential "cards" that I'm aware of: OpenPGP SmartCard V2 Yubikey Neo Crypto Stick https://www.crypto-stick.com/ (I put "cards" in quotes, because the Crypto Stick includes a "thumb" form-factor USB interface. Though not as tiny as the Neo, it still supports 4096 bit keys.) - - David Aside: I selected the OpenPGP SmartCard V2 for my personal use, because the Crypto Stick has been out of stock for a while, and the Yubikey Neo appears to only support 2048 bit keys. If I really want the "thumb" form factor of the Crypto Stick, I may try popping out the ID-000 minicard from the OpenPGP SmartCard and putting it into a "Gemalto USB Shell Token V2" (aka the "IDBridge K30"). Otherwise, the "SCM SCR3500" reader is almost small enough for use on a key chain, and is widely available at reasonable prices. (about $40 total for a SmartCard V2 with a SCM SCR3500 reader.) -----BEGIN PGP SIGNATURE----- iQIcBAEBCgAGBQJSL0jdAAoJEDnNbkIYxVca7psP/1oJT7/IFofnfM8Qs4ugb7RJ 1P3jeZHKD7QtgGtRQk4kUYypvxZq56xGQd2k2hZSUtVYrmewj//Siyi9cpIRrdts h2XUi5RhOUCT6Rz/Zd8Mti0urcEghbxaDHjUa4JichEOlKRAjZsQjc0xnHsuyauw TBGCuOeAhw9gCuKrXOpHnzwnRtcmBRcxLrOn+q9cQCx8EkdEiQgklMl5qqzNpOa3 VnvvMNk5wZ144WUYd5F78Tn9ssDEO/Jt1DO6WtWEJq5DjTAZVxyRXVp1/7e6/se9 haiUJu8Zl8Co7HeLZBtJlNDG2pzqiQu5vCywZyprMFf0ZNpLwpvP7iLmuz2n5R16 0EYQJ5z3g5c2YLivIawxzUO+26gXEDLpFZZFzRf8zobnfYhvqjQFPNU3HtR/jp34 UPgg3urHlUIvGPns3/Z2pfIuyru7uUfLZEWHPiPx/g4pFBLrZAdzyRJZOJ9SWCtd eNdfNGtMf/XfRYyb4eYlEUxEdvt0qJ8M9u+/1jPupDYvVhn/feFgZE/cumlv+AM3 VFA8HvQ1grDgW9JL4KkUCuasEpAjJo9on7AGx0SrKiHyYKSjOCR183yzlckoOz8c O5hhbGb07hL4cfGAIDJ7rBwAliejyrZ2OBHpyLvJ3Eanwbdux72saIcEvmStDK5L MI3+5DeZoV0vBUVmkgxp =pa6I -----END PGP SIGNATURE----- _______________________________________________ Guardian-dev mailing list Post: Guardian-dev(a)lists.mayfirst.org List info: https://lists.mayfirst.org/mailman/listinfo/guardian-dev To Unsubscribe Send email to: Guardian-dev-unsubscribe(a)lists.mayfirst.org Or visit: https://lists.mayfirst.org/mailman/options/guardian-dev/eugen%40leitl.org You are subscribed as: eugen(a)leitl.org ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5

1 0

Re: [cryptome] Interesting
by John Young 10 Sep '13

10 Sep '13

Security theater. Phony as thinking NSA and national spies spy from embassies, not the key internet exchanges and telecom hubs in Frankfurt and other locations around the globe. This is amply described in a slew of technical reports and popular articles and books. Although, tellingly, not much discussed on crypto and comsec fora where the telecom and internet experts blow smoke and jerk off one other about trivial arcana to conceal their role in helping the spies for handsome salaries and fees. NDAs behind the wanking are abundant, hopefully some to be revealed by Snowden if not quietly redacted by those very same wankers ostensibly helping spread the word of perfidy by TLAs as cover for crypto onanism. At 09:23 AM 9/10/2013, you wrote: >Colleagues, > ><http://www.spiegel.de/international/germany/german-helicopter-searched-for-…>http://www.spiegel.de/international/germany/german-helicopter-searched-for-… >-- >Best regards. > >Haim Barak >To Serve and Protect Our Community >In God We Trust >Israel#: 5353... >Email: <mailto:haim357@gmail.com>haim357(a)gmail.com >Skype: haim.357 ><http://haim357.wordpress.com/>http://haim357.wordpress.com/ > ><http://haim357.files.wordpress.com/2009/11/banner.jpg> >This e-mail is intended only for the named recipient(s) and may contain >information that is privileged, confidential and/or exempt from >disclosure under applicable law. No waiver of privilege, confidence or >otherwise is intended by virtue of communication via the Internet. Any >unauthorized use, dissemination or copying is strictly prohibited. >Thank you.

1 0

Re: [Cryptography] The One True Cipher Suite
by Eugen Leitl 10 Sep '13

10 Sep '13

----- Forwarded message from Jerry Leichter <leichter(a)lrw.com> ----- Date: Tue, 10 Sep 2013 07:42:55 -0400 From: Jerry Leichter <leichter(a)lrw.com> To: Phillip Hallam-Baker <hallam(a)gmail.com> Cc: "cryptography(a)metzdowd.com" <cryptography(a)metzdowd.com>, ianG <iang(a)iang.org> Subject: Re: [Cryptography] The One True Cipher Suite X-Mailer: Apple Mail (2.1283) On Sep 9, 2013, at 12:00 PM, Phillip Hallam-Baker wrote: > Steve Bellovin has made the same argument and I agree with it. Proliferation of cipher suites is not helpful. > > The point I make is that adding a strong cipher does not make you more secure. Only removing the option of using weak ciphers makes you more secure. I'm not so sure I agree. You have to consider the monoculture problem, combined with the threat you are defending against. The large burst of discussion on this list was set off by Perry's request for ways to protect against the kinds of broad-scale, gather-everything attacks that Snowden has told us the NSA is doing. So consider things from the side of someone attempting to mount this kind of attack: 1. If everyone uses the same cipher, the attacker need only attack that one cipher. 2. If there are thousands of ciphers in use, the attacker needs to attack some large fraction of them. As a defender, if I go route 1, I'd better be really, really, really sure that my cipher won't fall to any attacks over its operational lifetime - which, if it's really universal, will extend many years *even beyond a point where a weakness is found*. On the other hand, even if most of the ciphers in my suite are only moderately strong, the chance of any particular one of them having been compromised is lower. This is an *ensemble* argument, not an *individual* argument. If I'm facing an attacker who is concentrating on my messages in particular, then I want the strongest cipher I can find. Another way of looking at this is that Many Ciphers trades higher partial failure probabilities for lower total/catastrophic failure probabilities. Two things are definitely true, however: 1. If you don't remove ciphers that are found to be bad, you will eventually pollute your ensemble to the point of uselessness. If you want to go the "many different ciphers" approach, you *must* have an effective way to do this. 2. There must be a large set of potentially good ciphers out there to choose from. I contend that we're actually in a position to create reasonably good block ciphers fairly easily. Look at the AES process. Of the 15 round 1 candidates, a full third made it to the final round - which means that no significant attacks against them were known. Some of the rejected ones failed due to minor "certificational" weaknesses - weaknesses that should certainly lead you not to want to choose them as "the One True Cipher", but which would in and of themselves not render breaking them trivial. And, frankly, for most purposes, any of the five finalists would have been fine - much of the final choice was made for performance reasons. (And, considering Dan Bernstein's work on timing attacks based on table lookups, the performance choices made bad assumptions about actual hardware!) I see no reason not to double-encrypt, using different keys and any two algorithms from the ensemble. Yes, meet-in-the-middle attacks mean this isn't nearly as strong as you might naively think, but it ups the resource demands on the attacker much more than on the defender. Now, you can argue that AES - the only cipher really in the running for the One True Symmetric Cipher position at the moment - is so strong that worrying about attacks on it is pointless - the weaknesses are elsewhere. I'm on the fence about that; it's hard to know. But if you're going to argue for One True Cipher, you must be explicit about this (inherently unprovable) assumption; without it your argument fails. The situation is much more worse for the asymmetric case: We only have a few alternatives available and there are many correlations among their potential weaknesses, so the Many Ciphers approach isn't currently practical, so there's really nothing to debate at this point. Finally, I'll point out that what we know publicly about NSA practices says that (a) they believe in multiple ciphers for different purposes; (b) they believe in the strength of AES, but only up to a certain point. At this point, I'd be very leery of taking anything NSA says or reveals about it practices at face value, but there it is. -- Jerry _______________________________________________ The cryptography mailing list cryptography(a)metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5

1 0

Re: The US government has betrayed the Internet. We need to take it back
by Eugen Leitl 10 Sep '13

10 Sep '13

----- Forwarded message from "John S. Quarterman" <jsqnanog(a)quarterman.com> ----- Date: Fri, 06 Sep 2013 06:47:26 -0400 From: "John S. Quarterman" <jsqnanog(a)quarterman.com> To: sam(a)circlenet.us, "John S. Quarterman" <jsq(a)quarterman.com>, nanog(a)nanog.org Subject: Re: The US government has betrayed the Internet. We need to take it back > On 2013-09-06 05:57, Roland Dobbins wrote: > > There are no purely technical solutions to social ills. Schneier of > > all people should know this. Schneier does know this, and explicitly said this. -jsq http://www.theguardian.com/commentisfree/2013/sep/05/government-betrayed-in… Three, we can influence governance. I have resisted saying this up to now, and I am saddened to say it, but the US has proved to be an unethical steward of the internet. The UK is no better. The NSA's actions are legitimizing the internet abuses by China, Russia, Iran and others. We need to figure out new means of internet governance, ones that makes it harder for powerful tech countries to monitor everything. For example, we need to demand transparency, oversight, and accountability from our governments and corporations. Unfortunately, this is going play directly into the hands of totalitarian governments that want to control their country's internet for even more extreme forms of surveillance. We need to figure out how to prevent that, too. We need to avoid the mistakes of the International Telecommunications Union, which has become a forum to legitimize bad government behavior, and create truly international governance that can't be dominated or abused by any one country. Generations from now, when people look back on these early decades of the internet, I hope they will not be disappointed in us. We can ensure that they don't only if each of us makes this a priority, and engages in the debate. We have a moral duty to do this, and we have no time to lose. Dismantling the surveillance state won't be easy. Has any country that engaged in mass surveillance of its own citizens voluntarily given up that capability? Has any mass surveillance country avoided becoming totalitarian? Whatever happens, we're going to be breaking new ground. Again, the politics of this is a bigger task than the engineering, but the engineering is critical. We need to demand that real technologists be involved in any key government decision making on these issues. We've had enough of lawyers and politicians not fully understanding technology; we need technologists at the table when we build tech policy. To the engineers, I say this: we built the internet, and some of us have helped to subvert it. Now, those of us who love liberty have to fix it. ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5

4 3

Re: hardware RNG
by Juan Garofalo 10 Sep '13

10 Sep '13

Thanks for the replies guys! I'm going through the links provided. Meanwhile I got a follow up question... Creating hardware rngs for individual PCs or phones or similar devices isn't really hard. We don't need to rely on a multibillion american corporation like intel to produce some state-of-the-art circuitry. There are applications that need a fast stream of random numbers, but those applications are not the applications end users run on their devices for security purposes - Did I get the general idea right? J.

3 2

[Cryptography] What TLS ciphersuites are still OK?
by Eugen Leitl 09 Sep '13

09 Sep '13

----- Forwarded message from Ben Laurie <ben(a)links.org> ----- Date: Mon, 9 Sep 2013 17:29:24 +0100 From: Ben Laurie <ben(a)links.org> To: Cryptography Mailing List <cryptography(a)metzdowd.com> Subject: [Cryptography] What TLS ciphersuites are still OK? Perry asked me to summarise the status of TLS a while back ... luckily I don't have to because someone else has: http://tools.ietf.org/html/draft-sheffer-tls-bcp-00 In short, I agree with that draft. And the brief summary is: there's only one ciphersuite left that's good, and unfortunately its only available in TLS 1.2: TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 _______________________________________________ The cryptography mailing list cryptography(a)metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5

1 0

Re: [Bitcoin-development] Blockchain archival
by Eugen Leitl 09 Sep '13

09 Sep '13

----- Forwarded message from rob.golding(a)astutium.com ----- Date: Sun, 08 Sep 2013 04:56:17 +0100 From: rob.golding(a)astutium.com To: bitcoin-development(a)lists.sourceforge.net Subject: Re: [Bitcoin-development] Blockchain archival User-Agent: Roundcube Webmail/0.8.5 > (there's no way to be completely trust-free without this). Not quite true, as I said balance-at-point-in-time would solve that (and make the storage requirements much lower) >> If going that route, then solutions to the 'consolidate >> addresses/wallets' >> question and formal 'discard' of addresses could get addressed. > > Not sure what you mean here. Addresses and wallets are two completely > different things. Addresses are single-use destinations that point to > a wallet > (which is itself private and unknown to the network). For bitcoin to grow beyond interesting experiment into global everyday use a number of things would have to happen, not least of which is taking 'average punter' into account. Whilst new ideas can filter into the general consciousness over time,sometimes concepts have to go with 'what already works' :) People's concept of money hasn't really changed in over 1,000 years - it remains 'something of known value i can exchange for something else'. No-one outside of bitcoin dev's and early adopters really gets the one-shot concept of addresses - possibly rightly so - keeping issues of it lowering levels of anonymity etc out of the discussion - it doesn't fit with the mindset people have - it's difficult enough getting merchants to setup separate addresses for each client, one per transaction is simply a waste (of addresses, storage, blockchain size, numnber of inputs|outputs when spending etc) I'm sure the wife would love a new handbag everytime she gets some money, but the real-world just isnt like that ;) Addresses are perceived as the equivalent of a jar you stick your coins in. You can have lots of jars. Each jar can be for a specific reason or whatever, but the analogy is there. Wallets are like a box you keep some of your jars in. With the added interesting concept that a jar can be in multiple boxes at the same time. Only the person with the right 'key' can open the jar and take the contents. However unlike the 3 money boxes I have behind me right now - which i can take 1 single penny out of one and put it into another - if I want to move bitcoins from one addresses (jar) to another *of my own* I have to pay a fee. Worse still if the jar doesnt have much in it I'm denied that ability. End user will neither understand why or want to pay the fee, for dealing with their own coins. If a jar breaks I can just tip the contents into a new one - unless I'm very careless, the amount in the new one = the amount in the old one - people will want/need it to work like that. Similarly if you do have all these addresses around, you may want (as good housekeeping) discard some of them (after moving the cash). So having the ability to specify address to send from is essential (and a sadly missing feature of the QT client) 'intra-wallet' transfers with an 'also discard the sending address' would be a way of (once confirmed) stopping any further use of that address (denied any further transactions by miners ?) and when balance-at-point-in-time is implemented, a way of shrinking the storage for all other bitcoin users (who chosse not to have a full transaction set). If i send luke 10, and luke sends me back 3, i have 3, luke has 7. If luke sends me 2, and i send luke 1, i have 4 and luke has 6. To verify my ability to send jeff 4, all that is needed is to know that I have 4, not all the transactions that led to that state - thats how its done now, thats not necessarily efficient as bitcoin grows If luke sends me 4 more, i now have 4 again, luke has 3 If i send 1 to each of the children, they have 1 each (*4) Having a 'family' wallet means when on holiday they can have that rental of quad-bikes - to send the rental company 4 the client only needs to know that those addresses now have 1 each in them, not all the previous transactions - if they didnt exist at the point-in-time balance, then yes, it would need to know about the luke>rob>kids transactions, but thats all I moved to a new netbook recently - it took 140 *hours* to d/load and process the blockchain (yes the wifi was that bad), I heard from one of our clients that (although they only had the client running during working hours) that to their desktop it was over 9 days before it had caught up. If all I was d/loading were the transactions since the last difficulty change (as one example of a fixed point), and the remaining balance on any not-discarded address as at that point it would have been much much quicker, and not be shagging my shiny new hard drive. There's more but it's 4.45 in the morning, and I cant think coherently until after a few hours kip and some good coffee :) Rob ------------------------------------------------------------------------------ Learn the latest--Visual Studio 2012, SharePoint 2013, SQL 2012, more! Discover the easy way to master current and previous Microsoft technologies and advance your career. Get an incredible 1,500+ hours of step-by-step tutorial videos with LearnDevNow. Subscribe today and save! http://pubads.g.doubleclick.net/gampad/clk?id=58041391&iu=/4140/ostg.clktrk _______________________________________________ Bitcoin-development mailing list Bitcoin-development(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5

1 0

Scott Aaaronson: NSA: Possibly breaking US laws, but still bound by laws of computational complexity
by Eugen Leitl 09 Sep '13

09 Sep '13

http://www.scottaaronson.com/blog/?p=1517 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’s “black budget,” contained the following enigmatic line from the Director of National Intelligence: “We are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” So, the journalist wanted to know, what could these “groundbreaking” capabilities be? And in particular, was it possible that the NSA was buying quantum computers from D-Wave, and using them to run Shor’s algorithm to break the RSA cryptosystem? I replied that, yes, that’s “possible,” but only in the same sense that it’s “possible” that the NSA is using the Easter Bunny for the same purpose. (For one thing, D-Wave themselves have said repeatedly that they have no interest in Shor’s algorithm or factoring. Admittedly, I guess that’s what D-Wave would say, were they making deals with NSA on the sly! But it’s also what the Easter Bunny would say.) More generally, I said that if the open scientific world’s understanding is anywhere close to correct, then quantum computing might someday become a practical threat to cryptographic security, but it isn’t one yet. That, of course, raised the extremely interesting question of what “groundbreaking capabilities” the Director of National Intelligence was referring to. I said my personal guess was that, with ~99% probability, he meant various implementation vulnerabilities and side-channel attacks—the sort of thing that we know has compromised deployed cryptosystems many times in the past, but where it’s very easy to believe that the NSA is ahead 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’ve guessed even less than 1% probability 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’t 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’s ever been. So, how did my uninformed, armchair guesses fare? It’s only halfway 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’s Web site in June. “Properly implemented strong crypto systems are one of the few things that you can rely on,” 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… Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware… Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method. 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, discovered 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 “a challenge in finesse.” So, in pointing to implementation vulnerabilities as the most likely possibility for an NSA “breakthrough,” I might have actually erred a bit too far on the side of technological interestingness. It seems that a large part 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’t mathematical cryptography’s fault—any more than it would be mathematical crypto’s 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 information it does—by “beating crypto in a fair fight” (!) or, more likely, by exploiting backdoors that it itself installed—the mere fact that it collects so much is of course unsettling enough from a civil-liberties perspective. So I’m glad that the Snowden revelations have sparked a public debate in the US about how much surveillance we as a society want (i.e., “the balance between preventing 9/11 and preventing Orwell”), what safeguards are in place to prevent abuses, and whether those safeguards actually work. Such a public debate is essential if we’re serious about calling ourselves a democracy. At the same time, to me, perhaps the most shocking feature of the Snowden revelations is just how unshocking they’ve been. So far, I haven’t seen anything that shows the extent of NSA’s surveillance to be greater than what I would’ve considered plausible a priori. Indeed, the following could serve as a one-sentence summary of what we’ve 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—that assumption being 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’s 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 computer science’s academic teacup. As many readers of this blog might know, Neal Koblitz—a respected mathematician and pioneer of elliptic curve cryptography, who (from numerous allusions in his writings) appears to have some connections at the NSA—published a series of scathing articles, in the Notices of the American Mathematical Society and elsewhere, attacking the theoretical computer science approach to cryptography. Koblitz’s criticisms were varied and entertainingly-expressed: the computer scientists are too sloppy, deadline-driven, self-promoting, and corporate-influenced; overly trusting of so-called “security proofs” (a term they shouldn’t even use, given how many errors and exaggerated claims they make); absurdly overreliant on asymptotic analysis; “bodacious” in introducing dubious new hardness assumptions that they then declare to be “standard”; and woefully 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, the judgments of mathematicians with … taste and experience, who can just see what’s likely to be vulnerable and what isn’t. 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 tangle 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—even if the steps seem obvious or boring. Any time anyone has tried to do that, it’s been easy for the natives of the unruly wilderness to laugh at the systematizing newcomers: the latter often know the terrain less well, and 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’m dredging up this old dispute now, is that I think the recent NSA revelations might put it in a slightly new light. In his article—whose main purpose is to offer practical advice on how to safeguard one’s communications against eavesdropping by NSA or others—Bruce Schneier 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 “merely” ensure that NSA or other interested parties weren’t providing input into which elliptic curves to use. But I think there’s also a broader issue: that, in cryptography, it’s unwise 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—that 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—now looks close to an established fact. In cryptography, then, it’s not just for idle academic reasons that you’d like a publicly-available trail of research papers 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’s final piece of advice is this: “Trust the math. Encryption is your friend.” “Trust the math.” On that note, here’s a slightly-embarrassing confession. When I’m watching a suspense movie (or a TV show like Homeland), and 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 ⊂ P/poly would collapse the polynomial hierarchy, and I can tell you exactly why. It would likewise be the case that you couldn’t break the GGM pseudorandom function without also breaking the underlying pseudorandom generator on which it’s based. Math could be defined as that which can still be trusted, even when you can’t 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 from your own site. 24 Responses to “NSA: Possibly breaking US laws, but still bound by laws of computational complexity” Aaronson on crypto. Schneier “elliptic-curve systems; the latter have constants that the NSA influences when they can.” | Gordon's shares Says: Comment #1 September 8th, 2013 at 1:22 pm […] Link. Trust math, but not NSA mathematicians. […] Douglas Knight Says: Comment #2 September 8th, 2013 at 1:35 pm Could you be more specific about what you mean by the hypothetical “big improvement” 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’t break all instances, but, as has 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’s condemnation of ECC seems to require more than 1% chance NSA knows something special about ECC. PS – David Jao, commenting on Schneier’s 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’s easy.) Anonymous Says: 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’t relate to the practice and we know many of our standard models are not good enough approximation of the reality and arguably there isn’t 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: 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’t grok the entire mathematical arguments for each cryptographical system, or doesn’t 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’ work and sit on standards committees, not to mention the programmers who implement it in code, what are we to do? Daniel W. Says: Comment #5 September 8th, 2013 at 2:33 pm In my mind, the best circumstantial evidence that the NSA has not practically 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: Comment #6 September 8th, 2013 at 2:43 pm Scott, ” … the clarity and rigor of the systematizing approach has eventually won out.” No doubt. In Euclid’s time as well as the present, though, it is helpful to have something to systematize. Making that assumption available and convenient is what mathematicians do. Scott Says: 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 … 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’t gone through every detail of the math used by the crypto in my web browser, and I dare say that most professional cryptographers haven’t either. For another, the point is much broader than cryptography: how can you trust quantum mechanics, if you haven’t done the requisite experiments yourself? The physicists could’ve all been bought off by some anti-realist cabal. :-) Or how can you trust that the government isn’t putting mind-control drugs into the fruit you buy in the supermarket, etc. etc. So we’re extremely lucky that science hit on a solution to these problems—the only workable solution, really—back in the 17th century. The solution is to open up every question to scrutiny, discussion, and challenge by any interested person. Assertions gain credibility by surviving public criticism—and that’s just as true in math as it is in experimental sciences. I believe many theorems even though I haven’t checked the proofs myself, because I know that if there were an error, then someone else could’ve 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 would only tell their friends, then that doesn’t do me any good. That’s why the dividing line between “crypto as black art” and “modern crypto” 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: Comment #8 September 8th, 2013 at 3:20 pm Unfortunately, this xkcd.com/538/ had it right imho. Scott Says: 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’s all elaborate psychological warfare, to prevent us from discovering the fact that these cryptosystems were broken? And that even Snowden himself is part of the NSA’s master 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’t believe any conspiracy theories—as in zero, not one. Scott Says: Comment #10 September 8th, 2013 at 3:32 pm Douglas Knight #2: Sure, dramatic improvements in elliptic-curve algorithms would certainly count—as would “merely” subexponential algorithms, were the improvements large enough to threaten key sizes that the academic cryptographers considered safe. More broadly, though, you’re entirely right that there’s not a sharp line between “improved number-theory algorithms” and “implementation vulnerabilities.” Often, what’s happened in practice is that 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 “99%” part of my probability estimate. In the “1%” part, I really had in mind “something that would give theoretical cryptographers a heart attack” (like, I dunno, factoring in L(1/10), or elliptic curve discrete log in quasipolynomial time). Scott Says: 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’ve read pretty much all of his and Menezes’s anti-TCS screeds, and to me what he’s doing seems, if you like, too easy to be helpful. Koblitz’s favorite M.O. is to recount various slip-ups by people in the “Goldreich school of crypto” and laugh at them: “haha, they talk about ‘provable security,’ but there was a bug in their proof! or their security definition left out an important class of side-channel attacks!” Then, with even more glee, Koblitz relates how the hapless computer scientists put out a new paper 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’s 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’s not that instead of adaptive chosen ciphertext attack, he has a better definition to propose, or that instead of “bodacious” new hardness assumptions, he can give a single assumption that suffices for everything. Instead, what he appears to want is simply a return to the “black art” era of cryptography, when security arguments boiled down to “we tried to break it and failed” or “trust us, we have better mathematical taste than you.” The trouble is, I can’t think of a single case in the history of science when mathematical foundations as well-developed as cryptography’s now are, were simply abandoned wholesale without better mathematical foundations to replace them. So intellectually, Koblitz strikes me as someone who’s throwing spears at battle-tanks. Being the excellent marksman that he is, he actually scores some hits—but 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’t relate to the practice and we know many of our standard models are not good enough approximation of the reality and arguably there isn’t enough effort to deal with these issues. Would one also say that the mathematical foundations of topology—open sets, Urysohn’s Lemma, etc.—are useless if they don’t relate to the practice of tying and untying knots? I think that’s a pretty close analogy for the relationship between what, say, Goldreich or Goldwasser or Micali do, and the actual practice of cryptography. In both cases, yes, there’s some relation between the intellectual foundations on the bottom 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’t know is whether 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—in which case, the strongest case in their favor might be stronger than the strongest case that can ever be made publicly. The fact that President Obama, who’s so reasonable on so many issues, has 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’s actions had always been 100% justified, I’d still want them to be more accountable to the public than they are now. “Trust that we have our reasons, even though we can’t tell you what they are” simply doesn’t 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’t been). Anonymous Says: 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 crypto and go back to purely engineering art treatment. Regarding reasonability of what NSA does, NSA and its backers would of course claim these tools are useful. To be honest, security was a weak point of Obama’s campaign, he is not really knowledgeable in these issues and 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 have 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’s 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’s power). I don’t see why so much 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, … cases demonstrate). And even when courts find that someone 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 law 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, and Games Group Says: Comment #13 September 9th, 2013 at 2:16 am […] the aid that cstheory can offer to biological understanding. In yesterday’s post on the NSA and computational complexity, Aaronson — with attribution to mathematician Greg Kuperberg — provided the following […] Paul Beame Says: 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′s, particularly after the publication of The Puzzle Palace, 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’s Endicott House in June 1985 with one or two official NSA attendees. At the time, there were one 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: “If you are interested, just mention it in a phone conversation with one of your friends and we’ll get back to you.” This didn’t exactly endear them to anyone. J Says: Comment #15 September 9th, 2013 at 2:51 am “Math could be defined as that which can still be trusted, even when you can’t trust anything else” Wait till someone shows multiplication and addition have same complexity or possible Voevodsky’s/Nelson’s worst nightmare comes true Refer: http://mathoverflow.net/questions/40920/what-if-current-foundations-of-math… http://mathoverflow.net/questions/36693/nelsons-program-to-show-inconsisten… Scott Says: Comment #16 September 9th, 2013 at 4:20 am J #15: Multiplication and addition having the same complexity (and yes, it’s conceivable that there’s a linear-time multiplication algorithm) wouldn’t do anything whatsoever to undermine my trust in math—why would it? Also, even if ZF set theory were shown to be inconsistent (and it won’t be :-) ), that wouldn’t do anything whatsoever to undermine my trust in theorems about (say) finite groups, or low-dimensional topology, or theoretical computer science—in fact, about anything that doesn’t involve transfinite sets. It would “merely” tell me that there was a need (and, of course, an exciting opportunity) to rethink the foundations. That’s 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: Comment #17 September 9th, 2013 at 4:58 am I agree, Scott, with your general position that any time one claims that “evidence for x is really evidence for a powerful cabal trying to prevent everyone from discovering not(x)” one’s credibility drops by an irrecoverably large factor, and I agree with you that “math can be defined as that which can still be trusted, even when you can’t trust anything else” (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 “open up every question to scrutiny, discussion, and challenge by any interested person” may be necessary in order to establish public trust, it isn’t sufficient because we still have 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 “Snowden himself is part of the NSA’s master plan” (as you playfully alluded to)? To that end you may be interested in Why Doesn’t the Public Trust Scientists?, a lecture by The Right Honourable Professor The Baroness O’Neill of Bengarve, Emeritus Professor of Philosophy at the University of Cambridge and past Principal of Newnham College, Cambridge, which she presented in 2005 as part of the Science Futures series by the San Diego Science and Technology Council’s Center for Ethics in Science and Technology. Note that while “scientists” are the titular and exemplary referent matter in that lecture, Baroness O’Neill’s talk actually considers a range of questions in regard of public trust, including the roles of professional organizations, trustworthiness (which can’t replace trust because of the quis custodiet 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’Neill argues, if I may be so bold as to suggest a précis, that going back through the 17th century (as you noted) western liberal democracies have indeed evolved a multipartite methodology that does tend work in practice and 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 are applying those techniques to your vaunted Agency in particular. Scott Says: Comment #18 September 9th, 2013 at 5:01 am Paul Beame #14: I’ve actually heard that joke many times, in other variants. (“Interested in career opportunities at the NSA? Call your mom and let her know!”) I didn’t know that NSA people themselves used the joke at conferences, but it doesn’t surprise me at all. J Says: Comment #19 September 9th, 2013 at 6:39 am “Multiplication and addition having the same complexity (and yes, it’s conceivable that there’s a linear-time multiplication algorithm) wouldn’t do anything whatsoever to undermine my trust in math—why would it?” 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: 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 wrong. 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: 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ürer, and building on many previous works), and it hasn’t 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 Ω(n). I suppose I’d guess that Ω(n logn) is some sort of barrier, but not with any strength of conviction: if a linear-time algorithm were discovered, it certainly wouldn’t cause me to doubt the consistency of ZF set theory. :-) Scott Says: Comment #22 September 9th, 2013 at 7:16 am Vitruvius #17: it remains unclear to me … how effectively you folks in the United States of America are applying those techniques to your vaunted Agency in particular. As long as we’re trading mild national barbs, you’re Canadian? You guys do have the Communications Security Establishment, which according to the NYT article is one of only four foreign agencies (along with Britain’s, Australia’s, and New Zealand’s) that “knows the full extent” of the NSA’s decoding capabilities and is cleared for its “Bullrun” program. Though I confess that, when I try to imagine Canada’s CSE, I come up with something like the following: Read this gentleman’s private email? Ooo, nooo, that doesn’t sound terribly polite, eh? J Says: Comment #23 September 9th, 2013 at 7:21 am Professor I am well aware of all $n^{1+\epsilon}$ algorithms and Schonage’s $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 – $Z$ has been a puzzle before as well – it is the simplest ring with a spectrum of prime ideals whose dimension is unclear to be interpreted in a standard way) Scott Says: 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 (“Actual actual reality: nobody cares about his secrets”).

1 0