9 May 2001. Updated by SC request at 5:55 PM.
Scott A. Crosby <crosby@qwes.math.cmu.edu>
Wed May 9 13:02:56 EDT 2001
Distribution status: Distributable anywhere as long as attributation is
given.
I think I've found a few weaknesses in the High-bandwidth Digital Copy Protection System (HDCP) [1], at least as enumerated in the 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 HDCP 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 (Ai)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 (Ai)keys at the offsets in (Aj)ksv. Device j adds together elements in its vector of (Aj)keys at the offsets in (Ai)ksv. The 56 bit shared secrets are Km 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 Km.
What I have:
I assume that I can determine the private key array (Ai)keys for several devices that have different (Ai)ksv's. This requires either hardware hacking or software hacking...
Under these assumptions:
If I can determine 40 sets of vectors (A1)keys... (A40)keys, where the corresponding 40 (A1)ksv ... (A40)ksv's are linearily independent, then I can completely break the system; I can determine the secret key array Xkeys for any Xksv that I wish.
In other cases where the seperate keys are not linearily independent, I can still creat Xkeys for any Xksv that is within the span of the (Ai)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? Straightforward linear algebra.
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: A1 .... An, and I knew the Xksv from system X (this is public information from the protocol), then they could determine the Xkeys private key array.
If assume that I have 40 (Ai)ksv's that are linearily independent.
I know:
[ Xkeys ] * (A1)ksv == [(A1)keys ] * Xksv
[ Xkeys ] * (A2)ksv == [(A2)keys ] * Xksv
...
[ Xkeys ] * (A40)ksv == [(A40)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. (Ai)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 (Ai)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 (Ai)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. If device B can authenticate with Ai, then we have the property that if we have
(Ki)'m = (A1)keys Bksv == Bkeys (Ai)ksv = (Ki)m
Now, let:
Xksv = a1 (A1)ksv + a2 (A2)ksv ... an (An)ksv,
we know that device B when authenticating with X will use a K_m that is:
Km = Bkeys Xksv
= Bkeys * (a1 (A1)ksv + a2 (A2)ksv ... an (An)ksv)
= a1 (A1)ksv Bkeys + ... an (An)ksv Bkeys
= a1 (K1)m + a2 (K2)m ... an (Kn)m
IE: a linear combination of the Km's of the ones it uses for devices A1 ... An. As we also know that (Ki)'m == (Ki) for all I, we can compute the matching K'm:
K'm = a1 (K1)'m + a2 (K2)'m ... an (Kn)'m;
= a1 (A1)keys Bksv + .. an (An)keys Bksv +
= [ a1 (A1)keys + ... an (An)keys ] . Bksv
As the choice of B was arbitrary, the works for any B, and we can let
Xkeys = a1 (A1)keys + ... an (An)keys
And X can authenticate successfully to B.
So thus, for any other Xksv with 20 one bits, and 20 zero bits in the subspace spanned by the (Ai)ksv's for which we know the corresponding (Ai)keys, we can construct a valid Xkeys through a linear combination of the (Ai)key's we know.
The only trick is finding a Xksv in the subspace that has the required number of 0 and 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'er 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