19 November 2001. Thanks to Scott Crosby.

See also Postscript version: http://nunce.org/hdcp/hdcp111901.ps (133KB)

The attacks on HDCP are neither complicated nor difficult.  They are basic linear algebra. Thus, there have been at least 4 independent discoveries of these flaws. The four I know of are my co-authors, Niels Ferguson, Keith Irwin [1], and myself[2]. The last two have been available publically for 3 months and 3 weeks prior to Niels Ferguson's declaration. Niels declaration and the Skylarov case were an eye-openers and made me fully realize what I had done, and what negative consequences I was in danger of experiencing.

What wrathful gods one can risk angering by a 20-minute straightforward application of 40-year-old math. For me, this was an accident, not a habit. Like other researchers, I do not want to be smited by angry gods, thus I do not expect to analyze any more such schemes as long as the DMCA exists in its current form. 

-- Scott Crosby

(This statement is my own and does not represent the opinions of my co-authors.)

[1] http://www.angelfire.com/realm/keithirwin/HDCPAttacks.html

[2] http://www.cryptome.org/hdcp-weakness.htm


A Cryptanalysis of the High-bandwidth Digital Content Protection System
PRESENTED AT ACM-CCS8 DRM WORKSHOP 11/5/2001

Scott Crosby
Carnegie Mellon University

Ian Goldberg
Zero Knowledge Systems

Robert Johnson         Dawn Song         David Wagner
University of California at Berkeley

What is HDCP?

High bandwidth Digital Content Protection (HDCP) is a system for preventing access to plaintext video data sent over Digital Visual Interface (DVI). Any technique that allows access to the plaintext data is considered breaking the system.

I show that with the public and private keys from 40 devices and $ O(40^2)$ work I can violate the design requirement--I can access the plaintext. Furthermore, with the 40 sets of keys and at most $ O(2^{40})$ offline work I can usurp the central authority completely.

The authentication process used in HDCP


The private key consists of a vector of 40 56-bit numbers.
The public key consists of a vector of 40 bits, half zero, half one.
Each device $ A,B, B^i$ has these keys assigned by a central authority.
Dot products are computed in the ring $ {\mathbb{Z}}{}/2^{56}{\mathbb{Z}}{}$.


$ A\rightarrow B:$		   $ \vec{A}_{public},n_{A}$

$ B:$		   $ K_{shared}=\vec{A}_{public} \cdot \vec{B}_{private},\;R=h(K_{shared},n_{A})$

$ B\rightarrow A:$		   $ \vec{B}_{public},R$

$ A:$		   $ K_{shared'}=\vec{B}_{public} \cdot \vec{A}_{private},\;R'=h(K_{shared'},n_{A})$
$ A:$   Verifies $ R=R'$ and $ \vec{B}_{public}$ is not on a blacklist.

The shared secret $ K_{shared}$ is reused later in the protocol.

The flaw


HDCP uses a linear system for generating the shared secret.


$\displaystyle \vec{A}_{public} \cdot \vec{B}_{private} = K_{shared} \overset{?}{=} K_{shared'} = \vec{B}_{public} \cdot \vec{A}_{private}$    


The flaw is that any device whose public key is a linear combination of public keys of other devices will, when assigned a private key that's a similar linear combination of the other devices private keys, successfully authenticate.

This flaw is fundamental, and cannot be worked around.

Proof of the break


I assume we have enough private keys $ \vec{B}_{private}^i$ whose public keys span $ M \subseteq ({\mathbb{Z}}{}/2^{56}{\mathbb{Z}}{})^{40}$, the module generated by all public keys assigned by the central authority. I assume that all of these devices will successfully authenticate with $ A$.

As the subspace is 40 dimensional, a set of at most 40 keys will be enough.

Consider any device $ C$ with $ C_{public} \in M$ whose public key and private key are any non-zero linear combination of $ B^k$'s public and private keys.

Say, $ \vec{C}_{public}=\sum_{i=1}^{40} a_i \vec{B}_{public}^i$

And, $ \vec{C}_{private}=\sum_{i=1}^{40} a_i \vec{B}_{private}^i$

Let $ A$ and $ C$ authenticate


$\displaystyle K_{shared}$ $\displaystyle = \vec{A}_{public} \cdot \vec{C}_{private} = \vec{A}_{public} \cdot \sum_{i=1}^{40} a_i \vec{B}_{private}^i$    
  $\displaystyle = \sum_{i=1}^{40} a_i (\vec{A}_{public} \cdot \vec{B}_{private}^i) = \sum_{i=1}^{40} a_i K_{shared}^i$    
$\displaystyle K_{shared'}$ $\displaystyle = \vec{C}_{public} \cdot \vec{A}_{private} = \vec{A}_{private} \cdot \sum_{i=1}^{40} a_i \vec{B}_{public}^i$    
  $\displaystyle = \sum_{i=1}^{40} a_i (\vec{A}_{private} \cdot \vec{B}_{public}^i) = \sum_{i=1}^{40} a_i K_{shared'}^i$    


When $ A$ and $ C$ authenticate


$\displaystyle \sum_{i=1}^{40} a_i K_{shared}^i = K_{shared} \overset{?}{=} K_{shared'}$ $\displaystyle = \sum_{i=1}^{40} a_i K_{shared'}^i$    



We know that $ K_{shared}^i = K_{shared'}^i$ for all $ i$ because by assumption, $ B^i$'s successfully authenticate with $ A$. Therefore, $ K_{shared} = K_{shared'}$ and this authentication succeeds.

Thus, for any device $ C$ with in $ C_{public} \in M$, we can decrypt any stream in $ O(40^2)$ work by rewriting $ \vec{C}_{public}$ as a linear combination of $ \vec{B}^i_{public}$.

Furthermore, we can forge keys in at most $ O(2^{40})$ work by enumerating all well-formed public keys and seeing if they're in $ M$. This completely usurps the central authority; we can do all that they can do.

In practice, I expect we can usurp the authority without this work factor.

Attacks that don't need the ability to forge


These avoid the hassle of finding well-formed public keys in $ M$.

We don't have to forge to be able to clone, eavesdrop, or avoid the blacklist. We do have a ready source of well-formed public keys: All devices come with such a key, and receivers supply their public key on demand.

We can masquerade as any receiver for whom we have their public key. Just sit in the middle between them and the transmitter, snarf the receivers public key, and use it as our own.

This can be done in $ O(40^2)$ work; by rewriting $ \vec{C}_{public}$ as a linear combination of $ \vec{B}^i_{public}$.

What about modifications? Longer key vectors?


If there are longer key vectors, the attacks continue to work, but we may not be able to forge because of the pesky well-formedness condition on public keys.

For example, they may chose a submodule where it may be hard to find a new key $ \vec{C}_{public} \in M$ that is well-formed. The best general algorithm I've found for finding well-formed keys is brute-force.

A variant of this problem is in is NP-complete (reduction from subset-sum).

But, longer key vectors do not make us immune from any of my non-forging attacks. I can decrypt, clone, and avoid any blacklist.

What about modifications? How about certificates?


Modify HDCP to add cryptographic certificates onto public keys so that each device includes a digital certificate on the device's public key signed by the central authority with some conventional algorithm (e.g., RSA). The receiver sends their public key and the certificate of the public key, authentication proceeds only if the certificate is verified.

Call this protocol HDCP+certs.

This scheme is susceptible to the attacks that do not require forging.

I conjecture based on the incomplete specification available that DTCP's Restricted Authentication Protocol may be a variant of HDCP+certs. If so, this raises serious questions about its design.

Conclusion


HDCP's linear key exchange is a fundamental weaknesses. We can:

The weaknesses are not easy to repair. Two proposed modifications are broken and still susceptible in $ O(n^2)$ work and $ n$ sets of keys to:

About this document ...


A Cryptanalysis of the High-bandwidth Digital Content Protection System
PRESENTED AT ACM-CCS8 DRM WORKSHOP 11/5/2001

This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html Cryptome-Presentation.tex -split 0

The translation was initiated by Scott Crosby on 2001-11-19


Scott Crosby 2001-11-19