When hashing does not improve privacy

Last week a local Portland station drew attention to Nordstrom piloting a program to track shoppers in-store using unique identifiers from their smart-phone. Intriguing quote from an article on StorefrontBacktalk covering the same story:

“To be precise, the MAC addresses of those shoppers are not being stored by Euclid; instead, a hashed version of those MAC addresses is being stored.”

The subtext of this statement is an article of faith about hashing: replacing sensitive information by its hash can magically assuage privacy concerns associated with the collection of personally identifiable information. In the case of Nordstrom and Euclid, the data in question is the unique hardware identifier of the wireless network adapter present in most smartphones. While exact details of the hashing process are not given in the article or for that matter Euclid website, some very general arguments can be advanced to the effect that hashing MAC addresses is unlikely to help in this case.

Quick detour into cryptography: a cryptographic hash function (hash function for short) is a mathematical abstraction designed to be easy to compute forward but difficult to invert. That is: given some input message M of any size– could be as short as an email address or as large as an MP3 file– we can compute a concise digest of that message quickly by applying a prescribed algorithm. But given such a fingerprint that came out of a computation where we were not privy to the original input, it should be very difficult– in other words, require inordinate amounts of computing power– to run the function backwards and come up with a message that could have been used as starting point to produce that fingerprint. (For completeness, there are additional requirements around pair-wise collision resistance, but these will not come into play.)

Storing hashed version of sensitive information looks like a privacy win. Instead of storing the MAC address of a shopper “00:87:44:D3:50:A4” we run that through a well-known hash function such as SHA1 and store the output: e266b50d6a98dafc962e9b7724092304170a3b8a. That may look like merely replacing one sequence of indecipherable symbols by another, but it hides information present in the original. For example MAC addresses have internal structure, with the first three bytes assigned to the hardware manufacturer. By looking up those digits in a public registry, it is possible to determine that. This alone can help distinguish users by the type of phone they carrying, since all units for a given model usually have the same type of wireless adapter. A good hash function wipes out such information. There is no correlation between the first-three digits of MAC and the output. Such simple mappings have been scrambled. The second benefit is that hashing can make it more difficult to link one observation (“user with hashed MAC address X walked into the store at 2:48PM”) against others involving the same person from other data sources, such as (“user with MAC address 008744D350A4 has Twitter handle of @alice”) by removing the common identifier that ties these records together.

There are two problems with this line of argument:

1. “One-way” is a computational notion. It only means there is no efficient algorithm to invert the function, to go from observed hash back to an input that generated it. This does not preclude very inefficient options, such as hashing all possible inputs to find the right one. Whether that is feasible depends on the number of candidates.

2. To prevent linking across different datasets based on a unique identifier such as MAC address, everyone has to adopt hashing. (Not only that, but use incompatible hash functions on purpose. Otherwise if everyone picked an unmodified function such as SHA1, then “SHA1 of MAC address” becomes the new de facto unique identifier for correlation.) It is not possible for one data owner to unilaterally prevent future linking by hashing their own records.

The Nordstrom scenario is an example of the first problem. If it proves “easy” to recover original MAC addresses from hashed versions, the benefits vanish.

To take an extreme case where hashing clearly does not help: consider health records database with one particularly sensitive column. This column can take two values: zero or one, depending on whether the patient tested negative or positive for performance enhancing substances. Replacing “0” with hash of 0 and “1” with the hash of 1 does absolutely nothing to improve the privacy of these records, for any choice of hash function. There are just too few possibilities: anyone with access to the records and knows the hash function can try both zero and one to uncover the status of any subject. (In fact for such an extreme case one need not even know the hash function– eg mixing a secret key into the process does not help either. If there is any a priori information about expected percent of cheaters, simply looking at the total incidence of two different values will suffice. For example if we assume optimistically that crooks are in the minority, then the hash value that appears less often must be the one corresponding to positive test.)

MAC addresses have a lot more than two possible values: roughly 281 trillion.** That may seem intractable but helping the attacker is the surprising efficiency of common hash functions, and how quickly they can run on modern hardware, an evolution driven in large part by research on password cracking. (In fact since passwords are typically stored in salted hashed form, that they can be recovered at all is rebuttal to naïvely equating hashing with privacy.) Using the popular cryptographic hash function SHA1 as an example, a single high-end GPU can grind through one billion hashes per second. Cluster together three dozen such processors, or better yet rent them from Amazon, and every possible MAC can be compared against a given mystery hash. (It should be emphasized that we do not know what hashing algorithm Euclid is using. But this is an example where a perfectly reasonable choice employed in many security applications fails to provide privacy.)

The picture gets worse when considering attacks against large number of users. Spending hours of computing time to recover a single MAC address may not seem economically viable for data mining purposes. But the marginal cost of inverting one more hash drops rapidly, thanks to more efficient cryptographic attacks using time-memory tradeoffs. These call for an upfront, sizable pre-computation phase to build a massive table which can be used later to crack individual hashes much faster than exhaustive search. The algorithm in effect takes up more storage space but reduces the time of each search. Refinements of this idea underlie the rainbow-table approach used for cracking Windows passwords. In other words, the cost of recovering MAC address does not scale linearly in the number of user. Bulk deanonymization is only slightly more expensive than going after a handful of individuals.

Bottom line: hashing does not magically anonymize personally identifiable information. In this case, there may not be much difference in privacy between storing MAC addresses and storing hashes. Without additional context, there is little reason to take comfort in a blanket statement to the effect that sensitive data is hashed.

** In reality, the hierarchical assignment of MAC ranges to different hardware manufacturers, combined with the fact that only certain models appear in smart phones, greatly reduces the range of possibilities. Here we assume worst case scenario.

The RFID boogeyman, part II: passports

If one could point to a single application responsible for giving RFID its bad reputation, it would have to be passports or machine readable travel documents (MRTD) in the standards parlance. The benefits of using smart card functionality to make passports more difficult to counterfeit are difficult to argue against. On the flip side, it has been equally difficult to articulate the value of having those chips support contactless access over RFID. In the US particularly, it has been a controversial decision pitting the privacy advocacy community against the State Department leading the charge for the new design.

Such vociferous opposition is understandable, as the stakes are higher compared to use of RFID for payment cards. While it requires something of a Luddite to completely opt out of the conveniences of credit/debit cards, consumers at least enjoy choice of issuers. The usual market forces are continue to operate: if there is indeed strong reluctance for contactless functionality in payments, customers will gravitate to banks catering to that demand. (Determined card-holders can even take unilateral action and fry the chip in the card.) By virtue of being government issued, passports offer no such easy opt-out. Crossing national borders usually requires some type of identification, and citizens have little choice but to obtain that ID from their country of their citizenship. More importantly NFC functionality is a critical part of passports– it is not an “optional” feature, unlike credit cards where transactions can still work the old-fashioned way by swiping the magnetic stripe. (Not to mention that tampering with passports is illegal.) The perception that a privacy infringing technology is being foisted on the populace has fueled many a conspiracy theory and FUD cycles.

That FUD has been non-stop and, quite frequently, wildly inaccurate. One sensationalist article from 2010 claims US passports can be read from 217 feet. Aside from the dubious use of “read” (see earlier post about what it takes to actually recover personal data from a passport) the article also conflates two different technologies. The actual demonstration at BlackHat involved EPC Gen 2 tags, which are RFID tags operating on a different frequency than the NFC chips present in passports. NFC stands for Near Field Communications— emphasis on “near.” While sufficiently powerful transmitters and sensitive antennas will no doubt increase the range significantly, up to several meters, to date there has not been a successful demonstration of reading NFC tags anywhere near distances implied by the article. Granted “attacks always get better” as the saying goes, but the article amounts to arguing that trains are dangerous by citing statistics on horse carriages.

An even more pervasive assumption is that individuals can be tracked simply by virtue of carrying their passport. This is a dubious proposition, at least in the simplistic interpretation of “tracking.” In the manifesto describing seven Laws of Identity— fashionable when Infocard/CardSpace was all the rage– Cameron posited that the problem with RFID is projecting an omni-directional identity:

Another example involves the proposed usage of RFID technology in passports and student tracking applications. RFID devices currently emit an omni-directional public beacon.

Paraphrased, this is asserting that RFID tags emit a constant, unique identifier to everyone instead of allowing the owner to project a variable identity based on the observer. While that holds true for earlier generation of RFID tags, it is demonstrably false for US passports, as anyone can verify with an NFC-capable Android phone. In fact it is required that passports are configured to emit a random identifier, picked anew each time the passport is scanned.

Granted randomizing the identifier emitted at the transport level is a necessary but not sufficient condition to prevent tracking. There could be other constant identifiers lurking in higher level protocols, permitting correlation. Here the picture is more complex. The designers have taken additional steps to avoid obvious pitfalls. For example retrieval of unique chip identifiers (such as the CPLC) is not allowed until the reader is authenticated to the card. That authentication step requires already knowing data from the passport, as explained in previous post. The design translates into a limited tracking capability: at best the reader gets a yes/no answer, learning whether the passport scanned is identical to one where the name, date of birth and expiration are known. By repeating this query, one could check against multiple persons. The time required for issuing these queries increases linearly with each such attempt– and these chips are not exactly blazing fast, given the requirement to be powered by an external field. (There is also an unintentional weakness which permits answering the same yes/no question using only a previously observed exchange with legitimate reader, without knowing the passport data.)

That is still enough for targeted surveillance against a small number of individuals, but not practical for tracking movement of every person with a passport who wanders within range of stealth readers. There is clearly room for improvement, because the expression of user “consent” for getting his/her passport scanned is far from clear. One could imagine alternatives where PIN entry is required (and this PIN can be changed by the user) or even a simple physical switch activated by pressing a touch-sensitive area on the passport. Similar designs have already seen trial deployments for payments. Even better, if NFC convergence takes off and passports are integrated into smart phones some day, existing mechanisms controlling when NFC functionality is accessible could provide a much better balance of privacy and user control over presenting their identity.

PIV card and mobile devices: NFC as missing link

An article in the Government Computing News titled Are mobile devices already making PIV cards obsolete? draws attention to the incompatibility of US government PIV standard with newfangled mobile devices. The author asks whether the shift to smart-phones and tablets is threatening to render the ID card program obsolete barely after it has gained momentum. With the prevalence of NFC in mobile devices (mostly owing to Android ecosystem, although Nokia, Blackberry predate it) this perceived incompatibility may be increasingly an artifact of design decisions in the PIV specification rather than any intrinsic limitation of smartcards. After all PIV cards are dual-interface: they have both old-school metal contacts for insertion into traditional card reader, as well as NFC antennas for communicating wirelessly. Since NFC-capable phones can act as card reader, one might expect that using the contactless interface will solve the problem– modulo NFC adoption, which is helped by the fact that the Pentagon favors Android for military applications. But it turns out that deliberate design decisions in PIV protocols frustrate that expectation.

Traditional contact-based card readers were historically used in conjunction with desktop machines, where having a separate gadget with dangling USB cable going back to the PC was less of a problem because the setup was stationary. Overtime came readers integrated into existing hardware such as keyboards, to better blend in with the existing peripherals. Laptops posed a slight s carrying yet another gadget quickly becomes a usability problem, even when the gadget in question can be quite tiny. In response manufacturers designed readers intended for the PC Card and later ExpressCard slot directly such that it can be left permanently fixed in place. (Strangely the move from PC Card to ExpressCard standard made the ergonomics worse. Now part of the reader must just out of the narrower slot in order to match ID-1 card dimensions, instead of being flush against the laptop edge in previous designs.)

Mobile devices however continue to pose a challenge due to the paucity of options. It is not that there are no card readers available– they are just very awkward looking. The generic availability of USB in Android makes it possible to reuse existing USB card readers, as ACR has done. Alternatively some manufacturers designed custom readers for phones, since they are no longer required to follow the USB CCID standard prevalent on Windows. There are a couple of products marketed as mobile CAC readers taking that route on iOS, Blackberry and other mobile operating systems. These gadgets are expensive, almost comparable to the cost of the phone and unwieldy. They combine the problems of one-more-widget-to-carry-around (or forget/lose) when not in use, with the problem of poor ergonomics when needed. Some of them functions as sleeve for the phone– a design that ironically would not fly on Android because it would interfere with NFC, with the card being recognized as NFC tag while also being activated on contact interface. Perhaps the least intrusive design is the baiMobile 3000MP which acts as a sleeve for the card and links up to the phone via Bluetooth.

What about NFC? Considering all card functionality can be accessed equally well over NFC, such kluges to get contact readers playing well with mobile device are no longer necessary for the latest crop of phones. In effect the devices are shipping with built-in contactless readers at no extra cost.

There is a catch. While it is true that communicating to the card works equally well from either interface, it does not follow that applications will respond identically. In fact card environments permit applications to determine what interface they have been invoked from and behave differently. In the extreme case, that could mean declining all requests from one interface. There are good security arguments for such discriminatory behavior. Case in point: payment applications running in a secure element inside a mobile device have reason to be suspicious of access from contact interface. That is where host applications and malware lurk. Contactless access from an NFC reader is the proper path for a legitimate point-of-sale terminal, and the payment application can check this during a transaction.

PIV also mandates similar restrictions, except in the other direction. The standard has a significant bias in favor of the contact interface, forbidding most operations over NFC. A look at the PIV data model in NIST SP 800-73 section 1 shows how bad the situation is. Appendix A lists up to four active X509 certificates and associated key pairs, identified by their purpose: card authentication, PIV authentication, signature and key management. Of these four, only the card authentication certificate can be used over NFC. Worse, that key does not provide two-factor authentication because there is no PIN entry required. It is primarily intended for low-security physical access scenarios. Employees tap their badge against a reader to open doors. (Even in that scenario, FIPS defines “restricted” and “exclusionary” areas where PIN entry and use of a different card key is required, which is only possible by inserting the card into a contact reader.)

The upshot is PIV cards can be accessed from an NFC-enabled mobile device, but they can not be used for any purpose other than physical access. Other applications such as Kerberos authentication with PKINIT, document signing or encrypted email call for using keys that are disallowed for contactless mode. These restrictions are not without good justification: NFC provides no encryption at the transport layer. This is unlike Bluetooth for example, where the pairing process also negotiates keys for protecting future traffic. If PIV messages between card and phone were carried over the air instead of direct contact, it would create new privacy problems. Most notably the user PIN sent to the card, as well as any decrypted data returned from the card would be susceptible to eavesdropping within NFC range. Future protocol improvements can overcome these limitations, but that will not help already deployed cards.

The RFID boogeyman, part 1: credit cards, HuMn wallet and identity theft

RFID is turning into what cookies were circa 2000: a poorly understood but universally reviled privacy infringing technology extraordiniare, synonymous with nefarious plans for consumer tracking by shadowy agencies. (Not to mention supernatural conspiracy theories.) NFC– Near Field Communications– being a type of RFID operating in the 13.56Mhz frequency, appears to have inherited all of that hysteria and vitriol, as it begins to overtake earlier incarnations of the technology. Case in point: HuMn is a KickStarter funded project to manufacture so-called RFID-safe wallets. Aside from the fact that it does not in fact cover all RFID objects, their marketing language appears to suffer from the same confusions about an ill-defined “identity theft” threat. (What about the US passport? Doesn’t look like the dimensions are compatible. And did they forget NFC-enabled phones? Where is the matching shielded phone cover?)

There is certainly a kernel of truth to the FUD: unauthorized payments can be made by bumping an NFC reader against the unsuspecting victim. Dramatic demonstrations of this abound on the tubes and the topic is rehashed often at conferences. This is not an iron-clad rule that follows necessarily from the technology, but an incidental property of the way cards are configured in the US. PIN entry is not required for credit card payments (not to be confused with debit, which does require it) unlike the chip-and-PIN system in Europe. Without a PIN gating authorization, mere proximity to the card is sufficient to exercise the payment protocol because the card has no other user-interface to ask for consent. (Mobile incarnations of NFC payments such as Google Wallet are a major improvement in that regard: on Android devices the phone screen must be powered on and users need to have recently entered the PIN to enable payments.)

But jury is out on whether that constitutes “identity theft.” Part of the problem lies in the ambiguity of the phrase, conflating routine credit card fraud with wholesale impersonation of the victim. An enterprising criminal in possession of someone else’s credit– even temporarily by NFC skimming– can spend funds available on that card. But armed with the victim’s full legal name, date of birth and social security number, that same crook can cause a lot more damage with new account fraud. They can get new loans with no intent to pay back or establish lines of credit in the name of the victim– all thanks to the bullet-proof authentication system used for such applications: if you know someone’s social security number, you must be that person. Vanilla card fraud takes place in a closed system, with a single institution implicated, namely the bank that issued this card to the legitimate card-holder. That company has an existing relationship with the consumer and presumably an interest in resolving the matter satisfactorily, in order to retain their business. (Card networks are structured such that that the issuer earns revenue from some portion of the interchange fee from every transaction, not to mention interest on balances.)

Between these two, plain card fraud is far less dangerous. It is also a problem the industry has “solved” to large extent by creating the appearance of zero liability for consumers, distributing losses between merchants and issuing banks.While dealing with fraud is time-wasting and inconvenient, losses are fully recoverable. By contrast new account fraud takes place in an open ecosystem, where the crook could have ripped off any number of participants with no prior relationship to the victim and not subject to the consumer-friendly liability arrangement of credit cards. It can be more challenging to undo this situation.

Lost in the ambiguity of “identity theft” is that neither SSN or date of birth can be gleamed from a credit card. RFID or not, it is not possible to get this information from a credit card so the risk here is one of plain fraud. for In fact NFC often provides the least information among all the different modes a payment can be made: while card-holder name is encoded in the magnetic stripe and embossed on the card, it is typically omitted from the equivalent “track data” sent during NFC payments. This is why the case of Barclay’s in UK was a big deal because the cards were personalized with full names.

It is unlikely that gangs of identity thieves are roaming crowded areas and bumping into unsuspecting people with NFC readers (Android phone counts as reader, in case stealth is desired) Such attacks are difficult to scale for three reasons. First skimming requires physical proximity to the victim, limiting the miscreants to a geographical area instead of being able to say target US citizens from the safety of Nigeria. Second the environment is not exactly target rich, with only a small number of banks having issued cards with NFC and even fewer people leveraging that. That makes it easy for fraud-detection systems to pick out anomalies because for most customers any contactless transaction is a red flag. Finally each bump only permits a limited number of transactions because the protocol employs a dynamic CVC3 verification value unique to each transaction. That is unlike swiping or typing card details into a web browser where the same fixed number is entered for the life of the card. In short, it is a bad proposition for the criminal, combining lots of effort with long odds and limited upside even when successful.

Returning to the original problem: yes it is true that unfettered access over NFC to credit cards allows making unauthorized payments. But then so does handing over the card to a bartender when settling a restaurant tab or holding the card in plain-view in any public setting with other people present– watch out for the person behind you in line wearing Google Glass. (Somehow “visible-light-spectrum-shielding wallet” does not sound as marketable.)

T-Mobile blocking traffic from Android wireless hot-spots

T-Mobile appears to be manipulating network traffic from users accessing the Internet through the wireless hot-spot functionality of their Android device:

IE screenshot showing T-Mobile man-in-the-middle against HTTP traffic

For background: ever since carriers began offering data connections to mobile subscribers, consumers have been trying to use these same pipes to get Internet access from other devices they might be carrying, such as their laptop. Over time different options emerged to connect these secondary devices and phones to accomplish this. In the beginning were USB cables, originating the concept of “tethering” with overtones of being tied down. Along came Bluetooth with the Personal Area Networking (PAN) profile, cutting the cable metaphorically. Final step in this evolution was the wireless hotspot, first introduced in Android 2.2 “Froyo” release and eventually taken up by the iPhone. In this model the phone acts as a wireless router, offering a wifi network. Instead of messing with cables or working through the ever-inconsistent implementations of Bluetooth pairing, users connect to this wireless network much like they would at a hotel, and get to access the Internet by tapping the same data connection they have already paid for as part of their cell phone plan.

At least that is the theory. The above screenshot is what happened in a recent session when attempting to navigate to www.youtube.com from a laptop connected to the wireless hotspot of a Galaxy Nexus running JellyBean. As the screenshot demonstrates, this is not exactly what the legitimate YouTube website looks like.

This is not exactly new. Carriers have been frequently at odds with their own users over tethering. Most recently Verizon got a shellacking from the FTC in a recent settlement ruling that the carrier can not keep customers from downloading tethering apps. AT&T meanwhile has resorted to stalking users with SMS when they start tethering on jail-broken iPhones. T-Mobile seems to have taken matters into its own hands by actively manipulating and blocking traffic. The carrier is using an explicit redirect, as the address bar shows a T-Mobile URL instead of the original location. This is accomplished by returning an intermediate response to the request for YouTube, redirecting the browser to the T-Mobile site instead. (With more nefarious transparent interception, T-Mobile could have returned the same bogus response while impersonating the original site the user expected to visit.)

Two consistent features of this based on initial observations:

Traffic manipulation does not commence immediately on connecting to the hot-spot, but only after some time has elapsed, or equivalent some bandwidth consumed. After that point all subsequent requests are tampered with, returning the above page. For what it’s worth, a quick check on Android settings shows the total data used before reaching this point was ~100MB:

Mobile data usage statistics

It is not clear what heuristics T-Mobile is using for detection. One article claims carriers rely on the TTL (time-to-live) field in IP packets, which is different for packets taking an extra hop through the phone a”router” verses directly originating from the phone itself. At least TTL is part of the packet header. A more disturbing possibility would be deep-packet inspection, where carriers are looking at content of packets. There are plenty of signals inside an HTTP request that permit easy identification of tethering scenarios. For example, if the HTTP user-agent header indicates the browser is IE9 running on Windows 7, chances are this is not coming from an Android phone.

Blocking is not attempted for pages accessed over SSL– in other words URLs starting with https. This is not surprising, as the SSL protocol carefully verifies the identity of the destination website using digital certificates. Any attempt by T-Mobile or other aspiring censors to masquerade as the legitimate site will result in a certificate error from major web browsers. Increasingly the UI for such errors is designed to be very difficult for even the unsuspecting user to ignore or bypass. It appears that T-Mobile made a conscious trade-off in condoning SSL usage and only tampering with unprotected HTTP traffic to display their advertising/upsell message. (Score another victory for HTTP Strict Transport Security or HSTS; websites such as GMail which can be configured to be always accessed over SSL are not affected because the web browser will use the HTTPS version even when a plain HTTP link is given.)

Time to revisit X509 name and path-length constraints?

Recalling the Leslie Lamport quote about the essence of a distributed system:

“You know you have a distributed system when the crash of a computer you’ve never heard of stops you from getting any work done.”

Substitute certification authority for “computer” and trust established for “work done,” and we have a good description of current PKI infrastructure. The fragility of this model, which has inspired critics such as Peter Guttman for over a decade now, was demonstrated again in the latest TurkTrust debacle. Here are the salient facts:

TurkTrust is a certification authority, present in Windows and NSS trusted root stores. Virtually all web browsers recognize this organization as valid issuer of SSL certificates used for secure connections on the web.
TurkTrust issued two leaf certificates to websites with the “CA” property set to true. In other words, the lucky recipients became intermediate certification authorities themselves, inheriting all the privileges afforded TurkTrust by web browsers to mint the equivalent of identity papers for any website in the world.
The intermediate CAs were used to issue fraudulent certificates, which were then used to falsely impersonate legitimate websites and intercept user traffic.
The problem was not discovered internally by TurkTrust during audits. Instead it was caught by Google, thanks to the Chrome certificate pinning feature.

There are a number of details lacking satisfactory explanation, in spite of a decent attempt at postmortem by TurkTrust. Leaving aside those questions, there are two fundamental questions around why the mistake was possible:

Why is TurkTrust– a CA based in Turkey and doing the majority of its business with companies Turkey– entrusted with issuing certificates for any company based anywhere in the world? This speaks to a profound breakdown of compartmentalization in X509, of any semblance of containing the failure of one component in the system from spreading to all others.
Why does a single mistake in using the wrong certificate template result in random website owners getting unfettered CA privileges, with no other checks and balances?

It turns out the X509 standard already has provisions to help out with both. Not surprisingly, these features have not been used properly in the PKI system that emerged over the years.

The solution to the first problem is name constraints. If the CA certificate contains this particular property, it can only issue for websites with name matching the specified pattern. The natural restriction for TurkTrust would be requiring that the site name ends in “.TR”, indicating the top-level country domain for Turkey. Design of these constraints allow specifying both permitted and disallowed names. For example if some subdomain of TR was particularly sensitive, it can be further protected against TurkTrust errors by excluding that pattern. Incidentally, name constraints are propagated down the chain. Even if a bumbling CA accidentally creates a subordinate CA lacking any name constraints, the restrictions specified in the root still apply.

The solution to the second problem is path-length constraints. Any CA certificate can express a requirement to the effect certificate chains leading up to that point will be no longer than some fixed number of hops. Setting the limit to 1 hop prevents any “accidental” intermediate CA from being operational. Leaf certificates issued from that unintended intermediary would have an additional hop to the root CA, violating the path-length constraint.

Realistically neither extension has been used in practice for existing trust anchor. Few carry any name or path-length constraints, with the exception of subordinate CAs issued to companies such as Microsoft to issue their own certificates for their own domains. Understandably it is not in the interest of the CA to impose restrictions on itself– what if TurkTrust later wanted to expand its business into another country or create additional subordinate CAs? A less draconian requirement is that all leaf-certificates must be issued from an intermediate CA that has a path-length constraint of one. Since the key used to sign leaf certificates must be online, in the sense of being available in the normal course of business, it is at highest risk of “accidents.” While the path constraint does not prevent issuing mistakes, such incidents will be isolated to a small number of sites each time. (Granted when that site is Microsoft or Google, the mistake can have large repercussions.) One could also envision separate intermediaries for different top-level domains, but this is unlikely to reduce overall risk. Most likely all of them will run on same infrastructure with same operational profile, having exactly the same vulnerabilities.

Given that the economics do not favor CAs to exercise self-discipline, the next best option is self-defense for users. Unfortunately that involves changes to certificate verification logic to artificially simulate the constraints. Windows cryptography API has some flexibility in limiting trust associated with root anchors, for example to remove ability to issue certificates for specific purpose such as code signing.

Editing properties using the management console

But that mechanism does not allow for introducing additional path or name constrains into an existing certification. (There is always the nuclear option of blacklisting a CA by putting them the Untrusted Certificates store but that goes well beyond the objective of “compartmentalizing” risk from CA failures.)

Using the secure element on Android devices (3/3)

(Continued from part I and part II)

As discussed in earlier posts, the embedded secure element on Android devices is a generic computing environment, with its own processor, RAM and persistent storage, however modest those may be in comparison to the phone itself. This platform supports running multiple applications, developed in Javacard. Javacard is a very restricted subset of Java optimized for resource-constrained environments. It’s worth emphasizing that while Android SE is programmed in Javacard, not all smart cards are. Some accept native code applications– “native” to their underlying bare-metal architecture. Not to be outdone by Sun, there is also .NET Card supported by Microsoft as a scaled down version of its .NET platform for Redmond-sanctioned smartcard development. The Android SE is also Global Platform compliant. This grandiose-sounding standard sets down a uniform model for card management, independent of form factor and internal architecture. GP can manage SIM cards over-the-air for GSM networks, as well as chip-and-PIN credits card inserted into an ATM. It can install Javacard applets just as well as deliver native code or C# applications.

Our starting point for this discussion was: what functionality does Android SE expose out of the box? It turns out the answer is, very little. Global Platform only mandates a card manager. The card manager is not the analog for an operating system per se. It is more akin to a trusted installer service that provides the only way to add/remove applications from the card. Unlike other smart cards that have a single dedicated purpose such as transit and no provisions for being enhanced in the field, the Android SE starts out with a blank slate. There is no TPM-style functionality, password manager or EMV-payment capability exposed to the outside world when the chip rolls off the assembly line. The underlying hardware and operating environment are very much designed to support all of these scenarios. In fact between the certified tamper resistance, hardware acceleration for cryptography and rich library of primitives in Javacard, the SE makes for an ideal platform for such security-critical functionality. It takes an application (“applet” in preferred Javacard terminology) to package those raw capabilities and offer them up in a way accessible externally. For example, when Google Wallet is installed and set up with cards/offers, then appropriate applets are installed that collectively implement the Paypass protocol for contactless payments over NFC.

Global Platform spells out how code is delivered (INSTALL for load and LOAD) and instantiated (confusingly named INSTALL for install.) By analogy to the PC, the first one installs new software while the second starts a new process from an executable image on the machine. GP also provides mechanisms for listing applications, deleting them, creating new security domains (similar to “users”) and managing the life-cycle of the card. For instance, locking the card if the issuer wants to suspend usage temporarily, or terminating it in an irreversible manner.

The catch is card management operations require authentication, specifically as the owner of the Issuer Security Domain. Global Platform defines this protocol, based on symmetric cryptography and clearly showing its age with a heavy reliance on DES– specifically triple-DES configured with two independent keys as 2TDEA. Each SE internally has a unique set of secret keys, called ISD keys or colloquially card manager keys. Possession of these keys is required for successful authentication, which in turn is a prerequisite for privileged operations like applet installation. GP envisions ISD keys being guarded by a trusted services manager (TSM), responsible for remotely managing the card without relinquishing keys to intermediate systems. This model strives for end-to-end security from TSM to the card, by avoiding security dependencies on other entities existing along the path. That includes the Android device, which is one of the final hops on the way. Card management commands are received from the cloud and funneled over to the SE. Rooting or jail-breaking the host operating system affords no special privileges because the local device does not have ISD keys.

Returning to the original question then: installing new functionality on the embedded secure element is possible on devices where:

The publisher of the application has card manager keys, or
Existing TSM in possession of such keys can perform the installation

** For completeness: there can be more than one set of ISD keys. All of them have equivalent privileges, including the ability to change other ISD keys. For example the embedded SE in PN65N from NXP Semiconductors features four key slots, theoretically allowing up to four different parties to manage the card at once. (That chip and its successor power virtually all NFC-enabled Android handsets. Only the recent Nexus 4 phone and Nexus 10 tablet have different hardware.) This is akin to having multiple cooks in the kitchen. Global Platform spec version 2.2 — which is not supported– adds even more flexibility with delegated management. ISD keys can be used to create supplementary security domains (SSD) which are capable of installing/removing applets on their own, but not interfere with code installed into other SSDs. That gives rise to an unbounded number of participants with ability to deploy applets in parallel.

Knight Capital, state-sponsored attacks and vulnerability of markets

The Knight Capital meltdown was an accident. So we are told– based on careful examination of the trading patterns and educated guesses, the culprit appears to be some testing code mistakenly released into the wild where it started conducting trades with real money on a real exchange, instead of the simulated environment used to verify the trading algorithms. There is no post-mortem released, at least not for public consumption– perhaps the SEC has received one under a confidentiality agreement. (That is a shame. The post-mortem would be required reading for software engineers, as another case study of a catastrophic bug missed before release, right up there with AT&T outage of 1990, Intel Pentium floating point unit and other epic failures.) Recalling the admonition, variously attributed to Robert Heinlein, that one should not attribute to malice what can be explained by incompetence, let us grant that there was no foul played involved. No rogue trader upset by his/her latest bonus, no corrupt insider bribed by a competitor to throw a wrench into the gears, no Stuxnet-style targeted malware poisoning the trading algorithms. The episode still provides a glimpse into the scale of disruption possible from a deliberate attack on markets, carried out by a skilled adversary in control of a high-frequency trading system.

Concerns have been raised in the past about the systemic risks from high-frequency trading, including the increased volatility and possibility for short-lived but significant pricing anomalies such as the Flash Crash of May 2010. (That incident turned out to be an unrelated problem, triggered by a large sell order from Kansas of all places.) Most of these critiques focus on accidental bugs, instead of deliberate attacks against the system. While Knight Capital proves the timeliness of the random-failure model, it paints an even more bleak picture in terms of the likely robustness of the system in adversarial settings. In other words, inability of quality assurance process to catch even “good-intentioned” bugs does not bode well for its ability to stop malicious tampering that is deliberately designed to evade detection.

One objection is that the errant trading did not result in destruction of wealth as much as it facilitated a coordinated and rapid transfer. Specifically, funds migrated away from the NJ firm and towards a multitude of other HFT shops on the winning side of the botched trades. It is a zero-sum game, this argument goes, and markets were efficient at punishing Knight Capital for its mistake, moving capital to other participants where it will be put to less foolish use. While the zero-sum property may have been (approximately) maintained this time around, it is not clear how that assurance can scale as the size of the disruption increases. The pattern of trading can just as easily cause prices of underlying assets to decline, generating losses for unrelated third-parties holding on to the same positions. The flash-crash of May 2010 was precisely such an incident that triggered a precipitous but short-lived decline in the market. The second problem is that drastic fluctuations can cause the proverbial “loss of investor confidence” among non-institutional investors, as well as disappearing liquidity as automated systems exit the market when reality parts ways from their models.

The likely suspect both in possession of resources to execute such an attack and motives to benefit from the ensuing chaos are nation states. Non-state actors such as terrorist groups may have motive, but probably lack the sophistication and access to markets with signficant capital. (Still the idea of villains initiating market mayhem while placing bets on the result has been a timeless plot device for B-grade action movies.) As for commercial entities, it is very risky for any legitimate company to actively tamper with a competing trading platform or ECN in order to reap profits. Getting caught has career limiting consequences for all involved. (On the other hand, theft of competitors’ trading model with the purpose of either front-running them or better yet trading against them is well within the realm of unethical possibilities, as in the Goldman Sachs programmer caught stealing source code in 2009.)

State sponsored computer warfare has received a lot of attention and FUD recently, mostly focused on the vulnerability of critical infrastructure such as the power grid or communication systems. Markets are not “critical infrastructure” in the sense that temporary disruption is not as life-threatening as widespread blackouts or toxic chemical release from industrial systems. On the other hand, it may have a very disproportionate effect on the economic well-being of the US. It is no secret that past waves of APT targets included financial institutions. But the geopolitical context driving such attacks and their objectives are complex. Stealing trade secrets or source code from companies headquartered in a different country provides an economical advantage to the country initiating the theft, as well as any domestic competitors who become the recipients of said ill-gotten goods. It is not surprising that some nations have embraced the practice as an integral component of foreign policy. But given the tight coupling between national economies (“when the US sneezes, rest of the world catches a cold”) an action causing wholesale market disruption would have repercussions for the aggressor as well. This poses a particular challenge for China, long suspected as main perpetrator of attacks against US networks. It is one of the largest holders of US Treasuries, and its growth engine remains dependent on US companies that outsource manufacturing operations. Then there is the collateral damage to sovereign wealth funds associated with other nations invested in the same market, making it difficult to separate allies from foes in terms of harm inflicted by an indiscriminate attack against trading infrastructure.

Using the secure element on Android devices (2/3)

The first post in this series described the permissions model for accessing the Android secure element from its contact interface. (Not to be confused with access from contactless aka NFC interface, which is open to any external device in NFC range.) This model can be viewed as a generalization of standard Android signature-based permissions— in fact for Gingerbread it was a vanilla signature permission based on matching the certificate used for signing NFC service.

Starting with ICS, there is an explicit whitelist of allowed signing certificates. Any user application signed with one of these keys can obtain access to the secure element, and more broadly to administrative actions involving the NFC controller such as toggling card emulation mode. These certificates can be retrieved and inspected from any Android device. With adb debugging enabled, an incantation such as “adb shell cat /etc/nfcee_access.xml | xmlstarlet select -T -o -t -v //signer[1]/@signature | xxd -r -ps | openssl x509 -inform DER -text -noout” will dump the certificate on a command line. [Full output]

Step by step:

Get the XML file containing the whitelist [nfcee_access.xml]
Locate the first signer element, then its signature attribute. In the above example this is done with an XPath query, with plain text output. On all production devices this blogger has encountered, there is exactly one such node. Development builds can have more. (As an aside, that XML attribute is a misnomer: “signature” contains an X509 certificate, instead of the signature on a particular APK. Same confusion exists in the Android API, where signatures field inside the package description actually contain certificates.)
Decode the value of the attribute as hex string
Interpret the result as an X509 certificate in ASN1 encoding, and parse the certificate.

But it is easier to save the certificate output after the third-step with a .der extension [certificate] and open the file using the built-in Windows UI for inspecting certificates:

Android code authentication model uses self-signed certificates– in the above example, the issuer and subject are identical. This is in contrast to Authenticode, where publishers obtain certificates from a trusted third-party certificate authority such as Verisign. When an external issuer is involved, the subject name in the certificate is verified during the issuance process. A competent CA is not supposed to issue a Google certificate to someone not affiliated with Google. (In reality, process failures have occurred, but nowhere with the same frequency as SSL certificate issuance mistakes.) With self-signed certificates, anything goes for the subject name since it is decided entirely by the software publisher, with no external sanity checks. Luckily in this case the field contains sensible information, identifying the publisher as associated with Android and specifically the NFC stack. The important property is that other applications signed using the same key will have access to the secure element. Additional publishers can be granted access by also including their certificates in the whitelist.

That solves half the problem: communicating with the SE from contact interface, or in other words being able to exchange APDUs in terms of developer view. The logical next step is determining what can be done with that capability, which boils down to two questions:

What features/functionality is present in the SE out of the box?
If the built-in feature set proves insufficient for some use case, how does one update the SE contents to add new capabilities?

The final post in this series will attempt to elaborate on these questions, which are also discussed in a Stack Overflow thread dedicated to the access control mechanism in ICS.

[continued]

Fine-grained control over framing web pages (1/2)

Firefox has recently enhanced its implementation of content framing checks, by adding support for Allow-From attribute of X-Frame-Options HTTP response header. This is a good time to revisit the motivation behind framing restrictions and the evolution of security mechanisms in web browsers to control framing.

HTML frames are a standard mechanism for aggregating content from different websites. Originally introduced as framesets in Netscape Navigator 2, they were later generalized to the more usable inline frame notion that remains in widespread use today. On the one hand, frames provide a safer alternative to other mechanisms such as script source inclusion. The same-origin policy can prevent active content from accessing resources on a different website, maintaining a security boundary between the framer and framee. On the other hand, the possibility of seamlessly framing other websites without any way for users to distinguish loca/external content can also lead to confusion and security issues.

The original X-Frame-Options header was introduced as a proprietary extension in Internet Explorer 8 in response to so-called clickjacking or UI-redress attacks. Clickjacking takes advantage of the flexibility of HTML layout to trick users into believing they are interacting with one website, when they are in fact interacting with a different one. The hypothetical example is clicking a seemingly harmless button on a malicious website, but having that click instead delivered to a different button on a banking website, which conveniently inititates a funds transfer from the victim to the attacker. The reason for that surprising otucome: the banking page was in fact present all along, inside a transparent frame “in front of” the malicious site, unbeknownst to the user.

Pulling this off requires the interaction of several features, all of which are seemingly benign in isolation:

Framing: Embedding the contents of one web site inside another page. In this case a trusted web page.
Positioning of frames: This allows shifting the framed content around, to better align with the fake UI element visually overlaid behind it.
Transparency: when third-party content is framed, its transparency can be adjusted from fully opaque to 100% transparent. The latter extreme end of the spectrum leads to a surprising situation: none of the content is visible to the user, but the browser treats this frame as the one in front. User interactions such as clicking inside that region will deliver those inputs to the transparent frame– even though it only has an ethereal presence.

X-Frame-Options tackles the problem by attacking the first condition, controlling which other sites can frame a given page. This is done by having the framee decare its intentions with a new HTTP response header when serving the page. The web browser is responsible for consulting this header when fetching framed content, and applying the stated restrictions to stop content rendering if necessary.

The original design was cobbled together quickly in response to the increasing alarm over clickjacking in spite of any lack of evidence for real-world exploitation. It provided three options: Allow, Deny and Same-Origin, corresponding to yes/no/conditional on origin permissions. This was a clear improvement over the string of unreliable frame-busting checks in Javascript which had become widespread at that point. Yet absent from the original spec was a middle ground: grant framing rights to a specific website, for the common scenario when widget.com to state that only acme.com is permitted to frame its pages. Same-origin is the closest option, and that does not help when the pages are in different domain. In fact “origin” in this case has strict definition of domain name; even foo.acme.com and bar.acme.com would be considered different origins. Since restricting framing to a set of known trusted sites is a common problem, there have been several workarounds to approximate the same behavior with varying degrees of success. For example:

Check the Referer header in the incoming HTTP request, identifyig the previous website the user is coming from. This sort of works, except that Referer is not guaranteed to be present and there were past vulnerabilities which allowed script or extensions such as Flash to forge that header. (While the user herself can always craft an HTTP request with any Referer, that constitutes a self-attack in this example. The bigger concern is when malicious.com can make a request to widget.com with Referer header set to acme.com, misleading the widget to believe it is being framed from an authorized container.) Given the fragility of the Referer header and its bad reputation as by-design privacy leak across sites, most robust designs shy away from depending on it for security checks.