I recently came across a real-world use of steganography which hides extra data in the LSB of CD audio tracks to allow (according to the vendor) the equivalent of 20-bit samples instead of 16-bit and assorted other features. According to the vendors, "HDCD has been used in the recording of more than 5,000 CD titles, which include more than 250 Billboard Top 200 recordings and more than 175 GRAMMY nominations", so it's already fairly widely deployed.

From http://www.hdcd.com/partners/proaudio/overview.html:

[...] Hidden Code Addition/Output Dither/Quantization The final step in the reduction to 16 bits is to add high-frequency weighted dither and round the signal to 16-bit precision. The dither increases in amplitude in the frequency range of 16 to 22.05 kHz, leaving the noise floor flat below 16 kHz where the critical bands of hearing associated with tonality occur. As part of the final quantization, a pseudo-random noise hidden code is inserted as needed into the least significant bit (LSB) of the audio data. The hidden code carries the decimation filter selection and Peak Extend and Low Level Range Extend parameters. Inserted only 2?5 percent of the time, the hidden code is completely inaudible-effectively producing full 16-bit undecoded playback resolution. The result is an industry-standard 44.1-kHz, 16-bit recording compatible with all CD replication equipment and consumer CD players. [...] The paper describing the process is available under the somewhat misleading name http://www.hdcd.com/partners/proaudio/AES_Paper.pdf. The description of the stego en/decoding process is on p.15 (it's a rather long excerpt, but it's interesting stuff): As part of the final quantization, a hidden code side channel is inserted into the LSB when it is necessary for the encoder to inform the decoder of any change in the encoding algorithm. It takes the form of a pseudo-random noise encoded bit stream which occupies the least significant bit temporarily, leaving the full 16 bits for the program material most of the time. Normally, the LSB is used for the command function less than five percent of the time, typically only one to two percent for most music. Because the hidden code is present for a small fraction of the time and because it is used as dither for the remaining 15 bits when it is inserted, it is inaudible. This was confirmed experimentally with insertion at several times the normal fraction of time. [...] The mechanism which allows insertion of commands only when needed consists of encapsulating the command word and parameter data in a "packet". A synchronizing pattern is prepended to the data and a checksum is appended. The resulting packet is then scrambled using a feedback shift register with a maximal length sequence and inserted serially, one bit per sample, into the LSB of the audio data. The decoder sends the LSB's of the audio data to a complementary shift register to unscramble the command data. A pattern matching circuit looks for the synchronizing pattern in the output of the descrambler, and when it finds it, it attempts to recover a command. If the command has a legal format and the checksum matches, it is registered as a valid packet for that channel. The arrival of a valid packet for a channel resets a code detect timer for that channel. If both channels have active timers, then code is deemed to be present and the filter select data is considered valid immediately. However, any command data which would effect the level of the signal must match between the two channels in order to take effect. The primary reason for this is to handle the case where an error on one channel destroys the code. In such a case, the decoder will mistrack for a short time until the next command comes along, which is much less audible than a change in gain on only one channel, causing a shift in balance and lateral image movement. If either of the code detect timers times out, then code is deemed not to be present, and all commands are canceled, returning the decode system to its default state. If the conditions on the encoder side are not changing, then command packets are inserted on a regular basis to keep the code detect timers in the decoder active and to update the decoder if one starts playing a selection in the middle of a continuous recording. Since the decoder is constantly scanning the output of the de-scrambler shift register for valid command packets even when none are present, the possibility exists that there may be a false trigger. For audio generated by the encoder, this possibility is eliminated in the absence of storage and transmission errors by having the encoder scan the LSB of the audio data looking for a match. If a match to the synchronizing pattern is found, the encoder inverts one LSB to destroy it. Modern digital storage and transmission media incorporate fairly sophisticated error detection and correction systems. Therefore, we felt that only moderate precautions were necessary in this system. The most likely result of an error in the signal is a missed command, which can result in a temporary mis- tracking of the decoding, as mentioned above. Given the low density of command data, and the small changes to the signal which the process uses, these errors are seldom more audible than the error would be in the absence of the process. The chances of a storage error being falsely interpreted as a command are extremely small. For material not recorded using the encoder, a small probability for a false trigger does exist. Given a moderate length for the scrambling shift register so that its mapping behaves in a noise-like fashion and a choice of synchronizing pattern which avoids patterns likely to appear in audio data with a higher than average probability, susceptibility to false triggers can be made arbitrarily small by increasing the length of the part of the packet requiring a match. In the case of the current system, the combination of the synchronizing pattern with the bit equivalence for all valid commands plus check sum results in a required match equivalent to 39 sequential bits. For a stereo signal, in which a match must occur in both channels within a one second interval and the commands in both channels must specify the same gains, this amounts to an expectation of one event in approximately 150 million years of audio. The scrambling operation uses a feedback shift register designed for a maximal length sequence in which data taken from taps in the register are added using modulo two arithmetic, equivalent to an 'exclusive or' operation, and fed back to the input of the register. For a given register length there are certain configurations of taps which will produce a sequence of one and zero values at the output that does not repeat until 2N-1 values have emerged, where N is the length of the shift register. This corresponds to the number of possible states of the shift register minus one illegal state, and is called a maximal length sequence. Such an output sequence has very noise-like properties and, in fact, is the basis of some noise generators. We use the noise-like behavior of the generator to scramble the command signals by adding them modulo two to the input of the shift register, as for example in Figure 7a. This has the advantage that a second similar shift register with taps in the same places but with only feed forward addition modulo two (Figure 7b) will reproduce the original input sequence when fed with the output of the first one. The fact that the decode side has no feedback means that the initialization requirements are limited to having N input samples prior to the beginning of decoding, which means that the decoder will "lock up" very quickly. In this scheme, the presence of a bit error anywhere in the length of a packet plus initialization sequence will completely scramble the data, preventing recovery. However, in practice, this has not been a problem for reasons described above. Peter. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com