

Block ciphering system, using permutations to hide the core ciphering function of each encryption round 
7876898 
Block ciphering system, using permutations to hide the core ciphering function of each encryption round


Patent Drawings: 
(8 images) 

Inventor: 
Gorissen, et al. 
Date Issued: 
January 25, 2011 
Application: 
10/596,336 
Filed: 
November 30, 2004 
Inventors: 
Gorissen; Paulus Mathias Hubertus Mechtildus Antonius (Eindhoven, NL) Trescher; Joachim Artur (Eindhoven, NL) Staring; Antonius Adriaan Maria (Eindhoven, NL) Mallon; Willem Charles (Eindhoven, NL) Treffers; Menno Anne (Eindhoven, NL)

Assignee: 

Primary Examiner: 
Zand; Kambiz 
Assistant Examiner: 
Poltorak; Peter 
Attorney Or Agent: 
Schwegman, Lundberg & Woessner, P.A. 
U.S. Class: 
380/200; 380/210; 726/26 
Field Of Search: 
380/255 
International Class: 
H04N 1/44 
U.S Patent Documents: 

Foreign Patent Documents: 
WO2005/060147 
Other References: 
Gabriele Spenger, "Authentication, Identification Techniques, and Secure ContainersBaseline Technologies,"Digital Rights Management, LNCS2770, pp. 6280, 2003. cited by examiner. Chow et al. , "A WhiteBox DES Implementation for DRM Applications", Preproceedigns for ACM DRM2002 workshop, Oct. 2002. cited by examiner. 

Abstract: 
In a system, a server provides a digital signal processing function f to an executing device in an obfuscated form. The function f includes a function cascade of signal processing functions f.sub.i, 1.ltoreq.i.ltoreq.N (e.g., FC.sub.1(x).ident.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x)). The server includes a processor for selecting a set of 2N invertible permutations p.sub.i, 1.ltoreq.i.ltoreq.2N; calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N; and calculating a set of N1 functions h.sub.i, where h.sub.i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N. The server equips the executing device with an execution device function cascade that includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters (e.g., ED.sub.1(y.sub.1, . . . , y.sub.N).ident.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcir cle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1), and provides the functions g.sub.1, . . . g.sub.N to the executing device. The executing device obtains the functions g.sub.1, . . . , g.sub.N and a processor for loading the execution device function cascade and applying the loaded execution device function cascade to the functions g.sub.1, . . . , g.sub.N (e.g., ED.sub.1(g.sub.1, . . . , g.sub.N)). 
Claim: 
The invention claimed is:
1. A method of providing a digital signal processing function f to an executing device having at least one processor in an obfuscated form; the function f including afunction cascade including a plurality of signal processing functions f.sub.i, 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output, the method including: performing the following steps by at least one processorof the executing device: selecting a set of 2N invertible permutations p.sub.i, 1.ltoreq.i.ltoreq.2N; calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for1.ltoreq.i.ltoreq.N; calculating a set of N1 functions h.sub.i, where h.sub.i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N; equipping the executing device with an execution device function cascadethat includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters, providing the functions g.sub.1, . . . , g.sub.N to the executingdevice; and in the executing device, applying the execution device function cascade to the functions g.sub.1, . . . , g.sub.N, wherein the execution of the g.sub.i and h.sub.i functions by the executing device in an interleaved manner enables thefunctionality of the execution device function cascade to be achieved without function f being directly recognizable.
2. A method of providing a digital signal processing function f as claimed in claim 1, wherein the execution device function cascade includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h. sub.N1.smallcircle. . . ..smallcircle.y.sub.1.smallcircle.p.sub.1.sup.1.
3. A method of providing a digital signal processing function f as claimed in claim 1, wherein the function cascade starts with a further signal processing function f.sub.0 and the execution device function cascade includesy.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1.smallcircle.S.sub.1, where S.sub.1 is functionally equivalent to p.sub.1.sup.1.smallcircle.f.sub.0.
4. A method of providing a digital signal processing function f as claimed in claim 1, wherein the execution device function cascade includes p.sub.2N.smallcircle.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1.
5. A method of providing a digital signal processing function f as claimed in claim 1, wherein the function cascade ends with a further signal processing function f.sub.N+1, and the execution device function cascade includesS.sub.2.smallcircle.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.sma llcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1 where S.sub.2 is functionally equivalent to f.sub.N+1.smallcircle.p.sub.2N.
6. A method of providing a digital signal processing function f as claimed in claim 1, including obtaining a unique identity of the executing device and/or user of the executing device; the set and/or sequence of 2N invertible permutationsp.sub.i being unique for the obtained identity.
7. A method as claimed in claim 1, wherein the step of equipping the executing device with the execution device function cascade includes providing the execution device function cascade embedded in a software program for execution by aprocessor in the executing device.
8. A method as claimed in claim 7, wherein the step of providing the functions g.sub.1, . . . g.sub.N to the executing device includes providing the functions g.sub.1, . . . , g.sub.N in the form of a plugin for the program.
9. A method as claimed in claim 7, wherein the step of providing the functions g.sub.1, . . . g.sub.N to the executing device includes embedding the functions g.sub.1, . . . g.sub.N in the software program by applying the execution devicefunction cascade to the function parameters g.sub.1, . . . g.sub.N.
10. A computer program product stored on a nontransitory computer readable storage medium that is operative to cause a processor in an execution device to execute a digital signal processing function f including a function cascade including aplurality of signal processing functions f.sub.i, where 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output, by: performing the following steps by at least one processor of the execution device: loading anexecution device function cascade that includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters, loading a set of functionsg.sub.1, . . . , g.sub.N; applying the execution device function cascade to the set of functions g.sub.1, . . . , g.sub.N; where: g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for1.ltoreq.i.ltoreq.N; h.sub.i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N; and p.sub.i is an invertible permutation, for 1.ltoreq.i.ltoreq.2N.
11. A system for providing a digital signal processing function f to an executing device in an obfuscated form; the system including a server (610) and an executing device (620); the function f including a function cascade including aplurality of signal processing functions f.sub.i, 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output; the server including a processor (612) for performing the following steps, under control of a program:selecting a set of 2N invertible permutations p.sub.i, 1.ltoreq.i.ltoreq.2N; calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N; andcalculating a set of N1 functions h.sub.i, where h.sub.i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N; and means (614) for equipping the executing device with an execution device function cascade thatincludes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters, and means (616) for providing the functions g.sub.1, . . . , g.sub.N tothe executing device; and the executing device (620) including: means (626) for obtaining the functions g.sub.1, . . . , g.sub.N from the server; and a processor (622) for, under control of a program, loading the execution device function cascade andapplying the loaded execution device function cascade to the functions g.sub.1, . . . , g.sub.N, wherein the execution of the g.sub.i and h.sub.i functions by the executing device in an interleaved manner enables the functionality of the executiondevice function cascade to be achieved without function f being directly recognizable.
12. An execution device (620) for use in the system as claimed in claim 11; the executing device including: means (626) for obtaining the functions g.sub.1, . . . , g.sub.N from the server; and a processor (622) for, under control of aprogram, applying the execution device function cascade to the functions g.sub.1, . . . , g.sub.N and applying the applied device function cascade to the digital signal input x.
13. A method of providing a digital signal processing function f to a plurality of executing devices, each identified by a unique index j, in an obfuscated, anonymous form; the function f including a function cascade including a plurality ofsignal processing functions f.sub.i, where 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output the method including: performing the following steps by at least one processor: selecting a set of 2N invertiblepermutations p.sub.i, where 1.ltoreq.i.ltoreq.2N; calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, 1.ltoreq.i.ltoreq.N; selecting for each device j acorresponding set and/or sequence of 2N invertible permutations p.sub.j,i, that is unique for the device and/or a user of the device; calculating for each executing device j a corresponding set of N1 functions h.sub.j,i, where h.sub.j,i is functionallyequivalent to p.sub.j,2i1.sup.1.smallcircle.p.sub.j,2i2 for 2.ltoreq.i.ltoreq.N; equipping each executing device j with a respective execution device function cascade ED.sub.j(y.sub.1, . . . , y.sub.N) that includesy.sub.N.smallcircle.h.sub.j,N.smallcircle.y.sub.N1.smallcircle.h.sub.j,N 1.smallcircle. . . . .smallcircle.y.sub.1; equipping each executing device j with a respective loader function loader.sub.j(x.sub.1, . . . ,x.sub.N)=(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j,1, . . . , l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N), where l.sub.j,i, is functionally equivalent to p.sub.j,2i.sup.1.smallcircle.p.sub.2i and r.sub.j,i is functionally equivalentto p.sub.2i1.sup.1.smallcircle.p.sub.j,2i.sup.1; providing to the executing device the functions g.sub.1, . . . , g.sub.N; and in the executing device, executing ED.sub.j(loader.sub.j(g.sub.1, . . . , g.sub.N)).
14. A method of providing a digital signal processing function f as claimed in claim 13, including providing g.sub.1, . . . , g.sub.N to each executing device through broadcasting and/or distribution on a storage medium with a same content foreach executing device.
15. A method of providing a digital signal processing function f as claimed in claim 14, including also providing the digital signal input x to each executing device through broadcasting and/or distribution on a storage medium with a samecontent for each executing device.
16. A method of providing a digital signal processing function f as claimed in claim 13, including providing to executing device j through a onetoone communication channel and/or a storage medium with a devicespecific content at least onethe following sets of corresponding functions: h.sub.j,i, l.sub.j,i or r.sub.j,i.
17. A method of providing a digital signal processing function f as claimed in claim 1, wherein the function f is a decryption function based on a Feistel cipher network and each of the signal processing functions f.sub.i is a respectiveFeistel decryption round function.
18. A method of providing a digital signal processing function f as claimed in claim 17, wherein each of the permutations p.sub.i is a Feistel transformer where a function Q operating on a sequential pair <x, y> is a Feistel transformerif there exist invertible functions Q.sub.x and Q.sub.y and Q(x, y)=Q.sub.x(x),Q.sub.y(y), where Q.sub.x(x).sym.Q.sub.x(y)=Q.sub.x(x.sym.y) and Q.sub.y(x).sym.Q.sub.y(y)=Q.sub.y(x.sym.y).
19. A computer program product stored on a nontransitory computer readable storage medium that is operative to cause a processor in an execution device j to execute a digital signal processing function f including a function cascade includinga plurality of signal processing functions f.sub.i, where 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output, the method including: performing the following steps by at least one processor of the executiondevice: loading an execution device function cascade that is unique for the execution device and that includes y.sub.N.smallcircle.h.sub.j,N.smallcircle.y.sub.N1.smallcircle.h.sub.j,N 1.smallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . ,y.sub.N are function parameters, loading a loader function loader.sub.j(x.sub.1, . . . , x.sub.N).ident.(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j ,l, . . . , l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N), loading a set of functionsg.sub.1, . . . , g.sub.N; applying the loader function to the set of functions g.sub.1, . . . , g.sub.N yielding a set of functions g.sub.j,1, . . . , g.sub.j,N and applying the execution device function cascade to the set of functions g.sub.j,1, . . . , g.sub.j,N, where: g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N; p.sub.i is an invertible permutation, for 1.ltoreq.i.ltoreq.N; h.sub.j,i is functionally equivalent top.sub.j,2i1.sup.1.smallcircle.p.sub.j,2i2 for 2.ltoreq.i.ltoreq.N; l.sub.j,i is functionally equivalent to p.sub.j,2i.sup.1.smallcircle.p.sub.2i; r.sub.j,i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.j,2i1; and p.sub.j,i areinvertible permutations, for 1.ltoreq.i.ltoreq.2N, being unique for the device and/or a user of the device.
20. A system for providing a digital signal processing function f to a plurality of executing devices, in an obfuscated, anonymous form; the system including a server and a plurality of executing devices, each identified by a unique index j; the function f including a function cascade including a plurality of signal processing functions f.sub.i, where 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output; the server including a processor forperforming the following steps, under control of a program: selecting a set of 2N invertible permutations p.sub.i, where 1.ltoreq.i.ltoreq.2N; calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent top.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N; selecting for each device j a corresponding set and/or sequence of 2N invertible permutations p.sub.j,i, that is unique for the device and/or a user of the device; calculating for each executing device j a corresponding set of N1 functions h.sub.j,i, where h.sub.j,i is functionally equivalent to p.sub.j,2i1.sup.1.smallcircle.p.sub.j,2i2 for 2.ltoreq.i.ltoreq.N; equipping each executing device j with arespective execution device function cascade ED.sub.j(y.sub.1, . . . , y.sub.N) that includes y.sub.N.smallcircle.h.sub.j,N.smallcircle.y.sub.N1.smallcircle.j,h.sub.N 1.smallcircle. . . . .smallcircle.y.sub.1; equipping each executing device j witha respective loader function loader.sub.j(x.sub.1, . . . , x.sub.N)=(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j,1, . . . , l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N), where l.sub.j,i is functionally equivalent top.sub.j,2i.sup.1.smallcircle.p.sub.2i and r.sub.j,i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.j,2i1; and providing to the executing device the functions g.sub.1, . . . , g.sub.N; and each executing device j, means forobtaining the functions g.sub.1, . . . , g.sub.N from the server; and a processor for, under control of a program: loading an execution device function cascade that is unique for the execution device and that includesy.sub.N.smallcircle.j,h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.j,N 1.smallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters, loading a loader function loader.sub.j(x.sub.1, . . . ,x.sub.N).ident.(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j ,1, . . . , l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N) applying the loader function to the set of functions g.sub.1, . . . , g.sub.N yielding a set of functions g.sub.j,1, . . . , g.sub.j,N; and applying the execution device function cascade to the set of functions g.sub.j,1, . . . , g.sub.j,N.
21. An execution device for use in the system as claimed in claim 20; where the executing device is identified by a unique index j; and includes: means for obtaining the functions g.sub.1, . . . , g.sub.N from the server; and a processorfor, under control of a program: loading an execution device function cascade that is unique for the execution device and that includes y.sub.N.smallcircle.h.sub.j,N.smallcircle.y.sub.N1.smallcircle.h.sub.j,N 1.smallcircle. . . ..smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters, loading a loader function loader.sub.j(x.sub.1, . . . , x.sub.N).ident.(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j ,1, . . . ,l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N) applying the loader function to the set of functions g.sub.1, . . . , g.sub.N yielding a set of functions g.sub.j,1, . . . , g.sub.j,N; and applying the execution device function cascade to the setof functions g.sub.j,1, . . . , g.sub.j,N where: g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1 for 1.ltoreq.i.ltoreq.N; p.sub.i is an invertible permutation, for 1.ltoreq.i.ltoreq.N; h.sub.j,i isfunctionally equivalent to p.sub.j,2i1.sup.1.smallcircle.p.sub.j,2i2 for 2.ltoreq.i.ltoreq.N; l.sub.j,i is functionally equivalent to p.sub.j,2i.sup.1.smallcircle.p.sub.2i; r.sub.j,i is functionally equivalent top.sub.2i1.sup.1.smallcircle.p.sub.j,2i1; and p.sub.j,i are invertible permutations, for 1.ltoreq.i.ltoreq.2N, being unique for the device and/or a user of the device. 
Description: 
FIELD OF THE INVENTION
The invention relates to a method of providing a cascaded signal processing function to an execution device in a secure and/or personalized way. The invention also relates to a system for providing a cascaded signal processing function to anexecution device in a secure and/or personalized way. The invention further relates to an execution device for executing a cascaded signal processing function provided in a secure and/or personalized way.
BACKGROUND OF THE INVENTION
The Internet provides users with convenient and ubiquitous access to digital content. Because of the potential of the Internet as a powerful distribution channel, many CE products strive to interoperate with the PC platformthe predominantportal to the Internet. The use of the Internet as a distribution medium for copyrighted content creates the compelling challenge to secure the interests of the content provider. In particular it is required to warrant the copyrights and businessmodels of the content providers. Control of the playback software is one way to enforce the interests of the content owner including the terms and conditions under which the content may be used. In particular for the PC platform, the user must beassumed to have complete control to the hardware and software that provides access to the content and unlimited amount of time and resources to attack and bypass any content protection mechanisms. As a consequence, content providers must deliver contentto legitimate users across a hostile network to a community where not all users can be trusted. The general approach in digital rights management for protected content distributed to PCs is to encrypt the digital content (for instance using DES) and tostore the decryption key (or the "license") in a socalled License database on the PC's hard disk. Digital content on the PC is typically rendered using media players, such as Microsoft's Media Player, Real's RealOne Player, Apple's QuickTime player. Such players can load for a specific content format a respective plugin for performing the formatspecific decoding. Those content formats may include AVI, DV, Motion JPEG, MPEG1, MPEG2, MPEG4, WMV, Audio CD, MP3, WMA, WAV, AIFF/AIFC, AU, etc. Theplayer and plugin structure is illustrated in FIG. 1, where a media player 100 includes a core player 110 and several formatspecific plugins (shown are plugins 120, 122 and 124). The core player 110 may, for example, provide the user interface forcontrolling the player. Each plugin includes a respective decoder. It may send the decoded content directly to rendering HW/SW, such as a soundcard, or pass it on to the core player 110 for further processing. For secure rendering, a secure pluginis used that not only decodes the content in the specific format but also decrypts the content. This is illustrated in FIG. 2, where the encrypted content is first fed through a decryptor 230 and next the decrypted content is fed through theformatspecific decoder 220. The decryptor 230 may receive a decryption key/license from a license database 210.
The largest vulnerability of digital rights management relying on encryption is the key distribution and handling. For playback, a software player has to retrieve a decryption key from the license database, it then has to store this decryptionkey somewhere in memory for the decryption of the encrypted content. This leaves an attacker two options for an attack of the key handling in a software player: firstly, reverse engineering of the license database access function could result in a blackbox software (i.e., the attacker does not have to understand the internal workings of the software function) capable of retrieving asset keys from all license databases. Secondly, by observation of the accesses to memory used during content decryptionit is possible to retrieve the asset key.
Typically digital rights management systems use an encryption technique based on block ciphers that process the data stream in blocks using a sequence of encryption/decryption steps, referred to as rounds. The output of i1.sup.th round is theinput of the i.sup.th round. Thus, for a system with N rounds the algorithm can be described as a function cascade f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x), where function f.sub.i represents the functionality of round i. Most block algorithmsare Feistel networks. In such networks, the input data block x of even length n is divided in two halves of length
##EQU00001## usually referred to as L and R. So, the input x fed to the first round is given as x=L.sub.0,R.sub.0. The i.sup.th round (i>0) performs the function f.sub.i, where f.sub.i is defined asf.sub.i(L.sub.i1,R.sub.i1)=R.sub.i1,(L.sub.i1.sym.F(R.sub.i1,K.sub.i )), K.sub.i is a subkey used in the i.sup.th round and F is an arbitrary round function.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a better protection of cascaded signal processing functions such as Feistel networks.
To meet the object of the invention, a method of providing a digital signal processing function f to an executing device in an obfuscated form, where the function f includes a function cascade including a plurality of signal processing functionsf.sub.i, 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output (for example, FC.sub.1(x).ident.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x)), includes:
selecting a set of 2N invertible permutations p.sub.i, 1.ltoreq.i.ltoreq.2N;
calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N;
calculating a set of N1 functions h.sub.i, where h.sub.i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N;
equipping the executing device with an execution device function cascade that includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N arefunction parameters (for example, ED.sub.1(y.sub.1, . . . , y.sub.N).ident.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcir cle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1),
providing the functions g.sub.1, . . . , g.sub.N to the executing device; and
in the executing device, applying the execution device function cascade to the functions g.sub.1, . . . , g.sub.N (for example, ED.sub.1(g.sub.1, . . . , g.sub.N)).
According to the invention the constituent functions f.sub.i are provided in an encapsulated form as g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N. Thefunctions p.sub.i used for the encapsulation are also hidden by being supplied in the form of h.sub.i which is a multiplied version of p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N. By executing the functions g.sub.i and h.sub.i inthe execution device in an interleaved manner (as for example is illustrated in FIG. 4) the functionality of the function cascade is achieved without f.sub.i being directly recognizable. In particular, if f.sub.i represents a round function of a Feistelcipher, the round key that is embedded in the round function is not directly recognizable. The obfuscated delivery of f.sub.i increases security. The execution function device cascade may form the core functionality of a media player, where the setg.sub.1, . . . , g.sub.N enables the player to execute a function cascade containing f.sub.1 up to and including f.sub.N.
The dependent claims 2 and 3 show two respective alternative embodiments for protecting the (functional) beginning of the function cascade. In the embodiment of claim 2, the execution device function cascade starts with p.sub.1.sup.1, forexample ED.sub.2(y.sub.1, . . . , y.sub.N)=y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h. sub.N1.smallcircle. . . . .smallcircle.y.sub.1.smallcircle.p.sub.1.sup.1. Applying this to g.sub.1, . . . , g.sub.N, gives as a functionalstart of the function sequence executed in the device: . . . .smallcircle.g.sub.2.smallcircle.h.sub.2.smallcircle.g.sub.1.smallcircle. p.sub.1.sup.1= . . . .smallcircle.p.sub.3.sup.1.smallcircle.f.sub.2.smallcircle.p.sub.2.smallcircle.p.sub.2.sup.1.smallcircle.f.sub.1.smallcircle.p.sub.1.smallcircle. p.sub.1.sup.1= . . . .smallcircle.p.sub.3.sup.1.smallcircle.f.sub.2.smallcircle.f.sub.1, in this way the execution device explicitly executes f.sub.1. In the embodiment ofclaim 3, security is increased by extending the function cascade with a starting function f.sub.0 that aids in hiding p.sub.1.sup.1. The function cascade may, for example, be FC.sub.2(x)=f.sub.N.smallcircle. . . ..smallcircle.f.sub.1.smallcircle.f.sub.0(x). The execution device function cascade starts with a function S.sub.1, for example ED.sub.3(y.sub.1, . . . , y.sub.N)=y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h. sub.N1.smallcircle. .. . .smallcircle.y.sub.1.smallcircle.S.sub.1, where S.sub.1 is functionally equivalent to p.sub.1.sup.1.smallcircle.f.sub.0. Since S.sub.1 only represents p.sub.1.sup.1 in a form multiplied with f.sub.0, p.sub.1.sup.1 can not be retrieved from theexecution device in a direct way such as reading certain memory locations. Preferably, f.sub.0 is a global secret.
The dependent claims 4 and 5 show two respective alternative embodiments for protecting the (functionally) ending of the function cascade in a manner analogous to claims 2 and 3
According to the measure of the dependent claim 6, the chosen sequence of permutations p.sub.i is unique for the device. In this way, the function cascade is supplied to the execution device not only in an obfuscated form but also in apersonalized form. For example, if the function cascade represents a Feistel cipher with embedded decryption key, cryptanalytic or brute force attacks may result in obtaining the black box functionality of g.sub.1, . . . , g.sub.N. This brokenfunctionality would then only work in combination with the corresponding execution device function cascade and not with any other execution device. This significantly limits the impact of a successful attack.
According to the measure of the dependent claim 7, the execution device function cascade is embedded in a program, for example in the form of a media player or a plugin for a media player. The execution device is thus provided with secure,personalized software.
According to the measure of the dependent claim 8, the functions g.sub.1, . . . , g.sub.N, form a plugin for the program. If the program itself is a plugin, then the functions g.sub.1, . . . , g.sub.N are in effect a plugin for the plugin.As an alternative, according to the measure of the dependent claim 9, the functions g.sub.1, . . . , g.sub.N may be embedded in the same program as the execution device function cascade.
To meet an object of the invention, a computer program product operative to cause a processor in an execution device to execute a digital signal processing function f including a function cascade including a plurality of signal processingfunctions f.sub.1, where 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output (for example, FC.sub.1(x).ident.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x)), by:
loading an execution device function cascade that includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are function parameters,
loading a set of functions g.sub.1, . . . , g.sub.N;
applying the execution device function cascade to the set of functions g.sub.1, . . . , g.sub.N; where:
g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N;
h.sub.i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2 for 2.ltoreq.i.ltoreq.N; and
p.sub.i is an invertible permutation, for 1.ltoreq.i.ltoreq.2N.
To meet an object of the invention, a method of providing a digital signal processing function f to a plurality of executing devices, each identified by a unique index j, in an obfuscated, anonymous form; the function f including a functioncascade including a plurality of signal processing functions f.sub.i, where 1.ltoreq.i.ltoreq.N, for processing a digital signal input x to yield a digital signal output (for example, FC.sub.1(x).ident.f.sub.N.smallcircle. . . ..smallcircle.f.sub.1(x)), includes:
selecting a set of 2N invertible permutations p.sub.i, where 1.ltoreq.i.ltoreq.2N;
calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N;
selecting for each device j a corresponding set and/or sequence of 2N invertible permutations p.sub.j,i, that is unique for the device and/or a user of the device;
calculating for each executing device j a corresponding set of N1 functions h.sub.j,i, where h.sub.j,i, is functionally equivalent to p.sub.j,2i1.sup.1.smallcircle.p.sub.j,2i2 for 2.ltoreq.i.ltoreq.N;
equipping each executing device j with a respective execution device function cascade ED.sub.j(y.sub.1, . . . , y.sub.N) that includes y.sub.N.smallcircle.h.sub.j,N.smallcircle.y.sub.N1.smallcircle.h.sub.j,N 1.smallcircle. . . ..smallcircle.y.sub.1;
equipping each executing device j with a respective loader function loader.sub.j(x.sub.1, . . . , x.sub.N)=(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j,1, . . . , l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N), where l.sub.j,i isfunctionally equivalent to p.sub.j,2i.sup.1.smallcircle.p.sub.2i and r.sub.j,i is functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.j,2i1;
providing to the executing device the functions g.sub.1, . . . , g.sub.N; and
in the executing device, executing ED.sub.j(loader.sub.j(g.sub.1, . . . , g.sub.N)).
The functions f.sub.i are obfuscated in the form of the functions g.sub.1, . . . , g.sub.N in the same way as described for claim 1. The functions g.sub.1, . . . , g.sub.N are the same for each device and can be seen as corresponding to onedefault/anonymous device. The execution devices are equipped with a device specific ("personalized") execution device cascade. A device specific loader function is used to convert the respective anonymous functions g.sub.i to corresponding devicespecific functions that can be fed to the execution device cascade. The loader function uses conversion functions l.sub.j,i and r.sub.j,i that are based on a set/sequence of permutations p.sub.j,i that are not revealed.
According to the measure of the dependent claim 12, the functions g.sub.i can be supplied to all devices in a same way, for example, using broadcasting or on a storage medium, such as a CDROM or DVD.
These and other aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter.
BRIEF DESCRIPTION OF THE DRAWINGS
In the drawings:
FIG. 1 shows a block diagram of a prior art plugin based decoding;
FIG. 2 shows a block diagram of a prior art based decryption;
FIG. 3 shows a block diagram of a prior art integrated decryption/decoding system;
FIG. 4 shows the obfuscating according to the invention;
FIG. 5 shows a simple example of obfuscation;
FIG. 6 shows a block diagram of a system according to the invention;
FIG. 7 shows a further embodiment of a system according to the invention;
FIG. 8 illustrates anonymous obfuscation according to the invention; and
FIG. 9 illustrates an alternative embodiment for anonymous obfuscation.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
FIG. 3 shows a block diagram of prior art system in which the invention may be employed. In the example of FIG. 3 content (typically Audio and/or video content) is distributed on a medium 310. The medium may be the same for each player. Themedium may be of any suitable type, e.g. audio CD, DVD, solid state, etc. The content on the medium is copy protected, preferably by being encrypted under using an encryption algorithm, such as a Feistel cipher. The storage medium may includeinformation relating the decryption key. Alternatively, the storage medium may include information 312 (such as an identifier) that enables the player to retrieve the information, for example by downloading it from a server in the Internet. Thedecryption key is created in a secure module 320 by using a keyspecific key 322 and the information 312 to calculate 324 the decryption key 326. The decryption key is the received 332 in a second module 330. The second module 330 decrypts 334, decodes336 and renders 338 the content 314 of the medium 310.
FIG. 4 illustrates the method according to the invention. A digital signal processing function f is provided to an executing device in an obfuscated form. The function f includes a function cascade including a plurality of signal processingfunctions f.sub.i, 1.ltoreq.i.ltoreq.N. For example the core of the function cascade may be formed by FC.sub.1(x).ident.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x). It should be noted that here the conventional mathematical notation is used:g.smallcircle.f(x)=g(f(x)). In principle, the function cascade may be any digital signal processing function. In a preferred embodiment, the function cascade includes a cipher. For example, the function f.sub.i may represent the i.sup.th round(i>0) of a Feistel cipher. In such a case, f.sub.i, is defined as: f.sub.i(L.sub.i1.sym.R.sub.i1)=R.sub.i1.sym.(L.sub.i1.sym.F(R.sub.i1 ,K.sub.i)), where K.sub.i is a subkey used in the i.sup.th round and F is an arbitrary round function.
According to the invention, a set of 2N invertible permutations p.sub.i, 1.ltoreq.i.ltoreq.2N is selected. Next, a set of N functions g.sub.i is calculated, where g.sub.i is functionally equivalent top.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N. In this context with functionally equivalent is meant that if g.sub.i is applied to a same input (e.g. x) the same outcome is achieved as whenp.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1 is applied to that input, for each allowed value of the input. The composite functions p.sub.2i.sup.1, f.sub.i, and p.sub.2i1 are not separately visible. g.sub.i provides the black boxfunctionality of p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1. FIG. 5 illustrates this approach for very simple onedimensional functions. In this example,
.function..function..function..function..times..function. ##EQU00002## Thus
.function..function..function..function..function..function. ##EQU00003## It is wellknown from the field of computer compiler building how the black box functionality of p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1 can be achievedusing socalled partial evaluation. Chapter 1 "Partial Evaluation and Automatic Program Generation" by N. D. Jones, C. K. Gomard, and P. Sestoft describes the concept of partial evaluation. This will not be described in more detail here. It will beappreciated that the digital signal input x is a multidimensional parameter, for example of 64 or 128 bit block/vector, to be able to perform a useful permutation. According to the invention, a set of N1 functions h.sub.i is calculated, where h.sub.iis functionally equivalent to p.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N. Using the simple example of FIG. 5, h.sub.2(x)=p.sub.3.sup.1.smallcircle.p.sub.2(x)=3p.sub.2(x);h.sub.3(x)=p.sub.5.sup.1.smallcircle.p.sub.4(x)=p.sub.5.sup.1( {square root over (x)}). Using these definitions, part of the execution device cascade that hides f.sub.2 would be:
.times..times..times..times..times..times..function..function..function..f unction..function..function. ##EQU00004## It can be observed that this is indeed functionally equivalent to p.sub.5.sup.1.smallcircle.f.sub.2.smallcircle.p.sub.2(x). Thus, the executing device that has executed this cascade has executed f.sub.2 without having explicit knowledge of f.sub.2.
In a further example, N=2, and f.sub.1 and f.sub.2 are each evaluated to a respective mapping table given by:
f.sub.1: {0.fwdarw.3, 1.fwdarw.1, 2.fwdarw.6, 3.fwdarw.2, 4.fwdarw.7, 5.fwdarw.5, 6.fwdarw.4, 7.fwdarw.0, 8.fwdarw.8},
f.sub.2: {0.fwdarw.4, 1.fwdarw.1, 2.fwdarw.5, 3.fwdarw.7, 4.fwdarw.6, 5.fwdarw.2, 6.fwdarw.0, 7.fwdarw.8, 8.fwdarw.3}.
In this example, f.sub.1 is an invertible function that converts a number between 0 and 8 to a number between 0 and 8, e.g. value 0 is converted to value 3, value 1 to 1, value 2 to 6, etc. The following four respective permutations are used inthis example:
p.sub.1: {0.fwdarw.5, 1.fwdarw.3, 2.fwdarw.1, 3.fwdarw.7, 4.fwdarw.0, 5.fwdarw.6, 6.fwdarw.2, 7.fwdarw.8, 8.fwdarw.4}
p.sub.2: {0.fwdarw.8, 1.fwdarw.6, 2.fwdarw.7, 3.fwdarw.3, 4.fwdarw.4, 5.fwdarw.2, 6.fwdarw.0, 7.fwdarw.1, 8.fwdarw.5}
p.sub.3: {0.fwdarw.3, 1.fwdarw.5, 2.fwdarw.7, 3.fwdarw.1, 4.fwdarw.6, 5.fwdarw.0, 6.fwdarw.2, 7.fwdarw.8, 8.fwdarw.4}
p.sub.4: {0.fwdarw.3, 1.fwdarw.0, 25, 3.fwdarw.2, 4.fwdarw.7, 5.fwdarw.8, 6.fwdarw.1, 7.fwdarw.4, 8.fwdarw.6}
For this example the following three inverse permutations are used:
p.sub.2.sup.1: {0.fwdarw.6, 1.fwdarw.7, 2.fwdarw.5, 3.fwdarw.3, 4.fwdarw.4, 5.fwdarw.8, 6.fwdarw.1, 7.fwdarw.2, 8.fwdarw.0}
p.sub.3.sup.1: {0.fwdarw.5, 1.fwdarw.3, 2.fwdarw.6, 3.fwdarw.0, 4.fwdarw.8, 5.fwdarw.1, 6.fwdarw.4, 7.fwdarw.2, 8.fwdarw.7}
p.sub.4.sup.1: {0.fwdarw.1, 1.fwdarw.6, 2.fwdarw.3, 3.fwdarw.0, 4.fwdarw.7, 5.fwdarw.2, 6.fwdarw.8, 7.fwdarw.4, 8.fwdarw.5}
Giving these functions, h.sub.2(x)=p.sub.3.sup.1.smallcircle.p.sub.2(x) is then given as:
h.sub.2: {0.fwdarw.7, 1.fwdarw.4, 2.fwdarw.2, 3.fwdarw.0, 4.fwdarw.8, 5.fwdarw.6, 6.fwdarw.5, 7.fwdarw.3, 8.fwdarw.1}.
For example, p.sub.2 maps 0 to 8 and p.sub.3.sup.1 maps 8 to 7. Thus, h.sub.2(0)=p.sub.3.sup.1.smallcircle.p.sub.2(0)=7. Similarly, g.sub.1(x)=p.sub.2.sup.1.smallcircle.f.sub.1.smallcircle.p.sub.1(x) is given by:
g.sub.1: {0.fwdarw.8, 1.fwdarw.5, 2.fwdarw.7, 3.fwdarw.6, 4.fwdarw.3, 5.fwdarw.4, 6.fwdarw.1, 7.fwdarw.0, 8.fwdarw.2}
and g.sub.2(x)=p.sub.4.sup.1.smallcircle.f.sub.2.smallcircle.p.sub.3(x) is given by:
g.sub.2: {0.fwdarw.4, 1.fwdarw.3, 2.fwdarw.5, 36, 4.fwdarw.1, 5.fwdarw.7, 6.fwdarw.2, 7.fwdarw.0, 8.fwdarw.8}
The executing device is equipped with the execution device function cascade that includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1, a where y.sub.1, . . . , y.sub.N arefunction parameters. This is shown in FIG. 4 as a sequence of functions h.sub.N, h.sub.N1, . . . , h.sub.2 410. An exemplary execution device function cascade is ED.sub.1(y.sub.1, . . . ,y.sub.N).ident.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcir cle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1. Furthermore, the functions g.sub.1, . . . , g.sub.N are provided to the executing device. This is shown in FIG. 4 as asequence of functions g.sub.1, g.sub.N1, . . . , g.sub.1 420. In the executing device, the execution device function cascade is applied to the functions g.sub.1, . . . , g.sub.N. This gives, for example, the total signal processing functionED.sub.1(g.sub.1, . . . , g.sub.N) in the executing device. This function can then be applied to the digital signal input x.
Taking a look at a middle part of the chain like h.sub.i+1.smallcircle.g.sub.i.smallcircle.h.sub.i, this gives: h.sub.i+1.smallcircle.g.sub.i.smallcircle.h.sub.i=p.sub.2i+1.sup.1.smallcircle.p.sub.2i.smallcircle.p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircl e.p.sub.2i1.smallcircle.p.sub.2i1.sup..smallcircle.p.sub.2i1=p.sub.2i+ 1.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i2. The first and least term of this expression willbe eliminated by the respective g terms. The total outcome is that the executing device executes a function that includes the function cascade f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x) without having access to any of the functions f.sub.i. These functions are thus obfuscated.
In preferred embodiments, options are given for dealing with the beginning and ending of the chain. Without any further measures, the resulting total signal processing function in the executing device may be ED.sub.1(g.sub.1, . . . ,g.sub.N).ident.p.sub.2N1.sup.1.smallcircle.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x).smallcircle.p.sub.1. For example, the term p.sub.1 can be eliminated by using an execution device function cascade that includesy.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1.smallcircle.p.sub.1.sup.1. For example, ED.sub.2(y.sub.1, . . . ,y.sub.N).ident.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcir cle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1.smallcircle.p.sub.1.sup.1. Preferably, the term p.sub.1.sup.1 is kept secure in the executing device. A preferred way ofdoing this is to extend the function cascade with a further signal processing function f.sub.0, (for example, FC.sub.2(x).ident.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1.smallcircle.f.sub.0(x)). The execution device function cascade then includesy.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . . .smallcircle.y.sub.1.smallcircle.S.sub.1, for example (ED.sub.3(y.sub.1, . . . , y.sub.N).ident.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1.smallcircle.S.sub.1), where S.sub.1 is functionally equivalent to p.sub.1.sup.1.smallcircle.f.sub.0. In this way the individual terms p.sub.1.sup.1 and f.sub.0 need not be revealed, but only themultiplicated form p.sub.1.sup.1.smallcircle.f.sub.0 exists. Preferably, f.sub.0 is a global secret, i.e. known to the parties that need to known it but not distributed any further. Global secrets in itself are known and ways of communicating globalsecretes in a secure way are also known and will not be discussed here any further.
In a corresponding way, measures can be taken for dealing with the term p.sub.2N1.sup.1. For example, the execution device function cascade may include p.sub.2N.smallcircle.y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1 (e.g, ED.sub.4(y.sub.1, . . . , y.sub.N).ident.p.sub.2N.smallcircle.y.sub.N.smallcircle.h.sub.N.smallcirc le.y.sub.N1.smallcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1). To better protect p.sub.2N, the function cascade may end with a further signal processing function f.sub.N+1, (for example, FC.sub.3(x).ident.f.sub.N+1.smallcircle.f.sub.N.smallcircle. . . . .smallcircle.f.sub.1(x)). The execution device functioncascade then includes S.sub.2.smallcircle.y.sub.N.smallcircle.h.sub.N.smallcircle.y.su b.N1.smallcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1 (e.g., ED.sub.5(y.sub.1, . . . ,y.sub.N).ident.S.sub.2.smallcircle.y.sub.N.smallcircle.h.sub.N.smallcircl e.y.sub.N1.smallcircle.h.sub.N1.smallcircle. . . . .smallcircle.y.sub.1), where S.sub.2 is functionally equivalent to f.sub.N+1.smallcircle.p.sub.2N.
FIG. 6 illustrates a system in which the invention may be employed. The system 600 includes a server 610 and at least one executing device 620. The server may be implemented on a conventional computer platform, for example on a platform used asa server, such as a web server, or file server. The server includes a processor 612. The processor 612 is operated under control of a program. The program may be permanently embedded in the processor in an embedded storage, like embedded ROM, but mayalso be loaded from a background storage, such as a hard disk (not shown). Under control of the program, the processor 612: selects the set of 2N invertible permutations p.sub.i, 1.ltoreq.i.ltoreq.2N; calculates the set of N functions g.sub.i, whereg.sub.i is functionally equivalent to p.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N; and calculates the set of N1 functions h.sub.i, where h.sub.i is functionally equivalent top.sub.2i1.sup.1.smallcircle.p.sub.2i2, for 2.ltoreq.i.ltoreq.N. The permutations may be selected (e.g. randomly or pseudorandomly) chosen from a very large set of permutations that may be stored in a (preferably secure) storage (not shown). Theserver may also use a suitable program to generate the permutations. It is wellknown how to create invertible permutations and this will not be described here any further.
Additionally, the server includes means 614 for equipping the executing device with an execution device function cascade that includes y.sub.N.smallcircle.h.sub.N.smallcircle.y.sub.N1.smallcircle.h.sub.N1.s mallcircle. . . ..smallcircle.y.sub.1, where y.sub.1, . . . , y.sub.N are the function parameters. The server may do this in any suitable form. For example, in a factory the terms h.sub.i may be stored in a storage module of the executing device during themanufacturing of the executing device 620. FIG. 6 shows that the terms are downloaded through the Internet 630 directly to the executing device 620. The server 610 also includes means 616 for providing the functions g.sub.1, . . . , g.sub.N to theexecuting device 620. The functions g.sub.i incorporate the respective functions f.sub.i. The functions f.sub.i may be chosen specifically for the digital signal input x. For example, each video title may be encrypted with a corresponding encryptionfunction (e.g. using a same cipher but with a content specific key). To this end, the server 610 may also include the software for controlling the processor 612 to encrypt the content 640 and supply the encrypted content 642 to a distribution medium,e.g. for distribution on a storage medium or through a communication medium like the Internet.
The executing device 620 includes means 626 for obtaining the functions g.sub.1, . . . , g.sub.N from the server 610. These means cooperate with the means 616 of the server and will not be described further. The executing device 620 furtherincludes a processor 622. The processor may be of any suitable type, such as a processor known from personal computers or an embedded microcontroller. The processor 622 is operated under control of a program. The program may be permanently embedded inthe processor 622 using an embedded storage, like embedded ROM, but may also be loaded from a background storage, such as a hard disk (not shown). Under control of the program, the processor 622 loads the execution device function cascade and appliesthe loaded execution device function cascade to the functions g.sub.1, . . . , g.sub.N, for example by executing ED.sub.1(g.sub.1, . . . , g.sub.N). The resulting signal processing function may then be applied to the signal input x (e.g. contentreceived from a medium). The processor 622 may load the execution device function cascade in any suitable form. For example, the cascade may have been prestored during manufacturing in a storage, reducing the loading to a straightforward memory readaccess. In the example of FIG. 6, the executing device 620 includes means 624 for retrieving the cascade (or the terms of the cascade), for example, through the Internet 630 or from the medium 650. Similarly, the executing device 620 may retrieveencrypted content 652 from the medium 650, and decrypt this using the processor 622. The processor may also decode the decrypted content.
FIG. 7 shows a preferred embodiment wherein the execution device function cascade is provided to the executing device 620 embedded in a software program 710 for execution by the processor 622. Same numbers in FIG. 7 refers to the same items asused in FIG. 6. The software program 710 may be a plugin for a program like a media player. Thus, the means 614 of FIG. 7 may supply this plugin 710 via the Internet (e.g. item 630 of FIG. 7) or embed it directly into the executing device 620 duringmanufacturing.
In an embodiment, the functions g.sub.1, . . . , g.sub.N are supplied to the executing device 620 in the form of a plugin for the program 710. In the case where the program 710 is already a plugin, the functions g.sub.1, . . . , g.sub.N areeffectively a plugin for a plugin. Alternatively, the functions g.sub.1, . . . , g.sub.N are provided to the executing device 620 by embedding the functions g.sub.1, . . . , g.sub.N in the software program 710 by applying the execution devicefunction cascade to the function parameters g.sub.1, . . . , g.sub.N. In this way, the program 710 embeds both the functions h.sub.i and g.sub.i.
In an embodiment, each executing device and/or user of the executing device is unique and identified by a unique identity (e.g., a unique number j). In the system and method according to the invention, it is ensured that the sequences g.sub.iand h.sub.i are unique for the involved party. This can be achieved by obtaining the unique identity j of the executing device and/or user of the executing device a respective set of 2N invertible permutations p.sub.i that is unique for the obtainedidentity. Similarly, using the same set of permutations, a unique sequence of the permutations may be chosen. Both techniques (choosing a different set of permutations or a different sequence of permutations) may be combined. Preferably, the serverstores (in a secure way) the unique set/sequence for each unique identity. In this way, each software media player in a personal computer can be supplied with a unique plugin for decrypting and/or decoding a media title. The medium it self need not beunique. The encrypted content only depends on the encryption functions, not on the unique set/sequence of permutations. By regularly (e.g. at startup of the media player) checking whether the software corresponds to the identity and only executing thesoftware if a match can be established it can be ensured that no player software can be executed on a PC to which it does not belong. If inadvertently a hacker manages to obtain the devicespecific permutations they can only be used on the involved PC,possible also for content protected with a different encryption (resulting in different functions f.sub.i), but not on different platforms.
Above a method and system have been described wherein a signal processing function cascade is supplied to executing devices in an obfuscated way. For each device the same set/sequence of permutations may be used or a devicespecific set/sequencemay be used. In the remainder an preferred approach is described for achieving a devicespecific set/sequence by distributing the signal function cascade (`key`) in an obfuscated way that is the same for each device and using a conversion routine(`loader`) that converts the common key to a devicespecific key. The `common key` is created in much the same way as described before. The common key can in principle `unlock` a reference player or anonymous player that, however, in this embodiment isnot executed by any actual executing device. As before, the method includes selecting a set of 2N invertible permutations p.sub.i, where 1.ltoreq.i.ltoreq.2N and calculating a set of N functions g.sub.i, where g.sub.i is functionally equivalent top.sub.2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.2i1, for 1.ltoreq.i.ltoreq.N. Now additionally, the method includes selecting for each executing device, each identified by a unique index j, a corresponding set and/or sequence of 2N invertiblepermutations p.sub.j,i, that is unique for the device and/or a user of the device. This set is used to provide each device a unique `player`. This unique player is formed by calculating for each executing device j a corresponding set of N1 functionsh.sub.j,i, where h.sub.j,i is functionally equivalent to p.sub.j,2i1.sup.1.smallcircle.p.sub.j,2i2 for 2.ltoreq.i.ltoreq.N and equipping each executing device j with a respective execution device function cascade ED.sub.j(y.sub.1, . . . , y.sub.N)that includes y.sub.N.smallcircle.h.sub.j,N.smallcircle.y.sub.N1.smallcircle.h.sub.j,N 1.smallcircle. . . . .smallcircle.y.sub.1. This devicespecific set h.sub.j,i, however, does not match the obfuscated function cascade, that can `unlock` areference player that uses set h.sub.i. This latter set/player set is not made available to any executing device. Instead, the executing device j is equipped with a respective loader function loader.sub.j(x.sub.1, . . . ,x.sub.N)=(l.sub.j,1.smallcircle.x.sub.1.smallcircle.r.sub.j,1, . . . , l.sub.j,N.smallcircle.x.sub.N.smallcircle.r.sub.j,N), where l.sub.j,i is functionally equivalent to p.sub.j,2i.sup.1.smallcircle.p.sub.2i and r.sub.j,i is functionally equivalent top.sub.2i1.sup.1.smallcircle.p.sub.j,2i1. As before, each executing device is provided with the same functions g.sub.1, . . . , g.sub.N. The executing device then executes ED.sub.j(loader.sub.j(g.sub.1, . . . , g.sub.N)). In this formulaloader.sub.j(g.sub.1, . . . , g.sub.N) effectively converts the anonymous key g.sub.1, . . . , g.sub.N into a devicespecific key that optimally matches the execution device function cascade ED.sub.j(y.sub.1, . . . , y.sub.N). Using the definitionthat loader.sub.j(g.sub.1, . . . , g.sub.N)=(g.sub.j,1, g.sub.j,2, . . . , g.sub.j,N), the ith component of loader.sub.j(g.sub.1, . . . , g.sub.N) is g.sub.j,i=l.sub.j,i.smallcircle.g.sub.i.smallcircle.r.sub.j,i. Using the definitions given above,this gives g.sub.j,i=p.sub.j,2i.sup.1.smallcircle.p.sub.2i.smallcircle.p.sub.2i.sup .1.smallcircle.f.sub.i.smallcircle.p.sub.2i1.smallcircle.p.sub.2i1.sup. 1.smallcircle.p.sub.j,2i1, that can be rewritten asg.sub.j,i=p.sub.j,2i.sup.1.smallcircle.f.sub.i.smallcircle.p.sub.j,2i1. This is the same as using a devicespecific set/sequence of permutations, where the devicespecific set h.sub.j,i eliminates the permutations.
The concept of using an anonymous obfuscated key and a devicespecific loader is also illustrated in FIG. 8. The anonymous player PlR 810 incorporates the functions h.sub.i. The anonymous player PlR can be unlocked by the corresponding keyKR 812 that includes the obfuscated signal processing functions f.sub.i in the form of the set g.sub.i. The anonymous player PlR is not disclosed to any party. Each party is instead provided with a unique, devicespecific player, shown are playersPl1 830 and Pl2 840. The common key KR is provided to all parties. However, this common key does not match the specific players. Therefore, each party is also provided with a devicespecific key loader KL, shown are 820 and 825. The loader 820,825 is used to convert the anonymous key KR 812 into a devicespecific key Kj. To this end, loader KL.sub.i includes the functions l.sub.j,i and r.sub.j,i. As is shown in FIG. 8, in principle, a devicespecific loader is used. As is furtherillustrated in FIG. 9, in fact, the loader may be the same, but fed with the devicespecific functions l.sub.j,i and r.sub.j,i. In the example of FIG. 9, being fed with l.sub.1,i and r.sub.1,i converts the anonymous key KR 812 into the device specifickey 832 for device 1; being fed with l.sub.2,i and r.sub.2,i converts the anonymous key 812 into the key 842 for device 2. The devicespecific players 830, 840 are then unlocked using the devicespecific key sets h.sub.1,i, 832 and 842, respectively. It will be appreciated that in these examples, the phrase `key` and `player` is interchangeable since two chains of functions interlock. The example of FIG. 4 illustrates both chains as keys. In an analogous way, it could also be illustrated as twointerlocking players.
It will now be understood that the anonymous player 810 (incorporating g.sub.N, . . . , g.sub.1) may advantageously be provided to each executing device through broadcasting and/or distribution on a storage medium with a same content for eachexecuting device, simply because this player is the same for each device. Similarly, the digital signal input x to be processed by each executing device can be distributed through broadcasting and/or distribution on a storage medium with a same contentfor each executing device. The loaderspecific aspects are preferably provided to executing device j through a `onetoone communication channel` and/or a storage medium with a devicespecific content with at least one the following sets ofcorresponding functions: h.sub.j,i, l.sub.j,i, or r.sub.j,i. The `onetoone communication channel` may be achieved in any suitable way. Preferably, the server downloads the devicespecific information via a secure link (e.g. SSL) using Internet.
As described above, the function f may be a decryption function based on a Feistel cipher network and each of the signal processing functions f.sub.i is a respective Feistel decryption round function. In such a case, each of the permutationsp.sub.i is preferably a Feistel transformer where a function Q operating on a sequential pair <x, y> is a Feistel transformer if there exist invertible functions Q.sub.x and Q.sub.y and Q(x,y)=Q.sub.x(x),Q.sub.y(y), whereQ.sub.x(x).sym.Q.sub.x(y)=Q.sub.x(x.sym.y) and Q.sub.y(x).sym.Q.sub.y(y)=Q.sub.y(x.sym.y). If these conditions are met, the functions f.sub.i can be optimally hidden. In practice, it can be shown that many such Feistel transformers exist, giving ampleroom for devicespecific choices of permutations. The definition of the Feistel transformer is based on the insight that using the definitions given above a Feistel round f.sub.i(L.sub.i1,R.sub.i1)=R.sub.i1,(L.sub.i1.sym.F(R.sub.i1,K.sub.i )) canbe seen as f.sub.i=swap.smallcircle.involutary.sub.F, with the definitions swap(x,y)=swap(y,x) and involutary.sub.F(x,y)=x,y.sym.F(x). It then holds that swap.sup.1=swap and involutary.sub.F.sup.1=involutary.sub.F.
It will be appreciated that the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a codeintermediate source and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention. The carrier be any entity or device capable of carrying the program. For example,the carrier may include a storage medium, such as a ROM, for example a CD ROM or a semiconductor ROM, or a magnetic recording medium, for example a floppy disc or hard disk. Further the carrier may be a transmissible carrier such as an electrical oroptical signal that may be conveyed via electrical or optical cable or by radio or other means. When the program is embodied in such a signal, the carrier may be constituted by such cable or other device or means. Alternatively, the carrier may be anintegrated circuit in which the program is embedded, the integrated circuit being adapted for performing, or for use in the performance of, the relevant method.
It should be noted that the abovementioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. Inthe claims, any reference signs placed between parentheses shall not be construed as limiting the claim. Use of the verb "comprise" and its conjugations does not exclude the presence of elements or steps other than those stated in a claim. The article"a" or "an" preceding an element does not exclude the presence of a plurality of such elements. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the deviceclaim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measurescannot be used to advantage.
* * * * * 


