具隐密性及完整性的个人档案网状储存系统

1、具隱密性及完整性的個人檔案網狀儲存系統Personal Grid Storage System with Secrecy and Integrity邱錫彥、宋振華、林之寅工業技術研究院摘要在這篇論文中，針對個人使用的檔案伺服器系統，我們提出了一種具資料隱密性及完整性的個人檔案網狀儲存系統。此系統可預防資料被竊取、竄改甚至毀壞。我們並提出了三種資料區塊索引的方法。在單一伺服器損毀時，我們能夠將全部的重要資料復原。我們也根據不同伺服器的特性，如穩定性(availability) 與儲存能力(capability)，來得到不同的檔案儲存規則。關鍵字：安全、檔案系統、儲存系統、檔案伺服器1. 簡介St

2、oica等人Stoica et al., 2001在2001年提出了一種稱為Chord的網路檔案查詢服務模式，這種服務模式是使用在peer-to-peer的網路中，任何人可以藉由這種服務模式，在網際網路上的許多分享出來的檔案伺服器中，找到自己想找的資料。DabekDabek et al., 2002等人也陸續提出了一種稱為CFS(Cooperative File System)的peer-to-peer檔案儲存系統，這種系統提供了一種distributed hash的目錄，來負責儲存與取回特定的區塊(blocks)，且管理了區塊的分配、複製和貯藏等功能。在這篇論文中，針對個人使用的檔案伺服器系

3、統，我們提出了一種具資料隱密性及完整性的個人檔案網狀儲存系統。整個系統可以分成資料分配取回、資料區塊索引、安全的處理，以及個別伺服器的處理與管理四大部分。我們將類似Chord的查詢服務模式，應用在我們系統的資料分配與取回的部分。而不管是Chord、CFS或是我們的系統，要找到一個特定的區塊，必須先知道這個區塊的索引(index)，才能藉由這個索引，找到這個區塊。我們也提出了三種資料區塊索引的方法，來應用到我們的系統。這些區塊索引的方法，也可使用在Chord、CFS的網路檔案分享系統，解決了Chord系統與CFS系統尚未解決的區塊索引問題。在我們的系統中，我們亦考慮到安全性的問題，包含資料的隱密

4、性及完整性，可預防資料被竊取、竄改甚至毀壞，而不使用Chord或CFS這些直接將檔案明文放在可能不被信任的伺服器上的方式。而如果儲存的檔案被竊取，攻擊者無法知道檔案的任何明文資訊，達到資訊的隱密性。若檔案被攻擊者竄改，我們也能由系統的判別來知道資料已被變更，達到資料的完整性。甚至資料若被惡意刪除、破壞，我們也有相對防護的措施來救回資料。值得一提的是，在密碼系統方面，我們只用了對稱式密碼及單向函數，與CFS比較起來，因為沒有用到非對稱式密碼系統，所以提高了整體系統的速度表現。在本系統中，當某一台單機伺服器忽然停止運作時，我們能夠將全部的資料復原，並且重新分配區塊資料。當自己的主機忽然毀壞時，也能

5、夠在任何一台主機，找回所有在伺服器保密的備份資料，並將資料全數救回。在本系統中，我們還考慮到各個伺服器的特性，如穩定性(availability)、儲存能力(capability)與信賴度(trustiness)，來決定各個伺服器的檔案儲存分配及其特殊處理方式。例如，藉由不同單機伺服器的特性，來決定其資料分配的多寡與資訊儲存的方法等機制。當然，本論文亦考慮到每個檔案的新增、刪除以及更新時的方法。在每個伺服器加入與離開時的檔案處理狀況，也提出了處理的方式。2. 相關研究在這個部分，我們將介紹與我們的系統比較有關係的一些研究。包含Consistent Hashing、Chord系統與Coopera

6、tive File System。分別說明如下。2.1. Consistent Hashing每個檔案區塊是用block index來作為區塊分配或搜尋之用，其中block index是將每個區塊作單向函數的運算而得到的值。在得到block index之後，我們使用每個block的index，來mapping到各個Server node的ID，此法與Consistent Hashing Karger et al. 1997的方式很像，也與一些研究計畫Ratnasamy et al., 2001 Rowstron et al., 2001 Sherma et al., 1999有同樣的精神。使用

7、Consistent Hashing的方式的好處是，當Server node有變動時，不需重新改變檔案儲存的位置。而在我們的系統中也有這種特性，當Server node改變，不需要重新改變檔案儲存的位置。2.2. Chord系統在2001年，Stoica等人Stoica et al., 2001提出了一種稱為Chord的資料查詢系統，用在全球Internet的許多電腦同時分享檔案的機制上。就像NapsterNapster、GnutellaGnutella和FreenetClarke et al., 2000，Chord系統是一種peer-to-peer的系統。這個系統將Consistent H

8、ashing的觀念用在他們提出來的Chord Ring。Chord Ring上面的Node ID是由各個電腦的IP與Port作單向函數而得到的值。接著藉由區塊index，來放在相對的Node ID。然而，這個方法是用在每個Server是由不同的人來管理，且必須同時使用他們的機制才可行，而檔案的分享也必須完全遵照他們的方式。一個Server必須一上線，就幫忙儲存許多區塊資料，在下線之前，必須主動將儲存的資料傳遞給他人。對於一般的使用者，可能不想等待下線前搬移資料動作的時間，而不予理會就直接下線了，如此會造成存在這個Server的區塊資料損失。再者，若全球Internet上的許多Server，持續

9、不斷的作上下線的動作，則區塊資料必須不停地被搬移，如此必佔用大量的網路資源，加上使用者忽略下線前動作的狀況，使這個系統不如預期地運作。另外，在如何由一個檔名，找到全部的區塊資料，也是他們正在研究的問題。2.3. Cooperative File SystemDabek等人Dabek et al., 2002提出一種Cooperative File System (CFS)的儲存方法，也是用在全球Internet的許多電腦同時分享檔案的機制上。他們使用Chord Layer與Dhash Layer兩層來運作他們的系統。Chord Layer是使用Chord的方法來搜尋區塊資料，而Dhash La

10、yer則是利用Distributed Hash Table來作區塊的負載平衡（Load balance）、複製（Replication）和貯藏（Caching）的動作。3. 本系統之方法本系統大致上可以分成六大部分，分別是（1）檔案前置處理；（2）資料區塊索引；（3）伺服器管理；（4）區塊分配與取回；（5）伺服器變動處理；（6）個別伺服器處理。其中伺服器管理、區塊分配與取回以及伺服器變動處理與Chord是雷同的，所以我們針對檔案前置處理、資料區塊索引以及個別伺服器處理來作說明。本系統有兩個非常重要的表，分別是File index table與Node table。由於這兩個表非常重要，我們建議

11、將這兩個表，除了隨時放在Client的位置之外，還必須另外隨時備份在一些特定的Server。我們先定義在本系統使用之符號，接著分別說明本系統的方法。表 1：Notation Description 符號敘述符號意義AVA一個伺服器的Availability參數C密文Ih(indx)indxh(c1)|h(c2)|h(c3)|h(ck)k密文切割之區塊數M明文S密文切割後之區塊大小SC一個Physical Server的容量SN#一個伺服器的Server node數|x|檔案x的大小xCeiling function (天花板函數)3.1. 檔案前置處理圖 1：檔案前置處理檔案前置處理可分成（A

12、）檔案加密與切割以及（B）檔案合成、解密與驗證兩個部分。（A）檔案加密、切割與分配如圖1所示，檔案加密與切割的步驟如下：(1) 將明文M做單向函數的運算，得到h(M)，其中h()代表單向函數。(2) 將M|h(M)加密得到密文C。(3) 將密文C以S為單位，切割成c1, c2, c3, , ck，其中k = |C|/S。（B）檔案合成、解密與驗證檔案合成、解密與驗證的步驟與檔案加密、切割與分配相反，其步驟如下：(1) 將c1, c2, c3, , cn 結合成為密文C。(2) 將密文C解密，得到M|h(M)。(3) 比對h(M)是否等於h(M)。若不是，則此區塊有問題，嘗試找到各個區塊的備份資

13、料，並比對各個區塊是否有差異的地方。3.2. 資料區塊索引在資料區塊索引的部分，我們提出三種不同的方法，且各有其優缺點。每個資料區塊索引的方法，又可分成兩個部分，分別是（A）由區塊得到索引；以及（B）由索引得到區塊。這三種方法分別介紹如下。(一) Chained index法所謂chained index法，就是讓每一個block有一個index，而且上一個block紀錄著這一個block的index，這一個block又紀錄著下一個block的index，如此只要找到第一個index，就可以將全部的區塊找到。缺點是在取得每個block時，必須有順序性，無法批次處理。由區塊得到索引的步驟如下。(

14、1) 將ci做單向函數運算後，得到h(ci)，其中i = 1, 2, 3, , k。(2) 如圖2，將h(ci)|ci|h(ci+1)當作區塊，以h(ci)當作區塊的index，準備做區塊資料的分配。圖2：資料區塊索引之index chain法(3) 建立File Index Table（如表2）。包含明文M的檔案名稱FN、時間t，與第一個block的index h(c1)。其中時間t又可以分成建檔時間(create time)，修改時間(modify time)，與最後讀取時間(access time)。表2：File Index Table of chained index methodF

15、ile NameTimeIndexFN1t1h(c11)FN2t2h(c21)FN3t3h(c31)FN4t4h(c41)由索引得到區塊的步驟如下。(1) 由File Index Table找到檔案名稱以及檔案的Index h(c1)。(2) 以h(ci)當作區塊h(ci)|ci|h(ci+1)的index，取回區塊資料h(ci)|ci|h(ci+1)，並比對h(ci)是否等於h(ci)。若不是，則此區塊有問題，嘗試找到此區塊的備份。(3) i+，重複第(2)個步驟，直到找到h(ci)|ci|end為止。這個chained index法，有其變形的方法，例如使下一個index與這個index有

16、關係(e.g. hi+1 = f(hi)，其中hi為ci的index)，又或者使每個index可以事先計算，如此不但在取得各個block時，可以同時處理，而且可以節省紀錄index的空間。例如：使用hash chain，使hi+1 = h(hi)，其中hi為ci的index；也可以使用hi+1 = hi + 1等最簡單的公式。(二) Recorded index法所謂recorded index法，就是讓每一個block有一個index，並將這些index全部紀錄在File Index Table上。如此只要由File Index Table，就可以得到全部的區塊的index，並同步地將所有的

17、block抓回。缺點是若檔案很大時，File Index Table必須紀錄許多個block index，將會佔許多空間。由區塊得到索引的步驟如下。(1) 將ci做單向函數運算後，得到h(ci)，其中i = 1, 2, 3, , k。(2) 如圖3，將h(ci)|ci當作區塊，以h(ci)當作區塊的index，準備做區塊資料的分配。(3) 建立File Index Table（如表3）。包含明文M的檔案名稱FN、時間t，與各個block的index h(c1), h(c2), h(c3), 。圖 3：資料區塊索引之All-index record法表3：File Index Table of

18、recorded index methodFile NameTimeIndexFN1t1h(c11), h(c12), h(c13), FN2t2h(c21) , h(c22), h(c23), FN3t3h(c31) , h(c32), h(c33), FN4t4h(c41) , h(c42), h(c43), 由索引得到區塊的步驟如下。(1) 由File Index Table找到檔案名稱以及檔案的index h(c1), h(c2), h(c3), 。(2) 以h(ci)當作區塊h(ci)|ci的index，取回區塊資料h(ci)|ci，並比對h(ci)是否等於h(ci)。若不是，則此區

19、塊有問題，嘗試找到此區塊的備份。(三) Dual index法所謂dual index法，就是先讓每一個block有一個index，然後將這些index全部整合成另一個新的block，並使這個新的block也有一個index I，紀錄在File Index Table上。如此只要由File Index Table上的index I，就可以先得到全部區塊的index，然後同步地將所有的block抓回。由區塊得到索引的步驟如下。(1) 將ci做單向函數運算後，得到h(ci)，其中i = 1, 2, 3, , k。(2) 令I = h(indx)，其中indx = h(c1)|h(c2)|h(c3)

20、|h(ck)。(3) 如圖4，將h(ci)|ci與I|indx當作區塊，以h(ci)與I當作區塊的index，準備做區塊資料的分配。圖4：資料區塊索引之dual index法(4) 建立File Index Table（如表4）。包含明文M的檔案名稱FN、時間t，與它的Index I。表4：File Index Table of dual index methodFile NameTimeIndexFN1t1I1FN2t2I2FN3t3I3FN4t4I4由索引得到區塊的步驟如下。(1) 由File Index Table找到檔案名稱以及檔案的Index I。(2) 以I當作區塊I|indx的i

21、ndex，取回區塊資料I|indx，並比對I是否等於h(indx)。若不是，則此區塊有問題，嘗試找到此區塊的備份。(3) 將indx中的h(ci)當作區塊h(ci)|ci的index，取回區塊資料h(ci)|ci，並比對h(ci)是否等於h(ci)。若不是，則此區塊有問題，嘗試找到此區塊的備份。3.3. 個別檔案與伺服器的處理我們可以根據檔案的重要性，來決定是否複製(r份)檔案區塊在(r個)CFS Server中，以增強檔案的可用性。關於一個伺服器的Server node個數，我們可以由伺服器儲存空間（Capacity）來考量。伺服器容量大的，就分配多一點的Server node個數，反之亦然

22、。舉例來說，假設一個伺服器的容量為SC，若我們以U為一個Server node的容量，則這個伺服器的Server node數SN#可以為SC/U。另外，除了伺服器儲存空間（Capacity）的考量，我們還可以根據伺服器的Availability，來決定一個伺服器Server node的多寡。一個伺服器的Availability，代表這個伺服器的穩定度，是不是常常當機，或者常常要維修等。在計算SN#後，我們可以再進一步討論一個伺服器的Availability，來影響這個伺服器的Server node數。舉例來說，我們可以令一個伺服器的Availability AVA為0到10的整數，0代表最弱、

23、5代表一般、10代表最強，則這個伺服器的真正Server node數SN#就等於SN# (AVA/5)。3.4. 伺服器管理、變動處理與區塊的分配與取回在這篇論文，我們將Chord的方法，應用在個人檔案伺服器管理中。除了配合本論文的index之外，伺服器管理與變動處理方式與CFS系統一樣，而區塊的分配與取回也是使用Chord系統的方法。3.4.1 伺服器管理在Chord系統中，每一個node都有它的successor node。如果這個node存在一個server，那麼這個node的successor node就是它本身；如果這個node不存在一個server（virtual node），那麼

24、這個node的successor node就是這個node的順時針遇到的第一個server node。這時找一個virtual node的successor node就必須靠一個server node的Finger Table，來快速尋找。在我們的系統中，我們將successor node的資訊，放在一個Node Table上（表5為個hash長度為4的例子）。如此，只要查詢這個Node Table，就可以快速地找到每個node的successor與predecessor。表5：Node TableIDIP or DNSuccessor ID000080.245.197.xxx00000001

25、61.219.38.xxx00010010140.96.111.xxx00100011Null0100010080.245.197.xxx01000101216.109.112.xxx01010110140.96.111.xxx01100111Null1000100080.245.197.xxx10001001140.116.163.xxx10011010140.96.111.xxx10101011Null1100110080.245.197.xxx11001101209.59.137.xxx1101111061.219.38.xxx11101111Null00003.4.2 區塊分配與取回若

26、我們要將檔案儲存在我們的系統中，在做了檔案的加密與切割之後，就要將資料區塊分配並儲存在Chord Ring的Server node上。反之，若我們要將儲存在系統中的檔案取回，我們必須在Chord Ring的Server node上找到我們的檔案區塊，並在取回檔案區塊後，做檔案的合成、解密與驗證。至於區塊的分配與取回，必須先決定使用哪一種index方法，再使用與Chord系統相同的方式來分配或取回區塊。3.4.3 伺服器變動處理在確定Physical Server的個數（2個以上）與Server Node的個數之後，可以開始建立本系統。此系統的Server Node位置大致上是不會變動的。然而，

27、伺服器加入、伺服器離開，以及伺服器損壞時，Server Node的位置將會改變，我們也必須對Node Table做調整。而Index是與區塊在一起跟著改變的，故不須要更動File Index Table。4. 系統與安全性分析在這個部分，我們大致說明一些在文章中尚未談到的系統特性，包括當Physical server增加時，系統的Scalability特性；資料在Server node變動時，資料區塊儲存的一致性；以及當Index一樣時的碰撞問題。並在最後作一個系統安全性的分析。4.1. Scalable的系統在Chord Ring系統中，每一個Server node的ID長度為hash的長度

28、。若增加Physical Server，其ID值並不需要改變，故可以大量地增加Physical Server，而不影響整體的檔案存放方法與位置。4.2. Consistent的資料在本系統中，不管是chained index法、recorded index法或是dual index法，資料區塊的index是計算區塊的單向函數來獲得，是一種確定式（非機率式）的計算方式。而資料區塊存放到Server node的位置，也是由區塊的index來決定，故也是一種確定式的存放方法。在Server Node增加或減少時，大部分的資料區塊存放位置並不會改變，只會變動增加或減少的Server Node本身，及鄰

29、近Server Node的資料。4.3. 資料碰撞問題在我們的系統中，兩個區塊的index如果完全一樣，那麼就產生區塊index碰撞問題，儘管這種狀況發生的機率非常小。當區塊的index發生碰撞時，解決的方法非常簡單，只要將兩個區塊同時取回，並分別做區塊整合與解密的動作，那麼在檔案驗證甚至人工驗證的過程中，就可以判定那一個區塊是正確的。另外，如果在File Index Table，檔案名稱完全一樣，且無法由時間（建立時間、修改時間、最後讀取時間）來判斷，或者時間也完全一樣，儘管這種狀況發生的機率也非常小。這個時候就發生了檔名碰撞的問題。解決這種問題也非常簡單，只要將兩個檔案同時取回，即可用人工

30、驗證的方法，判定那一個檔案是自己要的。此時，建議將兩個檔案的名稱，重新作適當的命名，以免同樣的情形發生。最後，在Dual index方法中，如果兩個檔案的index I值完全一樣，那麼就產生的檔案index碰撞問題，儘管這種狀況發生的機率也非常小。這時的處理方式與檔名碰撞問題的處理方式完全一樣，先將兩個檔案index為I的檔案同時取回，再判定那一個檔案是自己要的。4.4. 安全性探討在我們的系統中，我們考慮到安全性的問題，包含資料的隱密性及完整性，可預防資料被竊取、竄改甚至毀壞。當資料被攻擊者竊取時，因為資料是加過密的，所以攻擊者無法知道明文資訊。而當資料被竄改時，因為所有的block的ind

31、ex，等於block內容的hash值，若攻擊者想更改block內容，則必須找到一樣的hash值，來當作這個block的index，找到這種block的機率非常低，約2-160（若使用SHA-1演算法）。就算攻擊者真的成功地偽造出個一樣hash值的block，在密文C解密之後，會得到M|h(M)，這時候檢查h(M)是否等於h(M)，就可以知道資料是否被竄改，而這裡竄改成功，又系統檢查不出來的機率也是2-160。如果攻擊者直接毀壞甚至刪除了一個block，我們可以在這個block的Next successor找到複製的block，來得到毀壞或刪除的block資料。另外，在密碼系統方面，我們只用了對

32、稱式密碼及單向函數，與CFS比較起來，因為沒有用到非對稱式密碼系統，所以提高了整體系統的速度表現。5. 結論在這篇論文中，針對個人使用的檔案伺服器系統，我們提出了一種具資料隱密性及完整性的個人檔案網狀儲存系統。此系統可預防資料被竊取、竄改甚至毀壞。我們並提出了chained index、recorded index與dual index三種不同資料區塊索引的方法。在單一伺服器損毀時，我們能夠將全部的重要資料復原。我們也根據不同伺服器的特性，如穩定性(availability) 與儲存能力(capability)，來得到不同的檔案儲存規則。我們最後也作了安全性分析與資料碰撞問題的討論。參考文獻1

33、. Clarke et al., 2000 Clarke, I., Sandberg, O., Wiley, B., and Hong, T. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the Workshop on Design Issues in Anonymity and Unobservability (July 2000), pp. 4666.2. Dabek et al. 2004 Frank Dabek, Russ Cox, Frans

34、Kaashoek, Robert Morris (2004), Vivaldi: A Decentralized Network Coordinate System, In Proceedings of ACM SIGCOMM04, Portland, Oregon, Aug, 2004.3. Dabek et al. 2002 F. Dabek, M. F. Kasshoek, D. Karger, R. Morris, and I. Stoica. (2002), Wide-area Cooperative Storage with CFS. ACM SOSP01, October 2001. Topologies with Rocketfuel. ACM SIGCOMM, 2002.4. Gnutella Gnutella website. .5. Karger et al. 1997 Karger, D., Lehman, E.