Steganographic method and device

• US 5,613,004 A
• Filed: 06/07/1995
• Issued: 03/18/1997
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Wistaria Trading Inc.
• Original Assignee: The Dice Company
• Inventors: Cooperman, Marc, Moskowitz, Scott A.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/489,172
• Time in Patent Office: 650 Days
• Field of Search: 380/4, 380/25, 380/28
• 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 a message, represented as series of data bits into or out of a series of digitized samples, comprising:

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

b) a digital signal processor for performing spectral transforms;

c) a memory to contain information representing

1) primary mask,

2) convolutional mask,

3) start of message delimiter,

4) a mask calculation buffer,

5) a message buffer,

6) an integer representing a message bit index,

7) an integer M representing message size,

8) an integer representing an index into said primary mask,

9) an integer representing an index into said convolution mask,

10) an integer representing the state of a decode process,

11) a table representing a map function;

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

13) a positive integer S representing a number of samples to read into said sample buffer, and

14) a flag indicating the size of a message which has been decoded;

wherein at least one of the primary mask, the convolutional mask and the start of message delimiter are random or pseudo-random;

d) an input to acquire digital samples;

e) an output to output modified digital samples;

f) an input for inputting the values of (c1)-(c5) and (c11) and (c13);

g) an output to output the message stored in (c5) as the result of a decode process and the value of (c10) to an attached digital circuit;

h) at least one data bus to transfer information from

(d) to (a),

(a) to (b),

(b) to (a),

(a) to (e),

(f) to (c), and

(c) to (g); and

i) a clock which generates a clock signal to drive (b) and control the operation of the apparatus.

8. The apparatus of claim 1, further comprising a tamper-resistant packaging, enclosing said apparatus wherein circuitry and information stored therein are destroyed if said packaging is opened.

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

A) obtaining a mask set to be used for encoding, said set including;

a random or pseudo-random primary mask,

a random or pseudo-random convolution mask,

a random or pseudo-random start of message delimeter,

wherein said mask set are concatenated and manipulated as a single bit stream;

B) obtaining a message to be encoded;

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

1) a start of message delimiter,

2) an integer representing the number of message bytes to follow the message, and

3) the message;

D) loading the message bit stream, a map table, the primary mask, the convolution mask, and the start of message delimiter into a memory;

E) resetting a primary mask index, a convolution mask and message bit index, and setting the message size integer equal to the total number of bits in the message bit stream;

F) clearing a message encoded flag;

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

H) resetting the primary mask index and looping through the sample buffer from a first sample to a last sample incrementing the primary mask index each time a sample is visited, such that for each sample position, a value of the mapping function is computed, which is either true or false, by using a bit of the primary mask representing a current sample and a bit of the convolution mask indicated by the convolution index to calculate an offset in the map table;

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

J) outputting the modified samples in the sample buffer, and if the message encoded flag is set jumping back to said step E);

K) incrementing the convolution index, wherein if the convolution index equals the length of the convolution mask in bits then set the convolution index to 0; and

L) jumping back to step G).

3. The method of claim 2 wherein the samples are obtained from a sample stream representing digitized sound or music.

4. The method of claim 3 wherein the identical encode process is performed on two sample streams representing channel A and channel B of digitized stereo sound.

5. The method of claim 3 wherein the sample streams represent channel A and channel B of digitized stereo sound and are interleaved before being input as a single sample stream and are separated into two channels upon output.

6. The method of claim 2 wherein the samples are obtained from a sample stream representing a digitized video.

7. The method of claim 2 wherein the samples are obtained from a sample stream representing a digitized image.

9. The method of claim 2, further comprising a pre-encoding step which customizes the message to be encoded including:

calculating over which windows in the sample stream a message will be encoded, computing a secure one way hash function of the samples in those windows, and placing the resulting hash values in the message before the message is encoded;

wherein the hash calculating step includes;

calculating the size of the original message plus the size of an added hash value, and pre-processing the sample for the purpose of calculating hash values of each series of windows that will be used to encode the message and creating a modified copy of the message containing the hash value such that each message containing a hash value matches each window series uniquely.

10. The method of claim 2, wherein an authority for on line distribution of content encodes at least one of the following items into a sample stream;

the title,

the artist,

the copyright holder,

the body to which royalties should be paid, and

general terms for publisher distribution.

11. The method of claim 10, wherein the authority combines at least one item with a secure private key signed message from a publisher containing at least one of the following pieces of information:

the title,

the publisher'"'"'s identification,

the terms of distribution,

any consideration paid for the right to distribute the content,

a brief statement of agreement, and

the publisher signs and encrypts the combined message using a public key cryptosystem and encodes the signed and encrypted message into the sample stream.

12. The method of claim 11, wherein a publisher obtains the encoded sample stream and additionally obtains information form the authority and combines this with a message received from a consumer, which has been signed using a public key cryptosystem and wherein the signed message contains at least one of the following data

the content title,

consumer identification,

the terms of distribution,

the consideration paid for the content,

a brief statement of agreement, and

the publisher uses a public key cryptosystem to sign the combined information and finally encodes the signed information.

13. The method of claim 2, wherein the sample stream is obtained from at least one audio track contained within a digitized movie, video game software, or other software.

14. The method of claim 2, wherein the sample stream is obtained from at least one digitized movie or still image contained within a video game or other software.

15. The method of claim 2, wherein encoded information is contained in the differences or relationship between samples or groups of samples.

16. The method of claim 2, wherein the encoding of the message bit into the sample in step I includes altering the sample value such that said sample value falls within a prespecified range of valves relative to its original value.

17. The method of claim 2, wherein the map table is defined such that any index of the map table directs the process to encode information.

32. The method of claim 2 wherein the encoding of the message bit into the message in step I includes encoding a single bit of the sample to match the message bit.

44. The method of claim 2 wherein the encoding of the message bit into the sample in step I includes altering the sample value such that said sample value falls within a prescribed range of values relative to its original value.

18. A method of encoding information into a sample stream of data, comprising the steps of:

A) obtaining a mask set to be used for encoding, including;

a random or pseudo-random primary mask,

a random or pseudo-random convolution mask, and

a random or pseudo-random start of message delimiter,

wherein said mask set are concatenated and manipulated as a single bit stream;

B) inputting a message to be encoded;

C) generating a message bit stream to be encoded including a start of message delimiter,

an integer representing the number of message bytes to follow the message, and

the message;

D) loading the message bit stream, a map table, and the mask set into a memory;

E) resetting a primary mask index, a convolution mask and message bit index, setting the message size index equal to the number of bits in the message bitstream, and clearing a message encoded flag;

F) reading a window of samples of the inputted message and storing the samples sequentially in a sample buffer;

G) computing a spectral transform of the samples in the buffer;

H) resetting the primary mask index and looping through the sample buffer from a first spectral value to a last spectral value incrementing the primary mask index each time a spectral value is visited, such that for each spectral value position, a value of the mapping function is computed, which is either true or false, by using a bit of the primary mask representing a current spectral value and a bit of the convolution mask indicated by the convolution index to calculate an offset in the map table;

I) obtaining the bit value stored in the map table, wherein if the bit value is true, then encoding the bit of the message indicated by the message bit index into the current spectral value and incrementing the message bit index, if the message bit index equals the number of message bits, setting the message encoded flag, and exiting the loop;

J) computing the inverse spectral transform of the spectral values stored in the sample buffer;

K) outputting the values in the sample buffer, and if the message encoded flag is set, then clear the flag and jump back to step E);

L) incrementing the convolution index and when the convolution index equals the length of the convolution mask in bits resetting the convolution index; and

M) jumping back to step F).

19. The method of claim 18, wherein the encoding of the message bit into the sample in step H includes encoding a single bit of the sample to match the message bit.

20. The method of claim 18, further comprising a pre-encoding step which customizes the message to be encoded including:

calculating over which windows in the samples stream a message will be encoded, computing a secure one way hash function of the samples in those windows, and placing the resulting hash values in the message before the message is encoded;

wherein the hash calculating step includes;

calculating the size of the original message plus the size of an added hash value, and pre-processing the sample stream for the purpose of calculating hash values of each series of windows that will be used to encode the message and creating a modified copy of the message containing the hash value such that each message containing a hash value matches each window series uniquely.

21. The method of claim 18 wherein the samples are obtained from a sample stream representing digitized sound or music.

22. The method of claim 21 wherein the identical encode process if performed on two sample streams representing channel A and channel B of digitized stereo sound.

23. The method of claim 21 wherein the sample streams represent channel A and channel B of digitized stereo sound and are interleaved before being input as a single sample stream and are separated into two channel upon output.

24. The method of claim 18 wherein the samples are obtained from a sample stream representing digitized video.

25. The method of claim 18 wherein the samples are obtained from a sample stream representing a digitized image.

26. The method of claim 18, wherein an authority for on line distribution of content encodes at least one of the following items into a sample stream:

the title,

the artist,

the copyright holder,

the body to which royalties should be paid, and

general terms for publisher distribution.

27. The method of claim 26, wherein the authority combines at least one item with a secure private key signed message from a publisher containing at least one of the following pieces of information:

the title,

the publisher'"'"'s identification,

the terms of distribution,

any consideration paid for the right to distribute the content,

a brief statement of agreement, and

the publisher signs and encrypts the combined message using a public key cryptosystem and encodes the signed and encrypted message into the sample stream.

28. The method of claim 27, wherein a publisher obtains the encoded sample stream and additionally obtains information from the authority and combines this with a message received from a consumer, which has been signed using a public key cryptosystem and wherein the signed message contains at least one of the following data

the content title,

consumer identification,

the terms of distribution,

the consideration paid for the content,

a brief statement of agreement, and

the publisher uses a public key cryptosystem to sign the combined information and finally encodes the signed information.

29. The method of claim 18, wherein the sample stream is obtained from at least one audio track contained within a digitized movie, video game software, or other software.

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

31. The method of claim 18, wherein encoded information is contained in the differences or relationship between samples or groups of samples.

33. The method of claim 18 wherein the encoding of the message bit into the spectral values in step I includes altering the spectral values such that said spectral values fall within a prescribed range of values relative to an original value.

38. The method of claim 18 wherein the map table is defined such that any index of the map table directs the process to encode information.

43. The method of claim 18 wherein the encoding of the message bit into the spectral values in step I includes encoding a single bit of the spectral values to match the message bit.

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

A) obtaining a mask set including;

(1) a random or pseudo-random primary mask,

(2) a random or pseudo-random convolution mask, and

(3) a random or pseudo-random start of message delimiter;

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

C) resetting a primary mask index and convolution mask index and setting a message size integer equal to 0;

D) clearing a message decoded flag;

E) setting a state of the decode process to SYNCHRONIZED;

F) checking the state of the decode process and if the decode state is UNSYNCHRONIZED, setting a number of samples to equal 1 and resetting the convolution index to 0;

otherwise, setting the number of samples to equal S (S≧

1);

G) reading the number of samples specified in step F) into a sample buffer;

H) resetting the primary mask index, and looping through the sample buffer from the first sample to the last sample, incrementing the primary mask index each time, and for each sample position, computing the value of a mapping function to calculate an offset into the map table;

I) obtaining the bit value in the map table, and if the value is true, decoding the bit of the message indicated by the message bit index, storing the bit into the message buffer at the message bit index, and incrementing the message bit index;

J) comparing the 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 bits match, then setting the state of the decode process to SYNCHRONIZED;

otherwise setting the state of the decode process to UNSYNCHRONIZED;

K) if the state of the decode process is SYNCHRONIZED and the number of bits in the message buffer is greater than or equal to the sum of the number of bits of the start of delimiter and the message size, then setting the state of the decode process to SYNC-AND-SIZE and copying certain bits from the message buffer to a message size integer container;

L) if the state of the decode process is SYNC-AND-SIZE and the number of bytes in the message buffer divided by 8 is greater than or equal to the message bit size, then setting the message decoded flag, outputting the message and the message decoded flag and ending the method;

M) incrementing the convolution index, and if the convolution index equals the number of bits in the convolution mask resetting the convolution index; and

N) jumping to step F).

36. The method of claim 34 wherein the decoding of the message bit from the sample in step I includes reading a single bit of the sample.

37. The method of claim 34 wherein the decoding of the message bit from the sample in step I includes mapping a range of sample values onto a particular message bit value.

41. The method of claim 34, wherein the map table is defined such that any index of the map table directs the process to encode information.

35. A method of decoding information from sampled data, comprising the steps of:

A) Obtaining a mask set including

(1) a random or pseudo-random primary mask,

(2) a random or pseudo-random convolution mask, and

(3) a random or pseudo-random start of message delimiter;

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

C) resetting a primary mask index and convolution mask index and setting a message size integer equal to 0;

D) clearing a message decoded flag;

E) setting a state of the decode process to SYNCHRONIZED;

F) checking the state of the decode process and if the decode state is UNSYNCHRONIZED, setting a number of samples to equal 1 and resetting the convolution index to 0;

otherwise, setting the number of samples to equal S (S>

1);

G) reading the number of samples specified in step F) into a sample buffer;

H) computing a spectral transform of the samples stored in the sample buffer;

I) resetting the primary mask index and looping through said transform samples from the first sample to the last sample, incrementing the primary mask index each time, and for each sample position, computing the value of a mapping function by using the bit of the primary masks corresponding to the primary mask index and the bit of the convolution masks indicated by the convolution phase to calculate an offset into the map table representing the mapping function;

J) obtaining a bit value stored in the map, and if the value is true, decoding the bit of the message indicated by the message bit index from the current transform message, storing the bit into the message buffer at the message bit index, and incrementing the message bit index;

K) comparing the 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 bits match, then setting the state of the decode process to SYNCHRONIZED;

otherwise, setting the state of the decode process UNSYNCHRONIZED;

L) if the state of the decode process is SYNCHRONIZED, and the number of bits in the message buffer is greater than or equal to the sum of the number of bits of the start of delimiter and the message size, then setting the state of the decode process to SYNC-AND-SIZE and copying certain bits from the message buffer to a message size integer container;

M) if the state of the decode process is SYNC-AND-SIZE and the number of bits in the message buffer divided by 8 is greater than or equal to the message bit size, then setting the message decoded flag, outputting the message and the message decoded flag and ending the method;

N) incrementing the convolution index, wherein if the convolution index equals the number of bits in the convolution mask, then resetting the convolution index; and

O) jumping to step F).

39. The method of claim 35, wherein the decoding of the message bit in step J includes reading a single bit of the sample.

40. The method of claim 35, wherein the decoding of the message bit in step J includes mapping a range of supply values onto a particular message bit value.

42. The method of claim 35, wherein the map table is defined such that any index of the map table directs the process to encode information.