Key selection vector

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Key Selection Vector means the numeric value 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.

Role of KSV in Restricted Authentication[edit]

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.

KSVs are unique to each device[edit]

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.

Apparent KSV weaknesses[edit]

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 number of KSVs 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)KSVs for which we have found the private keys. There will be, however, no guarantee of them satisfying the 20 one and 20 zero bits property.

How could this be broken?[edit]

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.

What do we know?[edit]

If we assume that we have 40 (A_i)KSVs 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 KSVs, 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)KSVs doesn't span the full 40 dimensional space, we're probably OK. Either, the KSVs 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 KSVs 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)keys 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.

See also[edit]

External links[edit]