14 September 2010. Via Reddit, HDCP Master Key: http://pastebin.com/kqD56TmU

20 November 2001. See latest report on cryptanalysis of HDCP by Scott Crosby and others:

http://cryptome.org/hdcp/hdcp111901.htm

9 May 2001

Apparent HDCP authentication protocol weaknesses

Scott A Crosby <crosby@qwes.math.cmu.edu>

May 9 13:02:56 EDT 2001

Distribution status: Distributable anywhere as long as attributation is given.

Hello... I think I've found a few weaknesses in HDCP[1], at least as enumerated in this purported revision 1.0 specification. HDCP is a control technology designed to encrypt and authenticate high speed digital video interfaces from playback devices to display devices.

As I am unqualified to judge the cryptography, I looked at other places that seem breakable. One thing that caught my attention was the initial authentication (Section 2.2 in the specification).

How it authenticates: Each device is given a 40-bit public device ID, the (A)ksv. Each device also has a secret vector of 40 56-bit (A_i)keys numbers. (A)ksv has the property that it has 20 'one' bits and 20 'zero' bits.

To construct a shared secret for devices i, j by adding together the elements in its (A_i)keys at the offsets in (A_j)ksv. Device j adds together elements in its vector of (A_j)keys at the offsets in (A_i)ksv. The 56 bit shared secrets are K_m for the transmitter and K'_m for the receiving device. They should be identical if authentication is successful, and be different otherwise.

Then, as is usual, the receiving device encrypts a nonce received from the transmitter with K'_m and sends it to the transmitter. The transmitter verifies that it matches the nonce encrypted with K_m.

What I have:

If I can determine 40 linearily independent sets of vectors (A_1)keys ... (A_40)keys, say, through reverse-engineering hardware. then I can completely break the system; I can determine the secret key array for any Xksv that I wish.

In other cases where the seperate keys are not linearily independent, I can still crate Xkeys for any Xksv that is within the span of the (A_i)ksv's for which I have found the private keys. (Though I have no guarentee of them satisfying the 20 one and 20 zero bits property.)

--

So, how can this be broken?

First, it is rare to find Akeys's, Bkeys's, Aksv and Bksv that have the above property that when each device does the operation, they can both come up with the same shared secret. There is some mathematical model that creates such subsets.

Since the keys are generated linearly in the given system, it appears that if someone could determine the Akeys vector from any 40-50 different systems: A_1 .... A_n, and I knew the Xksv from system X (this is public information from the protocol), then I could determine the Xkeys private key array.

If I assume that I have 40 (A_i)ksv's that are linearily independent.

I know:

[ Xkeys ] * (A_1)ksv == [(A_1)keys ] * Xksv [ Xkeys ] * (A_2)ksv ==
[(A_2)keys ] * Xksv ...  [ Xkeys ] * (A_40)ksv == [(A_40)keys ] * Xksv

Which is a set of n linear equations on 40 unknown -- the Xkeys key vector array. I know all the ksv's, and I assume I know the secret key vectors (A_i)keys.

Now, to generate a new Bkeys for any other device with an arbitrary Bksv. Well, we can repeat the above algorithm: We let Xksv = Bksv$, and then we're done.

If the space spanned by the (A_i)ksv's doesn't span the full 40 dimensional space, we're probably OK. Either, the ksv's were designed to not span the space, or we need to get the (A_i)keys from a few more devices to round out the space. (Each additional device has low odds of being linearly dependent with the existing set. Roughly 1/2^(40-dimensionality-of-spanned-space)

Otherwise, this linear dependence was done on purpose. Thus, we know that all other ksv's are in the space spanned by the one we're given.

We can construct a valid Xksv and Xkeys from a linear combination of any that we already know. So thus, for any other Xksv with 20 one bits, and 20 zero bits in the subspace spanned by the (A_i)ksv's for which we know the corresponding (A_i)keys, we can construct a valid Xkeys through a linear combination of the (A_i)key's we know.

The only trick is finding a Xksv in the subspace that has the required number of 0 & 1 bits. This is the only potentially difficult part, though given a concrete example, I think it would not be difficult.

----

Implications:

1: They cannot allow the public disclosure of Akeys from more than 39 linearily independent devices without breaking security entirely.

2: Each successive linearily independent break approximately doubles the number of forgable keys.

3: Thus, their revocation mechanism as stated, does not have the properties I believe they expected.

4: Or, I am an idiot and made one or more stupid mistakes.

Fixes to the algorithm

1: Have at most 39 Aksv vectors total.

2: Revocation revokes a subspace spanned by a set of vectors, not just a single vector.

3: Replace the mechanism with one with non-linearity.... I have a few ideas that may work.

4: Give up, if someone can examine your hardware, you're dead any way you roll it.

--

All in all, studying this mechanism was an interesting process. The mathematics of this part of the specification is simple and elegant which facilitates analysis by people who are non-expert in differential cryptoanalysis or such.

The state machines are unwieldy. I may get around to feeding them to a modelchecker to determine what security properties they posess.

Scott A. Crosby

____________________________

[1] High Bandwidth Digital Content Protection System

http://cryptome.org/hdcp-v1.htm