Digital PDFs

XX-XXXXX-XX

2000

8 pages

Original

82.5kB

Document:	Lost document 26285
Order Number:	XX-XXXXX-XX
Revision:	000
Pages:	8
Original Filename:	http://www.digiater.nl/openvms/decus/vmslt06a/net/a-cryptanalysis-of-the.pdf

OCR Text

A Cryptanalysis of the High-bandwidth Digital Content
Protection System
Scott Crosby1 , Ian Goldberg2 , Robert Johnson3 , Dawn Song3 , and David Wagner3
1

Carnegie-Mellon University
Zero Knowledge Systems
3 University of California at Berkeley
2

Abstract. We describe a weakness in the High Bandwidth Digital Content Protection (HDCP) scheme which may lead to practical attacks. HDCP is a proposed
identity-based cryptosystem for use over the Digital Visual Interface bus, a consumer video bus used to connect personal computers and digital display devices.
Public/private key pairs are assigned to devices by a trusted authority, which possesses a master secret. If an attacker can recover 40 public/private key pairs that
span the module of public keys, then the authority’s master secret can be recovered in a few seconds. With the master secret, an attacker can eavesdrop on
communications between any two devices and can spoof any device, both in real
time. Additionally, the attacker can produce new key pairs not on any key revocation list. Thus the attacker can completely usurp the trusted authority’s power.
Furthermore, the protocol is still insecure even if all devices’ keys are signed by
the central authority.
t
u

1 Introduction
The High-bandwidth Digital Content Protection (HDCP) scheme is a cryptographic
extension to the Digital Visual Interface (DVI) designed to prevent the copying of video
data transmitted over the DVI bus. DVI is already commonly used between personal
computers and display devices such as LCD monitors. If the HDCP enhanced DVI
standard is also adopted by monitor and television manufacturers, then it could serve
as the last leg of a secure channel for the online distribution of television, movies,
and other video data. Online content distributors would like to build this channel to
prevent perfect digital copies by never exposing the digital video signal as plaintext in
the receiver’s computer.
Because DVI devices from many different manufacturers need to interoperate and
perform key exchange with no user intervention, the HDCP authors chose to use an
identity-based cryptosystem. It appears that the authors wanted the implementation of
the scheme to be extremely low cost, and so avoided any of the conventional public-key
schemes in the literature [1–5]. In personal communication with the HDCP authors, we
learned that they designed HDCP to be implementable in fewer than 10,000 gates[6].
This stringent design requirement led the HDCP authors to develop custom algorithms
which are insecure.
In the HDCP scheme, device manufacturers purchase HDCP licenses from a trusted
authority. A license includes, for each device A, a public vector vA , called the Key

Selection Vector (KSV), and a private vector, uA . When devices A and B wish to communicate, they exchange vA and vB . Device A computes the dot product uA · vB and B
computes uB · vA , and they use this as their shared secret for the rest of their interactions. The trusted authority uses some secret information to choose vA , vB , uA , and uB
so that the above computations will produce the same answer. This protocol is used in
both the Upstream and Downstream versions of HDCP. The Upstream version of HDCP
is designed for the communication link between software running on a personal computer, such as a user friendly video playback utility, and the HDCP devices attached
to that computer. The Downstream protocol is used between HDCP devices. Since the
cryptographically relevant portions of these protocols are identical, our attack applies
to both.
Our purpose in presenting these results is not to enable illegal copying. Rather, we
hope to advance the cryptographic science, to help systems designers build more secure
systems in the future, and to help users assess what level of security they can reasonably
expect from these technologies.
We observe that attackers can exploit a well-known cryptographic design mistake:
the shared secret generation is entirely linear. The attack only needs 40 public/private
key pairs such that the public key pairs span M ⊂ (Z/256 Z)40 , the module generated by
all public keys. Since HDCP devices divulge their public keys freely, one can easily test
whether a set of 40 devices have public keys spanning M before expending the effort
to extract their private keys. With these keys, the authority’s secret can be recovered in
only a few seconds on any desktop computer.
The consequence of these flaws is that, after recovering the private keys of 40 devices, one can attack every other interoperable HDCP device in existence: an attacker
can decrypt eavesdropped communications, spoof the identity of other devices, and even
forge new device keys as though he were the trusted center. Note that this allows an attacker to bypass any revocation list or “blacklisting”: such mechanisms are rendered
completely ineffective by these flaws in HDCP. We also describe several further attacks on the HDCP protocol (see Section 6). Therefore we recommend that the current
HDCP cryptosystem should be abandoned and replaced with standard cryptographic
primitives.
The HDCP cryptosystem is also unusual in that it can be broken without fully understanding its operation. The HDCP specification does not describe the key generation
process used by the center but, based solely on the properties of generated keys, we can
characterize all possible key generation strategies and show that they are all insecure. In
other words, we can prove, given just the interface, that every possible implementation
that follows this interface is insecure.

2 Related Work
Blom described a scheme very similar to HDCP as an alternative to the emerging publickey schemes of the time[7, 8]. He realized immediately the danger of colluding users,
and tried to maximize the number of traitors required to compromise the scheme while
minimizing the storage requirements placed on the system’s users. We should note that
since HDCP is closely related to Blom’s protocol, it achieves the same storage lower-

A → B : v A , nA
B : K 0 = vA · uB , R0 = h(K 0 , nA )
B → A : v B , R0
A : K = vB · uA , R = h(K, nA )
A : Verifies R = R0
Table 1. The HDCP Authentication Protocol

bound he presented in his paper. Blom’s analysis considered only information-theoretic
security; we show that with only a small number of colluding users, the scheme is
computationally insecure, as well.
Other researchers have looked at HDCP, too. An author of the present paper informally published similar results[9]. Irwin independently discovered this attack, and
pointed out several other weaknesses in HDCP[10]. Niels Ferguson has discovered
weaknesses in HDCP, but has not published them because of the Digital Millennium
Copyright Act[11].

3 The HDCP Authentication Protocol
The HDCP protocol is described completely in [12]. We present an abstracted version that captures the cryptographically relevant portions of both the Upstream and
Downstream versions of HDCP. A trusted authority assigns to each device, A, a public
vector vA ∈ (Z/256 Z)40 , called the Key Selection Vector (KSV), and a private vector,
uA ∈ (Z/256 Z)40 . The vector vA consists of 20 zeros and 20 ones. The vector uA must be
kept in tamper-proof hardware or, in the case of a software implementation, obscured
by code obfuscation techniques. When devices A and B wish to communicate, they exchange vA and vB . A computes K = uA · vB and B computes K 0 = uB · vA . The trusted
authority has used some secret information to choose vA , vB , uA , and uB so that K = K 0 .
In HDCP, one device is the transmitter and one is the receiver. To verify that the key
agreement process has been successful, the transmitter A also sends a nonce n A , and the
receiver replies with the 16-bit value R0 computed by R0 = h(K 0 , nA ). The transmitter
performs the analogous computation and verifies that the results are the same. The noninvertible function h is completely described in the specification, but the details of its
operation are not important here. We assume that all DVI transmitters can interoperate
with all DVI receivers, an assumption that seems to be implied by the specification.
HDCP also supports revocation of certain KSVs. Transmitters are required to check
that their peer’s KSV is not on the current revocation list. According to the HDCP
license, KSVs can be placed on the KRL if the corresponding private key has been
leaked, or if requested by the National Security Agency.

4 Linear Algebra over Z/256 Z
Computations in HDCP are done in the ring Z/256 Z. Since Z/256 Z is not a field, not
all the basic facts from linear algebra hold in this setting. Nonetheless, much of our

Name
Size
Comment
vA , vB
40 bits
Must have Hamming weight 20
uA , uB Vector of 40 56-bit numbers
nA
64 bits
K, K 0
56 bits
K = vB · uA, K 0 = vA · uB
R, R0
16 bits
R = h(K, nA ), R0 = h(K 0 , nA )
Table 2. Summary of HDCP Protocol Variables

intuition carries over with not too many changes. In this section we set down the few
results we need. These results are not new, but some of them are a bit obscure, so we
include them here. Let R = Z/pn Z, where p is prime. The following fact is used without
proof.
Fact 1. The standard determinant function, det, is multiplicative, and a matrix T is
invertible if and only if det T is a unit in R. Since R = Z/pn Z, this implies T is invertible
if and only if gcd(det T, pn ) = 1.
R has exactly one chain of ideals, (0) = (pn ) ⊂ (pn−1 ) ⊂ . . . ⊂ (p1 ) ⊂ (p0 ) = R.
This makes Gaussian elimination work almost as well as over a field.
Proposition 1. Any m × n matrix A over R can be transformed, via invertible row operations, into an upper triangular matrix such that if the leading nonzero term of row
i is in column j, then the leading nonzero term of row i + 1 is in column j + 1 or later.
Furthermore, the leading terms will all be powers of p.
Proof. The Gaussian elimination algorithm need only be modified slightly.


a1,c
1



 0 ...




ak,c


k



0 ak+1,c ∗ · · · ∗ 
A=

k+1

∗
··· 



 ..
..
..
 .
.
.
··· 




0
0
∗
··· ∗
Let c1 be the first non-zero column. Let r1 be a row such that, for all r, (ar,c1 ) ⊆ (ar1 ,c1 ).
By dividing row r1 by a unit, we can transform ar1 ,c1 into pe1 for some e1 . We then
interchange row r1 with row 1. We can now use row 1 to cancel all the other non-zero
terms below a1,c , since the column c1 entries of all the other rows now lie in (a1,c ). We
1
1
now repeat with column c2 , the first column with a non-zero entry in rows 2, . . . , m, and
so on. If, after swapping, entry ak,c = 1, then we may optionally use row k to cancel
k
the non-zero terms above ak,c . It is a standard fact that the row operations used here are
k
invertible.

Define σ : (Z/256 Z)40 → Z/256 Z by σ (v1 , . . . , v40 ) = ∑40
i=1 vi . Then, since KSVs
have Hamming weight 20, for any KSV v, σ (v) = 20. Since σ is linear, σ applied to
any linear combination of KSVs will be in the ideal (4) ⊂ Z/256 Z. Since not all vectors
α in (Z/256 Z)40 have σ (α ) ∈ (4), no set of KSVs will ever span (Z/256 Z)40 . Let M
be the module spanned by all possible KSVs. The following proposition tells us when
a set of KSVs spans M.
Proposition 2. A set of KSVs v1 , . . . , v40 spans M if and only if the matrix V whose rows
are v1 , . . . , v40 has gcd(detV, 256 ) = 4.
h i
Proof. Let V 0 = v0i j be the result of applying the above Gaussian elimination algorithm to V . Since the Gaussian elimination is invertible, there exists a matrix U, with
gcd(detU, 256 ) = 1, such that V 0 = UV . Thus detU −1 detV 0 = detV . Since detU −1 is
coprime to 256 , we must have gcd(detV 0 , 256 ) = gcd(detV, 256 ) = 4. Since V 0 is upper
40 0
0
0
0
triangular, detV 0 = ∏40
i=1 vii . But vii is a power of 2 for each i, so detV = ∏i=1 vii = 4.
0
0
Since the only nonzero entry in row 40 is v40,40 , we must have v40,40 a multiple of 4 by
σ considerations. Since detV 0 = 4, V 0 has the following form.


1 0 0∗
 ..



V0 = 0 . 0 ∗
0 0 1 ∗
0 0 04
Let v0i be the ith row of this matrix. If w = (w1 , . . . , w40 ) is a KSV, then put w0 = w −
0
0
0
56
0
∑39
i=1 wi vi = (0, . . . , 0, w40 ). As we observed above, σ (w ) = w40 , lies in (4) ⊂ Z/2 Z.
39
0
0
0
So there exists a c such that w40 = 4c. Hence w = ∑i=1 wi vi + cv40 . Note that this does
not prove the existence of a KSV matrix V with gcd(detV, 256 ) = 4, but such matrices
can easily be found experimentally. Thus the rows of the matrix V 0 above do lie in M.
If, on the other hand, v1 , . . . , v40 span M, then there exists a matrix U such that
V 0 = UV . Thus, by the multiplicativity of det, gcd(detV, 256 ) is at most 4. By a σ
argument similar to the above, gcd(detV, 256 ) is at least 4. Thus gcd(detV, 256 ) = 4.
It will also be useful to know the probability that 40 + m KSVs contain a set of 40
KSVs that span M. The following table was created by generating 10000 sets of 40 + m
random KSVs and testing whether the set contained a spanning subset of 40 KSVs.
Number of KSVs 40 42 44 46 48 50
Prob. of Spanning M .295 .773 .940 .982 .997 .999

5 The Authority’s Secret
We now prove that the authority’s secret information can be recovered by an attacker.
The main insight is that the secret can be captured in a 40 × 40 matrix, and hence
techniques from linear algebra suffice to recover it. Before we proceed, we must note
that the center may choose to issue only KSVs from a submodule, N, of M, the module
spanned by all KSVs.

Observation 1. Let v be a KSV, and suppose u1 and u2 are both valid private keys for
v. Then u1 − u2 ∈ N ⊥ .
Proof. Let (v0 , u0 ) be any other valid key pair. Since v0 · u1 = v · u0 = v0 · u2 , we have
v0 · (u1 − u2 ) = 0 for all v0 ∈ N.
The content of this observation is that, if two different key vectors, uA and u0A , form
valid key pairs with the same KSV, then K = K 0 = uA · vB = u0A · vB for all devices B.
Hence uA and u0A are functionally indistinguishable.
Corollary 1. The map T : M → (Z/256 Z)40 , mapping public keys to private keys, is
well defined mod N ⊥ .
We can now prove that the map S has a particularly nice form.
Observation 2. T can be represented by a 40 × 40 matrix, S.
Proof. To show that a map can be represented by a matrix, we only need to show that
it is linear. So let v = cv1 + v2 . Then (cT (v1 ) + T (v2 )) · v0 = cT (v1 ) · v0 + T (v2 ) · v0 =
cT (v0 ) · v1 + T (v0 ) · v2 = T (v0 ) · v = T (v) · v0 , for arbitrary v0 ∈ N. Thus T (v) = cT (v1 ) +
T (v2 ) mod N ⊥ .
Recovering S is now straightforward. First collect a set of key pairs (vi , ui )ni=1 such
that the vi span N. Then use any standard technique to solve the systems of equations
U = SV . For example, the Gaussian elimination algorithm of Section 4 can be applied
here. This allows an attacker to recover all of the trusted center’s secret, no matter how
the center picks keys.

6 Forging Key Pairs
Let G be a matrix recovered as in Section 5. Then G and S agree on the submodule
spanned by the recovered vectors v1 , . . . , vn , and quite probably disagree everywhere
else. If v1 , . . . , vn span M, then G is equivalent to S. In other words, Gv = Sv for all
valid KSVs v. Thus, to forge a new key pair, one can simply pick a random KSV, v, and
compute the corresponding private key u = Gv.
The authority may try to prevent the total recovery of S by only assigning to devices
key pairs with KSVs in a submodule of N ⊂ M. If hv1 , . . . , vn i = N 6= M, then attackers
using linear algebra can only forge key pairs (v, u) where v ∈ N. Finding new KSVs
in the span of the recovered KSVs may be difficult.1 This could be a problem if the
attacker wishes to build a device that interoperates with other HDCP devices and if the
authority has placed all recovered KSVs on the key revocation list.
However, the HDCP protocol does not require devices to check that their peer’s key
is not the same as their own, and so a “parroting” attack is possible. To build an interoperable receiver, we can simply embed the matrix G in the device, and program it to
1 It’s not hard to reduce the subset-sum problem to the problem of finding a new KSV in the span

of some other KSVs. However, since the dimension is only 40, an attacker could brute-force
this problem if necessary.

reply to all authentication challenges with the KSV it just received from the transmitter.
It can compute the corresponding private key on the fly and proceed with the authentication protocol. We note that an attacker could use essentially the same trick to build an
interoperable transmitter, but the transmitter will have to perform two authentications.
The first time, it will send a random KSV and collect the KSV of its peer. The transmitter will then abort the authentication and restart it using the KSV it just learned from
the receiver. This attack only works if the authority uses the same mapping, T , for both
transmitters and receivers. For reasons of clarity, we have made this assumption in our
presentation of HDCP and our other attacks. The other claims in this paper hold in the
more general setting, but the parroting attack does not.
One might be tempted to correct the defects in HDCP by signing the KSVs with
a private key known only to the central authority. Then, when two devices execute the
authentication protocol, they exchange the certificates containing their KSVs, verify
each others’ certificates using the authority’s public key, and proceed as before. This
change accomplishes very little. Eavesdropping would still be possible since the certificates, and hence the KSVs, of each device would be available to the eavesdropper
who could then compute the corresponding private keys needed to decrypt the traffic.
Devices would still be clonable by embedding the victim’s certificate and private key
in the clone. The paroting attack above is still available, too. The only thing certificates
prevent is forging new keys. The Digital Transmission Content Protection (DTCP) standard includes a Restricted Authentication protocol that may be just such a certificateenhanced variant of HDCP [13]. The information needed to fully evaluate the security
of DTCP is not publicly available, but what little is public gives reason to be sharply
concerned that DTCP’s restricted authentication protocol may be susceptible to similar
attacks.

7 Conclusion
These attacks are very powerful and very flexible. To recover the center’s master secret, an attacker needs 40 key pairs, and we point out a variety of ways to get them. An
attacker can reverse engineer 40 different HDCP video software utilities, he can break
open 40 devices and extract the keys via reverse engineering, or he can simply license
the keys from the trusted center. According to the HDCP License Agreement, device
manufacturers can buy 10000 key pairs for $16000. Given these 40 spanning keys, the
master secret can be recovered in seconds. So in essence, the trusted authority sells a
large portion of its master secret to every HDCP licensee. With the master secret in
hand, one can eavesdrop on all device communications, spoof any device, and clone
any device, all in real time. One can produce a device that, by parroting back the KSVs
of its peers, cannot be disabled by any blacklist. With a reasonable amount of computation, an attacker can also produce new device keys not on any key revocation list.
For these reasons, we recommend that HDCP be abandoned in favor of conventional
cryptographic schemes.
The HDCP design requirements called for an implementation in less than 10,000
gates. The fact that the designers chose a custom cryptosystem instead of off-the-shelf
algorithms shows that there is work to be done in the area of efficient, secure hard-

ware design. A brief search for the state-of-the art turned up an RSA implementation
in 18,000 gates[14] 2 , and the KASUMI cryptosystem, which can be implemented in
3,000 gates[15]. 3 Coupling these with a generous 9,000 gates of HDCP state machine
would give a secure authentication and encryption subsystem in under 30,000 gates, but
building a secure system in 10,000 gates is still a challenge.

Acknowledgements
We would like to gratefully acknowledge Intel and Digital Content Protection, LLC for
helpful comments on this paper and for pointing us to Blom’s work on key distribution systems. We thank Adrian Perrig for suggesting identity-based cryptosystems as a
secure alternatve to HDCP.

References
1. A. Shamir. Identity-based cyrptosystems and signature schemes. In Crypto’84, 1984.
2. Y. Desmedt and J. Quisquater. Public-key systems based on the difficulty of tampering. In
Crypto’86, 1986.
3. H. Tanaka. A realization scheme for the identity-based cryptosystem. In Crypto’87, 1987.
4. S. Tsuji and T. Itoh. An ID-based cryptosystem based on the discrete logarithm problem. In
IEEE Journal of Selected Areas in Communication, volume 7, 1989.
5. Dan Boneh and Matthew Franklin. Identity-based encryption from the Weil pairing. In
CRYPTO’2001, 2001.
6. David Barth. Personal communication. September 2001.
7. Rolf Blom. An optimal class of symmetric key generation systems. In T. Beth, N. Cot, and
I. Ingemarsson, editors, Proc. EUROCRYPT 84, pages 335–338. Springer-Verlag, 1985.
8. Rolf Blom. Non-public key distribution. In R. L. Rivest, A. Sherman, and D. Chaum, editors,
Proc. CRYPTO 82, pages 231–236, New York, 1983. Plenum Press.
9. Scott Crosby.
Apparent HDCP authentication protocol weaknesses.
http://cryptome.org/hdcp-weakness.htm, May 2001.
10. Keith
Irwin.
Four
simple
cryptographic
attacks
on
HDCP.
http://www.angelfire.com/realm/keithirwin/HDCPAttacks.html,
July 2001.
11. Niels Ferguson.
Censorship in action: Silenced by the DMCA.
http://www.macfergus.com/niels/dmca/index.html, August 2001.
12. Intel Corporation. High-Bandwidth Digital Content Protection System, 1.00 edition, February 2000.
13. Hitachi, Ltd. and Intel Corporation and Matsushita Electronic Industrial Co., Ltd. and Sony
Corporation and Toshiba Corporation. Digital Transmission Content Protection System, Volume 1, July 2001.
14. Semiconductor Design Solutions.
RSA2048A RSA coprocessor data sheet.
http://www.sidsa.com/datasheets/RSA/ds rsa2048a short.html.
15. 3GPP Security Algorithms Group of Experts. 3GPP KASUMI evaluation report. Technical
report, 3rd Generation Partnership Project, Oct 2000.
2 The cited RSA design supports up to 2048-bit keys. We imagine the gate count could be cut

substantially without compromising security by using only 768-bit keys.
3 We have not evaluated KASUMI’s ability to achieve the data rates required for uncompressed

video.