古特曼演算法

古特曼演算法（英語：Gutmann method）是一種將電腦硬碟中的內容，如檔案，進行安全抹除的演算法。該演算法由彼得·古特曼與科林·普拉姆設計，最早出現於1996年6月的期刊文章《Secure Deletion of Data from Magnetic and Solid-State Memory》。主要特色是在要被抹除的區段中重複寫入35個片段。

而片段的選擇，是在假定使用者不知道使用在硬碟的編碼機制為何，因此該演算法特別為3種不同型別的硬碟，設計不同的片段。如果使用者知道硬碟所使用的編碼模式，就可以為這個硬碟選用專屬的片段模式。一個硬碟當中不同的編碼機制，會需要不同的片段模式。

在古特曼演算法當中，大多數的片段模式多是設計給較老舊的MFM/RLL編碼硬碟。較為近代的硬碟類型技術上都不是使用這種較老舊的編碼模式，造成這些由古特曼設計的片段模式成為累贅^[1]。因此，從約2001年開始，ATA IDE與SATA硬碟製造商，針對「安全抹除」標準進行支援設計，避免了使用古特曼演算法抹除整個硬碟的需求^[2]。

自2001年起，一些高技術配置及SATA硬碟製造商的設計已支援ATA Secure Erase標準，使得在清除整個硬碟時，不再需要使用古特曼演算法。^[3]此外，古特曼演算法不適用於隨身碟：一項2011年的研究顯示，有 71.7% 的資料仍可被恢復。而在固态硬盘上，使用該方法後的資料恢復率約為 0.8% 至 4.3%。^[4]

背景

在大多數作業系統中，刪除功能僅會將檔案所佔用的空間標記為可重複使用（即移除檔案的指標），但不會立即移除其內容。因此，在此階段，透過許多資料恢復軟體仍能相對輕鬆地還原檔案。然而，一旦該空間被其他資料覆寫後，已無法透過純軟體方式來恢復被覆寫的資料，因為儲存裝置的介面僅能回傳當前的內容。

彼得·古特曼主張，情报机构可能具備高階工具（例如磁力顯微鏡搭配图像分析），可以偵測磁碟上先前的資料位元。然而，根據《使用磁力顯微鏡從硬碟重建資料》的研究，這項主張被認為站不住腳。^[5]

方法

一次完整的覆寫程序由四組隨機寫入模式作為開頭，接著隨機執行第 5 至 31 次的特定寫入模式（詳見下表），最後再以四組隨機模式作為結束。

每個第 5 至 31 次的模式皆針對某一種磁儲存的代码方式設計，以隱藏磁碟上的資料，達到無法輕易恢復的效果。儘管下表中的位元模式專門針對特定編碼方式，但覆寫時仍會對整個磁碟進行多次寫入，確保資料被徹底覆蓋。使用該方法的最終目標是，即使是高階的物理掃描技術（如磁力顯微鏡），也無法恢復任何資料。


次數	寫入資料 (表示法)		針對的編碼方式之磁碟寫入模式
次數	二进制	十六进制	(1,7)長度限制編碼	(2,7)長度限制編碼	改良頻率調變
1~4	(隨機)	(隨機)
5	`01010101 01010101 01010101`	`55 55 55`	`100`...		`000 1000`...
6	`10101010 10101010 10101010`	`AA AA AA`	`00 100`...		`0 1000`...
7	`10010010 01001001 00100100`	`92 49 24`		`00 100000`...	`0 100`...
8	`01001001 00100100 10010010`	`49 24 92`		`0000 100000`...	`100 100`...
9	`00100100 10010010 01001001`	`24 92 49`		`100000`...	`00 100`...
10	`00000000 00000000 00000000`	`00 00 00`	`101000`...	`1000`...
11	`00010001 00010001 00010001`	`11 11 11`	`0 100000`...
12	`00100010 00100010 00100010`	`22 22 22`	`00000 100000`...
13	`00110011 00110011 00110011`	`33 33 33`	`10`...	`1000000`...
14	`01000100 01000100 01000100`	`44 44 44`	`000 100000`...
15	`01010101 01010101 01010101`	`55 55 55`	`100`...		`000 1000`...
16	`01100110 01100110 01100110`	`66 66 66`	`0000 100000`...	`000000 10000000`...
17	`01110111 01110111 01110111`	`77 77 77`	`100010`...
18	`10001000 10001000 10001000`	`88 88 88`	`00 100000`...
19	`10011001 10011001 10011001`	`99 99 99`	`0 100000`...	`00 10000000`...
20	`10101010 10101010 10101010`	`AA AA AA`	`00 100`...		`0 1000`...
21	`10111011 10111011 10111011`	`BB BB BB`	`00 101000`...
22	`11001100 11001100 11001100`	`CC CC CC`	`0 10`...	`0000 10000000`...
23	`11011101 11011101 11011101`	`DD DD DD`	`0 101000`...
24	`11101110 11101110 11101110`	`EE EE EE`	`0 100010`...
25	`11111111 11111111 11111111`	`FF FF FF`	`0 100`...	`000 100000`...
26	`10010010 01001001 00100100`	`92 49 24`		`00 100000`...	`0 100`...
27	`01001001 00100100 10010010`	`49 24 92`		`0000 100000`...	`100 100`...
28	`00100100 10010010 01001001`	`24 92 49`		`100000`...	`00 100`...
29	`01101101 10110110 11011011`	`6D B6 DB`		`0 100`…
30	`10110110 11011011 01101101`	`B6 DB 6D`		`100`…
31	`11011011 01101101 10110110`	`DB 6D B6`		`00 100`…
32~35	(隨機)	(隨機)

表中的模式透過不同編碼方式展示了磁碟上的位元如何排列。這些模式旨在隱藏原始資料，使即便有進階的工具也難以找回。

批評

美國全國經濟研究所這間私人非營利研究機構的丹尼爾·費恩柏格（Daniel Feenberg）對葛特曼的主張提出了批評。他質疑葛特曼所宣稱的「情報機構有能力讀取被覆寫的資料」的說法，指出此類主張缺乏證據支持。費恩柏格發現，葛特曼引用了一個不存在的資料來源，且其他來源也無法實際證明成功恢復資料，只能進行部分成功的觀察。此外，葛特曼對「隨機」的定義與常見的理解也有所不同。他認為，隨機資料應該是偽隨機數據，且序列的生成規律需為資料恢復方所知。然而，這與一般的「不可預測」隨機數不同，例如由密码学安全伪随机数生成器所生成的序列。^[6]

儘管如此，一些政府的資訊安全程序仍認為，磁碟即使已被覆寫一次，仍屬於敏感資料。^[7]

葛特曼本人對部分批評進行了回應，並在其原始論文的後記中批評了人們對其演算法的濫用。他指出^[8]^[9]：

「自從這篇論文發表以來，有些人將我所描述的35 次覆寫技術，視為一種驅邪儀式來驅逐邪靈，而非基於磁碟編碼技術的技術性分析。因此，他們主張即使在PRML和EPRML磁碟上也應進行完整的 35 次覆寫，儘管這樣做的效果不會比單純以隨機資料覆蓋更有效。」
「實際上，對任何磁碟進行完整的 35 次覆寫都是毫無意義的，因為此技術的設計涵蓋了所有常用編碼技術的組合，包括超過 30 年歷史的 MFM 方法（如果你不了解這段話的意思，請重讀論文）。如果你使用的磁碟採用某一種特定的編碼技術X，只需要進行針對 X 的覆寫，而不需要進行全部 35 次的覆寫。」
「對於現代的 PRML 和 EPRML 磁碟而言，進行幾次隨機資料的擦除已是最佳方法。正如論文所說，『用隨機資料進行徹底擦除，已經是所能達到的最佳效果』。這在1996 年如此，現在依然如此。」
— 彼得·古特曼，〈從磁性與固態記憶體中安全刪除資料〉，奧克蘭大學電腦科學系

參考文獻

^ Gutmann, Peter. (July 22–25, 1996)Secure Deletion of Data from Magnetic and Solid-State Memory. （页面存档备份，存于互联网档案馆） University of Auckland Department of Computer Science. Epilogue section. (writing, "In fact performing the full 35-pass overwrite is pointless for any drive since it targets a blend of scenarios involving all types of (normally-used) encoding technology, which covers everything back to 30+-year-old MFM methods (if you don't understand that statement, re-read the paper). If you're using a drive which uses encoding technology X, you only need to perform the passes specific to X, and you never need to perform all 35 passes. For any modern PRML/EPRML drive, a few passes of random scrubbing is the best you can do. As the paper says, "A good scrubbing with random data will do about as well as can be expected". This was true in 1996, and is still true now.").
^ Communications Security Establishment. July 2006. Clearing and Declassifying Electronic Data Storage Devices （页面存档备份，存于互联网档案馆）, page 7.
^ Clearing and Declassifying Electronic Data Storage Devices (PDF) (PDF). Communications Security Establishment: 7. July 2006. （原始内容 (PDF)存档于2014-03-03）.
^ Michael Wei; Laura M. Grupp; Frederick E. Spada; Steven Swanson. Reliably Erasing Data From Flash-Based Solid State Drives (PDF). USENIX Conference on File and Storage Technologies. 2011 [2018-01-08]. Wikidata Q115346857 （英语）.
^ Data Reconstruction from a Hard Disk Drive using Magnetic Force Microscopy (PDF). UNIVERSITY OF CALIFORNIA, SAN DIEGO. 2013. （原始内容存档于2015-10-27）.
^ Daniel Feenberg. Can Intelligence Agencies Read Overwritten Data? A response to Gutmann. National Bureau of Economic Research. 2013 [2003].
^ Clearing and Declassifying Electronic Data Storage Devices (PDF) (PDF). Communications Security Establishment. July 2006. （原始内容 (PDF)存档于2014-03-03）.
^ Gutmann, Peter. (July 22–25, 1996) Secure Deletion of Data from Magnetic and Solid-State Memory. University of Auckland Department of Computer Science. Epilogue section.
^ Cranor, Lorrie Faith; Garfinkel, Simson. Security and Usability: Designing Secure Systems that People Can Use. 25 August 2005: 307. ISBN 9780596553852.

[Gutman-1] Gutmann, Peter. (July 22–25, 1996)Secure Deletion of Data from Magnetic and Solid-State Memory. （页面存档备份，存于互联网档案馆） University of Auckland Department of Computer Science. Epilogue section. (writing, "In fact performing the full 35-pass overwrite is pointless for any drive since it targets a blend of scenarios involving all types of (normally-used) encoding technology, which covers everything back to 30+-year-old MFM methods (if you don't understand that statement, re-read the paper). If you're using a drive which uses encoding technology X, you only need to perform the passes specific to X, and you never need to perform all 35 passes. For any modern PRML/EPRML drive, a few passes of random scrubbing is the best you can do. As the paper says, "A good scrubbing with random data will do about as well as can be expected". This was true in 1996, and is still true now.").

[2] Communications Security Establishment. July 2006. Clearing and Declassifying Electronic Data Storage Devices （页面存档备份，存于互联网档案馆）, page 7.

[3] Clearing and Declassifying Electronic Data Storage Devices (PDF) (PDF). Communications Security Establishment: 7. July 2006. （原始内容 (PDF)存档于2014-03-03）.

[Wei2011-4] Michael Wei; Laura M. Grupp; Frederick E. Spada; Steven Swanson. Reliably Erasing Data From Flash-Based Solid State Drives (PDF). USENIX Conference on File and Storage Technologies. 2011 [2018-01-08]. Wikidata Q115346857 （英语）.

[5] Data Reconstruction from a Hard Disk Drive using Magnetic Force Microscopy (PDF). UNIVERSITY OF CALIFORNIA, SAN DIEGO. 2013. （原始内容存档于2015-10-27）.

[6] Daniel Feenberg. Can Intelligence Agencies Read Overwritten Data? A response to Gutmann. National Bureau of Economic Research. 2013 [2003].

[7] Clearing and Declassifying Electronic Data Storage Devices (PDF) (PDF). Communications Security Establishment. July 2006. （原始内容 (PDF)存档于2014-03-03）.

[Gutmann-8] Gutmann, Peter. (July 22–25, 1996) Secure Deletion of Data from Magnetic and Solid-State Memory. University of Auckland Department of Computer Science. Epilogue section.

[security-and-usability-9] Cranor, Lorrie Faith; Garfinkel, Simson. Security and Usability: Designing Secure Systems that People Can Use. 25 August 2005: 307. ISBN 9780596553852.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]