彙集對稱式認證：從感測點到雲端

Aggregating Symmetric Authentication: From Motes to Clouds

陳煜弦(Yu-Shian Chen)

指導教授 ： 雷欽隆

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2013年)

https://doi.org/10.6342/NTU.2013.01152

摘要

本論文研討使用對稱式密碼學生成的認證的彙集。這也表示認證標記是被對稱性地彙集，或者說就是單純以雜湊函數處理。本論文可概分為應用面與理論面。應用面包含四大主題：動態認證字典、感測網路內的廣播認證、多點路由內的
假訊過濾、以及可檢驗的加密雲儲存。
一、認證字典是一個泛型的計算問題，在於彼方如何檢驗他方是否正確記錄被寄存的資料。以往的解法（多沿用 Merkle 樹）或僅適合靜態認證字典，或使用低效率的資料結構。基於典型的 Merkle 樹，本文提出數個新穎的資料結構來處理動態認證字典，並支援負查詢。包含基數Merkle 樹、疊 Merkle 樹、和二元 Merkle 樹林。與往者不同，這些提案保持了原始 Merkle 樹的結構簡易性。
二、廣播認證是感測網路運作的基礎。受限於節點的有限運算能力和電力，尤其在無線感測網路中，感測點不應採用昂貴的非對稱運算。在這個原則上，μTESLA 的鏈狀設計成為可靠且持久的認證依據。但鏈型的優點在長期來看亦成為其缺點，使得更新認證源極為不便。簾（Curatin）利用壓縮 Bloom 過濾器彙集多重μTESLA。Curtain 增長μTESLA 使用期限與提高更新效率，並延續其自我修
復的功能。mCurtain 則是進階版的Curtain ，可用於多方廣播者的情境中，系統可動態增加或撤銷廣播者。使用 Curtain 和 mCurtain 的成本僅接受端需紀錄少量的點陣圖。
三、輕量化的在路由認證對多跳點網路，特別是無線網路，是難以根除的問題。。在無線環境下，中介的路由點是顯而易見的攻擊標的。攻擊者可任意植入無意義的假性通訊，導致多餘的訊息轉發、消耗節點資源、和降低網路效能。即使假訊最終被識別，路由點必然得為難以完全遏止的假訊付出代價。再次地，本文提出使用 Bloom 過濾器的低成本解法，稱為 EAB。每個使用 EAB 的路由點可在短時間內以輕量運算過濾絕多數的假訊。在多點路由中，最終能成功穿越網路的假訊量以冪次降低。
四、僅能保證機密性或完整性其一的雲儲存並不符現代資料安全要求。沒有加密的遠端儲存等同不可逆的資料外洩；沒有檢驗機制的加密儲存則可能被置換成無效亂碼而無法咎責。層雲（Stratus）針對這種矛盾提出完整解法。以用戶的觀點為本，Stratus 旨在提供對加密雲儲存的便利化存取與資料檢驗。此外，Stratus 隱性地保存原始目錄階層並允許不需要經過反向解密的無痛資料移植與分享。藉由虛設目錄（dummy list）的技巧，Stratus 可以進行懶刪除（lazy deletion）以提高系統效率。其他Stratus 的特點包含確實刪除和O(logN) 的負查詢等
最末，在理論面，本文推導彙集認證的安全極限。首先給予具有 On-The-Fly(OTF) 特性之彙集認證的嚴謹定義。這個定義將涵蓋前述之Curtain、mCurtain、和 EAB 等。接著結合消息理論、認證理論和Bloom 過濾器演算，推導與證明此彙集認證的安全極限。結果呼應過去獨以認證理論或密碼學推論的文獻。
Merkle 雜湊樹和 Bloom 過濾器這兩個古老又簡單的資料結構是本文使用的主要認證技術。讀者將發現即使在非對稱式密碼學主宰的廿一世紀，善用與變化舊工具有機會能更有效率解決新問題。

關鍵字

彙集 ； 認證 ； Merkle 雜湊樹 ； Bloom 過濾器 ； 認證字典 ； 感測網路 ； 雲儲存

並列摘要

This thesis discusses the aggregation of authentication created purely from symmetric cryptography. It also means that the authentication tags are aggregated in a symmetric way, or simply via hash functions. The contents of this work can be can be roughly classified
as the applications and theory parts.
From the aspect of applications, it consists of four computational applications regarding data and communication authenticity, spreading from micro-scaled sensor networks to macro-scaled cloud. These topics include (1) dynamic authenticated dictionary, (2) broadcast
authentication in sensor networks, (3) en-route false injection filtering, and (4) verifiable encrypted cloud storage. Two canonical hash-based data structures are employed, the Merkle Tree (MT) and the Bloom Filter (BF).
1. Dynamic authenticated dictionary: As a generic computation paradigm, the authenticated dictionary is to verify that the delegated remote correctly store the outsourced data. Prior solutions, mostly adopting the Merkle Tree (MT), are either only suitable for static dictionary or lack of efficient structures. We propose several novel approaches to extend the MT's ability of data update and negative query. Unlike the
other hash-based schemes for authenticating dynamic data, these proposals retains the structural simplicity of MT.
2. Broadcast authentication: Broadcast authentication (BA) is a crucial foundation of wireless sensor networks (WSN). Limited by computation and energy resources, the sensor motes should not directly adopt asymmetric cryptography. Hence, the μTESLA protocol has been acting as the major role for doing BA in WSN. The chain structure of TESLA, however, brings inconvenience to update of authentication source. To prolong durability and support self-healing property, the Curtain applies compressed Bloom filters (CBF) to multiple μTESLA. It greatly reduces the network communication overhead at the cost of a moderate memory usage in receiving motes. The mCurtain, an extended version of Curtain, works for scenario of multiple senders. It allows the system to dynamically add and revoke senders.
3. False injection filtering: Lightweight en-route authentication is a challenging task in wireless multi-hop networks. An adversary can inject false data into the system, incurring redundant message forwarding, consuming node resources, and degrading network performance. Although the injection might be identified, en-routers have paid price for them. We utilize Bloom filter techniques, again, to build an authentication
manifest called en-route authentication bitmap (EAB). EAB helps nodes on the routing path to filter out false data in high success rate, thus confine the injection attacks within the one or two hops from the adversary. The evaluation shows that EAB effectively protect the forwarding path of tens of hops with only a few bytes cost.
4. Verifiable encrypted cloud storage: A cloud storage service is never sufficient if it only guarantees one of data confidentiality and integrity. Remote storage without encryption could expose private information to outsiders; while storage without integrity could be appended with garbled and useless cipher. This paper presents the Stratus, an integrated encrypted storage atop of heterogeneous cloud storage.
Standing on user's perspective, Stratus focuses on offering transparent and convenient access and integrity verification of the data outsourced. Also, Stratus preserves implicitly the folder hierarchy of the original storage and allows painless data migration and sharing without backward decryption. By the technique of dummy list, Stratus is able to perform lazy deletion, reducing access overhead. Other salient features of Stratus include assured deletion and space query in O(log n).
Finally, from the aspect of theory, the work derives a rigorous proof of the security extreme of aggregated authentication. First, we give a precise definition of Aggregate message authentication codes (AMACs) with the property of one-the-fly (OTF) verification.
The AMACs encompass portions of each previous mentioned application. Combing information theory, authentication theory, and Bloom computation, the theoretical security extreme of such authentication is derived and proved. The results correspond to prior
research adopting other methodologies in literature.
The Merkle trees and Bloom filters, both ancient and simple hash-based structures, are the two foundations of this thesis. Readers will find that the old tools might be more efficient in tackling emerging problems, even in the modern computational world dominated
by asymmetric cryptography.

並列關鍵字

Aggregation ； Authentication ； Merkle Tree ； Bloom Filters ； Authenticated Dictionary ； Sensor Networks ； Cloud Storage

參考文獻

[27] Yu-Shian Chen, He-Ming Ruan, and Chin-Laung Lei. Stratus: Check and share encrypted data among heterogeneous cloud storage. Journal of Internet Technology, Special Issue on Cloud Computing and Big Data:(to appear), 2013.

[3] Wassim Znaidi, Marine Minier, and Cêdric Lauradoux. Aggregated authentication (AMAC) using universal hash functions. In International Conference on Security and Privacy in Communication Networks (SecureComm), pages 248--252, 2009.

[5] Scott A. Crosby and Dan S. Wallach. Authenticated dictionaries: Real-world costs and trade-offs. ACM Trans. Inf. Syst. Secur., 14(2):17, 2011.

[6] Michael T. Goodrich and Roberto Tamassia. Efficient authenticated dictionaries with skip lists and commutative hashing. US Patent App, 10(416015), 2000.

[7] Michael T. Goodrich, Roberto Tamassia, and Andrew Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In DARPA Information Survivability Conference And Exposition, pages 68--82. IEEE Computer Society Press, 2001.