> 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.
Re:HDCP master key allegedly posted
by tlrobinson on Tuesday September 14, 2010 @11:31AM
(#1690895)
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?
Re:HDCP master key allegedly posted
by logicalmind on Tuesday September 14, 2010 @05:28PM
(#1692389)
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.
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.