改進(jìn)的Mix&Slice 算法: 對稱密碼在云存儲的應(yīng)用*

杜少宇, 鄧辰辰, 矯 琳

1. 密碼科學(xué)技術(shù)國家重點實驗室, 北京 100878

2. 清華大學(xué)北京信息科學(xué)與技術(shù)國家研究中心, 北京 100084

1 簡介

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

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

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

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

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

2 算法描述

2.1 定義與標(biāo)記

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

2.1.1 分塊、小分塊與大分塊

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

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

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

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

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

2.1.2 標(biāo)記

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

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

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

· 在加密過程中, 分塊或者小分塊的下標(biāo)表示生成它的輪數(shù).

·M表示分塊中小分塊的個數(shù).

·a||b表示比特串a(chǎn)、b的級聯(lián).

2.2 混合操作

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

對一個大分塊(包含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′] 劃分到當(dāng)前輪的同一個輸入分塊. 準(zhǔn)確地說, 依次取span 中間隔distance 的m個小分塊組合為一個分塊作為運算E的輸入, 即spana[c+distance·0]||spana[c+distance·1]||···||spana[c+distance·(m-1)] 為加密運算E的輸入(0≤c ＜mi). 每輪結(jié)束時,單個span 內(nèi)的所有小分塊進(jìn)行了充分的混合,即span 的每個小分塊依賴于初始輪對應(yīng)span 的全部小分塊. 算法1 為混合操作的運算過程, 圖1 給出了對含有16個小分塊,m=4 的大分塊進(jìn)行混合的示例.

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

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

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

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

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

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

2.3 切分操作

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

定義1(切分與片段). 令R表示資源M0,M1,··· ,MM-1, 表示其中(已經(jīng)分別混合過) 的大分塊,每個大分塊包含(m·b)個小分塊.切分算法產(chǎn)生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 權(quán)限管理

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

圖3 是對片段進(jìn)行重新加密的示例.

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

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

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

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

算法3 對資源R 的權(quán)限撤銷Revoke Input: R Output: R 1 隨機(jī)選擇R 中的一個片段Fi ;/* 將要重寫的片段*/2 從服務(wù)器上下載Fc i;/* 存儲的當(dāng)前版本的片段*/3 if c ＞0 then/* F0 i 在某次權(quán)限撤銷中已經(jīng)被改寫了*/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;/* 重寫當(dāng)前版本*/11 用acl(R) 的密鑰加密sl;/* 限制只能被當(dāng)前授權(quán)用戶訪問*/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] 的串聯(lián)，i = 0,1,··· ,(m·b)-1;10解密Mj 11endfor 12 endfor

2.5 安全性評估

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

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

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

3 需要改進(jìn)的問題

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

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

3.1 初始向量的裝載

在混合開始前, Mix&Slice 算法使用隨機(jī)初始向量異或每個大分塊中的第一個分塊, 以保證取值相同的兩個大分塊的混合結(jié)果不同, 但在大部分情況下仍不能保證大分塊的安全性, 原因如下. 假設(shè)兩個大分塊為M0,M1, 經(jīng)過混合操作之后得到的結(jié)果為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]. 由于大分塊不是原始明文加密的基本單元, 則當(dāng)原始明文加密的基本單元小于大分塊規(guī)模, 所選Ex算法不能保證第一個分塊的信息擴(kuò)散到其他分塊, 且原始明文數(shù)據(jù)的長度超過一個大分塊時,M0和M1相應(yīng)的分塊解密得到的明文完全相同. 常見的EX算法包括分組密碼算法的ECB、CBC、CFB、OFB、CTR 模式[11], 針對磁盤加密的保長的可調(diào)分組密碼包括小分組可調(diào)加密方案XTS[12]和大分組可調(diào)加密方案EME[13]等.

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

· ECB 模式: 同樣的密文對應(yīng)同樣的明文;

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

· CFB 模式: 自Mi,Mi+1后, 密文對應(yīng)同樣的明文Pi+2,i取值與l和s有關(guān);

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

· CTR 模式: 密文分塊之間互不相關(guān), 密文與明文的對應(yīng)關(guān)系與計數(shù)器T相關(guān), 存在同樣的Mi對應(yīng)同樣的Pi的概率.

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

(2) XTS 模式

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

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

·P: 128-bit 明文;

·i: 128-bit tweak value;

·j: 當(dāng)前128-bit 分組在數(shù)據(jù)單元內(nèi)部的序號;

·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 數(shù)據(jù)單元的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;

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

(3) EME 模式

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

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

3.2 權(quán)限撤銷的適用場景與優(yōu)化

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

算法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 改進(jìn)的Mix&Slice 算法

4.1 初始向量的裝載

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

根據(jù)改進(jìn)一, 當(dāng)兩個大分塊為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 異或在每一個分塊中, 則當(dāng)IV0/= IV1時,M0和M1每個分塊取值都不相同. 由于使用了基礎(chǔ)加密算法Ex, 此時M0,M1解密之后得到的P0和P1差異很大. 即改進(jìn)后Mix&Slice 輸出相同的兩個分塊, 對應(yīng)的明文P0,P1沒有相似性.

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

算法9 Mix&Slice 算法改進(jìn)二_Mix(M, IV)_Improve Input: M, m Output: Mix(M)1 for i := 1,2,··· ,x do/* x 表示輪數(shù)*/2span := mi;/* 當(dāng)前輪混合的小分塊個數(shù)*/3distance := mi-1;/* 混合算法加密的跨度*/4for j := 0,1,··· ,b-1 do/* j 代表一次混合算法中的加密運算*//* 下述迭代識別作為第j 次加密輸入的*//* 在每個span 內(nèi)相距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);/* 將結(jié)果寫回到第j 個分塊*/12end 13endfor 14 endfor算法10 Mix&Slice 算法改進(jìn)二MS_Encrypt_Improve2 Input: R, M Output: R 1 將R 切分為M 個大分塊M0,M1,··· ,MM-1;2 對最后一個大分塊MM-1 進(jìn)行填充;3 IV:= 隨機(jī)選擇的初始向量值;4 for i := 0,1,··· ,M -1 do/* 對大分塊進(jìn)行加密*/5Mix(Mi,IV)_Improve ;/* 加密當(dāng)前大分塊*/6IV := IV+1 ;/* 計算下一個大分塊的初始向量值*/7for j := 0,1,··· ,mx -1 do/* 切分*/Fj[i] = Mi[j];9endfor 10 endfor 8

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

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

圖5 Mix&Slice 與改進(jìn)實驗驗證Figure 5 Experimental verification of Mix&Slice and its improvement

4.2 懶惰撤銷機(jī)制

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

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

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

5 總結(jié)

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