Defending Against Statistical Steganalysis (part 2)

本篇文章延續 part 1 的討論, 將焦點鎖定在 Section 6 Correcting Statistical Deviations, 探討 OutGuess 0.2 是如何做到將掩護影像(cover-images) 的直方圖特性保留在偽裝影像(stego-images) 之中。

從 part 1 的討論, 我們知道 OutGuess 0.2 並沒有把所有的冗餘位元(redundant bits) 都拿來作為機密訊息嵌入之用。在 Selection process 中, 最多只允許一半的冗餘位元放置機密訊息。

隱藏學這個研究領域有一項要特別注意的就是: 通常我們並不知道將來對手會用什麼的統計測試(statistical tests) 來偵測機密訊息是否被嵌入到媒體之中。假設我們已經知道一些特定的攻擊手法, 自然就可以事先防範, 同樣用一些冗餘位元來將這些因為嵌入動作而產生的統計偏差(statistical deviation) 給修正回來。

作者首先考量的是 one-correlation 和 Maurer test。作者在本篇論文 Section 1 Introduction 中曾提及:

For example, ones and zeros are equally likely in a message that has been encrypted. However, the redundant data being replaced might have a strong correction towards either zero or one. Embedding the encrypted message weakens that correction.

Maurer test 則是一個用來測試所產生的二元亂數資料是否符合良好亂數的規範的工具 (Ueli M. Maurer, "A Universal Statistical Test for Random Bit Generators," Journal of Cryptography, Vol. 5, pp 89-105, 1992 )。基本上, 當有一個冗餘位元從 0 被改成 1, 作者便嘗試在附近找到另一個冗餘位元將其從 1 改成 0, 這樣做的優點是可以避免增加冗餘位元的亂度(entropy), 確保機密訊息無法從這種統計方式偵測出來。然而, 使用上述的方法, 針對 JPEG 影像, 會使得 DCT 係數直方圖走樣(distortion), 如 Figure 5 中的 DCT 係數 -2 與 -1 比 Figure 3 更接近, DCT 係數 2 與 3 則幾乎相同。


Figure 5: The naive statistical corrections cause the frequency of adjacent DCT coefficients to be equalized. It is immediately evident that the image is modified.

要避免 DCT 係數直方圖走樣的情況發生, 勢必要進行其他的校正(correction)工作來維持住 DCT 係數的分布。舉例來說, 如果要嵌入機密訊息到第 j-th 個 DCT 係數, 令這個係數值為 DCT(j), 假設 DCT(j) = 2i, 那這個 DCT 係數就會被改成 2i+1。要校正這個嵌入動作所產生的走樣, 就要在臨近位置找一個 DCT 係數, 其值剛好為 2i+1, 然後將其值改成 2i。令所找到的這個位置為 k, 那麼 DCT(k) 將由 2i+1 改變成 2i。如果在每一個改變原值的嵌入動作後, 就立刻執行這項校正工作, 那所產生偽裝影像的 DCT 係數直方圖將與原始的掩護影像一模一樣。

再者, 校正轉換(correcting transform) 基本上就是要保持所有的 DCT 係數 (即 frequency counts) 維持不變。因此, 以 frequency counts 為基礎的統計方式是無法偵測出原始媒體與偽裝媒體之間的差異的。

令 f 表示在直方圖中的一個 frequency count, 而 g 為其相鄰的 frequency count, 在不失其一般性的情況下, 令 f > g。令 α 表示冗餘位元用於嵌入機密訊息的比例。在嵌入機密訊息後, frequency count 變成:

f* = f - α ( f - g ) / 2 ,
g* = g + α ( f - g ) / 2 .

我們知道當嵌入量 α 為 0% 時, f 與 g 之間的差距為 ( f - g ), 當 α 越來越大時, f* 與 g* 會越來越接近, 當 α 達到 100% 時, 則

f* = f - ( f - g ) / 2 = ( f + g ) / 2 ,
g* = g + ( f - g ) / 2 = ( g + f ) / 2 .

換句話說, 當全部的冗餘位元都拿來做為嵌入機密訊息之用時, f* = g* = ( g + f ) / 2.

OutGuess 為了維持 DCT 係數直方圖不變, 必須保留足夠的冗餘位元可以在嵌入機密訊息後, 做為校正轉換之用, 因此底下的式子必須成立:

(1- α ) g ≥ α ( f - g) /2

上述式子可以化簡得到 α 的預先估計值(a priori estimate), 做為嵌入機密訊息時的參考:

α ≤ 2 g / (f + g)

給定一個機密訊息, 我們可以使用這個估計值來選擇一個用有足夠冗餘位元來保持原始 frequency counts 的掩護影像。有趣的是, 擁有更多 DCT 係數的影像, 並不代表擁有更多可供嵌入機密訊息的冗餘位元, Figure 6 說明了此一現象。Figure 6 中的每一個圈圈代表一個影像, 橫軸表示其擁有的 DCT 係數的總數, 總軸表示經過上述公式計算後, 所得到可以用來嵌入機密訊息的比例(fraction)。


Figure 6: The fraction of the DCT coefficients that can be used for data hiding does not increase linearly for images with more coefficients.

作者希望提出的校正轉換(correcting transform) 能夠具備下列兩個需求(requirements):

1. For any part of the image, the distribution of the DCT coefficients should be similar to the unmodified image.

2. The number of corrections necessary to preserve statistical properties should be small.

仔細剖析這兩個需求, 要同時達到最佳狀況是不可能的。因為如果要讓第二個需求 - 校正個數達到最小, 就要先分析整體的嵌入狀況, 再著手校正所產生整體誤差, 在這種情況下, 很可能發生某些部分影像 DCT 係數的分布, 無法跟原始分布一樣。換句話說, 要做到任何部分影像的 DCT 係數分布和原始分布一樣, 就必須在這個部分影像中, 立即把嵌入機密訊息的走樣修正回來。如此, 就不可能使校正數目達到最小。作者針對這個問題, 提出一個妥協的方法, 為每個頻率(frequency) 定義了一個臨界值 (threshold), 來表示該 frequency count 可容忍的誤差值。


Algorithm 1: This transform preserves the statistical properties of an JPEG image. It keeps track of differences in the frequency counts between original and stego medium. If the differences exceed a certain threshold, the frequency count is adjusted.

作者宣稱 Algorithm 1 可以滿足上述兩項需求。Algorithm 1 是在整個機密訊息嵌入完成之後, 才開始執行校正的。在論文中, Algorithm 1 註記了 5 個標記, 我們在此分別說明這些關鍵步驟:

標記 1 : 從原始掩護影像中, 計算 DCT 頻率的直方圖, 並將之存放於陣列 N 之中。

標記 2 : 決定每一個頻率可容忍的誤差值, 並將之存放於陣列 N* 之中。
　　　　計算方式如下:
　　　　k ← number of coefficients in image;
　　　　α← 0.03 * 5000 / k ;
　　　　N*(i) = α * N(i);
　　　　用陣列 N error 記錄每個 DCT 係數目前的累積誤差。
　　　　Nerror (i) ← 0;

標記 3 : AdjDCT ← DCT(i) ⊕ 1;

Algorithm 1 針對每一個可供嵌入的位置, 從影像的開端開始處理, 如果找到一個 DCT 係數遭到修改, 他並不會直接就去想辦法校正回來, 而是看看這個修改是否已經超出可容忍的程度, 如果只是就先去看看與其配對的 DCT 係數 AdjDCT (標記 3) 是否也存在誤差值, 如果也存在誤差值 (標記 4), 那就正好可以抵銷, 不需另外做修正, 以滿足第二個需求 - 校正越少越好。如果 AdjDCT 並不存在誤差值, 再加上本身的誤差尚未超出容忍值 (標記 5), 則暫時先不做校正動作, 僅是累計其誤差值 increment Nerror [DCT(i)]。如果誤差已經超出容忍值 N*[DCT(i)] 了, 為了滿足第一項需求, 必須要立即執行校正程序: 在附近找到配對的係數修正回來, 也就是執行 Algorithm 2: exchDCT(i, DCT(i)); 如果找不到配對的係數, 則記錄其誤差, 留待最後階段再一起做大範圍 (從影像末端 k, 開始往前找) 的校正工作。

如果想要更進一步了解 Algorithm 1 中 threshold frequencies 作用的讀者, 可以嘗試將 α 值先設定為 0, 觀察執行情形, 然後將 α 值先設定為 1, 再觀察其變化, 應該就能比較了解 α 所扮演的角色。


Algorithm 2: Find a specific DCT coefficient and change it to its adjacent DCT coefficient.

Algorithm 1 在兩種情況下會呼叫 Function exchDCT() 進行實際校正的動作:

1. 當累積的誤差 Nerror 已經超過可容任的範圍, 則會立即進行校正動作, 以免累機誤差太大, 不符合需求 1。

If the number of errors for the coefficient, Nerror[DCT(i)], can be incremented without exceeding its threshold value. If another increment is possible, we continue with the next modification. Otherwise, we have to correct the current modification in the image. The exchDCT algorithm is responsible for that.

2. 最後階段, 進行大範圍的搜尋, 將所有的誤差都校正回來。雖然, 並不是所有的誤差都可以校正回來, 但只要能夠將大部分的誤差都校正回來, 就不會被偵測出來。

After all modifications have been examined, we need to correct all remaining errors. Not all the corrections might be possible. However, if we are able to correct most of the errors, changes in the histogram are not detectable.

　
Back to: Defending Against Statistical Steganalysis (part 1)
Go to: Defending Against Statistical Steganalysis (part 3)


Niels Provos, "Defending Against Statistical Steganalysis,"10th USENIX Security Symposium, August 13-17, 2001.