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 , and myself. 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.)
Carnegie Mellon University
Zero Knowledge Systems
Robert Johnson Dawn Song David Wagner
University of California at Berkeley
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 work I can violate the design requirement--I can access the plaintext. Furthermore, with the 40 sets of keys and at most offline work I can usurp the central authority completely.
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 has these keys assigned by a central authority.
Dot products are computed in the ring .
|Verifies and is not on a blacklist.|
The shared secret is reused later in the protocol.
HDCP uses a linear system for generating the shared secret.
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.
I assume we have enough private keys whose public keys span , the module generated by all public keys assigned by the central authority. I assume that all of these devices will successfully authenticate with .
As the subspace is 40 dimensional, a set of at most 40 keys will be enough.
Consider any device with whose public key and private key are any non-zero linear combination of 's public and private keys.
We know that for all because by assumption, 's successfully authenticate with . Therefore, and this authentication succeeds.
Thus, for any device with in , we can decrypt any stream in work by rewriting as a linear combination of .
Furthermore, we can forge keys in at most work by enumerating all well-formed public keys and seeing if they're in . 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.
These avoid the hassle of finding well-formed public keys in .
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 work; by rewriting as a linear combination of .
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 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.
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.
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 work and sets of keys to:
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