Hacker News Reader

Comment by nash | Hacker News Reader

I believe the update of keys relies on the secrecy of the master key, which is never released in a device.

Hence the master key pretty much kills it all.

HDCP key exchange is very weird cryptosystem. Usually you generate some essentially random private key and trivially derive public key from it. In HDCP, it works other way around: central authority has ability to convert (random) public keys to private keys using some secret information (purpotedly this matrix). Motivation of this design is twofold: (a) actual hardware implementation is simple and (b) this central authority can impose varios policies about who gets private keys. On the other hand both these points make this cryptosystem very weak.

Therefore, this matrix may not even be leaked, but somebody might reconstruct it from relatively small number (I don't remember exact required number, but i recollect that it is at most thousands) of keypairs recovered from devices in circulation.

By the way similar mode of deployment was once recommended for RSA (having shared modulus whose factorization is known to central authority), but it is long known to be insecure (for RSA). I don't know of any non-HDCP related analysis of public key cryptography based on similar approach as HDCP (vector summing or matrix multiplication, depending on viewpoint), which probably means that it is very well known to be insecure.

Edit: and for the key update: you would have to update all deployed keys simultaneously, which is probably impossible. Moreover HDCP does not even specify any kind of infrastructure to accomplish this.

I recall hearing ~50 keypairs would be required to reconstruct this matrix thing. Certainly there are more than 50 HDCP devices (manufacturers?)

Is this another lesson in why you should not invent your own crypto system?

They didn't actually invent their own crypto system. They used the scheme devised by Swedish cryptographer Rolf Blom, know as Blom's Scheme. Which is a form of "threshold secret sharing". It has been known for quite some time that the system falls apart once a particular number of keys are known.

I assume that each device should have it's own keypair, but it is only my assumption. I recall that HDCP somehow "does not work as intended" (whatever that means) when both devices have same key. And as for the ~50 number, that seems likely, I vaguely recollect that the required number was 40 (probably for 50% chance of success), but I don't remember the exact details and assumptions for this attack, so I take "at most thousands" as safe overestimation. Also I expect that time complexity of this attack (which is probably not exactly fast, as it entails solving pretty large system of equations) decreases with more known keys.

> Therefore, this matrix may not even be leaked, but somebody might reconstruct it from relatively small number (I don't remember exact required number, but i recollect that it is at most thousands) of keypairs recovered from devices in circulation.

According to Wikipedia, you only need to collect 39 Dragon Balls to reconstruct the master matrix.

http://en.wikipedia.org/wiki/Hdcp#Cryptanalysis

Reply on news.ycombinator.com