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
LOCVPS：美国XEN架构VPS七折,全场八折,日本/新加坡XEN架构月付29.6元起
LOCVPS发来了针对XEN架构VPS的促销方案，其中美国洛杉矶机房7折，其余日本/新加坡/中国香港等机房全部8折，优惠后日本/新加坡机房XEN VPS月付仅29.6元起。这是成立较久的一家国人VPS服务商，目前提供美国洛杉矶(MC/C3)、和中国香港(邦联、沙田电信、大埔)、日本(东京、大阪)、新加坡、德国和荷兰等机房VPS主机，基于XEN或者KVM虚拟架构，均选择国内访问线路不错的机房，适合建...
bluehost32元/月，2核2G/20GB空间,独立ip，新一代VPS美国云主机!
bluehost怎么样?bluehost推出新一代VPS美国云主机!前几天，BlueHost也推出了对应的周年庆活动，全场海外虚拟主机月付2.95美元起，年付送免费的域名和SSL证书，通过活动进入BlueHost中文官网，购买虚拟主机、云虚拟主机和独立服务器参与限时促销。今天，云服务器网(yuntue.com)小编给大家介绍的是新一代VPS美国云主机，美国SSD云主机，2核2G/20GB空间,独立...
HaBangNet（6.95美元/月）美国vps 5TB流量/德国vps 香港双向CN2 GIA VPS
HaBangNet支持支付宝和微信支付，只是价格偏贵，之前国内用户并不多。这次HaBangNet推出三个特价套餐，其中美国机房和德国机房价格也还可以，但是香港机房虽然是双向CN2 GIA线路，但是还是贵的惊人，需要美国和德国机房的可以参考下。HaBangNet是一家成立于2014年的香港IDC商家，中文译名：哈邦网络公司，主营中国香港、新加坡、澳大利亚、荷兰、美国、德国机房的虚拟主机、vps、专用...
esc为你推荐
-
支付宝查询余额支付宝怎么查余额？！？！人人时光机寻时光机歌词中国电信互联星空互联星空是什么？是电信公司的吗？唱吧电脑版官方下载唱吧有电脑版吗滚动代码来回滚动代码数据库损坏数据库坏了,怎么修复?保护气球什么气球可以骑？iphone6上市时间苹果六什么时候出的安全漏洞如何发现系统安全漏洞电子商务网站模板我想开发一个电子商务网站，但是想加入自己设计的模板，可以吗？