闪存数据应急销毁算法的研究与设计

1、第3 0卷第9期2 0 13年9月c o m p u t rapplcatonsa ndsofwarvo 1 3 0 no. 9sep. 2 0 13闪存数据应急销毁算法的研究与设计郑光苏锦海孙万忠(信息工程大学 河南 郑州450004)摘要首先阐述了闪存数据应急销毁的研究现状，介绍零覆写、块删除和加密三种闪存数据销毁技术及sun算法和l e e算法两种闪存数据销毁算法，并分析它们的优缺点。在此基础上，设计一个更为安全的闪存数据应急销毁算法，并评估其性能。关键词闪存数抑;应急销毁算法零覆写块删除加密技术中图分类号 t p 3文献标识码 ad o i 1 0 . 3 9 6 9 /. i s .

2、 1 0 0 0 8 6 x . 2 013. 0 9 . 0 8 4research and d e s i n of emergency data s an i i a t i nalgor i hm for flash memoryzhengguang s u j n h a i sunwanzong(1 f ra t oneng i e rngun i e s t, zhegzou450004, h e a n , chia)a b s r a c t wefrtexpoundtesatsofrsarhi emerencydat sniiatonfrfas memores andten

3、itoducetrefas da tsni iatontchniuesicldigtezr o v e r r t n g blckdeltonandencrpton, a s w ei a s t o f a s d a t sni iatonalortmsofsun alortm andleealortm, teiadvantgesanddiadvantgesar a n a j s d a s w e 1.0 n t i b a $ $ weprsnttedesgnofamor s c u r emerencydat sniiatonalortm frfas memor atls,wee

4、valat i sperorance.keywords emerencydat sniiatonalortm frfas memor z e r v e r r t n g b1 c k d e 1 ton encrptontchnolg y感信息后向其中覆写一定次数的随机数可以降低敏感信息被恢 复的概率。001 言本文首先阐述了设计应急销毁算法的研究背景，然后介绍了主要的闪存数据销毁技术和算法，并详细描述了闪存数据应闪存分为nand型和nor型两种，前者具有高存储密度、急销毁算法，后评估其性能，最后总结。更高的写速度和较低的成本，在数据存储方面广为应用，本文所指的闪存均是nand型闪存。闪存

5、在信息存储领域逐渐受到亲睞，尤其是在敬感信息和机密信息存储方面，更有着极人的应用空间。闪存具有一些不同于磁性存储介质的存储特性，主要方：利用浮栅门器件原理实现数据存取；按页读写数据，按块擦除数据；写前擦除，对同一页的重写，必须要先擦除：擦除次数有46近年来随着针对闪存攻击技术的不断发展，闪存也面临了越來越严峻的安全威胁。而针对闪存数据销毁的研究述不是十分地深入。文献1 从概率论的角度，证明了通过覆写能够达到安全销毁数据的目的。文献3对目而的主流销毁工具对闪存的销毁效果做了一组测试，得出少数能销毁闪存数据，但没何得到正确使川；务数销毁匚具不能贞正销毁闪存，甚至在执行完销毁命令后，元数据完好无损地

6、存储在闪存中。文献2 , 6分析了闪存数据残留的危险和威胁，并给出r建议：在闪存存储敏1 应黛销毁算決的设计1 . 1主要的闪存逻辑销毁技术1）零覆写技术零覆写技术是通过对指定的页进行全零覆写，达到安全删 除的目的。它的基本流程如图1所示。零覆写的优点是灵活性 好，块中要删除的页占少数时，以页为删除颗粒可以降低数据销 毁需要的时间。但是缺点是当块中要销毁的页校多时，频繁的 零覆写会增加系统开销。图1零覆写2）块删除技术块删除技术是通过删除整块來实现安全删除的ii的。它的流程如图2所示。它的优点是删除单位犬，在大规模删除中占ihi o m iiv r i yn hnn收稿日期:2 0 12-08

7、-2 8 郑光，硕士生，主研领域:信息安全。苏锦海，履授。孙万忠,h t ue e c nga t z i1 hi ,hrh e i ha t z i eqn u n how i i ,oiy iw 1 ha t z ig i hg i hgi h h ry ch s i e hie ga t zi g i h o1 hya tu e t f mga t zi g i ho 1 hyoo w i ioiy i e限，-燉擦除次数为1 o1 o次。冇优势，能够减少系统开销。但是缺点是不够灵活。毁算沐年表1主流数据销毁标准图2块删除3）加密技术安全规范。l e e算法只执行一次擦除操作，也不满足任

8、 何安全规范。因此，s u n机制和l e e机制都不是严格意义上的安全 销加密技术对存储的数据进行加密，在闪存中存储密文的形 式來保护数据。需要删除数据时，只需要删除密钥就行，英流程 如图3所示。它的优点是删除的工作屋少，能节省大虽:时间，缺 点是密文仍然完整地存储在闪存中，一旦密钥彼攻破，会适成极 大的损失。图3加密技术1 . 2主要的闪存逻辑销毁算法分析文献7 中sun等人结合了響覆写和块擦除的优缺点， 提出了一种基于覆写的闪存逻辑销毁算法。它的基本描述如下：（1）搜索待删除页：（2）检查覆写待删除页的成木是否比擦除包含待删除页的块的成木低。如果覆写成本低于块擦除，那么就执行零覆写；（3

9、）否则，首先将待擦除块中有效页拷贝到其它块中，再对 目标块执行块擦除操作。文献8 中l e c等人提出了-种基于加密的闪存逻辑销毁 算法。它的数据测除基本过程描述如下：（1 ）搜索存储了待删除数据对应密钥的页；< 2 ）检査包含有待删除密钥的块是否还包含其他有 效密钥。如果包含，那么将这些密钥拷贝至其他块；（3 ）删除目标块。结合表1中的数据覆写标准，经过分析发现：s u n算法包含 两部分：零覆写和块擦除。然而，零覆写仅执行一次覆写，因此 只满足nsa/ss安全规范。而块擦除仅执行一次，不满足任何1 . 3应急销毁算法妙分析了上而三种技术的特点及主耍的闪存逻辑销毁算法 的缺点后，木文通

10、过结合三种数据销毁技术，提出了更为安全, 也更为高效的应急借毁算法。这一算法的基本思想是，以密文的形式存储敬感信息，在销 毁数据的时候，为彳m：c：ii:ii n0x000x000x1j0有效贝空页空页俏毁标准描述9d o d 5 2 2 (1 22 m sup 1 ( 1 9 9 5 )1:擦除所有数据2：用单个字符进行覆写3 :用单个字符的补值进行覆写4：用随机单个字符进行覆写5：检査是否需额外程序dod 5 2 2 0 2 2 m (灯7 )1 :用单个字符进行覆写2：対已覆写区域进行擦除nsa/css$toragedev i ce1 :用已知非密模板进行覆写2：用随机重读校验已覆写区

11、域mediaclearing, purging, anddes t i o n1 :擦除所有数据2：用伪随机值进行两次覆写3：用已知模板进行一次覆写4：检査是否需额外程序f e k i空页&安全的随机息i的加密 律鍬隗枣乖h i令推导eu （）:使用秘密密钥k和对称密码算法e进行加密i :初始化向最】）密钥的生成、存储和加密过程密钥的生成如下所示。（1）首先，使用随机数发生器rng （）生成feki：空页空页rng () o每个敏感信息都使用f e k i进行加密。每个敏感信息 的f e k i則捫症法，敏感（2 ）当被创建后，按下却仝3 a s e k e =1对用户口令进行多次哈希

12、可以防永礬力攻击。接f来使用m a s e k e般轉奁轉誓心（fek）。将加密后密文勺f e后赵卫行上述算m 口 令）。 飒据块头块头块头块图紅躍怎痛脇i程2）数据存储（1）在敏感信息被存储到闪存之前，必须用feki进行加密。采用分组密码对数据进行加密，即数据m = m 1 ii m 2 ii . iirng（i用户口令 beka mayerkcy存储刘头块"一 （fekj 头块mn0工作模式采用c bc模式。图5给出了数据加密过程。图5数据加密过程（2）加密密钥以密文形式彼存储在敏感信息头块中，密文 存储在数据块中。数据存储的整个过程如图6所示。图6数据存储过程3）安全销毁毎个f

13、eki占用一页，这些页彼存储在同一块中。新的算法既需要安全销毁敏感信息加密密钥，也需要销毁存储的密 文。除了对删除页进行覆写z外，新算法还要视零覆写与块删除的成本选择对待删除块的操作，从而满足表1中女种规范的闪存安全销毁标准。图7给出密钥的销毁过程，图8给出密文的销毀过程。安全销毁敏感信息的步骤如下：（1）搜索存储待删除敏感信息i的feki及敏感信息i所在 的块。（2 ）用随机数序列覆写待删除f e k i及敏感信息 i所在的页。（3）检查待删除块屮的有效页占总页数的比例，如果有效p故页占总页的比例满足 > 50%,则执行步骤（4）；如果小于5 0 %,则执行步骤（5 ）。（4 ）用随机

14、数的补码覆写删除页。（5 ）将有效页拷贝到新块中，擦除冃标块。2性能分析21安全性能分析安全性能方面，我们主耍考虑闪存数拯应急销毁算法是否 满足表1中的各个国家政府出台的闪存安全销毁标准，如果满 足，我们就能够认为它是安全的。根据表1中各国政府提供的安全销毁标准，我们发现，每一 个标准基本上都包含四种主要的步骤：（1 ） “擦除所有的数据”图8密文的删除过程图7密钥的删除过程(2 ) “用一个已知值覆写”(3 ) “覆写已知值的补码”(4 ) “覆写随机数”。表2是闪存数据应急销毁算法、s u n 算法和l e e算法比较的结果。根据表2屮的比对结果，闪存数据应急销毁算法符合现何 的四种主流闪

15、存数摇備毁标准，并且，碍合了三种主要的闪存、加 逻辑销毁技术，因此j它是安全的。j,j2 . 2 时间性能为了分析闪存数据应急销毁算法的时间性能，榊将它与其 他两种算法做-个比较，我们i首先做-些约定屯对一页的读时间孑谄即 对-块的擦除时间记为t i洌头块 包含有待删除页的块数：nblock;闪存包含4 0 9 6块，每一块包含匀地分布在每个块中，每一块中包含n个待删除页。sun算法用于覆写的时间可以记为：3 2號并且待删除页均t z e r o_o v e r w r i t e = ( fl x t w ) xn block用于擦除的时间记为：t b 1 0 c k_e rase = (3

16、2 i1)x(tr + t w ) + t e xn block 其中(3 2 n) x (tr +tw) xnb,"用于将块中的有效页复制到新3ct r ys u n算法lee算法应急销毁算法采用的步骤(1 ) (2)(1 )(1 ) (2) (3) (4 )采用的技术零覆写、块删除加密技术零覆写、块删除、加密技术满足的 安全规范nsa/csnsa/css、dod 5 2 2 0 2 2 m安全性低低高块中；te xnbiock用于擦除块。由于lee算法只需要擦除一次目标块，因此，它的时间开销 主要是将其它的有效页复制到新块中，因此l e e算法 时间 记为：tlcc = 3 1

17、x ( tr 4-tw) +te根据算法的描述，对指雄文件密钥的删除只需用随机数覆写一次，再用它的补码覆写一次，记为：temcrse ncy _ key = 2 x t w对密文的删徐，在有效页占到总页数的5 0%以上时， 应急销毁算法采用的是用随机数的补码覆耳待删除贝，那么用丁销毁密文的时间记为：temergency_ciphertexl_l = 2xflxtw xn block 其中n< 1 6.当有效页占到总页数的5 0%以下时，先采用的是用随机数 覆写待删除页，再将有效页复制到新块中，删除块。它的时间开 销记为：t emergency_c i phe rtext_2 = i) x

18、 t w xn b i o c k 4" ( 3 211) x(t w +tr) +te xn h i 0 c k 其中n > 1 6。根据文献1 4,假定 tr =3 0 u s, tw = 2 0 0 u s, te = 1 8 0 0 u s> )9 mata b编辑三者的时间开销分别如图(9) _图(1 1 )所示。年3结语本文首先分析了闪存数据应急销毀的研究现状，介绍了主 要的闪存销毁技术和算法,提出了闪存数据应急销毁算法,最后 对其性能进行了评估。参考文献从图中可以看出，l e c算法的时间开销最小，应急销毁算法 次之，时间开销最多的是s u n算法。图9 s

19、un算法的时间开销图1 0 lee算法的时间开销图11应急销毁篦法的时间开销1 ma rkkinows i mihalprykuckitomas slumisidatdellon w i h p r v a b i s e c u r t e b / l h t p： / / w w. srngerik. com 2 wutannp s e c u r del tonofdat fom magnetcandsold t tmemor c / /hesi t u s e n 1 s e c u r t symposum ( 1 9 9 6 )3 m i h a c 1w e i l a u r

20、m .grpprclablersngdatfrmfls a s ds o 1 d s t t drveseb/l h t p ： / / b usn i or.4 b r e u w s a m. d c j n g h m, k 1 v e r c» ctajfornscdat r c o v e r f om f a s m e m o r j. sm a 1s c a i diialdeviefornscsjural 2 0 0 7 , 1 ( 1 )：11 7 5 s u b h a s八nalorlm f r s e c u r d e 1 t o n i f 1 s me

21、mores eb/ ol h t p ： / /eeexpl r e e e or.6 sereiskorbogatv d a t remancncci f i s memor devics e b / ol h t p ： / / w w c i c a m. ac. uk7 s u n k, choijleed, e t a 1m o d ei and de sgnofanadaptvehybrd shemef rscur del tonofdat i consmerelctonis j.【ee trnsctonsonconsmerelctoni s200854100 104.8 leej

22、heojchoy, e t a i s e c u r deltonfrnandfas f 1 s s e m c/rceedigsofacm symposum onappledcomputng2008： 17 101 7 1 4 9 natonal idusralsccurt prgrm opertngmanualsupplmenteb/0l 995-02 h t p： / / ww. fsor/gp/irr/ipo m_s p pdf10 natona idusralsccurt prgrm opertngmanualeb/lht t : / / w w nls. gov/ea rh/rd

23、uctasx 11 nsa/ssstrgedeviedeclsi iatonmanualeb/l h t p： /www. ns. goy/a/fls/overmenl / dg/s a_cs s_s t r g e_d e v i e _d e c 1 s i a t o n_m a n u a 1 p d f12 4cdi c i a r n g p u r i g anddesrcton eb/l h t p ： / / w w orl gov/oe/oe_o r_dmg/mr/mrs/oe%2 0ci%20gu i ance%20cs13141 1 pdfbauetjspryanlan

24、b. seeur datdel tonfrliuxflssemsc/ pre*k i rgf r ce t0o ek ,czy0>7.wrpn k .ii1 nmjrii s aytx hxiycui y aio a h b e1a e0d cxgem0aeie y1hye g tcion,g i h o1a hiio eggahy c w9siii0e einur c eaa iur c ,91 h i e yp 0n111 ,digsofteusenl s e c u r t s y m o s u m(a u g ui j xl nohsh, ea ； a s a c e f i i n t f a $ tansj. ieetn$cton$onconsm e r e 1 cm s6 3 7 5 k iy h. iprf rnce asdsol tonselcton（上接第3 0 4页）1112k i j h, ha n