On the NSA – Mirrored from A Few Thoughts on Cryptographic Engineering

In which I repost Matthew Green’s blog post in full, for everyone to read, no matter what Johns Hopkins decides to do. Full copyright is his, and the original should be available at http://blog.cryptographyengineering.com/2013/09/on-nsa.html. But either way, here it is.

Thursday, September 5, 2013

On the NSA

Let me tell you the story of my tiny brush with the biggest crypto story of the year.A few weeks ago I received a call from a reporter at ProPublica, asking me background questions about encryption. Right off the bat I knew this was going to be an odd conversation, since this gentleman seemed convinced that the NSA had vast capabilities to defeat encryption. And not in a ‘hey, d’ya think the NSA has vast capabilities to defeat encryption?’ kind of way. No, he’d already established the defeating. We were just haggling over the details.

Oddness aside it was a fun (if brief) set of conversations, mostly involving hypotheticals. If the NSA could do this, how might they do it? What would the impact be? I admit that at this point one of my biggest concerns was to avoid coming off like a crank. After all, if I got quoted sounding too much like an NSA conspiracy nut, my colleagues would laugh at me. Then I might not get invited to the cool security parties.

All of this is a long way of saying that I was totally unprepared for today’s bombshell revelations describing the NSA’s efforts to defeat encryption. Not only does the worst possible hypothetical I discussed appear to be true, but it’s true on a scale I couldn’t even imagine. I’m no longer the crank. I wasn’t even close to cranky enough.

And since I never got a chance to see the documents that sourced the NYT/ProPublica story — and I would give my right arm to see them — I’m determined to make up for this deficit with sheer speculation. Which is exactly what this blog post will be.

‘Bullrun’ and ‘Cheesy Name’ 

If you haven’t read the ProPublica/NYT or Guardian stories, you probably should. The TL;DR is that the NSA has been doing some very bad things. At a combined cost of $250 million per year, they include:

1. Tampering with national standards (NIST is specifically mentioned) to promote weak, or otherwise vulnerable cryptography.
2. Influencing standards committees to weaken protocols.
3. Working with hardware and software vendors to weaken encryption and random number generators.
4. Attacking the encryption used by ‘the next generation of 4G phones‘.
5. Obtaining cleartext access to ‘a major internet peer-to-peer voice and text communications system’ (Skype?)
6. Identifying and cracking vulnerable keys.
7. Establishing a Human Intelligence division to infiltrate the global telecommunications industry.
8. And worst of all (to me): somehow decrypting SSL connections.

All of these programs go by different code names, but the NSA’s decryption program goes by the name ‘Bullrun’ so that’s what I’ll use here.

How to break a cryptographic system

There’s almost too much here for a short blog post, so I’m going to start with a few general thoughts. Readers of this blog should know that there are basically three ways to break a cryptographic system. In no particular order, they are:

1. Attack the cryptography. This is difficult and unlikely to work against the standard algorithms we use (though there are exceptions like RC4.) However there are many complex protocols in cryptography, and sometimes they are vulnerable.
2. Go after the implementation. Cryptography is almost always implemented in software — and software is a disaster. Hardware isn’t that much better. Unfortunately active software exploits only work if you have a target in mind. If your goal is mass surveillance, you need to build insecurity in from the start. That means working with vendors to add backdoors.
3. Access the human side. Why hack someone’s computer if you can get them to give you the key?

Bruce Schneier, who has seen the documents, says that ‘math is good’, but that ‘code has been subverted’. He also says that the NSA is ‘cheating‘. Which, assuming we can trust these documents, is a huge sigh of relief. But it also means we’re seeing a lot of (2) and (3) here.

So which code should we be concerned about? Which hardware?

SSL Servers by OS type. Source: Netcraft.

This is probably the most relevant question. If we’re talking about commercial encryption code, the lion’s share of it uses one of a small number of libraries. The most common of these are probably the Microsoft CryptoAPI (and Microsoft SChannel) along with the OpenSSL library.

Of the libraries above, Microsoft is probably due for the most scrutiny. While Microsoft employs good (and paranoid!) people to vet their algorithms, their ecosystem is obviously deeply closed-source. You can view Microsoft’s code (if you sign enough licensing agreements) but you’ll never build it yourself. Moreover they have the market share. If any commercial vendor is weakening encryption systems, Microsoft is probably the most likely suspect.

And this is a problem because Microsoft IIS powers around 20% of the web servers on the Internet — and nearly forty percent of the SSL servers! Moreover, even third-party encryption programs running on Windows often depend on CAPI components, including the random number generator. That makes these programs somewhat dependent on Microsoft’s honesty.

Probably the second most likely candidate is OpenSSL. I know it seems like heresy to imply that OpenSSL — an open source and widely-developed library — might be vulnerable. But at the same time it powers an enormous amount of secure traffic on the Internet, thanks not only to the dominance of Apache SSL, but also due to the fact that OpenSSL is used everywhere. You only have to glance at the FIPS CMVP validation lists to realize that many ‘commercial’ encryption products are just thin wrappers around OpenSSL.

Unfortunately while OpenSSL is open source, it periodically coughs up vulnerabilities. Part of this is due to the fact that it’s a patchwork nightmare originally developed by a novice who thought it would be a fun way to learn C. Part of it is because crypto is unbelievably complicated. Either way, there are very few people who really understand the whole codebase.

On the hardware side (and while we’re throwing out baseless accusations) it would be awfully nice to take another look at the Intel Secure Key integrated random number generators that most Intel processors will be getting shortly. Even if there’s no problem, it’s going to be an awfully hard job selling these internationally after today’s news.

Which standards?

From my point of view this is probably the most interesting and worrying part of today’s leak. Software is almost always broken, but standards — in theory — get read by everyone. It should be extremely difficult to weaken a standard without someone noticing. And yet the Guardian and NYT stories are extremely specific in their allegations about the NSA weakening standards.

The Guardian specifically calls out the National Institute of Standards and Technology (NIST) for a standard they published in 2006. Cryptographers have always had complicated feelings about NIST, and that’s mostly because NIST has a complicated relationship with the NSA.

Here’s the problem: the NSA ostensibly has both a defensive and an offensive mission. The defensive mission is pretty simple: it’s to make sure US information systems don’t get pwned. A substantial portion of that mission is accomplished through fruitful collaboration with NIST, which helps to promote data security standards such as the Federal Information Processing Standards (FIPS) and NIST Special Publications.

I said cryptographers have complicated feelings about NIST, and that’s because we all know that the NSA has the power to use NIST for good as well as evil. Up until today there’s been no real evidence of malice, despite some occasional glitches — and compelling evidence that at least one NIST cryptographic standard could have contained a backdoor. But now maybe we’ll have to re-evaluate that relationship. As utterly crazy as it may seem.

Unfortunately, we’re highly dependent on NIST standards, ranging from pseudo-random number generators to hash functions and ciphers, all the way to the specific elliptic curves we use in SSL/TLS. While the possibility of a backdoor in any of these components does seem remote, trust has been violated. It’s going to be an absolute nightmare ruling it out.

Which people?

Probably the biggest concern in all this is the evidence of collaboration between the NSA and unspecified ‘telecom providers’. We already know that the major US (and international) telecom carriers routinely assist the NSA in collecting data from fiber-optic cables. But all this data is no good if it’s encrypted.

While software compromises and weak standards can help the NSA deal with some of this, by far the easiest way to access encrypted data is to simply ask for — or steal — the keys. This goes for something as simple as cellular encryption (protected by a single key database at each carrier) all the way to SSL/TLS which is (most commonly) protected with a few relatively short RSA keys.

The good and bad thing is that as the nation hosting the largest number of popular digital online services (like Google, Facebook and Yahoo) many of those critical keys are located right here on US soil. Simultaneously, the people communicating with those services — i.e., the ‘targets’ — may be foreigners. Or they may be US citizens. Or you may not know who they are until you scoop up and decrypt all of their traffic and run it for keywords.

Which means there’s a circumstantial case that the NSA and GCHQ are either directly accessing Certificate Authority keys* or else actively stealing keys from US providers, possibly (or probably) without executives’ knowledge. This only requires a small number of people with physical or electronic access to servers, so it’s quite feasible.** The one reason I would have ruled it out a few days ago is because it seems so obviously immoral if not illegal, and moreover a huge threat to the checks and balances that the NSA allegedly has to satisfy in order to access specific users’ data via programs such as PRISM.

To me, the existence of this program is probably the least unexpected piece of all the news today. Somehow it’s also the most upsetting.

So what does it all mean? 

I honestly wish I knew. Part of me worries that the whole security industry will talk about this for a few days, then we’ll all go back to our normal lives without giving it a second thought. I hope we don’t, though. Right now there are too many unanswered questions to just let things lie.

The most likely short-term effect is that there’s going to be a lot less trust in the security industry. And a whole lot less trust for the US and its software exports. Maybe this is a good thing. We’ve been saying for years that you can’t trust closed code and unsupported standards: now people will have to verify.

Even better, these revelations may also help to spur a whole burst of new research and re-designs of cryptographic software. We’ve also been saying that even open code like OpenSSL needs more expert eyes. Unfortunately there’s been little interest in this, since the clever researchers in our field view these problems as ‘solved’ and thus somewhat uninteresting.

What we learned today is that they’re solved all right. Just not the way we thought.

Notes:

* I had omitted the Certificate Authority route from the original post due to an oversight — thanks to Kenny Patterson for pointing this out — but I still think this is a less viable attack for passive eavesdropping (that does not involve actively running a man in the middle attack). And it seems that much of the interesting eavesdropping here is passive.

** The major exception here is Google, which deploys Perfect Forward Secrecy for many of its connections, so key theft would not work here. To deal with this the NSA would have to subvert the software or break the encryption in some other way.

Posted by Matthew Green at 11:27 PM

I am Science. You are Science. She is Science. We are Science.

[This is a re-post of my first submission for New York Academy of Science’s now-defunct Education Blog, where I briefly had a blog called “Dropping Mad Science.” It’s my entry for Kevin Zelnio’s “I Am Science” project, which inspired me to start this blog in the first place. It’s also the culmination of the story I began with “Children’s Story.” Enjoy.]

Why “I Am Science”

In 2012, I spent a week at my first “un-conference”with 450 or so of the most amazing science communicators, educators and practitioners in the world: Science Online 2012. Unlike most conferences where “experts” indoctrinate us with powerpoints, this un-conference was defined by the people formerly known as the audience (hat tip to Jay Rosen): all of us. While there, I attended an incredible session about the diversity of people in science, where we discussed the myriad paths we take to science, and how our life experiences inform our approaches – often in unacknowledged positive ways.

Shortly after I returned home , I was part of another conversation about inclusiveness that resulted in the creation of Twitter hashtag “#IAmScience.” My friend and inspiration Kevin Zelnio tweeted: “Let’s all tweet our nontraditional paths to our current involvement in science whether research, journalism, or other.” The hashtag evolved from #IAmScio12 (in reference to the conference) to #IAmScience, which pulled people into the discussion that had not attended the conference. For those of you that haven’t been sucked into the Twitter vortex, a “hashtag” is a little numeric symbol (aka the pound sign) stuck before a word or phrase that makes anything after it more easily searchable and indexable. Within seconds, this hashtag became a Twitter “meme,” went “viral,” and came damn close to creating a “paradigm.” Which is to say, it got everyone talking. I tried to enter the conversation with my own #IAmScience 140-character biography, and found myself stuck. I have finally figured out meaningful ways to incorporate the love of science into my life, but my journey here has been far too long and winding to dump onto my peers on Twitter. As many readers of this blog are teachers, I thought you might be in a unique position to appreciate it.

Hope Without a Home

I will never forget the day I placed in the Massachusetts Northeast regional science fair. I was fourteen years old, homeless and terrified. My mother and I had parted ways and after months of staying with friends, I had run out of favors. At 5’9 with long, flowing hair, I looked closer to twenty than fourteen, so no one questioned my presence on the Harvard campus. Seeing that I left to row crew every morning before dawn, I was never caught. The only issue I faced was the time someone took my sleeping bag and I was forced to shiver through the night.

That morning, I had rolled up my sleeping bag and stashed it back under the bench in the basement of the Harvard Psychology building where I’d slept the night before. I had brushed my teeth and washed my face in the public bathroom, then headed to the school gym where I kept my toiletries and a few changes of clothes. I had showered, changed into my nicest outfit and carefully drawn on the black eyeliner and red lipstick that had become my trademark.

I Don’t Belong Here

Despite being armored with a lipsticked smile, straight back and all the trappings of confidence, I was terrified my work would be deemed unscientific, and I would be rejected as a fraud. My study exposed Piaget’s confirmation bias and the regional limitations of his findings. I had already won a $1,000 scholarship at my school science fair for my research methods, but placing at this level meant (to me) that psychology research was “real” science, when done using stringent methods and self-awareness. It served as a warning for researchers to remain ever vigilant in checking their own biases. It also helped me justify my existence at this precarious moment in my life.

When I received my award, I met two people that would prove key to the direction of my life. One was an executive of Arthur D. Little that hired me to write a column on cutting-edge science for their science newsletter, thus inspiring a life passion for communicating about the business and science of innovative ideas. The other was Ms. Splaine, a remarkable science teacher at my high school that honed my scientific talents and introduced me to opportunities I had never imagined. In 1990, one year before I arrived, Ms. Mary M. Splaine created the curriculum for a new biotechnology program at the Cambridge Rindge and Latin High School. Unbeknown to me, this remarkable woman was one of my judges at the fair. A few days later, she showed up to my seventh period biology class and asked my teacher if she could take me with her. After submitting me to a half-day of biology and chemistry tests, Ms. Splaine invited me to join an exclusive, corporate-funded biotechnology track with a limit of six students, where I spent the next two and a half years of high school taking classes at Harvard and MIT while working as a paid intern at Massachusetts Eye and Ear Hospital. Though I had struggled through sophomore year chemistry class, I loved organic chemistry and took a natural shine to protein interactions.

Struggling with my own health problems, I had a personal stake in biomedical research, and wanted to help push forward human understanding of our bodies and their interactions with the world around us. As a woman with no money or support to even envision college, Ms. Splaine said I was a prime candidate to serve in the new, wildly successful biotechnology industry. “They need us,” she told me. “They’re up to their ears in problems and need us women to get in there and solve them.”

No Nancy Kerrigan

I will also never forget the day I quit science. I was working two jobs and paying my own rent while an intern studing cataracts at Massachusetts Eye and Ear Infirmary. On paper, my internship was pretty standard: three times a week, from 3:30-6:30 pm, I was hired to centrifuge calf eyes, extract strands of DNA, run gels and input results. In reality, it was far from a normal high school internship experience. Unlike most high school interns who are usually shunted off to the least junior grad student for mentoring, I was working directly under the head of the lab, as his star pupil.

Normally, when I arrived, I would find the first and last steps of a protein transformation on the board – and would have to draw as many of the interim steps as I could determine. The day I quit, I had worked that morning at one of my other jobs, taken a final and, honestly, simply lost interest in bench science. The fact that it was a gorgeous Spring day soon before my birthday did not help.

I came in to find a much easier job on the board than usual – a basic chemical name. My PI tried to pretend he was ignoring me, but I could feel his stare boring through the back of my head. I began to draw and then just gave up. I did not want to do it. More than that, I did not want to be a scientist. I did not want to become meek and antisocial, like the graduate students in my lab. I did not want to spend my days alone with an overprotective old man, being molded into his dream assistant.

My PI tried to pretend he was ignoring me, but I could feel his stare boring through the back of my head. He piped up as I stood there, paralyzed in hesitation. “Whaaat are you doooing?” I told him I couldn’t do it that day – could I please get one day off? He declined. I could draw the chemical or I could go home. We fought back and forth about it, and I think he knew I wanted to leave, because once I put my chalk down he picked it up and threw it in my face, hitting me right below the right eye. “You do not quit!” He spat in the dusty silence. “You do not waste my time only to quit!” He began to pace and yell, fume and scream. Finally, resigned, he started to cry, and said the words that sealed my fate: “I wanted you to be my Nancy Kerrigan!”

Kerrigan was the princess of American ice skating before her rival Tonya Harding took out her kneecaps. She had worked herself up from nothing was the pinnacle of discipline. Parents across the country used her as an ideal. I did not want to be his, or anyone’s, Nancy Kerrigan. I had finally healed unhealthy relationship dynamics at home with my mom – I was not now going to let myself be bullied by an unhealthy father figure into becoming someone I was not. Further, I refused to work in a system that purportedly sought answers to health problems but perpetuated such unhealthy relationship dynamics. I was, and am, a complicated, resilient woman with a lot more to offer the world than some drawings of protein transformations.

The Long Road Home

Like Nancy Kerrigan, I was also a young white woman offered many opportunities that were never imagined by my classmates back in high school. When a community nourishes and sustains you, and then you see yourself given blatant advantages never imagined by your community, it leaves a sour taste in your mouth and a churning in your gut. Because deep down, you know that if you take those opportunities and run with them, you will have stolen them from the people you love and that love you.
My love of science has inspired a number of pursuits, including journalism, activism, documentary filmmaking, patent law and now, science education. I have sought to take my advantages and bring them home. Still, I question my objectives, actions and impact every day. Join me as I continue to explore these questions, and please share your own thoughts on any of these issues you face as you do your part to give back to the world. #YouAreScience, too – what is your story?

Children’s Story Part Three

By the time I got to high school, things at home had changed. Now that my stepfather was gone, my mother was lonely, depressed and fearful. She started having flashbacks of the abuse she suffered at the hands of my father, and turned to alcohol to dampen the clamor in her head. We faced another source of tension by unhappy accident: I had hit puberty at the exact same time she had hit menopause. Our hormones were like high-pitched sine waves out of sync: the effect was discordant and painful. Most nights in junior high had involved my mom quietly, sullenly writing at her electric typewriter while I studied and talked on the phone, but by the spring of my eighth grade year, every night was another round in the migraine-inducing, shrieking battle of estrogen versus progesterone. I started staying out later. Then I started staying over friends’ houses. Then I stayed out all night, sitting up reading William Burroughs and The Watchmen at the 24-hour diner in Harvard Square. Once it got warm, I stashed my sleeping bag under a bench in the basement of the psychology building at Harvard and slept there. By end of summer, the sleeping bag had been taken away, so I began sleeping under the fruit trees in Radcliffe Yard. One day during the first week of high school, I had slept so little each night that I nodded off in the girl’s bathroom and slept there through two periods. Yes, I fell asleep on the toilet. To add embarrassment to idiocy, I didn’t wake up until the dean of my program woke me, flanked by the hall monitor and a student who’d innocently come in to pee and heard me snoring.

I was lucky.

Word got out about my “incident” and some new friends of mine from hanging out in Harvard Square expressed their concern. I started living at their houses, taking a week shift at each. The dean knew, but he never told. My mom knew, and knew well enough not to say anything. The last time I had tried to leave, she had grabbed my hair as I approached the door. I didn’t let go, neither did she, and next thing I knew, my scalp was bleeding. I left in shock and we didn’t mention it the next day. But I could feel her shame.

Staying with friends week to week meant getting to know the kids from my new high school. I had been active in a program called the High School Studies Program at MIT, and was still tight with all of my friends from junior high, so I hadn’t expected to want to socialize at school. But now I had no choice. I did the best I could at fitting in, but failed miserably. I was simultaneously way too worldly and way too geeky to make sense to most of my peers. So while I tried to fake normalcy, I also tried to escape into my studies. Given the program I was in (I will name no names), that was impossible. The teachers there were burned out and no one wanted to be there. The only class where I could be me took place in a different program within the school: biology. I took it with friends of mine from elementary school, so I was able to expose the real, goofy, studious ME for one period a day. It was no wonder that when it came to do our projects for the science fair, I put my heart and soul into it.

Later that semester, I was assigned an experiment in psychology class. I was living with a friend whose mom was a daycare provider, so I decided my project would see if Piaget’s experiments on children in France were replicable with children in Cambridge. I performed his experiments on children at my friend’s daycare center, at the one I had attended, and at another local daycare. None of the results came close to his. I began hypothesizing on why, and contacted a student at Lesley College who had studied my class the year before (this was a common occurrence in uncommon Cambridge, Massachusetts). She had been a friend and mentor, and I trusted her to tell me whether my methods had been flawed. She actually came with me on a visit, observed my method and told me I had performed it with scientific rigor. She was so interested in my result, she decided to help me perform my scholarly research, which led us to a 1981 study that showed inner-city children lagged significantly behind those in Piaget’s study. I had independently confirmed the results that challenged the replicability of Piaget’s results. It was pretty cool. Cool enough that my teacher asked me to enter it into the science fair.

[Note: this took me two years to publish, because I really wasn’t sure if I wanted anyone to read it. Thanks to Kevin Zelnio for his constant inspiration to stay honest.]