15 August 2001: See also Keith Irwin's "Four Simple Cryptographic Attacks on HDCP:"

http://cryptome.org/hdcp-4attacks.htm

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 (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

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:

I assume that I can determine the private key array (A_{i})keys for
several devices that have different (A_{i})ksv's. This requires either
hardware hacking or software hacking...

Under these assumptions:

If I can determine 40 sets of vectors (A_{1})keys...
(A_{40})keys, where the corresponding 40 (A_{1})ksv ...
(A_{40})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
(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? 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: *A _{1}* ....

If 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. If device B can authenticate with A_{i}, then
we have the property that if we have

(Km_{i})'m = (A_{1})keys Bksv == Bkeys (A_{i})ksv = (K_{i})

Now, let:

Xksv = a,_{1}(A_{1})ksv + a_{2}(A_{2})ksv ... a_{n}(A_{n})ksv

we know that device B when authenticating with X will use a K_m that is:

K_{m}= Bkeys Xksv= Bkeys * (a_{1}(A_{1})ksv + a_{2}(A_{2})ksv ... a_{n}(A_{n})ksv)= a_{1}(A_{1})ksv Bkeys + ... a_{n}(A_{n})ksv Bkeys= a_{1}(K_{1})m + a_{2}(K_{2})m ... a_{n}(K_{n})m

IE: a linear combination of the Km's of the ones it uses for devices
A_{1} ... A_{n}. As we also know that (K_{i})'m ==
(K_{i}) for all I, we can compute the matching K'm:

K'm = a_{1}(K_{1})'m + a_{2}(K_{2})'m ... a_{n}(K_{n})'m;= a_{1}(A_{1})keys Bksv + .. a_{n}(A_{n})keys Bksv += [ a_{1}(A_{1})keys + ... a_{n}(A_{n})keys ] . Bksv

As the choice of *B* was arbitrary, the works for any B, and we can
let

Xkeys = a_{1}(A_{1})keys + ... a_{n}(A_{n})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 (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 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