Key selection vector

From Wikipedia, the free encyclopedia

The Key Selection Vector means the numerical associated with a Device Key Set and distributed by Licensor or its designee to Adopters and used to support authentication of Licensed Products and Revocation. It is considered a confidential set of keys used in Restricted Authentication process of the HDCP. Restricted authentication is an AKE method for devices with limited computing resources. This method is used by copying devices of any kind (such as DV recorders or D-VHS recorders) and devices communicating with them for authenticating copy-one-generation and no-more-copies contents. The restricted authentication protocol employs asymmetric key management and common key cryptography and relies on the use of shared secrets and hash functions to respond to a random challenge.

1 Role of KSV in Restricted Authentication
2 KSVs are unique to each device
3 Apparent KSV weaknesses
4 How could this be broken?
5 What do we know?
6 See also
7 External links

[edit] Role of KSV in Restricted Authentication

This method is based on a device being able to prove that it holds a secret shared with other devices. One device authenticates another by issuing a random challenge that is responded to by modifying it with the shared secrets and multiple hashings.

During the authentication process, both parties exchange their KSVs. Then each device adds (without overflow) its own secret keys according to a KSV received from another device. If a particular bit in the vector is set to 1, then the corresponding secret key is used in the addition, otherwise it is ignored. For each set of keys a special key called a KSV (Key Selection Vector) is created. Each KSV has exactly 20 bits set to 0 and 20 bits set to 1. Keys and KSVs are generated in such a way that during this process both devices get the same 56 bit number as a result. That number is later used in the encryption process. The following figure gives an overview of restricted authentication:

Numerical description: 1. The host initiates the first phase of authentication by sending the display its KSV and a 64-bit random number. 2. The display responds by sending its own KSV and a Repeater bit. This bit tells the host whether the downstream device is a repeater or a standalone display. 3. If the display's KSV is listed in the host's SRM, or if it doesn't contain exactly 20 bits set to zero and 20 bits set to one, the display is assumed to be unauthorized and transmission is terminated. 4. If the display's KSV is valid, the host and display each use their own Device Keys and the other device's KSV to generate the Content Key. These calculations are designed to run efficiently in hardware, requiring only straightforward 56-bit binary (modulo 256) addition. Each device simply adds together those of its Device Keys that correspond to the twenty bits set to 1 in the other device's KSV. 5. If both sets of Device Keys and KSVs are valid, the two Content Keys will be identical, and can be used as symmetric keys to encrypt and decrypt the video stream. To further ensure the integrity of the system, the actual Content Keys are never passed through the connection.

[edit] KSVs are unique to each device

Even valid keys can become compromised (hacked), so HDCP includes a mechanism to revoke keys. The KSV values are unique to each key set and, therefore, to each device. The system can then compare these values to a revocation list, and if either the transmitter or receiver appears on that list, authentication fails. Updates to the revocation list arrive with new media and are automatically integrated. So if a key set somehow does get exposed or copied, the damage can be limited.

This revocation process does not affect other devices, even if the devices are of the same make and model. In that sense, KSV values are like serial numbers.

Exemplification:

Suppose that Sally and Bob buy the same kind of TV on the same day at the same store. Bob somehow hacks his set, gets caught, and has his KSV value revoked. Sally needn't worry. Her TV has a different KSV value and won't be affected in any way.

[edit] Apparent KSV weaknesses

If we can find 40 linearly independent sets of vectors ( $A 1$ ) keys ... ( $A 40$ )keys, say, through reverse-engineering hardware, then we can completely break the system. At that point, one can extract the secret key array for any Xksv that he wishes.

In other cases where the separate keys are not linearly independent, it is still possible to create Xkeys for any Xksv that is within the span of the ( $A i$ )ksv's for which we have found the private keys. There will be, however, no guarentee of them satisfying the 20 one and 20 zero bits property.

[edit] How could this be broken?

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. Therefore, this means it exists a 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$ .... $A n$ , and knew the Xksv from system X (this is public information from the protocol), then he could determine the Xkeys private key array.

[edit] What do we know?

If we assume that we have 40 ( $A i$ )ksv's that are linearly independent, we’ll have a set of n linear equations on 40 unknown –

The Xkeys key vector array:

[Xkeys] * (A1)ksv = = [(A1)keys] * Xksv[Xkeys] * (A2)ksv = = [(A2)keys] * Xksv...[Xkeys] * (A40)ksv = = [(A40)keys] * Xksv

By having acknowledgment on all the ksv's, and assuming we know the secret key vectors ( $A i$ )keys, we can repeat the above algorithm to generate a new Bkeys for any other device with an arbitrary Bksv. Last step will be to substitute Xksv = Bksv. 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.

Through a linear combination of any known ksv (with 20 one bits and 20 zero bits) and (A_i)key's we can construct a valid Xksv and Xkeys already know. The only trick is finding a Xksv in the subspace that has the required number of 0 & 1 bits. This is the only potentially difficult part, though given a concrete example, it would not be difficult to solve.