改進的Mix&Slice 算法: 對稱密碼在云存儲的應用*

杜少宇, 鄧辰辰, 矯 琳

1. 密碼科學技術國家重點實驗室, 北京 100878

2. 清華大學北京信息科學與技術國家研究中心, 北京 100084

1 簡介

2016 年的CCS 會議上, Enrico 等提出了一種基于對稱密碼的Mix&Slice 算法[1], 用于解決云端加密數據高效的權限撤銷問題. Mix&Slice 算法面向云計算與云存儲服務, 是解決現在越來越多的企業和個人用戶傾向于使用云存儲, 將自己的數據存放在外部不可控環境下導致安全隱患問題的一種方法. 對數據進行加密是保證合法用戶對數據的訪問控制的一種有效方式[2–9], 使用加密技術有三個優點: (1) 加密的代價低, 對于性能要求高的應用和場景尤其適用; (2) 加密防止數據存儲提供商對數據的讀取; (3) 加密不需要可信方制定強制政策, 數據擁有者個人對自己的密鑰負責.

用密碼技術實現訪問控制的技術難點之一在于訪問權限的撤銷. 數據擁有者可以通過分發密鑰來授予用戶數據訪問權限, 權限撤銷時數據擁有者可以采用兩種方式控制對數據的訪問, 一種方式是用新密鑰重新加密全部數據, 另一種方式是撤銷對原密鑰的訪問權限. Mix&Slice 算法是一種簡潔的權限管理方案,避免對大規模數據的上傳和下載, 并且能夠防止用戶使用本地存儲的密鑰解密數據. 算法的主要思路是在密文的每一比特充分混淆的基礎上, 對密文的一小部分比特重新加密. 由于密文充分混淆, 一小部分的缺失將導致整個密文不能解密, 以此實現對數據的權限控制. 這與AONT (all or nothing transform)[3]算法的思路相似.

Mix&Slice 算法運行時,先將數據分為若干大分塊;在大分塊內進行混合,混合基于并行迭代地使用對稱加密算法并合理設置迭代策略; 然后將大分塊切分到許多片段, 任何一個片段的缺失將導致所有大分塊無法解密; 權限撤銷時, 隨機選擇一個片段用新密鑰重新加密. 設計者[1]給出了Mix&Slice 算法的安全性分析, 包括為了保證加密數據的安全使用初始向量IV, 研究如何抵抗合謀攻擊, 詳細計算了已撤銷權限的用戶仍然能夠訪問數據的概率. 由于基礎加密元件為分組加密算法, Mix&Slice 算法的效率優于已有的訪問控制策略.

本文聚焦于Mix&Slice 算法的安全性及部署場景, 發現算法安全性不足, 其初始向量的使用不當可導致數據泄露. 我們討論為了保證Mix&Slice 算法的安全, 算法需要與已有的對稱加密算法配合使用; 進一步討論在不同的分組密碼工作模式的配合下Mix&Slice 算法的安全性, 并修改Mix&Slice 算法的初始向量裝載方式以確保達到原文[1]提出的安全強度. 實驗驗證改進后的Mix&Slice 算法的效率與原算法相近.同時發現結合懶惰撤銷策略, Mix&Slice 算法在一般訪問控制規則下具有更優的效率.

本文的結構如下: 第2 節給出Mix&Slice 算法的具體描述, 第3 節分析算法的安全漏洞和安全評估存在的問題, 第4 節給出算法改進, 并實驗驗證改進后的效率, 第5 節總結.

2 算法描述

2.1 定義與標記

Mix&Slice 算法的描述分為兩個相對獨立的部分:混合操作與切分操作.操作基于不同長度的塊,其標記與定義如下.

2.1.1 分塊、小分塊與大分塊

· 分塊(block): 分組密碼算法的輸入. 長度記為bsize.

· 小分塊(mini-block): 特定長度的比特串, 小分塊包含于分塊中, 是Mix&Slice 算法的基本操作單元(即操作至少針對一個小分塊). 長度記為msize.

· 大分塊 (macro-block): 一系列分塊的組合, 對大分塊進行操作擴展了分組密碼算法的應用,Mix&Slice 算法在大分塊上進行混合, 把對單個分組的保護擴展到對整個大分塊. 長度記為Msize.

· 分塊、小分塊、大分塊長度的關系: 分塊的長度是小分塊長度的倍數; 大分塊的長度是小分塊長度的倍數, 倍值為分塊中小分塊數量(分塊和小分塊長度的比率) 的冪次.

例1 以AES-128 為例, 分塊長度為128 比特, 設置小分塊長度為32 比特, 則每個分塊包含4 個小分塊, 那么大分塊的長度應該為32·4x,x取任意值.

2.1.2 標記

·bj[i] 表示分塊bj中的第i個小分塊.

·Mj[i] 表示大分塊Mj中的第i個分塊.

· [i] 表示分塊或者大分塊中的第i個小分塊, [[j]] 表示第j個分塊.

· 在加密過程中, 分塊或者小分塊的下標表示生成它的輪數.

·M表示分塊中小分塊的個數.

·a||b表示比特串a、b的級聯.

2.2 混合操作

混合操作是幾輪并行迭代加密的統稱, 基礎操作是分組加密算法E,E輸入的長度為一個分塊. 對分塊使用AES 等算法加密可起到分塊內比特充分混淆的效果, 即輸出分塊包含的任意一個小分塊都依賴于輸入分塊包含的全部小分塊.

對一個大分塊(包含b=mx-1個分塊) 的混合需要x輪, 每輪并行b次加密運算E. 將第i輪的輸入劃分為mx-i個span, 每個span 中包含mi個小分塊(spana[b] 表示第a個span 中的第b個小分塊,0≤a ＜mx-i, 0≤b ＜mi), 如果bmodb′= distance, distance =mi-1, 則將spana[b] 與spana[b′] 劃分到當前輪的同一個輸入分塊. 準確地說, 依次取span 中間隔distance 的m個小分塊組合為一個分塊作為運算E的輸入, 即spana[c+distance·0]||spana[c+distance·1]||···||spana[c+distance·(m-1)] 為加密運算E的輸入(0≤c ＜mi). 每輪結束時,單個span 內的所有小分塊進行了充分的混合,即span 的每個小分塊依賴于初始輪對應span 的全部小分塊. 算法1 為混合操作的運算過程, 圖1 給出了對含有16個小分塊,m=4 的大分塊進行混合的示例.

算法1 對大分塊M 的混合算法Mix(M)Input: M,m Output: Mix(M)1 for i := 1,2,··· ,x do/* x 表示輪數*/5令所有滿足條件的小分塊[l] 組合成一個分塊;2span := mi;/* 當前輪混合的小分塊個數*/3distance := mi-1;/* 混合算法加密的跨度*/4for j := 0,1,··· ,b-1 do/* j 代表一次混合算法中的加密運算*//* 下述迭代識別作為第j 次加密輸入的*//* 在每個span 內相距distance 的小分塊*/6其中, (l mod distance) = j 且(j ·m) div span = l div span;[[j]]i := E(k,block);/* 將結果寫回到第j 個分塊*/8endfor 9 endfor 7

為了保證每輪混合操作的可操作性(每輪span 的大小保證成m倍增長), 算法要求大分塊長度是小分塊長度的冪次倍, 即要求例1 中大分塊包含4x個小分塊(分塊包含4x-1個小分塊). 在大分塊長度不滿足條件時, 可以用常見算法進行填充.

圖1 混合16 個小分塊, m=4 的示例圖[1]Figure 1 Mixing of 16 mini-blocks assuming m=4 [1]

在每次迭代中使用AES 算法的情形下, logm(m·b) 輪可以實現對一個大分塊的全部混合. 值得注意的是, 混合操作的一種解釋是它將常規分組密碼對一個分組的輸入輸出之間的加密保護擴展到對任意長度的分組的加密保護. 另外一種替代的方法是使用Feistel 結構, 它使用類似于Feistel 結構中的輪函數作為分組密碼算法. 這種方法可以迭代使用, 每輪分組長度加倍. 分析表明, 這種方法的效率低于使用AES 算法, 需要的基礎算法迭代輪數為2·logm(m·b). Feistel 結構可以用于小分塊長度大于已有的原始分組密碼分組長度的情況, 類似地可以使用其他基于大分組的分組加密體制來支撐較大的小分塊, 這樣同時可以降低輪數. 例如AESQ 利用4 個AES 分組, 可以作為512-分組算法.

當資源較大時, 將一個資源保存為一個大分塊是不推薦的, 可以將資源分為M個大分塊, 每個大分塊單獨混合. 為了保證取值相同的兩個大分塊的混合結果不同, 在混合開始前, 每個大分塊中的第一個分塊與隨機選擇的初始向量(IV) 異或. 后續大分塊的向量值為前一分塊的值加1, 如算法2 的第5、7 行.

算法2 對資源R 的Mix&Slice 算法Input: R, M Output: R 1 將R 切分為M 個大分塊M0,M1,··· ,MM-1;2 對最后一個大分塊MM-1 進行填充;3 IV:= 隨機選擇的初始向量值;4 for i := 0,1,··· ,M -1 do/* 對大分塊進行加密*/9 5Mi[[1]] := Mi[[1]]⊕IV ;/* 第一個分塊異或IV 值*/6Mix(Mi) ;/* 加密當前大分塊*/7IV := IV+1 ;/* 計算下一個大分塊的初始向量值*/8for j := 0,1,··· ,mx -1 do/* 切分*/Fj[i] = Mi[j];10endfor 11 endfor

2.3 切分操作

切分操作的目標是, 每個大分塊中的一個小分塊被一個片段(fragment) 包含, 沒有任何兩個片段包含同一個小分塊, 并且所有的小分塊都被片段包含. 為了便于管理, 切分操作將不同大分塊中位于同一位置的小分塊切分到同一個片段. 切分算法定義如下.

定義1(切分與片段). 令R表示資源M0,M1,··· ,MM-1, 表示其中(已經分別混合過) 的大分塊,每個大分塊包含(m·b)個小分塊.切分算法產生R的(m·b)個片段Fi=＜M0[i],M1[i],··· ,MM-1[i]＞,其中i=1,2,··· ,(m·b).

圖2 顯示資源的切分過程. 綜合混合操作和切分操作, 對資源R的Mix&Slice 見算法2.

圖2 從資源到片段[1]Figure 2 From resources to fragments [1]

2.4 權限管理

使用Mix&Slice 算法將數據授權給某用戶訪問, 只需要用戶能夠訪問所有的片段, 并且令用戶得到相關的加密密鑰. 當有用戶被撤銷權限時, 數據擁有者隨機下載某個片段, 對它重新加密之后上傳, 并以某種方式令仍有訪問權限的用戶得到該片段的新密鑰. 多次權限撤銷會消耗數量較多的片段加密密鑰, 使用密鑰復原技術(key regression)[10]可以簡化這部分密鑰的生成和分發.

圖3 是對片段進行重新加密的示例.

圖3 片段重新加密和替換示例[1]Figure 3 Fragments evolution [1]

k0,k1,k2,k3的生成可以使用密鑰復原技術. 密鑰復原基于RSA 算法, 數據擁有者通過種子狀態s0使用私鑰迭代解密生成一系列狀態s0,s1,··· ,su,對狀態進行哈希生成一系列對應的用于對稱加密的密鑰k0,k1,··· ,ku, 這樣被授權的用戶可以使用公鑰從ki(或者說對應的狀態si) 中迭代計算出kj(j ≤i). 用戶由于不持有數據擁有者的私鑰, 因而不能求取kz(z ＞i). 可以將最新的密鑰ki保存在數據描述中, 并對數據描述進行加密保護, 該加密使用與數據的acl 相關的密鑰(該密鑰只能被授權用戶持有).

授權用戶訪問數據時, 需要先下載數據描述, 解密得到最新的狀態sl, 通過狀態回溯之前片段加密使用的密鑰, 獲取所有的片段并解密得到使用k0加密的原始狀態. 然后用戶將片段中的小分塊還原到大分塊, 利用混合操作解密大分塊以恢復明文數據.

撤銷用戶訪問權限時, 數據擁有者生成一個新的狀態si, 由狀態得到密鑰ki, 對隨機選擇的一個片段解密并使用ki重新加密, 保存新加密的片段并將si更新到數據描述中, 更新時使用與新的acl 相關的密鑰加密(該密鑰只能被授權用戶持有). 具體的權限撤銷和訪問策略見算法3 和4.

算法3 對資源R 的權限撤銷Revoke Input: R Output: R 1 隨機選擇R 中的一個片段Fi ;/* 將要重寫的片段*/2 從服務器上下載Fc i;/* 存儲的當前版本的片段*/3 if c ＞0 then/* F0 i 在某次權限撤銷中已經被改寫了*/4求取密鑰kc ;/* 使用密鑰衍生算法求取kc */5F0 i := D(kc,Fc i) ;/* 得到片段的初始值*/6 end 7 判斷序列中最后一個使用的密鑰kl-1;8 生成新的密鑰kl;9 Fl i := E(kl,F0 l );10 上傳Fl i 覆蓋Fc i;/* 重寫當前版本*/11 用acl(R) 的密鑰加密sl;/* 限制只能被當前授權用戶訪問*/12 更新R 的描述;/* 添加新的sl */算法4 對資源R 的訪問Access Input: R Output: R 1 下載R 的描述和它全部的片段;2 得到最后一次加密使用的種子sl;3 計算密鑰k0,k1,··· ,kl;4 for 每個下載的片段Fx i do 5if x ＞0 then i := D(kx,Fx i ) ;/* 還原片段的原始值*/7end 8for j = 0,1,··· ,M -1 do/* 重組并解密大分塊*/6 F0 9 Mj := 小分塊F0 i [j] 的串聯，i = 0,1,··· ,(m·b)-1;10解密Mj 11endfor 12 endfor

2.5 安全性評估

理想情況下被撤銷權限的用戶至少不能解密一個片段的數據, 為了恢復一個大分塊攻擊者需要窮舉2msize次, 若被撤銷權限之后有fmiss個片段被改寫, 那么攻擊需要窮舉2msize·fmiss次.

Mix&Slice 算法的設計初衷在于避免大規模數據的上傳下載, 其安全性假設是如果攻擊者恢復明文時需要下載和保存大量的數據, 那么這種攻擊是無效的. 由于被撤銷權限的用戶仍然能夠獲取后續的密文,并且可以利用已獲得的密鑰對密文解密, 這導致一定的不安全性. 主要的安全威脅是某些用戶在被撤銷權限之前從服務器下載并保存了部分數據.

如果用戶保存的片段恰好是他被撤銷權限之后重新加密的片段, 那么該用戶依然可以對所有的片段進行解密. 數據擁有者對重新加密的片段的選擇是隨機的, 對保存一個片段上述情況出現的概率是1/f. 假設某用戶本地保存了floc個片段, 假設在他攻擊時已經有fmiss個片段被改寫, 這時該用戶依然能夠恢復明文的概率PA=(floc/f)fmiss.

3 需要改進的問題

Mix&Slice 算法的設計初衷在于避免大規模數據的上傳下載, 作者推薦將較大的資源切分為多個大分塊, 并在最后一個大分塊進行填充. 這里需要注意的是, 在許多資源規模小于大分塊規模的情形下, 將多個資源組合為一個大分塊進行Mix&Slice 的開銷遠小于將每個資源填充為一個大分塊, 這也更符合實際場景, 例如網絡音視頻等各種應用產生的海量小文件的存儲. 這意味著Mix&Slice 算法使用對稱密碼算法實現的是對密文的訪問控制, 即資源R是原始明文數據經密鑰加密后的密文. 如若不然, 假設兩個用戶A和B分別對隸屬于同一個大分塊內的兩部分資源R1和R2擁有訪問權限, 且R1和R2直接存儲明文, 那么用戶A(B) 訪問R1(R2) 時, 可以直接獲得R2(R1) 的內容.

Mix&Slice 算法保護資源R時使用的密鑰為ki(i ≥0), 其中k0是混合操作使用的密鑰,ki是用戶權限被撤銷之后, 對隨機選擇的切分片段重新加密使用的密鑰. 記資源R在Mix&Slice 操作之前使用的基礎加密算法(一般為分組密碼的加密模式) 為Ex,Ex的輸入為原始明文P, 輸出為Mix&Slice 操作的輸入M.Ex的選擇影響Mix&Slice 算法安全性, 需要改進Mix&Slice 算法初始向量的裝載. 具體分析如下.

3.1 初始向量的裝載

在混合開始前, Mix&Slice 算法使用隨機初始向量異或每個大分塊中的第一個分塊, 以保證取值相同的兩個大分塊的混合結果不同, 但在大部分情況下仍不能保證大分塊的安全性, 原因如下. 假設兩個大分塊為M0,M1, 經過混合操作之后得到的結果為MS_Encrypt(M0) 和MS_Encrypt(M1), 混合使用的向量為IV0, IV1. 在已有混合操作模式下, 若MS_Encrypt(M0)=MS_Encrypt(M1), 則通過同樣的k0解密之后得到的值為M0⊕IV0和M1⊕IV1, 由于向量IV 只異或在大分塊的第一個分塊中, 則大分塊剩余的分塊取值相同M0/M0[[1]]=M1/M1[1]. 由于大分塊不是原始明文加密的基本單元, 則當原始明文加密的基本單元小于大分塊規模, 所選Ex算法不能保證第一個分塊的信息擴散到其他分塊, 且原始明文數據的長度超過一個大分塊時,M0和M1相應的分塊解密得到的明文完全相同. 常見的EX算法包括分組密碼算法的ECB、CBC、CFB、OFB、CTR 模式[11], 針對磁盤加密的保長的可調分組密碼包括小分組可調加密方案XTS[12]和大分組可調加密方案EME[13]等.

(1) 常見的加密模式(見圖4)

· ECB 模式: 同樣的密文對應同樣的明文;

· CBC 模式: 除M1(P1) 和P2之外, 后續密文Mi,Mi+1對應同樣的明文Pi+1(i ≥2);

· CFB 模式: 自Mi,Mi+1后, 密文對應同樣的明文Pi+2,i取值與l和s有關;

· OFB 模式: 密文與明文的對應關系與OFB 模式加密本身的IV 相關, 在IV 相同的情形下, 同樣的Mi對應同樣的Pi, 否則不存在一定相等的關系;

· CTR 模式: 密文分塊之間互不相關, 密文與明文的對應關系與計數器T相關, 存在同樣的Mi對應同樣的Pi的概率.

以上常見的分組密碼加密模式作為Mix&Slice 操作之前的基礎加密算法Ex時, Mix&Slice 已有的初始向量裝載方式不能保證大分塊的安全性.

(2) XTS 模式

XTS 能滿足磁盤加密存儲的要求, 屬于可調密碼. 在XTS 中, tweak value 通常是數據單元所在位置,不需要額外的空間存儲tweak value. 具體過程參見算法5、算法6, 使用的標記有:

· Key: 256-bit 密鑰, 被等分為兩個AES 密鑰Key=Key1||Key2;

·P: 128-bit 明文;

·i: 128-bit tweak value;

·j: 當前128-bit 分組在數據單元內部的序號;

·M: 128-bit 密文.

圖4 分組密碼的加密模式Figure 4 Encryption modes of block ciphers

算法5 128-bit 分組的XTS 加密M ←XTS-AES-128Enc(Key,P,i,j)Input: Key, P, i, j Output: M 1 T ←AES(Key2,i)×αj ;/* 由Tweakvalue 生成T, α 為域上元素*/2 PP ←P ⊕T ;/* 明文異或T 生成PP */3 MM ←AES(Key1,PP) ;/* 加密*/4 M ←MM ⊕T ;/* 加密后異或T 生成密文M */算法6 數據單元的XTS 加密M:=XTS-AES-Enc(Key, P, i)Input: Key, P, i Output: M 1 將明文按128 bit 劃分P = P0|P1|···|Pm 為0–127 bit;2 for q = 0,1,··· ,m-2 do/* 前m-2 塊直接加密*/3Mq:=XTS-AES-128Enc(Key, Pj, i, q);4 endfor 5 b := Pm 的比特長度;/* 后兩塊做填充后加密*/6 if b == 0 then 7Mm-1:=XTS-AES-128Enc(Key, Pm-1, i, m-1) ;8Mm:=empty;9 end 10 else 11MM:=XTS-AES-128Enc(Key, Pm-1, i, m-1);12Mm :=MM 的前b 比特;13MP:=MM 的后(128-b) 比特;14PP:=Pm|MP;15Mm-1:=XTS-AES-128Enc(Key, PP, i, m) ;16 end 17 M := M0|M1|···|Mm;

數據單元的XTS 加密類似CTR 模式, 除了最后兩個分塊之外, 密文分塊之間互不相關, 密文與明文的對應關系與tweak valuei以及數據存儲的位置j有關. Mix&Slice 算法已有的只在第一個分塊M0裝載初始向量的模式存在一定的概率使得混合結果相同的大分塊C回溯得到的原始明文P中的大部分分塊取值相同.

(3) EME 模式

磁盤通常被分成固定長度的扇區(一般是512 字節), XTS 模式是將512 字節分為長度相等的分塊(一般是16 字節) 進行加密的小分組可調加密方案. EME 模式是對512 字節直接加密的大分組可調加密方案. EME-32-AES 需要128 (192 或256) 比特的加密密鑰Key 和一個公開的128 比特的TweakT(T由扇區位置確定), 對512 字節的消息P=P1|P2|···|P32, EME-32-AES 的具體過程見算法7.

EME 模式并行使用AES 算法對512 字節進行加密, 且EME 模式密文第一個32 字節的信息可以通過m擴散到所有512 字節的明文, 因此Mix&Slice 已有的在第一個分塊添加初始向量IV 的方式, 可以保證其安全性.

3.2 權限撤銷的適用場景與優化

Mix&Slice 算法的設計初衷在于避免大規模數據的上傳下載, 因此其權限撤銷的安全性要求是被撤銷權限的用戶不能通過之前下載的片段恢復某些資源. 這強于一般的訪問權限管理[14]. 在一般系統的訪問控制中, 取得訪問權限的用戶一經授權即可以下載全部授權的數據, 這意味著已有數據并不對剛撤權用戶保密. 按照文獻[1] 的有效性分析, Mix&Slice 抵抗的攻擊是如果用戶保存的片段恰好是他被撤銷權限之后重新加密的片段, 那么該用戶依然可以對所有的片段進行解密. 但是這種情形下, 撤權用戶得到的資源并沒有超出一般訪問權限規則下其之前被授權的范圍. 基于上述討論, 可以使用一般訪問權限規則提高Mix&Slice 算法權限撤銷的效率.

算法7 EME-32-AES-Enc(Key, P, T)Input: Key, P, T Output: M 1 將明文按128 bit 劃分為P = P1|P2|···|P32 ;2 L := 2EKey(0128);3 for j = 1,2,··· ,32 do 4PPj := Pj ⊕(2j-1L);5PPPj := AESKey(PPj);6 endfor 7 sP:=PPP1 ⊕PPP2 ⊕···⊕PPP32;8 mP:=PPP1 ⊕sP ⊕T;9 mM:=AESKey(mP);10 m:=mP ⊕mM;11 for j = 2,3,··· ,32 do 12MMMj := PPPj ⊕(2j-1m);13 endfor 14 sM:=MMM2 ⊕MMM3 ⊕···⊕MMM32;15 MMM1 := mM ⊕sM ⊕T;16 for j = 1,2,··· ,32 do 17MMj := AESKey(MMMj);18Mj := MMj ⊕2j-1L;19 endfor 20 M := M1|M2|···|M32;

4 改進的Mix&Slice 算法

4.1 初始向量的裝載

對XTS 模式以及常見的分組密碼加密模式, 在資源R存儲的是明文P加密之后的數據M的前提下, 為了避免相同的密文C解密之后得到近似的M和P, 可以改進IV 的裝載, 在混合操作初始化的每個分塊都異或IV 值(改進一), 或者在混合操作的每一層的第一個分塊都異或IV 值(改進二). 改進一更新MS_Encrypt 算法(算法8), 改進二更新Mix(M) 算法(算法9) 和MS_Encrypt 算法(算法10).

根據改進一, 當兩個大分塊為M0,M1, Mix&Slice 后的輸出為MS_Encrypt_Improve1(M0) 和MS_Encrypt_Improve1(M1) 且MS_Encrypt_Improve1(M0)=MS_Encrypt_Improve1(M1) 時, 通過同樣的k0解密之后得到的值為M0⊕IV0和M1⊕IV1. 由于向量IV 異或在每一個分塊中, 則當IV0/= IV1時,M0和M1每個分塊取值都不相同. 由于使用了基礎加密算法Ex, 此時M0,M1解密之后得到的P0和P1差異很大. 即改進后Mix&Slice 輸出相同的兩個分塊, 對應的明文P0,P1沒有相似性.

算法8 Mix&Slice 算法改進一MS_Encrypt_Improve1 Input: R, M Output: R 1 將R 切分為M 個大分塊M0,M1,··· ,MM-1;2 對最后一個大分塊MM-1 進行填充;3 IV:= 隨機選擇的初始向量值;4 for i := 0,1,··· ,M -1 do/* 對大分塊進行加密*/5for l := 0,1,··· ,mx -1 do Mi[[l]] := Mi[[l]]⊕IV ;/* 所有分塊都異或IV 值*/7endfor 8Mix(Mi) ;/* 加密當前大分塊*/9IV := IV+1 ;/* 計算下一個大分塊的初始向量值*/10for j := 0,1,··· ,mx -1 do/* 切分*/6 11Fj[i] = Mi[j];12endfor 13 endfor

算法9 Mix&Slice 算法改進二_Mix(M, IV)_Improve Input: M, m Output: Mix(M)1 for i := 1,2,··· ,x do/* x 表示輪數*/2span := mi;/* 當前輪混合的小分塊個數*/3distance := mi-1;/* 混合算法加密的跨度*/4for j := 0,1,··· ,b-1 do/* j 代表一次混合算法中的加密運算*//* 下述迭代識別作為第j 次加密輸入的*//* 在每個span 內相距distance 的小分塊*/5令所有滿足條件的小分塊[l] 組合成一個分塊;6其中, (l mod distance) = j 且(j ·m) div span = l div span;7 if j == 0 then 8[[j]]i := E(k,block ⊕IV);/* 每輪的第一個分塊異或IV 后再加密*/end 10else 9 11[[j]]i := E(k,block);/* 將結果寫回到第j 個分塊*/12end 13endfor 14 endfor算法10 Mix&Slice 算法改進二MS_Encrypt_Improve2 Input: R, M Output: R 1 將R 切分為M 個大分塊M0,M1,··· ,MM-1;2 對最后一個大分塊MM-1 進行填充;3 IV:= 隨機選擇的初始向量值;4 for i := 0,1,··· ,M -1 do/* 對大分塊進行加密*/5Mix(Mi,IV)_Improve ;/* 加密當前大分塊*/6IV := IV+1 ;/* 計算下一個大分塊的初始向量值*/7for j := 0,1,··· ,mx -1 do/* 切分*/Fj[i] = Mi[j];9endfor 10 endfor 8

根據改進二, 在IV0/= IV1時, 每一層的Mix 操作使得輸入的差分很難在輸出中體現, 則當Mix 操作超過兩層時, 同樣的輸出MS_Encrypt_Improve2(M0) 和MS_Encrypt_Improve2(M1), 對應的輸入M0和M1沒有相似性.

我們通過實驗對比兩種改進和原算法的Mix&Slice 效率. 實驗結果如圖5. 實驗驗證這兩種改進對Mix&Slice 算法的效率的影響可以忽略. 實驗選擇的小分塊、分塊、大分塊規模為32 比特、128 比特和1024 字節,E算法為AES-128. 實驗平臺為Intel(R) Core(TM) i7-3770 CPU 3.40 GHz (內存4 GB).

圖5 Mix&Slice 與改進實驗驗證Figure 5 Experimental verification of Mix&Slice and its improvement

4.2 懶惰撤銷機制

結合懶惰撤銷機制[15], 可以在一般訪問權限規則下提升Mix&Slice 算法的有效性和效率. 當某個用戶的權限被撤銷時, 并不對切分重新加密, 直到資源的某一部分被更新. 當資源R被更新之后, 使用k0重新對R進行混合切分, 再隨機選擇某個slice 使用新密鑰ki加密, 并將ki添加到當前擁有訪問權限的用戶的acl 中, 如算法11. 在用戶權限較多且資源更新較少的情況下, 懶惰撤銷機制是一種平凡的可以節省開銷的優化訪問控制效率的方法. 圖6 給出了在權限撤銷頻率超過資源更新頻率50%、100%、200% 的情形下, 結合懶惰撤銷機制改進后兩種Mix&Slice 算法的效率(與原算法的對比).

算法11 權限撤銷的改進Revoke_improve Input: R Output: R 1 等待直到R 中的內容被修改;2 Acess(R);/* 解密當前資源R */3 解密更新數據后加密生成新的密文資源R′;4 MS_Encrypt_Improve1/2(R′);/* 混合更新后的資源R′ */5 隨機選擇R 中的一個片段Fi ;/* 選擇將要重寫的片段*/6 從服務器上下載Fc i;/* 存儲當前版本的片段*/7 判斷序列中最后一個使用的密鑰kl-1;8 生成新的密鑰kl;9 Fl i := E(kl,F0 l );10 上傳Fl i 覆蓋Fc i;/* 重寫當前版本*/11 用acl(R) 的密鑰加密sl;/* 限制只能被當前授權用戶訪問*/12 更新R 的描述;/* 添加新的sl */

圖6 結合懶惰撤銷機制后兩種改進的效率(與原Mix&Slice 算法對比)Figure 6 Efficiencies of two improvements under lazy-revocation (compared with original Mix&Slice)

5 總結

文獻[1] 提出了一種基于對稱密碼的Mix&Slice 算法, 用于解決云端加密數據高效的權限撤銷問題,主要思路是在密文的每一比特充分混淆的基礎上, 對密文的一小部分比特重新加密. 本文分析了算法的應用場景, 改進了算法的初始化向量裝載方式以提高算法安全性. 實驗驗證在提高安全強度的同時, 改進沒有帶來效率損失. 另外, 針對一般的訪問控制規則, 提出懶惰撤銷機制可以作為優化算法效率的一種途徑.