G GM MD Repor D Reportt 41 GMD ­ Forschungszentrum Informationstechnik Jana Dittmann, Petra Wohlmacher, GmbH Patrick Horster, Ralf Steinmetz (Eds.) Multimedia and Security Workshop at ACM Multimedia `98 Bristol, U.K. September 12 -13, 1998 October 1998 © GMD 1998 GMD ­ Forschungszentrum Informationstechnik GmbH Schloß Birlinghoven D-53754 Sankt Augustin Germany Telefon +49 -2241 -14 -0 Telefax +49 -2241 -14 -2618 http://www.gmd.de In der Reihe GMD Report werden Forschungs- und Entwicklungs- ergebnisse aus der GMD zum wissenschaftlichen, nichtkommerziellen Gebrauch veröffentlicht. Jegliche Inhaltsänderung des Dokuments sowie die entgeltliche Weitergabe sind verboten. The purpose of the GMD Report is the dissemination of research work for scientific non-commercial use. The commercial distribution of this document is prohibited, as is any modification of its content. The Workshop was supported by Patrick Horster and Petra Wohlmacher, University of Klagenfurt, Austria Anschriften der Herausgeber/Addresses of the editors: Patrick Horster Petra Wohlmacher Institut für Informatik - Systemsicherheit Universität Klagenfurt Villacher Straße 161 A-9020 Klagenfurt E-mail: petra@ifi.uni-klu.ac.at pho@ifi.uni-klu.ac.at Jana Dittmann Ralf Steinmetz Institut für Integrierte Publikations- und Informationssysteme GMD ­ Forschungszentrum Informationstechnik GmbH Dolivostraße 15 D-64293 Darmstadt E-mail: Jana.Dittmann@gmd.de Ralf.Steinmetz@gmd.de ISSN 1435-2702 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 3 Multimedia and Security Workshop at ACM Multimedia Recently security has certainly become one of the most significant and challenging problems for spreading new information technology. Digital data can easily be copied and multiplied without information loss. This requires security solutions for such fields as distributed pro- duction processes and electronic commerce, since the producers seek to provide access con- trol mechanisms to prevent misuse and theft of material. The first ACM workshop on "Multimedia and Security" took place in conjunction with the ACM Multimedia'98 in Bristol, U.K., September the 12th. We focused on the analysis of spe- cific security problems of multimedia systems and multimedia material in the digital envi- ronment. The objective was to bring together experienced researchers, developers, and practitioners from academia and industry for a state of the art evaluation and discussions of topics and problems for multimedia security environments for the next century. The workshop reflects the strength and weaknesses of what the multimedia community has to offer to meet the needs of secure multimedia environments. Beside technical approaches legal requirements for secu- rity solutions are further topics. The workshop provided space for intensive discussions among the addressed problems of security in and with multimedia. The proceedings show cur- rent solutions and still open problems which must be addressed in the near future. A major field of the discussion was the identification of acceptance problems to use distrib- uted multimedia production systems in digital marketplaces. Solutions for confidential trans- mission, authentication of original, copyright protection and Try&Buy transactions were ad- dressed. As a main result the discussion in the workshop shows the need for a flexible and open watermarking environment for embedding robust watermarks. We would like to take the opportunity to thank the presentators for the excellent talks and the participants for the inten- sive discussions. We understand that the interest and importance of security is reflected in the great number of participants in Bristol. We could claim a very international community and had a wide range of highly interesting topics. Due to the excellent feedback of the participants and the engage- ment in the preparation this was certainly one of the best international workshops in the mul- timedia-security area. Based on these excellent experiences we are planning the next work- shop on Multimedia and Security at the ACM Multimedia '99 to continue the discussion and especially to see the advantages in digital watermarking, the robustness and the practical us- age. Additionally in the '99 event we want to address the topic, that existing multimedia security mechanisms are not realised by using multimedia tools applying security. Thus the discussion is extend to the use of multimedia to perform security. Though security is recognised as an important issue in multimedia it is, ironically, mostly not presented by the new media. Usu- ally, security algorithms are seen as background processes, invisible to the user. Based on the discussions on security in multimedia environments we want to analyse interactive multime- dia tools which strengthen the producers acceptance to use available security features. Jana Dittmann Ralf Steinmetz Workshop CoChair Conference CoChair Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 4 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 5 Contents P. Wohlmacher:Requirements and Mechanisms of IT-Security Including Aspects of Multimedia Security............................................................................. 11 1 Introduction .............................................................................................................................................11 2 Requirements and Measures...................................................................................................................11 3 Cryptographic Mechanisms....................................................................................................................12 4 Confidentiality .........................................................................................................................................12 4.1 Session-Key Scheme .........................................................................................................................12 5 Data Integrity................................................................................................................ ...........................12 6 Data Origin Authenticity ........................................................................................................................13 6.1 Message Authentication Code ...........................................................................................................13 6.2 Digital Signatures ..............................................................................................................................14 7 Entity Authenticity ..................................................................................................................................15 8 Non-Repudiation......................................................................................................................................16 9 Public-Key Infrastructure.......................................................................................................................17 10 Security for Multimedia ..........................................................................................................................17 11 References.................................................................................................................................................18 A. Miedbrodt:The Functions of Digital Signatures from a Legal Point of View. 21 1 Introduction .............................................................................................................................................21 2 How are the digital signatures embedded in the German legal system?.............................................22 2.1 Writing Form .....................................................................................................................................22 2.2 Evidence Law ....................................................................................................................................22 3 The German Digital Signature Law.......................................................................................................22 3.1 Requirements for the Keys ................................................................................................................23 3.2 Requirements for the Procedure of Establishment and Testing the Signatures..................................24 3.3 Requirements For The Services Performed By The Certification Authorities...................................25 4 Acknowledgments....................................................................................................................................28 5 References.................................................................................................................................................28 U. Kohl: Secure Container Technology as a Basis for Cryptographically Secured Multimedia Communication.................................................................... 29 1 Introduction .............................................................................................................................................29 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 6 2 Multimedia Security Requirements .......................................................................................................29 3 Internet Security Mechanisms................................................................................................................30 3.1 Building Blocks Of Security Solutions..............................................................................................30 3.2 Securing Connections ........................................................................................................................31 4 Protection on the Document Level .........................................................................................................33 5 Summary ..................................................................................................................................................34 6 Acknowledgments....................................................................................................................................34 7 References.................................................................................................................................................34 C. Griwodz: Video Protection by Partial Content Corruption ............................. 37 1 Protecting the Cache ...............................................................................................................................37 2 Protecting the Delivered Video...............................................................................................................39 3 Conclusion ................................................................................................................................................39 4 References.................................................................................................................................................39 Th. Kunkelmann: Applying Encryption to Video Communication...................... 41 1 Introduction .............................................................................................................................................41 2 Multimedia Data and Encryption ..........................................................................................................41 2.1 Data Formats For Video Transmission..............................................................................................41 2.2 Performance Aspects For Encrypted Video.......................................................................................42 2.3 Integration Of Security Functionalities In The System......................................................................42 3 Partial Video Cryption Methods ............................................................................................................43 3.1 SEC-MPEG .......................................................................................................................................43 3.2 Partial Encryption Of Intracoded Frames ..........................................................................................43 3.3 Permutation Of DCT Block Information ...........................................................................................43 3.4 Reducing The Amount For Strong Encryption..................................................................................43 Scalable Method For JPEG-Based Video..........................................................................................................44 4 Evaluation of Results...............................................................................................................................44 4.1 Possible Reconstruction Of Protected Data .......................................................................................44 4.2 Experimental Results .........................................................................................................................44 4.3 Comparison Of The Encryption Methods..........................................................................................44 5 Encryption of Scalable Video Streams...................................................................................................45 5.1 Scalable Video Coding With A Spatial Resolution Pyramid.............................................................45 5.2 Partial Video Encryption ...................................................................................................................45 Partial Encryption Results For Mpeg-1 And The Scalable Codec.....................................................................46 6 Conclusions...............................................................................................................................................46 7 Literature .................................................................................................................................................47 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 7 Ching-Yung Lin and Shih-Fu Chang:Generating Robust Digital Signature for Image/Video Authentication................................................................................... 49 1 Introduction .............................................................................................................................................49 Image Authentication System.............................................................................................................................50 3 Signature Generation ..............................................................................................................................50 4 Authentication Process............................................................................................................................51 5 Performance Enhancement.....................................................................................................................51 5.1 Tolerance Bound For Recompressing Noise ..................................................................................... 51 Multi-Layer Feature Codes................................................................................................................................51 6 Robustness................................................................................................................................................51 7 Experimental Results...............................................................................................................................52 8 Video Authentication System..................................................................................................................53 9 Conclusion ................................................................................................................................................53 10 References.................................................................................................................................................53 F. Petitcolas, R. J. Anderson: Weaknesses of Copyright Marking Systems ..... 55 1 Introduction .............................................................................................................................................55 2 Copyright marks......................................................................................................................................55 3 Attacks......................................................................................................................................................56 3.1 The Jitter Attack ................................................................................................................................56 3.2 Stirmark .............................................................................................................................................56 3.3 The Mosaic Attack.............................................................................................................................57 3.4 A General Attack On Audio Marking................................................................................................57 3.5 Attack On Echo Hiding......................................................................................................................58 3.6 Protocol Considerations.....................................................................................................................59 3.7 Implementation Considerations .........................................................................................................59 3.8 Robustness Against Insiders ..............................................................................................................59 4 Conclusion ................................................................................................................................................60 5 Acknowledments......................................................................................................................................60 6 References.................................................................................................................................................60 Mitchell D. Swanson, Bin Zhu, and Ahmed H. Tewfik: Audio Watermarking and Data Embedding - Current State of the Art, Challenges and Future Directions - .................................................................................................................................. 63 1 Introduction .............................................................................................................................................63 2 Data Embedding Requirements .............................................................................................................64 2.1 Perceptual Transparency....................................................................................................................64 2.2 Recovery Of Data With Or Without Access To Original Signal .......................................................64 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 8 2.3 Bit Rate Of Data Embedding Algorithm............................................................................................64 2.4 Robustness.........................................................................................................................................64 2.5 Security..............................................................................................................................................65 2.6 Copyright Protection And Ownership Deadlock ...............................................................................65 3 Signal Insertion: The Role Of Masking .................................................................................................65 4 The Human Auditory System .................................................................................................................65 5 Previous Audio Work..............................................................................................................................66 6 Current Research.....................................................................................................................................66 7 Future Directions.....................................................................................................................................68 8 References.................................................................................................................................................68 M.t L. Miller, I. J. Cox, J. A Bloom : Watermarking in the Real World: An Application to DVD ................................................................................................. 71 1 Introduction .............................................................................................................................................71 2 Application Framework ­ DVD Copy Protection System....................................................................71 3 Challenges.................................................................................................................................................74 4 Conclusion ................................................................................................................................................76 5 References.................................................................................................................................................76 F. Hartung, J. K. Su , B. Girod: Digital Watermarking for Compressed Video... 77 1 Introduction .............................................................................................................................................77 2 Digital watermarking ..............................................................................................................................78 2.1 Requirements.....................................................................................................................................78 3 Digital watermarking of compressed video ...........................................................................................78 3.1 Principle.............................................................................................................................................78 3.2 Properties Of The Proposed Method .................................................................................................78 4 References.................................................................................................................................................79 T. Abe, H. Fujii, Y. Takashima: Image Distribution with Scrambling and Watermarking.......................................................................................................... 81 1 Introduction .............................................................................................................................................81 2 Image Distribution...................................................................................................................................81 3 Protocol...................................................................................................................... ...............................81 4 Constituent technique..............................................................................................................................82 4.1 Scrambling.........................................................................................................................................82 4.2 Watermarking ................................................................................................................ ....................82 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 9 5 Implementation........................................................................................................................................82 6 Summary ..................................................................................................................................................82 7 References.................................................................................................................................................82 R. Ohbuchi, H. Masuda, M. Aono: Watermarking Multiple Object Types in Three- Dimensional Models ............................................................................................... 83 1 Introduction .............................................................................................................................................83 1.1 Data Embedding Classifications........................................................................................................83 2 Embedding Target Objects In 3d Models..............................................................................................84 3 Embedding Algorithms For 3D Polygonal Meshes...............................................................................85 3.1 An Algorithm Based On Geometrical Quantity Modification...........................................................86 An Algorithm Based On Topological Modification ..........................................................................................87 3.3 An Algorithm Based On Shape Attribute Modification ....................................................................88 4 Summary And Future Work ..................................................................................................................90 5 REFERENCES ........................................................................................................................................90 K. Nahrstedt, L. Qiao: Non-Invertible Watermarking Methods for MPEG Video and Audio*............................................................................................................... 93 1 Introduction .............................................................................................................................................93 2 Rightful Ownership and Non-invertibility Problem.............................................................................93 3 Non-invertible Scheme for MPEG Video ..............................................................................................94 3.1 Watermark Construction....................................................................................................................94 3.2 Watermark Embedding Procedure.....................................................................................................95 3.3 Verification Process...........................................................................................................................96 3.4 Discussion..........................................................................................................................................96 4 Non-invertible Scheme for MPEG Audio ..............................................................................................96 4.1 Watermark Construction....................................................................................................................96 4.2 Watermark Embedding Procedures ...................................................................................................96 5 Conclusion ................................................................................................................................................98 6 References.................................................................................................................................................98 A. Herrigel, S. Voloshynovskiy: Copyright and Content Protection for Digital Images based on Asymmetric Cryptographic Techniques................................. 99 1 Introduction .............................................................................................................................................99 2 Definitions...............................................................................................................................................100 3 Security Requirements ..........................................................................................................................101 4 Security Architecture ............................................................................................................................101 4.1 Symbols ..................................................................................................................... ......................102 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 10 4.2 Registration Based Copyright And Content Protection ...................................................................102 4.3 Content Protection ...........................................................................................................................104 4.4 Remarks...........................................................................................................................................104 5 Implementation......................................................................................................................................105 5.1 The Copyright Holder Application Process.....................................................................................105 5.2 The Copyright Certificate Center Application Process....................................................................105 5.3 The Buyer Application Process .......................................................................................................105 5.4 The Public Key Infrastructure..........................................................................................................105 5.5 Example...........................................................................................................................................106 6 Conclusions and Future Work..............................................................................................................106 7 Acknowledgments..................................................................................................................................107 8 References...............................................................................................................................................107 9 Annex......................................................................................................................................................109 J. Dittmann, M. Stabenau, R. Steinmetz: Robust MPEG Video Watermarking Technologies ........................................................................................................ 113 1 Motivation .................................................................................................................... ..........................113 2 Digital Watermarking ...........................................................................................................................114 2.1 Requirements For MPEG Video Watermarking..............................................................................114 3 The Zhao Koch Algorithm....................................................................................................................114 4 The Fridrich-Algorithm ........................................................................................................................115 5 Experimental System - MPEG Watermarking ...................................................................................115 5.1 Approach I in the DCT Domain.......................................................................................................115 5.2 Approach II In The Spatial Domain.................................................................................................118 5.3 Problems In The Experimental Systems ..........................................................................................121 6 Applicability for Object Watermarking ..............................................................................................121 7 Conclusions.............................................................................................................................................121 8 References...............................................................................................................................................122 E. Delp: Watermarking: Who Cares? Does it Work? ......................................... 123 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 11 Requirements and Mechanisms of IT-Security Including Aspects of Multimedia Security Petra Wohlmacher University of Klagenfurt Villacher Str. 161 A-9020 Klagenfurt 0043-463-2700854 petra@ifi.uni-klu.ac.at ABSTRACT curity criteria within different classifications regard- ing the following basic threats: In this paper we describe the most important * threat of confidentiality (unauthorised revealing security requirements, which must be ful- of information), filled by today's IT-systems, and the security * threat of integrity (unauthorised modification of measures used to satisfy these requirements. information), These security measures are based on mod- * threat of availability (unauthorised withholding ern cryptographic mechanisms as well as on of information or resources). security infrastructures. From these threats we may derive the basic require- Regarding data security and communication ments for the security of a given IT-system. Security security in particular in the field of multime- requirements are met by security measures, which dia, the requirements on security increase. If generally consist of several security mechanisms. Se- and in which way the discussed security curity services can be made available by security mechanisms can be applied to multimedia se- mechanisms. Secure and trustworthy actions and interactions are curity is difficult to analyse. This is mainly important requirements for multimedia within the due to the complexity of multimedia data and digitised world, too. Whether or not a multimedia their applications. This paper introduces the application fulfils these requirements will have a main issues of IT-security and represents the substantial influence on the acceptance of this rela- basis for solutions of security problems in the tively new medium. field of multimedia. The remainder of this paper deals with the most im- KEYWORDS portant security requirements of today's IT-systems. Additionally, security measures and security mecha- Security requirements, security measures, security nisms, which are fulfilling these requirements, are mechanisms, multimedia, confidentiality, integrity, discussed. The presented requirements and measures authenticity, non-repudiation, session key, one-way may constitute the elementary basis for solutions of hash function, trapdoor one-way hash function, mes- security problems of multimedia. sage authentication code, digital signature, authenti- cation protocol, challenge-response protocol, security 2 Requirements and Measures infrastructure, trust center, public key infrastructure, The following security requirements are essential for originality. IT-systems. They are met by the succeeding security 1 Introduction measures: * Confidentiality: Cipher systems are used to keep IT-systems play an essential role in all areas of to- information secret from unauthorised entities. day's information community. By increasing the re- * quirements for efficiency and the possibilities of IT- Data integrity: The alteration of data can be de- tected by means of one-way hash functions, mes- systems the needs for security and trustworthiness sage authentication codes and digital signatures. also increase. These needs are particularly important for security-relevant applications as well as for appli- * Data origin authenticity: Message authentication cations processing sensitive personal data. codes and digital signatures enable the proof of In order to assess the trustworthiness of IT-systems, origin (and integrity) of data. world-wide catalogues for security criteria have been * Entity authenticity: Entities taking part in a published [2, 8, 16, 17, 19]. One of the most impor- communication, can be proven by authentication tant ones is the Europe-wide valid ITSEC catalogue protocols. These protocols ensure that an entity of criteria [8], which contains criteria for evaluating is the one it claims to be. the security of IT-systems. This catalogue defines se- * Non-repudiation: Non-repudiation mechanisms prove to involved parties and third parties Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 12 whether or not a particular event occurred or a 4.1 Session-Key Scheme particular action happened. The event or action In consideration of performance1 large amounts of can be the generation of a message, the sending data are enciphered by a session-key scheme. This of a message, the receipt of a message and the scheme applies both a private-key and a public-key submission or transport of a message. Non- cryptosystem to an encryption scheme (see figure 1, repudiation certificates, non-repudiation tokens, x||y defines the concatenation of x and y). and protocols establish the accountability of in- formation. The mechanisms are based on mes- U ser A: plaintext m (Sender) c := f(K ,m ) c := g(PK B ,K ) c || c m K m K sage authentication codes or digital signatures combined with notary services, timestamping services and evidence recording. The security measures above mentioned use crypto- U ser B : plaintext m m := f -1(K ,c ) K := g-1(SK B ,c ) c || c graphic mechanisms which we will explain in the (R eceiver) m K m K next section. Figure 1: Session-key scheme 3 Cryptographic Mechanisms Plaintext m shall be encrypted with a session key, Cryptographic mechanisms can be implemented by which is used for the secret key of a private-key the use of cryptosystems. These systems consist of a cryptosystem. This key is generated in form of a ran- set of invertible functions, a set of keys, parameter- dom number by the originator of m during the begin- ising these functions, and sets, on which these func- ning of each communication (session). The key is tions operate. Cryptosystems are subdivided into pri- only valid within one session. vate-key cryptosystems and public-key cryptosys- User A (sender) encrypts the plaintext m with the en- tems. In private-key cryptosystems the communicat- cryption function f parameterised by the key K. To ing entities share a key K, which must strictly be kept transmit this key to the recipient in a secure way, a secret. Due to this requirement the key is called se- public-key cryptosystem is used: session key K is cret key. In public-key cryptosystems each entity encrypted with the encryption function g, parameter- holds a key-pair (PK,SK). This pair consists of a se- ised by the public key PKB of the receiver, user B. cret key SK and a public key PK corresponding to Then the ciphertexts cK and cm are transmitted to B. SK. The key SK must strictly be kept secret, the key In a first step user B (receiver) recovers the session PK may be made public, e.g. in a public-key direc- key K by decrypting the key-ciphertext cK: he com- tory. Given a public key PK it is computationally in- putes K by using the function g-1, which is param- feasible to find the secret key SK. In other words, eterised by the secret key SKB corresponding to even with the most powerful computers it is not pos- PKB. Then he computes the plaintext m from the en- sible to deduce PK from SK during a period of time. crypted data cm by use of the function f -1 of the pri- 4 Confidentiality vate-key cryptosystem, parameterised by K. Confidentiality can be achieved by means of cipher Based on the combination of private-key and public- systems. These systems are used to keep information key cryptosystems described above, the key ex- secret from unauthorised entities. change problem of secret keys with respect to pri- A cipher system consists of a set of encryption func- vate-key cryptosystems can be solved. Given that the tions, a corresponding set of decryption functions, public key has been exchanged authentically, it en- and a set of keys. The data to be encrypted (plaintext) sures that only the legal owner of the secret key SKB is transformed by the encryption function param- is able to recover the secret key K used for encryp- eterised by a key. The result of this transformation is tion. A possible solution for this problem will be called ciphertext or cipher. The plaintext can be re- given in section 8. Besides that it ensures that only covered by a decryption function also parameterised the legal owner of the secret key SKB is able to re- by a key. cover the secret key K used for encryption. Private-key and some public-key cryptosystems can Some examples of private-key cryptosystems which be used for cipher systems. In addition there exist so- are used for cipher systems are DES [14], triple-DES called session-key systems (also known as hybrid [1] and IDEA [13]. Examples of public-key crypto- cryptosystems), which employ both types of crypto- systems, used for encryption schemes, are RSA [21] systems. Because of the importance of session-key and ElGamal [5]. Commonly used combinations for schemes we will give a more detailed discussion in session-keys schemes are DES with RSA or IDEA the following section. with RSA. 5 Data Integrity The integrity of data can be checked by means of so- called one-way hash functions. These functions are 1 Example [22]: In hardware, DES is about 1000 times and, in software, about 100 times faster than RSA. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 13 often named manipulation detection code (MDC), 6 Data Origin Authenticity message digest, digital finger print, cryptographic The following two mechanisms assure not only data checksum or message integrity code (MIC). These integrity but also data origin authenticity: mechanisms cannot prevent data manipulations, but * message authentication code (MAC), and they make these manipulations detectable. Therefore * digital signatures. they are called detective mechanisms. The protected Just like the mechanisms for data integrity these data remain in plaintext. mechanisms are detective, and the protected data A one-way hash function H maps strings of arbitrary again remains in plaintext. length to strings of a maximum or fixed length |n|: H: 6.1 Message Authentication Code 0* [0,n] 0 where n 0. With respect to bi- nary strings used as input, H can be defined as fol- A message authentication code (MAC) is a one-way lows: H: {0,1}** {0,1}n, where n typically assigns hash function h = H(k,m), which is parameterised by one of the values 64, 128 or 160 bits. A hash function a secret key k. The security of a MAC depends on reduces the data m to its so-called hash value the length of the generated hash value as well as on h := H(m). the quality of the used key k. Only those entities that Hash functions possess the characteristic that the im- know the secret key k may calculate the MAC. age H(m) can be computed easily, but that it is com- The mechanism works as follows (see figure 3): putationally infeasible to find any preimage m such that m = H(m). O riginato r: data m M A C := H (k,m ) m || M A C Since there exist infinitely many strings of arbitrary length, but only finitely many strings with a m true length * |n|, it is obvious that so-called collisions au thentic exist, where different input values are mapped to the MAC V erifier: = M A C * := H (k,m ) m || M A C same hash value. However, hash functions must have MAC * the property of collision resistance: it must be hard to m n ot find two different preimages m au thentic false 1 and m2 which are mapped to the same hash value H(m1) = H(m2). Figure 3: Message Authentication Code (MAC) Some examples of hash functions are MD5 [20], RIPEMD-128 [4], RIPEMD-160 [4] and SHA-1 The originator who wants to protect the data m cal- [15]. culates a checksum of m using a one-way hash func- Hash functions are public, i.e. no secret information tion and the key k, i.e. he computes MAC := H(k,m). is used for computing a hash value. Thus everyone Anyone who owns key k can check the data m for who knows the function may compute the hash value authenticity. For this the verifier computes a check- and thereby check the integrity of the data. sum MAC* := H(k,m). If this value corresponds to Figure 2 illustrates how a one-way hash function is the original MAC, the data m (and also the MAC) are used. authentic. Otherwise either m or the MAC has been changed in the time period between the generation of O riginator: data m h := H (m ) m || h the MAC and its verification process. It is important to note that for this mechanism to work at least two parties, namely the originator and m has true integrity the verifier, need to hold the same key k. Thus, a MAC can not be used to prove anything (e.g. trans- V erifier: h = h* h* := H (m ) m || h mission or authenticity) to a third party. m has no integrity A simple hash function commonly used to compute a false MAC is based on a block cipher operating in the ci- Figure 2: One-Way Hash Function H pher-block-chaining mode (CBC-based MAC, see figure 4). Data m is divided into n blocks of the same To verify data integrity, the received hash value h is length, determined by the domain of the block cipher compared with the newly computed hash value (for example 64-bit blocks): m = m h*=H(m). If h is equal to h*, the data (and also the 1||m2||...||mn. If necessary the last block m hash value) are considered to be unchanged. This is n is padded with a number of padding bits to extend it to the required length. due to the fact that the modification of even one bit Each block m in the data m leads to a different hash value H(m). In i is linked in some way to the previ- ously generated ciphertext block c addition to the above explained collision resistance i-1 (i>1) and en- crypted with the encryption function E parameterised property, hash functions must fulfil the following by a secret key k. The last ciphertext block c criterion: whenever one input bit is changed, every n forms the resulting MAC (sometimes the MAC is defined bit of its hash value will change with probability of by a part of this ciphertext block). 1/2 (avalanche effect). Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 14 m E(k,m ) c rately. The other, commonly used possibility is to use 1 1 1 a hash function to reduce m to a value H(m) < n which can then be signed. This increases both the se- curity and the performance. For example, it is no m E k, bm g 2 c1 c 2 2 longer possible to change the order of the signed blocks (and thereby the signed data). Thus, the sig- nature is not calculated from the data itself, but from the hash value of the data. One-way hash functions used in digital signature m E k, bm g n cn-1 c =: M A C n n schemes are for example MD5 [20], RIPE-MD 128 [4], RIPE-MD 160 [4] and SHA-1 [15]. Figure 4: An example: CBC-based MAC For protecting the authenticity of data by digital sig- If the key is publicly available, the hash function can natures the following steps are performed (see fig- be taken as a manipulation detection code. ure 5). The description given here is limited to a sim- ple scheme of a digital signature (e.g. RSA [21]). 6.2 Digital Signatures The idea and the term "digital signature" were intro- Signer A: data m h := H (m ) s := S(SK A ,h) m || s duced by Diffie and Hellman. In [3] they suggest the following: The digital signature of an entity A (the signer) to data m shall depend on the content of m m true h* := H (m ) authentic and, additionally, on some secret information only V erifier: h = h* m || s known to the signer. Each user shall be able to verify m not the authenticity of the signature created by A (verifi- authentic h := V (PK A ,s) false cation), by using a publicly available information of A. Since only A possesses the secret information, Figure 5: The Principle of a Digital Signature only he is able to create the signature to m by using Signer A wants to transmit data m and its signature the signing function S. Therefore, unlike the MAC, to a verifier. For this A computes the hash value h of the digital signature may be used to prove some fact m by means of a hash function h := H(m). Then A (origin, authenticity) to a third party. calculates the value s := S(SKA,h) by applying the The functions used for generating a digital signature signing function S to H(m) and a secret value only are called trapdoor one-way functions These func- known to him (his secret key SKA). Finally A trans- tions are one-way functions in the following sense: mits m and the corresponding digital signature s to given a preimage x it is easy to calculate the image the verifier. f(x), but it is computationally infeasible to find a pre- The verifier needs to know the public key PKA of A, image x for any given f(x). However, if some addi- the hash function H and the verification function V. tional information y (called the trapdoor information) First he computes a hash value h* := H(m) of the re- is known, it is easy to compute x. ceived data m. Then he transforms the received sig- Public-key cryptosystems can be used to generate nature using the verification function and the signer's and verify digital signatures. The secret key SK of a public key, i.e. he calculates h = V(PKA,s). Finally, user represents the secret information, and the public he compares the values h and h*. If h = h*, A's sig- key PK the publicly available information. nature is correct, meaning that neither the data nor Sometimes a MAC generated with a private-key the signature have been altered after their generation. cryptosystem is called "digital signature". But this Since A is the only one being in possession of the se- does not have one of the most important properties of cret key SKA, only A can compute the correct sig- a signature, namely that it can only be generated by nature s to m. If h * h*, the signature is considered one entity. as false and the data as not authentic. This can be Some examples of a public-key cryptosystem which caused for example by the modification of the data m can be used for digital signatures are RSA [21], DSS or the signature s in the time between the signing and [18], ElGamal [5], GMR [7] and Fiat-Shamir [6]. verifying process, or by a public key not corre- The document m to be signed may not exceed a cer- sponding to the secret key used for the signature gen- tain size, which is determined by the domain of the eration. employed digital signature scheme. For example, Besides this relatively simple possibilities for com- some functions used in a digital signature scheme puting and verifying signatures (signature with ap- operate on the finite set of integers 9n* 9n where pendix) there are further, more complex methods, n = p q or GF(p)* GF(p) where p and q prime. which concern the signature's format (like signature Thus for signing and verifying data m outside the giving message recovery or signature giving limited range of the signature function there are two possi- message recovery). bilities. One is to split the data m into blocks If the data are to be transmitted confidentially and m1,...,mk with e.g. mi < n and sign each block sepa- authentically, the sender first signs the data with his Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 15 secret key and second encrypts m together with the Entity A (verifier) wants to check the identity of en- signature using the recipient's public key. tity B (claimant). For this, A generates a random 7 Entity Authenticity number R (challenge), and transmits it to B. Entity B As described in the previous paragraph, data authen- encrypts this random number by means of an en- ticity can be checked by digital signatures. Beyond cryption function f and the key K. Then he sends the that, it is often additionally necessary to ensure the resulting cipher R* (response) to A. Entity A de- authenticity of entities, e.g. for guaranteeing that the crypts the received cipher by use of f -1 and the key communicating parties (this may be persons as well K. Then he checks if the calculated value corre- as devices) are indeed the ones they claim to be. sponds to the random number R. If so, claimant B is Schemes enabling such a proof are called authentica- considered to be authentic. tion protocols. The data which is transmitted between Since each entity possesses the same key, high secu- the parties during the protocol may contain additional rity requirements result on the storage of the key. textfields. These fields may be used to exchange se- The need of user A and user B to hold the same key cret keys for a further confidential communication. may be overcome by the so-called derived key con- In the following we present the simplest version of cept: individual keys, which are derived from master an authentication protocol: the challenge-response keys and some additional information, are used protocol. This protocol can be implemented on the within the challenge-response protocol. Let us as- basis of a private-key or a public-key cryptosystem sume the master key MK is stored by entity B. Entity (see figures 6, 7 and 8) [11]. A possesses an individual key IK, which can be cal- Basically such a protocol works as follows: The veri- culated by B using MK and data provided by entity fier sends to the claimant a randomly generated A. For this, A transmits unique data describing his number, the so-called challenge. The claimant re- identity (IDA) to B. IDA is used as an argument of turns a response to the verifier which consists of a the calculation of the derived key: IK = f(MK,IDA). ciphertext generated by using the challenge. For each Finally both A and B share a common secret key, authentication a new question is generated, thus this which may be used within a challenge-response pro- kind of authentication is called dynamic authentica- tocol. tion. If two entities want to authenticate themselves mutu- Authentication is subdivided into unilateral and mu- ally, there exist two possibilities. The straight for- tual authentication. Within the unilateral authentica- ward solution is to process the presented unilateral tion an entity proves to another entity its authenticity, authentication twice with reversed roles of claimant within the mutual authentication both entities prove an verifier in the second run. In order to simplify this their authenticity mutually. protocol and to reduce the transaction time, the fol- Within a challenge-response protocol based on a lowing authentication protocol is used for mutual private-key cryptosystem the two entities use the authentication (see figure 7): same encryption/decryption algorithm f and f -1 and Entity A Entity B need to share a key K. In the following we describe Random Number Random Number the unilateral authentication according to ISO 9798-2 RA RB (see figure 6). RB E ntity A E ntity B f (K,RA||RB) (V erifier) (C laim ant) R andom N um ber f (K,RA||RB) R f -1 (K, f (K,RA||RB)) = RA||RB R yes RB no R * := f (K ,R ) correct R * authentication authentication successful not successful f (K,RB||RA) true R = f -1(K ,R *) false f -1 (K, f (K,RB||RA)) = RB||RA authentication authentication successful not successful yes RA no correct Figure 6: Unilateral Authentication Using a Private- authentication authentication Key Cryptosystem successful not successful Figure 7: Mutual Authentication Using a Private-Key Cryptosystem Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 16 Both entities A and B generate a random number RA Besides the simple authentication protocols described and RB, respectively, and B sends its random num- in this paper there exist more complicated protocols ber to A. A encrypts the concatenation RA||RB and which are discussed in the standard ISO/IEC 9798 transmits the cipher f(K,RA||RB) to B. Entity B de- [11]. Here five methods are defined: the unilateral crypts the cipher and checks if the resulting second one pass authentication, the unilateral two pass integer corresponds to the random number RB gener- authentication, the mutual two pass authentication, ated by himself. If so, B encrypts the concatenation the mutual three pass authentication, and the mutual RB||RA and sends the cipher f(K,RB||RA) to A. En- two pass parallel authentication. tity A decrypts the cipher and performs the equiva- Some examples of public-key cryptosystems, which lent check. If both checks succeed, A has proven his are used for digital signatures, are RSA [21], DSS authenticity to B and vice versa. [18], ElGamal [5], GMR [7] and Fiat-Shamir [6]. Since the transmitted data are depending on each It is important to note that the above described other and thus no instruction can be inserted unno- authentication protocols are not secure in general. If ticed during the protocol, the security of the authenti- both A and B are able to start the protocol, and addi- cation protocol increases. tionally the received random number is accepted as a Private-key cryptosystems, which are used for cipher challenge without any check, then the following at- systems, are e.g. DES [14], triple-DES [1] and IDEA tack, the so-called replay attack, may be performed: [13]. Verifier A transmits a random number R1 to the Challenge-response protocols based on a public- claimant, which is intercepted by some adversary X. key cryptosystem use the fact that digital signature In the role of the claimant, X sends R1 to A by start- are appropriate for authentication protocols. Here, ing a second protocol run. Then entity A as claimant two different keys are used: the public key and the encrypts the random number R1 and transmits the ci- secret key of the claimant. The unilateral authentica- pher R1* to X as the verifier of protocol run 2. This tion is performed as follows (see figure 8): terminates the second protocol run, and adversary X can use R1* to send, again adopting the role of the E ntity A E ntity B (V erifier) (C laim ant) claimant of the first run, R1* to verifier A. A will then consider the communication as authentic. R andom N um ber R In order to prevent this (and other possible) attacks, the unique identification number of the verifier and/or claimant are added to the transferred data R [11]. Using timestamps instead of random numbers disables replay attacks as described above, but this R * := S (SK ,R ) will raise the problem that A and B have to be equipped with synchronised clocks. R * 8 Non-Repudiation Within legal facilities digital signatures in their own true R = V (PK,R*) false are not sufficient to link data and actions to their originators. The two following examples may clarify this: authentication authentication successful not successful * A sender may disavow that he signed a particu- lar message, e.g. by publishing his secret key Figure 8: Unilateral Authentication Using a Public-Key anonymously, and then claiming the key has Cryptosystem been lost or stolen. Thus, he may also declare Entity A wants to verify the identity of entity B. First that the signature of the message has been A obtains B's public key PKB, e.g. provided by pub- forged. lic key directory. Then A generates a random number * A sender may claim that messages, which were R and transmits R to B. Entity B signs R by means of already signed by him before the compromising the signature function S and his secret key SK. Sub- of his secret key, are forged. To achieve this, he sequently, he transmits the result R* to A. By the use simply attaches an earlier timestamp to already of the verification function V and B's public key PK, signed messages and signs them again. Now he A verifies the received signature, by checking if R may claim that the signatures have been forged. corresponds to the value calculated by him. If so, B is considered authentic. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 17 Here, security infrastructures and security techniques 9 Public-Key Infrastructure may be used to provide some evidence that will be The use of public-key cryptosystems raises the fol- accepted by courts. So-called non-repudiation lowing problems: mechanisms [12], which are based on private-key * By means of session-key schemes the encrypted cryptosystems (message authentication code) or pub- session key (and thus the plaintext) may be re- lic-key cryptosystems (digital signatures), are sup- covered only with the secret key of the recipient porting such security techniques. They comprise non- (so-called addressed confidentiality). However it repudiation certificates, non-repudiation tokens and cannot be ascertain whether or not the public protocols. Trusted Third Parties (TTP) supply notary key, which is used for the encryption of the ses- Sender A : data m s := S(SK A ,m ) s := S(SK A, ID A || m || s ) ID A || m || s || s m m m true true A rbiter Z : ID A || m || s || s ID A s* := V (P K A,s) s = s* s := S(SK Z, ID A || m || s || T ) ID A || m || s || T || s m m m correct false false m not authentic true R eceiver B : ID A || m || s || T || s s* := V (P K Z,s) ID A s = s* true s * := V (P K A ,s ) s = s * true m m correct m m m m authentic false false false m not authentic Figure 9: Arbitrated Digital Signature services, timestamping services and evidence re- sion key, actually belongs to a particular person cording. By means of these mechanisms it can be (or device). proven to involved parties and third parties whether * By use of digital signatures and signature-based or not a particular event occurred or a particular ac- authentication protocols it can be checked tion happened. The event or action may be generat- whether the signature to particular data was gen- ing a message, sending a message, receiving a mes- erated by a specific key by verifying the digital sage or transmitting a message. Therefore these signature. Thus the authenticity of a message or mechanisms are subdivided into: communication can be proven. However it is not * non-repudiation of origin, provable whether or not the used keys actually * non-repudiation of delivery, belong to a certain person. * non-repudiation of submission, and Obviously, an authentic link between the public key * non-repudiation of transport. and its owner is needed. Such a link is provided by In the following we will give an example of non- so-called public-key certificates [9, 10]. For the is- repudiation of origin by use of arbitrated digital sig- suing of certificates a trustworthy authority, a so- natures (see figure 9). called trust center (TC), is needed. Trust centers Entity A wants to transmit data to entity B, whereby authenticate the link of users to their public keys, and A must not be able to repudiate being the originator can provide further services like non-repudiation, of the data. Sender A possesses an identity string revocation handling, timestamping, auditing and di- IDA, which uniquely describes his identity. First A rectory service. signs the data m by using his secret key SKA. Then Within a trust center these services are provided by he signs the concatenation IDA||m||s special components. Each trust center, and even its m, and transmits it together with its signature s to a trustworthy third components, comply with a so-called security policy. party, the arbiter Z. Arbiter Z checks IDA and veri- This policy regulates the generation and distribution fies the signature s of the data IDA||m||s of certificates, and how to ensure the availability of m generated by A. If all checks are successful, the arbiter Z at- the services. taches a timestamp T to the data IDA||m||sm and signs 10 Security for Multimedia these sequence, too. Now, he transmits the signed Whether or not the presented security functions can data to entity B. Receiver B verifies the signature of be used easily for multimedia data and multimedia Z, checks IDA for correctness and finally verifies the applications, must be checked for each kind of appli- signature sm of A. If all checks are correct, A can not cation separately. The following problems may result deny to be the originator of the data. due to the data formats and the amount of data: Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 18 * For reasons of performance, instead of encrypt- RIPEMD. Fast Software Encryption - Cam- ing the whole data only special parts of the entire bridge Workshop 1996, Md. 1039, Springer- data are encrypted (partial encryption). If the se- Verlag, Berlin 1996, pp.71-82. lection is well chosen, a sound confidentiality of [5] ElGamal, Taher: A Public Key Cryptosystem the whole data can be achieved. and a Signature Scheme based on Discrete Loga- * All security functions described in this paper that rithms. IEEE Transactions on Information The- can be used for checking the integrity and ory, Vol.31, Nr.4, Jul 1985, pp.469-472. authenticity of some data have the property that if one bit of the input is changed, the checks will [6] Fiat, Amos; Shamir, Adi: How to prove your- fail. Thus, if the authenticity of, say, graphic data self: Practical solutions to identification and sig- is needed, it seems to be difficult to define a nature problems. Advances in Cryptology - suitable input for digital signature schemes. Here Crypto'86 Proceedings, LNCS 263, Springer- a kind of data has to be used, which is not altered Verlag, pp.186-194. by the allowed operations such as scaling and [7] Goldwasser, Shafi; Micali, Silvio; Rivest, conversion of picture formats. Appropriate Ronald L.: A `Paradoxical' Solution to the Sig- methods include using characteristic vectors, nature Problem. 25th Symposium on Founda- which typify the graphic data as unique and are tions of Computer Science (FOCS), 1984, not influenced by allowed graphical operations. pp.441-448. * In order to provide non-repudiation services a [8] Information Technology Security Evaluation proper security infrastructure has to be estab- Criteria (ITSEC): Provisional Harmonised Crite- lished and a security policy must be defined. ria. Version 1.2, Jun 1991. Furthermore the three basic threats, which we pre- sented in paragraph 2, cannot cover the whole spec- [9] ISO/IEC 9594-8 | ITU-T Recommendation trum of the security requirements on multimedia. The X.509: Information technology - Open Systems essential, fourth basic threat to multimedia is: Interconnection - The Directory. Part 8: Authen- * threat of originality (unauthorised duplicating of tication Framework, 1993. data). [10] ISO/IEC 9594-8 | ITU-T Recommendation The originality of data guarantees that they are pre- X.509: Final Text of Draft Amendments DAM 1 sented in an unchanged form and not in a copy. For to ITU-T Recommendation X.509 (1993) | the protection of originality detectives mechanisms ISO/IEC 9594-8 on Certificate Extensions: are used, e.g. copyright protection, digital water- ISO/IEC JTC 1/SC 21/WG 4 and ITU-T Q15/7. marking and steganography. These mechanisms are Dec 1996. still an issue of the present research. Additionally le- [11] ISO/IEC 9798: Information technology - Secu- gal regulations, such as copyright protection, patent rity techniques - Entity authentication. Part 1: protection and computer criminal law, are trying to General (IS 1997). Part 2: Mechanisms using find countermeasures against this threat. encipherment algorithms (IS 1994). Part 3: With respect to the security of multimedia these few Mechanisms using a public key algorithm (IS examples show that there still exist a lot of open 1993). problems, which result in particular from the com- plexity of the multimedia data and their applications. [12] ISO/IEC 13888: Information technology - Secu- It has to be analyzed if and in which way the IT- rity techniques - Non-repudiation. Part 1: Gen- security mechanisms presented in this paper can be eral (IS 1997). Part 2: Using private-key tech- used to guarantee multimedia security. niques (DIS 1997). Part 3: Using public-key techniques (IS 1997). 11 References [13] Lai, Xuejia; Massey, James: A proposal for a [1] ANSI X9.17(Revised): American National Stan- New Block Encryption Standard (IDEA). Ad- dard for Financial Institution Key Management vances in Cryptology - Eurocrypt`90 Proceed- (Wholesale). American Bankers Association, ings, Springer-Verlag, Berlin 1991, pp.389-404. 1985. [14] National Bureau of Standards: Data Encryption [2] Department of Defense: Department of Defense Standard (DES). FIPS PUB 46-1, Jan 1988. Trusted Computer System Evaluation Criteria (Orange Book). DOD 5200.28-STD, Dec 1985. [15] National Bureau of Standards: Secure Hash Standard (SHS-1). FIPS PUB 180-1, 17.4.1995. [3] Diffie, Whitfield; Hellman, Martin E.: New Di- rections in Cryptography. IEEE Transactions on [16] National Computer Security Center: Trusted Information Theory, Vol.22, Nr.6, 11/1976, Database Management System Interpretation of pp.644-654. the Trusted Computer System Evaluation Crite- ria. NCSC-TG-021, Version 1, Apr 1991. [4] Dobbertin, Hans; Bosselaers, Antoon; Preneel, Bart: RIPEMD-160: A strengthened version of Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 19 [17] National Computer Security Center: Trusted [20] Rivest, Ronald L.: The MD5 Message Digest Network Interpretation of the Trusted Computer Algorithm. RFC 1321, Apr 1992. System Evaluation Criteria (Red Book). NCSC- [21] Rivest, Ronald L.; Shamir, Adi; Adleman, Leon- TG-005, Version 1, Jul 1987. ard A.: A method for obtaining digital signatures [18] National Institute of Standards and Technology: and public-key cryptosystems. Communications Digital Signature Standard (DSS). NIST FIPS of the ACM, Vol.21, Nr.2, Feb 1978, pp.120- PUB 186, May 1994. 126. [19] NATO: NATO Trusted Computer System [22] Schneier, Bruce: Applied Cryptography. John Evaluation Criteria (Blue Book). NATO AC/35- Wiley & Sons, Inc., 1996, p. 469. D/1027, 1987. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 20 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 21 The Functions of Digital Signatures from a Legal Point of View Anja Miedbrodt Research Area 403 Senckenberganlage 31 60054 Frankfurt/Main 049-69-79823361 a.hesse@jur.uni-frankfurt.de ABSTRACT According to the state of art one possible resolution for that is the concept of digital signatures. But there This paper provides on overview of the neces- are quite a number of technical and organizational sity of the digital signature for electronic requirements for digital signatures to fulfil their commerce and describes the legal require- functions. One of these requirements is for example ments of the German Digital Signature Act the cryptographic (mathematical) security of used and the Signature Ordinance compared with procedures. A secure generation of the keys, distri- the Proposal of the European Commission on bution, allocation, administration and maintenance of a common framework for electronic signa- revocation lists as well as the storage of the private tures. keys are further requirements. Specification of technical requirements for providers KEYWORDS of digital signature products is a widespread object of Electronic signature, value of evidence of digital sig- state legislation2 or the work of standards organisa- natures, technical requirements of the German Digi- tions3 as well as intended international agreements4 tal Signature Act and the Signature Ordinance. and transnational guidelines5. 1 Introduction The German Digital Signature Act (enacted on 1st The success of the Internet depends on the offered August 1997) and some Digital Signature Acts of contents. It is doubtful if originators will publish several States of the United States are forerunners on their work in the Internet without a sufficient legal the level of the state regulation. and technical protection. Equally the general public According to a provisional stature of research these will only use this medium, if there is a lot of infor- regulations could be divided at least into two ap- mation available and if it's integrity is guaran- proaches, which are partly founded on opposite teed.[16] goals: Because of the possibility of: * On the one hand there are detailed legal techno- * digital storage and sending of data without any logical and organizational requirements for lost of quality, digital signatures to actually determine the integ- * cheap creation and distribution of copies, rity and the authenticity of a message. This ap- proach is for example followed by the German * exact access to every point of a stored and indi- Digital Signature Act. These Acts aim to pro- vidual retrieval work, without necessity to buy mote the electronic commerce by legal condi- the whole work, tions of actually secure digital signatures. In * digital alteration, combination and disfigurement summary this approach aims to provide the of work [18] guarantee to prove obligations by technical law. the right of the originator to exploit his work is en- dangered. The protection is only guaranteed in the 2 interaction of legal and technical facilities. The pro- Beside the German Digital Signature Act is in Europe the Italian one enacted. Other European countries like Aus- tection has to be orientated on the attacks of third tria and Denmark plan to include in their drafts the ex- parties. pected Guideline of the European Union. In the United Beside the problem of proving the integrity of a mes- States, Utah, California, Florida, Illinois and Massachu- sage the impossibility to allocate a message to it's setts for example did enact Signature Acts. originator (the problem of authenticity) also exists in 3 X 509, FIPS 140- 1, ITSEC, Department of Defense electronic networks. This threats the electronic com- Trusted Computer Evaluation Criteria", Common Crite- merce, because it is impossible to enforce obliga- ria (CC). tions. Without an evidence of integrity and authen- 4 OECD-Crypto-Guidelines 1997, UNCITRAL- Draft Uni- ticity a court could not be convinced of obligations. form Rules On Electronic Signatures. 5 Proposal on a common framework for electronic signa- tures COM(1998)297/2/98/0191(COD). Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 22 * On the other hand the legislation aims at re- These evidences will be considered by court in the moving legal obstacles for digital signatures and course of free consideration of evidence9, which electronic commerce. These provisions aim at means that the judge has to be convinced of the facts. promoting digital signatures by nonregulation. There is only a practical level of certainty required, Mainly they face provisions, requiring hand- because the complete certainty can not be written signatures, because of historical reasons. achieved.[15] Object of these Acts are for example the explicit How the judge assets several evidences is entirely up admission of digital signatures for the communi- to him. Only in the course of the documentary evi- cation with offices or as an evidence in pro- dence he is limited, because there are some provi- ceedings. The guarantee of the technical security sions, which attach some facts to legal presumptions is left to the market. An example for this ap- of genuineness and freedom of damage of a declara- proach is the Proposal of the European Commis- tion included in a document.[3] That's why the sion on a common framework for electronic sig- document is a reliable evidence. natures (COM (1998)297/2/98/0191 (COD), But a document is only a mental declaration in let- passed at 13th Mai 1998. ters. [15] Because of the last requirement the digital * Between them there are a lot of hybrid ap- signed document can not serve as a documentary proaches. evidence. [4,17] 2 How are the digital signatures em- But it can provide as real evidence and expert evi- dence.[17] The actually capability of the digital sig- bedded in the German legal system? nature to provide the evidence of integrity and 2.1 Writing Form authenticity plays an important role for the consid- Generally according to the German civil law oral eration of evidences. contracts are valid, unless a rule of law requires a That's the reason why the German Digital Signature hand-written signature6 or the parties have arranged Act aims in accordance with § 1 paragraph 1 Signa- by contract the use of the writing form.7 The reason ture Act at the establishment of general conditions for writing requirements are: under which digital signatures are deemed secure. - to protect the parties against precipitation, It is possible, that the increasing experience in the - to prove the agreement and to create certainty usage of digital signature products could be appreci- about the obligations and rights, ated by the means of prima facie evidence.[6] - sometimes to make possible supervision by Prima facie evidence is a way to limit the free con- State.[14] sideration of evidence by the judge. If facts are cer- The evidence function of the hand-written signature tain, normally based on particular reasons, in adjudi- is based on cultural experience. The connection of cating a dispute, a court shall presume that these rea- the declaration with a durable medium guarantees the sons are proved. integrity. The authenticity is provided by the con- In opposite to the fundamental principal that the nection between the declaration and hand-written plaintiff has to prove all facts, which support his ac- signature as a genuine biometric feature of the origi- tion, in the case of prima facie evidence he only nator.[6] needs to demonstrate and prove the facts, which indi- At the moment the digital signature doesn't satisfy cate the typical reasons. The opponent, which de- this signature requirement, because it is not hand- clares the divergence of these typical reasons has to written. But the legislator is considering if it is nec- prove it. essary to introduce the electronic form which will be 3 The German Digital Signature Law equal to the hand-written signature. As above mentioned the Digital Signature Act pro- 2.2 Evidence Law vides an infrastructure for secure digital signatures. In the course of a proceeding, parties declare facts to Important corner pillars for the actual security of justify their claims. If any facts are contentious, they digital signatures according to the Germans Digital have to be proved. According to German code of Signature Act and the Digital Signature Ordinance, civil procedure, parties can use every evidence, in- enacted on 1st November 1997, are: cluding digital signed declarations. This is not natu- - governmental-licensed certification authorities,10 ral, because other legal systems require, that contacts - by the certification authority informed holders of have to be in written form to be enforceable.8 the keys,11 6 § 126 BGB. 9 § 286 ZPO. 7 § 125 sentence 2 BGB. 10 § 4 Digital Signature Act. 8 for example § 2-201 Statute of Frauds (Uniform Com- 11 §§ 6, 16 number 3 Digital Signature Act, § 4 Signature mercial Code). Ordinance. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 23 - qualified suitable technical components. The re- the services that have to be provided by the certifica- quirements are described as aims to offer space tion authorities. for innovation.12 - supervision by the competent authority and 3.1 Requirements for the Keys regularly inspections. [8]13 The technical components required for generation of The legal requirements for the qualified suitable signature keys must work in such a manner that it is technical components are applied to the certification nearly certain that any given key can occur only once authorities as well as to final-consumers and to those, and that a private key cannot be derived from the who offer their technical components commercially relevant public key.19 to final-consumers. A governmental control of the The competent authority shall publish in the Federal compliance with these legal requirements takes only Gazette an overview of the algorithms and pertinent place in the course of the licensing of the certifica- parameters considered suitable for generation of sig- tion authorities. These legal requirements shall be nature keys. Information published in this way shall deemed met when the competent authority has been include the date until the suitability is valid. This notified by means of a security concept of measures date should be at least six years after the time of as- ensuring compliance with the security requirements sessment and publication. The suitability shall be re- in this Act and the Ordinance and their implementa- determined on a yearly basis and as required. Suit- tion has been checked and confirmed by a body rec- ability shall be considered present if, throughout a ognised by the competent authority.14 The security certain time period, any undetectable forging of concept shall include all security measures and espe- digital signatures or manipulation of signed data can cially an overview of the applied technical compo- be ruled out with near certainty, by means in keeping nents and a description of the procedures used in with current scientific and technological standards. certification. The concept shall be modified without Suitability shall be determined in keeping with provi- delay in cases of security-relevant changes.15 sions of the Federal Agency for Security in Informa- The competent authority shall keep a catalogue of tion Technology, taking relevant international stan- suitable security measures and shall publish this dards into account. Experts from the areas of industry catalogue in the Federal Gazette16. These measures and science shall be consulted in this regard. 20 shall be taken into account in the preparation of the The secrecy of private keys must be assured, and it security concept.17 The catalogue shall be prepared must not be possible to duplicate keys.21 in keeping with provisions of the Federal Agency for This requires for the storage of the key a technical Security in Information Technology. Experts from component (for example a smartcard), which could the areas of industry and science shall be consulted in not be compromised according to the state of the art. this regard.18 Security-relevant changes in technical components These technical requirements of the Digital Signature must be apparent for the user.22 Act and the Signature Ordinance shall be faced in the If such changes have been taken place, the security following. of the technical component doesn't work sufficiently It should be distinguished between the requirements any more. It could be apparent for example through for the keys, the procedure for the generation and ex- failure. amination of the signature and the requirements for This should protect users from security-relevant ma- nipulation, especially from disclosure of their private keys. Testing of technical components must conform to the 12 § 14 Signature Act, §§ 16, 17 Signature Ordinance. E 4 Standard of the "Criteria for assessment of the 13 §§ 13, 16 number 5 Signature Act, § 15 Signature Ordi- security of information technology systems" (ITSEC) nance, 8. and must be rated as "high".23 14 § 4 paragraph 3 Sentence 3 Signature Act Such recog- The Ministry of Home Affairs with the agreement of nised authorities are Federal Agency for Security in In- the Ministry of Commerce has announced the Com- formation Technology, Debis Systemhouse Security mon Criteria for Information Technology (CC) ver- Services GmbH, TÜV Information Technology GmbH, sion 1.0. There are now valid evaluation critera. TÜV product Service GmbH ( DuD 1998, 236). Manufacturers and vendors of information technol- 15 § 12 paragraph 1 sentence 2 Signature Ordinance. ogy products and governmental offices could apply 16 § 12 paragraph 2 and § 16 Paragraph 6 Signature Ordi- for a certificate based on the Common Criteria at the nance. A first draft was presented on 18th November 1997 by the Federal Agency for Security in Information 19 § Technology. In the meantime drafts have been published 16 number 6 Signature Act , § 16 paragraph 1 sentence by the competent authority. The final draft will follow. 1 Signature Ordinance. 20 17 §§ 12 paragraph 2 sentence 2, 16 paragraph 6 sentence 2 § 17 paragraph 2 Signature Ordinance. Signature Ordinance. 21 § 16 paragraph 1 sentence 2 Signature Ordinance. 18 §§ 12 paragraph 2 sentences 3-4, 16 paragraph 4 senten- 22 § 16 paragraph 1 sentence 3 Signature Ordinance. ces 3-4 Signature Ordinance. 23 § 17 paragraph 1 Signature Ordinance. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 24 Federal Agency for Security in Information Technol- 3.2.3 Component For Display 32 ogy and at other institutions recognised by the com- Because of a technical manipulation or other techni- petent authority. [13] cal failure it could be happen, that data will be unin- tentional signed or that other data will be signed as 3.2 Requirements for the Procedure of displayed. Establishment and Testing the Sig- That's why the Act requires that the technical com- natures ponents for display of data for signing must work in 3.2.1 No Derivation Of The Private Key such a manner that the signing person can reliably The technical components required for generation or determine what data is to receive the signature; that a verification of digital signatures must function in digital signature is provided only at the initiation of such a manner that the private signature key cannot the signing person; and that such initiation is clearly be derived from the signature and the signature can- indicated in advance.33 The evaluation has to comply not be forged by any other means.24 with E 2 of ITSEC and must be rated as "high.34 This provision takes into account, that an attacker If technical components are commercially provided which has the public key and sufficient time as well to third parties for use, clear and reliable interpreta- as computering capacity, could try out all keys of the tion of the relevant data must be assured, and the limited number of keys till he has found the right technical components must automatically be checked one. [10] for genuineness when used.35 Security-relevant Digital signature products can only reach crypto- changes in technical components must be apparent graphic security at most, that means it must be im- for the user.36 possible with limited computering capacity in a suf- Technical components have to be in accordance with ficient short time to generate new and valid signa- E 4 of ITSEC and must be rated as high".37 tures. [10] 3.2.4 Component For Verification The used technical components have to be in accor- The technical components required for verifying dance with the E 4 Standard of the ITSEC and must signed data must function in such a manner that the be rated as "high".25 verifying person can reliably establish what data has Considered suitable algorithms and pertinent pa- received the digital signature; that the verifying per- rameters for generation of the keys shall be published son can reliably establish the identity of the signature in the Federal Gazette.26 key holder; and that the correctness of the digital sig- 3.2.2 Signature Component nature is reliably verified and appropriately dis- Use of the private signature key must be possible played.38 only following identification of the holder and must The technical components for verifying certificates require proper possession and knowledge; the key must permit clear and reliable determination of must not be disclosed during use.27 To realise these whether verified certificates were present, without requirements the use of a smartcard is necessary. having been invalidated, in the register.39 The techni- Protection from software is not sufficient. cal components must permit adequate determination, Biometrical characteristics may also be used for the as necessary, of the contents of signed data.40 identification of the signature key holder.28 The tech- If this technical components are commercially pro- nical components required for collecting identifica- vided to third parties for use, clear, reliable interpre- tion data must function in such a manner that they do tation of the relevant data must be assured, and the not reveal identification data and that the identifica- technical components must automatically be checked tion data is stored only on the data storage medium for genuineness when used.41 Security-relevant with the private signature key.29 Security-relevant changes in technical components must be apparent changes in technical components must be apparent for the user.42 for the user.30 The used technical components have to be in accor- 32 Regarding to the problem, that the Signature Ordinance dance with the E 4 Standard of the ITSEC and must doesn't determines the format of the data. [11] be rated as "high".31 33 § 16 paragraph 3 sentence 1 Signature Ordinance, § 14 paragraph 2 sentence 1 Signature Act. 34 § 17 paragraph 1 Signature Ordinance. 24 § 16 paragraph 2 sentence 1 Signature Ordinance. 35 § 16 paragraph 3 sentence 5 Signature Ordinance. 25 § 17 paragraph 1 sentence 2 Signature Ordinance. 36 § 16 paragraph 3 sentence 6 Signature Ordinance. 26 § 17 paragraph 2 Signature Ordinance. 37 § 17 paragraph 1 Signature Ordinance. 27 § 16 paragraph 2 sentence 2 Signature Ordinance. 38 § 14 paragraph 2 sentence 2 Signature Act. 28 § 16 paragraph 2 sentence 3 Signature Ordinance. 39 § 16 paragraph 3 sentence 3 Signature Ordinance. 29 § 16 paragraph 2 sentence 4 Signature Ordinance. 40 § 16 paragraph 3 sentence 4 Signature Ordinance. 30 § 16 paragraph 2 sentence 5 Signature Ordinance. 41 § 16 paragraph 3 sentence 5 Signature Ordinance. 31 § 17 paragraph 1 Signature Ordinance. 42 § 16 paragraph 3 sentence 6 Signature Ordinance. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 25 The technical components have to be in accordance be suitable pursuant to § 17 (2) of the Signature Or- with E 2 of ITSEC and must be rated as "high", un- dinance.53 less these components are commercially provided to The certification authority shall take measures to third parties for use. In this case they have to be con- prevent undetected forgery or manipulation of the form to E 4 of ITSEC.43 data intended for certificates.54 These measures re- On overview of suitable algorithms are published by quire especially repeated internal inspections and the competent authority.44 spot checks, which compare the content of certifi- 3.3 Requirements For The Services cates and application for certificates. [8] Performed By The Certification 3.3.3 Repository Authorities To provide a control of the validity of the certificates the certification has to maintain a repository.55 3.3.1 Generation Of Keys The technical components used to store certificates in The Signature Act does not contain any provision verifiable form56 must function in such a manner that about the question, who has to generate keys, either only authorised persons can make entries and the user or the certification authority. changes57, that the invalidation of a certificate cannot If the certification authority provides signature keys, be undetectably rescinded, and that information can this authority shall take precautions to prevent any be checked for genuineness.58 Protection against un- disclosure of private keys45 and any storage of pri- authorised retrieval are necessary. The information vate keys by the certification authority.46 Similar pre- must include mention of whether the verified certifi- cautions shall also apply to personal identification cates were present at the given time, without having numbers and other data used to identify the signature been invalidated, in the register of certificates.59 Se- key holder in conjunction with the data storage me- curity-relevant changes in technical components dium with the private signature key47 and to prevent must be apparent for the user.60 from unauthorised access.48 Storage of private sig- 3.3.4 Time Stamping Service nature keys by the certification authority shall not be Timestamps are necessary to provide an evidence permitted for the future, because this would endanger that data has been presented at a certain moment. the possibility to prove obligations. This is important for instance if the certificate has In this case somebody, who sends signed data could been revoked. declare, that the certification authority has been cop- The certification authority shall take precautions to ied and misused his private key. [9]49 protect the technical components used to generate If the signature key holder generates signature keys, time stamps from unauthorised access.61 the certification authority shall reliably establish The technical components with which time stamps whether the signature key holder uses suitable tech- are generated must function in such a manner that the nical components, pursuant to the Digital Signature valid official time62, without any distortion, is added Act and the Signature Ordinance, for storage and use to the time stamp when it is generated.63 Security- of the private signature key.50 relevant changes in technical components must be 3.3.2 Issue Of Certificates apparent for the user64. The certification authority shall take precautions to protect the components used to prepare the certifi- Proposal for a European Parliament and Council cates against unauthorised access.51 Directive on a common framework for electronic In accordance with the state of art the validity period signatures for a certificate, which has to be contained in the certificate52, shall be no longer than five years and shall not exceed the period during which the applied algorithms and pertinent parameters are assessed to 53 § 16 number 4 Signature Act, § 7 Signature Ordinance. 54 § 5 paragraph 4 sentence 1 Signature Act. 43 § 17 paragraph 1 Signature Ordinance. 55 § 4 paragraph 5 sentence 3 and § 5 paragraph 1 sen- 44 § 17 paragraph 2 Signature Ordinance. tences 2 Signature Act. 45 § 5 paragraph 2 sentence 1 Signature Ordinance. 56 § 4 paragraph 5 sentence 3 and § 5 paragraph 1 Sentence 46 § 5 paragraph 4 sentence 3 Signature Act. 2 Signature Act. 57 47 § 5 paragraph 2 Sentence 2 Signature Act. § 11 Signature Ordinance. 58 48 § 11 Signature Ordinance. § 16 paragraph 4 sentence 1 Signature Ordinance. 59 49 to the encryption-dispute [5], to the risk of a key recov- § 16 paragraph 4 sentence 2 Signature Ordinance. ery [1] 60 § 16 paragraph 4 sentence 4 Signature Ordinance. 50 §§ 14 paragraph 1 Signature Act, 16 number 3, § 5 para- 61 § 11 Signature Ordinance. graph 1 Signature Ordinance. 62 § 1 paragraph 4 Time Act 51 § 11 Signature Ordinance. 63 § 16 paragraph 5 sentence 1 Signature Ordinance. 52 § 7 paragraph 1 number 5 Signature Act. 64 § 16 paragraph 5 sentence 2 Signature Ordinance. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 26 On 13th Mai 1998 the European Commission has the scope of the Proposal. Contractual freedom passed a Proposal for a common framework for should prevail in such a context.70 electronic signatures. 3.3.6 Concept of regulation The European Parliament has to consent to this Pro- The European Commission recognises, that a legal posal. A decision is still pending. If this guideline framework is mainly needed for certificates to enable will be enacted the Member States have to transform the authentication of electronic signature of an sign- it in their legal systems. ing individual.71 This proposal aims at facilitating the use of elec- Nevertheless in the opposite of the German Digital tronic signatures as well as providing for their legal Signature Act the possibility to prove obligations recognition65. It aims at enabling the use of electronic shall be not provided by detailed technical require- signatures with an area without internal frontiers by ments. Ensuring legal recognition of electronic sig- focusing on the essential requirements for certifica- natures and of certification services is deemed to be tion services and leaves detailed implementation the most important issue in the area.72 The guarantee provisions to the Member States.66 of technical security is left to the market. But this 3.3.5 Field of application concept requires a functioning market, in which no The field of application of the Proposal is unlimited. monopoly exists and where security mechanism is 3.3.5.1 Technology- neutrality not subject to a limiting regulation and security is an While the digital signature technology is a recog- effective argument for purchase. [12] nised procedure to provide a proof of the integrity It might be possible, that the lack of detailed techni- and authenticity of a message, according to the cal requirements hinder the internal market of certifi- opinion of the European Commission, a Directive at cation services, because the Proposal provides no the European level should be technology-neutral and common level and no comparability for the security. should not focus only these kinds of signatures. This would be the opposite of the objectives of the That's why the Proposal describes the electronic sig- Proposal.73 nature functionally and not technically.[12] Since a 3.3.6.1 Liability rules variety of authentication mechanisms is expected to The liability rules74 shall support the trust-building develop, the scope of the Directive should be broad process for both customers and business, that rely on enough to cover a spectrum of "electronic signa- the certificates and service providers, and thus shall tures", which would include digital signatures based promote the broad acceptance of electronic signa- on public-key cryptography as well as other means of tures.75 authenticating data.67 Only in the Annex there are The certification service provider are liable to any special provisions concerning the content of a certifi- person who reasonably relies on the certificate for: cate68 and the obligations of certification service pro- * accuracy of all information in the certificate as viders in a public-key- infrastructure, based on digi- of the date it was issued, unless the certification tal signatures. service provider has stated otherwise in the cer- 3.3.5.2 Contractual freedom tificate. They are not liable for errors for infor- The freedom of the parties to agree among them- mation provided by the person to whom the cer- selves the terms and conditions under which they ac- tificate is issued, if the certification service pro- cept electronically signed data should be respected to vider can demonstrate that he has taken all rea- the extent allowed by national law.69 That's why electronic signatures used within closed groups, for example, where contractual relationships already exists, should not automatically fall within 70 Proposal on a common framework for electronic signa- tures COM(1998)297/2/98/0191(COD), background, Note 4, page 3. 71 Proposal on a common framework for electronic signa- 65 Art. 1 Proposal on a common framework for electronic tures COM(1998)297/2/98/0191(COD), aim and scope of signatures COM(1998)297/2/98/0191(COD). the Directive, Note 5, page 6. 66 Proposal on a common framework for electronic signa- 72 Proposal on a common framework for electronic signa- tures COM(1998)297/2/98/0191(COD), need for har- tures COM(1998)297/2/98/0191(COD), background, monisation, page 5. Note 5, page 3. 67 Proposal on a common framework for electronic signa- 73 Proposal on a common framework for electronic signa- tures COM(1998)297/2/98/0191(COD), background, tures COM(1998)297/2/98/0191(COD), need for har- note 2. page 3, aim and scope of the Directive note 2, monisation, page 5. page 6. 74 Art. 6 Proposal on a common framework for electronic 68 A certificate which complies with the requirements of signatures COM(1998)297/2/98/0191(COD). Annex I is called qualified certificate. 75 Proposal on a common framework for electronic signa- 69 Proposal on a common framework for electronic signa- tures COM(1998)297/2/98/0191(COD), aim and scope, tures COM(1998)297/2/98/0191(COD), note 9. note 8, page 7; note 11, page 10. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 27 sonably practicable measures to verify the in- give the certification service provider the possibility formation,76 to benefit from the legal validity of the associated * assurance that the holder identified in the certifi- electronic signatures by means of voluntary accredi- cate held, at the time of the issuance of the cer- tation schemes linked to common requirements.85 tificate, the signature creation device corre- These requirements are not as detailed as the re- sponding to the signature verification device quirements, demanded by the German Digital Sig- given or identified in the certificate,77 nature Act. The catalogue requires beside organiza- * in cases where the certification service providers tional and personal requirements, the usage of trust- generates the signature creation device and the worthy systems and use of products that ensure pro- signature verification device, assurance that the tection against modification of the products so that two devices functioning together in a comple- they can not be used to perform functions other than mentary manner.78 The certification service pro- those for which they have been designed. They must viders can limit their liability by including limits use electronic signature products that ensure the of the use of the certificates79 and by indicating a technical and cryptographic security of the certifica- limit on the value of transactions.80 This provi- tion services supported by the products. Further more sion has to be incorporated in the national legal provisions order to take measures against forgery of systems. Further liability provisions are based on certificates and in cases where the certification serv- the national laws. ice providers generate private cryptographic signa- 3.3.6.2 Technical requirements ture keys, they shall guarantee the confidentiality The legal recognition of electronic signatures is during the process of generating those keys.86 based on criteria, which are described in Annex II. The renunciation of minimal technical requirements The compliance with these requirements are not can complicate the enforcement of a suitable security linked to any prior authorisation or accreditation.81 level [12] and with it, the recognition of certificates, Certification Service providers should in general be issued by provider from foreign countries. free to offer their services without prior authorisa- 3.3.6.3 Legal recognition of electronic signa- tion. In accordance with the opinion of the European tures Commission there is no immediate need to ensure the The Proposal orders87, that Member States shall en- free circulation of certification services by harmo- sure that an electronic signatures, which are based on nising justified and proportionate national restrictions a qualified certificate according to Annex I issued by on the provision of these services.82 a certification service provider, which fulfils the re- That's why the Proposal determines, that Member quirements set out in Annex II, States shall not make the provision of certification * satisfy the legal requirements of a hand-written services subject to prior authorisation.83 signature; Regardless of that, Member States may introduce or * are admissible as evidence in legal proceedings maintain voluntary accreditation schemes aiming at in the same manner as a hand-written signatures. enhanced levels of certification service provision as a means to gain the confidence of customers84 and to This provision shows the contrary nature of the Pro- posal and the German Digital Signature Act. The Proposal is problematic, because it determines legal 76 Article 6 (1) (a) (2) Proposal on a common framework effects without safeguarding technical security. for electronic signatures The equal status of the hand-written signature and COM(1998)297/2/98/0191(COD). the electronic signatures requires clarity about the 77 Article 6 (1) (d) Proposal on a common framework for electronic signatures COM(1998)297/2/98/0191(COD). functions of the hand-written signature and that the 78 electronic signature provides actually the proof of the Article 6 (1) (d) Proposal on a common framework for electronic signatures COM(1998)297/2/98/0191(COD). integrity and authenticity. 79 This requires technical requirements, which can not Article 6 (3) Proposal on a common framework for elec- tronic signatures COM(1998)297/2/98/0191(COD). only determined and regulated by the market. The li- 80 ability rules are not a suitable instrument, because Article 6 (4) Proposal on a common framework for elec- tronic signatures COM(1998)297/2/98/0191(COD). they can't achieve the same security like a govern- 81 Proposal on a common framework for electronic signa- mental licensing scheme.[7] tures COM(1998)297/2/98/0191(COD), aim and scope of the Directive, Note 7, page 7. 82 Proposal on a common framework for electronic signa- 85 Proposal on a common framework for electronic signa- tures COM(1998)297/2/98/0191(COD), Note7, page 9. tures COM(1998)297/2/98/0191(COD), aim and scope of 83 Article 3 § 1 Proposal on a common framework for elec- the Directive, Note 4, page 6. tronic signatures COM(1998)297/2/98/0191(COD). 86 Annex II (f) Proposal on a common framework for elec- 84 Proposal on a common framework for electronic signa- tronic signatures COM(1998)297/2/98/0191(COD). tures COM(1998)297/2/98/0191(COD), background, 87 Art. 5 Proposal on a common framework for electronic Note 3, page 3. signatures COM(1998)297/2/98/0191(COD). Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 28 4 Acknowledgments [8] Deutscher Bundestag: Drucksache 13/7385 vom My thanks to Dr. Johann Bizer for giving useful ad- 09. April 1997. vices and help. [9] Federrath, Hannes, Schlüsselgenerierung in 5 References Trust Centern, DuD 1997, 98. [1] Abelson, Harold, Anderson, Ross, Bellovin, Ste- [10] Fox, Dirk, Fälschungssicherheit digitaler Signa- ven M., Benaloh, Josh, Blaze, Matt, Gilmore, turen, DuD 1997, 69. John, Neumann, Peter G., Rivest, Ronald L., [11] Fox, Dirk, Zu einem prinzipiellen Problem digi- Schiller, Jeffrey I., Schneider, Bruce, Risiken taler Signaturen, DuD 1998, 386. von key Recovery und Trusted Third Party- Verschlüsselung, DuD 1998, 14 . [12] Fox, Dirk, Grimm, Rüdiger, Entwurf einer EU- Richtlinie zu Rahmenbedingungen elektronis- [2] Begründung zur Signaturverordnung,. cher Signaturen", DuD 1998, 407. [3] Bizer, Johann, Hammer, Volker, Elektronisch [13] Mackenbrock, Common Criteria (Version 2.0), signierte Dokumente als Beweismittel, DuD Gemeinsame Kriterien für die Prüfung und 1993, 619. Bewertung der Sicherheit in der Information- [4] Bizer, Johann, Beweissicherheit im elektronis- stechnik, Seite 1, http://www.bsi.bund.de/literat/ chen Rechtsverkehr in A. Haratsch/D. Kugel- doc/cc_20d.htm. mann/U. Repkewitz (Hrsg.), Herausforderungen [14] Palandt, 56.Auflage, München 1997, § 125 Rdn. an das Recht der Informationsgesellschaft, Stutt- 1. gart (Boorberg Verlag) 1996, 141. [15] Putzo, Thomas, ZPO, 19. Auflage, München [5] Bizer, Johann, Kryptokontroverse Der Schutz 1995, § 286 Rdn.2. der Vertraulichkeit in der Telekommunikation, DuD 1996, 5. [16] Röhm, Alexander W., Wilop, Karsten, Urheber- rechtlicher Schutz im Internet, DuD 1998, 250, [6] Bizer, Johann, Digitale Dokumente im elektro- 251. nischen Rechtsverkehr, in: Detlef Kröger (Hrsg.), Internet für Rechtsanwälte und Notare, [17] Roßnagel, Alexander, Das Signaturgesetz, DuD Neuwied (Luchterhand) 1997, 148. 1997, [7] Bizer, Johann, Miedbrodt, Anja, Die digitale [18] Thomaschki, Kathrin, Europäisches Urheber- Signatur im elektronischen Rechtsverkehr, recht in der Informationsgesellschaft, DuD 1998, Deutsches Signaturgesetz und der Entwurf der 265. europäischen Richtlinie, in: Marc Andre Gimmy/Detlef Kröger (Hrsg.), Rechtspraxis im Internet (i.E.) Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 29 Secure Container Technology as a Basis for Cryptographically Secured Multimedia Communication Ulrich Kohl IBM Almaden Research Center 650 Harry Road San Jose, CA 95120, USA +1 (408) 927 1867 kohl@almaden.ibm.com ABSTRACT The requirements in the electronic marketplace are basically the same as these in the traditional market- Multimedia applications pose high require- place: Somebody who paid for something should be ments on their security. In this paper, two allowed - and restricted - to use the media in the way different categories of security technologies it was negotiated. This imposes requirements in all are described and discussed with regard to fields of security. their ability to secure communication and The shortcomings of Internet protocols in the secu- commerce of multimedia documents. After rity area were well known and tolerated ever since the introduction, the security requirements of the protocols were first deployed in the scientific multimedia systems are depicted. Section 4 world they originated from [2]. New concepts were gives an overview of cryptographic opera- developed and existing ideas were adapted in order tions and their use in existing Internet secu- to facilitate secure electronic commerce on the Inter- net. All of these new mechanisms - such as IPSP, rity solutions. Section 5 describes the con- SSL, SSH or S/MIME - attempt to secure the com- cept of cryptographically secured containers munication channel between two parties communi- using the IBM Cryptolope technology as an cating over the Internet. example. A summary concludes the paper. Secure Container technology takes a different ap- KEYWORDS proach. Instead of securing the connection, the con- Information Commerce, Multimedia Security, Inter- tent itself is protected. A secure container can be net Security, Secure Containers, Encryption transmitted as user data over a non-secure network. None of the protocols of the network have to be 1 Introduction modified in order to obtain security. Instead, dedi- Information commerce, enabled by the new commu- cated secure container handlers on both the sender nication technologies, is one of the most demanding and the recipient are used together with a clearing applications for security. The reason is obvious, as house to run the secure container transactions. (real) money is inherently involved. Moreover, commerce of multimedia documents can address a 2 Multimedia Security Requirements mass market, being able to handle electronic versions Multimedia applications already pose strong re- of goods like: quirements on the basic functionality of communica- * tion and storage systems and user interfaces. For ex- News, papers, magazines, books (texts and ample, high data rates have to be processed, commu- graphics), nicated, stored or displayed in real-time. Systems * Music, songs, albums (audio), were designed to satisfy the requirements; in order to * Video clips, movies (video), facilitate some problems, data compression tech- niques have been developed. * Computer software (binary data). Regarding security requirements, multimedia sys- The goal of multimedia information commerce is the tems pose the same requirements as standard infor- trade of digital content. Of particular interest is not mation commerce systems: only the data, but also its useright and copyright. The * At the beginning of a transaction, both content range of the communication and business models is provider and client want to make sure that their large. For example, the communications may be respective partner is the one he claims to be, i.e. point-to-point, multicast, or broadcast; the business have to authenticate each other. model may be pay-per-view or subscription; try&buy * Likewise, both parties will require that the con- features may be required. tent is authentic, i.e. that it has been really pub- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 30 lished by the provider, and that the content is Advanced Encryption Standard will fall under this intact, i.e. that nobody has altered it. To be se- category, too. cure from eavesdroppers, the content never Asymmetric cryptographic algorithms (or public-key- should be transmitted or stored in a readable algorithms) use a different key used for encryption format. and decryption. Public-Key-operations are per- * Both authenticity and integrity requirements are formed with key pairs: every message which is en- not only applicable to the content, but also to the crypted with one of these keys can only be decrypted contract. The content provider needs to prove using the other one. If one of these keys is kept se- that a client accepted the terms, and a client cret (the private key) and the other one is published needs to prove he has acquired a certain set of (the public key), asymmetric cryptographic algo- rights. rithms serve two purposes: * Data which is encrypted with a recipient's pub- * Privacy of a client also may be important. No lic key can only be decrypted with the corre- party, sometimes not even the content provider, sponding private key which is only known to the should be able to track which client was pur- recipient. chasing or using which piece of content. * Data which is encrypted with a sender's private Additional requirements come from special proper- key can be decrypted by everybody who is in ties of multimedia data. The immense data volume possession of a copy of the corresponding public which has to be processed, and the produc- key. This property serves as the foundation for tion/consumption pattern of many multimedia appli- digital signatures: The sender signs with the pri- cations favor more advanced communication proto- vate key and the signature can be verified with cols than just point-to-point. Broadcast or multicast the corresponding public key88. communication is used to reduce the network load. The concept of broadcasting or publishing encrypted The most prominent example for an asymmetric content which is purchased and decrypted by the cryptographic algorithm being used for both encryp- customers on demand is called superdistribution tion and digital signatures is RSA; another one which [13]. Even on broadcast systems, a pay-per-view is only suited for digital signatures is the Digital Sig- service should be able to be deployed. A subscription nature Algorithm (DSA). Since asymmetric algo- model is very reasonable for repetitive transactions, rithms are relatively slow, they are never used for the e.g. daily purchases of news, stock prices, journals, encryption of large amounts of data. Today's sys- premium TV channels etc. tems typically make use of the following two con- Several types of multimedia content also draw high cepts: attention to security issues. Movies or music albums * Large amounts of data are symmetrically en- are valuable types of content, address a mass market crypted with a random key. This so called ses- and thus promise high revenues for both the legal sion key is asymmetrically encrypted using the content owners and content pirates. With traditional recipient's public key and can thus be safely media, professional and amateur piracy of music and transferred. In connection oriented protocols, movies is already well-established and will be even this phase is referred to as key exchange. made easier using recordable digital media without * In the case of digital signatures, one way hash security mechanisms. functions are used to condense the data to be 3 Internet Security Mechanisms signed to a fixed length hash value, which is Most of the current security systems, regardless then encrypted with the sender's private key. whether they are incorporated in protocols or work- Examples for one-way hash functions are MD5 ing stand-alone, are based on cryptographic algo- or SHA. rithms. In this section, the main characteristics of Interested readers may consult a number of excellent some cryptographic algorithms are explained and books on cryptography, e.g. [11], and its use for se- their use in secure electronic commerce applications cure electronic commerce solutions [5]. is outlined. 3.1.2 Rights Management Language 3.1 Building Blocks Of Security Solu- The use of cryptography helps a lot to achieve secu- tions rity: only the owner of the right key is able to de- crypt and use encrypted information. Content pro- 3.1.1 Cryptographic algorithms viders may wish to express more complex terms and Cryptographic algorithms can generally be divided conditions of usage, though. For example, they may into two categories. In the case of symmetric crypto- restrict the operations for a client (view only, copy graphic algorithms, the same key is used for encryp- tion and decryption. Commonly found examples for this kind of algorithms are DES or RC4; the new 88 Of course, the verifier has to trust the correctness of the public key. This can be accomplished by providing pu- blic key certificates. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 31 once), offer rebates under special circumstances data into the digital documents. This allows for (club memberships, mass rebates). Such terms and example to embed usage restrictions such as conditions cannot be controlled by mere key owner- "copy once" to be encoded in digital movies. ship. Instead, flexible licensing mechanisms with so- called rights management languages (RML) have to 3.1.4 Tamper-resistant systems be deployed. An RML is used to specify the creden- All these security mechanisms only work properly if tials required by user to access a digital document they are executed correctly at each participating en- and determines the resulting usage rights. An exam- tity. Especially the client station has to be considered ple for an advanced RML can be found in [4]. a major point of attack because it is under full con- trol of a potentially malicious owner. Servers have a 3.1.3 Watermarking higher degree of physical security, but are vulnerable Partners in electronic commerce don't necessarily for insider attacks as well. A solution to ensure secu- know each other, so a content provider may not want rity on all stations are tamper-resistant systems. A to believe that a client adheres to the terms and con- tamper-resistant system tries to detect whether at- ditions and does not violate the copyright. Like in the tempts are made to use it improperly and stops exe- physical world, watermarks, which ideally are not cuting then. reproduceable or removable by an attacker (for at- Tamper-resistance is important, because the infor- tacks see [16]), can be applied to the information as a mation which is sold has a legal usage and thus is tracking mechanism. allowed to be decrypted for this use at the client sta- Digital watermarks [3] are barely perceptible trans- tion, so not only the cleartext, but also the parts of formations of digital data (image, audio or video the system which perform the decryption and the in- data) which can be extracted computationally. The tellectual property protection have to be protected use of digital watermarks enables different scenarios from tampering by applying the mechanisms de- [12]: scribed above to the software itself. An architecture * Ownership watermarks (fingerprints) can be for tamper-resistant code and a classification of the used in order to convey ownership information. possible attacks can for example be found in [1]; In this scenario they identify the recipient of however, also tamper-resistant devices can be broken digital documents and facilitate the detection of [8]. copyright violations. Due to its nature, owner- ship watermarking can only be applied when the 3.2 Securing Connections customer is already known. In the case of super- Security services can be introduced at different lev- distribution, ownership watermarking can only els of the layered structure of the Internet protocols. be done at the client station. Figure 1 shows the four-layered protocol stack of the * Originator watermarks are applied by the con- Internet protocols: The Internet Protocol (IP) is a tent owners in order to mark their copyright or connectionless, packet-oriented transport mecha- automatically trace slight alterations of their in- nism. TCP and UDP are transport layer protocols tellectual property. Additionally, they may be which provide, respectively, connection oriented and visible to prevent undetected illegal copying to connectionless transfer control services to the appli- media outside the system, e.g. with screen cap- cation level protocols. Figure 1 uses the application tures. level protocols HTTP (WWW) and SMTP (e-mail) as examples. * Captioning is an application of digital water- An exhaustive comparison of the security mecha- marking which refers to the integration of meta- nisms described in this section can also be found in Unsecured Internet Layer Transport Application (Standard IP) Security Layer Security Layer Security SHTT SHTTP P S/ S/MI MIME ME HTT HTTP, P, SMTP SMTP HTT HTTP, P, SMTP SMTP HTT HTTP, P, SMTP SMTP HTT HTTP P SMTP SMTP SSL TCP, TCP, UDP UDP TCP, TCP, UDP UDP TCP, TCP, UDP UDP TCP TCP IPSP IP IP IP IP IP IP IP IP Net Networ workk Net Networ workk Network Net Networ workk IPv4 IPv4 + IPSEC IPv4 + SSL PEM, SHTTP, IPv6 IPv4 + TLSP S/MIME Figure 1: Integrating Security Services in the Internet Protocols Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 32 [15]; [14] focuses on the overall building blocks of a W3 Security architecture. Manifest Internet Layer Security. As figure 1 shows, en- cryption and signing of all transmitted data can be Abstract / Metadata integrated into the family of Internet protocols at the Internet layer. As a consequence, these security Key File services are equally available for all application protocols, which do not even have to be recompiled Encrypted Encrypted in order to benefit from the security infrastructure. Content PEK Record An IETF working group called IPSEC is in the proc- ess of standardizing the necessary protocol structures which will be available as an addition to the Internet Encrypted Encrypted Protocol in its current version (the so called IP Secu- Content PEK Record rity Protocol IPSP) and as a part of the next version IPv6. The proposals are based on the use of DES for Encrypted bulk data encryption and MD5 for hashing; a mecha- Master Key nism for performing key-exchange has not yet been standardized. Terms and Conditions Since they involve changes to the basic Internet protocol, the main use of IP layer security mecha- Fingerprinting and nisms is currently in routers and firewall solutions Watermarking Instructions in order to implement security gateways and virtual private networks. Digital Certificates Transport Layer Security. Transport layer security means protection of the transmitted data above the transport layer. The most prominent example of Figure 2: A Cryptolope Container transport layer security is Netscape's Secure Socket 2. Confidentiality: Data to be transmitted is en- Layer (SSL), which is layered on top of TCP [6]. crypted with the session key. SSL provides the services to authenticate a server, 3. Integrity: Additionally to the user data, a mes- and optionally a client, to encrypt a session, and to sage authentication code (MAC) is generated authenticate messages. and transmitted. An IETF working group is in the process of stan- The application-independence of SSL has the disad- dardizing a so called Transport Layer Security Pro- vantage that it can only offer point-to-point protec- tocol (TLSP), which is in most aspects based on tion of the data during the communication process. SSL. In both the source and destination systems the data is SSL is intended to protect a single connection be- in the clear. It is not within SSL's capabilities to tween two communicating applications at the socket protect the data when a host is compromised or to layer. It protects any higher level protocol built on detect and fix the problem when a key is compro- sockets, such as Telnet, FTP or HTTP. In order to mised. achieve this, SSL places two layers on top of TCP. Application Layer Security. Finally, as shown in The lower layer is the SSL Record Protocol which is figure 1, security services can be integrated into the used for encapsulation of various higher level proto- Internet protocols at the application level. This refers cols. The upper layer is the SSL Handshake Protocol. to the design of new or the adaption of existing ap- It allows the end systems to authenticate each other plication protocols in order to integrate security fea- and to negotiate an encryption algorithm and cryp- tures into the protocol elements. tographic keys before the application protocols start One example of this approach is SHTTP, an exten- to transmit over the encrypted channel. sion of HTTP for security services [17]. SHTTP is a SSL in version 3 supports the use of several different superset of HTTP and adds authentication, confiden- symmetrical algorithms for the encryption of bulk tiality, integrity and non-repudiation. The system is data (among them DES and RC4). Integrity checks not tied to any particular cryptographic system, key are based on MD5 or SHA hash functions, several infrastructure, or cryptographic format. Messages are public key algorithms are supported for performing encapsulated within SHTTP in various ways includ- an initial authentication. The credentials used for ing encryption, signing, or MAC based authentica- performing the initial authentication and key ex- tion. Messages may be encapsulated multiple times change operations are X.509 certificates. to achieve multiple security features. Header defini- In detail, SSL provides the following security serv- tions for key transfer, certificate transfer, and similar ices to the higher protocols: administrative functions are provided. 1. Authentication: The identities of the server and SHTTP does not rely on a particular key certification optionally also of the client are verified. scheme. It includes support for RSA, in-band, out-of- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 33 band and other forms of key exchange. Public key IBM has coined the name CryptolopeTM (crypto- certificates can be provided in a message, or ob- graphic envelope) for its document encapsulation tained elsewhere. As in SSL, client public keys are technology [see 4]. There are others, for example not required if client authentication is not needed. DigiBoxTM [18] or a system for the electronic distri- Similar mechanisms are available for other applica- bution of audio data proposed by AT&T Labs [9]. tion protocols as well: PEM and S/MIME, for exam- As shown in figure 2, a cryptolope consists of multi- ple, are used to realize secure electronic mail and ple parts. In addition to the encrypted document, a SSH is in widespread use for secure remote com- cryptolope contains a clear text description of the en- mand execution and file transfer. crypted content which serves to support a user's pur- 4 Protection on the Document Level chase decision. The metadata gives information For multimedia applications, the solutions presented about the contents as a whole, such as author, size or in the previous section have several shortcomings. format and instructions on how the content may be The protected multimedia documents are separated purchased. The "real" information is stored in the encrypted content parts. For each part, a different from the associated usage rights and conditions. part encryption key (PEK) is chosen. The PEKs are -There is no way for the user to prove that a docu- themselves encrypted using a master key and stored ment was received under certain usage conditions. in the key records of the cryptolope. Once the document is transmitted to the user, these A Cryptolope Container The cryptolope further con- usage conditions cannot be enforced. tains the terms and conditions describing the rights -The content is decrypted at the end of the communi- associated with the content and fingerprinting and cation channel. This is acceptable if the content is watermarking instructions which specify when and only shown or played, but not if it would have to be how identifying information is to be added to the stored in the clear at the client station. documents. Digital signatures and certificates in- cluded in the cryptolope serve the purpose to -A connection oriented security mechanism does not authenticate the contents and optionally the users [7]. allow superdistribution of larger amounts of data. A cryptolope is created by the provider of content Document protection requires the document to be and can be distributed on arbitrary channels. Its secu- rity is inherently guaranteed because everybody can Content Provider / Packer check the checksums and signatures, so nobody can tamper with a cryptolope and nobody can use the 1. Pack cryptolope content without purchasing the PEKs. 2. Distribute cryptolope The purchasing transaction requires a clearing center Su which acts on behalf of the content provider. A client pe Royalty / License Clearing Center who decides to buy some content is directed by the rdis cryptolope instructions to an appropriate clearing 6. Receive buy message tri center. The buy request message contains the en- 7. Decrypt, re-encrypt master keys bu crypted PEK and public key certificate. The clearing 8. Send license message tio house knows the master key (which could be its own n private key or a shared secret symmetric key), de- User / Opener and Player crypts the PEK and re-encrypts it using the client's public key. After the client received the license mes- 3. Receive cryptolope sage containing the encrypted PEK, it can decrypt it 4. Decide to buy content using its private key and use it to decrypt the content 5. Request keys in buy message itself. Figure 3 depicts the cryptolope process [10]. 9. Receive licence message A cryptolope-based solution is well suited to meet 10. Decrypt and use content multimedia security requirements: 1. Entity authentication is needed just between cli- Figure 3: Cryptolope processing wrapped in a secure container at the content pro- ent and clearing house: the content provider vider's site, and only to be unwrapped at the end needs not to have a special relationship with user's computer. As a result, no further protection is each user. needed, neither for the communication channel nor 2. Every cryptolope and every message is digitally for the intermediate servers. Also, all of the intents signed and includes the certificate of the signer, of the content provider (protection, marking, etc.), so it can be checked easily. The signature proc- and all the terms and conditions he is offering, can ess is explicitly driven by the end user, so the expressed in a tamper-evident digitally signed pack- signature can be considered as an expression of age. This enables superdistribution; the package can free will to sign a contract. be moved freely from place to place without losing 3. Checksums and signatures of the content parts its intactness, its authenticity, and its associated allow to check the authenticity and integrity of terms and conditions. the content. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 34 - Verifies Usage Conditions - Performs Payment Functions - Issues Licences Clearing Center - Originator Watermarking - Secure Packing - Tamper Resistant - Defines Usage Superdistribution Opener Conditions - Ownership with RML Watermarking Publisher User PC - Digitally Signed - Authenticates Publisher Stefan Nusser almaden.ibm.com 137.208.4.7 (and User if Desired) Cryptolope - Contains Usage Conditions Figure 4: Use of security building blocks in the cryptolope architecture 4. Each encrypted part is confidential and can only process, but not before and afterwards. The control be decrypted by an owner of the key, i.e. the of the use of the information after the transmission content provider who created this key and the becomes a major requirement, though. client who buys the key from a clearing center. Secure container technology promises to be a solu- A clearing center is able to decrypt and sell the tion to this problem. Here, the main idea is to encrypt key, but generally does not decrypt the content. the information at its source and provide a means for The information is in clear text only at the con- a consumer to be able to decrypt it on demand. The tent provider's and the client's side within the information is encrypted and packed into a secure cryptolope processing environment. container which contains additional information, e.g. 5. As cryptolope processing requires dedicated what information is contained, what its price is, or opener and viewer software running on the cli- where and under which conditions a client can pur- ent, code signing techniques can be applied to chase the unlocking keys. Secure containers can be make the software on the client side hard to distributed via arbitrary, unsecure channels. Clearing tamper with. centers are used to process the purchase transactions. 6. Try&buy applications are possible. Free (per- IBM cryptolopes are an example of secure container haps lower-quality) samples of the content can technology. They can encompass all of the above de- be added in the clear to the cryptolope. With the scribed features and can be used to realize the idea of RML, arbitrary usage patterns can be allowed. superdistribution. Clients do not need to get a cryptolope directly and online from a content provider, but can copy a cryp- 6 Acknowledgments tolope from the nearest cache and purchase the un- The research work described in this paper was per- locking key from any authorized clearing house. formed jointly with Jeffrey Lotspiech and Stefan As a summary, figure 4 shows how the Cryptolope Nusser. architecture makes use of the building blocks of se- 7 References curity. Document layer security does not attempt to [1] David Aucsmith, Gary Graunke: Tamper Resis- secure a specific communication channel; it is not tant Software: An Implementation. In Proc. First even dependent on the Internet protocols as a trans- International Workshop on Information Hiding, port mechanism. 1996. 5 Summary [2] Steve M. Bellovin: Security Problems in the With more and more computer and communication TCP/IP Protocol Suite. In Computer Communi- systems capable to process multimedia data, com- cation Review, Vol. 19, No. 2, April 1989. merce of multimedia data opens a promising market. [3] Hal Berghel: Watermarking Cyberspace. In However, multimedia commerce poses even higher Communications of the ACM, Vol. 40, No 11, security requirements than established electronic November 1997. commerce systems. This paper discussed different approaches to add security mechanisms to existing [4] M. Blaze, J. Feigenbaum, J. Lacy: Decentralized Internet protocols. Trust Management. In Proc. 1996 IEEE Sympo- Internet security systems which protect communica- sium on Security and Privacy. tion channels often are not sufficient to meet the re- [5] Warwick Ford, Michael S. Baum: Secure Elec- quirements of multimedia document commerce: the tronic Commerce. Prentice Hall, 1997. data is only protected during the communication Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 35 [6] Alan O. Freier, Philip Karlton, Paul C. Kocher: The SSL Protocol Version 3.0. IETF Internet- Draft, 1996. [7] Marc A. Kaplan: IBM Cryptolopes, SuperDis- tribution and Digital Rights Management. Working Paper, V1.3.0,12/96. http://www.research.ibm.com/people/k/kaplan/. [8] Markus Kuhn, Ross Anderson: Tamper- Resistance: A Cautionary Note. In Proc. Second USENIX Workshop on Electronic Commerce, 1996. [9] Jack Lacy, James Snyder, David P. Maher: Mu- sic on the Internet and the Intellectual Property Protection Problem. White paper, http://www.a2bmusic.com/about/papers/. [10] J.B. Lotspiech, U. Kohl, M.A. Kaplan: Crypto- graphic Containers and the Digital Library. In Proc. VIS '97, Vieweg Verlag, October 1997. [11] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptogra- phy. CRC Press, October 1996. [12] F. Mintzer, J. Lotspiech, N. Morimoto: Safe- guarding Digital Library Contents and Users ­ Digital Watermarking. In D-Lib Magazine, De- cember 1997. [13] Ryoichi Mori, Masaji Kawahara: Superdistribu- tion: The Concept and the Architecture. In Transactions of the IEICE, Vol. E 73, No. 7, July 1990. [14] Gustaf Neumann, Stefan Nusser: A Framework and Prototyping Environment for a W3 Security Architecture. In Proc. CMS'97, Chapman & Hall, September 1997. [15] R. Oppliger: Internet Security ­ Firewalls and Beyond. In Communications of the ACM, Vol. 40, No. 5., May 1997. [16] Fabien A.P. Petitcolas, Ross J. Anderson, Mar- kus G. Kuhn : Attacks on copyright marking systems. In Proc. Second Workshop on Infor- mation Hiding, 1998. [17] E. Rescorla, A. Schiffman: The Secure Hyper- Text Transfer Protocol. Internet-Draft, March 1997. [18] Olin Sibert, David Bernstein, David Van Wie: The DigiBox: A Self Protecting Container for Electronic Commerce. In Proc. USENIX 95 Electronic Commerce Workshop. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 36 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 37 Video Protection by Partial Content Corruption Carsten Griwodz Darmstadt University of Technology Merckstr. 25 * D-64283 Darmstadt * Germany Tel.: (+49) 6151 166159 griff@kom.tu-darmstadt.de MOTIVATION parse the MPEG video. Still, each byte of the video data is manipulated once for each transmission. Many on-demand applications require that Kunkelmann et al. present [3] a variety of ap- the same content is delivered to many dif- proaches to the partial encryption of the complete ferent receivers in short sequence. In video video stream for use with a security gateway. They on demand the goal of the content provider consider a partial encryption of 10% of meaningful is the frequent sale of content in the most data appropriate for VoD applications, while full popular phase of their life cycle [1], which protection requires a major part of all data to be en- could be exploited by the introduction of crypted to prevent reconstruction. All of these ap- caching and prefetching techniques [6]. It is proaches are compute intensive and put a heavy not commercially feasible to restrict content strain on a VoD server. Kunkelmann et al. report an access to a small group of receivers. increase of CPU utilization by 10.5% for the play- back in comparison to unencrypted content. For such applications we want to provide a In the typical design of throughput-oriented com- simple approach that is able to protect the mercial video servers, the computing power is con- content owner from data theft in the wide sidered sufficient for the envisioned scenarios. This area network while protecting the infra- does not hold when the server re-encrypts the con- structure from an unnecessary number of tent for each customer of the service in real-time. transmissions. We want to provide a The use of caching and pre-distribution with an ac- straightforward mechanism for these appli- ceptable compromise to protection reduces further cations which can interoperate with caching the load on servers and networks. Figure1 shows a systems as well as reasonably powerful serv- sketch of the distribution system we envision for ers. The mechanism should be computation- our approach. From a video, we create two files by writing bytes from the original video to a small data ally cheap, in order not to overload the slice and destroy those bytes in the original. When server with the task of modifying the con- the larger part of the video is corrupted in this way, tent (e.g. watermarking or encryption) for it can be distributed freely because it is useless by an arbitrary number of concurrent unicast itself, while the small slice is protected and uni- transmissions. We believe that partial con- casted on demand. The unicast access informs the tent corruption provides similar protection content owner of each use. The corruption is con- for video content as full content encryption tent-independent, the small slice is encrypted on the but can still make efficient use of caching server side using a personal key of the receiver. The and pre-distribution for the bulk of the con- computational load of encrypting this portion of the tent, using protected unicast only for a video is relevantly below that of content-aware methods. At the receiver's side, the unicasted slice minimal amount of data. We propose a is decrypted and synchronized with the main part of novel scheme for inhibiting and investigat- the data coming from a cache server. For synchro- ing copyright violations. nization the methods described in [2] can be ap- 1 Protecting the Cache plied. The initial approach towards video encryption was encryption of the whole stream. Various more effi- cient encryption algorithms were implemented. Maples and Spanos present in [4] an approach of encrypting only I-frames of MPEG videos. Qiao et al. [5]) propose a video encryption algorithm that works exclusively on the data bytes and does not Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 38 Figure 1: Distribution System For videos encoded in MPEG-1, Huffmann encoding If an attacker would look for these infrequent bytes improves the effectiveness of the corruption of single in the same way, he could identify them if the inser- bytes of data. Since the Huffmann algorithm is bit- tion of the values would still leave them the least oriented rather than byte-oriented, a Huffmann de- frequent. Since the entropy of MPEG streams is ex- coder is unable to recover from the error for the rest tremely high (we found entropy values between of a data segment. Furthermore, a complete Huff- 97.4% - 99% in our example videos), even a single mann decoding of the data is necessary before the insertion of a value might make a different one least corruption is detected. As a result of this error propagation from a corrupted byte to the rest of a data segment in a frame, the number of bytes that need to be destroyed to corrupt compressed data is much lower than for an uncompressed frame. Thus, the destruction of larger blocks with the same overall ratio of corrupt to correct bytes is not feasible. The corruption of single bits may be as efficient as the corruption of bytes, but it increases the computa- tional load. We considered potential attacks to the scheme. In experiments we distinguished the selection of fixed or variable byte values used for the corruption of the original stream, and the applications of this corrup- Figure 3: Rare values tion at periodic or variable offsets from each other. An attacker can identify both a periodic offset (by frequent. the use of auto-correlation) and a fixed replacement It is known that header reconstruction is simple when value (by gathering statistics on frequencies, see the encoder is known, so we conducted our experi- Figure2). Both information should be concealed as ments with reconstructed headers. The remaining er- good as possible. rors are disturbing enough to yield results that are To prevent the identification of offsets it is essential to vary them. We use the Poisson distribution to compute offsets because of its memory-less property and select a random seed per video. The seed value is distributed to the receiver at the start of the en- crypted unicasted transmission. The receiver's im- plementation of the distribution function must be- have identically to the sender's to find exactly the same bytes. Figure2 shows that constant values are easily detected. Since the value is irrelevant for the reconstruction, we use values that are well hidden in the stream instead. At each insertion point, we insert Figure 2: Fixed Value the least frequent byte from the beginning of the file, counting the number of occurrences of bytes in the unacceptable for commercial exploitation. We corrupted rather than the original file (see Figure3). started experiments with a destruction ratio of 1%, which rendered videos (with correct headers) un- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 39 playable to two MPEG players (ActiveMovie, Vid- that a least one byte error remains. For a 1GB eoCharger Player) and showed nothing but artifacts MPEG-1 video, 0.5% encrypted transmission, bytes in another (MpegTV). We found 0.5% to deliver bad (resulting in a byte error rate in the video) and , this quality and 0.1% to provide a quality sufficient to computes to 0.537. Smaller intervals increase this read text in large font which remains unmoving for probability considerably. several seconds. All of our numbers are adequately However, the necessary length of the video for the above current capabilities of restoration to good application of this idea is large, so further investiga- quality which handle bit error rate of about to 10-4 tions are necessary to understand whether this is fea- well. sible. 2 Protecting the Delivered Video 3 Conclusion The scheme presented so far protects from the theft We have presented a novel scheme for the protection of data that is located in caches. However, the of copyright in commercial video-on-demand sys- authenticated receiver of the video, who has the full tems that use caching and pre-distribution. The quality data available, may choose to record and re- scheme exploits the error propagation of Huffmann sell it. We consider the insertion of random se- encoding to corrupt large parts of a video, which can quences of very scarce bit errors into the unicast then be distributed freely, while the information that portion of the stream means, not to prevent, but to is necessary to reconstruct the content is delivered in prove copyright violation. Like watermarking, this a secure way. To help proving resale of videos by can be exploited to prove copyright violation in a authenticated customers, we propose to add the in- way that makes the danger of manipulation to the sertion of infrequent byte errors to this scheme. decoder software irrelevant. The unauthorized reseller may decide to request the 4 References video multiple times in order to use a voting mecha- [1] C. Griwodz, M. Bär, L. C. Wolf: "Long-term nism and eliminate the bit errors (since we assume Movie Popularity Models in Video-on-Demand that the technique is known). It is relevant to find a Systems or The Life of an on-Demand Movie", scheme that will yield a sufficiently large number of ACM Multimedia 1997, November Seattle, WA, remaining bit errors to single out the unauthorized USA, November 1997 reseller and take further measures to prove the con- [2] J. Jarmasz, N. D. Georganas: "Designing a Dis- tract violation. Bit errors that remain after the execu- tributed Multimedia Synchronization Sched- tion of voting steps to eliminate bit errors can be uler", Proc. IEEE Multimedia Systems'97, Ot- identified by the content provider using a brute force tawa, June 1997 approach of computing these values based on the [3] T. Kunkelmann, R. Reinema, R. Steinmetz, T. seed values on file. Blecher: Evaluation of Different Video Encryp- We have examined a couple of schemes that insert tion Methods for a Secure Multimedia infrequent bytes into the video stream randomly and Conferencing Gateway, Proc. of the 4th Int'l found that completely random errors are easily fixed COST237 Workshop, Lisboa, Portugal, Dezem- by applying voting mechanisms. Our current idea is ber 1997, pp. 75-89 to choose for each video a random sequence of inter- vals of the unicast portion. For each delivery of the [4] T. B. Maples, G. A. Spanos: "Performance stream, a uniform distribution is applied to put one Study of a Selective Encryption Scheme for the byte error into each interval. Similar to the distor- Security of Networked, Real-Time Video", tions of a watermark, each copy can be identified by Proc. of the 4th Int'l Conf. on Computer Com- these randomly inserted errors when the provider munications and Networks, Las Vegas, Nevada, keeps the random seed values in a database. If un- September 1995 authorized copies of the video are uncovered, the bit [5] L. Qiao, K. Nahrstedt, I. Tam: "Is MPEG En- error sequences can be compared with the series of cryption Using Random Lists instead of Zig Zag bit errors which are generated by the seed value on Order Secure?", IEEE International Symposium file using a brute force approach. on Consumer Electronics, December 1997, Sin- If the attacker chooses a 3-copy voting to eliminate gapore the bit errors, errors remain with some probability [6] R. Tewari, M. Dahlin, H. M. Vin, J. S. Key: that can be used to identification the original cus- "BeyondHierarchies: Design Considerations for tomer. Let the length of the video be Sf, the unicast Distributed Caching on the Internet", UTCS portion Su, with . If the average offset is O and the Technical Report TR98-04, UTexas, 1998. length of each interval is I, there is a probability of Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 40 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 41 Applying Encryption to Video Communication Thomas Kunkelmann Darmstadt University of Technology Information technology Transfer Office Wilhelminenstr. 7 64283 Darmstadt, Germany kunkel@ito.tu-darmstadt.de ABSTRACT TV, VoD). The expense to break into an encryption scheme needs not to be high, but it should be more In multimedia communications, the need for expensive than the legal access to the video service. confidentiality and privacy gains more and In all these distributed multimedia applications, the more in importance, particularly in open cryptographic functionalities must cover different networks like the Internet. This paper pres- aspects of security, like confidentiality, integrity and ents an overview of the security requirements authenticity. Therefore different modules of encryp- of multi-media conferencing systems and of tion mechanisms must be available to the ap- applicable security functions. For real-time plication. Scalability for encryption methods can be video trans-missions there is a special need achieved by partial encryption of multimedia data. for se-lective encryption of the transmitted The main focus of this paper considers encryption data. Existing methods are investigated and methods to provide confidentiality, since their appli- cation to multimedia data streams will cause time- their strengths and weaknesses will be critical problems when encrypting the whole data shown. stream. Besides integrity checks, the other security Besides video standards like MPEG and functionalities do not cause any problems concerning H.261, scalable video codecs become more the real-time constraints. and more popular. A scalable codec trans- The rest of this paper is organized as follows: Sec- mits a video signal in different layers, each tion 2 deals with general aspects of combining mul- encoded at its own bit rate. Applying encryp- timedia data with encryption. Section 3 presents tion methods to them is a straightforward some methods for the partial encryption of video task and can be integrated easily. data streams. Those methods will be evaluated for MPEG video compression in Section 4. In Section 5 KEYWORDS the application of partial encryption to scalable video Multimedia communication, Security, Encryption, is presented. Section 6 concludes this paper. Partial encryption 2 Multimedia Data and Encryption 1 Introduction Several multimedia data formats require a special Communication and cooperation in heterogeneous treatment in terms of encryption. In particular, these distributed environments are playing a rapidly in- are data formats with real-time properties, like audio creasing role in the business processes of today's and video communication. Here encryption methods enterprises. Nowadays several enterprises with dis- cannot be applied straightforward due to the severe tributed locations shift their personal communication time constraints for data processing and the com- and meetings more and more to so-called virtual plexity of secure encryption standards. Either en- meetings via computer links. In these cases confiden- cryption must be realized with special hardware, tial information has often to be passed securely over which is not available on many platforms, or the data open networks like the Internet. streams have to be subdivided in order to separate Another kind of distributed multimedia applications data portions relevant to the human perception for with a high demand for security mechanisms are encryption. The latter case is known as partial en- video databases and video-on-demand (VoD) serv- cryption schemes. ices. The security policy for these applications is not focused on optimal protection of highly confidential 2.1 Data Formats For Video Transmis- data, rather on protecting data against illegal access. sion Therefore the encryption methods needed here tend For the partial encryption of multimedia data it is to be fast, with respect of the high data bandwidth of important to see how video data is organized in the video streams, and to be cheap to implement in order data stream, in order to develop applicable methods to supply an emerging market of private users (Pay- for extracting the relevant data portions. Therefore, a Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 42 short survey over the common data formats used in The H.261 standard also specifies many format pa- toady's video conferencing systems is presented. A rameters. The resolutions supported by H.261 are more general survey can be found in [1] and [2]. CIF (Common Interface Format, 352×288 pixels) 2.1.1 Motion-JPEG and QCIF (1/4 CIF). The frame rate is defined as The Motion-JPEG (M-JPEG) video format is not 29.97 fps. The encoding schemes for H.261 are standardized, it consists of a sequence of single similar to those used in MPEG. video images (frames) encoded with the JPEG for- 2.2 Performance Aspects For En- mat [3]. The JPEG image encoding technique leads crypted Video to a high compression ratio for continuous-toned im- As pointed out in [6], modern high-performance ages. It is based on a combination of applying the workstations and servers are capable of playing Discrete Cosine Transformation (DCT) to blocks of MPEG-1 or M-JPEG video, leaving about 20 to 60 8×8 image pixels, followed by an entropy coding [1]. percent CPU time for other jobs when using hard- The M-JPEG video format is used mainly for video ware JPEG support. On most desktop workstations conferencing tools due to a symmetrical expense for such a computing power is not available. Here the encoding and decoding. frame rate or the pixel resolution has to be reduced to 2.1.2 MPEG-1 and MPEG-2 meet the limited CPU capacity. Performance meas- The MPEG format for coding and transmitting video urements on a PC (100 MHz Pentium, Linux) signals along with the corresponding audio informa- showed that such a system can playback about three tion has been standardized by the ISO [4]. For H.261 QCIF video streams with frame rates suffi- MPEG there are three different standards specified, cient for video conferencing (between 11 and 12 MPEG-1, MPEG-2 and MPEG-4 (standard sched- fps). uled for November 1998). MPEG-1 is today's com- Table 1 shows the performance evaluations of sev- monly used video compression standard due to its eral hardware platforms decrypting video streams in availability for many platforms and appropriate software, with standard library implementations of hardware support. It covers data rates of about 1.2 to the DES algorithm. The reason for investigating DES 1.85 Mbit/s. An MPEG data stream is formed of dif- is the fact that cryptanalysists consider it to be a safe ferent layers, responsible for the synchronization of algorithm for ciphertext-only and known-plaintext audio and video, and providing pre-defined starting attacks, except for its small key space. points for re-synchronization. MPEG utilizes the For most scenarios, the need for reducing the en- compression techniques of JPEG, along with inter- cryption effort is obvious, the slower workstations frame relationships (prediction and motion compen- are already overloaded with the DES decryption. For sation). the H.261 scenario, an encryption CPU usage of 20 2.1.3 H.261 and H.263 percent implies a frame reduction from e.g. 11 to 8.8, H.261 and H.263 are widespread standards adopted violating the lower bounds for human image percep- by the ITU [5] for transmitting video data streams. tion. Therefore, partial encryption is a suitable solu- The intention of H.261 is to provide video informa- tion also for this case. tion at a data rate of p×64 Kbit/s (with p {1, ... 30}), 2.3 Integration Of Security Function- matching the ISDN specification. Therefore H.261 is alities In The System toady's mostly used video compression standard for Security functionalities can be built up on two differ- ISDN video conferencing systems. The codec (en- ent layers of a system dealing with the transmission coding and decoding functionality) is designed for a of digital video information: symmetrical encoding and decoding process with a maximum end-to-end delay of 150 ms. DES CPU usage 1.5Mbit MPEG 2Mbit M-JPEG 3×128 Kbit H.261 Intel Pentium-100, Linux 86.70 % Z115.62 % 21.67 % DEC Alpha 1000/ 266 65.63 % 87.50 % 16.41 % Sparc 20 (Solaris) 76.01 % Z101.34 % 19.00 % Sparc 4c (SunOS) Z312.77 % Z417.03 % 78.19 % Table 1: CPU utilization of different hardware systems for DES software encryption (Z Z = projected values). The MPEG and M-JPEG cases represent e.g. Pay-TV scenarios (16 - 25 fps), while the H.261 scenario describes an ISDN video conference with three video channels open (12 - 15 fps). Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 43 H DC AC AC AC H DC AC H DC AC AC AC AC H DC AC AC AC ... Figure 3: Encrypted parts of a video stream with the partial encryption method of [7]. (H: Header data; DC: low frequency (DC) coefficient; AC: higher-frequency DCT coefficient) * Security in the transmission or networking layer, stream. In level 2 a subset of DCT blocks is selected, i.e., security is already provided by the network- which will be partially encrypted, while level 3 en- ing protocol used (e.g., SSL, RTP [8], ATM [9]). crypts all intracoded image information. An additional data manipulation by security ap- 3.2 Partial Encryption Of Intracoded plications is not necessary. * Security in the data layer, i.e., before data is Frames transmitted from a sender to a receiver it will be Some work has been done in partially encrypting manipulated by the appropriate security functions only the intracoded frames (I-Frames) of an MPEG in the application. The security functionality can stream [12] or the intracoded blocks in intercoded either be applied to the application, or the ap- frames. In [13] an example of this kind of encryption plication itself is designed to gain security for is given, the authors also show the limits of this tech- other programs, e.g. the Secure Shell (SSH) [10]. nique. Video sequences with a high degree of motion One of the drawbacks of network layer security still show a lot of details of the original scene. As a mechanisms is the need for secure underlying trans- remedy the increase of intracoded- frames is sug- port protocols, which are not available at the mo- gested, but this will also vastly increase the size of ment. IPnG and ATM will provide these functionali- video data. ties in the near future. The advantage of data layer 3.3 Permutation Of DCT Block Infor- security is that the transmitted data can be subdi- mation vided into parts with sensitive and insensitive data A method for an encoding/ decoding process with no with respect to the human perception, necessary for significant delay resulting from additional encryption partial encryption methods. is applicable to video compression techniques based 3 Partial Video Cryption Methods on the JPEG algorithm. In [14] this method is de- Considering the results from performance measures scribed for the MPEG standard. It is based on the in secure video systems, several methods for partial zigzag ordering of the DCT coefficients before en- encryption of video data have been proposed in the tropy coding is applied, which is randomly per- last few years, which are summarized in this section. muted. The drawback of this method is the worse 3.1 SEC-MPEG performance of the run length encoding, which re- sults in an expansion of the encoded video data of SEC-MPEG [11] is a toolkit for partial encryption of about 20% to 40% for the tested video sequences. MPEG-1 data. The aim of this toolkit is to achieve confidentiality and integrity checks. Confidentiality 3.4 Reducing The Amount For Strong is achieved by using the DES algorithm, integrity Encryption checks are carried out by a cyclic-redundancy check Statistical analysis of MPEG streams show that it is (CRC). The toolkit supports four levels of confiden- still sufficient to reduce the effort for encryption to tiality, beginning with encrypting the header infor- one half of the video stream, and use these data as a mation, up to an encoding of the whole MPEG Figure 4: Maximal possible reconstruction for intracoded block encryption (center) and with the method of [7] (right), both frames with about 46% encrypted data (video flowers, 1/2 original size, the original image is shown left). Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 44 Figure 5: Video sequence biker (left) with 25% encrypted data, playback (center) and maximal possible recon- struction (right) one-time pad for the other half of the stream, in order probably reconstruct a video frame as in the exam- to obtain a strong cryptographic protection for the ples of figure 2. Here the non-reconstructible pro- whole MPEG data [15]. The method needs about tected information is set to zero, otherwise the ran- 53% of the effort for encrypting the whole data dom encrypted information would still obscure the stream, its drawbacks are the usage of multiple en- reasonable information. cryption keys and the overwriting of some MPEG These examples motivate to protect truly confidential header fields, which makes the solution infeasible for video information with an adequate method, e.g. the most existing applications. scalable approach presented in [7]. In other scenar- 3.5 Scalable Method For JPEG-Based ios, where encryption is merely used to aggravate the Video access for the public, e.g., video-on-demand systems, the expense for reconstructing parts of a video is out In [7] we present a scalable partial encryption of all proportion to the fee for joining the movie method, which allows a security level of nearly broadcast legally. In these scenarios, a simple en- every granularity. It can be applied to all video com- cryption method might be considered as sufficient. pression methods based on the JPEG standard, in particular the formats mentioned above. This method 4.2 Experimental Results is not prone to the motion prediction problems men- All experiments are based on a series of different tioned in 4.2. Our method takes advantage of de- video sequences, which reflect several scenarios creasing importance for the image composition of where digital video can be used. Movies are repre- the DCT coefficients, so it is sufficient to encrypt sented by the videos flowers, biker and coastguard, only the first few of them. The algorithm starts with while akiyo is an example for a video conference encrypting a data block at the beginning of a DCT scene. block and guarantees the protection of at least the In VoD scenarios the encryption effort need not to be first n DCT coefficients of a block, encrypting con- high, even with a few percent of encrypted data the secutive data portions in the video stream of the en- quality of the video material becomes intolerably cryption method's block size. The parameter n of en- poor [16]. In Figure 3 an example for an encrypted crypted coefficients provides scalability for the secu- video image with about 25% of the data encrypted is rity level. Table 1 gives an example (with n=3), presented. About 10 percent encryption can be con- which parts of an MPEG stream will be encrypted. sidered as a satisfactory level for VoD applications, which complies with the fact that here the software 4 Evaluation of Results and hardware effort must be minimized to keep the First, some aspects on the safety of partial encryption costs per set-top unit cheap. methods for video data are presented. Based on these For truly confidential video sequences it is not suffi- considerations, a comparison of the different meth- cient at all to pick some few video blocks or DCT ods with respect to safety, time consumption and coefficients for encryption, as it is done in most par- communication overhead is given. tial encryption schemes. Here the approach in [7] is a 4.1 Possible Reconstruction Of Pro- good choice for partial encryption. When using our tected Data scalable approach it is necessary to protect at least With methods used in cryptanalysis, e.g., statistical the first 10 to 12 DCT coefficients in order to keep a and entropy evaluations, it may always be possible to high level of confidence. This results in an en- detect those portions of a data stream which have cryption rate of 40% or more of the video data. been encrypted. However, this will be a difficult job 4.3 Comparison Of The Encryption for partially encrypted (MPEG or similar encoded) Methods video streams due to the nearly redundancy-free In Table 2 the different partial encryption methods Huffman encoding. An eavesdropper who succeeded are compared with respect to security, scalability, in analyzing a partially encrypted video stream might time effort, and protocol signaling overhead. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 45 An important factor is the signaling or control data formation. These refinement data are needed to re- overhead an encryption scheme generates. These construct the frames within the CIF layer from those data can be embedded in the video stream as it is transmitted in the base layer at QCIF resolution. The done in SEC-MPEG with a special encryption header scalable codec combines low complexity downsam- flag, or it can be transmitted via a separate control pling and interpolation filters with highly efficient channel. A complete comparison of different partial E8-lattice vector quantization. Decoder complexity is encryption schemes can be found in [17]. 5 Encryption of Scalable Video QCIF, 30 Hz ... Streams CIF, 30 Hz I P P P Besides video standards like Motion-JPEG, MPEG ... and H.261/H.263, scalable video codecs are becom- I P P P ing more and more popular [18]. A scalable codec transmits a video signal in different layers, each en- Size of GOP: 15 frames coded at its own bit rate. Therefore it is possible to decode an already encoded video at different bit rates Figure 7: Spatial resolution pyramid used for the without any additional content parsing. scalable codec 5.1 Scalable Video Coding With A Spa- sufficiently low to allow software-only implementa- tial Resolution Pyramid tions on today's PCs and workstations [6]. Encoder The scalable video codec that is investigated here is complexity is mainly determined by motion estima- based on a spatial resolution pyramid [19]. Figure 4 tion as it is also the case for all standardized motion- shows this two-layer pyramid. The original video compensated hybrid codecs. Similar to MPEG and signal is decomposed into two spatial layers. The other video compression schemes, I- and P-frames codec expects an input signal corresponding to a CIF are used. Motion-compensated prediction is based on resolution at 30 frames per second. Layer 1 contains 16 × 16 blocks. The scalable codec is described in a spatially downsampled version of the original sig- more detail in [18]. Figure 6: Coastguard: Original (left), transparent encryption with 75% protected data (right). Method Security Scalability Time overhead Protocol overhead SEC-MPEG high 3 levels DES encryption about 17 to 32%(own data format) Frame-type encryption high I: 25-40% DES encryption none IP: 70-85% IPB: 99% Intra-block encryption high no DES encryption none DCT permutation breakable no None none, data volume + 20% to 40% Scalable method high full, from 8% to 100% DES encryption 3-5% Table 2: Comparison of different partial encryption methods nal at QCIF resolution, layer 0 contains the signal at its full resolution. 5.2 Partial Video Encryption By using a predictive pyramid coder, the spatial In contrast to the methods mentioned in Section 4, resolution pyramid is transmitted within a base and partial encryption can be easily included into a scal- an enhancement layer, which carries refinement in- able codec. The scalable codec generates a natural partitioning of the video data into more important Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 46 and less important data without requiring additional frame with an `undecodable' base layer is shown in content parsing. The type of scalability used here is figure 6. spatial scalability. Other possible types of scalability are temporal and SNR [4] scalability. Spatial scal- 5.3 Partial Encryption Results For ability allows two different encryption schemes, Mpeg-1 And The Scalable Codec namely base and enhancement layer encryption [20]. In table 3 simulation results for an MPEG-1 and a Figure 8: Akiyo: original video image (left), reconstruction of 50 % partially encrypted video data from an MPEG-1 data stream (center) and from a scalable video stream (right) Enhancement layer encryption is also known as scalable video stream are compared. As test se- transparent encryption. Its purpose is to restrict ac- quences coastguard and akiyo are used. Partial cess to the full video quality only to receivers own- MPEG encryption is done with the method described ing the correct decryption key. Other recipients can in [7]. As can be seen, MPEG-1 needs 1071 kbps to only decode the base layer(s). This scenario makes encode coastguard at a PSNR of 28.7 dB and 123 perfectly sense for Pay-TV applications, where the kbps to encode akiyo at a PSNR of 33.7 dB. The cor- content provider allows free previews at a low qual- responding rates needed by the scalable codec de- ity. The decodable quality mainly depends on the pend on the rate spent within the base layer. The val- number of encrypted layers. For transparent encryp- ues show that at low and medium base layer rates the tion it is important not to encrypt the headers and scalable codec outperforms MPEG-1 in terms of starting sequences of the upper layers, since a de- coding efficiency. coder should be able to discard the information of By comparing the energy values E of both partial en- these layers if it does not possess the correct decryp- cryption methods it can be seen that the protection tion key. Transparent encryption does not require obtained from simple base layer encryption is com- any modifications at the decoder. An example of this parable to the best known partial MPEG encryption kind of encryption is shown in figure 5. method. For akiyo, an even higher protection can be Protecting only the base layer of a scalable video obtained with the same encryption effort. Since base stream can already achieve a good content protec- layer encryption needs no content parsing, its com- tion, since in terms of image perception most of the putational complexity is much lower than partial relevant information is concentrated in the base MPEG encryption. layer. The enhancement layer(s) only cater for minor details in the video scene and can be left unprotected 6 Conclusions in many cases [20]. An example for a reconstructed This paper pointed out the security requirements needed for multimedia communication. A special sequence encryption MPEG-1 Scalable Codec (CIF, rate bit PSNR E bit PSNR E 30 Hz) percentage rate [dB] rate [dB] [kbps] [kbps] ~25 % 344 948 29.4 212 coastguard ~50 % 1071 28.7 162 984 28.9 130 ~75 % 49 1044 28.4 91 ~50 % 103 122 33.7 32 akiyo ~66 % 128 33.9 61 132 33.6 22 ~75 % 43 136 34.9 13 Table 3: Simulation results for partial encryption obtained with MPEG-1 and the scalable codec. Encryption rate percentage is the percentage of the encrypted bit rate with respect to the overall bit rate. For the scalable codec this percentage is identical to the percentage of the base layer bit rate with respect to the overall bit rate. The overall bit rate is the bit rate needed for transmitting a test sequence at the given PSNR. E denotes the en- ergy contained in the decodable frames after the given rate percentage has been encrypted. All values are com- puted as averaged values over the first 100 frames of each test sequence. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 47 treatment has to be applied for real-time video data [9] The ATM Forum: ATM Security Framework due to the large amount of data to be protected. Par- 1.0. AF-SEC-0096.000, 1998 tial encryption is a solution to solve this problem. [10] T. Ylönen: The SSH (Secure Shell) Remote MPEG-1/MPEG-2 and H.261/H.263 are widespread Login Protocol. http://www.cs.hut.fi/ssh/RFC, compression standards used in most of today's video 1995 conferencing applications. They are well suited for partial encryption because on the one hand they [11] J. Meyer, F. Gadegast: Security Mechanisms for make use of DCT, which has a high potential for di- Multimedia Data with the Example MPEG-1 viding data in more relevant less relevant parts (en- Video. http://www.cs.tu-berlin.de/~phade/ tropy of the coefficients). On the other hand, large secmpeg.html, 1995 amounts of video data are encoded by reference to [12] T.B. Maples, G.A. Spanos: Performance Study preceding or following blocks (intracoded blocks), of a Selective Encryption Scheme for the Secu- from this it follows that only the referenced blocks rity of Networked Real-time Video. Proc. 4th have to be protected. Int'l Conference on Computer and Communica- There are several sophisticated approaches for ap- tions, Las Vegas, NV, 1995 plying partial encryption methods to non-scalable [13] I. Agi, L. Gong: An Empirical Study of Secure standard-based hybrid video coding schemes. Nev- MPEG Video Transmissions. ISOC Symposium ertheless, the protection obtained from simple base on Network and Distributed System Security, layer encryption of a scalable encoded video based San Diego, CA, 1996 on a spatial resolution pyramid is comparable to the best known partial MPEG encryption method. Base [14] L. Tang: Methods for Encrypting and Decrypt- layer encryption does not require content parsing and ing MPEG Video Data Efficiently. Proc. 4th therefore has a much lower overall computational ACM Int'l Multimedia Conference, Boston, complexity than partial MPEG encryption. Note that MA, 1996 for base layer encryption the amount of encrypted [15] L. Qiao, K. Nahrstedt: A New Algorithm for data has to be determined a priori whereas partial MPEG Video Encryption. Proc. 1st Int'l Conf. MPEG encryption allows different security levels on Imaging Science, Systems and Technology, even if a video has already been encoded. Las Vegas, NV, 1997 7 Literature [16] T. Kunkelmann, H. Vogler, M.-L. Moschgath, [1] R. Steinmetz: Data Compression in Multimedia L. Wolf: Scalable Security Mechanisms in computing - standards and systems. Multimedia Transport Systems for Enhanced Multimedia Systems, 1(4), pp. 187-204, Springer Verlag, Services. Proc. 3rd European Conf. on Multi Berlin 1994 media Applications, Services and Techniques [2] R. Steinmetz, K. Nahrstedt: Multimedia: Com- (ECMAST'98), Berlin, Germany, 1998 puting, Communications and Applications. [17] T. Kunkelmann, R. Reinema, R. Steinmetz, T. Prentice Hall, München 1995 Blecher: Evaluation of Different Video Encryp- [3] ISO/ IEC International Standard 10918: Digital tion Methods for a Secure Multimedia Compression and Coding of Continuous-Tone Conferencing Gateway. Proc. 4th COST 237 Still Images. 1993 Workshop, Lisboa, Portugal, 1997 [4] ISO/ IEC IS 13818-2: Generic coding of moving [18] U. Horn and B. Girod: Scalable video coding for pictures and associated audio information: the Internet. Computer Networks and ISDN Video. 1996 Systems, Vol. 29, No. 15, pp. 1833-1842, Nov. 1997 [5] ITU-T Recommendation H.263: Video coding for low bit rate communication. 1996 [19] M. Vetterli, K.M. Uz: Multiresolution coding techniques for digital television: A review. Mul- [6] P. Bahl, P.S. Gauthier, R.A. Ulichney: Software- tidimensional Systems and Signal Processing, only Compression, Rendering, and Playback of Vol. 3: pp. 161-187, 1992 Digital Video. Digital Technical Journal Vol. 7(4), 1995 [20] T. Kunkelmann, U. Horn: Video Encryption Based on Data Partitioning and Scalable Coding [7] T. Kunkelmann, R. Reinema: A Scalable Secu- - A Comparison. 5th Int'l Workshop on Interac- rity Architecture for Multimedia Communica- tive Distributed Multimedia Systems and Tele- tion Standards. Proc. 4th IEEE Int'l Conference communication Services (IDMS'98), Oslo, on Multimedia Computing and Systems, Ottawa, Norway, 1998 Canada, 1997 [8] H. Schulzrinne, S. Casner, R. Frederick, V. Jacobson: RTP: A Transport Protocol for Real- Time Applications. RFC 1889, 1996 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 48 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 49 Generating Robust Digital Signature for Image/Video Authentication Ching-Yung Lin and Shih-Fu Chang Department of Electrical Engineering and New Media Technology Center Columbia University New York, NY 10027, USA {cylin, sfchang}@ctr.columbia.edu ABSTRACT a watermark in the image/video is equivalent to signing a specific digital producer identification (sig- Image/video authentication techniques pro- nature) on the content of images/videos [2,3]. Once tect the recipients against malicious forgery. the image/video is manipulated, this watermark will In this paper, we describe an image authenti- be destroyed such that the authenticator can examine cation technique that verifies the originality it to verify the originality of contents. Another ap- of the received images. The authentication proach generates a content-based digital signature signature can distinguish content-changing which includes the important information of contents manipulations (such as pixel replacing) from and the exclusive producer identification [4-10]. The content-preserving manipulations (such as signature is generated by a producer-specific private JPEG compression). We also propose a video key such that it can not be forged. Therefore, the authentication method that generates robust authenticator can verify a received image/video by examining whether its contents match the informa- signatures for compressed video. The signa- tion conveyed in the signature [4]. tures can survive some of the transcoding Today, most digital multimedia data are stored or process of MPEG. distributed in compressed form. Moreover, to satisfy KEYWORDS the various needs of broadcasting, storage and trans- Authentication, watermark, digital signature, ma- mission, some transcoding of compressed digital im- nipulation, transcoding ages/videos may be required [11,12]. For instance, digital video clips are usually shot and stored in the 1 Introduction compressed format with a pre-determined bit-rate. The concept of content-based image/video authenti- But the final distributed bit rate of them may be dif- cation builds upon the increasing need for trustwor- ferent. Another example is that digital images shot thy digital multimedia data in commerce, industry, and stored in one format may need to be distributed defense, etc. Digital media become popular in the in different formats. These transcoding processes past few years partly because of their efficiency of change the pixel values of the digital image/video but manipulation. Editing or modifying the content of a not its content. Therefore, these processes should not digital image or video can be done efficiently and alter the authenticity of the data. Robustness is an seamlessly. However, these advantages decrease the important concern in developing multimedia authen- credibility of digital data. To ensure trustworthiness, tication techniques. Without robustness, an authenti- content-based image/video authentication techniques cation method can only verify the images/videos at are needed for verifying the originality of video the final stage of transcoding processes, but not content and preventing forgery [1]. Observers require authenticate them. In other words, unless we trust all them to verify either the "reality" of images/videos the transcoders in the processes, the "reality" or the of natural events or the "intactness" of artificial im- "intactness" of the multimedia data cannot be proven ages/videos such as motion pictures, film, etc. without robust signatures. The proof of the "reality" of a video clip or an image Robustness consideration for authentication is dif- can be provided only by the digital camera that took ferent from that for general watermarking techniques the shot. Similarly, the proof of the "intactness" of a [13-15]. Watermarks used for copyright protection received image/video should be provided by the pro- are expected to be robust to most manipulations. But ducer. A signature, which conveys the identification authentication signatures are expected to survive of the camera or the producer and is relative to the only acceptable transcoding or compression and re- contents, can be the proof. Image/video authentica- ject other manipulations. tion techniques are based on two methods: embedded watermark and external digital signature. Embedding Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 50 Of the two authentication methods, the embedded found that some quantitative invariants or predictable watermarking method is more convenient but usu- properties can be extracted. ally does not work well with lossy compression. The watermarks are either too fragile for compression or too flexible for manipulations. In other words, a wa- termarking method that can reliably distinguish com- pression from other manipulations still has not been found. The external signature method is not as effi- cient because anyone who needs to authenticate the received image/video has to request the source to provide the signature. But since the signatures re- main untouched when the pixel values of the im- ages/videos are changed, they provide a better pros- pect for achieving robustness. In this paper, we describe an effective technique for Figure 1: Signature Genera- content-based image/video authentication that is tor and Image Authentication based on the robust authentication signature we pro- posed in [8-10]. This signature can survive JPEG compression, because the content-based information Because all DCT coefficient matrices are divided by included in the signatures is invariant before and af- the same quantization table in the JPEG compression ter JPEG compression. The proposed video authenti- process, the relationship between two DCT coeffi- cation signature is also robust to some of the cients of the same coordinate position should remain transcoding processes of MPEG. the same after the quantization process. Furthermore, Section 2 describes the proposed robust image due to the rounding effect after quantization, the re- authentication system and its characteristics. Section lationship of the two may be the same or become 3 shows the process of generating robust signatures. equal. For instance, if one coefficient Fp(n) in the Section 4 describes the authenticator. In Section 5, position n of block p is larger than the other coeffi- we describe two methods to enhance the performance cient Fq(n) in the position n of block q, then after of the authentication system. Section 6 shows the ro- compression, their relationship, Fp'(n) Fq'(n), bustness of this robust digital signature. In Section 7, we show some experimental results of the image where Fp'(n) = Integer Round (Fp(n)/Q) Q and authentication system. Section 8 describes the com- Fq'(n) = Integer Round (Fq(n)/Q) Q , is guaran- mon transcoding processes of MPEG compressed teed. It can be summarized as Theorem 1: videos and a robust video authentication system. We This property holds for any number of decoding and present a brief conclusion in Section 9. re-encoding processes. The signature generation process is as follows: Each 2 Image Authentication System 8x8 block of an image captured directly by a digital The proposed method is shown in Figure 1. Our me- thod uses a concept similar to that of the digital si- Theorem 1: gnature method proposed by Friedman [4], but their if Fp(n) > Fq(n) then Fp'(n) Fq'(n) , technique doesn't survive lossy compression. A si- gnature and an image are generated at the same time. if Fp(n) < Fq(n) then Fp'(n) Fq'(n) , The signature is an encrypted form of the feature if Fp(n) = Fq(n) then Fp'(n) = Fq'(n). codes or hashes of this image, and it is stored sepa- rately. Once a user needs to authenticate the image camera, a digital camcorder, or computer graphic he receives, he should decrypt this signature and software is transformed to the DCT coefficients, and compare the feature codes (or hash values) of this sent to the image analyzer. The feature codes are image to their corresponding values in the original generated according to two controllable parameters signature. If they match, this image can be claimed to in the analyzer: mapping function, W, and selected be "authentic". The most important difference bet- ween our method and Friedman's "trustworthy came- positions, b, in the DCT domain. Given a block p in an image, the mapping function is used for selecting ra" is that we use invariance properties in JPEG lossy the other block to form a block pair, i.e., q = W(p). A compression as robust feature codes instead of using coefficient position set, b, is used to indicate which hashes of the raw images. positions in a 8x8 block are selected. The feature 3 Signature Generation codes of the image records the relationship of the dif- The generation of a signature can be divided into two ference value, Fp(n)-Fq(n), and zero, at the b se- parts: feature extraction and feature encryption. Fea- lected positions. If the difference is larger than or ture extraction is the core problem of this paper. equal to zero, a bit 1 is represented; otherwise, a bit 0 From the compression process of JPEG, we have is recorded. This process is applied to all blocks to Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 51 ensure the whole image is protected. (i.e., each block ture codes record the relationship of the difference has to be, at least, in a block pair.) In the last step, the value, Fp(n)-Fq(n), and a threshold, kr. Therefore, feature codes are encrypted with a private key by they indicate the possible ranges of the difference of using the Public Key Encryption method [4]. More DCT coefficients, which will be tested in the authen- detailed descriptions of signature generation process ticator. are in [10]. 6 Robustness 4 Authentication Process The feature codes generated in the Section 3 are The procedure of authentication process is also based on the characteristics of JPEG compression. shown in Fig. 1. Given a signature derived from the With the robust digital signature generated from original image and a JPEG compressed image bit- these feature codes, images may be compressed and stream, Bm, for authentication, at the first step, we decompressed several times and still considered as have to decrypt the signature and reconstruct DCT authentic. coefficients from Bm. Because the feature codes de- In some practical applications, some other manipula- crypted from the signature record the relationship of tions are also considered acceptable, such as intensity the difference values and zero, they indicate the sign enhancement, scaling, cropping, file format trans- of the difference of DCT coefficients, despite the formation, etc. These acceptable manipulations can changes of the coefficients incurred by lossy JPEG be either pre-determined by the signature generator compression. If these constraints are not satisfied, we with special consideration on the controllable pa- can claim that this image has been manipulated by rameters, or decided by the authenticator with case- another method. dependent tolerance bound. The methods for 5 Performance Enhancement achieving robustness to these manipulations are dis- cussed as follows: 5.1 Tolerance Bound For Recompress- * Intensity enhancement: ing Noise If a constant intensity change is applied to the whole Rounding noises may be added during the JPEG image, it only changes the DC values of all the 8x8 compression process and they may cause false alarm. DCT blocks. Because the authenticator compares the In practice, computer software and hardware calcu- difference of DCT coefficients, this manipulation late the DCT with finite precision. Because the error will be considered as acceptable. On the other hand, may accumulate throughout the multiple recompres- if the authenticator wants to reject it or limit the ran- sion processes, we have to introduce some tolerance ge of change, we can include the mean value of all bounds to prevent the authenticator from reporting DC coefficients in the signature such that the au- some false alarm in the accepted recompression pro- thenticator can reject large intensity changes. cess. If we assign a tolerance bound, , to the * Cropping: authentication system, then the following property, should be considered as acceptable value changes in In most situations, cropping only selects a part of the the authenticator. image, such that it may introduce a different visual meaning to the cropped image. However, if this ma- 5.2 Multi-Layer Feature Codes nipulation is allowed in some situations, we can de- sign a robust signature with carefully selected map- Theorem 2: ping function. For instance, we can select block pairs from adjacent blocks. Then, the feature codes of tho- if Fp(n)-Fq(n) k then se cropped blocks can be found in the original si- Fp'(n)­Fq'(n) k- 1/2 (Qp(n)+Qq(n)), gnature. In practical situations, the cropped image has to provide its related location on the original if Fp(n)-Fq(n) < k then image to the authenticator. Because the origin point Fp'(n)­Fq'(n) k+ 1/2 (Qp(n)+Qq(n)) of the cropped image may not be at the grid points of the original image, (i.e., each 8x8 block in the crop- Given two DCT coefficients at the same positions of ped image may cover parts of four 8x8 original two blocks, not only their relationship after compres- blocks), the authenticator can only verify the cropped sion is constrained, but also the range of their differ- image excluding its boundary pixels. In this case, the ence after compression is limited. Defining Qp and recompress process may introduce different variation Qq as the quantization matrix of the block p and q, to pixels from recompressing the original image. respectively, the following theorem must be satisfied: Therefore, some tolerance may be needed in this si- Applying Theorem 2, we can use multi-layer feature tuation. codes to protect the DCT difference values within * Scaling: more precise ranges. For instance, the r-th layer fea- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 52 Scaling is a common operation on the images, which pixel values are not too great, we can still consider is accepted in many situations. For instance, a scan- them as some kind of noise and use larger tolerance ner may scan an image with a high resolution. This values. This method can also be applied to other ope- image may be down-sampled to an appropriate size rations. later. In the scaling cases, the signature generator has to record the original size of the image. An authenti- 7 Experimental Results cator can re-scale this scaled image to its original si- The `Lenna' image is compressed with a compres- ze before general authentication processes. Because sion ratio of 9:1. The authentication signature is gen- the DCT transformations are linear and the difference erated based on the original image. The compressed in the pixel values of the original and the re-scaled bitstream is sent to the system for authentication. As image should not be too great, there will be no large predicted, the authenticator will verify the com- changes on the DCT coefficients. Similar to the ge- pressed image as authentic and decompress this im- (a) (b) (c) (d) (e) Figure 2: Experimental Results: (a) original image, (b) 9:1 JPEG compressed, (c) 9:1 JPEG recompressed from a 6:1 compressed image, (d) manipulated image, (e) authentication result of the manipulated image. neral recompression noise, these changes can be also age perfectly. The authentication result is shown in considered as some kinds of noise that can be solved Fig. 2(b). by allowing larger tolerance values in the authenti- The original image is compressed with a compres- cator. sion ratio 6:1. Then, this image is decompressed by Format transformation with other lossy compressi- Photoshop 3.0, rounded to integral values, and re- ons: compressed into an image with compression ratio Other lossy compressions such as wavelet-based 9:1. In this case, the recompression process (9:1) methods or color space decimation methods can be does not trigger the manipulation detector and the fi- considered as introducing noises to the original nal compressed image is still verified as authentic. image. Similarly, we can use larger tolerances in the The final decoded image is similar to Fig. 2(c). authenticator to allow these lossy compressions. In the third experiment, we flipped the mouth area of Filtering and other operations: the image. It is shown in Fig. 2(d), with its authenti- Filtering, such as low-pass filtering and edge enhan- cation result shown in Fig. 2(e). It can be clearly cement, may probably change more visual meaning shown that the manipulated part has been detected as of images. The authenticator would be hard to deal fake and highlighted by the authenticator. with these operations. However, if the changes on Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 53 8 Video Authentication System the coefficient relationships, similar to that described Similar to the image authentication system, a video in [10]. authentication signature has to be robust to the Situation 5 poses the most challenging case for transcoding processes. Regardless of the format authentication. The GOP structure in the video is transformation between different compression stan- changed and so is the relationship of DCT coeffi- dards (such as MPEG-1, MPEG-2, H.261 and cients among blocks. The design scheme for gener- H.263), five transcoding processes may be applied to ating a robust signature in this situation is still under the compressed video [16,17]: study. 1. Dynamic Rate Shaping [18,19]: A real-time A more detailed description of the content-based rate-control scheme in the compressed domain. video authentication techniques will be shown in This technique sets dynamic control points to [26]. drop the high-frequency DCT coefficients on 9 Conclusion each 8x8 block in a macroblock. Motion vectors In this paper, we have described a method for robust are not changed. image/video authentication. Robust signatures can 2. Rate Control without Drift Error Correction distinguish the JPEG lossy baseline compression [20,21]: This technique is also applied in the from other malicious manipulations for images, and compressed domain. DCT coefficients are re- the Rate-Control Coding from other manipulations quantized to satisfy different bit-rate constraint. for compressed videos. Our analytic and empirical Motion vectors are not changed. performance analyses have shown the effectiveness 3. Rate Control with Drift Error Correction [16]: of the image authentication system and presented a This technique improves the video quality, but possible direction for further video authentication re- it needs more computations. DCT coefficients search. of the residue of intercoded blocks are changed to satisfy the change of the re-quantized intra- 10 References coded blocks. Motion vectors are not changed [1] Bearman, D., and Trant, J. Authenticity of Digi- in this case. tal Resources: Towards a Statement of Require- 4. Transcoding with Mostly Consistent Frame ments in the Research Process. D-Lib Magazine, Types [16,17,23]: The frame types (I, P and B), June 1998. are kept unchanged in each generation. It may [2] Yeung, M. and Mintzer, F. An Invisible Water- be used in creating a new sequence by cutting marking Technique for Image Verification. Proc. and pasting several video segments with con- Of ICIP, Santa Barbara, CA, USA, Oct. 1997. sistent GOP units within each segment except the frames at the boundary. [3] Lin, C.-Y. and Chang, S.-F. A Watermark-Based 5. Transcoding with Inconsistent Frame Types Robust Image Authentication Method Using [16]: In some editing process, the compressed Wavelets. ADVENT Report, Columbia Univer- videos are transformed to the uncompressed bit- sity, Apr. 1998. http://www.ctr.columbia.edu/ streams which are then re-encoded. The GOP ~cylin/pub/a98wav.ps structures of frames and the motion vectors may [4] Friedman, G.L. The Trustworthy Digital Cam- change in this case. era: Restoring Credibility to the Photographic Video authentication signatures can be generated for Image. IEEE Trans. on Consumer Electronics, different situations. For instance, to generate a sig- Vol.39, No.4, pp.905-910, Nov. 1993. nature that is robust to situations 1, 2 and 4, we can [5] Quisquater, J.-J., Macq, B., Joye, M., Degand, use the DCT coefficients of the luminance and chro- N. and Bernard, A. Practical Solution to matic matrices in each macroblock to generate the Authentication of Images with a Secure Camera. comparison pairs. Since the quantization_scale is SPIE Storage and Retrieval for Image and Video specified for each macro-block [25], the relative re- Databases, San Jose, CA, USA, Feb. 1997. lationships of the coefficients are invariant during transcoding. Therefore, similar to the signature gen- [6] Gennaro, R., and Rohatgi, P. How to Sign Digi- eration process of images, we can use them to gener- tal Streams. CRYPTO '97, Santa Barbara, CA, ate the feature codes. If a more flexible choice of USA, August 1997, pp.180-197. comparison pair is necessary, the authentication sys- [7] Gennaro, R., Krawczyk, H. and Rabin, T. RSA- tem can generate signatures based on the criteria we based Undeniable Signatures. CRYPTO '97, have proposed in [9,10]. It should be noted that, in Santa Barbara, CA, USA, August 1997 situation 4, the frames in the boundary of video seg- [8] Lin, C.-Y. and Chang, S.-F. A Robust Image mentations cannot be verified by this method. Authentication Method Surviving JPEG Lossy Because the drift error correction process changes the Compression. SPIE Storage and Retrieval for DCT coefficient values, statistical models of the Image and Video Databases, San Jose, CA, changes can be used to provide tolerance bounds for USA, Jan. 1998. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 54 [9] Lin, C.-Y. and Chang, S.-F. An Image Authenti- [18] Eleftheriadis, A. and Anastassiou, D. Con- cator Surviving DCT-based Variable Quantiza- strained and General Dynamic Rate Shaping of tion Table Compression. CU/CTR Technical Compre-ssed Digital Video. Proceedings of the Report 490-98-24, Nov. 1997. 2nd IEEE International Conference on Image [10] Lin, C.-Y. and Chang, S.-F. A Robust Image Processing (ICIP95), Arlington, VA, USA, Oct. Authentication Method Distinguishing JPEG 1995. Compression from Malicious Manipulation. [19] Jacobs, S. and Eleftheriadis, A. Straming Video CU/CTR Technical Report 486-97-19, Dec. using Dynamic Rate Shaping and TCP Flow 1997. Control. Visual Communication and Image Rep- http://www.ctr.columbia.edu/~cylin/pub/authpap resentation Journal, Jan. 1998. er.ps [20] Viscito, E. and Gonzales, C. A Video Compres- [11] Wells, N.D. The Atlantic Project: Models for sion Algorithm with Adaptive Bit Allocation and programme production and distribution. Pro- Quantization. SPIE Vol. 1605 Visual Communi- ceedings of the European Conference on Multi- cations and Image Processing '91. media Applications Services and Techniques [21] Ding, W. and Liu, B. Rate Control of MPEG (ECMAST 96), Louvaine-la-Neuve, Belgium, Video Coding and Recording by Rate- May 1996, pp. 243-253. Quantization Modeling. IEEE Trans. on Circuits [12] Brightwell, P.J., Dancer, S.J. and Knee, M.J. and Systems for Video Technology, Vol. 6, No. Flexible Switching and Editing of MPEG-2 1, pp.12-19, Feb. 1996. Video Bitstreams. International Broadcasting [22] Meng, J. and Chang, S.-F. Tools for Com- Convention (IBC 97), Amsterdam, Sep. 1996, pressed-Domain Video Indexing and Editing. pp. 547-552. SPIE Conference on Storage and Retrieval for [13] Cox, I., Kilian, J., Leighton, T., and Shamoon, Image and Video Database, Vol. 2670, San Jose, T. Secure Spread Spectrum Watermarking for CA, USA, Feb. 1996. Multimedia. NEC Research Institute Technical [23] Meng, J. and Chang, S.-F. CVEPS ­ A Com- Report, 95-10, 1995. pressed Video Editing and Parsing System. Pro- [14] Braudaway, G.W., Magerlein, K.A. and Mintzer, ceedings of ACM Multimedia 96, Boston, MA, F. Protecting Publicly-Available Images with a USA, Nov. 1996. Visible Image Watermark. IBM Research Divi- [24] Chang, S.-F. and Messerschmitt, D. G. Manipu- sion, T.J. Watson Research Center, Technical lation and Compositing of MC-DCT Com- Report 96A000248, 1996. pressed Video. IEEE Journal of Selected Areas [15] Meng, J. and Chang, S.-F. Embedding Visible in Communications, Vol. 13, No. 1, pp.1-11, Watermarks in the Compressed Domain. IEEE Jan. 1995. International Conference on Image Processing [25] Haskell, B.G., Puri, A. and Netravali, A.N. (ICIP 98), Chicago, IL, USA, Oct. 1998. Digital Video: An Introduction to MPEG-2. [16] Tudor, P.N. and Werner, O.H. Real-Time Chapman and Hall, 1997. Transcoding of MPEG-2 Video Bit Streams. In- [26] Lin, C.-Y. and Chang, S.-F. Issues and Solutions ternational Broadcasting Convention (IBC 97), for Authenticating MPEG Video. SPIE Storage Amsterdam, Netherlands, Sep. 1997, pp. 286- and Retrieval for Image and Video Databases, 301. San Jose, CA, USA, Jan. 1999. [17] Werner, O.H. Generic Quantiser for Transcoding of Hybrid Video. Proceedings of the 1997 Pic- ture Coding Symposium, Berlin, Germany, Sep 1997. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 55 Weaknesses of Copyright Marking Systems Fabien A.P. Petitcolas Ross J. Anderson University of Cambridge, Computer Laboratory University of Cambridge, Computer Laboratory Pembroke Street, Cambridge CB2 3QG, UK Pembroke Street, Cambridge CB2 3QG, UK fapp2@cl.cam.ac.uk rja14@cl.cam.ac.uk ABSTRACT `fair use' provisions are strongly entrenched. Another problem, according to Samuelson, is that `Tolerating Hidden copyright marks have been proposed some leakage may be in the long run of interest to as a solution for solving the illegal copying publishers' [2]. A European legal expert put it even and proof of ownership problems in the con- more strongly: that copyright laws are only tolerated text of multimedia objects. We show that the because they are not enforced against the large num- first generation of systems does not fulfil the bers of petty offenders [3]. expectation of users through a number of at- Similar issues are debated within the software indus- tacks that enable the information hidden by try; some people argue, for example, that a modest them to be removed or otherwise rendered level of amateur software piracy actually enhances unusable. revenue because people may `try out' software they have `borrowed' from a friend and then go on to buy KEYWORDS it. Bill Gates' view is significant: `Although about Digital watermarking, fingerprinting, attacks. three million computers get sold every year in China, 1 Introduction people don't pay for the software. Someday they will, The ease with which digital media could be copied though. And as long as they're going to steal it, we led people to propose techniques for embedding hid- want them to steal ours. [...] Then we'll somehow den copyright marks and serial numbers in still im- figure out how to collect sometime in the next dec- ages, video and audio. We formed the view that use- ade.' [4] ful progress might come from trying to attack all For all these reasons, we may expect leaks in the these first generation schemes. In the related field of primary copyright protection mechanisms and wish cryptology, progress was iterative: cryptographic al- to provide independent secondary mechanisms that gorithms were proposed, attacks on them were found, can be used to trace and prove ownership of digital better algorithms were proposed, and so on. Eventu- objects. Here too marking techniques are expected to ally, theory emerged: fast correlation attacks on be important. stream ciphers and differential and linear attacks on 2 Copyright marks block ciphers, now help us understand the strength of There are two basic kinds of mark: fingerprints and cryptographic algorithms in much more detail than watermarks. One may think of a fingerprint as an before. embedded serial number while a watermark is an Electronic copyright management schemes have been embedded copyright message. The first enables us to proposed as a solution to the copying problem. These trace offenders, while the second can provide some schemes might be imposed in applications such as of the evidence needed to prosecute them. It may Digital Versatile Disk (DVD) and video-on-demand ever, as in the DVD proposal, form part of the pri- where the idea is that DVD players would refuse to mary copy management system; but it will more of- copy files containing suitable copyright marks. But ten provide an independent back-up to a copy man- such schemes suffer from a number of drawbacks. agement system that uses overt mechanisms such as They rely on the tamper-resistance of consumer digital signatures. electronics ­ a notoriously unsolved problem [1]. In [5], we discussed various applications of finger- The tamper-resistance mechanisms being built into printing and watermarking, their interaction, and DVD players are fairly rudimentary and the history some related technologies. Here, we are concerned of satellite TV piracy leads us to expect the appear- with the robustness of the underlying mechanisms. ance of `rogue' players which will copy everything89. What sort of attacks are possible on marking Electronic copyright management schemes also con- schemes? What sort of resources are required to re- flict with applications such as digital libraries, where move marks completely, or to alter them so that they are read incorrectly? What sort of effect do various 89 As a matter of fact techniques to bypass the territorial possible removal techniques have on the perceptual lock of certain DVD implementations are already availa- quality of the resulting audio or video? ble on the Internet. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 56 The basic problem is to embed a mark in the digital representation of an analogue object (such as a film or sound recording) in such a way that it will not re- duce the perceived value of the object while being difficult for an unauthorised person to remove. A first pass at defining robustness in this context may be found in a recent request for proposals for audio marking technology from the International Federa- tion for the Phonographic Industry, (IFPI) [6]. The Fig. 1 - We exaggerate here the distortion applied by goal of this exercise was to find a marking scheme StirMark to still pictures. that would generate evidence for anti-piracy opera- tions, track the use of recordings by broadcasters and others and control copying. The IFPI robustness re- 3.1 The Jitter Attack quirements are as follows: Our starting point in developing a systematic attack * the marking mechanism should not affect the on marking technology was to consider audio mark- sonic quality of the sound recording; ing schemes. A simple and devastating attack on these schemes is to add jitter to the signal by remov- * the marking information should be recoverable ing samples or duplicating other. In fact most simple after a wide range of filtering and processing op- spread-spectrum based techniques are subject to this erations, including two successive D/A and A/D kind of attacks. Indeed, although spread-spectrum conversions, steady-state compression or expan- signals are very robust to distortion of their ampli- sion of 10%, compression techniques such as tude and to noise addition, they do not survive timing MPEG and multi-band nonlinear amplitude errors: synchronisation of the chip signal is very im- compression, adding additive or multiplicative portant and simple systems fail to recover this syn- noise, adding a second embedded signal using chronisation properly. So, in general time scaling the same system, frequency response distortion based attacks are very efficient against audio mark- of up to 15 dB as applied by bass, mid and treble ing systems. controls, group delay distortions and notch fil- ters; 3.2 Stirmark * there should be no other way to remove or alter Following this attack and after evaluating some wa- the embedded information without sufficient termarking software, it became clear that although degradation of the sound quality as to render it many schemes could survive basic manipulations ­ unusable; that is, manipulations that can be done easily with standard tools, such as rotation, shearing, resampling, * given a signal-to-noise level of 20 dB or more, resizing and lossy compression ­ they would not the embedded data channel should have a band- cope with combinations of them. This motivated the width of 20 bits per second, independent of the design of StirMark, initially implemented by Markus signal level and type (classical, pop, speech). G. Kuhn and enhanced and maintained by the first Similar requirements could be drawn up for marking author [14]. still pictures, videos and multimedia objects in gen- StirMark is a generic tool developed for simple ro- eral. However, before rushing to do this, we will bustness testing of image marking algorithms and consider some systems recently proposed and show other steganographic techniques. StirMark simulates attacks on them that will significantly extend the a resampling process, i.e. it introduces the same kind range of distortions against which designers will of errors into an image as printing it on a high quality have to provide defences, or greatly reduce the avail- printer and then scanning it again with a high quality able bandwidth, or both. scanner. It applies a minor geometric distortion: the image is slightly stretched, sheared, shifted and/or 3 Attacks rotated by an unnoticeable random amount and then This leads us to the topic of attacks and here we pre- resampled using Nyquist interpolation. sent some quite general kinds of attack that destroy, With those simple geometrical distortions we could or at least reveal significant limitations of, several confuse most marking systems available on the mar- marking schemes: PictureMarc 1.51 [7], SysCoP [8], ket. More distortions ­ still unnoticeable ­ can be SureSign [9], JK_PGS (É.P.F.L. algorithm, part of applied to a picture. We applied a global `bending' the European TALISMAN project), EIKO- and `random displacement' to the image: in addition NAmark [10], [11], Echo Hiding [19], Giovanni [17] to the general bi-linear property explained previ- and the N.E.C. method [13]. We suspect that systems ously, a slight deviation is applied to each pixel, that use similar techniques are also vulnerable to our which is greatest at the centre of the picture and al- attacks. most null at the corners and to which is added a higher frequency displacement of the form Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 57 ësin( xx)sin( y y) + n(x,y) ­ where n is a random The attack was motivated by a fielded automatic number ­ is added ( Fig. 1). system for copyright piracy detection, consisting of a Finally a transfer function that introduces a small and watermarking scheme plus a web crawler that smoothly distributed error into all sample values is downloads pictures from the net and checks whether applied. This emulates the small non-linear ana- they contain a watermark. logue/digital converter imperfection typically found It consists of chopping an image up into a number of in scanners and display devices. smaller subimages, which are embedded in a suitable In order for these distortions ­ which are practically sequence in a web page. Common web browsers ren- unnoticeable as one can see from Fig. 2 ­ to be most der juxtaposed subimages stuck together, so they ap- effective, a medium JPEG compression should be pear identical to the original image (Fig. 3). This at- applied after StirMark.90 tack appears to be quite general; all marking schemes require the marked image to have some minimal size (one cannot hide a meaningful mark in just one pixel). Thus by splitting an image into sufficiently small pieces, the mark detector will be confused. The best that one can hope for is that the minimal size could be quite small and the method might therefore not be very practical. There are other problems with such `crawlers'. Java applets, ActiveX objects, etc. can be embedded to display a picture inside the browser; the applet could even de-scramble the picture in real time. Defeating Fig. 2 - `Lenna' before and after StirMark used such techniques would entail rendering the web page, with default parameters. detecting pictures and checking whether they contain We suggest that image-watermarking tools, which do a mark. An even more serious problem is that much not survive StirMark ­ with default parameters ­ current piracy is of pictures sold via many small should be considered unacceptably easy to break. services, from which the crawler would have to pur- This immediately rules out the majority of commer- chase them using a credit card before it could exam- cial marking schemes. ine them. A crawler that provided such `guaranteed One might try to increase the robustness of a water- sales' would obviously become a target. marking system by trying to foresee the possible 3.4 A General Attack On Audio transforms used by pirates; one might then use tech- Marking niques such as embedding multiple versions of the Audio restoration techniques have been studied for mark under suitable inverse transforms; for instance several years and have proved to be very useful to Ó Ruanaidh and Pereira suggest using the Fourier- remove localised degradations (clicks, crackles, Mellin transform. However, the general theme of the scratches, etc.) from old recordings [15], [16]. After attacks described above is that given a target marking finding the local degradations, these methods basi- scheme, we invent a distortion (or a combination of cally ignore the bad samples and interpolate the sig- distortions) that will remove it or at least make it un- nal using the neighbouring ones. readable, while leaving the perceptual value of the Our attack is based on this idea: the signal is recon- previously marked object undiminished. We are not structed block by block using the original data. The limited in this process to the distortions produced by method we used assumes that the recorded data x is common analogue equipment, or considered in the the realisation of a stationary autoregressive (AR) IFPI request for proposals cited above. process of order p, i.e. It is an open question whether there is any marking p scheme for which a chosen distortion attack cannot xn = a kxn-k +en n = p+ ,1 ,N (1) be found. k 1 = 3.3 The Mosaic Attack where e = [ep 1+, , eN ]T is the `excitation' noise This point is emphasised by a `presentation' attack, which is of quite general applicability and which vector. We suppose that we want to reconstruct a possesses the initially remarkable property that a block of l consecutive samples starting at sample marked image can be unmarked and yet still rendered m +1 and assume to be unknown. Estimators for pixel for pixel in exactly the same way as the marked both a and x are chosen such that they minimise the image by a standard browser. quadratic error eT E = e which is a function of the unknown samples xu = [xm+1, , xm+ ]T l and the un- 90 We preferred not to include JPEG or similar known AR parameters a = [a1, ,ap ]T . compression techniques in StirMark in order to keep the program simple. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 58 also be used against image marking too. Similar al- gorithms for image reconstruction are given in [18]. 3.5 Attack On Echo Hiding Echo hiding hides information in sound by introduc- ing echoes with very short delays [19]. It relies on the fact that we cannot perceive short echoes (say 1 ms) and embeds data into a cover audio signal by in- troducing an echo characterised by its delay and its relative amplitude . By using two types of echo it is possible to encode ones and zeros. For this purpose the original signal is divided into chunks separated by spaces of pseudo-random length; each of these Fig. 3 -Screen-shot of a web browser while chunks will contain one bit of information. downloading an image after the mosaic attack. This at- The echo delays are chosen between 0.5 and 2 milli- tack chops a watermarked image into smaller images, seconds and the best relative amplitude of the echo is which are stuck back together when the browser ren- around 0.8. According to its creators, decoding in- ders the page. We implemented software 2Mosaic that reads a JPEG picture and produces a corresponding volves detecting the initial delay and the auto- mosaic of small JPEG images as well as the necessary correlation of the cepstrum of the encoded signal is HTML code automatically [1]. In some cases down- used for this purpose. loading the mosaic is even faster than downloading The `obvious' attack on this scheme is to detect the the full image! In this example we used a 350×280- echo and then remove it by simply inverting the con- pixel image watermarked using PictureMarc 1.51. volution formula; the problem is to detect the echo Photography: Kings' College Chapel, courtesy of John without knowledge of either the original object or the Thompson, JetPhotographic, Cambridge. echo parameters. This is known as `blind echo can- cellation' in the signal processing literature and is known to be a hard problem in general. Minimisation of E is non-trivial since it involves We tried several methods to remove the echo. Fre- non-linear fourth order unknown terms but a subop- quency invariant filtering was not very successful. timal solution to the above problem can be used. Instead we used a combination of cepstrum analysis First E is minimised with respect to a by taking an and `brute force' search. arbitrary initial estimate for xu (typically zero) in The underlying idea of cepstrum analysis is pre- order to obtain an estimate a of a. If we note sented in [20]. Suppose that we are given a sig- nal y(t), which contains a simple single echo, i.e. 1 x = [xp 1+, , x ]T N , then equation (1) can be written e = x y(t) = x(t)+ x(t - ). If we note the power 1 - B(x)a and a is given by: xx spectrum of x then BT a B = BT 1 x (2) xx f ( 2 1+ 2 cos 2 f + ) yy ( f ) = ( ) ( ) Then E is minimised with respect to xu and using whose logarithm is approximately a . Equation (1) is written as e = Dk (x)xk + Du (x)xu ln yy (f ) ln xx(f )+ 2 cos( 2 f ). This is a where xk is the vector of known samples. After function of the frequency f and taking its power minimisation, the reconstructed block x u is given spectrum raises its `quefrency' , that is the fre- by: quency of cos( 2 f ) as a function of f. The auto- T D D u uxu + DuDk xk = 0 (3) covariance91 of this later function emphasises the These two steps can be iterated to get better results peak that appears at `quefrency' . but it seems that one iteration is usually enough. For Experiments on random signals as well as on music the attacks we just increase m in steps of the block show that this method returns quite accurate estima- length l and compute for each step an estimated tors of the delay when an artificial echo has been block which is appended to the others. We end up added to the signal. In the detection function we only with a fully reconstructed signal. consider echo delays between 0.5 and 3 milliseconds. Other and better interpolation algorithms are avail- Below 0.5 ms the function does not work properly able, but the least square AR interpolation technique, and above 3 ms the echo becomes too audible. we briefly summarised, gives satisfactory results if Our first attack was to remove an echo with random the blocks are relatively small, up to 80 samples [15], relative amplitude, expecting that this would intro- [16]. duce enough modification in the signal to prevent Although we used it only against BlueSpike's method [17], this attack is quite general and could 91 C(x) = E ((x - x)(x x) - ) Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 59 watermark recovery. Since echo hiding gives best re- nesses in the implementation rather than the under- sults for greater than 0.7 we could use ~ ­ an es- lying marking algorithms, even although these are timation of ­ drawn from, say a normal distribution weak (the marks can be removed using StirMark). centred on 0.8. It was not really successful, so our Each user has an ID and a two-digit password, which next attack was to iterate: we re-apply the detection are issued when she registers with Digimarc and pays function and vary ~ to minimise the residual echo. for a subscription. The correspondence between IDs We could obtain successively better estimators of the and passwords is checked using obscure software in echo parameters and then remove this echo. When the implementation and although the passwords are the detection function cannot detect any more echo, short enough to be found by trial and error, the attack we have got the correct value of ~ (as this gives the first uses a debugger to break into the software and lowest output value of the detection function). disable the password checking mechanism. We note in passing that IDs are public, so either password 3.6 Protocol Considerations search or disassembly can enable any user to be im- The main threat addressed in the literature is an at- personated. tack by a pirate who tries to remove the watermark A deeper examination of the program also allows a directly. As a consequence, the definition commonly villain to change the ID and thus the copyright of an used for robustness includes only resistance to signal already marked image as well as the type of use manipulation (cropping, scaling, resampling, etc.). (such as adult versus general public content). Before Craver et al. show that this is not enough by exhibit- embedding a mark, the program checks whether ing a `protocol' level attack [21]. there is already a mark in the picture, but this check The basic idea is that many schemes provide no in- can be bypassed fairly easily using the debugger with trinsic way of detecting which of two watermarks the result that it is possible to overwrite any existing was added first: the process of marking is often addi- mark and replace it with another one. tive, or at least commutative. So if the owner of the Exhaustive search for the personal code can be pre- document d encodes a watermark w and publishes vented by making it longer, but there is no obvious the marked version d + w and has no other proof of solution to the disassembly attack. If tamper resistant ownership, a pirate who has registered his watermark software [29] cannot give enough protection, then as w' can claim that the document is his and that the one can always have an online system in which each original unmarked version of it was d + w - w'. user shares a secret embedding key with a trusted Craver et al. argue for the use of information-losing party and uses this key to embed some kind of digital marking schemes whose inverses cannot be ap- signature. Observe that there are two separate keyed proximated closely enough. However, our alternative operations here; the authentication (which can be interpretation of their attack is that watermarking and done with a signature) and the embedding or hiding fingerprinting methods must be used in the context of operation. a larger system that may use mechanisms such as 3.8 Robustness Against Insiders timestamping and notarisation to prevent attacks of Although we can do public-key steganography ­ this kind. hiding information so that only someone with a cer- Registration mechanisms have not received very tain private key can detect its existence [30] ­ we much attention in the copyright marking literature to still do not know how to do the hiding equivalent of a date. The existing references such as [22], [23], [25] digital signature; that is, to enable someone with a and [26] mainly focus on protecting the copyright private key to embed marks in such a way that any- holder and do not fully address the rights of the con- one with the corresponding public key can read them sumers who might be fooled by a crooked reseller. but not remove them. But if the stego key is widely Moreover a good registration and trading mechanism released (e.g. as part of a global law enforcement or cannot be based on a weak marking technique. in equipment) it is very likely to leak over time. 3.7 Implementation Considerations Another problem is that a public decoder can be used The robustness of embedding and retrieving tech- by the attacker; he can remove a mark by applying niques is not the only issue. Most attacks on fielded small changes to the image until the decoder cannot cryptographic systems have come from the oppor- find it anymore. This was first suggested by Perrig in tunistic exploitation of loopholes that were found by [26]. In [31] a more theoretical analysis of this attack accident; cryptanalysis was rarely used, even against is presented as well as a possible countermeasure: systems that were vulnerable to it [27]. randomising the detection process. One could also We cannot expect copyright marking systems to be make the decoding process computationally expen- any different and the pattern was followed in the first sive. However neither approach is really satisfactory attack to be made available on the Internet against in the absence of tamper-resistant hardware. the most widely used picture marking scheme, Pic- Unless a breakthrough is made, applications that re- tureMarc, which is bundled with Adobe Photoshop quire the public verifiability of a mark (such as and Corel Draw. This attack [28] exploited weak- DVD) appear doomed to operate within the con- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 60 straints of the available tamper resistance technology of research. On the contrary; practical schemes for (one could use a number of marks with keys revealed most realistic application requirements are probably in succession92), or to use a central `mark reading' feasible and the continuing process of inventing service. This is evocative of cryptographic key man- schemes and breaking them will enable us to advance agement prior to the invention of public key tech- the state of the art rapidly. niques. Finally, we suggest that the real problem is not so 4 Conclusion much inserting the marks as recognising them after- We have demonstrated that the majority of copyright wards. Thus progress may come not just from devis- marking schemes in the literature are vulnerable to ing new marking schemes, but in developing ways to attacks involving the introduction of sub-perceptual recognise marks that have been embedded using the levels of distortion. In particular, many of the mark- obvious combinations of statistical and transform ing schemes in the marketplace provide only a lim- techniques and thereafter subjected to distortion. The ited measure of protection against attacks. Most of considerable literature on signal recognition may the image marking systems are defeated by StirMark, provide useful starting points. a simple piece of software that we have placed in the 5 Acknowledments public domain [14]. We have also shown specific at- The first author is grateful to Intel Corporation for fi- tacks some audio marking systems. nancial support under the grant `Robustness of In- This experience confirms our hypothesis that formation Hiding Systems'. steganography would go through the same process of evolutionary development as cryptography, with an 6 References iterative process in which attacks lead to more robust systems. [1] Ross J. Anderson and Markus G. Kuhn. Tamper Our experience in attacking the existing marking Resistance ­ A Cautionary Note. In Second schemes has convinced us that any system which at- USENIX Workshop on Electronic Commerce, tempted to meet all the accepted requirements for pages 1­11, Oakland, CA, USA, November marking (such as those set out by IFPI) would fail: if 1996. ISBN 1-880446-83-9. it met the robustness requirements then its bandwidth [2] Pamela Samuelson. Copyright and Digital Li- would be quite insufficient. This is hardly surprising braries. Communications of the ACM, pages 15­ when one considers that the information content of 21, 110, 38(4), April 1995. many music recording is only a few bits per second, [3] Alastair Kelman. Electronic Copyright Man- so to expect to embed 20 bits per second against an agement ­ The Way Ahead. Security Seminars, opponent who can introduce arbitrary distortions is University of Cambridge, 11 February 1997. very ambitious. Our more general conclusion from this work is that [4] The Bill & Warren Show. Fortune, page 44, 20th the `marking problem' has been over-abstracted; July 1998. Public dialogue between Bill Gates, there is not one `marking problem' but a whole con- founder and CEO of Microsoft Corporation, and stellation of them. We do not believe that any general Warren Buffett, chairman of Berkshire Hatha- solution will be found. The trade-offs and in particu- way Inc. lar the critical one between bandwidth and robust- [5] Ross J. Anderson and Fabien A.P. Petitcolas. On ness, will be critical to designing a specific system. The Limits of Steganography. IEEE Journal of We already remarked in [5] on the importance of Selected Areas in Communications (J-SAC) ­ whether the warden was active or passive ­ that is, Special Issue on Copyright & Privacy Protec- whether the mark needed to be robust against distor- tion, pages 474­481, 16(4), May 1998. ISSN tion. In general, we observe that most real applica- 0733-8716. tions do not require all of the properties in the IFPI [6] International Federation of the Phonographic In- list. For example, when auditing radio transmissions, dustry. Request for Proposals ­ Embedded Sig- we only require enough resistance to distortion to nalling Systems Issue 1.0. 54 Regent Street, deal with naturally occurring effects such as mul- London W1R 5PJ, June 1997. tipath. Many applications will also require supporting protocol features, such as the timestamping service [7] Geoffrey B. Rhoads. Steganography methods that we mentioned in the context of reversible marks. employing embedded calibration data. Digimarc So we do not believe that the intractability of the Corporation. US Patent 5,636,292, 3 June 1997. `marking problem' is a reason to abandon this field [8] E. Koch and J. Zhao. Towards Robust and Hid- den Image Copyright Labeling. In Workshop on 92 This is what happens for bank note printing in some Nonlinear Signal and Image Processing, pages countries: notes have a number of `anti-copy' features, 452­455, Neos Marmaras, Greece, 20­22 June which are publicised in succession. Forgers are less li- 1995. IEEE. kely to reproduce them since they do not know their exi- stence. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 61 [9] Signum Technologies ­ SureSign digital finger- tions (J-SAC) ­ Special Issue on Copyright & printing. http://www.signumtech.com/, October Privacy Protection, pages 573­586, 16(4), May 1997. 1998. ISSN 0733-8716. [10] Alpha Tec Ltd. EIKONAmark. [22] Marc Cooperman and Scott A. Moskowitz. http://www.generation. Steganographic method and device. The DICE net/~pitas/sign.html, October 1997. Company. US Patent 5,613,004, 18 March 1995. [11] I. Pitas. A method for signature casting on digi- [23] Alexander Herrigel, Adrian Perrig and Joseph tal images. In International Conference on Im- J.K. Ó Ruanaidh. A Copyright Protection Envi- age Processing, volume 3, pages 215­218, Sep- ronment for Digital Images. In Verläßliche IT- tember 1996. Systeme '97, Albert-Ludwigs Universität, [12] Ross J. Anderson, editor. Information hiding: Freiburg, Germany, October 1997. first international workshop, volume 1174 of [24] David Aucsmith, editor. Information hiding: Lecture notes in Computer Science. Springer second international workshop, Lecture Notes in Verlag, Berlin, Germany, May 1996. ISBN 3- Computer Science, Portland, Oregon, USA, 540-61996-8. 1998. Springer Verlag, Berlin, Germany. (to ap- [13] Ingemar J. Cox, Joe Kilian, Tom Leighton and pear) Talal Shamoon. A Secure, Robust Watermark [25] Alexander Herrigel, Joseph J.K. Ó Ruanaidh, for Multimedia. In Anderson [12], pages 183- Holger Petersen, Shelby Pereira, and Thierry 206. Pun. Secure copyright protection techniques for [14] Markus G Kuhn and Fabien A.P. Petitcolas. digital images. In Aucsmith [24], pages-. StirMark. [26] Adrian Perrig. A copyright protection environ- http://www.cl.cam.ac.uk/~fapp2/watermarking/s ment for digital images. Diploma dissertation, tirmark/, November 1997. École Polytechnique Fédérale de Lausanne, [15] Saeed Vahed Vaseghi. Algorithms for restora- Lausanne, Switzerland, February 1997. tion of archived gramophone recordings. PhD [27] Ross J. Anderson. Why cryptosystems fail. thesis, Emmanuel College, University of Cam- Communications of the ACM, 37(11):32-40, No- bridge, UK, February 1988. vember 1994. [16] Simon J. Godsill, Peter J.W. Rayner and Olivier [28] Anonymous (zguan.bbs@bbs.ntu.edu.tw). Learn Cappé. Digital audio restoration. In Mark Kahrs cracking IV ­ another weakness of PictureMarc. and Karlheinz Brandenburg, editors, Applica- news:tw.bbs.comp.hacker mirrored on tions of Digital Signal Processing to Audio and http://www.cl.cam.ac.uk/~fapp2/watermarking/ Electroacoustics. Kluwer Academic Publishers, image_watermarking/digimarc_crack.html, 1998. August 1997. Includes instructions to override [17] Giovanni audio marking software. Blue Spike any Digimarc watermark using PictureMarc. company. http://www.bluespike.com/, May [29] David Aucsmith. Tamper resistant software: An 1998. implementation. In Anderson [12], pages 317- [18] Raymond Veldhuis. Restoration of lost samples 333. in digital signals. International Series in Acous- [30] Ross J. Anderson. Stretching the limits of tics, Speech and Signal Processing. Prentice steganography. In Anderson [12], pages 39-48. Hall, Hertfordshire, UK, 1990. [31] Jean-Paul M.G. Linnartz and Marten van Dijk. [19] Daniel Gruhl, Walter Bender and Anthony Lu. Analysis of the sensitivity attack against elec- Echo hiding. In Anderson [12], pages 295­315. tronic watermarks in images. In Aucsmith [24], [20] Bruce P. Bogert, M.J.R. Healy and John W. Tu- pages ­. key. The Quefrency Alanysis of Time Series for Echoes: Cepstrum, Pseudo-Autocovariance, Cross-Ceptstrum and Saphe Cracking. In M. Ro- senblatt, editor, Symposium on Time Series Analysis, pages 209­243, New-York, USA, 1963. John Wiley & Sons, Inc. [21] Scott Craver, Nasir Memon, Boon-Lock Yeo and Minerva M. Yeung. Resolving Rightful Ownerships with Invisible Watermarking Tech- niques: Limitations, Attacks, and Implications. IEEE Journal of Selected Areas in Communica- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 62 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 63 Audio Watermarking and Data Embedding - Current State of the Art, Challenges and Future Directions - Mitchell D. Swanson1, Bin Zhu1, and Ahmed H. Tewfik1,2 1Cognicity, Inc. 2Dept. of Electrical and Computer Engineering 7171 Ohms Lane, Edina University of Minnesota MN 55439 USA 4-174 EE/CSCI Building (612) 841-7100 200 Union St. SE, Minneapolis MN 55455 USA info@cognicity.com (612) 625-6024 tewfik@ece.umn.edu ABSTRACT proposed as a means to identify the owner or dis- tributor of digital data. Data embedding algorithms embed binary Data embedding also provides a mechanism for streams in host multimedia signals. The em- embedding important control, descriptive or refer- bedded data can add features to the host ence information in a given signal. This information multimedia signal or provide copyright pro- can be used for tracking the use of a particular clip, tection. We review developments and re- including billing for commercials and audio broad- quirements in transparent data embedding cast. It can be used to track audio creation, ma- techniques for audio signals. We describe nipulation and modification history within a given our latest audio embedding algorithm and signal without the overhead associated with creat- include experimental results indicating re- ing a separate header or history file. It can also be markable robustness to low bit rate MPEG- used to track access to a given signal. This infor- mation is important in rights management applica- Layer 3 and Dolby AC-3 coding. We con- tions. clude with a discussion of future research Data embedding is also ideally suited for covert directions. communications. Data embedding can securely hide KEYWORDS large amounts of potentially encrypted information into an audio signal. Data embedding, data hiding, watermarking, copy- A most interesting application of data embedding is right protection, steganography providing different access levels to the embedded 1 Introduction data. For example, the quality of an audio signal The past few years have seen an explosion in the can be controlled. A person with a high access level use of digital media. Digital media offers several can hear details that another person with a lower distinct advantages over analog media including access level would not hear. Similarly, data embed- easy access, manipulation, and transmission. These ding allows users to tailor an audio signal to their advantages have opened many new possibilities. In needs, e.g., by listening to a song broadcast over a particular, it is possible to hide data (information) single channel in a particular rating. In this case, within signals. The information is hidden in the data embedding is used to embed alternative lyrics sense that it is perceptually and statistically unde- in a given version of the song that is broadcast. tectable. With many schemes, the hidden informa- The goal of this paper is to present an overview of tion can still be recovered if the host signal is modi- the challenges and issues that need to be addressed fied. by successful watermarking and data embedding Digital data embedding has many applications. techniques and the current state of the art. In the Foremost is passive and active copyright protection. next section, we review requirements for data em- Many of the inherent advantages of digital signals bedding algorithms. Insertion of the data into audio increase problems associated with copyright en- signals is then described, followed by previous forcement. For this reason, creators and distributors work in the field. Our latest research results for a of digital data are hesitant to provide access to their robust perception-based audio data hiding algo- intellectual property. Digital watermarking has been rithm are then presented. We conclude with a dis- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 64 cussion on future directions for audio data embed- between an arbitrary segment of the host signal and ding. the projection direction decreases as the size of the 2 Data Embedding Requirements segment increases, i.e., an increase in process gain. However, as that size increases, the amount of data As mentioned in the Introduction, data embedding that can be embedded in the host signal decreases. can be used in many different applications. Obvi- Post-processing effects can complicate the detec- ously, different applications will have different re- tion process. For example, synchronization prob- quirements. Therefore, there is no unique set of re- lems may arise as a consequence of temporal quirements that all data embedding techniques must rescaling, cropping, resampling, etc. Many modifi- satisfy. Nevertheless, certain requirements must be cations lead to new signals which have a different satisfied in several application areas. In this section, number of samples than the original signal with we shall review some of these requirements and in- embedded data. To extract the embedded informa- dicate when they are important [1]. tion, the extraction algorithm must adapt to the new 2.1 Perceptual Transparency signal with fewer samples automatically or access the original to register the signal. Note however that In most applications, such as copyright and usage loss of synchronization does not imply that the em- tracking, the algorithms must embed data without bedded data has been erased. affecting the perceptual quality of the underlying host signal. Furthermore, data embedding should 2.3 Bit Rate Of Data Embedding Al- not produce artifacts that are perceptually dissimilar gorithm from those that may be detected in an original host Some applications of data embedding, e.g., inser- signal. tion of a serial number or author identification, re- 2.2 Recovery Of Data With Or With- quire that relatively small amounts of information be incorporated repeatedly in the signal. However, out Access To Original Signal in some envisioned applications of data embedding, In some applications, such as copy tracking and e.g., covert communications, the algorithms must copyright protection, the data extraction algorithms be able to embed an amount of data that is a signifi- may use the original signal to decode the embedded cant fraction of the amount of data in the host sig- data. However, in most applications, data embed- nal. ding algorithms do not have access to the original audio signal while extracting of the embedded sig- 2.4 Robustness nal. This inability to access the original signal lim- Lossy signal processing operations are frequently its the amount of data that can embedded in a given applied to the host audio. Operations that damage host signal. It also renders data extraction more dif- the host signal also damage the embedded data. ficult. Furthermore, third parties may attempt to modify Specifically, the embedded data may be considered the host signal to thwart detection of the embedded as information transmitted on a communication data. The data embedding algorithm must often channel and corrupted by a strong interference and survive modifications including: channel effects. The strong interference consists of the host signal. Channel effects correspond to post- * additive and multiplicative noise; processing operations. Most data extraction proce- * linear and nonlinear filtering, e.g., lowpass fil- dures are inherently projection techniques on a tering; given direction. Ideally, a larger projection value * compression, e.g., MPEG audio layer 3, Dolby will indicate the presence of one type of data, e.g., a AC-3; binary symbol or a watermark that represents an author. A segment of the original host signal that is * local exchange of samples, e.g., permutations; highly correlated with the projection direction will * quantization of sample values; provide a false detection. Furthermore, it may be impossible to modify that segment to reduce its cor- * temporal scaling, e.g., stretch by 10%; relation with the projection direction without af- * removal or insertion of samples; fecting the perceptual quality of the host signal. * averaging multiple watermarked copies of a Hence, the algorithm may be unable to embed use- signal; ful data into that segment. Note that the projection direction cannot be easily * D/A and A/D conversions; changed since the decoder does not have access to * a second embedded signal; the original host signal. Any change in that direc- tion must be accomplished through an algorithm * frequency response distortion; that uses the received modified host signal. Note * group-delay distortions; also that the probability of getting a high correlation * frequency notches and hopping. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 65 Several of these requirements were proposed by the 3 Signal Insertion: The Role Of Recording Industry Association of America (RIAA) Masking and the International Federation of the Phono- The first problem that all data embedding and wa- graphic Industry (IFPI). In an effort to protect own- termarking schemes need to address is that of in- ers of digital audio, the entities issued a Request for serting data in the digital audio without deteriorat- Proposals in mid 1997 seeking a technology to in- ing its perceptual quality. Of course, we must be audibly embed data in audio signals. The evaluation able to retrieve the data from the edited host signal, process was carried out by the MUSE Project that is i.e., the insertion method must also be invertible. jointly funded by the recording industry and the Since the data insertion and data recovery proce- European Union. Several commercial systems were dures are intimately related, the insertion scheme submitted. However, perceptual tests revealed that must take into account the requirement of the data some of the systems tested were audible. Further- embedding application. In many applications, we more, the robustness tests indicated very mixed re- will need to be able to retrieve the data even when sults [2]. The systems did not meet the require- the host signal has undergone modifications, such ments, despite initial claims. As a result, a second as compression, editing or translation between for- round of proposals was requested. The second mats, including A/D and D/A conversions. round is currently under investigation. Data insertion is possible because the digital media 2.5 Security is ultimately consumed by a human. The human hearing system is an imperfect detector. Audio sig- In many applications the embedding procedure nals must have a minimum intensity level before must be secure in that an unauthorized user must they can be detected by a human. These minimum not be able to detect the presence of embedded data, levels depend on the temporal and frequency char- let alone remove the embedded data. Security re- acteristics of the human auditory system. Further, quirements vary with application. The most strin- the human hearing system is characterized by an gent requirements arise in covert communication important phenomenon called masking. Masking scenarios. Security of data embedding procedures is refers to the fact that a component in a given audio interpreted in the same way as security of encryp- signal may become imperceptible in the presence of tion techniques. A secure data embedding proce- another signal called the masker. Most signal cod- dure cannot be broken unless the unauthorized user ing techniques (e.g., [6]) exploit the characteristics has access to a secret key that controls the insertion of the human auditory system directly or indirectly. of the data in the host signal. Hence, a data embed- Likewise, all data embedding techniques exploit the ding scheme is truly secure if knowing the exact al- characteristics of the human auditory system im- gorithm for embedding the data does not help an plicitly or explicitly. In fact, embedding data would unauthorized party detect the presence of embedded not be possible without the limitations of the human data. An unauthorized user should not be unable to auditory system. For example, it is not possible to extract the data in a reasonable amount of time even modify a binary stream that represents programs or if he knows that the host signal contains data and is numbers that will be interpreted by a computer. The familiar with the exact algorithm for embedding the modification would directly and adversely affect data. Note that in some applications, e.g., covert the output of the computer. communications, the data may also be encrypted prior to insertion in a host signal. 4 The Human Auditory System Audio masking is the effect by which a faint but 2.6 Copyright Protection And Owner- audible sound becomes inaudible in the presence of ship Deadlock another louder audible sound, i.e., the masker [7]. Data embedding algorithms may be used to estab- The masking effect depends on the spectral and lish ownership and distribution of data. In fact, this temporal characteristics of both the masked signal is the application of data embedding or water- and the masker. marking that has received most attention in the lit- Frequency masking refers to masking between fre- erature. Unfortunately, most current watermarking quency components in the audio signal. If two sig- schemes are unable to resolve rightful ownership of nals which occur simultaneously are close together digital data when multiple ownership claims are in frequency, the stronger masking signal may made, i.e., when a deadlock problem arises. The in- make the weaker signal inaudible. The masking ability of many data embedding algorithms to deal threshold of a masker depends on the frequency, with deadlock, first described by Craver et al. [3], is sound pressure level (SPL), and tone-like or noise- independent of how the watermark is inserted in the like characteristics of both the masker and the multimedia data or how robust it is to various types masked signal. It is easier for a broadband noise to of modifications. Solutions to the issues described mask a tonal, than for a tonal signal to mask out a in [3] were derived independently in [4] and [5]. broadband noise. Moreover, higher frequency sig- nals are more easily masked. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 66 The human ear acts as a frequency analyzer and can technique to embed data by encoding it as one or detect sounds with frequencies which vary from 10 more whitened direct sequence spread spectrum Hz to 20000 Hz. The HAS can be modeled by a set signals/FSK signals and transmitted such that the of bandpass filters with bandwidths that increase signal is masked by the audio signal. In [13], the with increasing frequency. The bands are known as authors present an audio watermarking algorithm the critical bands. The critical bands are defined that exploits temporal and frequency masking by around a center frequency in which the noise band- adding a perceptually shaped pseudo-random se- width is increased until there is a just noticeable quence. difference in the tone at the center frequency. Thus if a faint tone lies in the critical band of a louder 6 Current Research tone, the faint tone will not be perceptible. Our current work on perceptual audio data embed- Frequency masking models are readily obtained ding techniques aggressively pursues the require- from the current generation of high quality audio ments mentioned in Section 2. The approach is de- codecs, e.g., the masking model defined in ISO- signed to be flexible, e.g., embedding data rates that MPEG Audio Psychoacoustic Model 1, for Layer I range from low to high, depending on the applica- [8]. tion. The algorithm employs a projection of an Temporal masking refers to both pre- and post- audio's frequency subbands onto a pseudo-random masking. Pre-masking effects render weaker signals direction dictated by a secret key. The projection is inaudible before the stronger masker is turned on, followed by a non-linear quantization step to avoid and post-masking effects render weaker signals in- the need for the original audio signal during extrac- audible after the stronger masker is turned off. Pre- tion. Furthermore, the detection process includes a masking occurs from 5-20 msec. before the masker sophisticated searching mechanism to properly syn- is turned on while post-masking occurs from 50- chronize with the embedded data without access to 200 msec. after the masker is turned off [7]. Note the original audio signal. Note that the process does that temporal and frequency masking effects have not require long random sequences to obtain the dual localization properties. Specifically, frequency significant process gain factor required by the masking effects are localized in the frequency do- popular spread-spectrum systems. The technique main, while temporal masking effects are localized uses a non-linearity to avoid the conventional use of in the time domain. matched filters. The data embedding algorithms supports many 5 Previous Audio Work features, including the ability to embed data into Several techniques have been proposed in the lit- multiple (potentially overlapping) frequency bands. erature. Most are based on spread spectrum meth- The bands are modified in such a way as to produce ods and are inherently projection techniques on a minimal interband distortion. Furthermore, the data given key-defined direction. in multiple bands may be embedded all at once, or Several approaches are described in [9]. The tech- in multiple passes. Such a feature is beneficial in niques include embedding data by modifying the copyright ownership and tracking environments phase values of Fourier Transform (FT) coeffi- where an audio signal may be repeatedly stamped cients, spread spectrum, and echo coding. Another with sales and tracking information. It is also useful audio data embedding technique is proposed in for maintaining a modification history of an audio [10], where FT coefficients over the middle fre- clip. quency bands, 2.4 to 6.4 kHz, are replaced with The data embedding algorithm is designed to be ro- spectral components from a signature. Pruess et. al. bust to many distortions. To illustrate the robust- [11] embed data into audio by shaping a pseudo- ness to distortions, 21 mono and 14 stereo audio noise sequence according to the shape of the origi- signals representing a large assortment of audio nal signal. characteristics, e.g., impulses, tonals, etc., were Some commercial products are also available. The tested. Eight of the stereo signals, muse_1, muse_2, Identification Code Embedded (ICE) system from etc., are components of the MUSE Embedded Sig- Central Research Laboratories inserts a pair of very nalling audio test material described in Section 2. short tone sequences into an audio track. Solana Text data was embedded into the audio at a rate of Corporation's Electronic DNA (E-DNA) embeds 42 bits/second (i.e., 6 printable characters/second). data into subbands of the audio signal using a Two bands of the audio are used in the experiment. spread spectrum technique. The Dice Company also The embedded text data was random in nature. No has a technique for encoding information into digi- knowledge of the data structure or length, e.g., an N tal multimedia data. Cognicity, Inc., offers Audio- Byte repeating ID code, was used to improve de- Key, an audio data embedding algorithm based on tection performance. A total of 119042 bits were the algorithm discussed below. embedded in the 35 audio signals. Advanced audio embedding algorithms take into The audio signals were encoded using Sonic Foun- account perceptual masking. Moses [12] proposes a dry's commercial Dolby AC-3 software codec. The Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 67 mono signals were encoded at a rate of 56 kbps, muse_5 0 8 10668 while the stereo signals were encoded at 96 kbps. muse_6 13 14 8820 The detection results for the mono and stereo sig- muse_7 5 2 11760 nals are shown in Tables 1 and 2, respectively. The muse_8 12 14 12390 left column in each table consists of the audio clip's yoyoma 0 0 1302 name. The next two columns, B1 and B2, list the number of bit errors made by the detection algo- TOTALS 71 93 98994 rithm in each band. The last column lists the total BER 0.17% number of bits embedded in the clip. Of the 119042 Table 2. Bit error in stereo signals after AC-3 coding bits embedded into the mono and stereo audio sig- at 96 kbps. nals, only 255 bits were incorrectly decoded. The A similar test was conducted for the MPEG Layer-3 resulting mean bit error rate (BER) is 0.21%. Note (mp3) audio codec. The software used to encode that the MUSE tracks contain 160 errors out of the signals was Opticom's commercial .mp3 Pro- 91392 bits for a mean BER of 0.17%. ducer Pro v 2.1 based on the MPEG Layer-3 audio compression technology and software implementa- ac3, 21 bps Bit Errors Bits tion licensed from the Fraunhofer IIS. The detection Audio B1 B2 Embedded results for the mono and stereo clips after coding bach 0 0 798 the audio are shown in Tables 3 and 4. Again, the castanet 0 0 252 mono signals were encoded at a rate of 56 kbps, clarinet 0 0 546 while the stereo signals were encoded at 96 kbps. cooder 0 1 1974 The mean BER for the stereo and mono signals is drum 7 2 882 1.73%. The eight MUSE tracks have a mean BER lovettl 0 0 1428 of 1.92% at 96 kbps stereo mp3 coding. Recall that lovettr 1 2 1428 the first round of competitors in the MUSE pro- moon 12 9 672 posal failed to satisfy robustness requirements at piano 10 11 420 128 kbps stereo mp3 coding. prokofiev 0 1 756 ritenourl 3 6 1330 mp3, 21 bps Bit Errors Bits ritenourr 3 9 1330 Audio B1 B2 Embedded svega 1 1 966 bach 1 1 798 tchaikov 0 0 672 castanet 2 2 252 titanic_a10m 0 1 420 clarinet 0 1 546 titanic_a30m 2 3 1344 cooder 4 5 1974 titanic_b10m 0 0 420 drum 7 5 882 titanic_b30m 0 1 1344 lovettl 4 4 1428 vivc 1 0 462 lovettr 5 2 1428 yoyomal 0 0 1302 moon 13 13 672 yoyomar 1 3 1302 piano 8 12 420 TOTALS 41 50 20048 prokofiev 5 5 756 BER 0.45% ritenourl 6 5 1330 Table 1. Bit errors in mono signals after AC-3 coding ritenourr 8 10 1330 at 56 kbps. svega 4 4 966 tchaikov 1 1 672 titanic_a10m 0 0 420 ac3, 21 bps Bit Errors Bits titanic_a30m 2 1 1344 Audio B1 B2 Embedded titanic_b10m 1 1 420 lovett 0 0 1428 titanic_b30m 1 1 1344 ritenour 1 3 1344 vivc 0 0 462 titanic_a10 0 0 420 yoyomal 3 0 1302 titanic_a30 0 0 1344 yoyomar 8 3 1302 titanic_b10 0 0 420 titanic_b30 0 0 1344 TOTALS 83 76 20048 BER muse_1 5 9 11718 0.79% muse_2 2 2 17332 Table 3. Bit errors in mono signals after mp3 coding at 56 kbps. muse_3 30 40 7658 muse_4 3 1 11046 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 68 mp3, 21 bps Bit Errors Bits represents the projection direction. As the size in- Audio B1 B2 Embedded creases, the amount of data that can be embedded in lovett 13 14 1428 the host signal decreases. Furthermore, long blocks ritenour 12 17 1344 increase problems associated with distortions. For titanic_a10 2 5 420 example, the computational requirements of syn- titanic_a30 11 10 1344 chronization algorithms are frequently higher than titanic_b10 6 3 420 order N, where N is the length of the audio block. titanic_b30 13 14 1344 As a result, the detection speed performance after the numerous distortions listed in Section 2.4, most muse_1 23 33 11718 of which require synchronization, will be very poor. muse_2 157 149 17332 Future audio data embedding algorithms should muse_3 49 67 7658 avoid the overused spread spectrum/matched filter muse_4 28 31 11046 approach. As our knowledge of masking improves, muse_5 136 127 10668 the capacity and robustness of these algorithms will muse_6 79 64 8820 improve. Further, future data embedding algorithms muse_7 227 244 11760 are likely to implement active control over the muse_8 170 168 12390 audio clips and use more sophisticated signal de- yoyoma 16 11 1302 pendent keys. TOTALS 942 957 98994 8 References BER 1.92% [1] M. Swanson, M. Kobayashi, A. Tewfik, "Mul- Table 4. Bit error rates in stereo signals after mp3 timedia Data-Embedding and Watermarking coding at 96 kbps. Technologies," Proc. of IEEE, Vol. 86, No. 6, Of course, the mean BER drops further as the em- June 1998, pp. 1064-1087. bedded data rate is reduced to 28 bits/s and 14 [2] IFPI MUSE Project: Embedded Signalling bits/s. For example, the mean BER for the AC-3 http://www.ifpi.org/technology/muse_embed.ht coded audio with an embedded data rate of 14 bits/s ml drops to 0.01%. [3] S. Craver, N. Memon, B-L. Yeo, M. Yeung, Extensive experimental results indicate that the al- "Can invisible watermarks resolve rightful gorithm is capable of surviving multiple sampling ownership?," IBM Research Report RC20509, rates, time scaling, D/A and A/D conversions, and July, 1996. Also SPIE Storage and Retrieval RealNetwork's streaming audio format. for Image and Video Databases V, vol. 3022, The new algorithm includes further enhancements pp. 310-321, Feb. 1997. to the perceptual quality of the embedded audio signal using additional characteristics of the tempo- [4] S. Craver, N. Memon, B-L. Yeo, M. Yeung, ral and frequency masking phenomena. A formal "Resolving Rightful Ownerships with Invisible investigation into the perceptual quality is currently Watermarking Techniques: Limitations, At- underway with third-party "golden ear" profession- tacks, and Implications," IBM Research Report als. Preliminary tests performed by audio engineers RC20755, March, 1997. indicate that it outperforms our previous audio data [5] M. Swanson, B. Zhu, A. Tewfik, "Multiresolu- embedding algorithm that proved transparent in a tion Video Watermarking using Perceptual series of blind tests on a mixed background audi- Models and Scene Segmentation," IEEE J. on ence. Selected Areas in Communications, vol. 16, 7 Future Directions no. 4, May 1998, pp. 540-550. Also vol. II, pp. As described in Section 2.2, many of the current 558-561, Proc. ICIP '97. audio data embedding techniques are based on [6] N. Jayant, J. Johnston, R. Safranek, "Signal spread spectrum techniques and are inherently pro- compression based on models of human per- jection techniques on a given direction. Ideally, a ception," Proc. of the IEEE, Vol. 81, Oct. larger projection value will indicate the presence of 1993, pp. 1385-1422. a binary symbol that represents an author. To re- [7] P. Noll, "Wideband speech and audio coding," duce the probability of a false detection, the length IEEE Communications Magazine, Nov. 1993, of the audio segment and pseudo-random direction pp. 34-44. are increased to reduce the chances of a high corre- lation between the original host signal and the [8] ISO/IEC IS 11172, Information Technology - pseudo-random sequence. This is inevitable in the Coding of Moving Pictures and Associated audio environment, where typical audio signals Audio for Digital Storage up to about 1.5 have a strong broadband nature that interferes with Mbits/s. the spectrum of the pseudo-random sequence which Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 69 [9] D. Gruhl, A. Lu, W. Bender, "Techniques for [11] R. Preuss, S. Roukos, A. Huggins, H. Gish, M. data hiding", IBM Systems Journal, Vol. 35, Bergamo, P. Peterson, "Embedded Signalling", Nos. 3 & 4, pp. 313-336. U. S. Patent 5,319,735, 1994. [10] J. F. Tilki, A. A. Beex, "Encoding a Hidden [12] D. Moses, "Simultaneous Transmission of Data Digital Signature onto an Audio Signal Using and Audio Signals by Means of Perceptual Psychoacoustic Masking", in Proc. 1996 7th Coding," U. S. Patent 5,473,631, 1995. Int. Conf. on Sig. Proc. Apps. And Tech., pp. [13] M. Swanson, B. Zhu, A. Tewfik, L. Boney, 476-480. "Robust Audio Watermarking Using Percep- tual Masking", Signal Processing, vol. 66, no. 3, May 1998, pp. 337-355. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 70 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 71 Watermarking in the Real World: An Application to DVD Matt L. Miller Ingemar J. Cox Jeffrey A Bloom Signafy, Inc. NEC Research Institute Signafy, Inc. 4 Independence Way 4 Independence Way 4 Independence Way Princeton, NJ 08540 Princeton, NJ 08540 Princeton, NJ 08540 (609) 734-7620 (609) 951-2722 (609) 734-7620 mlm@signafy.com ingemar@research.nj.nec.com bloom@signafy.com ABSTRACT tal versatile disks (DVD). While the difficulty of removing watermarks is an important problem in this The prospect of consumer DVD recorders application, we have been confronted with a wide va- highlights the challenge of protecting copy- riety of other problems that have been given much righted video content from piracy. Digital less attention in the literature. In this paper we will watermarking can be used as part of a copy briefly describe the DVD copy protection framework protection. We describe the copy protection in which watermarking technology is to be applied system currently under consideration for and present some of the technical challenges which DVD. We will also highlight some implemen- have not yet been adequately addressed. tation issues that are being addressed. 2 Application Framework ­ DVD Copy KEYWORDS Protection System Watermarking, DVD, copy protection In 1996, the Motion Picture Association of America 1 Introduction (MPAA), the Consumer Electronics Manufacturers Association (CEMA), and members of the computer Digital multimedia watermarking is a field that has industry put together an ad hoc group to discuss the received an increasing degree of interest from re- technical problem of protecting digital video from pi- searchers in both academic and practical settings. racy, particularly in the domain of DVD [3]. This The fundamental challenge is to hide a piece of in- group, the Copy Protection Technical Working formation into a digital image file or a video or audio Group (CPTWG), is open to anyone who wishes to stream (also referred to as the cover material) such participate, and has no official decision-making that the information is not perceived and cannot be power. However, over the past year and a half, it has removed without causing significant perceptual deg- succeeded in designing the major part of a copy pro- radation to the cover [1]. Since the watermark is tection system that is likely to become the defacto embedded into the media, it has the property that it standard for DVD. will undergo the same transformations as the media Two major principals have guided the CPTWG's and can thus be used as an indicator of what those work. The first principal is that the copy protection transformations may have been. system should not be mandatory. This immediately Some potential applications include the use of a wa- divides devices into two categories: "compliant" de- termark as a signature identifying the copyright vices, which implement the protection system, and owner, as a fingerprint identifying the customer of "non-compliant" devices, which do not. The media to the cover media, as an authentication key describing be protected must be scrambled in such a way that it some feature of the media which would likely change cannot play on non-compliant devices, or else there if the cover were manipulated, or as a copy control will be no protection at all. mechanism indicating copy permission. Most of The second principal is that the system must be cost- these applications rely on the property that water- effective. This means it is unlikely to be secure marks are not easily separated from the content or against determined hackers, since that level of secu- cover media and, consequently, research into water- rity would require more computing power than is marking has focused on the problem of making wa- reasonable in low-cost consumer devices. Rather, the termarks difficult to remove without making them aim is to come up with a system that is cheap, and perceptible[2]. good enough to prevent casual copying by the aver- Since the middle of 1996, we have been working on age user. The design mantra is "keeping honest peo- a copy control application in which watermarks will ple honest." be one part of a system for protecting video on digi- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 72 Legal CGMS Disk Compliant Compliant (CSS) Player Recording Device CSS Illegal Disk (CSS) Illegal CSS APS, 5C Non-compliant Disk Non-compliant Recording Device (No CSS) Player (DVD, VHS, etc.) Figure 1. DVD copy protection system without watermarking The system designed by the CPTWG is still a work usually leads to unwatchable recordings. Before in progress. At present, there are three components being adopted for DVD, it has been widely used that are already being built into consumer devices. on videocassettes. These are the Content Scrambling System (CSS), the Of course, the data on a disk is not NTSC encoded, Analog Protection System (APS), and the Copy Gen- so APS has to be applied by the NTSC encoder in a eration Management System (CGMS). Two addi- DVD player. The information of whether a given tional components are being seriously considered: a video stream should have APS applied, and details system for secure communications across a PC bus about how it should be applied, is stored in the (designed by a coalition of 5 companies, and hence MPEG stream header. referred to as 5C), and watermarking. The water- * CGMS is simply a pair of bits in the header of marking component, of course, is the topic of this an MPEG stream that encode one of three possi- paper. The other four components are briefly de- ble rules for copying: "copy-always" (the video scribed below. may be freely copied), "copy-never" (the video * CSS is a low-cost method of scrambling MPEG- may never be copied), or "copy-once" (a first 2 video, developed by Matsushita. To descram- generation copy may be made, but no copies ble the video, a device requires a pair of keys. may be made of that copy). The copy-once case One of the keys is unique to the disk, while the is included to support such uses as time shifting, other is unique to the MPEG file being descram- where a copy of broadcast media is made for bled. The keys are stored on the lead-in area of later viewing. Copy-once is unlikely to appear the disk, which is generally only read by compli- on pre-recorded disks, but it is important for ant drives. Keys can be passed from a DVD DVD recorders to support it. drive to a descrambler over a PC bus using a se- cure handshake protocol (different from 5C). * The proposed secure transmission system, 5C, provides a mechanism for pairs of compliant de- The purpose of CSS is twofold. First and foremost, it vices on a computer bus to exchange keys, so prevents byte-for-byte copies of an MPEG stream they can send encrypted data to one another that from being playable, since such copies won't include no other devices can decrypt. The system is the keys. Second, it provides a reason for manufac- more secure than the handshake used for CSS. turers to make compliant devices, since CSS scram- bled disks won't play on non-compliant devices. Development of 5C was prompted by the advent of Anyone wishing to build compliant devices must high-speed computer busses such as 1394, which can obtain a license, which contains the requirement that potentially carry uncompressed digital video from a the rest of the copy protection system be imple- player or set-top-box to a monitor. The fear is that a mented. pirate could tap into the bus and record any unen- * The APS system, developed by Macrovision, is crypted video being transmitted. a method of modifying NTSC signals so that The role of these copy protection devices is illus- they can be displayed on televisions, but cannot trated in Figures 1 and 2. Figure 1 shows the system be recorded on VCR's. It works by confusing without watermarking and demonstrates the need for the automatic gain control in VCR's, and this watermarking. In this illustration we assume that Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 73 Legal Disk Compliant Compliant (CSS) Player Recording Device CSS Record Ctl. Illegal Disk Playback Ctl. (CSS) Illegal CSS APS, 5C Non-compliant Disk Non-compliant Recording Device (No CSS) Player (DVD, VHS, etc.) Figure 2. DVD copy protection system with watermarking available in the marketplace will be both compliant illegal, unencrypted copies when they are made, by and non-compliant players and recording devices. making them unplayable on compliant devices. Three possible types of disks are considered: factory- Figure 2 shows the same scenario except that now pressed, legal disks containing copy protected video, watermarking is included. The two functions of the bit-for-bit illegal copies of these disks, and illegal watermark mentioned above are referred to as "rec- copies made of the video after descrambling. ord control" and "playback control", respectively. Legal disks will be scrambled with CSS and can be Record control takes over the job of CGMS. It works played only on compliant devices. Bit-for-bit copies regardless of how the video reaches the compliant of these disks won't be playable on any devices, be- recorder, since the watermark that contains the cause they won't contain the descrambling keys. This CGMS data is never removed by normal video proc- in ensured by storing the keys on the lead-in area of essing. the legal disk, which is only read by compliant Copy-once control can also be implemented in the drives. The compliant drives take precautions to pre- compliant recording device. Recording of source data vent the keys from being copied. containing this copy-once watermark is allowed, CGMS is intended to prevent illegal copies, however however some modification is made to indicate a a non-compliant player may strip out these copy third state called copy-no-more which can be treated control bits from the header, leaving the video in the the same as copy-never. clear, or unprotected. At this point there is nothing Playback control introduces a new point of protection left to indicate copy restrictions to the compliant re- in the system. Should a pirate be successful in gener- cording device and DVD RAM disks without CSS or ating a DVD RAM copy of a protected video without CGMS can be generated. CSS, this copy will still contain the watermark. Wa- Another potential weak point in the system is in the termarking allows compliant players to recognize as protection against copies being made on non- illegal a video marked with copy-never that is being compliant recorders. APS works only on VCR's, and read from an unscrambled DVD RAM and refuse 5C works only when the display device is a compli- playback. This playback control limits the potential ant, digital monitor. If the output of the player is, for market for pirated DVD to those consumers who example, analog RGB, a pirate can simply route it own non-compliant players, which will not play legal into an appropriate non-compliant recorder and make disks. an unencrypted copy. Of course, such a copy would In the summer of 1997, after receiving presentations not contain the CGMS bits. on watermarking technologies from several compa- Because of these two weaknesses, it can be expected nies, the CPTWG set up the Data Hiding SubGroup that many unprotected, illegal copies will be made. (DHSG) to evaluate these systems and determine These can be widely distributed, since they will play whether the technology is mature enough for inclu- in either compliant or non-compliant devices. The sion in the copy protection system. The CPTWG is- purpose of introducing watermarking into this system sued a call for proposals [4] in July 1997. Eleven is twofold: first, to improve the protection provided companies responded with proposals. After the initial by CGMS by making the copy-control information round of testing, seven proposals remain under con- harder to remove, and, second, to reduce the value of sideration. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 74 The remainder of this paper describes some of the the watermarking technology in Figure 2. This sug- challenges that are faced by the companies that sub- gests that the pirate has an interest in being able to mitted proposals to the DHSG. remove the watermark [5]. Watermarks that are im- 3 Challenges age independent can easily be reconstructed by frame As the copy protection system described above and averaging and, once found, can be subtracted from illustrated in Figure 2 is implemented an array of the watermarked video source. Another documented challenges related to the watermarking technology "attack" on watermarks is called sensitivity analysis have arisen. The issue of watermark removal is often in which a detector is used to reconstruct the water- addressed in watermarking literature and remains an mark in a frame by a systematic degradation of the important concern [5]. There are a number of other image. Again, once found, the watermark can be issues, some technical and some non-technical, subtracted from the video source. The field of wa- which have also come to play an important role. In termark removal is very active and the robustness of the remainder of this section we briefly introduce and watermarking techniques is constantly being chal- discuss the following issues: enforcement, system lenged. While possession, sales, and distribution of tampering, detector placement within the system, illegal copies are prohibited by law, there are no such computational cost of the detector, effects of geomet- constraints on the sales of watermark removal hard- ric distortion, interaction between the watermarking ware or software. and compression systems, false positive rates and There are two common approaches to this problem. analysis, and copy generation control. The most obvious approach is to invent a watermark that is truly tamper resistant. The other, perhaps more Enforcement - One interpretation of Figure 2 is that the DVD world may be split in two, one compliant realistic approach may seem at first to be counter in- and one non-compliant. The copy protection system, tuitive. A company that relies on the tamper resis- specifically the watermarking technology and the tance of a watermarking technology may wish to ac- CSS, will prevent legal copies from being played on tively seek out, invent, and patent any reasonable non-compliant players and illegal copies from being technique for removing that watermark. Any water- played on compliant players. This does not stop con- mark removal software or hardware using these tech- sumers from owning two players, one compliant and niques would then represent a patent infringement. A one non-compliant, and does not prevent the sale of a third approach is to introduce and pass legislation to "dual" player containing both compliant and non- outlaw the sale of watermark removal hardware or compliant drives. The approach taken to discourage software. We understand that this is being consid- the manufacture of "dual" players is to note that both ered, particularly as many countries must update the CSS and watermarking technologies are pro- their copyright law to support recent changes by the tected by patents and may only be used in a DVD WIPO. player with the proper licenses. These licenses will Beyond watermark removal there are other ways to specify that the player must not possess the capabil- circumvent the copy protection system. These in- ity of playing non-compliant DVD sources. We will clude hardware modification to disable watermark then rely on the expense of owning two DVD players detection and source scrambling such that the water- and the fact that non-compliant DVD copy protected mark detector does not recognize the source as wa- source is illegal as a violation of the content pro- termarked video. In this latter case the video must be vider's legal copyright, to help "keep honest people descrambled after it passes by the watermark detec- honest." tor. Neither of these two approaches can be used to generate an illegal copy that will play on compliant System Tampering - The illegal copy without CSS of the Figure 1 scenario was rendered unplayable by players. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 75 DVD Drive MPEG Codec (HW or SW) Watermark Bus Detector (a) DVD Drive MPEG Codec (HW or SW) Watermark Detector Bus (b) Figure 3. Watermark Detector Placement Detector Placement ­ An issue of significant debate shows the asymmetry between the watermark em- within the DHSG involves the physical placement of bedder and decoder since the motion picture industry the watermark detector in the system. This is of par- is likely to accept an embedder with very high com- ticular interest for DVD drives installed in personal putational cost and physical cost on the order of computers. Two reasonable approaches are shown in $100,000. Figure 3. In the scenario of Figure 3a the watermark Geometric Distortion ­ DVD players have the fa- detector is located inside the MEPG codec and in cility to geometrically alter the video in two impor- Figure 3b it is in the DVD drive. Each of these solu- tant ways. Letterbox is a technique which changes tions has its advantages and its disadvantages. Hav- the aspect ratio from 4:3 to 16:9. Panscan represents ing the detector in the MPEG codec is an efficient a cropping of the larger image. The watermark must solution since both the codec and the detector can survive these geometric distortions as well as more share many of the same elements (tables, buffers, arbitrary scaling and cropping which a pirate may etc.). However, this solution also allows easy crea- use to avoid watermark detection. While these issues tion of a "dual" system in a computer, since most are generally addressed in watermarking literature, MPEG decoding applications will use non-compliant this special case where a frame buffer may not be MPEG decoders. available is particularly difficult. The second scenario, which is currently leading in Watermark/Compression Interaction ­ It can be the debate, places the watermark detector in the DVD argued that a goal of video compression, to remove drive. This has the advantage that it is more tamper all visually imperceptible information, makes the resistant. Record control will prevent watermarked, challenge of imbedding a visually imperceptible wa- non-compliant MPEG bitstreams from being re- termark much more difficult. If the watermark is corded. The DVD player also has knowledge of the placed in perceptually significant component, the disk type (ROM or RAM) from which the video is source may be more difficult to compress. being read and can check for an allowed combination In the DVD application, MPEG-2 compression is of disk type and watermark (e.g. copy-never and used and it is required that the watermark be detect- copy-once should not be found on a RAM disk). able in both the compressed data stream and the re- Detector Computational Cost ­ Adding a water- constructed video. The former case requires detection mark detector to a DVD RAM drive will require in the block-based DCT domain (without frame buff- some degree of redesign. In order to minimize that ers as previously mentioned) and both cases require cost, drive manufacturers have indicated that the de- that the watermark survive MPEG quantization. An- tector must fit onto unused silicon that already exists other requirement is that the watermarks be modifi- in the drives. This restriction on the cost of the wa- able in the compressed data stream without complete termark detector in the DVD application means that decompression and that the modifications not affect the detector must be implemented in about 30k gates. the bit-rate or position of I-frames.[6] The scalability A significant implication is that the detector may not features of MPEG-2 further complicate watermark use a frame buffer and must process the video in real detection and modification in the bitstream. time without reference to previous frames. This Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 76 False Positive Rate ­ Watermark detection can gen- mark without the tag would indicate copy-no-more. erally be expressed as a binary decision and there are Since no mechanism would be provided for copying penalties associated with incorrect decisions. In the the tag, any copy would necessarily be labeled with DVD application, when the detector decides that a copy-no-more. A weakness of this method is that all watermark is present in video that does not contain a devices that do not copy the video, such as set top watermark, the result will be that a user cannot do boxes, must preserve the tag. Current set top boxes some action that should be allowed. A couple might would have to be modified for this purpose. never be able to watch their wedding video. A foot- ball fan might not be able to record the Super Bowl 4 Conclusion for time shifting. The latter example is particularly We have described here several of the difficult prob- catastrophic; if a piece of the Super Bowl triggers a lems encountered in designing a real-world applica- false positive, no one will be able to record it on tion of watermarking for copy control in DVD. DVD. Our estimates of the required false positive While the problems of fidelity and robustness have rate are about one in 1011 or 1012 distinct frames. A received significant attention in the literature, several recent model for predicting the false positive rate can of the problems encountered here are less studied. be found in [7]. The most notable of them are Copy Generation Control ­ There are a number of * Interaction with compression algorithms proposed methods for using watermarks in a copy * Overall system design to avoid circumvention generation control system. The goal is to detect a copy-once state and change it to a copy-no-more * False positive rates state as the video is being recorded. One approach is * Issues of computational costs, such as designing to use a watermark that can actually be changed. Re- detectors without using frame buffers call that this will need to be done in the MPEG The details and relative importance of these problems stream without changing the bitrate. This approach is change with different applications. But they all pose likely to be more susceptible to tampering since the fundamental challenges that must be met before wa- ability to change a watermark implies the ability to termarking can fulfill its promise as a tool for copy- remove it. right protection. Another approach involves the addition of a separate watermark. Thus the copy-once state will be indi- 5 References cated by the presence of one watermark and copy-no- [1] Cox, I.J.; Kilian, J.; Leighton, F.T.; Shamoon, more by the presence of both. To do this, the DVD T., Secure spread spectrum watermarking for recorder, with it's limited computational complexity multimedia, IEEE Transactions on Image Proc- and cost, must be able to insert the copy-no-more essing, vol.6, no.12, p. 1673-87, 1997. watermark. As with the other watermarks, this copy [2] Cox, I.J. and Miller, M.L., Review of water- control watermark must be unobtrusive, indelible, marking and the importance of perceptual mod- and robust. eling, Proc. SPIE, vol.3016, p. 92-9, 1997. The opposite approach can also be taken where the [3] Bell, A., Personal communication, 15 May, presence of two watermarks, one of which is fragile, represents the copy-once state. The recorder then has 1998. the task of removing the fragile watermark. An inter- [4] DHSG Call for Proposals, http://www.dvcc.com/ esting example of this can be found in the Macrovi- dhsg. sion/Digimarc proposal [4] in which the fragile wa- [5] Cox, I.J. and Linnartz J-P., Some General Meth- termark is a visible pattern (placed in the overscan ods for Tampering with Watermarks, IEEE area of the frame so that it will be hidden by the edge Journal on Selected Areas in Communications, of a television screen). This pattern is designed in Vol. 16, pp. 587-93, 1998. such a way that it cannot be recorded on a VCR. Thus, a copy on a VCR removes the fragile mark, [6] Hartung, F. and Girod, B., Digital watermarking and automatically converts copy-once into copy-no- of MPEG-2 coded video in the bitstream do- more. Of course, a digital recorder will still have to main, IEEE International Conference on Acous- remove the fragile watermark explicitly. tics, Speech, and Signal Processing, pp. 2621-4, A completely different approach to generation con- 1997. trol is to use information that is not embedded in the [7] Hernández, J. R., et.al., Performance analysis of watermark, but must be available to the recorder if a 2-D-multipulse amplitude modulation scheme copy-once video is to be recorded. Such information, for data hiding and watermarking of still images, often referred to as a "tag" or "ticket", might be IEEE Journal on Selected Areas in Communica- stored in MPEG headers or in the vertical blanking tions, Vol. 16, pp. 510-24, 1998. interval of analog video. In such a system, the copy- once state is represented by the presence of a copy- once watermark and an appropriate tag. The water- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 77 Digital Watermarking for Compressed Video Frank Hartung Jonathan K. Su Bernd Girod Telecommunications Labo- Telecommunications Labo- Telecommunications Labo- ratory ratory ratory University of Erlangen University of Erlangen University of Erlangen Cauerstr 7 Cauerstr 7 Cauerstr 7 D-91058 Erlangen D-91058 Erlangen D-91058 Erlangen Germany Germany Germany Phone +49 9131 8527116 Phone +49 9131 8527103 Phone +49 9131 8527100 hartung@nt.e- su@nt.e-technik.uni- girod@nt.e-technik.uni- technik.uni-erlangen.de erlangen.de erlangen.de ABSTRACT KEYWORDS The ease of reproduction, distribution, and digital watermarking, multimedia security, video, manipulation of digital documents creates compressed video, MPEG-2, MPEG-4. problems for authorized parties that wish to 1 Introduction prevent illegal use of such documents. To Digital media are replacing traditional analog media this end, digital watermarking has been pro- and will continue to do so. By digital media, we posed as a last line of defense. A digital wa- mean digital representations of audio, text docu- termark is an imperceptible, robust, secure ments, images, video, three-dimensional scenes, etc. message embedded directly into a document. These media offer many benefits over their analog The watermark is imperceptible both percep- predecessors. Analog media - such as audio cas- tually and statistically. Robustness means settes and video tapes - degrade each time they are that the watermark cannot be removed or copied. Distribution of analog media is regulated and often requires special equipment (e.g., broad- modified unless the document is altered to casting equipment). In contrast, digital data can be the point of no value. The watermark is se- stored, duplicated, and distributed with no loss of fi- cure if unauthorized parties cannot erase or delity. The data can also be manipulated and modi- modify it. Current watermarking schemes fied easily, and editing software is readily available. employ principles adopted from spread- Perhaps the most important of these properties is the spectrum communications systems, which ease of distribution. With only a personal computer, transmit a message redundantly using a low- some free or inexpensive software, and an Internet amplitude, pseudo-noise carrier signal. For connection, virtually anyone can begin distributing compressed video, the embedding is done in digital media, which is accessible to millions of peo- the transform domain of the DCT encoded ple. Clearly, digital media offer many benefits, but they also create problems for parties who wish to signal. With appropriate rate control and prevent illegal reproduction and distribution of valu- drift compensation mechanisms included, the able digital media (e.g., copyrighted, commercial, bit-rate of the compressed video is not in- privileged, sensitive, and/or secret documents). Two creased due to watermarking, and the wa- classic methods for protecting valuable documents termark is not visible. The complexity is are encryption and copy protection. While encryp- similar to the complexity of a video decoder, tion can protect documents against unauthorized ac- and the rate of the embedded watermark in- cess, the decrypted document can be copied and dis- formation is typically a few bytes per second. tributed easily. Likewise, many copy-protection The principle applies to all video compres- mechanisms employ a header, which indicates sion schemes employing motion compensa- whether or not the document may be copied. By- passing the copy-protection mechanism is a rela- tion and DCT residual encoding, like MPEG- tively simple task. As a safeguard against failures of 1, MPEG-2, MPEG-4, ITU-T H.261, and encryption and/or copy protection, digital water- ITU-T H.263. marking [1] has been proposed as a "last line of de- fense'' against unauthorized distribution of valuable digital media. A digital watermarking system em- beds information directly into a document. For ex- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 78 ample, information about copyrights, ownership, embedded into many pixels. For security, it is further timestamps, and the legitimate receiver could be modulated using a pseudo-random signal, as sup- embedded. Thus, the document itself contains the plied by a random number generator, and added to information. Digital watermarking cannot by itself the data, obeying amplitude limitations for imper- prevent copying, modification, and re-distribution of ceptibility. documents. However, if encryption and copy protec- We apply the principle to compressed video, as it is tion fail, watermarking allows the document to be stored and distributed in real-world video distribu- traced back to its rightful owner and to the point of tion systems, like the WWW or video-on-demand unauthorized use. servers. Direct manipulation of the video pixels is 2 Digital watermarking not possible, because decompression, watermarking and compression are far too complex. 2.1 Requirements In order to avoid decompression and re-compression, In general, a watermark should comply to the fol- we apply a block-wise transform of the watermark lowing requirements: signal using the DCT, that is, the same transform that * Robustness:The watermark should be reliably is used in hybrid video compression schemes like detectable after alterations to the marked docu- MPEG-1 and MPEG-2. The compressed video se- ment. Robustness means that it must be difficult quence is then partly decoded in order to have access (ideally impossible) to defeat a watermark with- to the encoded DCT coefficients. The corresponding out degrading the marked document severely. DCT coefficients of the watermark are then added to * Imperceptibility or a low degree of obtrusive- the coefficients of the video and re-encoded. All ness: To preserve the quality of the marked other parts of the video bitstream are simply copied document, the watermark should not noticeably into the new, watermarked, video bitstream. If the distort the original document. bit-rate of the watermarked video must not exceed * Security: Unauthorized parties should not be the bit-rate of the unwatermarked video, a rate con- able to read or alter the watermark. trol can easily be applied which prevents such ex- * Fast embedding and/or retrieval: The speed of cess, at the cost of less robust watermark embedding. a watermark embedding algorithm is important Details of the proposed watermarking method can be for applications where documents are marked found in [3,4]. "on-the-fly'' (i.e., when they are distributed). The The watermark recovery is easily done after decom- large bandwidth necessary for video also requires pression of the watermarked sequence by employing fast embedding methods. a correlation receiver that knows the pseudo-noise * No reference to original document: For some signal used for embedding. The original (unwater- applications, it is necessary to recover the water- maked) video sequence is not required. Details can mark without requiring the original document. again be found in [3,4]. * Unambiguity: A watermark must convey unam- 3.2 Properties Of The Proposed biguous information about the rightful owner of a Method copyright, point of distribution, etc. This re- The proposed method allows to robustly embed an quirement is a cryptographic and protocol issue. invisible watermark into compressed video se- Of these properties, robustness, imperceptibility, and quences. The watermark can carry arbitrary infor- security are usually the most important. When mation, like information about souce and destination speaking of robustness, we often talk about attacks of the data, or copyright statements. on a watermark. An attack is an operation on the The embedding is done in the transform domain of marked document that, intentionally or not, may de- the DCT encoded signal. When using the rate control grade the watermark and make the watermark harder mechanism, the bit-rate of the compressed video is to detect. For images and video, compression (e.g., not increased due to watermarking. A drift compen- JPEG or MPEG), filtering, cropping, resizing, and sation mechanism avoids visible distortion in the se- other signal processing manipulations (even printing quence which could otherwise occur due to the itera- and rescanning) must not destroy the watermark. tive structure of video compression employing mo- 3 Digital watermarking of compressed tion-compensated prediction. The embeddding com- video plexity is similar to the complexity of a video de- coder, and the rate of the embedded watermark in- 3.1 Principle formation is typically a few bytes per second. The Virtually all proposed watermarking methods build principle applies to all video compression schemes on the same basic principles, namely the application employing motion compensation and DCT residual of small, unobtrusive, random-looking changes to the encoding, like MPEG-1, MPEG-2, MPEG-4, ITU-T data that are however deterministic and can lateron H.261, and ITU-T H.263. be re-discovered by correlation [2]. For redundancy With appropriate extensions of the basic scheme as and robustness, each bit of watermark information is described in [5], the watermarks resist all known at- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 79 tacks and modifications, including collusion attacks main", Proceedings of the 1997 IEEE Interna- and geometrical manipulations of the video se- tional Conference on Acoustics, Speech, and quence. Signal Processing, April 1997, vol. 4, pp.2621- 4 References 2624. [1] H. Berghel and L. O'Gorman, "Protecting Own- [4] F. Hartung and B. Girod, "Watermarking of Un- ership Rights Through Digital Watermarking", compressed and Compressed Video", Signal IEEE Computer, May 1996, pp. 101-103. Processing, vol. 66(3), pp. 283-301, May 1998. [2] I. Cox, J. Kilian, T. Leighton, T. Shamoon, "Se- [5] F. Hartung, J. Su, and B. Girod, "Spread Spec- cure Spread-Spectrum Watermarking for Mul- trum Watermarking: Malicious Attacks and timedia", technical report, NEC, 1995. Counter-Attacks", submitted to SPIE Confer- [3] F. Hartung and B. Girod, " Digital watermarking ence on Security and Watermarking of Multi- of MPEG-2 coded video in the bitstream do- media Contents 99. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 80 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 81 Image Distribution with Scrambling and Watermarking Takehito Abe Hiroshi Fujii Youichi Takashima NTT Information and Com- NTT Information and Com- NTT Human Interface Labs. munication Systems Labs. munication Systems Labs. 1-1 Hikarinooka 1-1 Hikarinooka 1-1 Hikarinooka Yokosukashi Yokosukashi Yokosukashi Kanagawa, Japan Kanagawa, Japan Kanagawa, Japan +81-468-59-2837 +81-468-59-2639 +81-468-59-3990 take@isl.ntt.co.jp fujii@dq.isl.ntt.co.jp yoh@mistral.hil.ntt.co.jp KEYWORDS like CD-ROM or broadcasting. We propose a new image distribution, scrambling, watermarking, copy- image distribution method that uses image scram- right. bling and watermarking. Our method makes it possi- ble to embed individual user information into images 1 Introduction distributed through mass-distribution media. In fol- The advent of computer networks and mass storage lowing section, we propose our image distribution media such as CD-ROMs has made it possible for method and describe the scrambling and water- anyone to distribute digital information easily and marking technique used in our distribution method. economically. In this new environment, image distri- We then describe its implementation to the practical bution methods suitable for electronic commerce are system. being widely studied. The most serious problem is 3 Protocol piracy, which is an obstacle to spread digital image distribution over an open network. Hence, secure The image distribution protocol is shown as Figure image distribution methods are strongly required. 1. 2 Image Distribution Image Provi- User Digital images must be protected against piracy in Original image I the following two phases. The first is the dealing Scrambling with image ISC Evaluation key Ks : I phase between providers and users. The second is the SC =SCKs ( I ) $ post distribution phase at the users' end. In first Request key and provide phase, users need to see a sample of the image prior Ciphering ID, Ks EKu(ID||Ks) with Extracting ID, Ks to its purchase. However, illegal copying must be user key Ku (ID, Ks)=E -1Ku ( EKu (ID||Ks) ) prevented. For this phase, we have proposed an im- Watermarking and descram- age scrambling technique called the `image partial bling IID =SC -1Ks (WID ( ISC )) scrambling method' [1], in which the image data are Reading Watermark scrambled and only legal users can descramble the Suspect illegally used ID'=R(IID' ) IID image. In the second phase, the distributed images Investigating User- must be protected from illegal copying. It is hard to prevent images from being copied with ordinary Figure 1. Protocol of digital image distribu- copy protection methods (e.g. computer program tion and image investigation. copy protection) because the image data must be ex- Description: posed for display. For this phase, a watermarking SCKs ( ) : scrambling with image key ks SC -1 technique is usually used [2]. By embedding copy- Ks ( ) : descrambling with image key ks || : combining process right information with this technique, providers can EKu ( ) : enciphering with user key ku E -1Ku ( ) : deciphering with user key ku prove if there has been a copyright violation. WID ( ) : watermarking ID R( ) : reading watermark If an individual user's information (e.g. user ID) is embedded in the image using this watermarking A provider makes a scrambling image ISC using the technique, providers will be able to administer their image key Ks and then transmits ISC to a user. The users. However, in order to embed individual user in- user evaluates ISC and requests the key to descramble formation in each image, providers must embed the the image. The provider makes confidential data by information before distribution. Hence, these images mixing and enciphering Ks and the user information cannot be distributed by mass-distribution method ID using user key Ku, and then the provider sends the data to the user. In the descrambling module at Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 82 the user's end, Ks and ID are deciphered using Ku, 5 Implementation and the image is watermarked and descrambled at We have developed a practical image distribution the same time. As a result, the user obtains an un- system, `InfoProtect' [3] using the method discussed scrambled image by purchasing only a little data, in- above (Figure 2). In this system, users, who are reg- cluding cipher key, and moreover, the images are istered with providers and get individual user IDs, watermarked with individual user information. purchase the descrambling key for their favorite im- 4 Constituent technique ages and pay by credit card or electronic coupon. The purchased images are embedded with the user 4.1 Scrambling IDs using watermarking technique when the images We have developed methods for scrambling and de- are descrambled at users' PC. scrambling digital image data coded by JPEG or MPEG. In our method, an image is scrambled by al- 6 Summary tering the value of DCT coefficients directly in ac- We described a new digital image distribution cordance with random numbers created from the ci- method that watermarks individual user information phering key. The rough outlines of images remain when descrambling an image at the user's end. In after scrambling. The original image can be obtained this method, images can be distributed through mass- by descrambling with the (de)cipher key. The scram- distribution media and copyright is administrated bling process is very efficient. The quality of the im- after distribution. We implemented our method in the ages can be controlled by choosing which coeffi- practical system. 7 References Payment Secure Key Transmission Key Transac- Protocol [1] H. Fujii, N. Taniguchi, and Y. Yamanaka. Database "Scrambling Digital Images for Distribution Key Server through Network", Proc. of the PTC '96, 2 3 Purchase of Honolulu (1996), p. 447 Key Registrati- on [2] T. Nakamura, H. Ogawa and Y. Takashima. "A Key Watermarking Technique for Still Images", 4 Acquisition NTT R&D Vol.47, No.6 (1998), pp.711-714, (In ** Distribution of Scrambled Image Descrambling 1Image Scrambling Image (Sample) Japanese) Embedding Watermark *User ID* [3] http://www.mmlab.ntt.ocn.ne.jp/ Protection Against 5 Copyright Violation Original Image 1080285 Image Provider Descrambled Image (Embedded with ID* User ID*1080285 User Watermark Identification Figure 2. Image distribution system, InfoPro- tect. cients to alter and the degree of alteration. In addi- tion, one image can be scrambled repeatedly. 4.2 Watermarking Watermarking is a technique which imperceptibly embeds sub-information into the main digital contents. There are two main requirements for watermarking scheme. One is that quality degradation due to wa- termarking should be minimum, and second is that rewriting the watermark without quality degradation should be difficult. Our method [2] is based on well- established process of spreading watermark data en- ergy across the picture area by use of a block trans- form. Security is provided by a "key", which is a seed to an appropriate pseudo random number gen- erator. A number of other features are included to counter any attempt discover the watermarking de- tails through statistical attacks. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 83 Watermarking Multiple Object Types in Three-Dimensional Models Ryutarou Ohbuchi Hiroshi Masuda Masaki Aono IBM Tokyo Research Laboratory The University of Tokyo IBM Tokyo Research Laboratory 1623-14 Shimotsuruma 7-3-1 Hongo, Bunkyoku 1623-14 Shimotsuruma Yamato-shi Tokyo, 113-8656, Japan Yamato-shi Kanagawa, 242-8502, Japan Kanagawa, 242-8502, Japan masuda@nakl.t.u- ohbuchi@acm.org tokyo.ac.jp aono@acm.org ABSTRACT data types. As a result, data embedding techniques for these "traditional" digital content data types has Three-dimensional (3D) graphical model is been studied by many [18, 19, 23, 1, 2, 11, 17, 3, 5, about to become a full-fledged multimedia 10, 21, 22]. As 3D model gains status as an important data type, prompted by increasing popularity member of multimedia data types, prompted by in- of Virtual Reality Modeling Language creasing popularity of Virtual Reality Modeling Lan- (VRML) [7] and imminent standardization of guage [6] and imminent standardization of MPEG-4 MPEG4 [8]. [7], we added 3D polygonal model of geometry to Following an introduction on data embed- the list of data embedding targets [12, 13, 14, 15]. ding, this paper presents a discussion on po- In this paper, we will first introduce data embedding tential targets of data embedding that exist in in general, followed by a discussion on embedding both VRML and MPEG4 formats. We then targets that exists in 3D models that follows VRML and MPEG4. We will then present three embedding present several algorithms that embed data algorithms, each of which is based on vertex coordi- in shape (i.e., geometry and topology of the nate modification, vertex topology modification, and shapes) and shape attributes associated with texture coordinate modification, respectively. shape (e.g., per-vertex texture coordinates). 1.1 Data Embedding Classifications KEYWORDS In this paper, following recommendation in [16], the Three-dimensional computer graphics, geometrical act of adding watermark is called (data) embedding modeling, information security, digital watermark. or watermarking, and retrieving the information en- 1 Introduction coded in the watermark for perusal is called extrac- The advantages of digital media, such as the Internet tion. The object in which the information is embed- and CD-ROMs lies in the fact that the duplication, ded is called cover-, the object with wa- distribution, and modification of contents are much termark is called stego-, and the infor- easier than the older media, such as printed media. mation embedded is called embedded-. For example, duplication of a digital content can be The suffix "" varies with data types, such performed without any loss of its quality. These ad- as image, text, or 3D model. For example, an embed- vantages, however, are double-edged swords. Digital ded-text is embedded in a cover-polygonal mesh to media made unauthorized duplication, distribution, produce a stego-polygonal mesh with embedded-text. and modification of their valuable contents easier. A watermarks can be classified by its (1) visibility Data embedding, or (digital) watermarking put (or, more generally, perceptibility) and (2) robust- structures called watermarks into digital contents ness, as suggested by Mintzer, et al. [10]. A visible (e.g., images) in such a way that the structures do not watermark is made intentionally visible to serve their interfere with intended use (e.g., viewing) of the purposes, for example, to deter a third party from un- contents. The watermarks carry information that can authorized sales of contents. On the other hand, an be used to manage the contents, for example, to add invisible watermark is imperceptible without proc- annotations, to detect tampering, or to authenticate essing by mechanical means. A robust watermark rightful purchasers. While data can be embedded in should resists both intentional and unintentional an analog media, digital media provided an opportu- modifications of the watermarked content. A fragile nity for a robust data embedding with significant data watermark, on the other hand, must be altered by in- capacity. tentional (and some unintentional) modifications so In the past, a multimedia content typically meant a that it could detect tampering of or damage to the content that includes text, image, video, and audio content. Here, unintentional modifications are the Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 84 kind a content should expect during a course of its 2 Embedding Target Objects In 3d intended use, while intentional modifications are the Models kind that are applied with an intention of destroying 3D models in VRML [6] and MEPG4 [7] formats or altering the watermark. contain many types of objects. Among them, we con- A watermark can be classified further by its use of sider objects in the following list to be important tar- cover data for extraction. If an extraction algorithm gets for data embedding. These objects are important requires original cover data as well as the (possibly since they have relatively large quantity of redun- corrupted) stego-data, the scheme is called private dancy that can be exploited for data embedding. watermarking. Otherwise, the scheme is called pub- 1. Shape lic watermarking. An embedding scheme by Cox et al [3] is an example of private watermarking. * Polygonal Mesh Topology and Geometry A watermarking scheme may employ a random se- * Regular Mesh Geometry quence generator to make an embedded message se- * Elevation Grid Height Field Values cure from being read by a third party. For example, 2. Shape attributes in an image watermarking, positions of pixels to be * Vertex color (opacity), vertex texture coordinate, modified for watermarks can be scrambled by a vertex normal vector, etc. pseudo-random sequence generated from a stego-key * Line color, etc. (or stego-keys) by using a public-key cryptographic * Face color (opacity), face normal vector, index of method [9]. The scrambling can also be used to erase refraction, etc. (reduce) statistical signature in order to make water- * Volume color (opacity), etc. marking less detectable. Both public-key cryptogra- 3. Animation parameters phy and shared-(private-)key cryptographic method * Interpolators can be used for this purpose. * Point/vertex coordinate and orientation.. Data embedding has many potential applications. * Colors and normal vector. Obviously, requirements for data embedding scheme * Camera position and orientation. vary depending on its intended application(s). Some * Face and Body Animation Parameters of the potential applications are listed below. * Parameterized position of eyes, tongue, etc. * Theft deterrence: A robust, visible yet unobtru- * Angle of joints, etc. sive watermark in an image could deter unau- * Animated Mesh thorized sales of the image by lowering commer- * Vertex coordinates displacements. cial value of the image. 4. Others * Copyright notification: A copyright could be * 2D still texture image, movie texture. embedded as a robust invisible watermark into an * Sampled sound. image. Such notification could direct users of the model to the web site of the model's copyright * Text string, text position and orientation, text owner. color, etc. Text-to-speech phoneme strings and synthetic sound * Tamper detection: Images taken by a digital still symbol sequences (e.g., a MIDI command sequence) camera can be marked in the camera with a frag- contain little redundancy to be used as good embed- ile invisible watermark so that modification made ding targets. to the image afterward can be detected. * Content integrity check: Since MPEG4 contents 2.1.1 Shapes are editable, content creators might fear that a Shapes, or geometrical components, of 3D objects part of her/his creation is extracted and played are arguably the most important class of target, for without context, or a part of the content might is without shape, 3D model means little. While point substituted. Watermarks in polygonal models and set and poly-lines are viable candidate for data em- other 3D model contents could be used to detect bedding targets, polygonal mesh is probably the most such tampering. important target for data embedding in 3D models. * Fingerprinting: If an image is "fingerprinted" Two components, vertex coordinates and vertex to- with the identities (e.g., digital signatures) of its pology, define shape of a 3D polygonal mesh. Vertex purchaser and seller by using a robust water- coordinate combined with vertex topology defines marking technique, circulation of unauthorized more complex geometrical primitives, that are, lines, copies of the image could be traced to the pur- polygons, and polyhedrons. These geometrical chaser. primitives have their own quantities such as length of * Play or duplication control: Robust invisible a line segment and volume of a polyhedron that are watermark could control hardware devices to stop called geometrical quantities in this paper. The delivery of pornographic or violent digital-video geometrical primitives have topology of their own, contents (a la v-chip for broadcast TV in USA), which are, for example, connectivity of triangles and or to prevent unauthorized duplication. tetrahedrons. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 85 Data can be embedded in a 3D shape by modifying using discrete cosine transformation of a short se- either geometry or topology of its geometrical primi- quence of displacement values. tives. A unit of such modification is called embed- The MPEG4 proposal also contains human face and ding primitive. It is also important to arrange these body models that can be animated by transmitted embedding primitives in an order so that the arranged animation parameters. For example, a facial model is set of embedding primitive as a whole carry a sig- controlled by a set of about sixty integer values, each nificant amount of information. Arrangement can be of which specify location of eyebrows, eyes, a created either by topology or by quantity of geomet- tounge, ears, etc. Most of these parameters use small rical primitives. Details of fundamental methods to embed data into Body position interpolator shapes can be found in papers [14] and [15]. Sec- 1 tion 4 of this paper presents two data embedding al- 0.8 x y z gorithms, one that targets geometry and the other tar- 0.6 gets topology. (These algorithms have previously ap- peared in [14] and [15], but included in here for 0.4 completeness. ) 0.2 2.1.2 Shape Attributes 0 Shape-attributes, such as vertex color, per-vertex 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 -0.2 texture coordinates, per-face color and per-volume Coordinate values refractive index, are essentially sets of numerical -0.4 values that can be modified to embed data. While -0.6 less important than a shape itself, a shape attribute -0.8 still is an important class of target for embedding. The approach to embedding using shape attributes is -1 similar to those used for algorithms that employ co- Key values ordinate embedding primitives; Values of the attrib- Figure 1. Plot of key values of a VRML coordinate in- utes are modified and the modifications are ordered terpolator in an animation sequence. to embed a significant amount of information. Details of a data embedding algorithm that targets quantization levels (from 2 to 5), except for a few. texture coordinate will be presented in Section 4. The body model is controlled by over 170 parame- (This algorithm has previously appeared in [15].) ters, each of which has quantization levels of 256. 2.1.3 Animation Parameters While face animation parameters with its small Animation parameters have potentials to become quantization levels may lack redunduncy for data very important targets for data embedding. For ex- embedding, body animation parameters will have ample, if polygon-based counterparts of music videos enough redunduncy to be exploited for data embed- are made, moves of a popular musician captured to ding. animate his/her figure could carry a very high value. It must be noted, however, that the MPEG4 proposal VRML provides various interpolators for animation. contains extensive list of both lossless and lossy An interpolator is a sequence of multiple sets of val- compression algorithms for shapes, shape attributes, ues that are linearly interpolated to produce continu- and for animation parameters. Data compression al- ously varying values. These varying values can be gorithms in general try to find and remove redundun- used to translate, rotate, or deform objects. cies that are necessary for data embedding algo- Figure 1 shows an example of VRML interpolator rithms. Embedding algorithms must take these data data generated by a 3D modeling and animation compression algorithms into account. software. It is a plot of trajectory of the torso of a 2.1.4 Others skateborder model as it performs a manuever called Sampled sound, 2D still texture and 2D movie tex- "540". In the torso alone, this animation sequence ture are obvious targets of embedding by using data contained 53 coodinate points, each of which is a 3D embedding algorithms developed previously for re- coordinate. Combined with the other parts, such as spective data types. However, care must be taken in head, upper-arm, lower-arm, camera, etc., there are using these objects for embedding since these objects siginificant amount of data that can be exploited for in a 3D model can be removed effortlessly. embedding in the animated 3D model. 3 Embedding Algorithms For 3D Po- The MPEG4 proposal [7] contains other types of data objects for animation. It contains animated (deform- lygonal Meshes ing) regular mesh whose vertices move over time In this section, we will present algorithms that target given a continuously transmitted list of incremental shape and a shape attribute of polygonal meshes for displacements. The displacements may be coded in data embedding. All the algorithms in this section are two ways, either by using simple difference or by implemented by using a kernel for a non-manifold modeler [9]. The system employs radial edge struc- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 86 ture [20] to represent the topological relationship For each triangle, the algorithm first modifies the ra- among vertices, edges, faces, and regions. tio hi/eij by changing hi only. Then the algorithm 3.1 An Algorithm Based On Geometri- modifies the ratio eij/ekl while keeping the height hi cal Quantity Modification constant. In order to embed the message repetitively, A pair of dimensionless quantities, for example, steps (1) to (4) are repeated many times. {e Figure 4 shows triangles that formed MEPs in darker 14/e24, h4/e12} in Figure 2, defines a set of similar gray. Due to the mutual exclusion rule described in triangles. The algorithm described in this section, the step (1) above, MEPs do not share vertices. Triangle Similarity Quadruple (TSQ) algorithm, uses Given a watermarked mesh and two numbers that such dimensionless quantity pair as the geometrical identify marker triangles, extraction proceeds ac- embedding primitive to watermark triangular cording to the following steps. meshes. (1) Traverse a given triangular mesh and find a tri- The TSQ algorithm can be classified as a public wa- angle with the marker, thereby locating a MEP. termarking scheme. Watermarks produced by the (2) Extract a subscript and two data symbols from TSQ algorithm withstand translation, rotation, and the triangles in the MEP. uniform-scaling transformations of the stego- (3) Repeat (1) to (2) above for all the marker trian- polygonal-meshes. An embedded message is resis- gles on a given triangular mesh. tant to resection and local deformation if it is repeat- (4) Sort the extracted symbols according to their edly embedded over a mesh. The watermarks are de- stroyed, among other disturbances, by a randomiza- tion of coordinates, by a more general class of geo- v0 metrical transformation, or by a topological modifi- e cation such as re-meshing. e 02 In order to realize subscript ordering, the algorithm 01 h S uses a quadruple of adjacent triangles in the configu- 0 e v 12 2 v ration depicted in Figure 2 as a Macro-Embedding- 1 Primitive (MEP). Each MEP stores a quadruple of e M e25 symbols {Marker, Subscript, Data1, Data2}. In Fig- 13 h h4 h 3 e 5 ure 2, the triangle marked M stores a marker, S stores 14 e24 D2 D1 a subscript, and D1 and D2 stores data values. A v3 e v marker is a pair of values that identifies MEPs. As e34 v 5 4 45 mentioned above, this public watermarking scheme Figure 2. A macro-embedding-primitive. In the figure, vi does not require cover-polygonal-mesh for extrac- are vertices, eij are lengths of the edges, and hi are heights of tion. However, the marker value pair is necessary for the triangles. extraction. A watermarked mesh would contain mul- tiple MEPs to embed a significant amount of data as shown in the example of Figure 3. While each MEP is formed by topology, a set of multiple MEPs is ar- "b" ranged by quantity of the subscript. "m" "n" M The TSQ algorithm embeds a message according to s(2) M the following steps. (For the detailed explanation and s(1) "g" s(5) execution examples, please refer [14].) M "e" (1) Traverse the input triangular mesh to find a set "-" of four triangles to be used as a MEP. MEPs "e" must not share edges or vertices to avoid inter- "i" M "D" "d" ference. M M "d" s(3) (2) Embed the marker value by changing a dimen- s(0) s(4) "3" sionless quantity pair in the center triangle of the MEP. In Figure 2, it is {e14/e24, h4/e12}. This modifies positions of vertices v1, v2, and v4. (3) Embed a subscript and two data symbols in a Figure 3. In this example of TSQ watermarking, six macro embedding primitives on a mesh embed a string "3D- similar manner by displacing vertices v0, v3, and embedding". Subscripts (denoted s(i) for a subscript i) ar- v5. Subscript is embedded in the pair {e02/e01, ranges the MEPs. h0/e12}, and two data symbols are embedded in the pairs {e subscripts. 13/e34, h3/e14} and {e45/e25, h5/e24}. (4) Repeat (1) to (3) above until all the data symbols The TSQ algorithm embedded 210 bytes of data, that of the message are embedded. is, 0.15 byte/triangle, in the model of Figure 4, which consisted of 1406 triangles. Experiments using seven Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 87 polygonal mesh models showed that the TSQ algo- (1) Starting from an edge e selected from the input rithm was able to embed 0.15-0.18 byte/triangle. mesh M, grow a triangle strip S on M by using the message bit-string to determine the direction of growth of the strip. Observe that a triangle at the end of (current) strip has two "free" edges, i.e., edges that are not adjacent to triangles of the current triangle strip. Since M is orientable, these two edges can be ordered on the triangle by traversing the edges in a fixed order (either counterclockwise or clockwise). Depending on the data bit, choose one of the two free edges as the edge to be shared with the next triangle of the strip. (See Figure 6.) (2) "Peel off" the triangle strip S from M by splitting all the edges and vertices on the boundary of S except the initial edge e. The strip S is connected to the rest of the mesh only by the edge e. The edge e serves as the initial condition for finding the triangle strip. Arrangement of embedding primi- tives is induced naturally by the connectivity of tri- angles on the triangle strip. Since the peeled strip Figure 4. Macro embedding primitives, each of which caps the hole completely, proper colors and vertex consists of four adjacent triangles, are shown in dark normal vectors make the watermark invisible. 3.2 An Algorithm Based On Topologi- Figure 6 shows an example of a triangle strip. The cal Modification strip drawn with solid lines, which start at edge e, The Triangle Strip Peeling Symbol sequence (TSPS) embeds a bit string "10101101011" in a sequence of embedding algorithm that will be presented in this 12 triangles. Each bit of the bit string steers the di- section is a public watermarking scheme based on a rection of growth of the triangle strip. If the last bit topological embedding primitive. It employs, as its of the string is "0" instead of "1", the last triangle embedding primitive, an adjacency of a pair of trian- will become the one that is drawn with broken lines. gles in a triangle strip, each of which encodes a bi- Steering by message bit strings produces strips nary bit of information. One-dimensional arrange- whose shape may not fit in a given mesh, depending ment of embedding primitives is induced by the ad- on a given bit string. In the example of Figure 6, a jacency of triangles on the triangle strip. To recog- message bit string with all "1" would keep steering nize the triangle strip with watermark, the strip is the strip to the left. If the message string is suffi- peeled off from the original mesh. ciently long, the strip will either hit the boundary of Since both embedding primitive and arrangement are the mesh or circle back to itself. To avoid this prob- topological, watermarks produced by the algorithm lem, shapes, locations and orientations of the strips are immune to geometrical transformation. Repeti- must be controlled carefully. We manipulate the tive embedding makes the watermarks resistant to re- shape of the triangle by using steering symbols. A section. The watermarks can be destroyed by topo- steering symbol is a bit that does not carry informa- logical manipulations, for example, by polygon sim- tion but simply steer direction of growth of a triangle plification algorithms. A disadvantage of this algo- strip. Steering symbols are interleaved with data rithm is its low space efficiency compared to many symbols, that are, symbols that encode embedded algorithms based on geometrical primitives. data, in order to control shape of triangle strips. Ob- Inputs to this embedding algorithm are an orientable viously, steering symbol halves the embedding data triangular mesh and a message bit string. The TSPS capacity. Our current implementation determines embedding algorithm embeds data according to the initial locations, directions of growth, and shapes of following steps. (See Figure 5.) triangle strip manually. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 88 would stitch the triangle strip back to the stencil mesh. Such mending can be prevented to some extent by modifying topology of stego-polygonal-mesh in e order to confuse mending algorithms. For example, vertices, edges, and polygons can be added into the stencil mesh R so that finding correspondence of M M M edges and vertices to be stitched together is difficult (a) Original mesh. (b) Generate triangle strip S (Figure 5(d)). based on the message bit string. 3.3 An Algorithm Based On Shape At- tribute Modification e S e An algorithm explained below embeds data in texture coordinates of polygonal mesh. A similar algorithm can be used to embed data in other per-vertex attrib- M' = R+S Peeled strip Peeled strip S M+ =R +S S utes, such as vertex colors. Data embedding into per- m (c) Cut out the strip S from (d) Scramble mesh topology face attributes of a polygonal mesh surface is also the mesh M, except at the of the stenciled mesh (M- possible; Modify per-face attributes and then arrange edge e. S) by adding vertices, these modified attributes. edges, and polygons, if A set of texture coordinates associated with vertices necessary. of a polygonal model is a good target for data em- Figure 5. Triangle strip S encoding a message bit string bedding. This is because a set of roper texture coor- is peeled off from the cover-polygonal mesh M. (The dinate is crucial to properly render texture mapped cracks around S in the figure is for illustration purpose objects, and a set of texture coordinates is difficult to only.) regenerate once it is lost. The algorithm we experimented modulates amplitude 0 of texture coordinates based on message bit string. e 1 1 0 1 1 1 0 1 0 0 1 Figure 6. Connectivity of 12 triangles (drawn with solid lines) in a triangle strip encodes the bit string "10101101011" (11 bits). If the bit string is "10101101010" (change in the last bit), the last triangle will be the one drawn with broken lines. Extraction of a message is carried out according to the following steps. Traverse the watermarked mesh and find an edge Figure 7. A triangle strip consisting of 27 triangles with topological features that starts a triangle strip of was cut out from a flat triangular mesh (214 triangles). The triangle strip, displayed in darker gray, encodes 13 known length that is attached to the stencil mesh by data bits interleaved with 13 steering bits. an edge. Starting from the initial edge, traverse the triangle Let si be ith bit of a bit string S. The embedding algo- strip to the open end as embedded bits are extracted. rithm modifies a coordinate value xi (e.g., either u or Figure 7 shows a simple example of TSPS embed- v) of a texture coordinates by the following steps, ding, in which a triangle strip of length 27 is peeled given a modulation amplitude A. off from a mesh that consisted of 214 triangles. The r=xi-xi/A; triangle strip encodes 13 data bits and 13 steering if si=`0' then b=A/4 else if si='1' then b=A*3/4; bits. Selection of steering bits in this case was done x manually. As another example, a model of triceratops i= r+b; (499 triangles) in Figure 8 is marked with a triangle This is just an example of modulation method. Many strip of length 19 triangles, which encodes 9 bits. other alternatives, including multi-valued modula- (The colors of the strips in these examples are inten- tions, are possible. Whatever the modulation method, tionally changed to show their location.) we can make two such modulations per 2D-texture Watermarks produced by the TSPS embedding algo- coordinates. Thus, if we embed one bit per floating rithm can be erased if a geometrical "mending" pro- point number, we can embed 2N bits into N 2D- gram, for example the one similar to [4], which texture coordinates. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 89 In modifying the texture coordinate, the modulation as the arrangement for embedding. This arrangement amplitude A must be chosen so that the watermark is robust enough without degrading quality of texture mapped objects. We conducted experiments to see how amplitude affect appearances of texture-mapped 3D polygonal mesh objects. Some of the results are shown in Figure 9 and Figure 10. (a) Ar=0 (No embedding) (b) Ar=0.1 % (c) Ar=0.5 % (d) Ar=1 % Figure 8. A triangle strip, 19 triangles long and shown Figure 9. A red-and-white stripe image is mapped in a light gray, is generated and peeled off from a model onto a sphere model (1800 triangles). Texture coordi- of a triceratops (499 triangles). (A part of the strip is not nates are modulated with relative amplitudes Ar=0 % visible from this viewpoint.) to Ar=1 %. Texture images are a synthetic red-and-white stripe image (256 x 256 pixels) and a photograph of a hu- man face with a tree leaves in background (300 x 300 pixels image area, 1024 x 1024 pixels overall). These images were texture-mapped onto a model of a sphere tessellated into 1800 triangles, which contained 961 vertices (and thus 961 texture coordinate). We can embed a maximum of 961 bytes in the sphere if we modify four bits per single- precision floating-point number. In this experiment, (a) Ar=0. (No embed- (b) Ar=0.1 % we embedded a 358 byte long text. ding) In the figures, Ar is the modulation amplitude rela- tive to the range of texture coordinate variation on the model. In these examples, the texture coordinates varied in the range [0,1] in both u and v coordinates so that the maximum variation range of texture was 1.0. In another word Ar=0.1 % means amplitude of 0.001. In Figure 9, in which the red-and-white stripe texture is used, distortion in the rendered image is percepti- ble in rendered images when Ar=0.5 % (Figure 9c) and Ar=1 % (Figure 9d). Complex, less geometrical, (c) Ar=0.5 % (d) Ar=1 % texture images reduced perceptibility of texture dis- tortions. Distortions of the human face texture shown Figure 10. A photograph of a human face is mapped in Figure 10 were difficult to perceive. Even for the onto a sphere model (1800 triangles). Texture coordi- image with Ar=1 % (Figure 10c), a careful compari- nates are modulated with several relative amplitudes son with the original image (Figure 10a) was neces- Ar=0.0% to 1%. sary to reveal distortions. In our prototype implementation, we used the order of appearance of texture coordinates in the input file Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 90 is destroyed easily by shuffling the positions of the [4] A. Gueziec, G. Taubin, F. Lazarus, and W. texture coordinates in the file. If this is a problem, Horn, Cutting and Stitching: Efficient Conver- there are alternative methods to introduce ordering sion of a Non-Manifold Polygonal Surface to a into a set of texture coordinates. Since each texture Manifold, IBM Research Report RC-20935 coordinates is associated with a vertex, ordering ver- (92693), July, 1997. tices implies ordering of texture coordinates. Several [5] F. Hartung and B. Girod, Copyright Protection examples of methods to order vertices are described in Video Delivery Networks by Watermarking in [14]. It is also possible to arrange texture coordi- of Pre-Compressed Video, Lecture Notes in nate by using a non-geometrical quantity itself. In the Computer Science, Vol. 1242, pp.423-436, example of texture coordinate, texture coordinate or Springer, 1997. quantity derived from it can be used to order vertices. Note that watermark that modifies geometry and/or [6] ISO/IEC 14772-1 Virtual Reality Model Lan- topology of a polygonal mesh do not interfere di- guage (VRML). rectly with non-geometrical attributes. It is possible [7] ISO/IEC JTC1/SC29/WG11 MPEG-4 Visual to combine an attribute-modifying algorithm (e.g., and MPEG 4 SNHC. the one described in this section that modifies texture [8] H. Masuda, Topological Operations for Non- coordinate) with an algorithm that modifies geometry Manifold Geometric Modeling and Their Appli- or topology (e.g., the triangle strip peeling algo- cations, Ph. D dissertation, Department of Preci- rithm). sion Machinery Engineering, University of To- This experiment showed that, if modification ampli- kyo, 1996 (in Japanese). tude is chosen appropriately, data embedding into texture coordinates is possible without noticeable [9] A. J. Menezes, P. C. van Oorshot, and S. A. change in the models rendered appearance. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. 4 Summary And Future Work In this paper, we first presented introduction to data [10] F. Mintzer, G. W. Braudway, and M. M. Yeung, embedding technology. It is followed by a discussion Effective and Ineffective Digital Watermarks, on possible data embedding targets that exist in 3D Proceedings of the IEEE International Confer- models, that are, shape (both topological and geomet- ence on Image Processing (ICIP) '97, Vol. 3, pp. rical components of shape), shape-attributes (e.g., 9-12, 1997. texture coordinates and vertex color), and others, [11] J. J. K. O'Ruanaidh, W. J. Dowling and F. M. such as mesh animation parameters and face/body Boland, Watermarking Digital Images for Copy- animation parameters. As examples, we presented right Protection, IEE Proc.-Vis. Image Signal three algorithms. Two of the algorithms embed data Process., Vol. 143, No. 4, pp. 250-256, August in shape, using both geometry and topology of 3D 1996. polygonal meshes. The other algorithm embeds data [12] R. Ohbuchi, H. Masuda, and M. Aono, Embed- in a shape-attribute, that is, texture coordinates, of ding Data in 3D Models, in Steinmetz, et al. eds, 3D polygonal mesh models. Lecture Notes in Computer Science No. 1309, In the future, we would like to experiment with algo- pp.1-11 (Proceedings of the IDMS '97, Darm- rithms that embed data in animation parameters that stadt, Germany, September) 1997. exists in MPEG4 and VRML formats. We need to evaluate effects of data compression algorithms used [13] R. Ohbuchi, H. Masuda, and M. Aono, Water- in these formats to compress shape, shape attributes, marking Three-Dimensional Polygonal Models, and animation parameters. We also would like to de- Proceedings of the ACM Multimedia '97, Seat- velop and test realistic scenarios employing data em- tle, Washington, USA, November 1997, pp. 261- bedding algorithms for 3D models. 272. 5 REFERENCES [14] R. Ohbuchi, H. Masuda, and M. Aono, Water- marking Three-Dimensional Polygonal Models [1] W. Bender, D. Gruhl, and N. Morimoto, Tech- Through Geometric and Topological Modifica- niques for Data Embedding, IBM Systems Jour- tions, pp. 551-560, IEEE Journal on Selected nal, Vol. 35, Nos. 3 & 4, 1996. Areas in Communications, May 1998. [2] G. Braudway, K. Magerlein, and F. Mintzer, [15] R. Ohbuchi, H. Masuda, and M. Aono, Geomet- Protecting Publicly-Available Images with a rical and Non-Geometrical Targets for Data Em- Visible Image Watermark, IBM Research Re- bedding in Three-Dimensional Polygonal Mod- port, TC-20336 (89918), January 15, 1996. els, to appear in August 1998 issue of the Com- [3] I. J. Cox, J. Kilian, T. Leighton, and T. puter Communications, Elsevier. Shamoon, Secure Spread Spectrum Watermark- [16] B. Pfitzmann, Information Hiding Terminology, ing for Multimedia, IEEE Trans. on Image in R. Anderson, Ed., Lecture Notes in Computer Processing, Vol. 6, No. 12, pp1673-1678, 1997. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 91 Science No.1174, pp. 347-350, Springer-Verlag, ing for CAD Applications, North Holland, pp. 3- 1996. 36, May 1986. [17] J. R. Smith and B. O. Comiskey, Modulation [21] M. M. Yeung, F. C. Mintzer, G. Braudway, and and Information Hiding in Images, in R. Ander- A. R. Rao, Digital Watermarking For High- son, Ed., Lecture Notes in Computer Science Quality Imaging, Proceedings of the First IEEE No.1174, pp. 207-296, Springer, 1996. Workshop on Multimedia Signal Processing, [18] K. Tanaka, Y. Nakamura, and K. Matsui, Em- Princeton, NJ, USA, June, 1997, pp. 357-362. bedding Secret Information into a Dithered [22] M. M. Yeung and F. Mintzer, An Invisible Multilevel Image, Proc. 1990 IEEE Military Watermarking Techniques for Image Verifica- Communications Conference, pp. 216-220, tion, Proceedings of the IEEE ICIP '97, Vol. 2, 1990. pp. 680-683, 1997. [19] S. Walton, Image Authentication for a Slippery [23] J. Zhao and E. Koch, Embedding Robust Labels New Age, Dr. Dobb's Journal, pp. 18-26, April into Images for Copyright Protection, Proc. of 1995. the Int'l. Congress on Intellectual Property [20] K. Weiler, The Radial Edge Structure: A Topo- Rights for Specialized Information, Knowledge, logical Representation for Non-Manifold Geo- and New Technologies, Vienna, August 1995. metric Boundary Modeling, Geometric Model- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 92 Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 93 Non-Invertible Watermarking Methods for MPEG Video and Audio* Klara Nahrstedt Lintian Qiao Department of Computer Science Department of Computer Science University of Illinois at Urbana-Champaign University of Illinois at Urbana-Champaign Urbana, IL 61801, USA Urbana, IL 61801, USA 217-244-6624 217-244-6624 klara@cs.uiuc.edu l-qiao@cs.uiuc.edu ABSTRACT schemes and how to resolve the rightful ownership of the invisible watermarking schemes. Craver et al Various digital watermarking techniques attacked existing watermarking techniques by pro- have been pro-posed in recent years as the viding counterfeit watermarking schemes that can methods to protect the copyright of multi- be performed on a watermarked image to allow media data. However, the rightful owner- multiple claims of ownerships. We refer to their ship problem has not been properly solved attack as the CMYY (Craver-Memon- Yeo-Yeung) as it is a non-trivial task to construct a non- attack. The rightful ownership problem is either not invertible watermarking process. In this pa- addressed at all or not addressed properly within per we give a brief overview of our water- current existing watermarking techniques. marking solutions which were proved to be In this paper we will briefly outline our solutions non-invertible in [4] and are successful in towards watermarking schemes applied to MPEG Video and Audio which have the properties of be- resolving rightful ownership of water- ing invisible and non-invertible. We introduce re- marked MPEG video and audio. quirements on the watermark construction so that We will discuss various issues of the water- the whole watermark has to be created by using a mark construction process, and watermark standard encryption function, e.g. DES. Because of embedding schemes applied to MPEG video these requirements, the non-invertibility of the pro- and audio. posed scheme is easily proved as shown in [4]. KEYWORDS Furthermore, we brie y discuss the watermarking methods for MPEG video and audio with the main Watermarking, Non-invertibility, Ownership, goal to make the watermark invisible. Copyright, MPEG Video and Audio The paper is outlined as follows: Section 2 presents 1 Introduction the rightful ownership and non-invertibility prob- With the growth of multimedia systems in distrib- lem, Section 3 and 4 discuss the non-invertible uted environments, the research of multimedia se- schemes for MPEG video and audio and Section 5 curity as well as multimedia copyright protection concludes the paper. becomes an important issue. Digital watermarking 2 Rightful Ownership and Non- techniques have been proposed in recent years as invertibility Problem the methods to protect the copyright of multimedia data. There are various watermarking schemes ap- The purpose of a watermark is to protect the plied to images and several methods applied to owner's copyright. But without a careful scheme audio and video streams. Among them, a large class design and proper requirements on the watermark, of watermarking schemes addresses invisible wa- an attacker can easily confuse everyone by ma- termarks. Craver et al [2] also pointed out the prob- nipulating the watermarked video (image, audio) lems of non-invertibility1 for watermarking and claim that he/she also is the original owner. This is called the "rightful ownership" problem. Craver et al provided the following scenario: given a watermarked video (image), it is possible for an attacker to watermark the watermarked video (im- 1 Informally, non-invertibility means that it is computa- tionally impossible for an attacker to find a pair of a fa- ked image and a watermark such that the pair can result * This research was supported by National Science in the same watermarked image created by the real ow- Foundation Career Grant CCR-96-23967 and Research ner. Board of University of Illinois at Urbana-Champaign. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 94 age) again using any watermarking scheme. This conclude that the use of timestamps is not a good twice watermarked video (image) has both original way to solve the watermark ownership problem. and attacker's watermarks on it. Both the original owner and the attacker can claim the ownership, 3 Non-invertible Scheme for MPEG therefore, defeat the purpose of using watermark. Video Using the original video clip (image) in the verifi- One possible approach against CMYY attack is to cation process can prevent the multiple ownership make a strict requirement on the construction of the problems in some cases. However, even with the watermark and bind the watermark with the original presence of the original video clip (image), the video (image) itself. This will greatly limit the rightful ownership problem still exists. Craver et al choices of the watermark WF and the falsified showed that the following scenario is possible: original" VF for an attacker. Clearly, if it is com- Assume that the original video clip (image) is V. putationally impossible for an attacker to find both The owner of the video clip uses watermark W to WF and VF which satisfy formula (2), then the non- create a watermarked video clip (image) V invertibility is achieved. In this section, we will de- W, and publishes V rive such a scheme which applies to the MPEG- W. We denote this process as V W => V encoded video streams. Of course, the derived W (1) The attacker creates a watermark WF , without schemes must not belong to the Self-Proof Class. knowing V, extracts WF from VW and creates a We will refer to V as a single I frame within the I, counterfeit video clip (image) VF . Notice that, P, B sequence of a MPEG stream. VF WF => VW (2) 3.1 Watermark Construction In this way, the attacker can use VF as his \original" Here we only describe the watermark construction and claim the ownership of VW. on a single image V which is encoded in JPEG If (2) can be achieved, then that scheme is called format. It can be easily extended to the I frames of invertible watermarking. Otherwise, it is called MPEG video clips. The method which we will use noninvertible watermarking. is based on the ideas from direct sequence spread There is a class of invisible watermarking schemes spectrum communications. which do not use original image (video clips) in the First, we choose a standard encryption function, verification process. We will refer to these schemes such as DES, and a key KEY . In Zig-Zag order, we as Self-Proof Class. Because the use of the Self- scan each block of the DCT-transformed image. Proof Class is simpler than that of other water- Let ACb,l denote the value of the l-th AC coeficient marking schemes, it is interesting to study its non- in the block b, where b = 1 ... nb, and nb is the invertibility. We want to know Are there any non- number of blocks in V , l = 1...63. Let invertible schemes which belong to the Self-Proof NZ Class?". Unfortunately, the answer is NO as shown b;l = 1 if ACb;l 6 0; 0 otherwise. (3) Let nAC in [4]. l; l = 1:::63 denote the total number of nonzero AC coeficients at the l-th position of each Of course, one can add the requirement of water- block, i.e., mark construction to the Self-Proof Class schemes. nAC But in order to verify the watermark construction, l = 1 b nb NZb,l (4) For example, if AC something other than watermarked image itself has 1;5 = 1, AC2,5 = -2, AC1001,5 = 4, AC to be presented. This contradicts to the concept and b,5 = 0 in all other blocks, then nAC5 = 3. Second, we transform first m (1 m _ nb) nAC the definition of Self-Proof Class scheme. l into binary numbers and concatenate those binary Another attempt to resolve the ownership problem numbers to form a PAD, i.e., PAD = nAC is provided by Wolfgang and Delp [5]. Their 1...nACm. The choice of m will depend on the number of bits method uses timestamp to generate the watermark. which can be embedded into the frame V . For ex- Then the owner with the earliest timestamp is the ample, for a standard MPEG-1 video with picture true owner. However, this scheme can be easily de- size 352x288 (pixels), there are totally 1584 blocks. feated because timestamps can be manipulated. For Therefore, 11 bits are required to represent each example, for a certain event such as "the Berlin nAC Wall came down", everybody knows exactly when l because 210 = 1024 < 1584 < 2048 = 211. If we are allowed to embed totally 101 bits, m will be it happened. If an attacker uses that time as his/her [101/11] = 10. timestamp in watermarking the video/image taken Third, we apply DES with KEY to PAD and get during that event, then who is the original owner? EPAD = DES The following example may be more realistic: in KEY (PAD). Forth, let us consider definitions of the following some videos, the real time clocks may be displayed bit sequences: somewhere in the picture, such as news broadcast- - Let Aj be a bit sequence, where j=1 ... total ing, basketball games, etc. The timestamps can be number of bits allowed to embedded in V, such accurately decided in these cases. Again, if an at- that tacker uses these timestamps, then who is the origi- A nal owner? Based on the above discussion, we can j = -1 if EPADj = 0; 1 otherwise (5) Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 95 - Let Bi be a bit sequence, such that 4. We want to achieve that the total length of a Bi = Aj, (j × Cr) i < ((j + 1) × Cr) (6) watermarked stream is less than or equal to the where Cr is the chip-rate2. total length of the original stream, so that the - Let pi be a bit sequence, such that watermarking process does not defeat the com- pi= -1 if i-th bit of DESKEY(V ) is 0; 1 other- pressing process of MPEG. wise (7) 5. In our scheme, the original video stream and a Last, we construct the watermark bit sequence by key are needed for both the watermark creation combining the sequences Bi and pi: and the verification process. w With the considerations of the above assumptions i = × Bi × pi; i = 1...(Width × Height) (8) We will discuss how we select the scaling number and requirements, we design an algorithm as fol- in the next subsection. lows: 3.2 Watermark Embedding Procedure 1. 1. A new watermark is created based on the encrypting information from the original I; We There are several assumptions which need to be denote the process as w mentioned before we describe our scheme. i = DESKEY (vi). We then put the sequence w 1. We will derive a watermarking scheme for i into a two dimension matrix of (Height × Width). The result is a MPEGcompressed video without fully decod- watermark in the form of a raw image. ing the video to raw image sequence and then 2. DCT is applied to the watermark; encoding again. We decode the video up to the 3. An AC coefficient in the original image V is DCT coeficients and then embed a watermark marked if the length of the resulting VLC into the stream at the DC and AC coeficient (Variable Length Code) does not increase. level. 4. An AC coefficient is marked and the last non- 2. We set = 1. Tests on various MPEG clips zero AC coefficient (in the zig-zag order) of a show that, with chip-rate 1000, if we water- block in the original image V is dropped if the mark the DC coefficients, then the water- total length of the resulting VLC does not in- marked video has lower quality and the water- crease. No more than two AC's can be dropped mark is visible. One way to solve this problem within a block.3 is to increase the chip-rate, for example, to We now discuss the results and the implications of 5000, but this will decrease the amount of in- the proposed scheme. formation that can be embedded by a factor of 1. Formula (nAC 5. Therefore, this is not a good solution. We l in VW) < (nACl in V ) always holds. This is because, for each block, there are choose not to mark any DC coefficients. (Set- three possible outcomes: the number of non- ting to a small number can also avoid the zero AC's decreases by 0 (unchanged), 1, or 2 quality degradation, but this means that there in comparison with the original video frame V . are many choices for in one scheme and dif- The outcome depends only on the original V ferent can be chosen in different schemes. and the key KEY . It is easy to see, the total This uncertainty gives an attacker freedom to number of nonzero AC coefficients in VW de- manipulate the verification process. Therefore, creased. In addition, the values of some non- we fix = 1.) zero AC coeficients in VW could also be 3. We only watermark I frames because I frames changed and the changes also depend only on are the most significant frames in a video V and KEY. stream. The watermark of I frames will be car- 2. The randomness of the embedded information ried over to P and B frames due to the depend- is guaranteed by the encryption function DES. ency between I, P, and B frames. It is true that pi in the spread spectrum scheme is the Pseudo an attacker could drop all watermarked I Random Noise Code. By applying DES to V, frames to get an unwatermarked video stream. we can create a Pseudo Random sequence of However, although P and B frames may con- values 1/-1 which can be used as pi. By choos- tain some I-blocks which can be de-coded by ing different KEY, a different pi sequence is themselves, there is enough dependency be- created. The KEY is safe due to the DES en- tween the I frame and the P and B frames, cryption algorithm which means that it is com- therefore, the quality of the P or B frames will putationally impossible for an attacker to find be bad enough if the I frames are dropped. out the key even with the knowledge of V. Furthermore, we only watermark the lumi- 3. The information contained in PAD is essen- nance blocks because they are more significant tially the number of first m non-zero AC coef- than the chrominance blocks. ficients in the frame V. This information is un- 3 Two AC's can be dropped only when one becomes 0 2 Chiprate: In spread spectrum systems, this is the rate at and another, which must be the last non-zero AC which the discrete signal is applied. coefficient, is dropped. Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 96 known without the knowledge of the original gorithm and then always use this preprocessed ver- V. sion as the original". In doing so, the original in- 3.3 Verification Process formation which were changed by the preprocess- The verification process justifies the ownership ing will never be exposed. claim and consists of three steps: 4 Non-invertible Scheme for MPEG 1. The claimant is required to provide his/her Audio original video clip V, the key KEY, and his/her Audio data as well as other types of multimedia watermark W. Then the trusted third party veri- data are often stored and transmitted in compressed fies the creation of the watermark. If the wa- format, such as MPEG audio. The watermarking termark is confirmed, then Step 2 is applied. schemes should target the compressed data domain. Otherwise, the ownership is denied to the Notice that, although the watermarking schemes claimant. such as Boney's scheme [1] work well in uncom- 2. The trusted third party applies the watermark pressed data domain, extra decoding and re- embedding algorithm. Let the resulting water- encoding steps have to be taken if the audio data is marked video/image be V . Goto Step 3. already available in compressed format. Because 3. The trusted third party compares the resulting the Boney's scheme uses the MPEG psychoacoustic V with the published watermarked video model to mask the watermark, there would be no clip/image VW. If V and VW are similar, i.e. watermark presented in MPEG audio stream. C(V ; VW; ) = 1, then the ownership is Therefore, the study of watermarking in MPEG granted to the claimant, otherwise the owner- audio bit stream is interesting. ship is denied. In this section, we cover the watermarking proce- The watermarking process including the watermark dures for MPEG Layer II audio streams. However, construction and the watermark embedding proce- the presented methods are easily extended to other dure were proven to be non-invertible in [4]. layers of MPEG audio. 3.4 Discussion 4.1 Watermark Construction Note that the construction of the watermark plays First of all, in order to be immune against CMYY an essential role in our scheme to solve the rightful attack, the watermarking scheme has to be non- ownership problem. By using the encryption func- invertible. There are several different approaches to tion as a black-box", the watermark can not be ar- implement the non-invertibility. One of them is to bitrarily chosen by an attacker. Because of this, create the watermark by applying standard encryp- checking the watermark construction is needed tion algorithm such as DES to the original data as during the watermark verification process. we discussed it in Section 3 for MPEG Video. In the watermark construction and in the verifica- The watermark construction for MPEG audio has tion process we indicated, that without the original, the following steps: we can not verify if a watermark is a legitimate one. First, a key KEY is selected, and for each MPEG However, the original" does not have to be a true audio frame aj , j=1, ..., N (number of audio image or part of the video clip. For example, we frames), we apply DES with KEY to it to get a ran- can Xor the original frame with the first 100000 dom byte sequence RBS: digits of and use the result as the original". RBS = DESKEY (one audio frame aj) (9) We also notice that EPAD is actually redundant in Second, let RBSi be the i-th byte of the random byte the watermark creation process. We can simplify sequence and wi be the i-th bit of watermark bit the process and use the random sequence pl as the stream, then the watermark can be created by: watermark as long as pl is created by applying DES wi = -1 if RBSi = even number; 1 otherwise (10) (or other encryption functions) to V. The watermark bit sequence is applied repeatedly to Finally, there is a concern that watermark embed- the audio data of the same audio frame if the length ding algorithm may be subject to the multiple- of the watermark bit sequence (the number i) is less document attack: the AC coefficients which were than the number of samples in a frame. Normally, i dropped in one watermarked version may appear in is in a range from 100 to more than 1000, therefore, other versions which were created by applying dif- it is secure enough to use it repeatedly. In the case ferent keys; the AC coefficients which were modi- that i is larger than the number of samples in a fied in one watermarked version might be un- frame, the over-produced bits are ignored. touched in other versions. Therefore it is possible 4.2 Watermark Embedding Proce- for the attacker to guess the original value of the AC coefficients if there are enough versions avail- dures able. One way to solve this problem is to use a Notice that there are two major parts in data fields master key to preprocess the original video clip of an MPEG audio frame. One is the scale factors (image) by applying the proposed watermarking al- and the other is the encoded samples. Both of these Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 97 two parts can be used to embed the watermark. We However, changing of these encoded samples is describe the two procedures below. very sensitive. Tests show that, if we change every 4.2.1 Watermarking Scale Factors encoded sample by either adding 1 or -1, the distor- Scale factor is the multiplier that makes the samples tion of the resulting audio is easily detected by hu- to fully use the quantizer range. The decoder multi- man ear and the watermarked audio is not accept- plies the scale factor with decoded quantizer output able. to reconstruct the quantized subband samples. Each In order to solve this problem, we introduce a scale factor takes 6 bits, therefore, we have as many spacing parameter sp which has the following as 63 levels of scale factors (indexed from 0 to 62, meaning: in approximately every sp samples, we 63 is not used by the standard). The level changing randomly select 1 or 2 samples to watermark. By of scale factor has an auditory effect that the sound choosing a good spacing parameter, the distortion becomes stronger when the scalefactor level in- can be minimized. This conclusion is also sup- crease (index decrease) and becomes weaker when ported by our experimental tests (see next section). the scalefactor level decreases (index increase). The use of spacing parameter gives us a method to However, tests show that a small change of scale- adaptively watermark MPEG audio depending on factor level (for example, increases or decreases by different audio streams. 1) normally can not be detected by the people. Our The watermark creation procedure is slightly modi- first MPEG audio watermarking procedure is based fied to incorporate the spacing parameter: on this observation. The watermarking procedure is very simple and just adds the watermark bit wi to the index of the corre- W sponding scale factor with two exceptions: (1) if in- i ={-1 if RBSi = 0 (mod sp) 1 if RBSi = 1 (mod sp) 0 otherwise dex is 0 and wi = -1 then do nothing; (2) if index is 62 and wi = 1 than do nothing. Let SF The watermarking procedure is similar to the previ- i(index) be the i-th scale factor with the level indicated by index and SFW ous one except that we have to make sure that the i be the i-th water- marked one. The watermarking procedure can be watermarked sample does not have the format of described as: 111...1" because this kind of sample coding is ille- gal in MPEG audio standard. Let Si be the i-th sample in an audio frame and SWi SFi(index) if index+wi = -1 or 63; be the i-th watermarked sample. Let nbal SFW i be the i = {SFi(index+wi) otherwise number of bit allocation for i-th sample (the infor- This scheme has drawbacks. The first one is that, mation of bit allocation for each sample comes for some audio streams, there are only a few scale from the Bit Allocation field in an audio frame). factors for a frame, therefore, our frame-based wa- The watermarking procedure can be described as: termarking scheme does not have much data to watermark. One solution is to group frames to- gether and to apply the watermarking procedure at a SWi ={Si if every bit of (Si + wi) is 1; S group of frames. i + wi otherwise When the scale factor is increased by 1 level (index 4.2.3 Discussion decrease by 1) or decreased (by 1 or multiple lev- Both MPEG audio watermark schemes are simple els), there is no significant audio distortion. How- extensions of the concepts from spread spectrum ever, when the scale factor is increased by 2 levels communications. They are designed to apply wa- or more, there is often perceivable audio distortion termark in the compressed data domain so that the and the noise can be heard. This introduces a prob- expensive decoding/re-encoding can be avoided. lem that multiple watermarks can not be applied. Because the creation of watermark is based on ap- The reason is that when multiple watermarks are plying standard encryption function to the original applied, certain scale factors would be increased by audio data, the non-invertibility of these schemes multiple levels and perceivable noise would be in- can be easily proved. troduced. Another requirement is that the original MPEG This also creates another problem because an at- audio stream must be presented in the verification tacker can lower the scale factors dynamically by 2 process because, in general, the watermark schemes levels or 3 levels (increase the index by 2 or 3) and which do not use the originals in their verification destroy the watermarks. are invertible. (See also [4, 3]). 4.2.2 Watermarking Encoded Samples Finally, we want to point out that, because the hu- The other choice is to embed the watermark into the man ear is more sensitive to audio distortion than sample data. The basic idea is to add the watermark human eye to image distortion, the amount of data (-1/1 bit sequence) to encoded sample sequence. which can be embedded as watermark is very lim- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 98 ited and depends on the content of the audio lem into our consideration. By creating the water- streams which we showed experimentally [3]. For mark using a standard encryption function such as this reason, in the 2nd scheme, we introduced the DES, the non-invertibility property can be achieved spacing parameter which can be thought as an indi- and the unique ownership can be determined. cator to measure how much data can be embedded. By choosing a smaller spacing parameter, we could 6 References reach the upper limit which means that if we embed [1] L. Boney, A. H. Tewfik, and K. N. Hamdy. more data, the distortion will be noticeable. This Digital Watermarks for Audio Signals. In Pro- also means that multiple watermarks can not be ap- ceedings of 1996 IEEE International Confer- plied. ence on Multimedia Computing and Systems, pages 473{480, Hiroshima, Japan, June 1996. 5 Conclusion [2] S. Craver, N. Memon, B. Yeo, and M. Yeung. In this paper, we presented watermarking methods Can Invisible Watermarks Resolve Rightful which embed the watermark directly into the Ownerships? Technical Report RC 20509, MPEG video and audio bit streams. This is very IBM Research Division, July 1996. much desired if the video and audio streams are al- ready in MPEG encoded format. Otherwise, if we [3] L. Qiao and K. Nahrstedt. Non-invertible wa- use watermarking schemes designed for uncom- ter- marking methods for mpeg encoded audio. pressed video and audio, we have to go through the Tech- nical report, University of Illinois at Ur- expensive decoding-watermarking-encoding proc- bana- Champaign, Urbana, IL, June 1998. ess. [4] L. Qiao and K. Nahrstedt. Watermarking Our experimental tests show that the watermarking Method for MPEG Encoded Video: Towards methods minimize the visual and acoustic distortion Resolving Rightful Ownership. In IEEE Inter- and provide good video and audio quality for vari- national Con- ference on Multimedia Comput- ous types of MPEG encoded streams. Although we ing and Systems, Austin, TX, June 1998. use only watermarking on MPEG I frames and [5] R. B. Wolfgang and E. J. Delp. A Watermark- MPEG Audio Layer II streams in our experimental ing Technique for Digital Imagery: Further tests, the proposed schemes can be applied to other Stud- ies. In Proceedings of the International compressed/uncompressed images/videos and Conference on Imaging Science, Systems, and MPEG Audio Layer I streams and Layer III Technology, Las Vegas, Nevada, JULY 1997. streams. We also take the rightful ownership prob- Multimedia and Security Workshop at ACM Multimedia '98. Bristol, U.K., September 1998. 99 Copyright and Content Protection for Digital Images based on Asymmetric Cryptographic Techniques Alexander Herrigel S. Voloshynovskiy Digital Copyright Technologies State University "Lvivska polytechnika" Stauffacherstr. 149 Faculty of Radio Engineering Devices 8004 Zurich, Switzerland 290646 Lviv Fax: +41-1-923.81.31 S. Bandery Str. 12, Ukraine Email: herrigel@usa.net Email: svolos@polynet.lviv.ua ABSTRACT has recently developed new technologies, protocols, and i