局部敏感哈希（Locality Sensitive Hashing，LSH）是一種作為可擴展，近似最近鄰搜尋物件的演算法。LSH可以預運算一個哈希（Hash）來跟另一哈希（Hash）作快速比較以判斷它們的相似度。LSH 的實際應用之一是用來優化資料處理和分析。一個例子是交通網路公司Uber將LSH實作在它們的架構中，用來處理資料以判斷行程有重疊的路線以減少GPS資料的不一致。趨勢科技從2009年開始就一直在此領域進行積極研究並發表了報告。在2013年，我們開放原始碼了一套適合用在安全解決方案的 LSH實作：趨勢科技局部敏感哈希（TLSH）。
TLSH是LSH的一種作法，可以用在白名單機器學習擴展的模糊哈希（fuzzy hashing）。TLSH可以生成用來分析相似性的哈希（Hash）值。TLSH根據與已知正常檔案的相似度來協助判斷是否能夠在系統上被安全地執行。比方說同一應用程式不同版本的數千個哈希（Hash）值可以透過排序和簡化來進行比較和進一步分析。後設資料（metadata）如憑證可以用來確認該檔案是否正常。
TLSH開發時也考慮到了主動合作。我們提供了開放原始碼工具來協助學習、評估和進一步加強TLSH。我們也有定期更新的後端查詢服務讓獨立安全研究人員和合作夥伴可以用來查詢及比較自己的檔案與好檔案間的相似度。
趨勢科技的研究顯示與LSH的其他開放原始碼版本比起來，TLSH是一種高精度的相似性摘要（similarity digest），在其範圍內更加靈活，更不易被攻擊，並且具備快速搜尋機制。TLSH還支持Linux或Windows（Visual Studio）和Python擴充環境。
TLSH如何協助企業?
對企業來說，辨識環境內安全的應用程式和檔案是件重要的任務。這通常是由IT和系統管理員來完成，他們通常是利用白名單（跟已知的好檔案列表進行比較）或憑證等方法。但這些方法都有局限性；白名單解決方案可能沒有完整的好檔案列表。要一直追蹤正常檔案的快速變化也相當的困難，這些是白名單解決方案的已知問題。而另一方面，只依賴憑證可能會出現安全漏洞，因為連憑證基礎設施也可能會被駭。
企業可以將檔案分類為：
- [群組WL]：在白名單內的檔案。
- [群組TC]：可信任軟體廠商憑證簽章的檔案。
企業可以採用政策如：
- 只允許群組WL內的檔案執行。
- 只允許群組WL或群組TC內的檔案執行。
政策A可能過於嚴格；檔案更新和安全更新都可能沒有在白名單內。政策B可能有問題，因為憑證簽發單位會被惡意濫用（惡意軟體可以用受信任的憑證發行單位簽章），或者是憑證基礎設施可能會被駭。
TLSH允許我們定義另一組檔案：
- [群組TLSH]：和白名單內檔案相似的檔案，並且跟相關檔案具備相同的憑證簽章。
群組TLSH還是可能有惡意軟體，因為惡意元件可以被插入正常應用程式。相似度測試可以和後設資料（如受信任的憑證簽章單位）結合來判斷軟體是否被允許執行。這會帶來新的政策：
- 只允許（群組WL內或是[群組TLSH,群組TC]交集）檔案執行
當加入到白名單系統，TLSH可以跟上軟體的快速修補和版本發行周期。提供組織更有效的方法來保持系統更新同時顯著地減少誤判。
簡而言之，TLSH讓企業可以避免去比較軟體更新版本的哈希（Hash）與允許執行的好檔案哈希（Hash）列表。進一步地說：我們的研究之一是將查詢一種應用程式/軟體超過50個版本所產生數以萬計不重覆的哈希（Hash）值簡化成TLSH生成的哈希（Hash）值，然後再分析它的數位簽章來確認是否為能夠安全執行在系統上的正常的檔案。
我們接下來會詳細介紹TLSH如何運作、如何產生以及如何更進一步用來保護企業：
趨勢科技局部敏感哈希（TLSH）：概述
TLSH協助偵測檢查已經在電腦或要放入電腦的檔案。它可以用來確保只有正常應用程式或檔案可以在系統上執行、開啟或儲存。TLSH提供對未知檔案與已知正常受允許檔案間相似性進行即時比較的機制。相似性摘要（similarity digest）的用意是提供可靠的關聯作法來識別每個檔案不同版本間相似度和獨特特性。
這個功能分為下面幾層：
- 相似性摘要（similarity digest）計算。提供一種方式來計算檔案的相似性摘要（similarity digest），並作比較來取得相似性或說是「距離分數」。距離分數可能從0到2000，這些「分數」表示兩個相似性摘要（similarity digest）間的數學距離。分數（或距離）越小，兩個檔案間的相似性越大。距離分數0代表基本上是相同的檔案。
- 可擴展相似性摘要（similarity digest）搜尋機制。此功能提供一個直接的方式來搜尋、交叉檢查和確認不明或可疑檔案與一組已知正常檔案相似性摘要（similarity digest）間的相似性。這搜尋機制也必須能夠擴充。因為會有相當大量的已知正常檔案摘要會被加進資料庫，同時必須維持可接受的低搜尋時間。TLSH使用的搜尋機制可以擴展到數千萬筆以上的相似性摘要（similarity digest）。
應用程式也可以在電腦實作本地端服務（如圖1）來使用TLSH，進行自己的相似性摘要（similarity digest）搜尋和比較。或實作成Web服務（如圖2）來替電腦系統處理搜尋和比較操作。
圖1：在本地端電腦操作TLSH
當作為本地端服務，這系統會接收一組相似性摘要（similarity digest）和一組已知正常檔案的相應文件標識。相似性摘要（similarity digest）搜尋機制會接著建立索引。相似性摘要（similarity digest）應用程式會計算傳入的未知檔案摘要。然後這應用程式使用索引來執行資料庫的近似最鄰近搜尋。
圖2：Web服務操作TLSH
TLSH以Web服務運作會略有不同。已知正常檔案會先儲存到Web伺服器上。相似性摘要搜尋機制計算所有儲存的檔案摘要並建立索引。該系統用Web伺服器上同樣的相似性摘要（similarity digest）計算層來計算輸入未知檔案的摘要。每個未知檔案的相似性摘要（similarity digest）接著會送到Web伺服器，讓Web服務應用程式用相似性摘要（similarity digest）搜尋機制來對每個未知摘要與已知正常檔案摘要進行搜尋和比較。對應已知正常檔案相似性摘要（similarity digest）的檔案ID接著會傳回電腦，然後決定要對這些檔案採取何種行動。
在系統採取動作前，有兩個選擇性步驟可以考慮。在檔案ID傳回電腦後，系統可以在查詢用類似檔案ID儲存的檔案。對應於每個檔案ID的相似檔案詳細資料接著會傳回電腦，然後決定要對檔案做什麼。
TLSH的優劣？
正常的電腦程式會不斷變化，從一連串的小更新到顯著的修改，包括修補程式、功能增強和檔案損毀。這些變化都可能改變程式的哈希（Hash）值。這對大多數傳統白名單軟體造成問題，因為它們比對的是加密哈希（Hash）如SHA256或MD5，加上已知好檔案哈希（Hash）的資料庫。
惡意分子可以將惡意程式碼插入檔案或程式，讓其哈希（Hash）值跟正常版本相似。TLSH用相似性摘要（similarity digest）的資料分數來分析程式以判斷這是一個好檔案。如果與已知正常程式相似，會進行額外測試來確認新檔案來自跟原始檔案相同的可信賴來源。
白名單應用程式使用相似性摘要（similarity digest）的作法已經相當普遍，這要歸功於像SDHASH和SSDEEP這類工具。兩者都可以用來計算和比較哈希（Hash）值的相似性。然而，SDHASH和SSDEEP所用的線性搜尋相當慢。根據我們的測試及分析，SSDEEP經常會漏檢並因此錯失識別電腦程式進行的更新。SDHASH比對具有相同的64位元序列的檔案，讓它可以比較具備顯著重疊區域（如使用共享的程式庫）的電腦程式，但其他部分可能會有大大不同。
此外，SSDEEP、SDHASH及其他相似性摘要（similarity digest）不具備快速搜尋機制；將其用在白名單系統可能並不實際，因為需要比較高達數千萬筆的正常電腦程式。使用索引和TLSH（以適當的距離分數）讓我們可以得到與一般資料庫查找相同的速度。
趨勢科技局部敏感哈希於3月30日和31日在新加坡濱海灣金沙飯店的2017年亞洲黑帽大會上以「使用局部敏感哈希的智慧型白名單」主題公開。同時也發表為同儕審查報告 – 「TLSH – 一種局部敏感哈希」和「使用隨機化來攻擊相似性摘要」。
＠原文出處：Smart Whitelisting Using Locality Sensitive Hashing 作者：趨勢科技（Jon Oliver和Jayson Pryde）