Kasumi算法FI函数的差分上界分析

Kasumi算法FI函数的差分上界 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 asum KiFI 2012-07-13#############2012-07-13#####2#0#1#2-07-13######## ，，孔凡杰李 磊韩文报 ( 450002)，信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 大学 信息工程学院河南 郑州 FI :。摘要差分分析是目前攻击分组密码十分有效的方法之一证明了 函数的平均差分概率上 ，FI : FI 。界值重点分析了 函数在各种变形下的平均差分概率上界结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明对于 函数这种结 2 )n ，S 2。构采用奇数维 盒可使得平均差分概率上界达到 :Kasumi ; ; ; 3GPP关键词算法差分分析平均差分概率 :TN918, 1:A) 0673( 2011) 02) 0129 ) 05:1671 中图分类号文献标识码文章编号 Differential Upper Bound on the FI Function of Kasumi Algorithm KONG Fan-jie，LI Lei，HAN Wen-bao ( nstitute of nformation Engineering，nformation Engineering University，Zhengzhou 450002，China) III Abstact: Differential cryptanalysis is an efficient method to attacklo ckb ciphers, The purposeof r this paperi s to give an upper bound to the averageiffere ndtial probability of FI functions, Moreover， it is showed that thereexis t functions such that the averageiffe rdential probabilities are less than or 2 )n equal to 2, Key words: Kasumi; differential cryptanalysis; average idfferential probability; 3GPP 0引言 ,8, KasumiTSI( EuropeanT elecommunication StandardsIn stitute) E分组密码由欧洲标准机构 下属的安全rd ,9,1999 3GPP( 3Generation Partnership Project) f 8，算法组于 年 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 被用于 移动通信的保密算法 和完整 ,9,f 9Kasumi 8 feistel ，64-bit 128-bit ，64- 。性检验算法 中算法是一个 轮的 结构密码由 输入和 的密钥产生 bit ，。的输出它是第三代移动通信系统的核心算法之一 Kasumi 3 ，FO、FL FI。FO FL ，FI 算法含有 个主要函数分别为 和 其中 和 构成算法的轮函数则用于 FO 。Kasumi FO ，FI FI 。组成 函数算法的非线性主要依赖 函数更进一步讲是依赖 函数因而 函数的平均 。差分概率对整个算法的抗差分分析影响很大 ,7,，差分密码分析是迄今已知的攻击迭代密码比较有效的方法之一因而分组密码的抗差分特性也成 。: 为衡量算法安全的标准之一差分攻击的基本思想是通过分析明文对的差值对密文对的差值的影响来 。，，、恢复某些密钥比特另外还有一些以差分密码分析为基础的扩展方法如高阶差分密码分析截断差分 、、。密码分析不可能差分密码分析飞来去器攻击和矩阵攻击等这几种推广分析方法既与差分密码分析的 ，，基本思想有关又不同于差分密码分析一些能抵抗差分密码分析的密码不一定能够抵抗这几种分析方 。Dunkelman Shamir ,1,Sandwich ，Kasumi 法如 和 等在文献中给出了一种 攻击从理论上巧妙地攻击了 算 。法 2012-07-13#############2012-07-13#####2#0#1#2-07-13######## :;:收稿日期修回日期 1 预备知识 1, 1相关定义,4, m n 1定义 = ( f ( x，) …，f ( x) ) : FF，S( x)是一个多输出布尔函数记 令 ? 1n2 2m m L = {l ( x) = x + a，xF: F，aF } ， ?ω?ω?? 222 m d( f，l) f( x) l( x) L ，即 是全体 元仿射布尔函数所成的集合又以 表示布尔函数 与仿射函数 之间的汉明距 d( u?S( x) ，l( x) ) ，N=minS( x) 。离称 为 的非线性度 S ml( x) L? 2n0u F?? 2,4, 2定义 令 …λλn 00 0(2 ) 1),, ,, ( S)= ， Λ, , …λm λm n , , ( 2 ) 1) 0( 2 ) 1) (2 ) 1) mmn S( x) ，={ xF+ S(x + ) = }) 1，，i，j = 0，1，…，2 ) 1; j = 0，1，…，2，i 其中λ?αβαβ分别为 的二 ij 2i j i j 。m ×n S 进制表示则 盒的差分均匀度为 mn ( S) =m ax{ i = 0，1，…，2 ) 1; j = 0，1，…，2) 1; i，j 0} 。δλ不同时为 ji,3,n =Y S X Y ， X3设 和 为 的输入和输出集合= 2。x，xx，yY， X 定义 对于 ΔΓ?和 ΔΓ?令 { xX S( x) (S xx) = y} ?ΔΔS DP( xy)ΔΔ = ;?n 2 2xx = S( x)? y}?ΓΓ { xX ?S , ) 1 2 LP( xy) =，ΓΓ ?n， ， 2 。此处的线性化的定义与标准定义略有不同同时定义 S S DP = max DP ( xy) ，ΔΔ? maxΔx?0，Δy 。,S S LP= max LP( xy)ΓΓ ? maxΓx，Γy?0 ,10,n Fq = 2=F，f: F，0 aF，H= H ( f) = { f( x) + 4定义 设 n设 n n 对于任意给定的 ??n 令 ? 2 2 2 2 a a f( x + a) :x } ，0a， H( f)= q /2，f PN( most PerfectN onnear) 。FFAAlli?n 如果对于所有的 ?n 称 为 ?2 2 a 1, 2 asum Ki算法 ,8, asumfeste ，64 64 Ki8 il、128 。算法是一个 轮的 结构分组密码它有 比特输入比特密钥和 比特的输出Kasumi FO、FL FI 3 ，FO FI FI ，算法包含 和 个主要函数和一个密钥扩展算法其中 和 为非线性函数而 在 asum i算法的轮函数是由 。K密钥确定时为线性函数 FO FL ，、和 两个函数构成但奇偶数轮这两个函数的 : FL FO 使用顺序是不同的奇数轮先使用 函数再使用 ，。函数偶数轮则正好相反 FO ，FI 。 函数是一个递归结构其轮函数是 函数 FO 96 ，48 FI 函数需要 比特的子密钥其中 比特用于 fes- ，48 。FI i函数比特用于混合运算函数本身是一个 tel ，FI FO 16 结构函数需要从它所属的 函数得到 比 ，FI 2 S : S7 S9( S7 7 特子密钥函数还用了 个 盒和 是 ? 7 ; S9 99 ) ，1 2。Kasumi 的置换是 的置换详见表 和表 ? 、1。算法结构函数结构及各个函数间的关系见图 Kasumi MISTY ，算法的密钥扩展算法比 要简单各 。128 个子密钥由密钥经过线性变化得到将 比特的密 8 16 : K，K，K，K，K，K，K，K。 钥分成 个 比特字1 2 3 4 5 6 7 8 1Kasumi图算法结构图K'= KC，18。C。i分别计算??其中为固定常数i i i i 2012-07-13################2012-07-13##2#0#1#2#-#0#7-13######## 3。具体扩展过程见表 1 asum 算法 S 盒 S7表Ki S输入输出函数关系式 7 y= xxxxxxxxxxxxxxxxxxxxxxx 0 1 3 4 0 1 4 5 2 5 3 4 5 6 1 6 3 6 2 4 6 4 5 6 y= xxxxxxxxxxxxxxxxxxxxxx1 1 0 1 0 4 2 4 5 1 2 5 0 3 5 6 0 2 6 3 6 4 5 6 y= xxxxxxxxxxxxxxxxxxxxxxxxx1 2 0 0 3 2 3 1 2 4 0 3 4 1 5 0 2 5 0 6 0 1 6 2 6 4 6 y= xxxxxxxxxxxxxxxxxxxxxxxx 3 1 0 1 2 1 4 3 4 0 5 0 1 5 2 3 5 1 4 5 2 6 1 3 6 y= xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1 4 0 2 3 1 3 1 4 0 1 4 2 3 4 0 5 1 3 5 0 4 5 1 6 3 6 0 3 6 5 6 y= xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1 5 2 0 2 0 3 1 2 3 0 2 4 0 5 2 5 4 5 1 6 1 2 6 0 3 6 3 4 6 2 5 6 y= xxxxxxxxxxxxxxxxxxxxxxxx 6 1 2 0 1 3 0 4 1 5 3 5 6 0 1 5 2 3 6 1 4 6 0 5 6 表 2 Kasumi 算法 S 盒 S9 S、输入输出函数关系式 9 y= xxxxxxxxxxxxxxxxxxx1 0 0 2 3 2 5 5 6 0 7 1 7 2 7 4 8 5 8 7 8 y= xxxxxxxxxxxxxxxxxxxx1 1 1 0 1 2 3 0 4 1 4 0 5 3 5 6 1 7 2 7 5 8 y= xxxxxxxxxxxxxxxxxxxxxx1 2 1 0 3 3 4 0 5 2 6 3 6 5 6 4 7 5 7 6 7 8 0 8 y= xxxxxxxxxxxxxxxxxxxx 3 0 1 2 0 3 2 4 5 0 6 1 6 4 7 0 8 1 8 7 8 y= xxxxxxxxxxxxxxxxxxx 4 0 1 1 3 4 0 5 3 6 0 7 6 7 1 8 2 8 3 8 y= xxxxxxxxxxxxxxxxxxxxx1 5 2 1 4 4 5 0 6 1 6 3 7 4 7 6 7 5 8 6 8 7 8 y= xxxxxxxxxxxxxxxxxxxxxxxx 6 0 2 3 1 5 2 5 4 5 3 6 4 6 5 6 7 1 8 3 8 5 8 7 8y= xxxxxxxxxxxxxxxxxxxxxx1 7 0 1 0 2 1 2 3 0 3 2 3 4 5 2 6 3 6 2 7 5 7 8 y= xxxxxxxxxxxxxxxxxxxx 8 0 1 2 1 2 3 4 1 5 2 5 1 6 4 6 7 2 8 3 8 3asum 表Ki算法密钥扩展 KLKLKOKOKOKKKIIIRound i，1i，2i，1i，2i，3i，1i，2i，3K,, 1,K,, 5,,, 8,,, 13,K'K'K'KKK' 1 1 32 6 7 5482 K,, 1,K'K,, 5,K,, 8,K,, 13,K'K'K' 2 43 7 8 6513 K,, 1,K'K,, 5,K,, 8,K,, 13,K'K'K' 3 54 8 1 7624 K,, 1,K'K,, 5,K,, 8,K,, 13,K'K'K' 4 65 1 2 8735 K,, 1,K'K,, 5,K,, 8,K,, 13,K'K'K' 5 76 2 3 1846 K,, 1,K'K,, 5,K,, 8,K,, 13,K'K'K' 6 87 3 4 2157 K,, 1,K'K,, 5,K,, 8,K,, 13,K'K'K' 7 18 4 5 326 ,, 1, K'K,, 5, K,, 8, K,, 13, K'K'K'K 8 8 2 1 5 6 4 3 7 2FI 函数平均差分概率上界 SS,5，6,i i ( n3) F，S DPp( LPp) ， 2 ，n ，1如图 所示轮?函数 假设每个 为一一变换并且 ??则引理 imaxmaxF2 F2 DP2p( LP 2p) 。 ?? maxmaxF2 F,3,F F1F1 F2 + DP( LPDP LP+ LP) 。F 23 F，DP引理 对于如图 所示的函数 有 ??如果 为一一 maxmaxmax max max maxF F1 F2 F F1 F2 min{ DP，DP} (L Pmin{ LP，LP} )。 ，DP映射对任意密钥均有 ?? maxmax maxmaxmax max,3,L R m ( nm) ，F 34 n F，XXn 引理 和 分别为 和 比特如果每个 均为对于如图 所示的 轮函数 设 ? i，一一映射则 FFFFFm )n FF1 2 2 3 1 3 DPmax( DPDP，DPDP，2DPDP) ; ? maxFFFFFm )n FF1 2 2 3 1 3 ( LPmax( LPLP，LPLP，2LPLP) ) 。 ? maxS7 S9 Kasumi FI S S7 S9 DPDPS7 S91 ，2 ，定理 算法的 函数个 盒 和 均为一一映射假设 和 分别为 和 maxmaxF S7 S9 2 S9 S9 FI max( DP，DP，2DPDP) 。 ，DP的最大差分则 函数的平均差分概率上界 ? maxmax maxmax maxF' FI DP，FI 3 证明 仅证明 函数前 轮的平均差分概率上界 对于 函数的平均差分概率上界可由引理 L R L R 2 。xxyy。 直接推导其中 Δ和 Δ分别表示输入差分的左半部分和右半部分同理 Δ和 Δ表示输出差分 S DPx0，， 。3 ，的左半部分和右半部分因为定义 中规定 时要求 Δ?对于几种特殊的情况必须单独说明所 max2012-07-13#########2012-07-13##2#0#1#2#-#0#7-13######## 4 。以将整个问题分成 种情况进行证明 L R x= 0，x0， ?若 ΔΔ有? F' S7 R L R S9 R L R S7 S9 DP( xy) = DP( xyx) DP( xyy) DPDP。 ΔΔΔΔΔΔΔΔ???? 1max maxR L L x= 0，x0。S7 0，3 S9 7-bit y。 ?若 ΔΔ则 的输出差分为 并且第 轮的 的输入差分的右 定为 Δ?F' 2 S9 L L S9 L L R 2 S9 S9 DP( xy) = 2DP( xy) DP( yyy) 2DPDP。ΔΔΔΔΔΔΔ ???? max maxL R R L yy= 0，3 S9 S9 x。x 0 1 ?若 ΔΔ则第 轮的 的输入差分为 并且第 轮 的输入差分比为 Δ同时 Δ?R 0，x0。Δ? F' S9 L R S7 R L S7 S9 DP( xy) = DP( xx) DP( xy) DPDP。ΔΔΔΔΔΔ? ??? max max S9 ， ，1 ?其它情况设第 轮的 的输出差分为 Δ则S9 L S7 R R L S9 R L R F' DP( x y)DP( x) DP( xxy) DP( xyy) = ΔΔ ? ΔΔΔΔ Δ ΔΔ ΔΔ Δ? ? ? ? ? Δ S9RLRS7 S9S7 S9 y yDPDPDPΔΔΔ) DPDP。?( x ? Δ? max max max max Δ FI 3 3 F，1 3 F，将 函数的前 轮看成图 中的 函数将最后 轮看成图 中的 函数所对应的平均差分概 1 2 S7 S9 2 S9 S9 S7 S7 S7 S9 max( DPDP，2DPDP) DP，DP,D PDP，2 率上界分别为 和 因为 则由引理 得出 max maxmax maxmaxmaxmax maxF S7 S9 2 S9 S9 S7 S7 S9 2 S9 S9 DPmax( max( DPDP，2DPDP) ，DP) max( DPDP，2DPDP) 。 ?? maxmax maxmax maxmaxmax maxmax max Kasumi FI FI Kasumi1 ，定理 可以用于从理论上估计 算法 函数的平均差分概率上界进而对 函数及 。算法的抗差分特性有一定的量化分析 3Kasumi 算法的平均差分分析 ，，通过对线性化的特殊定义线性化的分析方法及结论与平均差分相似因而本节重点介绍平均差分概 。率的相关结论 Kasumi FL FO 2 ，，FL ，FL 算法的轮函数由 和 个函数构成然而当密钥确定时函数为线性所以 函数对 FO ; DPp ，，1，Kasumi 轮函数的平均差分概率没有影响假设 在轮密钥相互独立的情况下由引理 可得 算? max 1kasumi 2 DP2p，asum FO 。FO KiFI 法的平均差分概率 因此 的平均差分概率主要依赖于 函数函数是由 ?函 max1FI FO 2 kasumi 4 KO ; DP,p ，3，m =n ，DPp。DPp， 数及子密钥 组合得到的假设 由引理 当 综上可得 则整个?? max 2max 2max 2 FI FI 。。算法的平均差分上界主要取决于 函数下面对 函数的平均差分概率进行具体分析 AES S FI ，。FI首先利用 盒提出一种改动的 函数进而可以比较改动前后的平均差分概率将改动的 FI-1 ，FI-1 Kasumi ，Kasimi-1，FI-1 :函数命名为 函数由 构成 算法设为 函数如下 16-bit I，2 。I = LR; S AES S 88 。 的输入 分成左右相等的 部分盒使用 的 的 盒‖?0 0 :操作过程 L= RR= S,L,R 1 01 00 L= RKIR= S,L,RKI 2 1 i，j，22 11 i，j，1 L= RR=S,L,R3 2 322 2012-07-13#########2012-07-13##2#0#1#2#-#0#7-13######## R= S,L,RR= R 4 334 3 : LR。输出‖ 4 4 f )n + 1 n n f，f DP2 ，APN ，n ，对于 进 出的函数 若 为一一映射当 为奇数时最小可达到 函数即可满足 maxf )n + 2 ; n ，DP2 ( ) 。Kasumi S7 要求当 为偶数时猜测 最小为 这是一个公开的难题通过计算可以得到 的 和 max1 ) 7 ) 6 1 ) 9 ) 8 2 ) 8 ) 6 S9 S 2= 2 2= 2 ; AES S 2= 2 。两个 盒的平均差分概率分别为 和 盒的平均差分概率为 由定 FI ) 14 FI ) 1 ) 12 3，DP2 、DP2 。， 理 可以得到 ??可见改动后的平均差分概率的上界扩大了抗差分攻击的能力 maxmaxKasumi ) 14 4 ) 55 Kasumi ) 1 ) 12 4 ) 47 DP2 ( 2 ) = 2 、DP2 ( 2 ) = 2 。 。1、3 1，减弱了综合引理 和定理 可得 ??改动后的 maxmax Kasumi-1 。，Kasumi-1 Kasumi 的平均差分概率的上界也扩大了因此从抗差分分析的方面说的安全性比 算 。法的安全性低 4 表FI 函数平均差分上界 : 16-bit ，FI 由上面的结论进一步思考以 输入为例对于 函数这种 ，16-bit ?L平均差分概率上界结构将 输入分为其它的情况平均差分上界会有怎样的变化 0 R) 12‖ 0 82 f)n + 2) 14 “f DP”，n ，2 在假设若 为一一映射当 为偶数时最小为 为正确‖max 2 8 ) 12 的 2 ) 14 72 ，1，FI 情况下利用定理 可计算出其它分组情况下的 函数的平均差分 ) 12 ‖2 ，4。) 14 上界具体见表 9 : LR，41622 从表 可以比较得到将 比特输入分为 个奇数的 ‖0 0 6) 14 ) 12 差 2 ，2 L R ，2 。分上界为 分为 个偶数 差分上界为 所以从抗差‖ 0 0‖ 分 asum 7 | 9| 。，2 。Ki分析的角度分为 个奇数组合相对较好算法基于硬件实现的考虑选择 这样的组合 10 5 ‖ 4结束语 11 4 ‖FI ，，文章证明了 函数的平均差分概率上界对于从理论上评估这个函数的抗差分特性有一定的帮助 12Kasumi 。并对进一步详细分析 算法的抗差分特性及设计结构类似的分组密码算法有一定帮助文章仅仅 3，。给出了平均差分概率上界对于函数的确切抗差分分析的能力还需进一步分析 ‖ 13 :参考文献 ,1, Orr Dunkelman，Nathan Keller，Adi Shamir, A Pratical-Time Attack on theA 5 /3 Cryptosystem Useind Third Generation GSM, Cryptology eprint Archive report201 0 /013,EB / OL,, ,2010-01-01,, http: // e print，iacr ,or g /2010 /013, pdf, -2010, ,2, Mtsuu Matsu, New Boc ncypton gothm MSTJ, Lecture notesin computers cense19971267: 54-68, irilkEriAlriIY,,i，，,3, Mitsuru Matsui, New Structure oBf lock Cipher with Provable Security against Differential and Linear Cryptanalysis,J,, Lec- ture Notesin ComputerS cience，1996，1039: 205-218, ,4, ，，, ,M,, : ，2000: 170-173,温巧燕钮心忻杨义先现代密码学中的布尔函数北京科学出版社 ,5, NybergK ，Knudsen L, Provable Security against Differential Cryptanalysis,J,, Lecture Notesin computerS cience，1995，740: 566-574, ,6, NybergK , Linear Approximation of Block Ciphers,J,, Lecture Notesin computerS cience ，1995，950: 439-444 ,7, , M,, : 2009: 99-132,，，,，吴文玲冯登国张文涛分组密码的设计与分析北京清华大学出版社 ,8, V3, 1, 1，2001，3G security，Specification of the 3GPP oCnfidentiality and Intergrity Algorithms; Document2K: ASUMI Specifica- tion,S,, ,9, V6, 1, 0，2002，3G security，Specification of theA 5 /3 Encryption Algorithms for GSM and ECSD，and tGEhe A3 Encryption Al- gorithm for GPRS; Document D4e; sign and evauation report,S,, l ,10, Dobbetin H, Almost Perfect Nonlinear Power Functions on GF( 2) ,J,, IEEE Transactions on Information Theory，1999，45: n 1271-1275, 2012-07-13################2012-07-13##2#0#1#2#-#0#7-13######## Your requestcould not be processed becauseof a configurationerror: "Could not connect to LDAPserver." For assistance,contact your network support team.