New NSA leaks: does crypto still work?




No cryptosystem has ever been able to withstand a determined attack by an adversary with the resources of a nation-state. Ordinarily, however, a nation-state brings those resources to bear only against its adversaries in time of war. Nowadays, however, it appears that our nations are at war with everyone: other nations, disfavored corporations, their own citizens, even internecine conflicts among their own leaders. At war with everyone, and always.

Reading our communications is only part of it. Demanding our papers, seizing our assets, searching our persons, imprisoning the innocent, summary execution in the streets. Western governments are guilty of all of the above.

And their citizens are cowed into either believing, or at least arguing loudly, that their warlords must have that kind of power in order to defend their nations against their enemies. Sometimes the warlord is worse than the enemy.

Tribalism and feudalism appear to be the only two forms of government that last.


Crypto itself does work. The key management system is what failed here.

I think authenticated Diffie-Hellman key exchange with session keys should be immune to the certificate compromise, as the cert itself is used only for signing the negotiated keys. Knowledge of the signing key may be of little help to Eve the Eavesdropper here. (Can anyone confirm or deny this, please? My crypto-fu is good only enough to be aware of how weak my knowledge is.)

The widespread compromising of certs, and of the staffs of the corporations, may also explain why the DH-whatever cipher suites were so underutilized, more than the little additional effort needed would suggest.


Sounds like a cogent argument for disposing of government!


What happened to Cory’s other post about 31C3? I have been enjoying these talks.


There are just enough-but-not-quite-enough details in the docs to know for sure. My suspicion is the NSA knows a few implementation details that may be weak, like maybe a weak seed generator (she has that ever happened). Or perhaps an analogous attack that the NSA helped protect against with DES.

But those are just guesses. It would certainly be easier just to get one of the NSAs bright stars hired on at RSA. Why break math when you can break weak operational security?


Ah, here we go. It is exploitation of implementation details of the key exchange. And it includes ssh.

Analysis of TOYGRIPPE and XKEYSCORE data, as well as from “daily VPN exploits,” is fed into BLEAKINQUIRY—a metadata database of “potentially exploitable” VPNs

Hopefully no one else, like the RBN knows of these exploits!

–edit 2–

Aaaand here is the operational security reference.

In cases where the keys just can’t be recovered, the VPN Exploit Team will “contact our friends for help”


Yes, the problem identified in that slide is that the Feds have access to the private keys of many major websites, so they can recover the session keys for your communications with them and eavesdrop directly (as opposed to requiring those websites to let the Feds see your transactions.)

Authenticated Diffie-Hellman reduces the problem - somebody who knows the target’s private keys can still run an active man-in-the-middle attack, so instead of Bob exchanging a key with Amazon, Bob is talking to Eve (who’s signing her key parts with Amazon’s keys), and Eve is talking to Amazon (pretending to be Bob, but since Amazon only authenticates Bob using login/password, not crypto or IP address or whatever, that half isn’t very hard.) There are ways to reduce that risk as well (sending the keyparts in two authenticated halves, or sending a hash first, etc., and checking that both Amazon and Bob have the same session key), but those only work if you check.

Active MITM attacks are a lot more work to set up (even if the eavesdropper has control of the communications in the middle, such as some cracker in your local coffee shop Wifi, or the NSA telling telecom companies what to do), and they have to be done in real-time, not after the fact, and they’re easier to detect.

What Authenticated Diffie-Hellman is really good for is preventing the “government requires you to hand over your crypto keys” attack - it’s a lot easier to argue in court that the government shouldn’t be able to impersonate you than that to argue against a law that says you have to hand over the keys they required you to retain.


Whoever was responsible for making that slide set missed the opportunity of making it Jeopardy-themed.


I know what you are getting at, but given the practical application of that scenario–i.e.the FISA courts reject literally one of of a thousand requests–i wouldn’t hold my breath.

But it is the undisclosed vulns against ssh and other common protocols that really makes me mad. Not disclosing a flaw in ssh means you have literally failed as a human, and a very special place in hell has been reserved.


…and I am out of likes…

The hopeful thing is that if one can see it, many others can see it too. Spotting a vulnerability is something many can do. (Arcane non-obvious ones are a different can of worms, though. The possibility of these and their impact is best to be mitigated by conservative design and compartmentalization.)


Regardless of what the Man in the Middle is up to, we use a dozen or so kernels between us and about the same number of user agents. The software is delivered on line through common channels. We can check the MD5s to our hearts content but it won’t tell us if that critical back door is hidden away in there.


Seriously. Spy agencies are going to spy, but this is threatening the technological viability of the country the NSA works for. And the icing on this crap cake is there are the people that know secrets can’t be kept forever.


I am dreaming of an open source project that does nothing but reviewing code, never producing a single line.


But who reviews the reviewer?


That’s precisely why the breakdown in trust here is so troubling. As I mentioned previously the NSA has been responsible for improving encryption.


I think ideally reviews should be as negative as possible. No fixes, no endorsements. That should at least help minimize additional risks.

And of course there are always the developers of the software. One hopes that they keep an eye on their code, too.


Web-of-trust of reviewers reviewing reviewers?

That said, what about some domain-specific language for crypto systems? Something higher-level than C that would translate to C (or be compiled on its own or run as bytecode), designed with formal verification in mind, trading performance for security (e.g. scrubbing memory on alloc and dealloc, so there can not be anything left over there, mitigating things like heartbleed) which in today’s hardware is not a problem?


At this point it is clear that the NSA has not been working in OUR best interests for some time. They have been effectively attacking things we depend on. Their most dangerous attacks have been to add features, complexity and compatibility to our crypto implementations. They have also guided the direction and perception of of security and crypto in ways that favor them instead of us.

One of the biggest missing bits in our current arsenal of crypto tools is we have blindly turned away from simple, secure communication channels using predistributed keys or one-time pads.

We need a simple, secure alternative to SSH for system administration. It should NOT negotiate protocols or parameters. It should simply enable trusted communications and control between an admin and his equipment. It should only use well tested symmetric crypto. It should only use large, pre-distributed keys or one-time pads. This is simply making available well understood and tested concepts that have been used for decades in secure phones.

A small team of good programmers + Dan Bernstein could probably have something much more secure than SSH available in a month.


Random thought.

Generate a list of n 256-bit random numbers, a list A. Generate a list of hashes of these numbers, a list B. For each item on the lists, generate also a 256-bit random number (the shared key, let’s name it K) and store it paired to the number in both A and B. On the server side, store list B. List A goes to the client.

When connecting, offer the A[n] value. The server calculates the hash, compares with list, retrieves B[n] (or says that the value was already used, and another has to be tried, in case the tables get desynchronized). On successful authorization, the K[n] keys are retrieved, encrypted connection is established, the A[n]:K[n] and the B[n]:K[n] pairs are securely wiped, and the K[n] stays in the RAM only until the end of the transaction.

(Possibly the server can remember the B[n] values, to tell the client that that key pair was already spent, to avoid trouble in syncing.)

A man-in-the-middle may intercept the encrypted conversation, but without the K (which never goes through the wire) has just a bunch of garbage. (Though the size of packets going back and forth and their timing may also tell something of value.)

The lists can be regenerated and synced between the client and the server by using e.g. the USB Armory gadget described here earlier, or a Raspi programmed for that purpose, or whatever. (Beware of flash memories, secure wiping may be problematic due to the sector remapping/wear leveling. A serial EEPROM may be a better bet here, due to the more deterministic assignment of address to physical memory cell, so red data aren’t just wandering around. Attaching such chip to the SMBus bus can be done by e.g. a dummy DIMM module - strip memory chips with hot air, replace the EEPROM with (say) 64kB one, and you’re golden. An I2C-slave microcontroller can be made to emulate the EEPROM, with added features like data access locking and limited number of tries. With battery backup and some switches/sensors it can be made even tamper-resistant.)


Hi Shaddack. That has some neat ideas. I liked the idea of separating the numbers and their hashes. And the self indexing key lookups are elegant. But, I think it would be more robust to be brutally simple. I am not a crypto guy. I am a security guy. I was a protocol guy. So, I tend to favor stark simplicity. This probably won’t work but, here is how I would approach the project of trying to create a simpler and more resistant SSH for system administration:

The goal of this tool should making security and defense easier and cheaper, If we can, we should also try to make attack more expensive.

Every project needs a snappy name. How about Secure Trusted Administration (STA).

One way to resist feature creep (and NSA manipulation) is to clearly define the goals and what is in scope and what is not in scope. For STA that would look like:

  • Features must be the minimum necessary to securely connect to and manage your own equipment.
  • Features must eliminate complexity from the crypto implementation.
  • Features must eliminate complexity from the communications.
  • Features must increase security.
  • Features must increase audibility.
  • Features must limit the exposure of a single compromise.
  • Features must increase robustness and reliability.
  • Efficiency is a lesser goal. Efficiency concerns may not impact the more important goals.
To me, STA looks like the well solved problem of secure phones. They have had simple, robust implementations for years. Their implementations look nothing like SSH. The more secure phones favor symmetric key encryption over more complex public/private key crypto. The simplest and most robust use a single pre-shared key, or a sequence of pre-shared keys that work like a one-time pad. They never trust random public keys from unknown people.

We have been told that secure phone approaches are too difficult and expensive for our needs. I think we are being mislead. Those old designs look like the cheapest, easiest way to create a secure channel for our own equipment. We have no problem with creating and distributing keys or one-time pads. We already touch all the equipment. If we want, we can even distribute a different key/pad for each managed box.

General Administrative overview of STA:

  1. Don't try to do a gui. Start with a command-line tool. The necessary functionality is to issue orders, see results and transfer files.
  2. Since this is for administration, we don't need or want to implement privilege elevation in the listening process on the managed equipment. The listener always runs as root/admin. The listener should not allow influence from other processes running on the managed box. The listener should not listen to the loopback interface. The listener should only listen for authenticated instructions from the remote admin. The listener does not need or want unprivileged or read/only functionality.
  3. That said, it is beyond the scope of this project to try to retrofit file system security. We will flag our secret files to only be accessible by root. If something on the box can defeat file system security, we have already lost the box and the keys.
  4. It is beyond the scope of this project to try to retrofit memory security. We should take normal measures to make the listening processes memory untouchable by unprivileged processes. But, if something on the box can directly access all memory, we have already lost the box and the keys.
  5. If somebody hacks a managed box, we can limit the spread by limiting the influence of the shared keys. We can limit contamination by eliminating complexity in the connection and reducing the chance of having programming errors in the input processing. We can limit the influence of a listening process over a sending process.
  6. The sending/commanding process should be as close to privilege free and read'only as possible. It needs to understand the communication protocol. It needs to implement the crypto. But it doesn't need to run all the time. When it is running, it should only have as much access as it needs to do the current task.

Protocol goals of STA:

  1. Don't negotiate anything. If we want to change something, then refresh the managed box with updated code and keys.
  2. The lower layers of the communication protocol should be stateless. Each message is self contained, encrypted, and authenticated.
  3. If we use symmetric crypto, we can cheaply create lots of keys using a good source of random noise. Then we can predistribute them. Memory is cheap. Flash is cheap.
  4. Trying to limit the size of keys is a false saving.
  5. Trying to extend the lifetime of a key is a false saving.
  6. Trying to limit the number of keys is a false saving.

Proposed details of creating a pre-distributed keyfile for STA:

  1. Make a big keyfile. Put several fields at the start: GMT time-stamp when this file was created; FileID for this file (This could just be a random 1024 bit value); Copy Number; Human readable name for this file.
  2. Add enough keys to change keys every minute for 5 years. This takes about 2635200 keys. If each is 1024 bits in size, the keyfile is less than 400 Megabytes. Make 2 copies of the keyfile. Update the first to be Copy #1 (Commander). Update the second to be Copy #2 (Listener).
  3. If we distribute this file to multiple managed devices, the listeners need some way to authenticate the commander. Generate another 2635200 pieces of random data. We will use these as passwords. They can be smaller. Maybe 512 bits in size. Select a good crypto hash function with an output size of 512 bits. Hash each password. Add the original 2635200 passwords to the Commander copy. Add the 2635200 password hashes to the Listener copy. Now the key files are about 600 megs in size.
  4. Distribute the copy of the Commander keyfile to your desktop/laptop. Distribute the Listener copy to each managed device. Update the copy count for each additional Listener.

Proposed message format for STA:

  1. Each message is shipped out and delivered in a single UDP packet. They are all the same size. After encryption, each message should be 1400 bytes. The size of the unencrypted message will depend on the expansion factor of the chosen encryption method.
  2. All the message formats are similar. The fields are: Number of non-padding bytes in message; Timestamp; Message #; From (Copy #); To (Copy #); Message Type; Optional Password (if received by Listener); Data; Optional padding; Checksum.
  3. Message #: is a 64bit counter that increments every time you send a message.
  4. Message Types: are a 16bit INT that defines things like: ACK, NAK, Please Repeat; Upload, Download; Execute and Report result; Report; Continue Command; Continue Report; Error; Report Attack; Switch Keyfile; Wipe Keyfile.
  5. Optional padding: are padding necessary to fill Message. Use repeated copies of the most recently discarded key for padding.
  6. Checksum: This validates that the decode was successful. Better use a robust checksum.

Proposed implementation of protocol for STA:

  1. When STA is launched, you indicate the acceptable receiving time accuracy window. This should probably not be more than a minute or two.
  2. Every time a message is sent or received: STA validates it's clock. If time gives an indication of running backward, exit with an error.
  3. Then, STA uses current time and calculates which key to use. Keys are discarded every minute, starting at the stored creation time of the keyfile. So, you just need to figure out how many minutes since the keyfile was created.
  4. Messages are always encrypted and sent using the current key. Once messages are sent, details about that message are added to the audit log.
  5. Each STA instance (both Listener and Commander) must have a maintenance process that overwrites and wipes any key info (both key and password/hash) that is older than 3 minutes or 3 times the Acceptable Time Window (which ever is greater.)
  6. If the Message Type of the sent message requires an ACK, then the sender places the message into a pending pool. Messages are removed from the pending pool if they receive a timely ACK. Once the Acceptable time window for each pending message has past, it is resent. Unmatched ACK's are discarded. Each discard increments your bad message counter.
  7. When messages are received, first you check their size and discard any that are not the right size. Each discard increments your bad message counter.
  8. When STA receives a properly sized message, it attempts to decode the message using the current key. If that fails, try each key within the acceptable accuracy range. If they fall with the acceptable receiving time window, we probably want to try the immediately older key, then the immediately newer.
  9. First test is to validate the checksum. Then you validate all remaining fields (including the padding) before acting on any of them. If any fail to validate, discard the message and increment the bad message counter. Careful validation should detect and eliminate duplicate messages due to network craziness or replay attacks.
  10. Next, if you are a Listener, verify that your calculated hash of the presented password matches your stored password hash for this key. If it does not match, then it is likely that the Keyfile has been copied from another Listener and you are under attack. Wipe the stored keyfile. Try to send a last Error message to your Commander. Generate critical error messages. Terminate.
  11. Check the Message # and see if you are missing messages. If any are missing, flag them to be NAK'ed if they have not shown up by the end of the acceptable time window.
  12. Send an ACK message to the other side for this message if appropriate for the received Message Type.
  13. Log details of the received message in the audit log.
  14. Process the message.

As you can see, this is crude, ugly, inefficient and slow. It should be simple to implement. It should be very robust. It should be easier to analyze. It may be much harder to attack than current SSH implementations.