

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 weaknessesScott 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 40bit public device ID, the (A)ksv. Each device also has a secret vector of 40 56bit (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 reverseengineering 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 4050 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^(40dimensionalityofspannedspace) 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. Fixes to the algorithm 1: Have at most 39 Aksv vectors total.  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 nonexpert 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/hdcpv1.htm
