Simon量子算法攻击下的可调加密方案研究.pdf
《Simon量子算法攻击下的可调加密方案研究.pdf》由会员分享,可在线阅读,更多相关《Simon量子算法攻击下的可调加密方案研究.pdf(10页珍藏版)》请在咨信网上搜索。
1、第 9 卷 第 2 期信 息 安 全 学 报Vol.9 No.22024 年 3 月Journal of Cyber SecurityMarch 2024通讯作者:王鹏,博士,副研究员,Email:本课题得到国家自然科学基金(No.61732021)和国家重点研发计划(No.2018YFB0803800,No.2018YFA0704704)资助。收稿日期:2020-05-30;修改日期:2020-09-08;定稿日期:2022-12-07Simon 量子算法攻击下的可调加密方案研究毛淑平1,2,王鹏1,2,胡磊1,21信息安全国家重点实验室 中国科学院信息工程研究所 北京 中国 1000852
2、中国科学院大学 网络空间安全学院 北京 中国 100049摘要随着量子计算机和量子计算技术的迅速发展,量子算法对密码系统安全性的威胁迫在眉睫。之前的研究表明,许多经典安全的对称密码结构或方案在基于 Simon 算法的量子攻击下不安全,例如 3 轮 Feistel 结构、Even-Mansour 结构、CBC-MAC、GCM 和 OCB 等方案。可调加密方案通常设计为分组密码工作模式,用于磁盘扇区加密,其结构可以分为 Encrypt-Mask-Encrypt(CMC、EME、EME*等)、Hash-CTR-Hash(XCB、HCTR、HCH 等)和 Hash-ECB-Hash(PEP、TET、H
3、EH 等)三种类型。本文利用 Simon 算法,对 HCTR、HCH、PEP 和 HEH 四种可调加密方案进行了分析,研究结果表明这四种可调加密方案在选择明文量子攻击下是不安全的,使用多项式次的量子问询即可得到与方案秘密值有关的周期函数的周期,进而将其和可调随机置换区分开来。对于利用 Simon 算法对可调加密方案的攻击,构造周期函数是关键。一般基于两种特殊形式的可调加密方案构造周期函数:一种是固定调柄,一种是变化调柄。本文用变化调柄的方法给出了对 CMC 和 TET 两种可调加密方案更简洁的量子攻击方法。通过对比分析,固定调柄和变化调柄两种不同的 Simon 量子攻击方式得到的周期不同,可结
4、合得到进一步的结果。最后本文从固定调柄和变化调柄的角度对可调加密方案的一般量子攻击方法进行了总结,并给出了对基于泛哈希函数可调加密方案(Hash-CTR-Hash 和 Hash-ECB-Hash)的通用攻击。关键词可调加密方案;HCTR;HCH;PEP;HEH;Simon 量子算法中图法分类号TP309.7DOI 号 10.19363/J10-1380/tn.2024.03.08Study on Tweakable Enciphering SchemesAgainstSimons Quantum AlgorithmMAO Shuping1,2,WANG Peng1,2,HU Lei1,21St
5、ate Key Laboratory of Information Security,Institute of Information Engineering,ChineseAcademy of Sciences,Beijing 100085,China2School of Cyber Security,University of ChineseAcademy of Sciences,Beijing 100049,ChinaAbstractWith the rapid development of quantum computers and quantum computing technolo
6、gy,the threat of quantumattack algorithms to the security of cryptosystems is imminent.Previous studies have shown that many classically securesymmetric cryptographic structures or schemes are not secure under quantum attacks based on Simons algorithm,forexample,3 rounds Feistel structure,Even-Manso
7、ur structure,and schemes including CBC-MAC,GCM,OCB,etc.Usuallydesigned as block cipher modes of operation,tweakable enciphering schemes can be used as disk sector encryptionalgorithm and its structures can be divided into three types:Encrypt-Mask-Encrypt(CMC,EME,EME*,etc.),Hash-CTR-Hash(XCB,HCTR,HCH
8、,etc.)and Hash-ECB-Hash(PEP,TET,HEH,etc.).This paper uses Simonsalgorithm to analyze four tweakable enciphering schemes including HCTR,HCH,PEP and HEH,showing that these fourtweakable enciphering schemes are insecure under the quantum chosen-plaintext attacks.The period of the periodicfunction relat
9、ed to the secret value of the scheme can be obtained by using Simons algorithm with polynomial quantumqueries,and then can be used to distinguish the scheme from a tweakable random permutation.For attacks on tweakableenciphering schemes using Simons algorithm,the construction of periodic functions i
10、s the key point.Generally,periodicfunctions are constructed based on two special forms of tweakable enciphering schemes:one is fixed tweaks,and the otheris variable tweaks.More concise quantum attacks against two tweakable enciphering schemes CMC and TET are given byusing the method of variable twea
11、ks.It is shown that the two different quantum attacks with fixed tweaks and variabletweaks have different periods,which can be combined to obtain further results.Finally,we summarize general quantumattacking methods against tweakable enciphering schemes from the perspective of fixed tweaks and varia
12、ble tweaks,andgives a general attack on tweakable enciphering schemes based on universal hash functions(Hash-CTR-Hash andHash-ECB-Hash).Key wordstweakable enciphering scheme;HCTR;HCH;PEP;HEH;SimonsAlgorithm毛淑平 等:Simon 量子算法攻击下的可调加密方案研究971引言1.1可调加密方案2011 年,Liskov 等人1提出了可调分组密码(tweakable block ciphers,简
13、称 TBC)的概念,将“调柄”加入了分组密码之中。调柄的加入使得分组密码更易于使用,基于其上的工作模式安全性更加容易证明。可调分组密码这一概念原本是为工作模式设计服务的,随后人们发现这一概念同时适用于磁盘扇区加密。磁盘扇区进行加密时,扇区地址对应调柄,每个扇区的明文和密文等长。磁盘扇区长度大于一般分组密码分组长度,一般需要再基于分组密码或者可调分组密码进行构造,这种加密方案被称为可调 加 密 方 案(tweakable enciphering scheme,简 称TES)。可调加密方案与可调分组加密的安全性定义一致,区别在于可调分组密码的分组长度固定,可调加密方案的分组长度一般是可变长的.可调
14、加密方案应用广泛,不仅可以直接用于磁盘扇区加密,而且可以通过简单对明文加入冗余信息的方式,成为认证加密方案,例如 AEZ 等方案的设计,其核心就是一个可调加密方案。可调加密方案可以分为 Encrypt-Mask-Encrypt、Hash-CTR-Hash 和 Hash-ECB-Hash 三种类型。其中Encrypt-Mask-Encrypt 类型的第一和三层都是加密模式(Encrypt),第二层先生成一些非线性的值,然后对其它对分组进行异或(Mask),这一类型包括 CMC2、EME3、EME*4等;Hash-CTR-Hash 类型的第一和三层用到了泛哈希函数(universal hash f
15、unction)处理数据,第二层主要用 CTR 模式加密数据,这一类型包括 XCB5、HCTR6、HCH7等;Hash-ECB-Hash 类型的第一和三层用到了泛哈希函数处理数据,第二层用 ECB 模式加密数据,这一类型包括 PEP8、TET9、HEH10等。1.2量子算法近年来量子技术迅速发展,量子算法在许多问题上可以达到经典算法的指数级加速。Shor11研究发现大数分解问题和离散对数问题都存在量子多项式时间算法,比相应的经典算法具有指数级的加速。由于 Shor 算法,量子计算对 RSA 等公钥密码构成了严重威胁。在对称密码领域,一直以来都认为最大的威胁来自于 Grover 量子搜索算法12
16、,此算法可以将?比特密钥的搜索复杂度降低为?。Simon13提出的量子算法可以用?次查询获取特殊函数?的周期,远远优于经典算法?次的查询。我们将这一算法称为 Simon 算法。近些年来,Simon 量子算法在对称密码领域得到应用,表明某些对称密码在量子攻击下的脆弱性。1.3基于 Simon 算法的量子攻击利用 Simon 算法的量子攻击可分为以下几步:(1)利用原方案构造一个周期函数,周期一般是一个和密钥等秘密信息相关的值;(2)利用 Simon 量子算法求出周期;(3)利用得到的周期,对原方案进行区分、伪造等攻击。2010 年,Kuwakado 和 Morii14利用 Simon 算法给出了
17、3轮Feistel结构的量子选择明文攻击,该攻击可在多项式时间内将轮函数为随机置换的 3 轮Feistel 结构与随机置换区分开来。2012 年,他们利用Simon 算法对 Even-Mansour 结构的分组密码进行了攻击15,表明 Even-Mansour 结构在量子环境下不安全。2016 年,Kaplan 等人16针对 Simon 承诺条件弱化的情况作了分析,表明在轮函数为随机函数的情况 下 Simon 算 法 仍 有 极 大 的 概 率 成 功,并 对CBC-MAC、GCM、OCB 等分组密码工作模式进行了量子攻击。2017 年 Leander 和 May17将 Simon 算法与 G
18、rover 算法结合起来,用 Grover 算法搜索的同时,用Simon算法求周期,表明分组密码前后异或独立密钥并不能在量子环境下提高安全性。2019 年,罗宜元等人18利用 Simon 算法对三轮 MISTY-L 结构与3 轮 MISTY-R 结构进行了区分攻击。2019 年 Ghosh 和 Sarkar19利用 Simon 算法分析了 6 种可调加密方案,包括 CMC、EME、XCB、TET、AEZ 和 FAST,这些方案在经典计算环境下都被证明是安全的,但是在量子环境下只需要?次查询就可以将其和随机置换区分开来。1.4本文贡献本文的贡献分为以下 3 个方面:(1)首次给出了对 4 种可调
19、加密方案的量子攻击方法,包括 HCTR、HCH、PEP 和 HEH。在经典环境中,这些方案都是可证明安全的。而在量子环境中,使用 Simon 量子算法可在多项式时间内将HCTR、HCH、PEP 和 HEH 方案与可调随机置换区分开来,因此上述 4 种可调加密方案在量子环境下是不安全的。(2)我们具体使用了固定调柄和变化调柄两种不同攻击方法。用变化调柄法给出了 CMC 和 TET98Journal of Cyber Security 信息安全学报,2024 年 3 月,第 9 卷,第 2 期更简洁的攻击。某些可调加密方案同时可以用两种攻击,所得周期涉及变量也不同,可根据攻击需要选择或结合两种攻击
20、方式分析。(3)给出了利用Simon算法攻击Hash-CTR-Hash和 Hash-ECB-Hash 两类可调加密方案的统一方法。2基础知识2.1基本定义分组密码是一个函数?:?,其中?躈是密钥空间,?躈是消息空间,?是所有?的保长置换。可调分组密码是函 数?:?其 中?是 调 柄 空 间,?是所有?和?的保长置换。我们令?表示通过均匀分布从集合?中选择一个随机元素?。令?为?上所有保长置换的集合。当?时,将其表示为?。同时令?为从?到?的所有映射的集合。?也可以看作是所有分组密码?:?的集合。如果?,则对于每一个?,?是一个随机置换。当?时,我们表示为?。敌手?是一种可以访问一个或多个查询对
21、象的算法,查询对象一般写在敌手?的上标位置。令?是带有查询对象?的敌手?输出比特 1 的事件。如果可调分组密码?:?无法与可调随机置换?区分开,则称可调分组密码是一个可调(强)伪随机置换(?或?)。具体来说:Adv?h?Pr?h?Pr?Perm?h?h?Adv?h?Pr?h?h?Pr?Perm?h?h?h?若对于任意满足一定资源限制的敌手?来说,Adv?是可忽略的,则称?为可调伪随机置换(?),即选择明文攻击安全的;若Adv?是可忽略的,则称?是可调强伪随机置换(?),即选择密文攻击安全的。2.2Simon 算法及扩展1997 年,Simon13提出了 Simon 问题和 Simon量子算法,
22、该算法对经典算法作出了指数级加速。Simon 问题可以叙述如下:Simon 问问题题:给定一个布尔函数?,对?,满足条件?,?非零且?,目标是求出?的值。其中条件?称为Simon 承诺,表明?是函数?唯一的周期。用“?”表示二 进制 异或 操作,查询 函数?满足?。Simon 算法用量子复杂度?来计算?,远远优于经典算法的?次的查询。对于 Simon问题,?,在?量子比特状态?的 Hadamard变换?有?h?,其中有?。Simon 算法的步骤如下:(1)初始化?个量子比特状态为?;(2)将 Hadamard 变换?应用于前?个量子比特获得量子叠加?;(3)对函数?的量子查询将其映射到状态?h
23、?;(4)对后?个量子比特测量,得到?h的输出,同时前?个量子比特坍缩为?h;(5)对前?个量子再次应用 Hadamard 变换?得到?h?h?h?,此时若?则?幅度为 0 测量不到,因此若测量得到?必有?,即测量得到的?必与?正交。通过重复该步骤?次,可以获得?个与?正交的独立向量 y,因此可以使用线性代数来恢复?.引理引理 1.17令?为?维子空间。若获得?个正交独立向量?,则?线性独立且形成?的基的概率大于?。实际上对于引理 1,至少可以以 0.288 的概率得到?个独立向量,文献18指出当?时算法成功率大于 0.99。2016 年,Kaplan 等人16针对 Simon 承诺条件弱化的
24、情况作了分析,并表明在轮函数为随机函数的情况下 Simon 算法仍有极大的概率成功。他们定义了一个衡量 Simon 承诺满足情况的指标并分析了在Simon 承诺弱化的情况下 Simon 算法成功的概率:定义定义 1.16对于?,且对任意?有?,定义?max?Pr?。定理定理 1.16(具有近似承诺的 Simon 算法)如果毛淑平 等:Simon 量子算法攻击下的可调加密方案研究99?f?sh?,则Simon算法经过?次查询后,得到正确?的概率至少为?。定定理理2.16在Simon算法的?次查询之后,如果?与算法的每个步骤返回的所有向量 ui正交,则Prxf x?t=f t p0概率至少为?。2
25、019 年,罗宜元等人18证明了即使 Simon 承诺不完全满足,若函数?存在周期,则其只存在唯一周期的概率接近 1,并计算表明当?即?时?,即当周期函数?的输入输出长度4时,其存在唯一周期的概率大于 0.99。3常见可调加密方案的 Simon 量子算法攻击对于利用 Simon 算法对可调加密方案的攻击,构造周期函数是关键。一般基于两种特殊形式的可调加密方案构造周期函数:一种是固定调柄,考虑两到三个分组输入的情况;另一种将调柄当成变量,考虑一个明文分组输入的情况。在之前利用 Simon算法对分组密码工作模式的攻击,由于不涉及调柄,多采用第一种形式。文献19对 CMC、XCB、TET 等可调加密
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Simon 量子 算法 攻击 可调 加密 方案 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。