Steganographic method and device

• US 5,687,236 A
• Filed: 12/31/1996
• Issued: 11/11/1997
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Wistaria Trading Inc.
• Original Assignee: The Dice Company
• Inventors: Moskowitz, Scott A., Cooperman, Marc
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/775,216
• Time in Patent Office: 315 Days
• Field of Search: 380/4, 380/5, 380/28, 380/54
• US Class Current: 380/28
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 2201/0064 for copy protection or copy management, e.g. CGMS, copy only once, one-time copy
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: G11B 20/00891 embedded in audio data
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/605 Copy protection
• CPC Class Codes: H04L 2209/608 Watermarking
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations
• CPC Class Codes: H04N 1/3216 using Fourier transforms
• CPC Class Codes: H04N 1/32187 with selective or adaptive application of the additional information, e.g. in selected frequency coefficients
• CPC Class Codes: H04N 1/32245 Random or pseudorandom selection of pixels
• CPC Class Codes: H04N 21/23614 Multiplexing of additional data and video streams arrangements for simultaneous broadcast of plural pieces of information H04H20/28
• CPC Class Codes: H04N 21/23892 involving embedding information at multiplex stream level, e.g. embedding a watermark at packet level
• CPC Class Codes: H04N 21/2541 Rights Management protecting software against unauthorised usage in a vending or licensing environment G06F21/10; security in data switching network management H04L41/28; security management or policies for network security H04L63/20; access security in wireless networks H04W12/08
• CPC Class Codes: H04N 21/4348 : Demultiplexing of additional data and video streams
• CPC Class Codes: H04N 21/835 : Generation of protective data, e.g. certificates protecting software against unauthorised usage in a vending or licensing environment G06F21/10
• CPC Class Codes: H04N 21/8352 : involving content or source identification data, e.g. Unique Material Identifier [UMID]
• CPC Class Codes: H04N 21/8358 : involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467
• CPC Class Codes: H04N 2201/3205 : of identification information, e.g. name or ID code H04N2201/3209 takes precedence
• CPC Class Codes: H04N 2201/3226 : of identification information or the like, e.g. ID code, index, title, part of an image, reduced-size image
• CPC Class Codes: H04N 2201/3233 : of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 : which are undetectable to the naked eye, e.g. embedded codes
• CPC Class Codes: H04N 2201/3281 : Encryption; Ciphering
• CPC Class Codes: H04N 7/1675 : Providing digital key or authorisation information for generation or regeneration of the scrambling sequence pseudo-random number generators in general G06F7/58

Abstract

An apparatus and method for encoding and decoding additional information into a stream of digitized samples in an integral manner. The information is encoded using special keys. The information is contained in the samples, not prepended or appended to the sample stream. The method makes it extremely difficult to find the information in the samples if the proper keys are not possessed by the decoder. The method does not cause a significant degradation to the sample stream. The method is used to establish ownership of copyrighted digital multimedia content and provide a disincentive to piracy of such material.

Claims

1. An apparatus for encoding or decoding independent information, including a digital watermark, represented as a series of data bits into or out of a series of digitized samples, comprising:

a) a sample buffer for holding, accessing and transforming digitized samples;

b) a digital signal processor for performing sample modifications and spectral transformations;

c) a memory for storing information representing;

1) a mask set, including one or more masks,

2) a start of message delimiter,

3) a mask calculation buffer,

4) a first buffer holding the independent information,

5) an information bit index,

6) a message size, representing an amount of information,

7) one index into each of said one or more masks,

8) a state of a decoding process,

9) a table representing a map function,

10) a flag indicating whether a complete message has been decoded or encoded,

11) a number of samples for reading into said sample buffer, and

12) a flag indicating a size of a message that has been decoded, wherein at least one of said one or more masks, or the start of message delimiter are random or pseudo-random;

d) a first input for acquiring a plurality of digital samples;

e) a first output for outputting a plurality of modified digital samples;

f) a second input for inputting a plurality of values to the one or more masks, the start of message delimiter, the mask calculation buffer, the first buffer, the table and the number of samples;

g) a third output for outputting the independent information stored in the first buffer as a result of the decoding process and a value of the state of the decoding process to an attached digital circuit;

h) at least one data bus for transferring information from;

1) the first input to the sample buffer,

2) the sample buffer to the digital signal processor,

3) the digital signal processor to the sample buffer,

4) the sample buffer to the first output,

5) the second input to the memory, and

6) the memory to the third output; and

l) a clock for generating a clock signal for driving the digital signal processor and the at least one data bus, and for controlling the operation of the apparatus.

2. A method for encoding independent information into a sample stream of data, said method comprising the steps of:

a) selecting a mask set, said mask set including one or more random or pseudo-random series of bits, referred to as masks;

b) selecting a random or pseudo-random start of message delimiter;

c) selecting independent information to be encoded;

d) generating a message bit stream to be encoded such that the stream includes;

1) the random or pseudo random start of message delimiter,

2) a number of message bytes that follow a message, and

3) the independent information;

e) loading the message bit stream, a map table, the mask set, and the random or pseudo-random start of message delimiter into a memory;

f) resetting all mask indices and a message bit index, and setting a message size equal to a total number of bits in the message bit stream;

g) clearing a message encoded flag;

h) reading a window of samples from a sample input device and storing them in a sample buffer;

I) resetting at least a first mask index and looping through the sample buffer from a first sample to a last sample and setting at least a second mask index as a function of sample position each time a sample is visited, such that for each sample position, a value of a mapping function is computed, which is either true or false, by using one or more bits of the mask set to calculate an offset in the map table;

j) obtaining a bit value stored in the map table and encoding a bit of the message indicated by a message bit index into a current sample if a bit value obtained from the map table is a predetermined value and incrementing the message bit index, determining whether the message bit index equals the number of message bits, and if so, setting the message encoded flag, and exiting the loop;

k) outputting a plurality of modified samples in the sample buffer, and if the message encoded flag is set jumping back to step f);

l) incrementing one or more mask indices, distinct from the first and second mask indices in step I), wherein if a third mask index of said one or more mask indices equals a length in bits of a third mask corresponding to said third mask index then resetting said third mask index; and

m) jumping back to step h).

9. The method according to claim 2, wherein the samples are obtained from a sample stream representing digitized audio.

10. The method according to claim 9, further comprising the steps of:

n) interleaving two sample stream representing channel A and channel B of digitized stereo sound before being input as a single sample stream; and

o) separating the single sample stream into two channels upon output.

11. The method according to claim 2, wherein the samples are obtained from a sample stream representing digitized video.

12. The method according to claim 2, wherein the samples are obtained from a sample stream representing a digitized image.

13. The method according to claim 2, further comprising the step of:

n) pre-encoding, which customizes the message to be encoded, said pre-encoding step including;

(1) calculating over which windows in the sample stream a message will be encoded,

(2) computing a secure one way hash function of the samples in those windows, and

(3) placing a plurality of hash values resulting from the step (2) of computing in the message before the message is encoded;

wherein the step (2) of computing further comprises;

(I) calculating a size of the original message plus a size of an added hash value,

(ii) pre-processing the sample stream to calculates hash values of each series of windows that will be used to encode the message, and

(iii) creating a modified copy of the message containing the added hash value such that each message containing a hash value matches each window series uniquely, wherein the hash function is insensitive to changes introduced by the watermark process.

14. The method according to claim 2, further comprising the step of:

n) encoding by an authority for on line distribution of content into a sample stream at least one selected from the group consisting of a title, an artist, a copyright holder, a body to which royalties should be paid, and general terms for publisher distribution.

15. The method according to claim 14, further comprising the step of:

o) combining by the authority at least one item with a digitally signed message from a publisher containing at least one selected from the group consisting of;

the title, a publisher'"'"'s identification, terms of distribution, any consideration paid for a right to distribute the content, a brief statement of agreement.

p) signing and encrypting by the publisher the combined message using digital signature and crypto systems; and

q) encoding by the publisher the digitally signed and encrypted message into the sample stream.

16. The method according to claim 15, further comprising the steps of:

r) obtaining by a publisher the encoded sample stream and obtaining additional information from the authority;

s) combining the additional information with the encoded sample stream with a message received from a consumer, which has been digitally signed using a digital signature system, wherein the signed message contains at least one selected from the group consisting of the content, title, consumer identification, the terms of distribution, the consideration paid for the content, a brief statement of agreement;

t) using by the publisher a digital signature system to digitally sign the combined information; and

u) finally encoding the signed information.

3. A method for encoding independent information into a sample stream of data, said method comprising the steps of:

a) selecting a mask set, said mask set including one or more random or pseudo-random series of bits, referred to as masks;

b) selecting a random or pseudo-random start of message delimiter;

c) selecting independent information to be encoded;

d) generating a message bit stream to be encoded such that the stream includes;

1) the random or pseudo-random start of message delimiter,

2) the number of message bytes that following the message, and

3) the independent information;

e) loading the message bit stream, a map table, the mask set, and the random or pseudo-random start of message delimiter into a memory;

f) resetting all mask indices and a message bit index, and setting a message size equal to a total number of bits in the message bit stream;

g) clearing a message encoded flag;

h) reading a window of samples from a sample input device and storing them in a sample buffer;

I) computing a spectral transform of the samples in the sample buffer and storing a plurality of spectral values resulting from the spectral transform in the sample bffer,

j) resetting at least a first mask index and looping through the sample buffer from a first spectral value to a last spectral value and setting at least a second mask index as a function of a sample buffer position each time a spectral value is visited, such that for each spectral value position, a value of a mapping function is computed, which is either true or false, by using one or more bits of the mask set to calculate an offset in the map table;

k) obtaining a bit value stored in the map table and encoding a bit of the message indicated by a message bit index into a current spectral value if the bit value obtained from the map take is a predetermined value and incrementing the message bit index, determining whether the message bit index equals a number of message bits, and if so, setting the message encoded flag, and exiting the loop;

l) computing an inverse spectral transform of the plurality of spectral values stored in the sample buffer and storing a plurality of modified samples resulting from the inverse spectral transform in the sample buffer.

m) outputting the plurality of modified samples in the sample buffer, and if the message encoded flag is set jumping back to step f);

n) incrementing one or more mask indices, distinct from the first and second mask indices in step j), wherein if a third mask index equals a length in bits of a third mask corresponding to the third mask index then resetting the third mask index; and

o) jumping back to step h).

4. The method according to claim 3, further comprising the step of:

b) encoding a single of bit of the independent information, including a single bit of the digital watermark, into a single sample by replacing a single bit of the single sample with the single bit of independent information.

5. The method according to claim 3, further comprising the step of:

b) encoding a single of bit of the independent information, including a single bit of the digital watermark, into a single spectral value by altering the single spectral value such that said single spectral value falls within a predetermined range of values relative to its original value.

6. The method according to claim 3, further comprising the step of:

b) encoding a single of bit of the independent information, including a single bit of the digital watermark, into a single sample by altering the single sample such that said single sample falls within a predetermined range of values relative to its original value.

7. A method for decoding information from a sample stream of data, comprising the steps of:

a) selecting a mask set, said set including one or more random or pseudo-random series of bits, referred to as masks;

b) selecting a random or pseudo-random start of message delimiter;

c) loading a map table, and the mask set into a memory;

d) resetting a plurality of mask indices and setting a message size variable to 0;

e) clearing a message decoded flag;

f) setting a state of the decoding process to SYNCHRONIZED;

g) checking the state of the decoding process and if the state of the decoding process is UNSYNCHRONIZED, setting a number of samples to equal one and resetting a first mask index of the plurality of mask indices, otherwise, setting the number of samples to equal S, where S is greater than or equal to one;

h) reading the number of samples specified in step g) into a sample buffer;

I) resetting a second mask index of the plurality of mask indices distinct from the first mask index, and looping through the sample buffer from a first sample to a last sample, setting at least one mask index of the plurality of mask indices as a function of a sample position, and for each sample position, computing a value of a mapping function using a plurality of mask bits indicated by the plurality of mask indices to calculate an offset into the map table;

j) obtaining a bit value in the map table, and if it is a predetermined value, decoding a bit of the message indicated by a message bit index, from a current sample, storing each bit that is decoded into a message buffer at the message bits index, and incrementing the message bit index;

k) comparing a plurality of decoded bits in the message buffer to the start of message delimiter, and if a number of the plurality of decoded bits in the message buffer is less than or equal to a number of bits in the random or pseudo-random start of message delimiter and the plurality of decoded bits match the random or pseudo-random start of message delimiter, then setting the state of the decoding process to SYNCHRONIZED, otherwise setting the state of the decoding process to UNSYNCHRONIZED;

I) if the state of the decoding process is SYNCHRONIZED and the number of the plurality of decoded bits in the message buffer is greater than or equal to a sum of the number of bits of the random or pseudo-random start of message delimiter and the message size, then setting the state of the decoding process to SYNC-AND-SIZE and copying a plurality of predetermined bits from the message buffer to a message size integer container;

m) if the state of the decoding process is SYNC-AND-SIZE and the number of the plurality of decoded bits in the message buffer is greater than or equal to the message size in bits, then setting the message decoded flag, outputting the plurality of decoded bits as the message and the message decoded flag and ending the method;

n) incrementing at least one mask index, and if a third mask index equals the number of bits in a third mask corresponding to the third mask index, resetting the third mask index; and

o) jumping to step g).

17. The method according to claim 7, wherein the sample stream is obtained from at least one audio track contained within a digitized move, video game software, or other software.

18. The method according to claim 7, wherein the sample stream is obtained from at least one digitized movie or still image contained within a video game or other software.

19. The method according to claim 7, wherein encoded information is contained in the differences or relationship between samples or groups of samples.

20. The method according to claim 7, wherein an identical encoding process is performed on two sample streams representing channel A and channel B of digitized stereo sound.

8. A method for decoding information from a sample stream of data, comprising the steps of:

a) selecting a mask set, said mask set including one or more random or pseudo-random series of bits, referred to as masks;

b) selecting a random or pseudo-random start of message delimiter;

c) loading a map table, and the mask set into a memory;

d) resetting a plurality of mask indices and setting a message size variable to 0;

e) clearing a message decoded flag;

f) setting a state of the decoding process to SYNCHRONIZED;

g) checking a state of the decoding process and if the state of the decoding process is UNSYNCHRONIZED, setting a number of samples to equal one and resetting at least a first mask index of the plurality of mask indices, otherwise, setting the number of samples to equal S, where S is greater than or equal to one;

h) reading the number of samples specified in step g) into a sample buffer;

I) computing a spectral transform of the samples stored in the sample buffer, and storing a plurality of spectral values resulting from the spectral transform in the sample buffer;

j) resetting at least a second mask index of the plurality of mask indices distinct from the first mask index of step g), and looping through the sample buffer from a first spectral value to a last spectral value, setting at least a third mask index of the plurality of mask indices as a function of a sample buffer position, and for each sample buffer position, computing a value of a mapping function using a plurality of mask bits indicated by the plurality of mask indices to calculate an offset into the map table;

k) obtaining a bit value in the map table, and if it is a predetermined value, decoding a bit of the message indicated by a message bit index, from a current spectral value, storing each bit decoded into the message buffer at the message bit index, and incrementing the message bit index;

l) comparing a plurality of decoded bits in the message buffer to the start of message delimiter, and if the number of bits in the message buffer is less than or equal to the number of bits in the start of message delimiter and the message bits match the random or pseudo-random start of message delimiter, then setting the state of the decoding process to SYNCHRONIZED, otherwise setting the state of the decoding process to UNSYNCHRONIZED;

m) if the state of the decoding process is SYNCHRONIZED and a number of bits in the message buffer is grater than or equal to a sum of a number of bits of the random or pseudo-random start of message delimiter and the message size, then setting the state of the decoding process to SYNC-AND-SIZE and copying a plurality of predetermined bits from the message buffer to a message size integer container;

n) if the state of the decoding process is SYNC-AND-SIZE and the number of bits in the message buffer is greater than or equal to the message size in bits, then setting the message decoded flag, outputting the plurality of decoded bits as the message and the message decoded flag and ending the method;

o) incrementing at least one mask index, and if the at least one index equals a number of bits in a mask corresponding to the at least one mask index resetting the at least one mask index; and

p) jumping to step g).

21. The method according to claim 8, wherein the sample stream is obtained from at least one audio track contained within a digitized movie, video game software, or other software.

22. The method according to claim 8, wherein the sample stream is obtained from at least one digitized movie or still image contained within a video game or other software.

23. The method according to claim 8, wherein encoded information is contained in the differences or relationship between samples or groups of samples.