root labs rdist

June 24, 2014

Timing-safe memcmp and API parity

Filed under: Security — Nate Lawson @ 4:03 am

OpenBSD released a new API with a timing-safe bcmp and memcmp. I strongly agree with their strategy of encouraging developers to adopt “safe” APIs, even at a slight performance loss. The strlcpy/strlcat family of functions they pioneered have been immensely helpful against overflows.

Data-independent timing routines are extremely hard to get right, and the farther you are from the hardware, the harder it is to avoid unintended leakage. Your best bet if working in an embedded environment, is to use assembly and thoroughly test on the target CPU under multiple scenarios (interrupts, power management throttling clocks, etc.) Moving up to C creates a lot of pitfalls, especially if you support multiple compilers and versions. Now you are subject to micro-architectural variance, such as cache, branch prediction, bus contention, etc. And compilers have a lot of leeway with optimizing away code with strictly-intended behavior.

While I think the timing-safe bcmp (straightforward comparison for equality) is useful, I’m more concerned with the new memcmp variant. It is more complicated and subject to compiler and CPU quirks (because of the additional ordering requirements), may confuse developers who really want bcmp, and could encourage unsafe designs.

If you ask a C developer to implement bytewise comparison, they’ll almost always choose memcmp(). (The “b” series of functions is more local to BSD and not Windows or POSIX platforms.) This means that developers using timingsafe_memcmp() will be incorporating unnecessary features simply by picking the familiar name. If compiler or CPU variation compromised this routine, this would introduce a vulnerability. John-Mark pointed out to me a few ways the current implementation could possibly fail due to compiler optimizations. While the bcmp routine is simpler (XOR accumulate loop), it too could possibly be invalidated by optimization such as vectorization.

The most important concern is if this will encourage unsafe designs. I can’t come up with a crypto design that requires ordering of secret data that isn’t also a terrible idea. Sorting your AES keys? Why? Don’t do that. Database index lookups that reveal secret contents? Making array comparison constant-time fixes nothing when the index involves large blocks of RAM/disk read timing leaks. In any scenario that involves the need for ordering of secret data, much larger architectural issues need to be addressed than a comparison function.

Simple timing-independent comparison is an important primitive, but it should be used only when other measures are not available. If you’re concerned about HMAC timing leaks, you could instead hash or double-HMAC the data and compare the results with a variable-timing comparison routine. This takes a tiny bit longer but ensures any leaks are useless to an attacker. Such algorithmic changes are much safer than trying to set compiler and CPU behavior in concrete.

The justification I’ve heard from Ted Unangst is “API parity“. His argument is that developers will not use the timing-safe routines if they don’t conform to the ordering behavior of memcmp. I don’t get this argument. Developers are more likely to be annoyed with the sudden performance loss of switching to timing-safe routines, especially for comparing large blocks of data. And, there’s more behavior that should intentionally be broken in a “secure memory compare” routine, such as two zero-length arrays returning success instead of an error.

Perhaps OpenBSD will reconsider offering this routine purely for the sake of API parity. There are too many drawbacks.

June 23, 2014

In Defense of JavaScript Crypto

Filed under: Security — Nate Lawson @ 4:05 am

Thai Duong wrote a great post outlining why he likes JavaScript crypto, although it’s not as strong a defense as you might guess from the title. While he makes some fair points of some limited applications of JavaScript, his post is actually a great argument against those pushing web page JS crypto.

First, he starts off with a clever Unicode attack on JS AES by Bleichenbacher. It is a great way to illustrate how the language, with its bitwise and type hostility, actively works against crypto implementers. Though Thai points out lots of different ways to work around these problems, I disagree that it’s clear sailing for developers once your crypto library deals with these issues. You’ll get to pick up where your low-level library left off.

Oh, and those of you were looking for defense of web page crypto for your latest app? Sorry, that’s still dumb. Google’s End-to-End will only be shipped as a browser extension.

The most ironic part of Thai’s post involves avoiding PCI audit by shipping JS to the browser to encrypt credit card numbers. Back in 2009, I gave a Google Tech Talk on a variety of crypto topics. Afterwards, a Google engineer came up to me and gave exactly Thai’s example as the perfect use case for JavaScript crypto. “We avoid the web server being in scope for PCI audits by shipping JS to the user,” he said. “This way we can strip off the SSL as soon as possible at the edge and avoid the cost of full encryption to the backend.”

He went on to describe a race-condition prone method of auditing Google’s own web servers, hashing the JS file served by each to look for compromised copies. When I pointed out this was trivial to bypass, he said it didn’t really matter because PCI is a charade anyway.

While he’s right that PCI is more about full employment for auditors & vendors than security, news about NSA tapping the Google backbone also shows why clever ways to avoid end-to-end encryption often create unintended weaknesses. I hope Google no longer underestimates their exposure to nation-state adversaries after the Snowden revelations, but this use-case for JS crypto apparently hasn’t died yet.

May 26, 2014

Catching up on recent crypto developments

Filed under: Crypto,Security — Nate Lawson @ 6:10 am

When I started this blog, the goal was to write long-form posts that could serve as a standalone intro to security and crypto topics. Rather than write about the history of the NSA as planned, I’ll try writing a few short notes in hopes that they’ll fit better within the time I have. (Running a company and then launching a new one the past few years has limited my time.)

Heartbleed has to be the most useful SSL bug ever. It has launched not just one, but two separate rewrites of OpenSSL. I’m hoping it will also give the IETF more incentive to reject layering violations like the heartbeat extension. Security protocols are for security, not path MTU discovery.

Giving an attacker a way to ask you to say a specific phrase is never a good idea. Worse would be letting them tell you what to say under encryption.

Earlier this year, I was pleased to find out that a protocol I designed and implemented has been in use for millions (billions?) of transactions the past few years. During design, I spent days slaving over field order and dependencies in order to force implementations to be as simple as possible. “Never supply the same information twice in a protocol” was the mantra, eliminating many length fields and relying on a version bump at the start of the messages if the format ever changed. Because I had to create a variant cipher mode, I spent 5x the initial design time scrutinizing the protocol for flaws, then paid a third-party for a review.

As part of the implementation, I provided a full test harness and values covering all the valid and error paths. I also wrote a fuzzer and ran that for days over the final code to check for any possible variation in behavior, seeding it with the test cases. I encouraged the customer to integrate these tests into their release process to ensure changes to the surrounding code (e.g., 32/64 bit arch) didn’t break it. Finally, I helped with the key generation and production line design to be sure personalization would be secure too.

I firmly believe this kind of effort is required for creating security and crypto that is in widespread use. This shouldn’t be extraordinary, but it sadly seems to be so today. It was only through the commitment of my customer that we were able to spend so much effort on this project.

If you have the responsibility to create something protecting money or lives, I hope you’ll commit to doing the same.

January 6, 2014

Digging Into the NSA Revelations

Filed under: Crypto,Hacking,iOS,NSA,Rootkit,Security — Nate Lawson @ 5:00 am

Last year was a momentous one in revelations about the NSA, technical espionage, and exploitation. I’ve been meaning for a while to write about the information that has been revealed by Snowden and what it means for the public crypto and security world.

Part of the problem has been the slow release of documents and their high-level nature. We’ve now seen about 6 months of releases, each covering a small facet of the NSA. Each article attempts to draw broad conclusions about the purpose, intent, and implementation of complex systems, based on leaked, codeword-laden Powerpoint. I commend the journalists who have combed through this material as it is both vague and obfuscated, but I often cringe at the resulting articles.

My rule of thumb whenever a new “earth shattering” release appears is to skip the article and go straight for the backing materials. (Journalists, please post your slide deck sources to a publicly accessible location in addition to burying them in your own site’s labyrinth of links.) By doing so, I’ve found that some of the articles are accurate, but there are always a number of unwarranted conclusions as well. Because of the piecemeal release process, there often aren’t enough additional sources to interpret each slide deck properly.

I’m going to try to address the revelations we’ve seen by category: cryptanalysis, computer exploitation, software backdoors, network monitoring, etc. There have been multiple revelations in each category over the past 6 months, but examining them in isolation has resulted in reversals and loose ends.

For example, the first conclusion upon the revelation of PRISM was that the NSA could directly control equipment on a participating service’s network in order to retrieve emails or other communications. Later, the possibility of this being an electronic “drop box” system emerged. As of today, I’m unaware of any conclusive proof as to which of these vastly differing implementations (or others) were referred to by PRISM.

However, this implementation difference has huge ramifications for what the participating services were doing. Did they provide wholesale access to their networks? Or were they providing court-ordered information via a convenient transfer method after reviewing the requests? We still don’t know for sure, but additional releases seem to confirm that at least many Internet providers did not intentionally provide wholesale access to the NSA.

Unwarranted jumping to conclusions has created a new sport, the vendor witch hunt. For example, the revelation of DROPOUTJEEP, an iPhone rootkit, was accompanied by allegations that Apple cooperated with the NSA to create it. It’s great that Jacob Applebaum worked with the Spiegel press, applying his technical background, but he is overreaching here.

Jacob said, “either they [NSA] have a huge collection of exploits that work against Apple products … or Apple sabotaged it themselves.” This ignores a third option, which is that reliable exploitation against a limited number of product versions can be achieved with only a small collection of exploits.

The two critical pieces of information that were underplayed here are that the DROPOUTJEEP description was dated October 1, 2008 and says “the initial release will focus on installing the implant via close access methods” (i.e., physical access) and “status: in development”.

What was October 2008 like? Well, there were two iPhones, the original and just-released 3G model. There were iOS versions 1.0 – 1.1.4 and 2.0 – 2.1 available as well. Were there public exploits for this hardware and software? Yes! The jailbreak community had reliable exploitation (Pwnage and Pwnage 2.0) on all of these combinations via physical access. In fact, these exploits were in the boot ROM and thus unpatchable and reliable. Meanwhile, ex-NSA TAO researcher Charlie Miller publicly exploited iOS 1.x from remote in summer 2007.

So the NSA in October 2008 was in the process of porting a rootkit to iOS, with the advantage of a publicly-developed exploit in the lowest levels of all models of the hardware, and targeting physical installation. Is there any wonder that such an approach would be 100% reliable? This is a much simpler explanation and is not particularly flattering to the NSA.

One thing we should do immediately is stop the witch hunts based on incomplete information. Some vendors and service providers have assisted the NSA and some haven’t. Some had full knowledge of what they were doing, some should have known, and others were justifiably unaware. Each of their stories is unique and should be considered separately before assuming the worst.

Next time, I’ll continue with some background on the NSA that is essential to interpreting the Snowden materials.

September 23, 2013

20 Years of Internet

Filed under: Protocols,Security — Nate Lawson @ 5:00 am

This month marks my 20th anniversary of first connecting to the Internet. It seems like a good time to look back on the changes and where we can go from here.

I grew up in a rural area, suspecting but never fully realizing the isolation from the rest of the world, technology or otherwise. Computers and robots of the future lived in the ephemeral world of Sears catalogs and Byte magazines rescued from a dumpster. However, the amateur radio and remote-controlled plane hobbies of my father’s friends brought the world of computing and electronics to our house.

Still, communications were highly local. The VIC-20 could connect to a few BBS systems and my father’s industrial control of warehouse refrigeration systems (way before SCADA). However, anything beyond that incurred long distance charges and thus was irrelevant. Only the strange messages and terminology in cracked games, distributed from faraway places like Sweden, hinted at a much broader world out there.

Towards the end of high school, our local BBS finally got a FidoNet connection. Text files started trickling in about hacking COSMOS to change your “friend’s” phone service and building colored boxes to get free calls. One of those articles described how to use the Internet. I’d spend hours trying to remember all the protocol acronyms, TCP port numbers, etc. The Internet of my imagination was a strange amalgamation of X.25, ARPA protocols, TCP/IP, and the futuristic OSI protocols that were going to replace TCP/IP.

Once I arrived at college, I was one of the first in line to register for an Internet account. Our dorm room had an always-on serial connection to the campus terminal server and Ethernet was coming in a few weeks. It took some encouraging from my friends to make the jump to Ethernet (expensive, and 10BASE-T was barely standardized so it was hard to figure out if a given NIC would even work). Along with free cable TV, you’ve got to wonder, “what were they thinking?”

The dorm Ethernet experiment soon became a glorious free-for-all. There was a lot of Windows 3.1 and Linux, but also a few NeXTSTEP and Sun systems. Campus network admin had its hands full, bungling rushed policy changes intended to stop the flood of warez servers, IPX broadcast storms from Doom games, IRC battles, sniffing, hacking, and even a student running a commercial ISP on the side. Life on the dorm network was like a 24/7 Defcon CTF, but if you failed, you were reinstalling your OS from 25 floppies before you could do your homework.

There were three eras I got to see: Usenet (ending in 1994), early Web (1994-1997), and commercial Web (1998 to present). The Usenet era involved major changes in distributed protocols and operating systems, including the advent of Linux and other free Unixes. The early Web era transitioned to centralized servers with HTTP, with much experimentation in how to standardize access to information (remember image maps? Altavista vs. Lycos?) The commercial Web finally gave the non-technical world a reason to get online, to buy and sell stuff. It continues to be characterized by experimentation in business models, starting with companies like eBay.

One of my constant annoyances with technological progress is when we don’t benefit from history. Oftentimes, what comes along later is not better than what came before. This leads to gaps in progress, where you spend time recapitulating the past before you can truly move on to the predicted future.

Today, I morn the abandonment of the end-to-end principle. I don’t mean networking equipment has gotten too smart for its own good (though it has). I mean that we’re neglecting a wealth of intelligence at the endpoints and restricting them to a star topology, client/server communication model.

Multicast is one example of how things could be different. Much of the Internet data today is video streams or OS updates. Multicast allows a single transmission to be received by multiple listeners, building a dynamic tree of routes so that it traverses a minimal set of networks. Now, add in forward error-correction (allows you to tune in to a rotating transmission at any point in time and reconstruct the data) and distributed hash tables (allows you to look up information without a central directory) and you have something very powerful.

Bittorrent is a hack to leverage an oversight in the ISP pricing model. Since upload bandwidth from home broadband was underutilized but paid for, Bittorrent could reduce the load on centralized servers by augmenting them with users’ connections. This was a clever way to improve the existing star topology of HTTP downloads but would have been unnecessary if proper distributed systems using multicast were available.

We have had the technology for 20 years but a number of players have kept it from being widely deployed. Rapid growth in backbone bandwidth meant there wasn’t enough pricing pressure to reduce wastefulness. The domination of Windows and its closed TCP/IP stack meant it was difficult to innovate in a meaningful way. (I had invented a TCP NAT traversal protocol in 1999 that employed TCP simultaneous connect, but Windows had a bug that caused such connections to fail so I had to scrap it.) There have been bugs in core router stacks, and so multicast is mostly disabled there.

Firewalls are another symptom of the problem. If you had a standardized way to control endpoint communications, there would be no need for firewalls. You’d simply set policies for the group of computers you controlled and the OS on each would figure out how to apply them. However, closed platforms and a lack of standardization mean that not only do we still have network firewalls, but numerous variants of host-based firewalls as well.

Since the late 90’s, money has driven an intense focus on web-based businesses. In this latest round of tech froth, San Francisco is the epicenter instead of San Jose. Nobody cares what router they’re using, and there’s a race to be the most “meta”. Not only did EC2 mean you don’t touch the servers, but now Heroku means you don’t touch the software. But as you build higher, the architectures get narrower. There is no HTTP multicast and the same-origin policy means you can’t even implement Bittorrent in browser JavaScript.

It seems like decentralized protocols only appear in the presence of external pressure. Financial pressure doesn’t seem to be enough so far, but legal pressure led to Tor, magnet links, etc. Apple has done the most of anyone commercially in building distributed systems into their products (Bonjour service discovery, Airdrop direct file sharing), but these capabilities are not employed by many applications. Instead, we get simulated distributed systems like Dropbox, which are still based on the star topology.

I hope that the prevailing trend changes, and that we see more innovations in smart endpoints, chatting with each other in a diversity of decentralized, standardized, and secure protocols. Make this kind of software stack available on every popular platform, and we could see much more innovation in the next 20 years.

January 28, 2013

History of memory corruption vulnerabilities and exploits

Filed under: Hacking,Security,Software engineering — Nate Lawson @ 5:12 am

I came across a great paper, “Memory Errors: The Past, the Present, and the Future” by van der Veen et al. The authors cover the history of memory corruption errors as well as exploitation and countermeasures. I think there are a number of interesting conclusions to draw from it.

It seems that the number of flaws in common software is still much too high. Consider what’s required to compromise today’s most hardened consumer platforms, iOS and Chrome. You need a flaw in the default install that is useful and remotely accessible, memory disclosure bug, sandbox bypass (or multiple ones), and often a kernel or other privilege escalation flaw.

Given a sufficiently small trusted computing base, it should be impossible to find this confluence of flaws. We clearly have too large a TCB today since this combination of flaws has been found not once, but multiple times in these hardened products. Other products that haven’t been hardened require even less flaws to compromise, making them more vulnerable even if they have the same rate of bug occurrence.

The paper’s conclusion shows that if you want to prevent exploitation, your priority should be preventing stack, heap, and integer overflows (in that order). Stack overflows are by far still the most commonly exploited class of memory corruption flaws, out of proportion to their prevalence.

We’re clearly not smart enough as a species to stop creating software bugs. It takes a Dan Bernstein to reason accurately about software in bite-sized chunks such as in qmail. It’s important to face this fact and make fundamental changes to process and architecture that will make the next 18 years better than the last.

Next Page »

The Rubric Theme. Blog at


Get every new post delivered to your Inbox.

Join 83 other followers