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
妮妮云80元/月,香港站群云服务器 1核1G
妮妮云的来历妮妮云是 789 陈总 张总 三方共同投资建立的网站 本着“良心 便宜 稳定”的初衷 为小白用户避免被坑妮妮云的市场定位妮妮云主要代理市场稳定速度的云服务器产品，避免新手购买云服务器的时候众多商家不知道如何选择，妮妮云就帮你选择好了产品，无需承担购买风险，不用担心出现被跑路 被诈骗的情况。妮妮云的售后保证妮妮云退款 通过于合作商的友好协商，云服务器提供2天内全额退款，超过2天不退款 物...
湖北22元/月（昔日数据）云服务器，国内湖北十堰云服务器,首月6折
昔日数据怎么样?昔日数据新上了湖北十堰云服务器，湖北十堰市IDC数据中心 母鸡采用e5 2651v2 SSD MLC企业硬盘 rdid5阵列为数据护航 100G高防 超出防御峰值空路由2小时 不限制流量。目前，国内湖北十堰云服务器,首月6折火热销售限量30台价格低至22元/月。(注意：之前有个xrhost.cn也叫昔日数据，已经打不开了，一看网站LOGO和名称为同一家，有一定风险，所以尽量不要选择...
DogYun（300元/月），韩国独立服务器,E5/SSD+NVMe
DogYun(中文名称狗云)新上了一批韩国自动化上架独立服务器，使用月减200元优惠码后仅需每月300元，双E5 CPU，SSD+NVMe高性能硬盘，支持安装Linux或者Windows操作系统，下单自动化上架。这是一家成立于2019年的国人主机商，提供VPS和独立服务器租用等产品，数据中心包括中国香港、美国洛杉矶、日本、韩国、德国、荷兰等。下面分享这款自动化上架韩国独立服务器的配置和优惠码信息。...
esc为你推荐
-
eset用户名谁能给我个可用的ESET用户名和密码ghostxp3GHOSTxp sp3系统有什么优点和缺点？？？pwpw域名的技巧镜像文件是什么什么是文件镜像?什么是镜像文件?硬盘人移动硬盘的优缺点商标注册查询官网全国商标注册查询在哪里查呀？cisco防火墙cisco防火墙里k9是什么意思南北互通什么叫网络运营商之间的互联互通啊？？？？跟服务器有关吗？？厦门铁通厦门铁通和电信哪个好点?空间装扮免费空间还有那些装扮是免费的？