Abstract:
A video source device and a video repeater device cooperatively authenticates said video repeater apparatus to said video source device. In one embodiment, the authentication is performed using an identical authentication process a video sink device would authenticate itself to the video source device. The video repeater device augment the identical process identifying itself as a repeater device. The video repeater device also in cooperation with at least one video sink device authenticates the at least one video sink device. The video repeater device in turn, in cooperation with the video source device, authenticates the at least one video sink device to the video source device. In one embodiment, the video repeater device also in cooperation with another video repeater device, authenticates yet another at least one video sink device to the video repeater device. In like manner, the video repeater device, in cooperation with the video source device, authenticates the yet another at least one video sink device to the video source device. In one embodiment, the video repeater device includes topological information of the video sink devices among the authentication information provided to the video source device. Accordingly, video sink devices may be hierarchically organized to the video source device.

Description:
RELATED APPLICATION 
   This application is a continuation-in-part application to U.S. patent applications Ser. Nos. 09/385,590 and 09/385,592, both entitled Digital Video Content Transmission Ciphering and Deciphering Method and Apparatus, filed on Aug. 29, 1999. 

   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to the field of content protection. More specifically, the present invention addresses authentication of hierarchically organized video receiving devices. 
   2. Background Information 
   In general, entertainment, education, art, and so forth (hereinafter collectively referred to as “content”) packaged in digital form offer higher audio and video quality than their analog counterparts. However, content producers, especially those in the entertainment industry, are still reluctant in totally embracing the digital form. The primary reason being digital contents are particularly vulnerable to pirating. As unlike the analog form, where some amount of quality degradation generally occurs with each copying, a pirated copy of digital content is virtually as good as the “gold master”. As a result, much effort have been spent by the industry in developing and adopting techniques to provide protection to the distribution and rendering of digital content. 
   Historically, the communication interface between a video source device (such as a personal computer) and a video sink device (such as a monitor) is an analog interface. Thus, very little focus has been given to providing protection for the transmission between the source and sink devices. With advances in integrated circuit and other related technologies, a new type of digital interface between video source and sink devices is emerging. The availability of this type of new digital interface presents yet another new challenge to protecting digital video content. While in general, there is a large body of cipher technology known, the operating characteristics such as the volume of the data, its streaming nature, the bit rate and so forth, as well as the location of intelligence, typically in the source device and not the sink device, present a unique set of challenges, requiring a new and novel solution. Parent applications Ser. Nos. 09/385,590 and 09/385,592 disclosed various protocol and cipher/deciphering techniques to authenticate a video sink device and protect transmission to the video sink device. 
   As technology advances, it is desired to be able to securely transmit digital video from a video source device to multiple hierarchically organized video sink devices. Thus, a need exist to authenticate devices and protect transmission in such hierarchical environment. 

   
     BRIEF DESCRIPTION OF DRAWINGS 
     The present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which: 
       FIG. 1  illustrates an example hierarchy of video source, repeater and sink devices incorporated with the teachings of the present invention, in accordance with one embodiment; 
       FIG. 2  illustrates an overview of the authentication method of the present invention, in accordance with one embodiment; 
       FIG. 3   a  illustrates the process for authenticating a video repeater device to a video source device, in accordance with one embodiment (which in one embodiment, is also the same process for authenticating a downstream video repeater device to an upstream video repeater device, a video sink device to a video repeater device, as well as a video sink device to a video source device); 
       FIG. 3   b  illustrates the process for a video repeater device authenticating downstream video sink devices to an upstream video repeater device or a video source device; and 
       FIGS. 4   a – 4   c  illustrate a one way function suitable for use to practice the symmetric ciphering/deciphering process employed in one embodiment of the processes illustrated in  FIGS. 3   a – 3   b  in further detail, in accordance with one embodiment. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   In the following description, various aspects of the present invention will be described, and various details will be set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all aspects of the present invention, and the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified in order not to obscure the present invention. 
   Various operations will be described as multiple discrete steps performed in turn in a manner that is most helpful in understanding the present invention. However, the order of description should not be construed as to imply that these operations are necessarily performed in the order they are presented, or even order dependent. Lastly, repeated usage of the phrase “in one embodiment” does not necessarily refer to the same embodiment, although it may. 
   Referring now to  FIG. 1 , wherein a block diagram illustrating an example hierarchy of video source, repeater and sink devices incorporated with the teachings of the present invention for authenticating the downstream video sink devices to the video source device is shown. As illustrated, example hierarchy  100  includes video source device  102 , video sink devices  104   a – 104   d , and video repeater devices  106   a – 106   b , coupled to each other as shown. As will be described in more detail below, each video device  102 ,  104   a – 104   d  or  106   a – 106   b  includes an authentication unit (not shown) correspondingly incorporated with the applicable aspects of the teachings of present invention for authenticating video sink devices  104   a – 104   d  to video source device  102 , to assure video source device  102  that post authentication video transmitted by video source device  102  will not be compromised by the downstream devices, such as making unauthorized copy of the video. 
   Except for the teachings of the present invention correspondingly incorporated therein, video source, repeater and sink devices  102 ,  104   a – 104   d , and  106   a – 106   b  are intended to represent a broad range of digital devices known in the art. For examples, video source  102  may be any one of a number of digital “computing” devices known in the art, including but are not limited to, server computers, desktop computers, laptop computers, set-top boxes, DVD players and the like, and video sink devices  104   a – 104   d  may be, but are not limited to, display devices such as Cathode Ray Tubes (CRT), flat panel displays, television sets, and the like, attached to these digital “computing” devices. Alternatively, one or more video sink devices  104 – 104   d  may be another digital computing device with storage capability or a digital recording device. Video repeater devices  106   a – 106   b  may be, but are not limited to, signal repeater devices. 
   These devices may be coupled to one another using any one of a number of communication links known in the art. Each of inter-device communication links for conducting the authentication process may or may not be the same communication link for transmitting the post-authentication video signals. In one embodiment, the devices are communicatively coupled to each other using serial communication links known in the art. Communications may be conducted with any pre-established protocols, which are of no particular relevance to the present invention. 
   Before proceeding to describing the authentication process of the present invention, it should be noted that while for ease of understanding, example hierarchy  100  includes only two repeater devices and four sink devices hierarchically organized into four hierarchy levels, video source device  102 , video sink device  104   a  and video repeater device  106   a , video sink devices  104   b – 104   c  and video repeater device  106   b , and video sink device  104   d , from the description to follow, it will be readily apparent to those skilled in the art, that the present invention may be practiced with any number of video repeater and sink devices hierarchically organized in two or more hierarchy levels. Any number of video repeater and sink devices may be present at each level. Further, a video repeater device may also be a video sink device. Nevertheless, for ease of understanding, the remaining description will treat repeater and sink devices as separate devices. 
     FIG. 2  illustrates an overview of the authentication process of the present invention, in accordance with one embodiment. As shown, upon start up, such as power on or reset, at  202 , a downstream video repeater/sink device will first authenticate itself to the immediately upstream video source/repeater device. For example, in the case of example hierarchy  100  of  FIG. 1 , video sink device  104   a  and video repeater device  106   a  will authenticate itself to video source device  102 , video repeater device  106   b  and video sink devices  104   b – 104   c  will authenticate itself to video repeater device  106   a , and video sink device  104   d  will authenticate itself to video repeater device  106   b.    
   For the illustrated embodiment, these authentications are all advantageously conducted with the same authentication process. That is, the operations performed by a pair of video source and sink devices, a pair of video source and repeater devices, a pair of video repeater devices, and a pair of video repeater and sink devices to authenticate the repeater/sink device to the source/repeater device, as the case may be, are basically the same operations. To differentiate an authenticating video repeater device, such as  106   a  or  106   b , from a video sink device, such as  104   a ,  104   b , or  104   c , a video repeater device, such as  106   a  or  106   b , will identify itself to the immediately upstream device, such as device  102   a  or  106   a , that the device is a repeater device, and a video sink device, such a  104   a – 104   d  would not make such identification, thereby facilitating the participate devices to know whether the remaining authentication process, to authenticate the downstream video sink devices need to be performed or not. 
   At  204 , an upstream device, such as source device  102  or repeater device  106   a , will await the downstream device who has identified itself as a repeater device, such as device  106   a  and  106   b , to provide the authentication information of all their downstream video sink devices, in the case of repeater device  106   a , sink devices  104   b – 104   c , and the case of repeater device  106   b , sink devices  104   c . When ready, that is having aggregated all authentication information of the downstream sink devices, repeater device  106   a / 106   b  would perform the remaining operations authenticating all downstream video sink devices to its immediately upstream device. As examples, in the case of example hierarchy  100  of  FIG. 1 , upon authenticating video sink device  104   d , video repeater device  106   b  would authenticate video sink device  104   d  to immediately upstream video repeater device  106   a , and for video repeater device  106   a , upon first authenticating video repeater device  106   b  and video sink devices  104   b – 104   c , and then authenticating video sink device  104   d , video repeater device  106   a  would authenticate video sink devices  104   b – 104   d  to video source device  102 . In each case, i.e. video repeater device  106   b  authenticating video sink device  104   d  to video repeater device  106   a , and video repeater device  106   a  authenticating video sink devices  104   b – 104   d  to video source device  102 , video repeater device  106   a / 106   b  also provides the topology information of the sink devices to video repeater/source device  106   a / 102 . In other words, video repeater device  106   b  will inform video repeater device  106   a  that video sink device  104   d  is immediately downstream from it, whereas video repeater device  106   a  will inform video source device  102  that video sink devices  104   b – 104   c  are immediately downstream from it, and video sink device  104   d  is downstream from it via video repeater device  106   b.    
   Accordingly, it can be seen, except for practical or commercial reasons, the present invention has no structural limit to the number video sink devices that can be attached to a video repeater device at each hierarchy level, nor is there any structural limit on to the number of hierarchy levels. 
   In one embodiment, the identical authentication process employed by the devices to authenticate itself to the immediately upstream device, as well as the authentication process employed by a repeater device to authenticate all downstream video sink devices to an immediately upstream video source/repeater device is a cooperative process that involves a symmetric ciphering/deciphering process independently performed by the authentication parties. 
     FIGS. 3   a – 3   b  illustrate two overviews of the symmetric ciphering/deciphering process based method for authenticating a downstream device to an immediately upstream device, and for a repeater device to authenticate all its downstream sink devices to its immediately upstream device, in accordance with one embodiment. For the illustrated embodiment, all devices correspondingly incorporated with the applicable portions of the teachings of the present invention, video source device  102 , sink devices  104   a – 104   b  and repeater devices  106   a – 106   d , are assumed to be equipped with an array of “cryptographic” device keys (Akey or Bkey) by a certification authority (hereinafter, simply device keys). In one embodiment, the assignment of these “cryptographic” device keys are performed in accordance with the teachings of the co-pending U.S. patent application Ser. No. 09/275,722, filed on Mar. 24, 1999, entitled Method and Apparatus for the Generation of Cryptographic Keys, having common assignee with the present application. 
   As illustrated in  FIG. 3   a , the authentication unit of an immediately upstream device, e.g. video source device  102 , video repeater device  106   a  or video repeater device  106   b , kicks off the authentication process with each immediately downstream device by generating a basis value (A n ) to the symmetric ciphering/deciphering process, and providing the basis value along with a device key selection vector (A n , Ak sv ) to the immediate downstream device, e.g. video sink device  104   a /video repeater devices  106   a , video repeater device  106   b /video sink devices  104   b – 104   c , and video sink device  104   c . [Further details on the assignment of device key selection vectors to devices may also be found in the aforementioned application Ser. No. 09/275,722.] For the example hierarchy  100  of  FIG. 1 , video source device  102  will kick off two authentication processes, one with video sink device  104   a  and another one with video repeater device  106   a , video repeater device  106   a  will kick off three authentication processes, one with video repeater device  106   b  and two others, on each, with video sink device  106   b , and video repeater device  106   b  will kick off an authentication process with video sink device  104   d . For the illustrated embodiment, basis value A n  is a pseudo random number. A n  may be generated in any one of a number of techniques known in the art. 
   In response, for each of the authentication processes, the authentication unit of the immediately downstream device, e.g. video sink device  104   a /video repeater device  106   a , video repeat device  106   b /video sink devices  104   b / 104   c , and video sink device  104   d  responds by providing its device key selection vector (Bk sv ) and an indicator (Repeater) indicating whether the downstream device is a repeater device or not. In one embodiment, the Repeater indicator is a 1-bit indicator set to “1” if the downstream device is a repeater device, and set to “0” if the downstream device is not a repeater device. 
   Thereafter, for each of the authentication processes, each of the authentication units, of the upstream and downstream devices, will independently generate a verification value R 0  and R 0 ′, using the basis value A n , their deviec keys, and the exchanged device key selection vectors AK sv  and BK sv  and the Repeater indicator. The authentication unit of the downstream device will provide its independently generated verification value R 0 ′ to the upstream device, and the authentication unit of the upstream device in turn compares the two verification values, and depending on whether the two verification values successfully compares, uses the provided Bk sv  to determine if the downstream device is an authorized device or a device to be trusted. The upstream device accepts Bk sv  and uses it to compare against an authorization list to determine whether the downstream device is an authorized or trustworthy device if R 0  equals R 0 ′, otherwise, if R 0  not equals R 0 ′, the downstream device is deemed to be an unauthorized or untrustworthy device. In one embodiment, subsequent video transmissions, if any, would not be passed by the upstream device to the immediately downstream device that failed the authentication process. 
   For the illustrated embodiment, the authentication unit of the upstream/downstream device independently generates the verification value R 0 /R 0 ′ by first generating an authentication key K m /K m ′. As illustrated, authentication key K m /K m ′ is generated by summing device key Akey/Bkey over device key selection vector BK sv /AK sv  (see application Ser. No. 09/275,722 for detail). Next, the authentication unit of the upstream/downstream device independently generates the verification value R 0 /R 0 ′ using K m /K m ′, Repeater indicator, and A n ). In one embodiment, the authentication unit generates R 0 /R 0 ′ employing a “one way function” with K m /K m ′ and Repeater indicator concatenated with A n . 
   For the illustrated embodiment, each authentication unit also generates, as part of the process for generating R 0 /R 0 ′, a shared secret M 0 /M 0 ′ and a session key K s /K s ′. Shared secret M 0 /M 0 ′ is used in the subsequent authentication of the video sink devices downstream to a video repeater device, as well as the protection of the video transmitted posted authentication. Session key K s /K s ′ is used in the protection of the video transmitted posted authentication. Employment of M 0 /M 0 ′ and K s /K s ′ to protect the video transmitted post authentication is the subject matters of the parent applications. See the respective applications for details. 
   At this point, the authentication process is completed between a video source device and a video sink device, and between a video repeater device and a video sink device. For video source device and video repeater device, and for video repeater device and video repeater device, the process continues as illustrated in  FIG. 3   b  for the immediately downstream video repeater device to authenticate to the immediately upstream video source/repeater device all downstream video sink devices. 
   As illustrated, for each upstream device, where the immediately downstream device has identified itself as a repeater device, it awaits for a “Ready” signal from the immediately downstream repeater device, denoting the downstream repeater device has reliably obtained the device key selection vectors of the downstream video sink devices and the downstream repeater device is ready to provide the list of device key selection vectors to the upstream device for authentication. This operation advantageously allows the device key selection vectors of the downstream video sink devices to be successively “percolated” upward through the downstream repeater devices. 
   Upon having reliably received all the device key selection vectors of the downstream video sink devices (Bk sv  list), the downstream repeater device provides the reliably accumulated Bk sv  list to its immediate upstream repeater/source device. For examples, for example hierarchy  100  of  FIG. 1 , video repeater device  106   b , upon reliably obtaining Bk sv  of video sink device  104   d , provides the particular Bk sv  to video repeater device  106   a . For video repeater device  106   a , upon authenticating Bk sv  of video sink devices  104   b – 104   c  and upon reliably provided Bk sv  of video sink device  104   d  by video repeater device  106   b , it provides Bk sv  of all downstream video sink devices,  104   d  as well as  104   b  and  104   c  to video source device  102 . 
   For the illustrated embodiment, each of the downstream repeater device provides the Bk sv  list along with a verification signature (V′) and the topology information of the downstream video sink devices. For example, the topological information provided by video repeater device  106   a  to video source device  102  denotes to video source device  102  of the fact that video sink device  104   d  is actually downstream to video repeater device  106   a  through video repeater device  106   b , however, video sink devices  104   b – 104   c  are immediately downstream to video repeater device  106   a.    
   For the illustrated embodiment, each authentication unit of an immediately downstream video repeater device generates the verification signature V′ using a predetermined hash function hashing the Bk sv  list, the topology “vector”, and the earlier described shared secret M 0 ′. In one embodiment, the Bk sv  list, the topology “vector”, and the earlier described shared secret M 0 ′ are concatenated together. The predetermined hash function may be any “secure” hashing function known in the art. 
   Upon receiving the Bk sv  list, the verification signature, and the topology “vector”, in like manner, the immediately upstream source/repeater device independently generates its own verification value V. In one embodiment, the immediately upstream source/repeater device independently generates its own verification value V, using the same hash function, the provided Bk sv  list, the topology “vector”, and its own independently generated shared secret M 0 . Upon generating its own verification value V, the immediately upstream source/repeater device compares the two verification values V and V′ to determine whether to accept the provided Bk sv  list. In one embodiment, the immediately upstream source/repeater device accepts the provided Bk sv  list (when V=V′) and compares the list against an authentication list to determine whether the video sink devices are authorized or trustworthy devices, and rejects the provided Bk sv  list if V does not equal V′. If the Bk sv  list is rejected, the video sink devices are deemed to be unauthorized or untrustworthy sink devices. When that occurs, future video will not be provided to the immediately downstream video repeater device, thereby protecting the video from being sent to the unauthorized or untrustworthy video sink devices. 
     FIGS. 4   a – 4   c  illustrate a one-way function suitable for use to practice the symmetric ciphering/deciphering process of  FIGS. 3   a – 3   b , in accordance with one embodiment. As alluded to earlier, in one embodiment, this one-way function is a part of the authentication unit of each of the video source/repeater/sink devices. As illustrated in  FIG. 4   a , the one way function  800  includes a number of linear feedback shift registers (LFSRs)  802  and combiner function  804 , coupled to each other as shown. LFSRs  802  and combiner function  804  are collectively initialized with the appropriate keys and data values. During operation, the values are successively shifted through LFSRs  802 . Selective outputs are taken from LFSRs  802 , and combiner function  804  is used to combine the selective outputs to generate the desired outputs. 
   In one embodiment, four LFSRs of different lengths are employed. Three sets of outputs are taken from the four LFSRs. The polynomials represented by the LFSR and the bit positions of the three sets of LFSR outputs are given by the table to follow: 
   
     
       
             
             
           
             
             
             
             
             
           
         
             
                 
                 
             
             
                 
               Combining Function Taps 
             
           
        
         
             
               LFSR 
               Polynomial 
               0 
               1 
               2 
             
             
                 
             
             
               3 
               X 17  + x 15  + x 11  + x 5  + 1 
               5 
               11  
               16 
             
             
               2 
               X 16  + x 15  + x 12  + x 8  + x 7  + x 5  + 1 
               5 
               9 
               15 
             
             
               1 
               X 14  + x 11  + x 10  + x 7  + x 6  + x 4  + 1 
               4 
               8 
               13 
             
             
               0 
               X 13  + x 11  + x 9  + x 5  + 1 
               3 
               7 
               12 
             
             
                 
             
           
        
       
     
   
   The initialization of the LFSRs and the combiner function, more spefically, the shuffling network of the combiner function, is in accordance with the following table. 
   
     
       
             
             
             
           
             
             
             
             
           
         
             
                 
                 
             
             
                 
               Bit Field 
               Initial Value 
             
             
                 
                 
             
           
           
             
                 
             
           
        
         
             
                 
               LFSR3 
               [16] 
               Complement of input bit 47 
             
             
                 
                 
               [15:0] 
               Input bits[55:40] 
             
             
                 
               LFSR2 
               [15] 
               Complement of input bit 32 
             
             
                 
                 
               [14:0] 
               Input bits[39:25] 
             
             
                 
               LFSR1 
               [13] 
               Complement of input bit 18 
             
             
                 
                 
               [12:0] 
               Input bits [24:12] 
             
             
                 
               LFSR0 
               [12] 
               Complement of input bit 6 
             
             
                 
                 
               [11:0] 
               Input bits[11:0] 
             
             
                 
               Shuffle 
               Register A 
               0 
             
             
                 
               Network 
               Register B 
               1 
             
             
                 
                 
             
           
        
       
     
   
   The combined result is generated from the third set of LFSR outputs, using the first and second set of LFSR outputs as data and control inputs respectively to combiner function  804 . The third set of LFSR outputs are combined into a single bit. 
     FIG. 4   b  illustrates combiner function  804  in further detail, in accordance with one embodiment. As illustrated, combiner function  804  includes shuffle network  806  and XOR  808   a – 808   b , serially coupled to each other and LFSRs  802  as shown. For the illustrated embodiment, shuffle network  806  includes four binary shuffle units  810   a – 810   d  serially coupled to each other, with first and last binary shuffle units  810   a  and  810   d  coupled to XOR  808   a  and  808   b  respectively. XOR  808   a  takes the first group of LFSR outputs and combined them as a single bit input for shuffle network  806 . Binary shuffle units  810   a – 810   d  serially propagate and shuffle the output of XOR  808   a . The second group of LFSR outputs are used to control the shuffling at corresponding ones of binary shuffle units  810   a – 810   d . XOR  808   b  combines the third set of LFSR outputs with the output of last binary shuffle unit  810   d.    
     FIG. 4   c  illustrates one binary shuffle unit  810 * (where * is one of a–d) in further detail, in accordance with one embodiment. Each binary shuffle unit  810 * includes two flip-flops  812   a  and  812   b , and a number of selectors  814   a – 814   c , coupled to each other as shown. Flip-flops  812   a  and  812   b  are used to store two state values (A, B). Each selector  814   a ,  814   b  or  814   c  receives a corresponding one of the second group of LFSR outputs as its control signal. Selector  814   a – 814   b  also each receives the output of XOR  808   a  or an immediately preceding binary shuffle unit  810 * as input. Selector  814   a – 814   b  are coupled to flip-flops  812   a – 812   b  to output one of the two stored state values and to shuffle as well as modify the stored values in accordance with the state of the select signal. More specifically, for the illustrated embodiment, if the stored state values are (A, B), and the input and select values are (D, S), binary shuffle unit  810 * outputs A, and stores (B, D) if the value of S is “0”. Binary shuffle unit  810 * outputs B, and stores (D, A) if the value of S is “1”. 
   Accordingly, a novel method and apparatus for authenticating hierarchically organized video repeater and sink devices has been described. 
   EPILOGUE 
   From the foregoing description, those skilled in the art will recognize that many other variations of the present invention are possible. Thus, the present invention is not limited by the details described, instead, the present invention can be practiced with modifications and alterations within the spirit and scope of the appended claims.