Dan Kaminsky's Blog

You know what’s great about being a nerd?

You get to write blog posts linking TRON: Legacy to actual important things, and you get to be totally shameless about it.

So, today, lets talk a little about one of my favorite things:  Isomorphisms.

What are they, you may ask?  Well, they’re not a new species of artificial life that lives on the Grid.  Not exclusively, anyway.  The Science Dictionary defines them as:

A one-to-one correspondence between the elements of two sets such that the result of an operation on elements of one set corresponds to the result of the analogous operation on their images in the other set.

Put another way, they’re two things that appear separate and distinct, but in fact possess such deep underlying similarity that anything you can do to one, you can do to the other.  The best explanation I’ve seen for their underlying importance comes from Stephen De Beste:

Mathematics is only useful to us because of its isomorphism to various real world operations; without it, all mathematics would be nothing more than an interesting intellectual puzzle. The only pitfall is when we think we can construct the two transform functions and assume an isomorphism which isn’t there; if we’re mistaken, then math will give us the wrong answer. It’s not that the math is false, rather it’s that either the transforms were incorrect or the function we tried to use wasn’t really isomorphic to the physical reality. For example, if we try to navigate a globe using a flat map and Euclidean geometry, we’ll get lost. Plane geometry is not isomorphic to nagivation on the surface of a sphere. Spherical geometry, on the other hand, is.

Technically, isomorphisms represent perfect, if transformed relationships.  So the fact that the earth is not, in fact, perfectly spherical (it’s a little bulgy) should break the isomorphism.  But it doesn’t — once you introduce the real world, you’re allowed a bit of fuzziness.  God plays dice, as it turns out.

Isomorphisms are interesting — they show up in security all the time, more often in fact than people realize.  They are most commonly recognized in cryptography, where it’s a very normal thing to “translate” one problem into another domain in which cracking or analysis requires less work.  What’s fascinating is not when such isomorphic translation helps, but when it doesn’t:  The apparently dissimilar problem of prime factorization — at the heart of RSA — and discrete logarithm — at the heart of Diffie-Helman — are in fact isomorphic.  As per Eric Bach, circa 1984:

To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes.

Apparent dissimilarity yields to ultimate similarity: if and when RSA falls, so too will Diffie-Helman, and vice versa.

Isomorphisms also show up in binary reverse engineering, where though the code may change, the relationships between segments of code don’t — and thus, “prepatch” and “postpatch” functions become recognized by their graph isomorphisms.

All P2P DNS systems are isomorphic to one another.  You can tell, they all fail for pretty much all the same reasons.  Distributed money systems too, it seems.  (Subject for another post.)

More obscure are the isomorphisms of the web.  For example, consider the following two features:

• Third party Tracking
• Single Sign On

The former is considered a troubling and ancient problem in the core privacy model of the web.  The latter is considered a critical security technology, part of how we will eventually get past the curse of passwords.

They’re the same technology — or, at least, they’re isomorphic to one another.  Any system that can implement one, can implement the other.  Any system that cannot implement one cannot implement the other.  This becomes obvious once you expand their definitions:

• In Third Party tracking, Bob and Charlie work with David to find out that Alice is browsing both of them
• In Single Sign on, Bob and Charlie work with David to authenticate that it’s Alice browsing both of them

Basically, in Single Sign On, the user enters his credentials and is given a cookie.  In Third Party Tracking, the user is just given a cookie.  After the first exchange, they’re the exact same technology. They’re completely isomorphic.

“But wait!”, you say.  “What about the browsers!  They include the capability to block third party cookies!  Are you saying that breaks Single Sign On?”

Yes, which is why the the feature is disabled by default and effectively nobody uses it.  Machines just cannot be made to reliably distinguish between two isomorphic expressions of the exact same technology.  And you’re not allowed to break the web.  Jeremiah Grossman and I go back and forth on this — but, put simply, Microsoft tried breaking the web, just a little.  They made some critical changes to IE, changes that effectively eliminated ActiveX as a major exploit vector.

Have you noticed how IE6 won’t go away?

Yeah.

The worst part is, unless you’re willing to thoroughly smash the web, you can’t even break the attack.  As Samy’s Evercookie showed, there will always be somewhere to hide long term state (here’s a good example:  TLS requires cookies in order to scale!).  Trying to technically block them all is whack-a-mole — the fundamental design is just not backing you up.

Where the isomorphism is in fact disambiguated, is in human interpretation.  Most engineers look down on policy-driven approaches — this has a lot to do with badly designed policies, frankly — but while a client can’t distinguish between a server implementing SSO and an ad server, management, industry, and regulators can.  So I happen to be something of a fan of the American FTC”s Do-Not-Track header, which effectively flips the burden of blocking tracking from the user and his browser to the provider and his legitimate offering.

It’s hard to argue you didn’t know the user wanted to be left out of tracking, when he told you on each HTTP request.  And it creates a much less messy situation than what’s going on with YouPorn, in which (when you get down to it) an element of the browser DOM was read back, when it shouldn’t have been exposed in the first place.

If you don’t think the YouPorn situation is messy, you’re not realizing just how many organizations have that exact sort of data, collected server side via ad networks and cookies instead of client side via a browser design flaw in the DOM.  Not a precise isomorphism…but not, not.

Of course, the ultimate isomorphism is that the web is still the result of human labor, and that labor still needs to be paid for, either directly through transfer of fees or indirectly through advertising.  Thus far, the social contract that paid for it all was simple:  If the browser lets you do it, you can do it.  (The browser blocks 99% of what the PC can do — thus is the price we’ve paid for ease of deployment and security.)  Figuring out a new social contract, one guided not by technical capability but by committee decision making, is more than a little scary.  Will web sites be subject to deep regulatory approval?  Will they turn into UAC-ish experiences, with a popup required for each new ad provider?  The EU has been struggling with all this.  Such are the consequences of the non-isomorphic solution…