杜少宇, 鄧辰辰, 矯 琳

1. 密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100878

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

1 簡(jiǎn)介

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

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

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

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

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

2 算法描述

2.1 定義與標(biāo)記

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

2.1.1 分塊、小分塊與大分塊

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

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

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

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

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

2.1.2 標(biāo)記

·bj[i] 表示分塊bj中的第i個(gè)小分塊.

·Mj[i] 表示大分塊Mj中的第i個(gè)分塊.

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

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

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

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

2.2 混合操作

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

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

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

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

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

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

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

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

2.3 切分操作

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

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

圖2 顯示資源的切分過程. 綜合混合操作和切分操作, 對(duì)資源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í), 數(shù)據(jù)擁有者隨機(jī)下載某個(gè)片段, 對(duì)它重新加密之后上傳, 并以某種方式令仍有訪問權(quán)限的用戶得到該片段的新密鑰. 多次權(quán)限撤銷會(huì)消耗數(shù)量較多的片段加密密鑰, 使用密鑰復(fù)原技術(shù)(key regression)[10]可以簡(jiǎn)化這部分密鑰的生成和分發(fā).

圖3 是對(duì)片段進(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,對(duì)狀態(tài)進(jìn)行哈希生成一系列對(duì)應(yīng)的用于對(duì)稱加密的密鑰k0,k1,··· ,ku, 這樣被授權(quán)的用戶可以使用公鑰從ki(或者說(shuō)對(duì)應(yīng)的狀態(tài)si) 中迭代計(jì)算出kj(j ≤i). 用戶由于不持有數(shù)據(jù)擁有者的私鑰, 因而不能求取kz(z ＞i). 可以將最新的密鑰ki保存在數(shù)據(jù)描述中, 并對(duì)數(shù)據(jù)描述進(jìn)行加密保護(hù), 該加密使用與數(shù)據(jù)的acl 相關(guān)的密鑰(該密鑰只能被授權(quán)用戶持有).

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

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

算法3 對(duì)資源R 的權(quán)限撤銷Revoke Input: R Output: R 1 隨機(jī)選擇R 中的一個(gè)片段Fi ;/* 將要重寫的片段*/2 從服務(wù)器上下載Fc i;/* 存儲(chǔ)的當(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 判斷序列中最后一個(gè)使用的密鑰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 對(duì)資源R 的訪問Access Input: R Output: R 1 下載R 的描述和它全部的片段;2 得到最后一次加密使用的種子sl;3 計(jì)算密鑰k0,k1,··· ,kl;4 for 每個(gè)下載的片段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 安全性評(píng)估

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

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

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

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

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

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

3.1 初始向量的裝載

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

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

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

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

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

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

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

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

(2) XTS 模式

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

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

·P: 128-bit 明文;

·i: 128-bit tweak value;

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

·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 的比特長(zhǎng)度;/* 后兩塊做填充后加密*/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 模式, 除了最后兩個(gè)分塊之外, 密文分塊之間互不相關(guān), 密文與明文的對(duì)應(yīng)關(guān)系與tweak valuei以及數(shù)據(jù)存儲(chǔ)的位置j有關(guān). Mix&Slice 算法已有的只在第一個(gè)分塊M0裝載初始向量的模式存在一定的概率使得混合結(jié)果相同的大分塊C回溯得到的原始明文P中的大部分分塊取值相同.

(3) EME 模式

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

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

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

Mix&Slice 算法的設(shè)計(jì)初衷在于避免大規(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ù)并不對(duì)剛撤權(quán)用戶保密. 按照文獻(xiàn)[1] 的有效性分析, Mix&Slice 抵抗的攻擊是如果用戶保存的片段恰好是他被撤銷權(quán)限之后重新加密的片段, 那么該用戶依然可以對(duì)所有的片段進(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 初始向量的裝載

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

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

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

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

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

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

4.2 懶惰撤銷機(jī)制

結(jié)合懶惰撤銷機(jī)制[15], 可以在一般訪問權(quán)限規(guī)則下提升Mix&Slice 算法的有效性和效率. 當(dāng)某個(gè)用戶的權(quán)限被撤銷時(shí), 并不對(duì)切分重新加密, 直到資源的某一部分被更新. 當(dāng)資源R被更新之后, 使用k0重新對(duì)R進(jìn)行混合切分, 再隨機(jī)選擇某個(gè)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 算法的效率(與原算法的對(duì)比).

算法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 中的一個(gè)片段Fi ;/* 選擇將要重寫的片段*/6 從服務(wù)器上下載Fc i;/* 存儲(chǔ)當(dāng)前版本的片段*/7 判斷序列中最后一個(gè)使用的密鑰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 算法對(duì)比)Figure 6 Efficiencies of two improvements under lazy-revocation (compared with original Mix&Slice)

5 總結(jié)

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