 |
Claims  |
|
|
What is claimed is:
1. Apparatus for receiving an executable application transmitted in modules
including a Directory Module containing information about further modules,
said Directory Module having at least an encrypted hash value over the
Directory Module and an encrypted certificate appended, which certificate
includes an identity of the application provider, said apparatus
comprising:
a memory
a detector for detecting said transmitted modules and storing detected
modules in memory;
means for separating said certificate from a detected Directory Module;
a decryptor for decrypting said certificate and said encrypted hash value;
a hash function element for hashing said detected Directory Modules to
produce a further hash value;
a processor programmed for authenticating decrypted said certificate, and
comparing decrypted said hash value with said further hash value, and if
decrypted said hash value and said further hash value are equal and said
certificate is authentic, permitting execution of said program.
2. The apparatus set forth in claim 1 wherein said Directory Module further
includes hash values of further program modules, and said apparatus
further includes:
means for accessing said hash values of further program modules from said
detected Directory Module;
means for applying respective said further program modules to said hash
function element for generating hash values over said further program
modules; and wherein
said processor is conditioned to compare said hash values of further
program modules accessed from said Directory Module with corresponding
hash values produced by said hash function element, and permitting
execution of said program if at least predetermined ones of corresponding
hash values are equal.
3. The apparatus set forth in claim 1 wherein said transmitted Directory
Module is encrypted, and said decryptor is conditioned to decrypt said
Directory Module with said application provider's public key.
4. The apparatus set forth in claim 2 wherein said processor includes means
to delete from said memory, modules for which corresponding hash values
are not identical.
5. The apparatus set forth in claim 1 wherein said decryptor and said hash
function element are subsumed in said processor.
6. The apparatus set forth in claim 1 wherein said detector includes
forward error correcting circuitry.
7. The apparatus set forth in claim 1 wherein said transmitted executable
application is transmitted in transport packets, each of which includes a
service channel identifier, SCID, and scrambling flags, and said detector
includes:
a programmable SCID detector for selecting transport packets having
predetermined SCID's from a multiplexed stream of transport packets; and
said apparatus further includes
a descrambler responsive to said scrambling flags, for descrambling
respective packets according to respective states of said scrambling
flags.
8. The apparatus set forth in claim 1 further including means for causing a
display to indicate detection of signal provided by an unauthorized
application provider.
9. The apparatus set forth in claim 1 further including:
a source of a digital version of predetermined text;
apparatus for preceding at least one of said modules, including the
Directory Module, with said digital version of predetermined text, and
wherein
said hash function element is conditioned to hash at least one of said
modules preceded with said digital version of predetermined text.
10. The apparatus set forth in claim 9 wherein said predetermined text is
OPENTV(.TM.).
11. The apparatus set forth in claim 1 wherein said Directory Module
includes a signature S calculated using a RSA algorithm with modulus N and
exponent e, and includes quotients Q1, Q2 derived from the signature S by
division by the modulus N, and said processor is conditioned to verify
said signature S using the quotients Q1 and Q2 without performing
arithmetic division.
12. A method of processing executable applications which are transmitted as
modules, in multiplexed packet format, said modules including a Directory
Module containing information linking respective further application
modules, said Directory Module having an encrypted certificate attached
which contains information about the provider of the application, and
which certificate is encrypted by a system provider's private key, said
method comprising;
detecting and selecting packets including a desired application, and
storing payloads of respective packets as respective modules;
selecting a Directory Module with encrypted certificate attached;
decrypting the certificate with the system provider's public key;
Comparing information in decrypted said certificate with corresponding
stored data;
hashing ones of said application modules to produce module hash values;
comparing said module hash values with corresponding module hash values
transmitted in said Directory Module; and
executing an application if corresponding produced and transmitted hash
values are identical and decrypted information contained in said
certificate is equivalent to said corresponding stored data.
13. The method set forth in claim 12 wherein said certificate includes an
application providers public key and said Directory Module has a hash
value of said Directory Module attached, which hash value is encrypted
with said application provider's private key, and said method further
includes the steps of:
extracting said application provider's public key from decrypted said
certificate and separating encrypted said hash value from said Directory
Module;
decrypting encrypted said hash value using said application provider's
public key; and
comparing decrypted said encrypted hash value with a hash value of detected
said Directory Module.
14. The method set forth in claim 12 further including appending a digital
form of the text OpenTv(.TM.) to said Directory Module prior to hashing
said Directory Module, and hashing said Directory Module with said digital
form of the text OpenTv(.TM.) appended.
15. Apparatus for transmitting executable applications comprising;
a processor for generating an executable application, and forming said
application into modules containing portions of said application and a
Directory Module containing information linking modules in an application;
a hash function element for performing one-way hash functions on modules of
said application to produce corresponding hash values, and cooperating
with said processor for inserting said hash values in said Directory
Module;
a source of an application provider's public key and a certificate signed
with a private key of a system controller and including, an application
provider's identifier, and a time stamp related to one of the time of
generation and the time of expiration of the certificate;
means for attaching said application provider's public key and said
certificate to said Directory Module; and
a transport processor for forming a time division multiplexed signal with
said modules of said application.
16. The apparatus set forth in claim 15 further including:
encryption apparatus for encrypting a hash value of said Directory Module
containing hash values of said application modules, with a private key of
said application provider; and
means for attaching encrypted said hash value of said Directory Module to
said Directory Module.
17. The apparatus set forth in claim 15 wherein ones of said modules are
Data Modules in which data is expected to change during execution of said
application, and said processor applies version numbers to respective
modules, and changes the version number of a module when such module
changes;
said hash function element hashes each changed version of a module to
produce a new hash value and cooperates with said processor to attach said
new hash value to the module to which it corresponds.
18. The apparatus set forth in claim 15 further including:
a source of a digital version of predetermined text;
a multiplexer for multiplexing said digital version of predetermined text
with said Directory Module, wherein said hash function element is
conditioned to hash the combination of said digital version of
predetermined text and the Directory Module.
19. A method of transmitting executable applications comprising:
generating an executable application and segmenting it into modules;
forming a Directory Module including information linking respective
application modules;
hashing respective-modules with a one way hash function to generate hash
values for respective modules;
including hash values for respective modules in said Directory Module;
accessing a certificate including an application provider's identity which
certificate is encrypted with a system controller's private key; and
attaching the certificate to said Directory Module, and transmitting said
application.
20. The method set forth in claim 19 further including:
hashing the directory Module with hash values included therein, to generate
a Directory Module hash value;
encrypting the Directory Module hash value;
attaching encrypted said Directory Module hash value to said Directory
Module.
21. The method set forth in claim 19 further including:
generating a further certificate including identification of a third party
provider;
encrypting the further certificate with the application provider's private
key; and
attaching encrypted said further certificate to said Directory Module.
22. The method set forth in claim 20 further including:
encrypting said Directory Module with an application provider's private
key, and transmitting said encrypted Directory Module; and
transmitting remaining application modules in plain text.
23. The method set forth in claim 19 wherein the step of including hash
values in said Directory Module includes respective hash values of 128 bit
length; and
the step of attaching the certificate to said Directory Module includes
attaching a Certificate including:
a 32 bit certificate descriptor or flags,
a 32 bit ID,
a 32 bit lifetime expiration descriptor,
a 32 bit file storage limit,
a 128 bit name, and
a 32 bit public key. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
This invention relates to a method and apparatus for insuring that data
accepted by an interactive television system is authorized data.
BACKGROUND OF THE INVENTION
Interactive television (TV) systems are known from for example U.S. Pat.
No. 5,233,654. Interactive television systems typically involve the
transmission of programming and/or control data (hereafter PC-data), as
well as audio and video information, to respective receiving apparatus.
The receiving apparatus decodes the PC-data, and applies it to some type
of control apparatus for automatic use by the receiver or selective use by
the user of the receiver. The control apparatus may take the form of a
computer, for example, and the use may include downloading selective e.g.,
financial data for subsequent user manipulation.
As envisioned herein, information in the interactive television system
(ITVS) is transmitted in compressed digital form. The receiving end of the
system includes an integrated receiver decoder (IRD) for receiving and
decompressing the transmitted information and providing decoded audio,
video and PC-data to respective processors. The audio and video processors
may be audio and video reproduction devices or a television receiver and
the PC-data processor may be a computer. Ideally the system will only
provide well tested PC-data provided by authorized service providers, and
under such conditions there is little likelihood of transmitted
information actually damaging respective receivers. However, if a large
number of service providers are authorized to use the system, it becomes
vulnerable to a) invasion by unauthorized users and intentional infliction
of damage to system users, and b) careless preparation of PC-data and
consequent unintentional damage to system users. The ability to broadcast
PC-data to tens of thousands of IRD's simultaneously, multiplies the
potential disruption that may be inflicted by ill behaved software many
fold. Thus there is a need for measures to assure protection of respective
ITVS receivers from both ill behaved and unauthorized PC-data.
SUMMARY OF THE INVENTION
A receiver embodiment of the invention includes an IRD which is responsive
to a transmitted program guide for selecting signal packets of PC-data.
The IRD temporarily stores the selected PC-data. Authorized PC-data will
include a certificate. A PC-data processor is configured to separate the
certificate and to check it for authenticity. The processor hashes
portions of the PC-data and compares the generated hash values with hash
values transmitted with the PC-data and corresponding to the same portions
of PC-data. If the hash values are identical and the certificate is
authentic, the system is conditioned to execute the transmitted program.
A transmitter embodiment includes software generating apparatus for
providing an interactive program. The program is divided into modules and
a Directory Module is generated. Respective modules are hashed and the
generated module hash values are included in the Directory Module. The
modules are then conditioned for transmission.
The invention will be described with the aid of the following drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of an interactive TV signal encoding system
embodying an aspect of the present invention;
FIG. 2 is a pictorial diagram of a portion of an exemplary AVI signal
FIG. 3 is a pictorial diagram of an exemplary transport packet
FIG. 4 is a pictorial diagram of the format of an exemplary AVI
application, useful in describing the invention.
FIG. 5 is a table of the contents of an exemplary transmission unit header.
FIG. 6 is a table of the contents of an exemplary Directory Module of a AVI
application embodying the invention.
FIG. 7 is a flow diagram illustrative of the process of applying
security/protection to an AVI application embodying the invention.
FIG. 8 is a block diagram of exemplary receiver apparatus embodying the
invention.
FIG. 9 is an expanded block diagram of an exemplary processor which may be
implemented for the processor of the FIG. 8 apparatus.
FIG. 10 is a flow chart showing operation of a portion of the receiver
apparatus of FIG. 8, and which describes a receiver embodiment of the
invention.
FIG. 11 is a flow chart of an exemplary process for authenticating a
certificate and is an embodiment of the invention
FIG. 12 is a pictorial representation of a preferred Directory Module
format according to the invention.
DETAILED DESCRIPTION
The invention will be described in the environment of a compressed digital
transmission system, as for example a direct broadcast satellite system.
It is presumed that a single satellite transponder will accommodate a
plurality of respective TV programs in time division multiplexed format.
Referring to FIG. 1, a packet multiplexer 16 provides, at its output port,
an audio-video-interactive (AVI) program. Similar such devices 26 generate
alternative AVI programs. A program guide, which includes information
associating the audio, video and interactive components of respective AVI
programs via service channel identifiers (SCID's), is provided in a
transmission format similar to the AVI programs by a processing element
27. The program guide and respective AVI programs are applied in transport
packet form to respective input ports of a channel multiplexer 28. The
channel multiplexer 28 may be of known construction for equally time
division multiplexing respective packet signals into a single signal
stream or it may be a statistically controlled multiplexer. The output of
the multiplexer 28 is coupled to a forward error coding (FEC) and signal
interleaving apparatus 31, which may include Reed-Solomon and Trellis
encoders. The output of the FEC 31 is coupled to a modem wherein the
multiplexed signal is conditioned for application to, for example a
satellite transponder. An exemplary statistically multiplexed packet
signal is illustrated in FIG. 2, and an exemplary format for respective
packets is illustrated in FIG. 3.
AVI formation is controlled by a system program controller 5. Program
controller 5 may have a user interface by which particular programs and
respective program signal components are selected. The program controller
assigns respective SCID's for respective audio, video and interactive
components of respective programs. The presumption is made that respective
receivers will access a program guide to determine which SCID's associate
AVI program components, and then select transport packets from the
transmitted signal stream containing the associated SCID's. The audio,
video and interactive components are assigned different SCID's so that one
or more of the components of one AVI program may conveniently be utilized
in the formation of alternate AVI programs. Using differing SCID's also
facilitates editing audio from one program with video from another etc.
A given AVI program may include a variety of signal component sources.
Shown in FIG. 1 are an interactive component source 10, a video source 17,
and first and second audio sources 20 and 23 (bilingual audio). The
controller 5 communicates with respective sources for time management
and/or enabling functions. The source of video signal 17 is coupled to a
video signal compression apparatus 18, which may compress signal according
to the video compression standard promoted by the Moving Pictures Experts
Group (MPEG). Similarly the respective audio signals from the sources 20
and 23 are applied to respective compression apparatus 21 and 24. These
compression apparatus may compress the respective audio signals according
to the audio compression standard promoted by the Moving Pictures Experts
Group (MPEG). Associated audio and video signals compressed according to
the MPEG protocol are synchronized with the use of presentation time
stamps (PTS), which are provided by a timing element 15. For insight into
how the audio and video may be temporally related, the reader's attention
is directed to INTERNATIONAL ORGANIZATION FOR STANDARDIZATION, ISO/IEC
JTC1/SC29/WG11; N0531, CODING OF MOVING PICTURES AND ASSOCIATED AUDIO,
MPEG93, SEPTEMBER, 1993.
The compressed audio and video signals are applied to transport packet
formers or processors 19, 22 and 25. Audio and video transport packet
processors are known and will not be described. Suffice it to say that the
packet processors divide the compressed data into payloads of
predetermined numbers of bytes and attach identifying headers including
SCID's, as indicated in FIG. 3. For detailed information on a video signal
transport packet processor, the reader is directed to U.S. Pat. No.
5,168,356. The packet processors are coupled to the packet multiplexer
which time division multiplexes the signal components. The transport
packet processor may include a buffer memory for temporarily storing
packetized data to accommodate the multiplexer servicing other components.
The packet processors include PACKET READY signal lines coupled to the
multiplexer to indicate when a packet is available.
Interactive programs are created, via known techniques, by a programmer
operating the interactive component source or programming element 10,
which may be a computer or personal computer (PC). In forming the
application the programming element 10 interfaces with a memory 11 and
memory controller 12, and the completed application is stored in the
memory 11. After completion, the application may be condensed or
translated to some native code to conserve signal bandwidth.
In the formation of the application, portions of the programs are formatted
into modules, transmission units and packets as shown in FIG. 4. The
packets are similar in form to the transport packets described above. A
transmission unit consists of a plurality of transport packets. Each
transmission unit includes a header packet which includes information
descriptive the transmission unit contents, and a plurality of basic
packets each of which includes a portion of the codewords of the
application. A module is divided into transmission units to facilitate
interleaving of information from different modules. Preferably,
interleaving of transmission units is permitted, but interleaving of
transport packets from different transmission units is not. For a more
detailed description of the formation of an application and transmission
units etc. the reader is referred to United States Patent No. (Ser. No.
08/234,139 allowed).
Modules are similar to computer files, and are of different types. A first
type of module is a Directory Module which contains information to
interrelate respective transmission units and modules as an application. A
second module type is a Code Module which comprises executable code
necessary to program a computing device at a receiver to perform or
execute the application. A third module type is a Data Module. Data
Modules include non-executable "data" used in the execution of the
application. Data Modules tend to be more dynamic than Code Modules, that
is Data Modules may change during a program while Code Modules generally
do not. A fourth type of module is designated a Signal Module. This module
is a special packet including information to trigger receiver interrupts,
which may be utilized for synchronization of e.g., video with application
program features, or to suspend operation of an application, or to
re-enable operation of a program etc. Synchronization is effected via
inclusion of presentation time stamps. Data Directory, Code and Signal
Modules are examples of the PC-data.
The respective modules may be error coded by the programming element 10.
For example the entire module may undergo cyclic redundancy coding CRC,
and error check bits may be added to the end of the module.
Each transmission unit, TU, is configured with a header including
information about the TU. Table I, shown in FIG. 5, illustrates exemplary
types of information included in each TU header packet. The header
includes a version number. The version number is included to indicate when
a change is made to the application during the presentation of the AVI
program. A receiver decoder may be arranged to update an executing
application responsive to detecting a change in version number. The Module
ID is similar to a computer file identifier and is provided by the
application programmer. The Module Transmission Unit Byte Offset is a
number which indicates the byte location in the module of the first
code/data byte of the payload of the TU. The Length (bytes) Of
Transmission Unit indicates the size of the TU and/or the location of the
last code/data byte in the TU.
Table II of FIG. 6 illustrates representative types of data included in the
Directory Module. The Directory Module includes a header with an
Application identifier, AID, a field indicating the application type, a
field which includes type qualifiers, a field which indicates the amount
of memory required to store and execute the application, a field
indicating the number of modules contained in the application, and a field
or fields (FIRST SECURITY INFORMATION) which may include security data
such as authenticating data. It will be appreciated that the respective
fields listed above, or those that follow, need not occur in the order
illustrated. A data portion of the Directory Module includes data for each
module similar to the header data for the respective modules. In addition
there is a string table which is a list of respective application module
names in ASCII format. The data section for each module may also include a
field or fields (FURTHER SECURITY INFORMATION) for security data related
to the respective module. Alternatively, this data may be included with
the more general directory information in the first security information
field. The contents of the module security information fields will be
discussed in detail below.
For transport packet formation, the interactive component source 10 may be
programmed to generate the actual transmission units and transport
packets, however in the embodiment of FIG. 1, a separate code/data packet
processor 14 is included. The code/data packet processor accesses the
respective areas of the memory 11 through the memory controller 12 and
generates packets in a sequence representing a respective application
(FIG. 4).
The packet multiplexer 16 is arranged to provide packets according to a
particular schedule. The schedule is nominally determined by the bandwidth
requirements of the AVI components. If there is multiplexing contention
between the respective AVI components it is preferred that the signal
component with packets that occur least frequently be assigned the higher
multiplexing priority.
The specifics of the packet multiplexer 16 will not be described because
multiplexing is a mature art and those skilled in digital signal
processing will readily be able to design a multiplexer to satisfy their
particular requirements. Suffice it to say that the packet multiplexer 16
may be arranged using three state logic switches with input ports coupled
to the respective component signals and their output ports coupled to the
multiplexer output port. A state machine may be arranged to control the
logic switches responsive to priorities established by the controller 5
and the respective packet ready signals provided by the packet formers.
Security in the AVI system is based on the close integration between
techniques implemented by the AVI system controller and security codes
resident in all AVI system compliant receivers. The security is based on
public key cryptography using the Rivest, Shamir, and Adleman, RSA,
algorithm or the Data Encryption Standard, DES. The algorithm preferred by
the present inventors is the RSA algorithm, using modulus and exponent
sizes which are respectively multiples of four (eight-bit) bytes. The
general type of security protection resides in authentication of a
certificate supplied with Directory Modules, and hash values generated
over respective other application modules.
A special class of RSA protocols is that in which the public exponent is 3.
An advantage resides in the fact that signature checking speed may be
enhanced by inclusion of "helping" information of the type described
below.
Consider that a receiver is to verify that S is a RSA signature over data
D, where the public modulus and exponent are N and 3 respectively. To
verify, the receiver essentially has to show that S.sup.3 =D(mod N).
Nominally this requires a division/modulo operation by N, which is
computationally difficult and time consuming. Since multiplication is a
computationally simpler and faster operation, a checking operation which
relies on multiplication rather than division will significantly speed up
the operation.
Consider the quotients Q1 and Q2 defined as follows
S.sup.2 /N=Q1+R1; S*R1/N=Q2+R2; R2=D; if S.sup.3 =D(mod N). That is, the
values Q1 and Q2 are whole number quotients derived from the signature by
division by N. R1 and R2 are respective remainders after division. Given
any N, S and D of size at most T bits, where S<N and D<N, then there exist
quotients Q1, Q2 of size at most T bits which will verify S.sup.3 =D(mod
N) using the algorithm outlined immediately below. If the values Q1 and Q2
are calculated by the application programmer (e.g. in non-real time) and
transmitted within the Directory Module with the signature S, it can be
shown that a fast check on the signature may be performed as follows.
At the receiver, extract S, Q1, Q2 from the Directory Module and;
______________________________________
1. compute
A = S.sup.2
2. compute
B = Q1 times N
3. compare
A > B; If A< B quit, signature cannot check,
else if A> B
4. compute
C = A- B
5. compare
C < N; If C > N quit, signature cannot check,
else if C < N
6. compute
E = C times S
7. compute
F = Q2 times N
8. Compare
E > F, If E < F quit, signature cannot check,
else if E > F
9. compute
G = E - F
10. Compare
G = D, if not, signature does not check.
______________________________________
Note that all arithmetic operations are simple multiplications or
subtractions. The detection of an erroneous signature may occur at steps
3, 5, 8 or 10. If an erroneous signature is detected at steps 3 or 5, very
little computational time has been expended.
The AVI receivers are provided with the public keys (and desirably helping
quotients Q1 and Q2) of the respective system providers for decrypting
signed certificates included with PC-data to determine program
authenticity. If program authenticity is not confirmed, the received
application is immediately dumped from the receiver. Central to such a
security system is the assignment of unique identifiers, ID's, to
application providers and the system controller or server. The system
controller allocates unique e.g. 32-bit ID's to each trusted AVI
application provider and also issues a certificate for the application
provider's public key. The certificate is essentially the system
controller's digital signature on the application provider's public key
and includes fields such as the expiration date of the certificate, the ID
of the provider, and a limit on the amount of storage an application with
this ID can use in the file system of the receivers. The system controller
may employ a plurality of different private-public key pairs, and the
certificate may include flags to designate which of the plurality of
public keys the receiver should use to decrypt respective certificates.
A certificate for application providers will nominally include:
CERTIFICATE.sub.-- FLAGS (which identify the certificate type and may
include the system controller's public key flag);
PROVIDER.sub.-- ID, (which indicate length of provider ID);
PROVIDER.sub.-- EXPIRE, (which indicates application lifetime);
PROVIDER.sub.-- AUTHORIZATION.sub.-- FLAGS,
PROVIDER.sub.-- STORAGE.sub.-- LIMIT, (which indicates allotted receiver
memory);
PROVIDER.sub.-- NAME, (the application provider's name)
PROVIDER.sub.-- FIXED.sub.-- CERT, (which is the providers public key).
This foregoing certificate information is hashed modulo 128, and the hash
value is appended thereto.
The CERTIFICATE.sub.-- FLAGS mentioned above include authorization flags
which grant/deny the receiver processors access to privileged actions.
Examples of representative pri | | |
