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
RackNerd提供四款高配美国服务器促销活动低至月$189
RackNerd 商家给的感觉就是一直蹭节日热点，然后时不时通过修改配置结构不断的提供低价年付的VPS主机，不过他们家还是在做事的，这么两年多的发展，居然已经有新增至十几个数据中心，而且产品线发展也是比较丰富。比如也有独立服务器业务，不过在他们轮番的低价年付VPS主机活动下，他们的服务器估摸着销路不是太好的。这里，今天有看到RackNerd商家的独立服务器业务有促销。这次提供美国多个机房的高配独立...
AlphaVPS（€3.99/月）VPS年付15欧，AMD EYPC+NVMe系列起
AlphaVPS是一家保加利亚本土主机商(DA International Group Ltd)，提供VPS主机及独立服务器租用等，数据中心包括美国(洛杉矶/纽约)、德国、英国和保加利亚等，公司办公地点跟他们提供的保加利亚数据中心在一栋楼内，自有硬件，提供IPv4+IPv6，支持PayPal或者信用卡等方式付款。商家提供的大硬盘VPS主机，提供128GB-2TB磁盘，最低年付15欧元起，也可以选择...
vpsdime7美元/月，美国达拉斯Windows VPS,2核4G/50GB SSD/2TB流量/Hyper-V虚拟化
vpsdime怎么样?vpsdime是2013年成立的国外VPS主机商，以大内存闻名业界，主营基于OpenVZ和KVM虚拟化的Linux套餐，大内存、10Gbps大带宽、大硬盘，有美国西雅图、达拉斯、新泽西、英国、荷兰机房可选。在上个月搞了一款达拉斯Linux系统VPS促销，详情查看：vpsdime夏日促销活动,美国达拉斯vps,2G内存/2核/20gSSD/1T流量,$20/年，此次推出一款Wi...
esc为你推荐
-
郭吉军二战中受害最大的国家？主页改不了为什么我电脑的主页改不了了?邮箱打不开怎么办我的邮箱打不开怎么办怎么在qq空间里添加背景音乐怎么在QQ空间里免费添加背景音乐？？？？arm开发板arm开发板是干什么用的，是用在什么领域方面的ios7固件下载iphone自动下载IOS7固件版本怎么删除网络广告投放网络广告投放有哪些技巧？怎么在图片上写文字怎么才能在图片上写字呢263企业邮箱设置ipad mini2怎么设置263企业邮箱怎样申请支付宝怎么申请支付宝？