信息安全技术SM3密码杂凑算法-编制说明-全国信息安全标准化

《信息安全技术SM3密码杂凑算法》（征求意见稿）编制说明一、任务来源根据国家标准化管理委员会XX年下达的国家标准制修订计划，国家标准《信息安全技术SM3密码杂凑算法》由国家商密办负责主办。标准计划号为XXXXX（全国信息安全标准化技术委员会XXXX年信息安全专项）。二、编制原则1．坚持安全、实用、美观的技术标准：全面分析所制定规范的安全性，对算法的可抗攻击性进行完善分析，重点考虑实用性和其以后的推广；保证算法能够有效抵抗比特追踪法以及其他已知的分析方法。算法的设计过程中，算法的符号表述尽量标准、美观。2．创新性：在算法标准的设计方面分别有不同的创新。3．自主性：设计自主、符合我国需求的哈希算法。4．高效性：设计的杂凑算法便于软、硬件平台高效的实现。在保障安全性的前提下，综合性能指标优于SHA-256。5．合法性：符合国家有关法律法规和已经制定的标准规范的相关要求。三、主要工作过程（一）密码行业标准起草工作过程1．设计评审阶段2002年1月21日，国密办下达了“杂凑算法”研制任务的通知，算法于2002年5月设计完成。2002年8月22日，技术处对数据所研制的SCH1杂凑算法进行了算法审查，并于8月29日至31日对其余六个分别由数据所、济南得安、中科院DCS中心、成都卫士通、江南所和山东大学研制的SCH2-SCH7进行了集中审查。确定并评审出SCH4杂凑算法。2．优化检测阶段2003年7月，国密办向SCH4研制单位中科院数据与通信保护研究教育中心下达了“关于对SCH4杂凑算法进行修改完善的通知”，9月26日“LSW杂凑算法课题组”完成SCH4杂凑算法修改完善工作完成并形成相关技术文档。2003年10月27日志12月26日，商用密码杂凑算法综合检测组在SSR02密码算法综合检测平台、IC卡汇编语言仿真检测平台、FPGA/ASIC仿真检测平台上对优化后的SCH4杂凑算法进行了综合检测并形成综合检测记录和检测报告。3．初稿编写及IP核实施阶段2004年6月国密办下达杂凑算法标准编写任务。7月～10月底，中科院数据通信与保护研究教育中心根据杂凑算法标准编写任务的要求完成商用密码杂凑算法标准，形成初稿。同年11月，根据国密办《关于下达杂凑算法IP核设计任务的通知》，国家密码管理委员会办公室商用密码研究中心承担了SCH4杂凑算法0.35um、0.25um、0.18um三种工艺IP核实现的设计任务，形成SCH4算法IP核实施方案。4．算法修改及初稿重新修订阶段2005年3月，针对王小云教授自主研发的比特追踪法破解MD5等算法的情况，国家密码管理局请专家组对SCH4算法进行了针对性分析，分析结果表明该算法不能有效抵御比特追踪法分析；随后国家密码管理局紧急组织成立了SCH杂凑算法研制攻关组，在保持SCH4基本结构的基础上，运用最先进的杂凑算法分析和设计理论对其修改，研制了SCH算法并对初稿进行重新修订。新算法采用了新颖的消息扩展算法、双字介入的并行压缩结构以及混合使用不同群运算，有利于消息的扩散和混乱，便于软、硬件实现。针对算法本身特点，综合运用差分抗碰撞分析、线性分析和均差分析等方法进行了深入的安全性分析，特别是针对国际上最先进的比特追踪法进行了安全设计和分析。结果表明，该算法安全强度高，灵活性好，技术先进，设计上有创新，适合软硬件实现，适合IC卡等终端用户产品实现。5．征求意见稿编写阶段2005年5月，对初稿进行修改和补充，结合各成员单位多年技术积累，反复交流，求同存异，在形成一致共识的基础上整理完成了规范的征求意见稿。6．送审稿编写阶段2008年4月，依据国密局字[2008]190号文件“关于下达《SM1分组密码算法》等标准文本修订任务的通知”，无锡江南信息安全工程技术中心组成了标准文本修订工作小组，开展对SM3密码杂凑算法标准文本的修订工作。工作小组遵照国家密码管理局关于“精心组织、周密安排，合理使用经费“的要求采取了集中办公的方式，统筹安排、合理分工、认真编写、交流讨论等方式开展工作。按照标准的规范性要求，在标准的结构、规范性要素的编写规则，尤其是密码算法的标准名称、前言、引言、范围、术语和定义、符号和缩略语、内容设置、图、表、公式表述、词语表达、符号选择、规范性引用文件和参考性文献以及规范性附录和资料性附录等方面，经多次讨论，反复修订，形成了《SM3密码杂凑算法》标准文本。2012年1月～2012年2月，国家密码管理局组织专家审查，对《算法》进行修改和讨论，并对送审稿进行补充完善，形成了《SM3密码杂凑算法》(送审稿)。（二）国家标准工作过程1、2013年3月-2013年9月，在上述工作的基础上，根据信息安全国家标准制修订工作程序，对标准文本进行完善修改，形成《信息安全技术SM3密码杂凑算法》征求意见稿，提交信安标委秘书处。2、2013年11月20日，信安标委秘书处组织专家对文本进行讨论修改；编制组根据专家意见对标准文本进行修改完善。四、标准的主要内容及确定内容的依据1．SM3杂凑算法流程描述SM3杂凑算法是一种基于分组迭代结构的杂凑算法。SM3杂凑算法流程描述如下：(1)消息填充分组处理：将输入消息比特X（不失一般性，限制消息串的比特长度小于264），按照特定的规定填充并分组成为固定长度整数倍的消息分组序列BB=BB0…BBn-2BBn-1，其中每一消息分组BBi长度固定为512比特，并且BBn-1中最好64比特用来指示消息x的比特长度。(2)迭代处理：从0到n-1迭代计算：(3)SM3()：Hi+1=CF（Hi，BBi）(4)消息比特串X的输出结果为：Hn=SM3(X)是输出长度为256比特的压缩函数。(5)其中H0-IV为一256比特常量，CF（Hi，BBi）是输出长度为256比特的压缩函数。(6)杂凑值输出：SM3杂凑算法将以上第n次迭代处理的256比特输出值Hn，通过选裁函数个g(Hn)得到160比特、192比特或256比特三种长度的杂凑输出值。2．SM3杂凑算法主要结构描述(1)填充过程假设消息x的长度为l。则首先将比特“1”添加到消息的末尾，再添加k个“0”，这里k是满足1448(mod512)lk的最小非负整数。然后再添加一个64比特长的块，其值等于消息x的长度l的二进制表示。产生的比特串'x的比特长度恰好为512的整数倍。例如，对消息比特串：011000010110001001100011应用以上填充得到比特串：42364240110000101100010011000111000000011000l将消息'x按512比特进行分组：011'......nxBBB，其中(65)512nlk。(2)迭代压缩算法对每一个消息分组iB按顺序进行以下处理：1(,)iiiVCFVB0,1,...,1in其中CF是压缩函数，0V为256比特初始值IV。迭代压缩的输出为nV。(3)消息扩展算法将消息分组iB按以下方法扩展成132个消息字0167,,...,,：a.将消息分组iB划分为16个字0115...。b.FOR16jTO6711693136((15))(7)jjjjjjWPENDFORc.FOR16jTO634'jjjENDFOR(4)压缩函数令,,,,,,,ABCDEFGH为字寄存器，1,2,1,2SSSSTTTT为中间变量，压缩函数1(,)iiiVCFVB计算过程详细描述如下：iABCDEFGHVFOR0jTO631[(12)()]7SSAETj21(12)SSSSA1[(,,)2]'jTTFFABCDSSW2[(,,)1]jTTGGEFGHSSWDC9CBBA1ATTHG19GFFE0(2)EPTTENDFOR1iiVABCDEFGHV压缩函数第j步框图如下：W′jTjSFFCDABR′R(5)选裁过程令消息x的n次迭代压缩输出值为nVABCDEFGH，长度为256比特。针对不同的杂凑输出值长度要求，通过选裁函数()nygV选裁产生256比特、192比特或160比特的杂凑值。a.256比特输出nABCDEFGHV，输出yABCDEFGH。b.192比特输出nABCDEFGHV0yABE，1yBF,2yCG3yDH,4yFC,5yDG输出192比特的杂凑值012345yyyyyyy。c.160比特输出nABCDEFGHV0yABE，1yBFC，2yCG，图2压缩函数1(,)iiiVCFVB中“第j步”的框图3yDH，4yDG输出160比特的杂凑值01234yyyyyy。五、与相关法律法规及国家有关规定、国内相关标准的关系1)与相关法律法规及国家有关规定的关系本标准遵守《商用密码管理条例》的各项规定，标准中定义的各项标识与GM/T0004-2012《SM3密码杂凑算法》中规定的相关密码算法的使用要求保持一致。2)与相关国际标准的关系本标准中的附录A“商用密码领域中的相关OID定义”定义了国产密码算法相关的标识符OID，与国际上相关密码算法的OID定义不存在冲突，是对国际上密码算法的OID定义的扩展。六、有关问题的说明1．函数与常数(1)初始值IV=7380166F4914B2B9172442D7DA8A0600A96F30BC163138AAE38DEE4DB0FB0E4E(2)内部常数774519015787981663jCCjTADAj(3)函数015(,,)()()()1663jABCjFFABCABACBCj015(,,)()()1663jEFGjGGEFGEFEGj(4)置换01()(9)(17)()(15)(23)PXXXXPXXXX2．算法特点（1）创新的结构设计SM3杂凑算法的压缩函数采用P置换作为加强雪崩的基本运算，结合双字介入的并行处理结构，增加了扩散和混乱的速度，在提高安全性的同时，又保证了算法的实现效率。消息扩展算法采用了带P置换的线性反馈移位寄存器结构，加强消息的雪崩，增强了寻找特殊结构消息的难度。（2）抗比特追踪法的高安全性设计针对单向性、抗碰撞性等密码安全要求，进行了差分分析、线性分析等全面的密码分析，优化了算法相关参数，满足杂凑算法安全性需求。特别是针对比特追踪法等最新杂凑算法分析方法，增加16步全异或布尔函数运算，采用P置换、消息快速扩散结构和不同群运算，首次设计出第一圈抗碰撞攻击的设计技术，进一步提高了算法抗新型分析的安全性。（3）软硬件高速实现SM3杂凑算法首次采用了可并行实现的双字介入结构、提出了易于实现的带循环移位的P置换、采用了并行两路加法链流水设计，提高了算法的硬件效率；使用针对字操作的混合不同群运算设计，满足了跨平台软件实现的高效性和广泛的适用性。3．与国内外同类研究技术综合比较（1）SM3与SHA-256的安全性比较由于MD5和SHA-1等算法存在碰撞攻击，我们仅对SM3压缩函数和SHA-256压缩函数的安全性关键指标进行比较。由于两个算法均包括64步，具体指标能够真实反映两者的安全性强度。局部碰撞：SHA-256存在着9步的局部碰撞，其概率为212。杂凑算法碰撞攻击的路线总是由局部碰撞路线复合而成。SHA-256的9步局部碰撞路线结合消息扩展可以构成23步的碰撞；而SM3的5步局部碰撞的概率为282，但该5步局部碰撞不能跟消息扩展相结合构成更多步的SM3的碰撞。单圈碰撞攻击：SHA-2（包括所有的MDx和SHAx系列算法）存在显然的16步（完整一圈）的概率为1的碰撞攻击。而SM3经各方多次评估均未发现SM3大于1282的一圈的碰撞攻击。碰撞攻击