CardSpace boasts a limited degree of unlinkability, based on a weak attack model: for self-signed cards, user can generate two assertions for two different websites that appear independent. (My colleague Ben from Google security team disputes even that weak guarantee, arguing that only assertions that can not be linked even with help from the identity provider qualify as “unlinkable”)

OpenID gets a bad reputation for allowing linkability but in fact there is no requirement of universal identifier in the specification. OpenID provider could choose to assert two different “names” for the same user to two dfiferent websites. (Of course they are still linkable in the sense that the ID provider knows what is going on, even if the sites can not put the picture together on their own– sort of, see next two points.)

The problem is even this weak guarantee of “unlinkable” identities at multiple websites breaks down in the real world, for two reasons.

First problem is that websites insist on email address or other unique identifier– and they want this at authentication time. When an inherently PII information such as email address is shared, unlinkability of the underlying protocol becomes largely irrelevant since there is another, even more universal identifier to go by. Same email address would appear even when user authenticates via two different identity provides– this is linkage across independent providers.

Federated ID providers are not in a position to say no: they are trying to convince relying sites to interoperate. Everyone already has a proprietary identity management system already, requiring users to sign up. This registration process collects some basic information and availability of that information is firmly embedded in the business logic. Going from a model where the site has an email address to one where they know the user as “pq2t45x” is not an appealing proposition. Similarly any time the user shares a global identifier such as address, real name or credit card number they void any privacy guarantees from the identity model.

As a matter of architecture, authentication systems should strive for minimum disclosure– more identifying information can always be added after the fact, but it is impossible to go back in the direction of greater privacy. Even if majority of transactions ended up with the user sharing PII during  at one point (making them very linkable regardless of authentication) it’s fair to argue that underlying protocols need to optimize for the best case of no disclosure and casual browsing. But the reliance on email address in existing scenarios means that redesigning basic protocols in this fashion to disclose less will be an exercise in rearranging deck chairs.

In many ways email address is the easiest attribute to fix, especially when ID provider is also the email provider– true for the three largest ID providers, Windows Live/Passport, GMail/Google and Yahoo– they could simply fabricate email aliases that forward to the original. Unfortunately that still breaks support scenarios because when alice@gmail.com calls asking for help, the system has her records files under the very private dx4r2p6@gmail.com. Other identifiers have their own private versions depending on the provider: some credit card companies support issuing one-time card numbers billing to the original. Mail services allow signing up for a PO box and hide original physical address (although good luck getting many ecommerce merchants to deliver to one due to their high incidence of fraud) and conceivably they could start algorithmically generating those PO box numbers to break linkage.

Even if every instance of linkable PII could be replaced by a pairwise unique variant, there is a second problem: linkage between identifiers is possible when user is authenticated to multiple sites at the same time.

[continued]

CP

Glad to see a comment from Dan Kaminksy on the last post about the severity of MD2 issues.

Follow-ups:

• There is no denying the problem with MD2. Discontinuing its use (eg rejecting certificates signed with MD2, as OpenSSL already has and t he upcoming MSFT patch will implement) is the right response.
• Point argued in the post is  that severity and urgency of the problem is low.  Compared to other X509 problems disclosed by Dan Kaminsky and Moxie Marlinspike — including the null handling, OID confusions and even more deadly remote code execution in NSS– MD2 issue is a distant second. The sky is not (yet) falling.
• It’s not clear  the MD5 parallel holds: When Wang and her colleagues found actual collisions people were widely using MD5 for new signatures. In fact the forgery of an intermediate CA cert in December 2008 proved some certificate authorities are so clueless that they continued using MD5 for new signatures after 4 years and several improved attacks. (The fact that SSL CAs are bound to be incompetent and clueless as the expected competitive outcome deserves its own blog post.) MD2 has long been retired for new signatures, leaving only past signatures to exploit.
• Basic birthday attacks are enough to exploit new signatures. Advances in the types of collisions possible– such as controlling the prefix– only improve the odds. But leveraging  past signatures in a hash function that is no longer used requires a second pre-image attack. Nobody has managed to produce even a single one for MD2.
• As of this writing, best second preimage attacks have time complexity comparable to 2**73 MD2 invocations and storage complexity of 2**73. And that second number makes this attack impractical . Eight billion terabytes– an awful lot of spare disk drives. (As an aside– Daniel Bleichenbacher looked into this and did not see any low-hanging improvements to the storage requirement either.)

Bottom line: yes there is a problem with MD2. It never presented an immediate danger. Cryptographic attacks are fascinating but the more mundane X509 parsing bugs disclosed around the same time– and continuing tradition of CA incompetence– are far more fatal to PKI.

CP

There has been a lot of talk about “unlinkability” in the context of web authentication systems. For example Cardspace is touted as being somehow more privacy friendly compared to OpenID because it can support different identifiers for each site the user is interacting with. This post is a first attempt to summarize some points around that– complete with very rusty blogging skills.

To start with, the type of unlinkability envisioned here is a very weak form compared to the more elaborate cryptographic protocols involving anonymous credentials. It comes down to a simple feature: when a user participates in a federated authentication system (which is to say, they have an account with an identity provider that allows the user to authenticate to websites controlled by different entitites) does the user appear to have a single, consistent identifier everywhere he/she goes?
It is not a stretch to see that when such a universal identifier is handed out to all of the sites, it enables tracking. More precisely it allows correlating information known by different sites. Netflix might know the movie rental history and iTunes might know their music preferences– if the user is known to both sides by the same consistent identifier, the argument goes, the two can collude and build an even more comprehensive dossier about the user. This is a slightly contrived example because movie rentals are uniquely identifying already (as the recent deanonymization paper showed) and chances are so is the music collection, but it is easy to imagine scenarios where neither site has enough information to uniquely identify a user but when they can collude and put all of the data together, a single candidate emerges. Consider Latanya Sweeney’s discovery in 2000 that 87% of the US population can be identified by birthdate, five-digit zipcode and gender. It does not require very many pieces of information– if they can be assembled together with the help of a unique ID each one is associated with– to pick out individuals from the online crowd.

The obvious solution is to project a different identity to each website. Alice might appear as user #123 to Netflix but iTunes remembers her as user #987. With a little help from cryptography it is easy to design schemes where such distinct IDs can be generated easily by the authentication system, and virtually impossible to correlated by the websites receiving them even when they are trying to collude.

[continued]

CP

There is much to write about the disclosure of vulnerabilities in X509, independently found by Moxie Marlinspike and Dan Kaminsky. There was some overlap in their discoveries, but also unique aspects. One worth highlighting is Moxie’s attack on defeating OCSP with a single byte.

Online Certificate Status Protocol attempts to verify the validity of web site certificates by contacting an OCSP responder, operated by the certification authority (CA) and asking the question “is the certificate with serial number #123 still valid?” This is one of two approaches to doing revocation checks– the Achilles heel of PKI. The other option is CRLs or certificate revocation lists. In that model the CA publishes a list of revoked certificates periodically and client download these (hopefully in advance, so that by the time you have to check it is locally cached) and look for the certificate in question there.

Now since the revocation status of a certificate is critical bit of information, the answer from the CA, whether packaged into a CRL or generated on-demand in response to an OCSP ping, has to be somehow protected. Otherwise the bad guys– on top of having obtained a bogus certificate and private key– can simply forge a response to suggest that all is well with the certificate.

It’s tempting to say “download the CRL / run the OCSP check over SSL” but that would create a circularity for boot-strapping. Not to mention that SSL is a very expensive solution to the problem of content integrity. Instead CRLs and OCSP responses are digitally signed, typically by another certificate that chains up to the issuing root CA.

Now if that had been the entire story revocation checking would be sound.

But Moxie noticed that by design OCSP allows unauthenticated responses, namely the set of responses collectively dubbed non-authoritative. This includes conditions such as an internal error with the service, malformed request  and “try again,” suggesting that the server might be overwhelmed with demand at the moment. These replies do not require a signature– by design. It’s in the RFC. In these cases a single byte indicating the response status is a valid OCSP response.

Of course this defeats one important security guarantee: when a non-authoritative response is received, the client can never be sure if it came from the OCSP responder. An attacker pulling of a man-in-the-middle attack could always forge one of these respones. Granted such an attacker could also drop the traffic and make it appear that the OCSP responder has vanished from the surface of the Earth. The bottom line is that in the absence of a signed response, client can not make any conclusions about the status of the certificate.

Of course implementations of OCSP must deal with this condition. They need to report what went on, and the buck stops somewhere along the application stack, where one developer decides what to do with these non-authoritative error codes.

Moxie’s discovery is for both Windows CAPI and NSS, that decision is to treat the “Try Again” response with code 3 as a successful revocation check. That means IE and Chrome (built on top of CAPI) and Firefox (built on top of NSS) are trivially confused in OCSP checks… with a one-byte response containing “3.”  Neatly summed up by one of the money slides in the presentation: a giant three interposed over the OCSP RFC.

Granted this is not the entire story: starting with Vista there is a complex revocation checking logic in CAPI that will load-balance between OCSP and downloading CRLs. CRLs are more efficient at scale: If every user in the world started hammering Verisign’s OCSP responder for every SSL request, Verisign would fall over in a matter of seconds. But they are highly inefficient in the short-term: in order to check the status of a single certififcate, the client is tasked with downloading a massive document, in the middle of setting up a connection. Vista tries to solve this problem by looking for frequent revocation checks and scheduling CRL downloads for them. Once a non-expired CRL has been downloaded, in principle the OCSP check is not required because looking at the locally cached document is faster and will reveal the revoked status of the certificate. In other words there may be edge cases to the Moxie attack where it stops working, depending on the past history of revocation checks.

Still a remarkable way to cap off a  series of attacks against X509 parsing.

cemp

The arrest of a disgruntled programmer trying to walk away with code for automated trading at Goldman Sachs raises questions about the value of intellectual property and challenges in protecting it.

First Goldman Sachs got very lucky in this case because the attempted theft was a case of amateur hour gone awry. The programmer may have been motivated and even knowledgable on quantitative modelling but clearly he was no security expert. The choice of exfiltration tactic, attempting to upload source code to a Germany, could have been easily detected by monitoring at the network perimeter or even internal machines. No doubt vendors specializing in the latest brand of snake oil, data-leak prevention or DLP, will capitalize on this opportunity for free advertising. But DLP is a case of we-catch-the-incompetent-ones. It is not possible to look at a stream of bits leaving the company network and decide if they correspond to intellectual property or harmless personal browsing. Techniques such as steganography make it possible to hide messages inside other, innocuous seeming messages that provide cover.

The second point is more disturbing: what was the corrupt insider  planning to do with the source code? How would he capitalize on the IP theft? Is he planning to set up his own trading system? Or is he planning to sell the code to another firm?

First option seems very likely. The latest trend in automated trading systems is high-frequency trading. Decision time between discovering market prices and placing trade order is on the order milliseconds here. In fact the servers are often  co-located near the exchanges themselves in order to reduce latency from order placement to execution. While the trades each earn small amount of revenue, but the ability to repeat this thousands of times for each market inefficiency allows quant hedge-funds to generate steady revenues. What all this means for potential disgrunted employees: it would be almost impossible for one individual working out of a basement or a bunch of guys sitting around Bloomberg terminals to capitalize on knowledge of the models. Even if they could predict the exact positions the model would take, the chances of front-running it are slim to none. Even given same speed, without massive capital to spread between thousands of trades, it simply would not scale enough to present a threat.

Since the speeds here are too high for human reaction times, the next option is to selling the software to another company with an existing system for low-latency trading in place. This is where a different problem emerges: no respectable company would touch stolen IP. Especially not one with deep pockets and an already viable line of business. The potential liability, both in lost revenue from the likely fines and direct personal culpability of senior ranking executives would all but guarantee that no serious player will take the risk. (Granted the case of Bernie “Made-off” Madoff provides evidence that highly dishonest operations exist in this space.)

Most likely option for monetizing such stolen IP then is a combination of individual risk and plausible deniability for a major competitor. The aspiring crook pretends that he/she came up with the trading strategy on his/her own (or perhaps the inverse strategy, since front-running is going to be a challenge, they can instead attempt to take the exact opposite positions.) The new employer is pleasantly surprised that the strategy is generating handsome returns, and appropriately rewards the brilliant quant, while HR departments pats themselves on the back for a great hiring decision. This is a case where the new employer may not be motivated to ask questions about the unexpected success.

One final aspect is that even in the absence of any reasonable way to monetize the stolen software, Goldman Sachs would be wise to give up on that particular model. The possibility itself that others may have studied the model and derived their own conclusions from it is enough to cast doubts on its future effectiveness.

cemp

In January this blogger gave a talk at Wharton Business School, as part of the Information Security Best Practices conference.

Here is a note from ZDNet summarizing one audience member’s perspective. The presentation is online. More about the main points in a future post.

cemp

My friend and former colleague Ryan provided some helpful comments on the previous post regarding MD5-collision attack against incompetent CAs.  (Ryan has also written an informative post about the attack on his blog.) Based on his pointers, here are some corrections and observations:

• The sparse appearance of the Vista trusted root store (compared to the 100+ roots in Windows XP) is largely an illusion. Both operating systems have a capability to update list of supported roots on demand from Windows Update. In XP most of the roots are pre-installed while Vista depends on this dynamic fetch process– which can be done in real-time when validating a new certificate to a greater extent.
• If a certificate authority does not show up in the root store does not mean that it is not trusted. There is always the possibility that consulting Windows update when attempting to build a certificate chain will lead to one or more new roots getting installed.
• A nasty surprise follows as corollary: removing a root from the trusted-roots node has no effect. It has to be explicitly placed in the untrusted roots store or the silent update from WU has to be disabled– the latter not being an advisable solution. Here is an extensive article about theproblem of dynamic installation of root certificates.
• There does not appear to be an official way to download a list of all trusted roots valid at a given point in time, although a knowledge base article from January ’08 documents the organizations who are members of the root certificate program. (Each company may have multiple roots and may introduce new ones over time via distribution from WU, there is no 1:1 correspondance. There is also no documentation of the fingerprints or other unique identifiers for the outstanding roots.)
• Microsoft requires the WebTrust for CAs certification standard for all CAs in the root program. WebTrust also has a series of requirements for extended validation certificates, which include the use of a stronger hash function such as SHA1 for issuance. (Not that it matters: websites using EV certificate are still vulnerable, as long as the code assign them identical trust as plain vanilla certificates. The green address bar and other window-dressing is intended for users’ eyes only; under the hood the code responsible for deciding to disclose data does not care about the distinciton.)

cemp

One of the more interesting attacks of 2008 came on the second-to-last day of  the year, when a group of researchers announced they had successfully forged a bogus CA certificate. Depending on perspective, it is either a novel demonstration or an obvious next step on MD5 collisions. Since the original announcement in 2004 of the MD5 collisions, there has been steady progress on crafting meaningful messages with identical hashes. 

• Random collisions for messages with no structure.
• Collisions with shared prefix, which is enough to come up with 2 different X509 certificates featuring different keys and identical hash.
• This attack was later extended to allow chosen, different prefixes on each message, as described in a Eurocrypt paper.

These birthday collisions are dangerous to the extent that an attacker can get the target to sign a message of their choice– the hope being that while the victim thinks they are signing innocuous message #1, they are also signing message #2 with same hash but worse implications. In general few applications afford that opportunity, because acting as a signing-oracle is the cryptographic equivalent to a bureaucrat rubber-stamping everything presented on his/her desk.

That brings us to the other problem: using MD5 was not the only screw up from the handful of CAs implicated in the vulnerability. The certificate contents signed were entirely predictable or controlled by the adversary. In particular, the serial ID which could have been easily made into a unique, deterministic and completely unpredictable value (by using the encryption of an incrementing counter) was implemented as a simple counter, bumped up by one each time a new certificate was issued. Since the target CAs received particularly low-levels of customer traffic, the rate of counter increase could be estimated– although it took several attempts to get it exactly correct.

In well designed systems, it rarely takes a single failure to cause a catastrophic breakdown in security. Aside from clueless CAs using MD5 and signing whatever came their way, credit for the epic failure in PKI also goes to SSL client implementations which place equal value in all certificate authorities. A certificate is valid as long as it chains up to any trusted certificate authority– and there are about 100 of them in the Windows XP root store alone. Verisign USA, which issues the majority of SSL certificates including EV certs receives the exact same treatment as RapidSSL and FreeSSL– the latter two being examples of mismanaged CAs implicated in the attack. (Strangely enough, Verisign Japan and one CA affiliated with Thawte, another large issuer, were likewise flagged as issuing MD5 certificates.) Windows will cache previously validated certificates, to save time on future path validation efforts. But there is no logic to notice discrepancies and ask why Bank of America, which used to have a valid, unexpired GTE certificate has suddenly switched over to using an obscure CA based in Esthonia.

From a business perspective, it is not fair to blame MSFT for the proliferation of inept CAs. The company is backed into a corner: who are they to reject RapidSSL or any of the other dozens of dubious garage companies that will issue any certificate to anyone? Not when CA business model is getting paid for those certificates. If standards were raised to exclude some, the companies will cry tort interference. (Remarkably the Vista root store appears to have been cleaned up a bit.)  There are minimum standards around certificate practices, but historically the  whole concept of certifying the certifiers has been window dressing. Verisign issues 2 bogus Microsoft certificates in 2002. It was partly in recognition of this fact that “extended validation” certificates were introduced, creating a lucrative business opportunity to issue far more expensive certificates with supposedly real due diligence this time. This time, not all CAs were invited to that party.

As an aside, EV would have made no difference here contrary to the MSRC wishful thinking on mitigating factors. It is purely a visual indicator: cookies and cross-domain access are still allowed to EV-protected content from a vanilla SSL protected page in the same origin, allowing man-in-the-middle attacks to succeed. For example the attacker could allow the normal login page to be displayed to collect credentials, complete with the green address bar to inspire warm, fuzzy feelings with users. (Actually usability research says that users do not pay any attention to the EV indicator, but let’s suspend disbelief for a moment.) Only when the user enters a password and submits their credentials to the website, that connection is intercepted by the attacker who substitutes a bogus, non-EV certificate which still passes the hostname check with flying colors.

cemp