前言

Dropbox 是一個很受歡迎的雲端資料儲存與備份服務 , 從使用者的角度 , 它真的很方便 , 有些很大的檔案往往也能很快就能完成上載 。 但您想過它為什麼可以做到這樣快速上傳 , 背後的技術原理是什麼 ? 對於您的資料安全與個人隱私又有什麼影響 ? 山姆鍋根據自己的了解 , 為您解釋 Dropbox 到底是如何運作的 。

雲端儲存或備份是目前很受歡迎的服務 , 尤其是以 Dropbox 為其中的代表 。 本文主要目的在說明類似 Dropbox 這樣的服務如何運 作 , 不代表 Dropbox 完全按照本文所描述的方式執行 。 雖然以 Dropbox 為例子 , 但基本概念也適用其他服務供應商 。

為了確保資料的可用性 , 雲端儲存服務必須提供一定的資料冗餘性 (Redundancy), 不管是藉由 「 資料複製 (Data replication)」 或者透過 「 資訊擴散演算法 (Information Dispersal Algorithm)」 [1] 來達成 。 關於 「 資訊擴散演算法 」, 您也可以參考山姆鍋的 這篇文章

「 資料複製 」 適合用在常常需要讀取的資料 ; 「 資訊擴散演算法 」 通常用在備份資料上 。 為了方便說明 , 之後當文章提到存一份檔案或區塊時 , 根據冗餘性需求 , 其實應該有多個備份 。

避免資料重複儲存

對於所有使用者上傳的資料 , 由於成本上的考量 , 同樣的資料系統只會存一份 。 何謂同樣的資料 ? 同樣的檔案自然是只有存一份 , 但是系統不是傻傻地以檔案為單位 , 來判斷資料有沒有重複 。 而是將每個要存放的檔案切割成很多較小區塊 , 然後根據這些區塊內容計算出雜湊值 (Hash value) 當作鍵值 (key) 來判斷是否有重複 。

如果您稍微思考一下會發現 : 即使是不同檔案 , 還是有可能大部份的內容是相同的 , 例如 : 同一個檔案在不同時間點的不同版本 。 這對於使用檔案系統作版本管理的人很常見 。 所以 , 將檔案切割成區塊來儲存 , 用於重複資料刪除 (Data deduplicaiton) 可以是很有效的作法 。

這裏衍生出一個有趣的技術問題 : 系統如何切割檔案成較小區塊 ? 自然不會是切割成固定大小 , 因為這樣做只要檔案小小的修改 , 就可能造成後面區塊切割點的改變 , 而造成區塊內容的改變 。 各家業者的演算法也許不同 , 但可以確定的是 : 都不會因為檔案小小的修改就造成多數區塊變動 。 針對切割演算法 , 山姆鍋打算在後續文章中提供一個我在網路上發現的有趣方法 。

大致了解資料如何儲存後 , 才好理解客戶端如何與雲端共同合作來避免資料重複上傳 。

避免資料重複上傳

當 Dropbox 客戶端偵測到有新增或修改的檔案時 , 它基本上會依照下列步驟來上載資料 :

  1. 使用檔案切割演算法計算一組區塊檢查碼後 , 上載這組檢查碼到雲端服務器 [2]
  2. 雲端服務器根據這組檢查碼以及目前已經存在系統的資料區塊 , 通知客戶端哪些資料區塊需要上傳 。
  3. 客戶端根據服務器的指示 , 只上傳必要的資料區塊 。

按照這樣的步驟 , 您可以知道 :Dropbox 很聰明地避免了資料重複上傳 。 但細心的讀者也許會注意到 , 即使是第一次放入 Dropbox 的檔案 , 有時也很快就上傳完畢 , 尤其是從別的地方取得的檔案 。 事實上 , 如果有人已經上傳過您要上傳到 Dropbox 的檔案 , 您可以省下上載的時間跟頻寬 。

節省時間跟頻寬 ? 從某個角度來說 , 這是優點 。 但是資料在上傳之前不是應該就加密過嗎 ? 為什麼資料還會跟別人的重複 ? 這就牽涉到下一小節要說明的 Convergent encryption

Convergent Encryption

能夠加密資料同時做到重複資料刪除的秘密在於 Convergent encryption 這個加密技巧 。 在 避免資料重複儲存 這一小節 , 山姆鍋提到儲存的檔案會被切割成較小的資料區塊 。 其實 , 除了這些資料區塊外 , 系統還會儲存中介 (Meta) 資料區塊 , 這些中介資料區塊提供實際資料區塊的索引 。 屬於同一個檔案的中介與實際資料區塊 , 通常會組織成樹狀資料結構 , 如下圖所示 :

Convergent-encryption

為了幫每個資料區塊加密 , 需要使用某個 對稱式加密 (Symmetric encryption) 以及雜湊演算法 (Hashing algorithm), 這裏山姆鍋假設加密使用 AES-256 CBC 模式 , 雜湊使用 SHA-256, 這兩者的組合很常被實際應用在雲端儲存服務 。 針對葉節點 (Leaf node) 資料區塊的加密步驟如下 :

  1. 計算資料區塊的 SHA-256 雜湊值 (Hash value)。
  2. 以上述步驟得到的雜湊值當作金鑰 , 使用 AES-256 CBC 加密此資料區塊 。

針對內部節點 (Internal node) 資料區塊加密步驟如下 :

  1. 將子節點的位址 、SHA-256 雜湊值以及其他中介資料寫入此資料區塊 。
  2. 計算此資料區塊的 SHA-256 雜湊值 (hash value)。
  3. 以上述步驟得到的雜湊值當作金鑰 , 使用 AES-256 CBC 加密此資料區塊 。

最後 , 根節點 (Root node) 的加密步驟跟內部節點相同 。 根節點的位址以及雜湊值會存放在一個使用者專屬的資料索引中 , 資料索引的大部份資料會以 Master key 來進行加密 。 總結一下 Convergent Encryption 的特性 :

  1. 相同內容的資料區塊雜湊值一定相同 。
  2. 使用相同的雜湊值當金鑰 , 經過加密後的資料區塊自然相同 。
  3. 只要保護好 Master key, 就有了完整加密保護機制 。

由於資料區塊的加密只跟區塊的原始內容有關 , 因此 , 不管資料區塊來自哪個使用者 , 加密後都會產生相同的內容 !!! 這個特性對於資料安全與個人隱私會有某種程度的影響 。

資料安全與個人隱私

像 Dropbox 這樣的雲端儲存服務 , 對於您的資料安全性以及個人隱私 , 有多少保障 ? 針對資料安全這點 , 先記住 :Dropbox 擁有您的解密金鑰 (Master key), 能夠在雲端將您的資料解碼 , 這也是使用者可以使用 Web 介面存取檔案的原因 。 倒不是說 ,Dropbox 會故意洩漏您的資料 , 但是下列原因 , 可能會讓您的資料暴露在危險中 :

  1. Dropbox 遭到駭客入侵 :

    可能性雖然低 , 但也不能忽略 。

  2. 內部人員操守問題 :

    內部人員可能受到威脅利誘 , 監守自盜 。

  3. 受到當局強制要求 :

    政府單位在某些情況下 , 可以依法強制 Dropbox 提供使用者資料 。

  4. 收到法院強制命令 :

    電影 、 音樂等版權業者 , 透過證明有人在 Dropbox 放置侵權內容 , 向法院申請要求 Dropbox 提供有存放該侵權內容的使用者資料 。

針對第 4 點 : 只要計算檔案上載時間便可以判斷是否有人已經在 Dropbox 上放置相同內容 。

那麼要怎樣改進 Convergent encryption 的缺點呢 ? 其實只要資料區塊在做加密時 , 使用區塊雜湊值加上使用者個人的秘鑰 [3] 。 由於每人使用不同的金鑰 , 不同的使用者間 , 就算是相同的資料也不會產生相同的編碼 。 如此 , 就可以避免資料區塊在使用者間共享 , 但依然達成同一使用者重複資料刪除的優點 。

結語

如果您有使用 Dropbox 這樣的服務 , 您必須在安全與便利之間做選擇 。 要維持便利 , 就接受服務安全性上的限制 。 針對需要較高安全性或者隱私性的檔案 , 使用工具先加密後再上傳 ; 或者選擇一家不會在使用者間分享資料區塊的供應商 。

參考資料

Rsync: https://en.wikipedia.org/wiki/Rsync

關於 rsync algorithm 演算法 : http://ijecorp.blogspot.tw/2014/02/rsync-algorithm.html

Data deduplication: https://en.wikipedia.org/wiki/Data_deduplication

對稱式加密 : https://en.wikipedia.org/wiki/Symmetric-key_algorithm

Convergent encryption: https://en.wikipedia.org/wiki/Convergent_encryption

How Does Dropbox Store Data?: http://blog.fosketts.net/2011/07/11/dropbox-data-format-deduplication/


[1] 資訊擴散演算法 (Information Dispersal Algorithm) 將資料切割成 K 個區塊 , 使用 Reed-solomom 這樣的糾刪碼產生 M 個同位檢查 (parity) 區塊 , 將這些 (K + M) 個區塊分散到不同的節點 。 讀取時 , 只要其中任意 K 個資料區塊便可以還原原始資料 。
[2] 由於 Dropbox 有使用 Rsync 程式庫 , 可以假設它利用跟 Rsync 類似方法做切割 。
[3] 只要是單一使用者專屬的亂數值就可以 。