Paper: Resampling and the Detection of LSB Matching in Colour Bitmaps

Andrew D. Ker
Oxford University Computing Laboratory, Parks Road, Oxford, England

Security, Steganography, and Watermarking of Multimedia Contents VII,
San Jose, CA, USA., 17-20 January 2005, pp. 1-15

(Original SPIE Digital Library Link)

Abstract

We consider the problem of detecting the presence of hidden data in colour bitmap images. Like straightforward LSB Replacement, LSB Matching (which randomly increments or decrements cover pixels to embed the hidden data in the least significant bits) is attractive because it is extremely simple to implement. It has proved much harder to detect than LSB Replacement because it does not introduce the same asymmetries into the stego image. We expand our recently-developed techniques for the detection of LSB Matching in grayscale images into the full-colour case. Not everything goes through smoothly but the end result is much improved detection, especially for cover images which have been stored as JPEG files, even if subsequently resampled. Evaluation of steganalysis statistics is performed using a distributed steganalysis project. Because evaluation of reliability of detectors for LSB Matching is limited, we begin with a review of the previously-known detectors.

1. INTRODUCTION: LSB STEGANOGRAPHY
1.1. LSB Replacement and LSB Matching
1.2. Detectors for LSB Matching
1.3. Evaluation Methodology

2. DETECTORS BASED ON CLOSE COLOUR PAIRS
2.1. Westfeld’s Detector
2.2. Performance Analysis

3. HISTOGRAM CHARACTERISTIC FUNCTION DETECTORS
3.1. Harmsen’s HCF COM Detectors
3.2. Performance Analysis

4. NOVEL DETECTORS
4.1. HCF COM Detectors Calibrated by Resampling
4.2. Alternative Methods of Calibration
4.3. Totalling Colour Components

5. CONCLUSIONS

Paper: A Method for Automatic Identification of Signatures of Steganography Software

Graeme Bell and Yeuan-Kuen Lee
IEEE Transactions on Information Forensics and Security
Volume 5, Issue 2 (June 2010) pp. 354 - 358.
( Original IEEE Xplore Link )

Abstract

A fully automated, blind, media-type agnostic approach to steganalysis is presented here. Steganography may sometimes be exposed by detecting automatically characterized regularities in output media caused by weak implementations of steganography algorithms. Fast and accurate detection of steganography is demonstrated experimentally here across a range of media types and a variety of steganography approaches.

From StegoRN

這篇論文在該本期刊的 Top Accessed Articles July 2010, 目前排名第 8 位, 還算不錯! (2010/08/21)

Paper: Detecting Low Embedding Rates

Author: Andreas Westfeld

Information Hiding Workshop 2002 (IHW 2002)
Noordwijkerhout, The Netherlands, 7–9 October 2002

Springer-Verlag Berlin Heidelberg,
LNCS 2578, pp. 324–339, 2003.


Abstract

This paper shows three approaches for detecting steganograms with low change density. MP3Stego is a steganographic algorithm with a very low embedding rate. The attack presented here is a statistical analysis of block sizes. It is able to detect 0.001 % of steganographic payload in MP3 files. The second approach is the use of hash functions to combine sample categories for the chi-square attack. One of these hash functions enables us to detect about 0.2 bits per pixel in true colour images. Another algorithm (Hide) was presented at the last workshop and constructed to be secure against visual and statistical chi-square attacks. The detection method for Hide combines the three colour components of each pixel to recognise an increased number of "neighbour colours".

From StegoRN

這篇論文提出三個偵測低嵌入量(改變量)的隱藏分析技術:

1. 針對 MP3Stego -
分析 MP3 檔案中, 每一個 block 的大小, 透過統計的方式找到一般 MP3 檔案不會出現的特徵, 藉此判定是否被 MP3Stego 這個隱藏工具嵌入機密訊息。實驗結果顯示, 當嵌入量為 MP3 檔案所能提供嵌入量的 0.001% 時, 此論文所提出的方法就可以辨識出來。

2. 提升卡方攻擊法(Chi-Square Attack)的偵測能力
第二個技術是透過雜湊函數(hash function) 整合樣本分群(sample category), 然後再使用原來的卡方攻擊法分析。本論文提到透過某種雜湊函數確實可以使卡方攻擊法偵測出儘含有 0.2 bpp 的彩色影像(true color image)。

3. 針對 Hide
Hide 是 IHW 2001 所提出來的隱藏軟體, 其使用的 LSB Matching 的技術可以抵抗卡方攻擊法的分析。這篇論文透過觀察每個色彩的臨色總數(the number of neighbor colors), 發現嵌有機密訊息的影像, 臨色總數明顯增加許多。

From StegoRN

From StegoRN

From StegoRN

關於 JPHide 的點點滴滴 (一) : N. Provos

Niels Provos 在 "Detecting Steganographic Content on the Internet" 這篇論文的 Section 5.2 整節都在談論 JPHide 這個隱藏軟體。內文如下:

　JPHide is a steganographic system by Allan Latham. There are two versions: 0.3 and 0.5. Version 0.5 supports additional compression of the hidden message. As a result, they use slightly different headers to store embedding information. Before the content is embedded, it is Blowfish encrypted with a usersupplied pass phrase.

Because the DCT coefficients are not selected continuously from the beginning, JPHide is more difficult to detect.

The program uses a fixed table that defines classes of DCT coefficients to determine in which order to modify the coefficients. All coefficients in the current class are used first to hide information before the next class is chosen. As a result, coefficients are selected in such a way that they those likely to be numerically high are used first.

One artifact of the implementation is that the information hiding continues in the current coefficient class even after the complete message has been embedded. The first class in the table are the DC coefficients of color component zero. An image with a resolution of 600 * 480 has approximately five thousand DC coefficients. Even if the message is only eight bits long, JPHide modifies all five thousand coefficients in such an image.

這邊提到 JPHide 有一個特殊方式來定義嵌入次序, JPHide 使用一個固定的表格來將 DCT 係數分成不同的 classes, 整張影像相同 class 中的 DCT 係數會依序拿來嵌入機密訊息, 直到此 class 的係數用完了, 才會動用到下一個 class 的 DCT 係數。接著, 相同 class 的係數, 數值較大者也會優先拿來嵌入機密訊息。個人覺得這樣做是有道理的, 因為嵌入影響對較大值的係數來說, 比例相對較小, 因此優先使用。

另外一點令人匪宜所思的是: 即使所有的機密訊息已經嵌入完畢了, JPHide 依然會繼續修改目前這個 class 的所有 DCT 係數。論文中提到一個例子, 第一個 class 就是 DC 係數, 假設一張 600*480的影像, 就會有 (600/8)*(480/8)= 75*60 = 4500 個 DC 係數, 那麼即使機密訊息只有 8 bits, JPHide 依然會去修改這所有的 DCT 係數。

　A pseudo-random number generator determines if coefficients are skipped. The probability of skipping bits depends on the length of the hidden message and how many bits have been embedded already.

JPHide modifies not only the least-significant bits of the DCT coefficients, it can also switch to a mode where the second-least-significant bits are modified.

如其他軟體一般, JPHide 用一個 PRNG 來決定哪些係數該跳過不嵌入機密訊息。然而, 較特殊的作法是跳過的機率是和 1) 機密訊息的長度, 2) 已經嵌入多少資料量。這代表每嵌入 1 個位元, 機率值就隨時進行更新, 用以控制所有的訊息可以完全順利嵌入。另外, JPHide 也會將機密訊息嵌入到次低位元中。

From StegoRN

Figure 6: JPHide has a signature similar to JSteg. The major difference is the order in which the DCT coefficients are modified.

Figure 6 shows the probability of embedding for an image containing information hidden with JPHide. Because JPHide can skip DCT coefficients, the probability is not as high as with JSteg.

Figure 6 是使用 Chi-Square Attack 來針對 JPHide stego-images 分析, 橫軸是將影像平分成 100 等份, 每一等份都用 Chi-Square Attack 計算嵌入機率 p。由於 JPHide 會跳過部份的 DCT 係數不藏, 因此所得到的 P 值並不像 Jsteg 那麼高。


Niels Provos and Peter Honeyman, "Detecting Steganographic Content on the Internet,"ISOC NDSS'02, San Diego, CA, February 2002.

關於 Jsteg 的點點滴滴 (七) : N. Provos

這張圖出現在 Niels Provos & Peter Honeyman 的 2002年 ISOC NDSS'02 研討會論文 "Detecting Steganographic Content on the Internet" 中 ( Figure 4, P. 4 )。原文是這樣描述的:

　Figure 4 shows the result of the X²-test for an image that contains information hidden with JSteg. In this case, the first chapter of “The Hunting of the Snark” has been bzip2 compressed prior to embedding. The low probability at the beginning of the graph is caused by the dictionary at the beginning of a bzip2 compressed file. The dictionary does not look like encrypted data and is not detected by the test.

這邊提到 bzip2 這個壓縮軟體, 作者先將機密訊息 “The Hunting of the Snark” 的 第一章內容 用 bzip2 壓縮至 15 KB, 然後用 Jsteg 將其藏到影像中。由於 bzip2 壓縮檔的檔頭存放著解壓縮時需要用到的 dictionary, 因此在 Figure 4 的最左端 - 約 5% 的影像 - 用 X²-test 所得到的 p 值並不像 5% ~ 25% 區間的 p = 100% 那麼高。


Figure 5: Using JSteg-Shell with RC4 encryption causes the probability of embedding to be high for all embedded data.

這張圖則是針對 Jsteg-Shell stego-image 分析所得到的結果。原文描述如下:

　JSteg-Shell is a Windows user interface to JSteg developed by Korejwa. It supports encryption and compression of the content before embedding the data with JSteg. JSteg-Shell uses the RC4 stream cipher for encryption. However, the RC4 key space is restricted to 40 bits.

　When encryption is being employed, we expect the probability of embedding to be high at the beginning of the image. There should be no exception.

　An example of JSteg-Shell is shown in Figure 5. Just observing the graph allows us to determine the size of the embedded message. Later we show how this can help to improve the automatic detection of steganographic content.

JSteg-Shell 在隱藏前, 針對機密訊息提供壓縮和加密的功能。因此, 沒有意外地, Figure 5 從一開始就有很高的 p 值。觀察上圖, 我們很容易就可獲知嵌入的資料量, 這項資訊可以用來改善自動偵測隱藏的訊息。

Niels Provos and Peter Honeyman, "Detecting Steganographic Content on the Internet,"ISOC NDSS'02, San Diego, CA, February 2002.
　

Detecting LSB Steganography in Color and Gray-Scale Images (RS steganalysis)

Detecting LSB Steganography in Color and Gray-Scale Images
Jessica Fridrich, Miroslav Goljan, Rui Du
Magazine of IEEE Multimedia, Special Issue on Security,
October-November 2001, pp. 22-28.

這篇論文將一張影像中的連續像素切割成一個一個的 pixel group G = (x1, x2, ... xn)。
假設每一個 pixel group 的大小為 2*2, 那麼一張 384*256 大小的影像, 就會有 (384/2)*(256/2) = 24576 個 pixel groups。

針對每個 group, 根據其特性將會被分成 Regular, Singular, Unusable 等三類。用來分類的特性由兩個因素決定:

1. discrimination function f

discrimination function 的目的是評量一個 pixel group 的平坦性(smoothness) 或規則性(regularity)。一般來說, 如果 group 所包含的 noise 愈多, f(G) 就會越大。論文中舉了一個例子, 用相鄰兩個像素值差的總和, 當作 discrimination function 所得到值。

2. flipping: invertible operation F。

flipping 基本上是針對灰階值的一種排列方式(permutation), 且連坐兩次就會回復成原來的灰階值(2-cycles), 即 F(F(x)) = x。論文中定義了三種 flipping operation, 分別為 F1, F-1 及 F0。
The permutation F1: 0←→1, 2←→3, 4←→5, ..., 254 ←→ 255。
The permutation F-1: -1←→0, 1←→2, 3←→4, ..., 255←→256。
　F-1(x) = F1(x+1) -1 , for all x
The identity permutation F0:
　F0(x) = x, for all x

針對每一個 pixel group G, 首先計算 discrimination function f(G) 的值, 然後對 G 做 flipping operation F, 得到 F(G), 然後計算 f(F(G)), 藉由比較 f(G) 與 f(F(G)) 的大小關係, 就可以對 G 進行分類。

　Regular groups:　G 屬於 R <=> f(F(G)) > f(G)
　Singular groups:　G 屬於 R <=> f(F(G)) < f(G)　
　Unusable groups:　G 屬於 U <=> f(F(G)) = f(G)

F(G) 所代表的意思是針對 pixel group G = (x1, x2, ... xn) 中的每一個 xi, 都分別使用相同的 flipping operation F。要針對不同的 xi, 使用不同的 flipping operation F, 必須再提供一個 mask M 來指明。M 是一個 n-tuple 的向量, 每個值都由 -1, 0, 1 所組成。假設 n=4, M=( 0, 1, -1, 0),

FM(G) 所代表的意思就是:
對 x1 做 F0 的 flipping operation;
對 x2 做 F1 的 flipping operation;
對 x3 做 F-1 的 flipping operation;
對 x4 做 F0 的 flipping operation。

使用 FM 的用意是模擬不可逆雜訊干擾行為(invertible noise adding) 對 pixel values 的影響。

RM 表示在針對 FM , 影像中 regular group 數量所佔的百分比 (percent of all group);
SM 則是 singular group 數量所佔的百分比。因此,

　RM + SM ≤ 1　and　R-M + S-M ≤ 1 ( -M: negative mask )

針對作者所提出的方法, 有一個統計假設前提(statistical hypothesis)是:

　RM ~= R-M　and　SM ~= S-M









(未完待續)