About OutGuess ... (part 1): N. Provos

OutGuess by Neils Provos
Offical Website: www.outguess.org


Niels Provos & Peter Honeyman 在 2001 年CITI 的技術報告, 還有 2002年 ISOC NDSS'02 研討會論文 "Detecting Steganographic Content on the Internet" 中是這樣描述 OutGuess 的:

[ P.5 ]
　OutGuess is a steganographic system available as UNIX source code. There are two released versions: OutGuess 0.13b, which is vulnerable to statistical analysis, and OutGuess 0.2, which includes the ability to preserve statistical properties and can not be detected by the statistical tests used in this paper.

　OutGuess is different from the systems described in the previous sections in that its chooses the DCT coefficients with a pseudo-random number generator. A user-supplied pass phrase initializes a stream cipher and a pseudo-random number generator, both based on RC4. The stream cipher is used to encrypt the content.

　Because the modifications are distributed randomly over the DCT coefficients, the X²-test can not be applied on a continuously increasing sample of the image. Instead, we slide the position where we take the samples across the image.

　For OutGuess 0.13b, we do not find any clear signatures. Figure 7 shows the probability of embedding for a sample image. The spikes indicate areas in the image where modifications to coefficients cause departures from the expected DCT coefficient frequency.

Figure 7: OutGuess 0.13b is more difficult to detect. Due to the random selection of bits, there is no clear signature.

上面這張圖是論文的 Figure 7, 將整張影像切割成 100 等份(橫軸), 每一等份都用 Chi-Square Attack 去估算嵌有機密訊息的可能性(縱軸)。由於 OutGuess 隨機地將資料分散在整張影像之中, 因此, 分別在這 100 份的部分影像所計算出來的可能值, p, 大小是不固定的, 可以說毫無特定特徵(signature)可言。因此, 相對於 Jsteg/JSteg-Shell 與 JPHide 來說, 隱藏在整張影像的機密訊息是較難被偵測出來的。

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

關於 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.

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

Niels Provos & Peter Honeyman 在 2001 年的技術報告 "Detecting Steganographic Content on the Internet" 中是這樣描述 Jsteg 的:

[ P.4 ]
JSteg is an addition by Derek Upham to the Independent JPEG Group's JPEG Software library. The DCT coefficients are modified continuously from the beginning of the image. JSteg does not support encryption and has no random bit selection.

The message data is prepended with a variable size header. The first five bits of the header express the size of the length field in bits. The following bits contain the length field that expresses the size of the embedded content.

IEEE Security & Privacy 在 2003 May/June 這一期中有一篇文章 "Hide and Seek: An Introduction to Steganography", 在 P. 34 的 Figure 3 中, 提到 Jsteg 的演算法。Niels Provos & Peter HoneyMand 是這樣描述 Derek Upham 的 Jsteg 嵌入法:

Derek Upham's JSteg was the first publicly available steganographic system for JPEG images. Its embedding algorithm sequentially replaces the least-significant bit of DCT coefficients with the message's data (see Figure 3). The algorithm does not require a shared secret; as a result, anyone who knows the steganographic system can retrieve the message hidden by JSteg.

About scientific and technical writing... (1)

做研究真的很有趣, 然而, 英文寫作實在不是我的專長, 仔細想想, 自己中文寫的文章和英文寫的文章, 在數量上, 之間的差別也實在太過懸殊了。不過, 既然走上這條路, 也只好慢慢累積了...

今天看 Hany Farid 的技術報告 "Detecting Steganographic Messages in Digital Images ", 看到他在描述實驗結果的用句, 正是我上學期在寫國科會結案報告時, 想要描述的情境。當時要寫英文摘要, 也翻了好多論文想參考別人的用法。剛剛在想, 如果當時有翻到這篇報告, 參考一下, 應該很快就寫好了。　:)

[ P. 5, for Jsteg ]
In this example, 99% of the training set is correctly classified. In the testing set 98% of the steg images are correctly classified with 2% false positives (i.e., a no-steg image incorrectly classified as a steg image).

[ P. 7, for EZstego ]
On average, 86.6% of the testing set is correctly classified, with 13:2% false positives, and 51:5% detection can be achieved with 1% false positives, Table 1.

[ P. 7, for OutGuess ]
Without statistical correction, detection rates are 80.4% with 19.4% false positives, or 22.5% detection with 2%false positives. With statistical correction, detection rates are slightly worse at 77.7% with 23.8% false positives, or 17.5% detection with 1.0% false positives.

About applications of steganography ... (1)

今天早上在研讀 Hany Farid 在2001年發表的技術報告 "Detecting Steganographic Messages in Digital Images", 報告中提到了有關 steganography 的應用, 包括:
1. unobtrusive military and intelligence communication
2. covert criminal communication
3. protection of civilian speech against repressive governments.

Other applications include unobtrusive military and intelligence communication, covert criminal communication, and the protection of civilian speech against repressive governments. Along with new and improved techniques for hiding information will come techniques for detecting (and possibly removing) such information.

Niels Provos & Peter HoneyMand 在 2001 年的技術報告 "Detecting Steganographic Content on the Internet" 的 Abstract 中也提到了 covert criminal communication:

Steganography is used to hide the occurrence of communication. Recent suggestions in US newspapers indicate that terrorists use steganography to communicate in secret with their accomplices. In particular, images on the Internet were mentioned as communication medium. While the newspaper articles sounded very dire, none substantiated these rumors.

當年的新聞連結如下:
CNN: Bin Laden exploits technology to suit his needs (September 21, 2001)
USA Today: Terror groups hide behind Web encryption (February 5, 2001)

關於 Jsteg 的點點滴滴 (四) : J. Fridrich

Jessica Fridrich 在她 2006 年 Fundamentals of Steganography 課程, Lecture 4 投影片 中, P. 7 談到 Jsteg 的作法, 從投影片中我們清楚的知道 Jsteg 並沒有考慮到四捨五入所造成的影響。完全是針對四捨五入後的 DCT 係數根據要藏入的訊息去修改係數。

關於 Jsteg 的點點滴滴 (三) : T. Tan

中國模式識別國家重點實驗室(NLPR) 在 ICPR04 (23-26 Aug., Cambridge Univ., UK.) 與 ICIP04 (24-27 Oct., Singapore) 兩個研討會都有論文提出, 論文所提出的方法大致是一樣的, 不過, 實驗範圍則有所延伸。

ICPR04 : "On Estimation of Secret Message Length in JSteg-like Steganography"
ICIP04 : "Model Based Steganalysis"

第一篇論文是針對 Jsteg-like steganography 的兩種嵌入次序 (sequential or random) 做隱藏分析; 第二篇論文則是將實驗範圍延伸到 QIM (Quantization Index Modulation) 嵌入技術。

基本上, 兩篇論文在描述 Jsteg 嵌入技術的文章都是一樣的。

The frequently used steganographic method in JPEG format is the JSteg-like algorithm, which is proposed by D. Upham [I]. It works by embedding message bits as the LSBs of the quantized DCT (Discrete Cosine Transform) coefficients. The embedding mechanism skips all coefficicnts with the values of '0' or '1'. There are two embedding ways according to the selection of coefficients. One is sequential embedding; the other is random embedding whose coefficients selection is usually determined by a secret stego key shared by the communicating parties.

在這篇論文中, 還有一點我覺得很有趣！可以做實驗看看。作者引用 P. Sallee 的 IWDW03 論文 "Model based steganography" [ PDF ] 所發現的, 認為用 generalized Cauchy distribution 來描述量化後的 DCT 係數的分布會比用 generalized Laplacian/Gaussian distribution 還要來得精確。

Sallee used a specialized form of a generalized Cauchy distribution instead of the generalized Laplacian. When taking into account a more accurate estimation of the quantization effects, Sallee found this distribution appears to fit DCT coefficients better than the generalizcd Laplacian/Gaussian.

關於 Jsteg 的點點滴滴 (二) : G. Tena

Guillermito Zone 的作者是 Guillaume Tena, 是法國資訊安全專家, 目前在美國　Harvard Medical School (HMS) 任職。

http://www.guillermito2.net/stegano/jsteg/index.html
這個網頁是我看過描述 JPEG steganography 最詳盡的網頁了, 網頁中我個人覺得很精采的部份, 分別如下:

1. 首先 Tena 將 Internet 上, 可以將訊息嵌入到 JPEG 影像的軟體, Open Source 都列出來, 並仔細說明其狀況為何。

2. 對 JPEG 壓縮技術的解說也非常詳盡, 例子更是清楚。尤其在解釋為什麼要先將 RGB 轉換成 YCbCr 的理由, 為什麼要對 Chrominance 做 subsampling, 更是用圖片解釋得讓你一清二楚。

3. 對 DCT 轉換的解釋, 也讓我佩服。用 y = ax + b 描述一條直線的觀念, 直接點破為什麼要做轉換, 這是我覺得看這個網頁收穫最大的地方。( 因為有關 Jsteg 或 JPEG 的資料, 我已經看過太多了！) 這個例子要學起來, 以後教學生時, 就可以派上用場。

4. Quantization 中, 對於 wavelet 的圖片與說明, 更讓我對 wavelet 更能捉得住感覺。

The higher the values on this table, the more details you will eliminate. You're actually going to eliminate the high frequency coefficients: think about removing the small wavelets on top of a big wave.

5. 在 Lossless compression 這段, 清楚地說明了三個壓縮技術 RLE (Run-Length Encoding), DPCM (Differential Pulse Code Modulation), Huffman coding 分別用在哪邊。之前, 我自己的報告中常忽略的 RLE 與 DPCM, 只是強調 Huffman coding 是不夠清楚的。

6. 網頁最後關於 Field A, B, C 的例子, 更是說明的一清二楚！

另外, 有一件事值得一提, 如果你到 Google 查 Guillaume Tena, 你會發現 Tena 最近很可憐, 他被法國法院判需要賠償一家 Anti-Virus 的軟體公司 (Tegam) 14,300 歐元, 原因是他在 2001 年公佈了他所發現關於 Tegam's Viguard anti-virus software 的瑕疵。為了指出他說的漏洞是確實存在的, Tena 一併公佈需要的 65 bytes 的原始碼。Tegam 因此對 Tena 提出違反著作權的官司, 並求償 900,000 歐元。判決前一陣子下來了, Tena 輸掉了著作權的官司！

天ㄚ, Tena 提出的是該公司軟體的安全漏洞耶！

Tena 在他的 Guillermito Zone 網站入口, 請求大家幫他購買一個新的防毒軟體, 原因是法國規定不可以針對罰金進行募款。募款迅速累積超過一萬歐元了, 網站中每天都有統計, 直到目標值 14,299 歐元達到, 將立即停止募款。

很離譜的法國法院吧！完全不懂什麼是資訊安全！

相關新聞:
1. Harvard University researcher punished for finding bugs (28 February 2006)
2. Donations flood in for 'guilty' security researcher (02 March 2006)

關於 Jsteg 的點點滴滴 (一) : N. Johnson

Neil F. Johnson & Sushil Jajodia 在 IHW 98 的論文 "Steganalysis of Images Created Using Current Steganography Software" 中, 有兩段提到 Jsteg, 在 P.277 他說 Jsteg 將 information 藏在四捨五入後的 DCT 係數中, 而且使用的技術就是去改變四捨五入的選擇來藏入資料。

The tool Jpeg-Jsteg is a steganography tool that hides information by manipulating the rounding values of the JPEG DCT coefficients. Information is hidden in the JPEG image by modulating the rounding choices either up or down in the DCT coefficients. Detection of such an embedded message would seem to be quite difficult. (An advantage DCT has over other transforms is the ability to minimize the block-like appearance resulting when the boundaries between the 8*8 sub-images become visible (known as blocking artifact).)

在 P. 283 中則指出使用 Jsteg 藏有資訊的 JPEG 影像, 對那些經過 IDCT 公式轉換回來的係數去重新繪圖, 會產生較多的不規則的古怪圖形, 這些現象都是因為藏資訊會擴大四捨五入造成的誤差所導致。

In plotting the coefficients using the IDCT formula of JPEG images, the expected result is a relatively smooth graph for values of not equal to zero. However, plotting the coefficients of images created with Jpeg-Jsteg produce more erratic graphs and show steps resulting from duplicate coefficient values due to exaggerated rounding errors caused by storing the hidden information. This distortion is more noticeable for coefficient values less than zero.

對了, 2001/02/20 在 Wired News 有一則關於 Neil F. Johnson 的新聞 "Secret Messages Come in .Waves"。新聞中談到 Johnson 在 steganalysis 上的工作, 其中也提到 steganalysis 可以應用到 law enforcement 與 military 用途上。

Johnson's work on steganalysis may seem obscure, but it has important law enforcement and military applications. The National Security Agency and police agencies have underwritten his research -- his center's graduate program at GMU is even certified by the NSA.

在新聞中, 還提到當年希臘與波斯帝國的戰爭...

The practice of steganography has a distinguished history: The Greek historian Herodotus describes how one of his countrymen sent a secret message warning of an invasion by scrawling it on the wood underneath a wax tablet. To casual observers, the tablet appeared blank.

在我自己的國科會計畫書中, 則是這樣描述這段歷史的:

隱藏學的起源, 最早可回溯到兩千多年以前的古希臘時代, 在希臘歷史學家 Herodotus 的史著中, 記載著一個非常有名的故事: 西元前 491 年, 斯巴達國王 Demaratus 因故被放逐後, 被對希臘懷有侵略野心的東方帝國 - 波斯, 奉為上賓。波斯皇帝 Xerxes 在弭平埃及反抗叛亂後, 開始著手安排對希臘各城邦的侵略戰爭。Demaratus 獲知 Xerxes 的意圖後, 便將平時書寫用的小蠟板, 把上層蠟括除, 再將 Xerxes 的企圖刻在木板, 重新用蠟封起, 送回斯巴達皇宮。由於小蠟板的外觀看起來並無異狀, 因此能夠順利通過邊境檢查, 送到斯巴達國王 Leonidas 手中。然而, 並沒有人能夠馬上理會出小蠟板的用意, 最後是由 Leonidas 的妻子 Gorgo 猜出小蠟板的下方可能藏有訊息, 命人括去蠟層後, 使得波斯帝國即將大舉入侵的消息揭露出來。斯巴達皇后 Gorgo 可以說是歷史上所記載第一位成功破解隱藏技術的人, 圖 2 是我們使用 Google 在網路上搜尋到的當年波斯戰爭地圖。