United States Patent (19)
`rzberg et al.
`He
`
`III
`
`US005745678A
`Patent Number:
`11
`45 Date of Patent:
`
`5,745,678
`Apr. 28, 1998
`
`54
`
`T5)
`
`73
`
`21
`22
`
`63
`
`51
`52
`58
`
`METHOD AND SYSTEM FOR THE
`SECURED EDSTRIBUTION OF MULTIMEDIA
`TITLES
`Inventors: Amir Herzberg; Hugo Mario
`Krawczyk, both of Bronx, N.Y.; Shay
`Kutten, Rockaway, N.J.; An Van Le,
`Sunnyvale, Calif.; Stephen Michael
`Matyas, Poughkeepsie; Marcel
`Mordechay Yung, New York, both of
`N.Y.
`
`Assignee: International Business Machines
`Corporation, Armonk, N.Y.
`
`Appl. No.: 914,911
`Filed:
`Aug. 18, 1997
`Related U.S. Application Data
`
`Continuation of Ser. No. 354,700, Dec. 13, 1994, aban
`doned.
`Int. Cl. ... HO4.9/00
`U.S. Cl. ....................................... 395/186; 380/4
`Field of Search ............................... 395/186, 187.01,
`395/188.01; 380/3, 4, 9, 23, 25
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,295,039 10/1981 Stuckert .................................. 235/380
`4,309,569
`1/1982 Merkle ............................... 340/825.34
`4,658,093 4/1987 Hellman .................................... 330/25
`4,789,863 12/1988 Bush .........
`3401825.34
`4,908,861
`3/1990 Brachtl et al. ..................... 340,825.35
`
`5,065,429 11/1991 Lang ........................................ 380/25
`5,191,613 3/1993 Graziano et al. ......................... 380/25
`5,224,166 6/1993 Hartman, Jr. ............................. 380/50
`5,231,666 7/1993 Matyas ..................................... 380/25
`5,241,671
`8/1993 Reed et al.....
`... 70/104
`5,247,575 9/1993 Sprague et al.
`379/55.1
`5,276,738
`1/1994 Hirsh. ......................................... 38Of46
`5.319,705 6/1994 Halter ...
`... 330/4
`5,343,527 8/1994 Moore .......
`... 38Of4
`5,379.343
`1/1995 Grube et al. .
`... 38Of4
`5,421,006 5/1995 Jablon et al. ............................... 38Of4
`5.432,939 7/1995 Blackledge ...
`395/700
`5,450,489 9/1995 Ostrover ...
`......, 380/3
`5.485,577
`1/1996 Eyer ......
`395/188.01
`5,530,751
`6/1996 Morris ......................................... 380/4
`5.535,188 7/1996 Dang .....
`... 369/84
`5,553,139 9/1996 Ross.
`... 380f4
`5,553,143 9/1996 Ross .......................................... 380/25
`FOREIGN PATENT DOCUMENTS
`565 314 A3 10/1993 United Kingdom.
`570 123A1 11/1993 United Kingdom.
`Primary Examiner-Albert Decady
`Attorney, Agent, or Firm-Casimer K. Salys; Daniel E.
`Venglarik; Andrew J. Dillon
`57
`ABSTRACT
`A method and system for detecting authorized programs
`within a data processing system. The present invention
`creates a validation structure for validating a program. The
`validation structure is embedded in the program and in
`response to an initiation of the program, a determination is
`made as to whether the program is an authorized program.
`The determination is made using the validation structure.
`
`38 Claims, 6 Drawing Sheets
`
`8
`Rae give
`rulirted a title
`(with timbedded
`ratus taken)
`802.
`
`F. vi.e.
`
`804
`Read are ded
`signature toker
`8 6
`Red able of
`contsils 1
`8 8
`C
`calcula:
`of
`a tab
`cartris
`81
`
`3
`
`836
`radicata
`tiri
`its in sid
`No
`stated
`disa
`
`rer OC
`
`acuate a
`28-bit A
`sced
`data waste
`
`of
`
`Rd in data
`(or) or the
`object-prap a ty
`pair poinle d to
`by the salacted
`its ract
`
`Wali sale M
`or tase of
`Rancies inty
`contants against
`sists and read
`RC stored a
`-2
`sigrature taken
`on
`at he
`retaining data
`records in the
`82 signature token
`
`838 (O- No 839
`
`Set Y -
`
`+
`
`3D
`Read digits
`signature in
`signature akan
`8.2
`
`Access
`public key
`84.4
`Walidata
`the digital
`signalute using
`public key
`8.
`Accep 1 tita or
`and
`its
`ity
`crities
`
`826
`
`824
`
`
`
`ridick
`tified is
`tits invasid
`
`82>
`
`(Os 8
`
`N
`
`licats
`rtim dia
`tie in fid
`
`86
`
`do go
`scre is
`ultiradia title
`88
`an og screen
`
`Waita is to
`on logo screer
`gains Mc
`to raid in
`signature in kan
`
`IPR2020-01218
`Sony EX1012 Page 1
`
`

`

`U.S. Patent
`
`Apr. 28, 1998
`
`Sheet 1 of 6
`
`5,745,678
`
`
`
`IPR2020-01218
`Sony EX1012 Page 2
`
`

`

`US. Patent
`
`e
`
`a
`
`I'll{:30:"III_m23ESI.2I‘ll...as.u9Eu.9..03253325
` MmmzwficoznoIEIII“All-ll.uE:moaa.Il.““_Ea;“mm.Efic..__...Mug3Imme.mm.235.hu1..-_e.§IIII3...:us.2:a:E_n2128.2.3:928I.-nuanroEuE
`
`:flnauwk.19m3:22.‘mxouchwoE3.3.2..>235.muo.‘m2_dIa....dom.mu==.—=.E,_hnAmI'll-IIIII—III‘III-lm“IIIIIIII¢II
`:22I...‘u.nll'lv_.3235III“2:.un.22.we2:.0:5:2;wm25E31»LEEupaaou
`
`
`
`
`223S.“HKI::u.IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII.n.1-m..II.nnmu:“I.".punnucuuii--.L2.c:1...“-.IIIII'"
`
`—m.
`
`lllmm.1.......................6n.a:5,uHn4“-mmm.m7.!IIIIllllllIIIIIIIIIIIIIIIIIIlllllllllllllllllllllllIIIIIIIIIIIlllllllllllL-EomlaurlllllllJ525.022022.2
`
`
`
`
`
`
`
`
`1_n..—gu_—_n-¢_uu---c“fillm
`953.93anIESun2ao:H3235
`EmuEoEoE..A"““f:
`e.x»BI
`
`cm.33...ucw
`
`E1
`
`:
`
`til
`III
`III
`
`|PR2020-01218
`
`Sony EX1012 Page 3
`
`0223:m<N.3;
`
`
`
`Nun::2.ton
`
`5a.:
`
`3:82:00
`
`-22.:
`
`3:303
`
`nn--
`
`IPR2020-01218
`Sony EX1012 Page 3
`
`
`
`

`

`U.S. Patent
`
`Apr. 28, 1998
`
`Sheet 3 of 6
`
`5,745,678
`
`Authoring
`Tool
`
`Master
`CD-ROM
`
`CD-ROM
`- Title
`- Signature Token
`
`300
`
`304
`
`306
`
`
`
`Signature Token
`Generation MO due
`
`308
`
`Title
`(with Signature Token)
`
`R U N T ME ENW R ON MENT with
`Signature Token
`Walidation Module
`
`Fig. 3
`
`Object
`identifier
`
`Property
`dentifier
`
`Type
`
`Location
`
`
`
`402
`404
`406
`408
`
`Fig. 4
`
`IPR2020-01218
`Sony EX1012 Page 4
`
`

`

`US. Patent
`
`A
`
`892
`
`8991
`
`hS
`
`.4
`
`5,745,678
`
`WJEooomSun
`
`
`
`:2;E31.235223:3
`
`¢om
`
`233353:30:EouomSusan333.3.0.EooomSaQE
`
`
`
`2.3.2.33235
`
`
`
`.3on$3235:33»23535
`
`
`
`
`
`2282cozmuza>233:5:20:00
`
`mcomcom
`
`
`
`6EmaoiEaaoi
`
`
`
`cmcozm3_m>5223.00
`
`m.E
`
`35332320
`
`539325
`
`3.323.820
`
`E212;
`
`|PR202001218
`
`Sony EX1012 Page 5
`
`IPR2020-01218
`Sony EX1012 Page 5
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 28, 1998
`
`Sheet 5 of 6
`
`5,745,678
`
`700
`
`7 12
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Receive
`multime dia
`title (without
`signature token)
`7 O2
`
`Fix variable s
`N and M
`
`704
`
`Read table of
`contents in
`multimedia title
`705
`
`Calcuate an
`MD C on table of
`Contents data
`706
`
`Read logo screen
`in multime dia
`title
`
`707
`
`Calculate an
`MDC on logo
`screen data
`708
`
`Calculate number
`of object-property
`pair (S) in
`multimedia title
`7 10
`
`Set n = n in
`(N, S)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Set R
`
`2
`
`Select an
`Object-property
`and read data
`from the
`multimedia title.
`Remember
`location of
`referenced data.
`7 16
`
`Calculate MDC
`On data
`
`Yes 722
`
`Build a
`signature token
`(less the digitat
`Signature)
`
`724
`
`Calculate a
`digital signature
`on the signature
`token and store
`in signature token
`
`720
`
`Set X = X + 1
`
`Fig. 7
`
`IPR2020-01218
`Sony EX1012 Page 6
`
`

`

`U.S. Patent
`
`Apr. 28, 1998
`
`Sheet 6 of 6
`
`5,745,678
`
`836
`
`in dicate
`mu time dia
`title invalid
`
`
`
`
`
`834
`
`No
`
`Calculated Yes
`MD C = d at a
`record
`MD C
`
`800
`
`Receive
`multimedia title
`(with embedded
`signature token)
`802
`
`Fix variable R
`
`804.
`
`838 (O-
`
`No 839
`
`Set Y = Y
`
`840
`Re a d digital
`signature in
`signature token
`842
`
`Access
`public key
`84 4
`Walidate
`the digital
`signature using
`public key
`846
`Accept title or
`and e title
`in valid
`condition
`
`
`
`
`
`
`
`
`
`
`
`826
`
`
`
`
`
`
`
`824
`
`indic at a
`multime dia
`title in valid
`
`Fig. 8
`
`Read embedded
`signature to ken
`806
`
`Read table of
`contents O
`808
`Cacuate MDC
`on table of
`conterts
`81 O
`Walidate MDC
`on table of
`contents a gain St
`MDC stored in
`signature to ken
`
`
`
`
`
`
`
`
`
`
`
`
`
`8 12
`
`Calculate a
`128-bit MDC
`on the selected
`data value
`
`Read the data
`(OP) for the
`object-property
`pair pointed to
`by the selected
`data record
`
`
`
`Randomly
`select and read
`one of the n-2
`remaining data
`record S in the
`signature token
`
`
`
`
`
`
`
`814
`indicate
`m ult in edia
`title invalid
`
`822
`
`
`
`8 16
`Read to go
`screen in
`multime di a title
`818
`Calculate MDC
`on to go screen
`8 20
`Walidate MDC
`on to go screen
`against MDC
`st of ed in
`signature token
`
`IPR2020-01218
`Sony EX1012 Page 7
`
`

`

`5,745,678
`
`1.
`METHOD AND SYSTEM FOR THE
`SECURED DISTRIBUTION OF MULTIMEDIA
`TITLES
`
`This is a continuation of application Ser. No. 08/354,700,
`filed Dec. 13, 1994, now abandoned.
`BACKGROUND OF THE INVENTION
`1. Technical Field
`The present invention generally relates to an improved
`data processing system, and in particular to a method and
`system for distributing multimedia programs. Still more
`particularly, the present invention relates to a method and
`system for checking for authorized multimedia programs
`and detecting unauthorized multimedia programs in a data
`processing system.
`2. Description of the Related Art
`Multimedia data processing systems present information
`in data to a user utilizing sound, graphics, animation, and
`text. Programs presenting data and information to a user in
`this form are also called multimedia titles. Typically, a
`software company develops and markets a software system
`for the production and presentation of multimedia titles.
`Such a software system is used in composing multimedia
`scripts formultimedia titles. Typically, the software system
`includes a set of authoring tools for producing multimedia
`titles by developers and a Run Time Environment (RTE) for
`presenting the multimedia titles to end users. Typically, the
`RTE is designed to execute on various computing platforms,
`which makes the authoring tools for the software system
`desirable to developers. Typically, developers pay a royalty
`to the software company for using the authoring tools to
`develop multimedia titles to run on the RTE. But some
`unscrupulous developers may produce unauthorized titles
`and avoid royalty payments in producing multimedia titles
`for use on the RTE. Therefore, it would be advantageous to
`have a method and system to allow authorized titles to
`execute on a data processing system and to detect attempted
`execution of unauthorized titles.
`
`5
`
`15
`
`20
`
`25
`
`30
`
`35
`
`SUMMARY OF THE ENVENTION
`It is one object of the present invention to provide an
`improved data processing system.
`It is another object of the present invention to provide a
`method and system for distributing multimedia programs.
`It is yet another object of the present invention to provide
`a method and system for checking for authorized multimedia
`programs and detecting unauthorized multimedia programs
`in a data processing system.
`The present invention provides a method and system for
`detecting authorized multimedia programs within a data
`processing system. The present invention creates a valida
`tion structure for validating a multimedia program. The
`validation structure is embedded in the multimedia program
`and in response to an initiation of the multimedia program,
`a determination is made as to whether the multimedia
`program is an authorized multimedia program. The deter
`mination is made using the validation structure.
`In creating the validation structure, sections of the pro
`gram (hereinafter called data objects) are selected and a
`cryptographic hash value is created or calculated on each of
`the selected data objects. The cryptographic hash value and
`the location of the selected data object are stored as a data
`record within the validation structure. In addition, a signa
`ture is included or associated with the validation structure.
`
`2
`The signature is calculated on the validation structure using
`a public key cryptographic algorithm in accordance with a
`preferred embodiment of the present invention.
`Determining whether a multimedia program is an autho
`rized multimedia program is accomplished by selecting a
`subset of the data objects within the multimedia program
`and validating the selected data objects using the validation
`structure stored in the multimedia program. This includes
`the steps of randomly selecting a portion of the data objects
`from among a defined set of data records listed in the
`validation structure, reading the selected data objects from
`the multimedia program using location information stored in
`the validation structure, and validating the selected data
`objects using validation information stored in the validation
`structure. For each selected data object, the location infor
`mation stored in the validation structure is accessed and used
`to read the selected data object from the multimedia pro
`gram. A cryptographic hash value is calculated on the
`selected data object and then compared for equality with a
`corresponding hash-value-of-reference stored in the valida
`tion structure The hash values must be equal for the selected
`data objects to be valid. In addition, the validation structure
`is itself validated through the use of the signature previously
`calculated on the validation structure, using a public key
`cryptographic algorithm, and stored within the validation
`structure. If the signature, validation structure, and subset of
`selected data objects are valid, the multimedia program is
`considered to be an authorized multimedia program. An
`authorized multimedia program is allowed to execute
`normally, otherwise, execution of the multimedia program
`may be prohibited or limited execution of the multimedia
`program may be allowed in response to a determination that
`the multimedia program is not an authorized program.
`The above as well as additional objectives, features, and
`advantages of the present invention will become apparent in
`the following detailed written description.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The novel features believed characteristic of the invention
`are set forth in the appended claims. The invention itself,
`however, as well as a preferred mode of use, further objec
`tives and advantages thereof, will best be understood by
`reference to the following detailed description of an illus
`trative embodiment when read in conjunction with the
`accompanying drawings, wherein:
`FIG. 1 depicts a data processing system in the form of a
`personal computer in which the present invention can be
`employed;
`FIG. 2 is a block diagram of a personal computer system
`illustrating the various components of personal computer
`system in accordance with the present invention;
`FIG. 3 is a block diagram of a creation and distribution
`process for multimedia titles on CD-ROM depicted in
`accordance with a preferred embodiment of the present
`invention;
`FIG. 4 is a depiction of entries in a table of contents in
`accordance with a preferred embodiment of the present
`invention;
`FIG. 5 is a block diagram of a signature token generation
`module, depicted in accordance with a preferred embodi
`ment of the present invention;
`FIG. 6 is a block diagram of a signature token validation
`module depicted in accordance with a preferred embodiment
`of the present invention;
`FIG. 7 is a flowchart of a process for generating signature
`tokens in a signature token generation module depicted in
`accordance with a preferred embodiment of the present
`invention; and
`
`45
`
`50
`
`55
`
`65
`
`IPR2020-01218
`Sony EX1012 Page 8
`
`

`

`3
`FIG. 8 is a flowchart of a process for validating multi
`media titles in a validation program depicted in accordance
`with a preferred embodiment of the present invention.
`DETALED DESCRIPTION OF PREFERRED
`EMBODIMENT
`With reference now to the figures and in particular with
`reference to FIG. 1, a data processing system, personal
`computer system 10 is depicted, in which the present inven
`tion can be employed. As shown, personal computer system
`10 comprises a number of components, which are intercon
`nected together. More particularly, a system unit 12 is
`coupled to and can drive an optional monitor 14 (such as a
`conventional video display). A system unit 12 also can be
`optionally coupled to input devices such as a PC keyboard
`16 or a mouse 18. Mouse 18 includes right and left buttons
`(not shown). The left button is generally employed as the
`main selector button and alternatively is referred to as the
`first mouse button or mouse button 1. The right button is
`typically employed to select auxiliary functions as explained
`later. The right mouse button is alternatively referred to as
`the second mouse button or mouse button 2. An optional
`output device, such as a printer 20, also can be connected to
`the system unit 12. Finally, system unit 12 may include one
`or more mass storage devices such as the diskette drive 22.
`As will be described below, the system unit 12 responds
`to input devices, such as PC keyboard 16, the mouse 18, or
`local area networking interfaces. Additionally, input/output
`(I/O) devices, such as floppy diskette drive 22, display 14,
`printer 20, and local area network communication system
`are connected to system unit 12 in a manner well known. Of
`course, those skilled in the art are aware that other conven
`tional components also can be connected to the system unit
`12 for interaction therewith. In accordance with the present
`invention, personal computer system 10 includes a system
`processor that is interconnected to a random access memory
`(RAM), a read only memory (ROM), and a plurality of I/O
`devices.
`In normal use, personal computer system 10 can be
`designed to give independent computing power to a small
`group of users as a server or a single user and is inexpen
`sively priced for purchase by individuals or small busi
`nesses. In operation, the system processor functions under
`an operating system, such as IBM's OS/2 operating system
`or DOS, OS/2 is a registered trademark of International
`Business Machines Corporation. This type of operating
`system includes a Basic Input/Output System (BIOS) inter
`face between the I/O devices and the operating system.
`BIOS, which can be stored in a ROM on a motherboard or
`planar, includes diagnostic routines which are contained in
`a power on self test section referred to as POST.
`Prior to relating the above structure to the present
`invention, a summary of the operation in general of personal
`computer system 10 may merit review. Referring to FIG. 2,
`there is shown a block diagram of personal computer system
`10 illustrating the various components of personal computer
`system 10 in accordance with the present invention. FIG. 2
`further illustrates components of planar 11 and the connec
`tion of planar 11 to I/O slots 46a-46d and other hardware of
`personal computer system 10. Connected to planar 11 is the
`system central processing unit (CPU) 26 comprised of a
`microprocessor which is connected by a high speed CPU
`local bus 24 through a bus controlled timing unit 38 to a
`memory control unit 50 which is further connected to a
`volatile random access memory (RAM) 58. While any
`appropriate microprocessor can be used for CPU 26, one
`
`45
`
`50
`
`55
`
`65
`
`5,745,678
`
`10
`
`15
`
`20
`
`25
`
`35
`
`4
`suitable microprocessor is the Pentium microprocessor,
`which is sold by Intel Corporation. "Pentium” is a trademark
`of Intel Corporation.
`While the present invention is described hereinafter with
`particular reference to the system block diagram of FIG. 2,
`it is to be understood at the outset of the description which
`follows, it is contemplated that the apparatus and methods in
`accordance with the present invention may be used with
`other hardware configurations of the planar board. For
`example, the system processor could be an Intel 80286,
`80386, or 80486 microprocessor. These particular micropro
`cessors can operate in a real addressing mode or a protected
`addressing mode. Each mode provides an addressing
`scheme for accessing different areas of the microprocessor's
`memory.
`Returning now to FIG. 2, CPU local bus 24 (comprising
`data, address and control components) provides for the
`connection of CPU 26, an optional math coprocessor 27, a
`cache controller 28, and a cache memory 30. Also coupled
`on CPU local bus 24 is a buffer 32. Buffer 32 is itself
`connected to a slower speed (compared to the CPU local
`bus) system bus 34, also comprising address, data and
`control components. System bus 34 extends between buffer
`32 and a further buffer 36. System bus 34 is further con
`nected to a bus control and timing unit 38 and a Direct
`Memory Access (DMA) unit 40. DMA unit 40 is comprised
`of a central arbitration unit 48 and a DMA controller 41.
`Buffer 36 provides an interface between the system bus 34
`and an optional feature bus such as the Micro Channel bus
`44. "Micro Channel' is a registered trademark of Interna
`tional Business Machines Corporation. Connected to bus 44
`are a plurality of I/O slots 46a-46d for receiving Micro
`Channel adapter cards which may be further connected to an
`I/O device or memory. In the depicted example, I/O slot 46c
`has a hard disk drive connected to it; I/O slot 46b has a
`CD-ROM drive connected to it; and I/O slot 46a has a ROM
`on an adapter card connected to it. Other devices, such as a
`modem may be connected to an I/O slot. An arbitration
`control bus 42 couples the DMA controller 41 and central
`arbitration unit 48 to I/O slots 46 and diskette adapter 82.
`Also connected to system bus 34 is a memory control unit
`50 which is comprised of a memory controller 52, an address
`multiplexer 54, and a data buffer 56. Memory control unit 50
`is further connected to a random access memory as repre
`sented by RAM module 58. Memory controller 52 includes
`the logic for mapping addresses to and from CPU 26 to
`particular areas of RAM 58. While the personal computer
`system 10 is shown with a basic 1 megabyte RAM module
`in RAM 58, it is understood that additional memory can be
`interconnected as represented in FIG. 2 by the optional
`memory modules 60 through 64.
`A further buffer 66 is coupled between system bus 34 and
`a planar I/O bus 68. Planar I/O bus 68 includes address, data,
`and control components respectively. Coupled along planar
`bus 68 are a variety of I/O adapters and other peripheral
`components such as display adapter 70 (which is used to
`drive an optional display 14 depicted in FIG. 1), a clock 72,
`nonvolatile RAM 74 (hereinafter referred to as “NVRAM”),
`a RS232 adapter 76, a parallel adapter 78, a plurality of
`timers 80, a diskette adapter 82, a PC keyboard/mouse
`controller 84, and a read only memory (ROM) 86. The ROM
`86 includes BIOS which provides the user transparent
`communications between many I/O devices.
`Clock 72 is used for time of day calculations. NVRAM 74
`is used to store system configuration data. That is, the
`NVRAM will contain values which describe the present
`configuration of the system. For example, NVRAM 74
`
`IPR2020-01218
`Sony EX1012 Page 9
`
`

`

`5
`contains information which describe the capacity of a fixed
`disk or diskette, the type of display, the amount of memory,
`etc. Of particular importance, NVRAM 74 will contain data
`which is used to describe the system console configuration;
`i.e., whether a PC keyboard is connected to the keyboard/
`mouse controller 84, a display controller is available or the
`ASCII terminal is connected to RS232 adapter 76.
`Furthermore, these data are stored in NVRAM 74 whenever
`a special configuration program is executed. The purpose of
`the configuration program is to store values characterizing
`the configuration of this system to NVRAM 76 which are
`saved when power is removed from the system.
`Connected to keyboard/mouse controller 84 are ports A
`and B. These ports are used to connect a PC keyboard (as
`opposed to an ASCII terminal) and mouse to the PC system.
`Coupled to RS232 adapter unit 76 is an RS232 connector.
`An optional ASCII terminal can be coupled to the system
`through this connector.
`Specifically, personal computer system 10 may be imple
`mented utilizing any suitable computer such as the IBM
`PS/2 computer or an IBM RISC SYSTEM/6000 computer,
`both products of International Business Machines
`Corporation, located in Armonk, N.Y. "RISC SYSTEM/
`6000” is a trademark of International Business Machines
`25
`Corporation and "PS/2" is a registered trademark of Inter
`national Business Machines Corporation.
`Distribution of multimedia programs or titles (hereinafter
`called "multimedia titles”) involves an application devel
`oper who produces multimedia titles using an authoring tool
`and a Run Time Environment (RTE) provided by a multi
`media company and a user who purchases multimedia titles
`for execution on a computer or computer platform executing
`the RTE. In accordance with a preferred embodiment of the
`present invention, checking for authorized multimedia titles
`35
`and detecting unauthorized multimedia titles involves a
`scheme of digital signatures using a public key algorithm. A
`"public key” is a key made available to anyone who wants
`to encrypt information. In public key cryptography, public
`key algorithms are used in which a public key is used for
`encryption and a private key is used for decryption. The
`basis for public key cryptography includes discrete
`logarithms, factoring, and the knapsack problem. Each
`authorized multimedia title includes an embedded digital
`signature token that can be verified by the RTE before the
`multimedia title is permitted to execute on the data process
`ing system.
`Two cryptographic subsystems are employed to facilitate
`the signature token generation and signature token verifica
`tion processes in accordance with a preferred embodiment of
`the present invention. One cryptographic subsystem enables
`the generation of signature tokens that, when embedded in
`authorized multimedia titles, will permit these titles to be
`validated. Another cryptographic subsystem is employed to
`validate the signature tokens. In this manner authorized
`multimedia titles may be distinguished from unauthorized
`multimedia titles.
`With reference to FIG. 3, a block diagram of a creation
`and distribution process for multimedia titles on CD-ROM
`is depicted in accordance with a preferred embodiment of
`the present invention. Those skilled in the art will recognize
`that the subject invention could be practiced in an imple
`mentation wherein multimedia titles are distributed on
`media other than a CD ROM medium. A multimedia title is
`developed by a developer using authoring tool 300. The
`multimedia title is then processed using signature token
`generation module 302. This module generates a signature
`
`45
`
`50
`
`55
`
`65
`
`5,745,678
`
`O
`
`15
`
`30
`
`6
`token for the multimedia title. The signature token is embed
`ded within the multimedia title. Thereafter, the multimedia
`title with the signature token embedded within it is sent back
`to the developer who creates a master CD-ROM 304.
`Alternatively, the signature token and multimedia title are
`sent back to the developer, whereupon the signature token is
`embedded into the multimedia title and a master CD-ROM
`304 is created by the developer. From master CD-ROM 304.
`CD-ROM 306 is produced containing the multimedia title
`and the embedded signature token. CD-ROM 306 may be
`placed within data processing system 308, which includes
`the RTE with the signature token validation module in
`accordance with a preferred embodiment of the present
`invention. When the title is to be executed within data
`processing system 308, the RTE reads the signature token
`from the CD-ROM and validates the signature token and a
`selected portion of the data objects also read from the
`CD-ROM using the signature token validation module.
`Typically, a multimedia title takes about one hour to play
`and contains about 650 megabytes of data. As a result, it is
`inefficient to validate a multimedia title by reading and
`checking each byte within the title. In accordance with a
`preferred embodiment of the present invention, the multi
`media title is validated by checking a portion of the data
`contained therein.
`Random sampling of data to validate multimedia titles is
`employed in accordance with a preferred embodiment of the
`present invention. If the data locations to be sampled were
`constant from one instance of validation to the next, then
`only a small portion of the multimedia title would be
`checked. In such a situation, forged titles could be more
`easily constructed. But by randomly selecting data locations
`for sampling, the possibility of forged multimedia titles is
`greatly reduced.
`In addition, the presently claimed invention utilizes data
`context sampling. A significant improvement in the valida
`tion of multimedia titles may be achieved if the logical
`structure of the multimedia titles themselves is employed to
`identify key pieces of data to be validated. For example, a
`preferred checking strategy may be based on checking part
`or all of the data in the table of contents for each file in a
`multimedia title. A multimedia title consists of one or more
`files, each containing its own table of contents. In many
`cases the multimedia title contains only one such file. When
`a file is opened, the table of contents is the first item to be
`read.
`With reference now to FIG. 4, a depiction of entries in a
`table of contents is illustrated in accordance with a preferred
`embodiment of the present invention. Table of contents 400
`includes entries 402-408. Each entry includes an object
`identifier, a property identifier, a type, and a location (offset
`and length). As a result, a particular entry indicates that at a
`particular offset on the disk, for this many bytes, a property
`with this ID belonging to an object with this ID of this type
`is located. Because the table of contents references data on
`the basis of an ObjectID and a Property ID, the referenced
`data object is said to be referenced by an object-property
`(OP) pair and the data object is referred to as OP data. Of
`course, other formats and specifications for the table of
`contents may be utilized in accordance with a preferred
`embodiment of the present invention. The table of contents,
`regardless of its format, structure, and sematics, may be
`employed to effectively validate a multimedia title in accor
`dance with a preferred embodiment of the present invention.
`Typically in multimedia titles, the table of contents is an
`example of a relatively short and easily identifiable piece of
`information that has an intrinsic dependency with most of
`
`IPR2020-01218
`Sony EX1012 Page 10
`
`

`

`5,745,678
`
`15
`
`20
`
`25
`
`30
`
`35
`
`7
`the other parts of the multimedia title. The table of contents
`could take the form of a symbol table, a linkage map, and so
`forth, but is rigidly specified and highly structured.
`Furthermore, for multimedia titles, the first few displayed
`screens typically contain the name of the title and its version.
`As a result, protecting these screens is desirable. Therefore,
`a checking strategy may include checking the first few
`screens of data displayed to a user so that a forged title,
`whose name is for example "Demons for the Deep", would
`be forced to display the name of the title upon which it is
`piggy-backing, say "Desert Wargames'.
`The present invention provides a method and system for
`validating multimedia titles by validating part or all of the
`table of contents and the first few displayed screens con
`taining the name of the title and its version for each
`multimedia file and validating a subset of the data objects in
`the multimedia title. These data objects are selected ran
`domly in accordance with a preferred embodiment of the
`present invention. But those skilled in the art will recognize
`that the data objects could be selected using a preferred
`method which is non-random, without departing from the
`spirit of the present invention.
`With reference to FIG. 5, a diagram of a signature token
`is depicted in accordance with a preferred embodiment of
`the present invention. Signature token 500 is constructed by
`a signature token generation module (not shown in FIG. 5).
`The signature token is constructed step-by-step by making
`repeated service requests to the signature token generation
`module. Once created, signature token 500 is embedded in
`the multimedia title upon which it was generated. This
`signature token is validated by a signature token validation
`module in the RTE. In validation, the signature token is
`validated step-by-step by making repeated service requests
`to the signature token validation module.
`Signature token 500 includes a header 502 and data
`records 1 through n that correspond to data or data objects
`in the multimedia title that can be selected and validated.
`The data records 1 through n in the signature token are
`different from the data objects in the multimedia title,
`although there is a direct correspondence. In addition, sig
`nature token 500 includes digital signature 504, which is
`employed to validate the header and the series of data
`records 1 through n in the signature token. Each data record
`within sig