linearesc
esc 时间:2021-02-23 阅读:()
Copyright2017NTTcorp.
AllRightsReserved.
CubeAttacksonNon-BlackboxPolynomialsbasedonDivisionPropertyYosukeTodoNTTSecurePlatformLaboratoriesandKobeUniv.
ThisisjointworkwithTakanoriIsobeKobeUniv.
YonglinHaoTsinghuaUniv.
WilliMeierFHNWESC20172Copyright2017NTTcorp.
AllRightsReserved.
OverviewAkindofhigher-orderdifferentialcryptanalysis.
‐Especially,it'spowerfulforstreamciphers.
Experimentalapproach.
‐Thecubeattackanalyzessymmetric-keycryptosystembyregardingitasblackboxpolynomials.
Newgenerictoolsforcubeattackstoexploittheinternalstructureofstreamciphers.
renewbestattacks.
CubeAttacksonBlackboxPolynomialsCubeAttacksonNon-BlackboxPolynomials3Copyright2017NTTcorp.
AllRightsReserved.
OurapproachDivisionpropertyintheworldofcubeattacksWhatisdivisionproperty‐Tooltofindintegraldistinguishersforblockciphers.
Firstapplicationtostreamciphers.
‐Zero-sumdistinguishersaretrivial.
‐But,It'snontrivialtorecoverthesecretkey.
Newinsight.
‐Whatdivisionpropertycando.
‐Anewhowtousedivisionproperty.
ItisusedtoanalyzeANFcoefficients.
‐Keysthatarenotinvolvedto"superpoly"areevaluated.
4Copyright2017NTTcorp.
AllRightsReserved.
Outline1.
Preliminaries.
1.
Cubeattacks(onblackboxpolynomial).
2.
Divisionproperty.
3.
Mixed-integerlinearprogramming.
2.
Zero-sumintegraldistinguishers.
3.
Ourapproach.
1.
AnalyzetheANFof"superpoly".
2.
Whatdivisionpropertycando.
3.
Howkeysarerecovered.
4.
Applications.
5Copyright2017NTTcorp.
AllRightsReserved.
Modelofstreamciphers.
secretvariables(key)publicvariables(iv)Letberegardedasthefirstbitofkeystream.
Keyinitialization6Copyright2017NTTcorp.
AllRightsReserved.
CubeattacksonblackboxpolynomialsLet=1,…,||{1,2,…,}betheindicesofactivebitsandbeasetof2||valueswhere{1,…,||}aretakingallcombinationsofvalues.
–bethemonomial,=1||.
–(,)iscalledthesuperpolyof.
–(,)missesatleastonevariablefrom.
–Attackersrecoverbyanalyzing(,).
7Copyright2017NTTcorp.
AllRightsReserved.
Howisrecoveredfromsuperpoly(,)ofrealstreamciphersistoocomplicatedtoanalyzeit.
Heuristicevaluation‐Randomlychosen.
‐isregardedasblackbox‐Wecannoticewhetherornotthesuperpolyislinearforwithhighprobability.
Significantdrawbacksofthisapproach.
‐Thesizeofcubeislimitedtoexperimentalrange.
‐Thesizeisatmostabout40.
8Copyright2017NTTcorp.
AllRightsReserved.
DivisionpropertyProposedatEurocrypt2015.
Tooltofindintegraldistinguishers.
DefinitionLetbeamultisetwhoseelementstakeavalueof2.
Letbeasetwhoseelementstakeavalueon2.
Whenthemultisethasthedivisionproperty1,itfulfillsthefollowingconditions:9Copyright2017NTTcorp.
AllRightsReserved.
DivisionpropertySincethreepropagationrules(copy,xor,and)aredefined,wecanevaluatearbitrarycircuit.
HowtomodelthreepropagationsbyMILP.
MILPsolvercanefficientlyevaluatethepropagationofdivisionproperty.
PropagationsearchusingMILP(XiangetalAC16)Bit-baseddivisionproperty(TodoetalFSE16)10Copyright2017NTTcorp.
AllRightsReserved.
Divisiontrail1230121Thereisadivisiontrail0,1,…,∈0*1**satisfyingthepropagationcharacteristic.
IfthereisNOTdivisiontrail,thethbitofciphertextisbalanced.
11Copyright2017NTTcorp.
AllRightsReserved.
ApplicationtostreamciphersTrivialapplicationiszero-sumdistinguisher.
‐CreateMILPmodelthatrepresentsthepropagationofdivisionpropertyfor(,).
‐Let=1,…,||{1,2,…,}betheindicesofactivebitsandevaluate(,).
‐Letbevalues.
t.
=.
‐IfthereisNOTdivisiontrail,thefirstbitofkeystreamisbalanced.
Wecan'trecoversecretvariables.
12Copyright2017NTTcorp.
AllRightsReserved.
OurapproachesforkeyrecoveryIt'spossibleifwecanenoughevaluateANFcoefficientsofsuperpoly.
Anewapplicationofdivisionproperty.
‐Weneverusedivisionpropertytofindzero-sumdistinguisher.
‐DivisionpropertyisusedtoanalyzeANFcoefficientof(,).
‐Secretvariablesinvolvedtothesuperpolyofgivencubeareevaluated.
13Copyright2017NTTcorp.
AllRightsReserved.
BasicknowledgeAlgebraicNormalFromIt'spracticallyinfeasibletoanalyzeall.
Let∈2beANFcoefficients.
14Copyright2017NTTcorp.
AllRightsReserved.
ANFofSuperpolyDecomposeaccordingtos.
t.
=15Copyright2017NTTcorp.
AllRightsReserved.
WhatdivisionpropertycandoAssumingthereisNOTtrail,Inotherwords,‐isalways0forany.
WecanusedivisionpropertyasatooltoevaluatefeatureofANFcoefficients.
isalwayszeroforany.
16Copyright2017NTTcorp.
AllRightsReserved.
Extensiontokeyrecovery.
AssumingthereisNOTtrail,isalways0forany(||).
Then,Thesuperpolyisindependentof.
17Copyright2017NTTcorp.
AllRightsReserved.
Attackstrategy1.
Evaluationphase.
‐Involvedsecretvariablesareevaluatedinthisphase.
‐ThisphaseisfeasiblebyusingMILP.
2.
Off-linephase.
‐Computethesumofgivencube.
‐Thisphaseisnotpractical,butthetimecomplexityisbounded.
3.
On-linephase.
‐Queryencryptionoracle.
‐Recoversecretvariables.
18Copyright2017NTTcorp.
AllRightsReserved.
1stphase--evaluationphase.
1.
Decidethepositionofactivebits=1,…,||{1,2,…,}.
2.
Preparetheset=.
3.
EvaluatewhetherornotthereisdivisiontrailLetbean-bitunitvectorwhosethbitis1.
Letbean-bitvectors.
t.
=.
4.
Ifthereisasuchtrail,=∪{}.
5.
Repeatallpossibleof∈{1,2,…}.
Finally,containsbitsthatmaybeinvolvedtothesuperpoly.
secretvariables(key)publicvariables(iv)19Copyright2017NTTcorp.
AllRightsReserved.
2ndphase--off-linephase.
1.
Decideinitialiv.
2.
Preparethesetofchosenivsbyflippingbitsin.
3.
Guess-bitsecretvariables(1,2,…,).
Foreachguess,computeandstore(,).
Thetimecomplexityofthisphaseis2||+||.
secretvariables(key)publicvariables(iv)20Copyright2017NTTcorp.
AllRightsReserved.
3rdphase--on-linephase.
1.
Accessencryptionoracleunderchosenivsetting.
Querythecubeusedintheoff-linephase.
Computethesum(,).
2.
Comparethesuminon-linephasewiththesumofeach{1,2,…,}inoff-linephase.
Ifthesumisdifferent,guessedsecretvariablesareincorrect.
Thedatacomplexityofthisphaseis2||.
secretvariables(key)publicvariables(iv)21Copyright2017NTTcorp.
AllRightsReserved.
ApplicationtoTriviumzistatesize=288bitsinitialization=1152rounds22Copyright2017NTTcorp.
AllRightsReserved.
ApplicationtoTriviumzi80-bitsecretkey80-bitinitializationvectorstatesize=288bitsinitialization=1152rounds23Copyright2017NTTcorp.
AllRightsReserved.
VerifyourideaexperimentallyActiveIVsInvolvedkeysRoundComplexity#ofactiveIVs=50,2,4,6,8#ofinvolvedkeys=418,19,20,6255729Experimentalresults–initialIV:515B6628BB3160851515–Wetest100randomkeys.
If(18|19|20|62)={0,3,4,7,8,B,D,E},thesumis1.
If(18|19|20|62)={1,2,5,6,9,A,C,F},thesumis0.
24Copyright2017NTTcorp.
AllRightsReserved.
TheoreticalcubeattacksActiveIVsInvolvedkeysRoundComplexity#ofactiveIVs=660,1,2,…,5254,56,58,…,78#ofinvolvedkeys=1022,24,25,26,35,41,55,66,67,68829276#ofactiveIVs=690,1,2,…,5860,62,64,…,78#ofinvolvedkeys=70,36,41,55,66,67,68830276#ofactiveIVs=710,1,2,…,6264,66,68,70,72,74,76,78#ofinvolvedkeys=448,73,74,75831275#ofactiveIVs=720,1,2,…,6466,68,70,72,74,76,78#ofinvolvedkeys=533,57,58,59,60832277Weonlyexecutethe1stphase(evaluationphase)25Copyright2017NTTcorp.
AllRightsReserved.
OtherapplicationsGrain128a‐Previousbestattackis177rounds,andit'sonlydistinguisher.
‐Ourattackis183roundsandit'spossibletorecoverthesecretkey.
ACORN(oneof3rdroundCAESARcandidates)‐Previousattackis477rounds.
‐Ourattackisatleast604rounds.
26Copyright2017NTTcorp.
AllRightsReserved.
ConclusionCubeattacksonnon-blackboxpolynomials.
‐Anewmethodtousedivisionpropertywasproposed.
ItisusedtoanalyzeANFcoefficients.
‐ThetaskofcryptographersisonlycreatingMILPmodelfordivisionproperty.
Thecostisverysmall.
It'sveryeasytoapplytovariousstreamciphers.
‐Wecanevaluatecubeattacksevenifthesizeofcubeistheoreticalrange.
AllRightsReserved.
CubeAttacksonNon-BlackboxPolynomialsbasedonDivisionPropertyYosukeTodoNTTSecurePlatformLaboratoriesandKobeUniv.
ThisisjointworkwithTakanoriIsobeKobeUniv.
YonglinHaoTsinghuaUniv.
WilliMeierFHNWESC20172Copyright2017NTTcorp.
AllRightsReserved.
OverviewAkindofhigher-orderdifferentialcryptanalysis.
‐Especially,it'spowerfulforstreamciphers.
Experimentalapproach.
‐Thecubeattackanalyzessymmetric-keycryptosystembyregardingitasblackboxpolynomials.
Newgenerictoolsforcubeattackstoexploittheinternalstructureofstreamciphers.
renewbestattacks.
CubeAttacksonBlackboxPolynomialsCubeAttacksonNon-BlackboxPolynomials3Copyright2017NTTcorp.
AllRightsReserved.
OurapproachDivisionpropertyintheworldofcubeattacksWhatisdivisionproperty‐Tooltofindintegraldistinguishersforblockciphers.
Firstapplicationtostreamciphers.
‐Zero-sumdistinguishersaretrivial.
‐But,It'snontrivialtorecoverthesecretkey.
Newinsight.
‐Whatdivisionpropertycando.
‐Anewhowtousedivisionproperty.
ItisusedtoanalyzeANFcoefficients.
‐Keysthatarenotinvolvedto"superpoly"areevaluated.
4Copyright2017NTTcorp.
AllRightsReserved.
Outline1.
Preliminaries.
1.
Cubeattacks(onblackboxpolynomial).
2.
Divisionproperty.
3.
Mixed-integerlinearprogramming.
2.
Zero-sumintegraldistinguishers.
3.
Ourapproach.
1.
AnalyzetheANFof"superpoly".
2.
Whatdivisionpropertycando.
3.
Howkeysarerecovered.
4.
Applications.
5Copyright2017NTTcorp.
AllRightsReserved.
Modelofstreamciphers.
secretvariables(key)publicvariables(iv)Letberegardedasthefirstbitofkeystream.
Keyinitialization6Copyright2017NTTcorp.
AllRightsReserved.
CubeattacksonblackboxpolynomialsLet=1,…,||{1,2,…,}betheindicesofactivebitsandbeasetof2||valueswhere{1,…,||}aretakingallcombinationsofvalues.
–bethemonomial,=1||.
–(,)iscalledthesuperpolyof.
–(,)missesatleastonevariablefrom.
–Attackersrecoverbyanalyzing(,).
7Copyright2017NTTcorp.
AllRightsReserved.
Howisrecoveredfromsuperpoly(,)ofrealstreamciphersistoocomplicatedtoanalyzeit.
Heuristicevaluation‐Randomlychosen.
‐isregardedasblackbox‐Wecannoticewhetherornotthesuperpolyislinearforwithhighprobability.
Significantdrawbacksofthisapproach.
‐Thesizeofcubeislimitedtoexperimentalrange.
‐Thesizeisatmostabout40.
8Copyright2017NTTcorp.
AllRightsReserved.
DivisionpropertyProposedatEurocrypt2015.
Tooltofindintegraldistinguishers.
DefinitionLetbeamultisetwhoseelementstakeavalueof2.
Letbeasetwhoseelementstakeavalueon2.
Whenthemultisethasthedivisionproperty1,itfulfillsthefollowingconditions:9Copyright2017NTTcorp.
AllRightsReserved.
DivisionpropertySincethreepropagationrules(copy,xor,and)aredefined,wecanevaluatearbitrarycircuit.
HowtomodelthreepropagationsbyMILP.
MILPsolvercanefficientlyevaluatethepropagationofdivisionproperty.
PropagationsearchusingMILP(XiangetalAC16)Bit-baseddivisionproperty(TodoetalFSE16)10Copyright2017NTTcorp.
AllRightsReserved.
Divisiontrail1230121Thereisadivisiontrail0,1,…,∈0*1**satisfyingthepropagationcharacteristic.
IfthereisNOTdivisiontrail,thethbitofciphertextisbalanced.
11Copyright2017NTTcorp.
AllRightsReserved.
ApplicationtostreamciphersTrivialapplicationiszero-sumdistinguisher.
‐CreateMILPmodelthatrepresentsthepropagationofdivisionpropertyfor(,).
‐Let=1,…,||{1,2,…,}betheindicesofactivebitsandevaluate(,).
‐Letbevalues.
t.
=.
‐IfthereisNOTdivisiontrail,thefirstbitofkeystreamisbalanced.
Wecan'trecoversecretvariables.
12Copyright2017NTTcorp.
AllRightsReserved.
OurapproachesforkeyrecoveryIt'spossibleifwecanenoughevaluateANFcoefficientsofsuperpoly.
Anewapplicationofdivisionproperty.
‐Weneverusedivisionpropertytofindzero-sumdistinguisher.
‐DivisionpropertyisusedtoanalyzeANFcoefficientof(,).
‐Secretvariablesinvolvedtothesuperpolyofgivencubeareevaluated.
13Copyright2017NTTcorp.
AllRightsReserved.
BasicknowledgeAlgebraicNormalFromIt'spracticallyinfeasibletoanalyzeall.
Let∈2beANFcoefficients.
14Copyright2017NTTcorp.
AllRightsReserved.
ANFofSuperpolyDecomposeaccordingtos.
t.
=15Copyright2017NTTcorp.
AllRightsReserved.
WhatdivisionpropertycandoAssumingthereisNOTtrail,Inotherwords,‐isalways0forany.
WecanusedivisionpropertyasatooltoevaluatefeatureofANFcoefficients.
isalwayszeroforany.
16Copyright2017NTTcorp.
AllRightsReserved.
Extensiontokeyrecovery.
AssumingthereisNOTtrail,isalways0forany(||).
Then,Thesuperpolyisindependentof.
17Copyright2017NTTcorp.
AllRightsReserved.
Attackstrategy1.
Evaluationphase.
‐Involvedsecretvariablesareevaluatedinthisphase.
‐ThisphaseisfeasiblebyusingMILP.
2.
Off-linephase.
‐Computethesumofgivencube.
‐Thisphaseisnotpractical,butthetimecomplexityisbounded.
3.
On-linephase.
‐Queryencryptionoracle.
‐Recoversecretvariables.
18Copyright2017NTTcorp.
AllRightsReserved.
1stphase--evaluationphase.
1.
Decidethepositionofactivebits=1,…,||{1,2,…,}.
2.
Preparetheset=.
3.
EvaluatewhetherornotthereisdivisiontrailLetbean-bitunitvectorwhosethbitis1.
Letbean-bitvectors.
t.
=.
4.
Ifthereisasuchtrail,=∪{}.
5.
Repeatallpossibleof∈{1,2,…}.
Finally,containsbitsthatmaybeinvolvedtothesuperpoly.
secretvariables(key)publicvariables(iv)19Copyright2017NTTcorp.
AllRightsReserved.
2ndphase--off-linephase.
1.
Decideinitialiv.
2.
Preparethesetofchosenivsbyflippingbitsin.
3.
Guess-bitsecretvariables(1,2,…,).
Foreachguess,computeandstore(,).
Thetimecomplexityofthisphaseis2||+||.
secretvariables(key)publicvariables(iv)20Copyright2017NTTcorp.
AllRightsReserved.
3rdphase--on-linephase.
1.
Accessencryptionoracleunderchosenivsetting.
Querythecubeusedintheoff-linephase.
Computethesum(,).
2.
Comparethesuminon-linephasewiththesumofeach{1,2,…,}inoff-linephase.
Ifthesumisdifferent,guessedsecretvariablesareincorrect.
Thedatacomplexityofthisphaseis2||.
secretvariables(key)publicvariables(iv)21Copyright2017NTTcorp.
AllRightsReserved.
ApplicationtoTriviumzistatesize=288bitsinitialization=1152rounds22Copyright2017NTTcorp.
AllRightsReserved.
ApplicationtoTriviumzi80-bitsecretkey80-bitinitializationvectorstatesize=288bitsinitialization=1152rounds23Copyright2017NTTcorp.
AllRightsReserved.
VerifyourideaexperimentallyActiveIVsInvolvedkeysRoundComplexity#ofactiveIVs=50,2,4,6,8#ofinvolvedkeys=418,19,20,6255729Experimentalresults–initialIV:515B6628BB3160851515–Wetest100randomkeys.
If(18|19|20|62)={0,3,4,7,8,B,D,E},thesumis1.
If(18|19|20|62)={1,2,5,6,9,A,C,F},thesumis0.
24Copyright2017NTTcorp.
AllRightsReserved.
TheoreticalcubeattacksActiveIVsInvolvedkeysRoundComplexity#ofactiveIVs=660,1,2,…,5254,56,58,…,78#ofinvolvedkeys=1022,24,25,26,35,41,55,66,67,68829276#ofactiveIVs=690,1,2,…,5860,62,64,…,78#ofinvolvedkeys=70,36,41,55,66,67,68830276#ofactiveIVs=710,1,2,…,6264,66,68,70,72,74,76,78#ofinvolvedkeys=448,73,74,75831275#ofactiveIVs=720,1,2,…,6466,68,70,72,74,76,78#ofinvolvedkeys=533,57,58,59,60832277Weonlyexecutethe1stphase(evaluationphase)25Copyright2017NTTcorp.
AllRightsReserved.
OtherapplicationsGrain128a‐Previousbestattackis177rounds,andit'sonlydistinguisher.
‐Ourattackis183roundsandit'spossibletorecoverthesecretkey.
ACORN(oneof3rdroundCAESARcandidates)‐Previousattackis477rounds.
‐Ourattackisatleast604rounds.
26Copyright2017NTTcorp.
AllRightsReserved.
ConclusionCubeattacksonnon-blackboxpolynomials.
‐Anewmethodtousedivisionpropertywasproposed.
ItisusedtoanalyzeANFcoefficients.
‐ThetaskofcryptographersisonlycreatingMILPmodelfordivisionproperty.
Thecostisverysmall.
It'sveryeasytoapplytovariousstreamciphers.
‐Wecanevaluatecubeattacksevenifthesizeofcubeistheoreticalrange.
- linearesc相关文档
- Multifunctionesc
- versionesc
- 心衰esc
- wireesc
- LBResc
- Greeceesc
鲸云10美元,香港BGPRM 1核 1G 10Mbps峰值带宽 1TB流量,江西CN2-NAT 1核 512MB内存 100M带宽 ,
WHloud Official Notice(鲸云官方通知)(鲸落 梦之终章)]WHloud RouMu Cloud Hosting若木产品线云主机-香港节点上新预售本次线路均为电信CN2 GIA+移动联通BGP，此机型为正常常规机，建站推荐。本次预售定为国庆后开通，据销售状况决定，照以往经验或有咕咕的可能性，但是大多等待时间不长。均赠送2个快照 2个备份，1个默认ipv4官方网站：https:/...
Megalayer美国独立服务器新用户首月优惠350元（30M优化不限流量）
Megalayer 商家在开始看到有提供香港服务器、香港站群服务器的时候有介绍过，后来就一直没有怎么关注。但是前几天有看到网友使用到他们家的美国独立服务器问其如何的，但是我没有使用过就不好评论，这不前几天也有介绍到Megalayer美国独立服务器。以及我们也有看到商家有提供美国站群服务器和美国大带宽服务器产品，可选30M不限制流量CN2优化线路，以及100M不限制流量国际带宽线路。新年元旦后，Me...
博鳌云¥799/月,香港110Mbps(含10M CN2)大带宽独立服务器/E3/8G内存/240G/500G SSD或1T HDD
博鳌云是一家以海外互联网基础业务为主的高新技术企业，运营全球高品质数据中心业务。自2008年开始为用户提供服务，距今11年，在国人商家中来说非常老牌。致力于为中国用户提供域名注册（国外接口）、免费虚拟主机、香港虚拟主机、VPS云主机和香港、台湾、马来西亚等地服务器租用服务，各类网络应用解決方案等领域的专业网络数据服务。商家支持支付宝、微信、银行转账等付款方式。目前香港有一款特价独立服务器正在促销，...
esc为你推荐
-
雅虎社区雅虎是中国的吗二叉树遍历二叉树三种遍历方式原则？arm开发板想购买一个ARM开发板，选什么类型的好arm开发板单片机开发板与ARM开发板有什么不同？网站联盟网盟跟b2b平台有什么区别qq空间装扮QQ空间装扮qq空间打扮QQ空间打扮宕机宕机是什么意思?机械键盘轴机械键盘蓝轴有什么作用电子商务网站模板电子商务网站模板哪个好？电子商务网站模板免费建站怎么样？