An Implementation of Key-Based Digital Signal Steganography

Author: Toby Sharp

Information Hiding Workshop 2001
Pittsburgh, PA, USA, April 25–27, 2001

Spring LNCS 2137, pp. 13-26, 2001

Abstract
A real-life requirement motivated this case study of secure covert communication. An independently researched process is described in detail with an emphasis on implementation issues regarding digital images. A scheme using stego keys to create pseudorandom sample sequences is developed. Issues relating to using digital signals for steganography are explored. The terms modified remainder and unmodified remainder are defined. Possible attacks are considered in detail from passive wardens and methods of defeating such attacks are suggested. Software implementing the new ideas is introduced, which has been successfully developed, deployed and used for several years without detection.

在談論這篇論文所使用的嵌入技術之前, 必須要先弄清楚 Pseudo-Random Sequence Generator 的運作方式。作者運用一個 Linear Feedback Shift Register (LFSR) 及使用傳訊者(sender) 和接收者(receiver) 所共同擁有的 stego-key 來建立與初始化這個 LFSR, 產生一連串的擬隨機序列。

使用 LFSR 所產生的擬隨機序列, 就可以決定要將訊息嵌入到 cover signal 的哪些 samples 之中, 作者稱造訪次序(visiting order) 為 sample sequence。假設 cover signal 一共有 P 個 samples, 令 t = log2(P), 因此我們就可以用 LFSR 所產生的 t 個位元來代表一個數字 k , 所以, 下一個要造訪的就是第 k 個 sample。作者在論文中還提到: 如果已經嵌入 x 位元, 剩下 (P-x) samples, 因此只要使用 t' = log2(P-x) 個擬隨機位元就可以決定下一個要造訪的 sample 了。

由上面的討論我們知道 sample sequence 是和 stego-key 值相關的, stego-key 不同, 所造訪的次序就不相同。除了和 stego-key 相關, 為了讓 sample sequence 也與 cover signal 及 embedded data相關, 作者還將所造訪的 sample value 的 Most significant Bit (MSB) 及 Least Significant Bit (LSB) 分別取出, 做為下一個擬隨機次序的前兩個位元。 而 MSB 所代表的就是 sample value, LSB 所代表的就是 embedded data。

這篇論文最重要的核心嵌入技術描述在 p. 15 的最後一段:

When a sample is visited, its data value is modified so that its least significant bit (LSB) is equal to the next bit of the secret data. The LSBs are not simply replaced; instead the whole sample value is incremented or decremented if the LSBs differ. This avoids the "pairs of values" statistical attack introduced in [9]. At each sample, one operation bit is taken from the generator and, if required, is used to determine whether to increment or decrement the sample value.

很可惜地, 論文中提到的隱藏工具 Hide, 網路上已經找不到下載點了。A. Westfeld 在 IHW 2002 年所提出的論文 "Detecting Low Embedding Rates" 中有一張執行的初始畫面(Fig. 6),

　
在本篇論文的 Fig.4 則是展示使用者介面。　
　
　

關於 Jsteg 的點點滴滴 (六) : A. Westfeld

Andreas Westfeld & Andreas Phitzmann 在 IHW99 的論文 "Attacks on Steganographic System" 中, 曾經三次提到 Jsteg:

1. 在 P.3 提到 Tinsley 的年度報告中有介紹一種關於 Jsteg 的攻擊方法。其實, Tinsley 另外還提出 j1, j2 兩個新嵌入法。

Related to this work is Final Year Project of Tinsley on Steganography and JPEG Compression. He describes statistical attacks applied to Jsteg using a different statistical model.

2. P.8 說明為什麼提出來的 Visual Attack 無法運用在破解 Jsteg。

Jsteg - embedding in a transformed domain. Jsteg embeds in JPEG images. In JPEG images, the image content is transformed into frequency coefficients to achieve storage as compact as possible. There is no visual attack in the sense presented here, because one steganographic bit influences up to 256 pixels.

3. P.12 最後, 運用作者所提出來的 Chi-Square Attack, 就可以成功破解 Jsteg。

Jsteg - embedding in a transformed domain. As already noted in Sect. 3, visual attacks do not work concerning Jsteg. Since Jsteg (as EzStego) embeds bits continuously, we use the former presentation of Fig. 16 in Fig 17, Fig. 18 and Fig. 19. The show that our statistical test is quite effective concerning Jsteg as well.

Andreas Westfeld 在 IHW01 的論文 "F5 - A Steganographic Algorithm High Capacity Despite Better Steganalysis" , 也有一整個章節在介紹 Jsteg, Figure 4 甚至將 C 的程式碼給貼出來, 最後, Westfeld 還自己在 IHW99 提出來 Chi-Square Attack 來說明 Jsteg 是不夠安全的。對了, 值得一提的是在判斷 DCT 係數不等於 0 或 1 的方法, Westfeld 的 C 程式是這樣寫的 if ((inval & 1) != inval), inval 就是 DCT 係數, ( inval & 1 ) 是用 bitwise operator & 將 LSB 前面的 bits 通通設為 0 了, 如果這樣做之後, inval 的值仍然沒有改變, 表示一定等於 0 或 1。一般簡單又明瞭的寫法是 if (( inval !=0)||(inval!=1)), 大家可以比較參考一下。

This algorithm made by Derek Upham serves as a starting point for the contemplation here, because it is resistant against the visual attacks presented in [5], and nevertheless offers an admirable capacity for steganographic messages (e. g., 12.8 % of the steganogram’s size). After quantisation, Jsteg replaces the least significant bits (LSB) of the frequency coefficients by the secret message. The embedding mechanism skips all coefficients with the values 0 or 1. Fig. 4 shows Derek Upham’s embedding function of Jsteg in C source code.

However, the statistical attack [5] on Jsteg reliably discovers the existence of embedded messages, because Jsteg replaces bits and, thus, it introduces a dependency between the value’s frequency of occurrence, that only differ in this bit position (here: LSB). Jsteg influences pairs of the coefficient’s frequency of occurrence, as Fig. 5 shows.