Key selection vector
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.
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.
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 number
s.
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.
sets of vectors (
) keys ... (
)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 KSV's 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 (
)KSV's 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.
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:
.... 
, and knew the Xksv from system X (this is public information from the protocol), then he could determine the Xkeys private key array.
)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 (
)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 (
)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 (
)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 bit
s. This is the only potentially difficult part, though given a concrete example, it would not be difficult to solve.
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
used in Restricted Authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
process of the HDCP. Restricted authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
is an AKE
Ake
Ake is an archaeological site of the pre-Columbian Maya civilization, located in the municipality of Tixkokob. in the Mexican state of Yucatán; 40 km east of Mérida, Yucatán....
method for devices with limited computing resources.
This method is used by copying devices of any kind (such as DV
DV
DV is a format for the digital recording and playing back of digital video. The DV codec was launched in 1995 with joint efforts of leading producers of video camcorders....
recorders or D-VHS
D-VHS
D-VHS is a digital recording format developed by JVC, in collaboration with Hitachi, Matsushita, and Philips. The "D" in D-VHS originally stood for Data VHS, but with the expansion of the format from standard definition to high definition capability, JVC renamed it Digital VHS and uses that...
recorders) and devices
Information appliance
In general terms, an information appliance or information device is any machine or device that is usable for the purposes of computing, telecommunicating, reproducing, and presenting encoded information in myriad forms and applications....
communicating with them for authenticating copy-one-generation and no-more-copies contents. The restricted authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
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
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 challengeChallenge-response authentication
In computer security, challenge-response authentication is a family of protocols in which one party presents a question and another party must provide a valid answer to be authenticated....
that is responded to by modifying it with the shared secrets and multiple hashings.
During the authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
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
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
process.
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
Revocation
Revocation is the act of recall or annulment. It is the reversal of an act, the recalling of a grant, or the making void of some deed previously existing.-Contract law:...
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 number
Serial number
A serial number is a unique number assigned for identification which varies from its successor or predecessor by a fixed discrete integer value...
s.
Exemplification:
Suppose that Sally and Bob buy the same kind of TV
Television
Television is a telecommunication medium for transmitting and receiving moving images that can be monochrome or colored, with accompanying sound...
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
If we can find 40 linearly independentLinear independence
In linear algebra, a family of vectors is linearly independent if none of them can be written as a linear combination of finitely many other vectors in the collection. A family of vectors which is not linearly independent is called linearly dependent...
sets of vectors (
) keys ... ()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 KSV's 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 (
)KSV's 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?
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
System
System is a set of interacting or interdependent components forming an integrated whole....
, it appears that if someone could determine the Akeys vector from any 40-50 different systems:
.... , 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?
If we assume that we have 40 ()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
Acknowledgement (data networks)
In data networking, an acknowledgment is a signal passed between communicating processes or computers to signify acknowledgment, or receipt of response, as part of a communications protocol...
on all the ksv's, and assuming we know the secret key vectors (
)keys, we can repeat the above algorithm to generate a new Bkeys for any other device with an arbitraryArbitrary
Arbitrariness is a term given to choices and actions subject to individual will, judgment or preference, based solely upon an individual's opinion or discretion.Arbitrary decisions are not necessarily the same as random decisions...
Bksv. Last step will be to substitute Xksv = Bksv. If the space spanned by the (
)ksv's doesn't span the full 40 dimensional space, we're probably OK. Either, the ksv's were designed to not span the spaceSpace
Space is the boundless, three-dimensional extent in which objects and events occur and have relative position and direction. Physical space is often conceived in three linear dimensions, although modern physicists usually consider it, with time, to be part of a boundless four-dimensional continuum...
, or we need to get the (
)keys from a few more devices to round out the space.Each additional device has low odds of being linearly dependent
Linear independence
In linear algebra, a family of vectors is linearly independent if none of them can be written as a linear combination of finitely many other vectors in the collection. A family of vectors which is not linearly independent is called 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
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
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 bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s. This is the only potentially difficult part, though given a concrete example, it would not be difficult to solve.