Friday, 3 January 2014

NSA quantum compute efforts

The Washington Post published an article and references regarding some NSA sourced Quantum cryptography efforts.

This is both reassuring and disturbing.

Looking at planet Earth, there are only three types of public key encryption used:  RSA, Diffie-Hellman & Elliptic curve. That's it. Just three. We have no other tricks in the toolbox yet for public key cryptography. A quantum cryptographic breakthrough by a true quantum computer, via Shor's algorithm, would break them all.

The NSA revelation is unsurprising but also a bit disturbing as they were working on the matter obviously industriously. One of the Washington Post papers was dated 21 September 2011. Schrödinger's cat is probably still in the bag, or box, but you'd think they would have made at least a bit of progress over two years, especially considering the good progress D-wave has made in that time with a much more limited budget.  D-wave's system is quantum-like, subject to much debate, and incapable of yet doing anything approximating Shor's algorithm.

It's not clear what the effect on symmetric ciphers may be but Grover's algorithm is the best hope there which, to date, means that symmetric ciphers are safe with perhaps modest key size improvements. Early daze, so who knows for sure. The NSA outpoints the rest of the world combined on crypto brain power and we are already a bit scared they might have some fancy secret algebraic attack on AES, so who knows indeed. We shouldn't rely on what we can't mathematically prove.

So whilst the quantum computing aspect is disturbing as it will break all public key crypto, I find the NSA revelations reassuring as:
  • it is unlikely, indeed very unlikely, they would have a functioning system by now; 
  • they have surveyed the state of the art with their omniscience and no one else seems to be there either; and,
  • perhaps most importantly, they want to do it to break hard public key crypto which means they haven't broken public cryptography and they still rely on weak systems and key theft.
So good news. Good public cryptography still works. It may be broken once quantum compute functions with enough qubits, but for some version of now since 2011, we're OK. When quantum qubits break public key crypto then perhaps it will only be for targeted attacks as quantum computers are unlikely to be cheap for a while.  Breaking all of google via their public key may be bad but smaller players would not be caught in a dragnet as they are now.

We should be reassured that governments and their apparatus are incompetent in the short term, but disturbed by the fact that their hierarchy and command-control organisation makes them asymptotically competent in the medium to long term.  That is, if they don't do the Roman thing and ebb away to a failed state, they will inefficiently grind it out and get there eventually if it is possible.

The only provably secure way to send data is via a one time pad. That's it. Nothing else is provably secure. You should pause and think about that for a moment.

Perhaps it is time to adopt the widespread use of one-time pads with enveloped PKI message exchanges (with optional obfuscation and entry-point protection via on-ramps such as TOR) to reduce the key distribution problem to a tractable issue. Simplifying the problem and reducing crypto cost and angst to simple physical key delivery or deliveries, with optional read once mechanisms, would let many sleep at night better and perhaps reduce overall crypto system cost. Then the focus may become the physical aspects, traffic analysis and legal protections, such as deflecting the Tailored Access Operations of your favourite adversary.  These things already matter, but by using one-time pads we may perhaps stop being mesmerised by the crypto distraction and focus on the real world.

Swift, as an NSA hackee, certainly needs to think about the economics of a one-time-pad infrastructure. Swift needs to plan for PKI breaking and there is only a couple of thousand transaction partners. Their financial transactions are the obvious high-valued transaction space to explore for such a change. Perhaps the economics of read once key distribution will stack up best for Swift or the next bank sponsored transaction network that replaces a Swift that refused to change.

It's time to go back to the future. One-time pads for all.


PS: Lattice based methods and Multivariate cryptographic methods may save us in a post-quantum cryptography world and these public-key methods seem the best candidates so far from the Post-Quantum Cryptography conference series.


  1. The NSA is funded to do this kind of research and half a F-22 was not a lot in 2011 as Antipater pointed out in slashdot. They would be remiss not to do it.

    The biggest problem is the breaking of the trust of the people, not crypto. The current violations of the Fourth Amendment make the retrospective application of quantum decode to the data they are meant to protect, and not break, disturbing in both a principled and mental sense.

    The NSA has a huge collection of data, your data, your companies data, to crack retrospectively that they have no Constitutional right to have. Its retention is illegal.

    Trust is like porcelain. Once it is broken, it takes some serious fixing.

    There is still [a] bull in your store. Should you fund the local farmer to bring another bull into your China store?

  2. In order to OTP to work efficiently, one needs a lot of quality random. Using Dual_EC_DRBG gives you random, but still NSA can crack it.
    Let's say you have good random source, how do you distribute it to your 700 fixed partner you want to communicate with? How do you ensure the NSA has not intercepted this while it is delivered?

    Bruce Schneier has it's own thoughts about OTP:

    To sum up: using OTP is not the solution...

  3. I think you're right that the traditional use of a OTP is not the solution, but I was meandering around a bit of a different application of a OTP.

    Whilst some domains, perhaps Swift, may justify the cost, the traditional OTP solution does not scale at it is a O(n^2) key distribution problem.

    Imagine this scenario. You get 1TB of random data to talk to your message broker (MB). Your message involves a PK negotiated cipher to protect it from your MB, perhaps with the symmetric encoding done twice with different algos (separately with an encoded random stream R and an encoded R xor'd data stream). Once the symmetric keys are established you could elect to go with less security and drop the OTP for the session to keep your OTP for important traffic.

    You only need one OTP which is used to talk to the MB. That way you only need one OTP and the problem is O(n) rather O(n^2) for key distribution.

    Here is a 2Gbps quantum random source. It is a fast one and Wikipedia lists a few more to suit a better budget. OTP distribution is from the MB.

    If your MB had NSA decrypt capabilities you might be in trouble, but say you trust them just enough to be not be the NSA. Only your inner encryption is transiently exposed to the MB.

    Part of my motivation is to force a tailored solution hack thereby raising the surveillance cost. Part of the motivation is also to get to a simpler solution that I can understand. Three years of ancient discrete math and a semester of crypto at uni in the 1980s is enough for me to understand RSA public-key but I'm out of date. I need to understand it to have trust. OTPs are easy and it is just a matter of having a truly random source. As you point out, not a compromised Dual_EC_DRBG, nor would I trust a pseudo random Fortuna. Random without pseudo please. That said, maybe Fortuna for the inner random pad for xor'ing where Fortuna was seeded from the outer pure random OTP could work as it still kinda results in breaking 2 crptyo systems to get at the inner data.

    I have a scheme in mind I call KOMPEST that assigns numbers to each level of an encryption system depending on the physical security, legal situation of end points and MB, MB procedures, OTP distribution or public key method, etc. Such a numbering system would let you know where you stand. For example, if you could trust that there were air gapped computers either end in properly guarded, physically secure and tempest sites within countries that don't allow access with physical delivery by trusted envoys of several OTP's XOR'd delivery by hard-to-read-more-than-once media would be close to the top of the tree. You work your way back from there by trading convenience and cost for security.

    Multiple methods for delivering OTPs can improve security but it is a bit of a fudge as it just raises the cost of a combined intercept. You could encode an FPGA solution to deliver a read once store in a tamper proof box to limit the avenues for a differential power analysis attack. Again, it just raises the cost.

    Part of my KOMPEST meandering contemplates using polling and multiple deliveries to disguise the traffic. The model doesn't include robust obfuscation of on-ramps such as that which a project such as TOR can provide. The world needs a project such as TOR to allow difficult to block access and there is no substitute for just having zillions of nodes but that is a separate problem to the domain my thought experiment is dealing with.

    There is no ultimate solution, a TAO, such as a couple of compromised employees guarding your data centre, or a person with a big enough gun who is willing to kick your door in, will always work.

    I think you could do a lot with a 1TB OTP and, perhaps, especially if you're a bank, save money.

    Thanks for the comment. Meanderingly yours,