DSA变种以及批认证的安全性证明

2020/06/25 CTF

下面给出一个基于标准DSA数字签名算法的变种的形式化安全性证明,同时给出该算法的批量认证算法以及对应的安全性证明。

签名方案的描述与形式化安全性证明

方案中的签名算法是基于DSA数字签名算法的变种,其中包含

  • 系统初始化:随机选择一个大素数,满足的比特长度;随机选择一个大素数的大素因子,满足,其中的比特长度;选择一个阶子群的生成元,满足;选择一个哈希函数是安全参数。

  • 密钥生成算法:选择一个随机数作为签名者的私钥,计算出 mod 作为签名者的公钥。随机数满足

  • 签名生成算法:对于消息,签名者选择一个随机数,满足。然后计算

    生成的签名结果为

  • 验证签名算法:对于消息m与相应的签名,验证者首先检查签名是否满足。如果不满足则对该签名认证不通过。否则检查下面的公式是否成立,如果成立则对该签名认证通过,否则认证不通过。

定理:假设是一个随机谕言机,如果与方案中相关的离散对数问题是困难的,则该方案是EUF-CMA安全的。

该EUF游戏如下:

  1. 挑战者运行系统初始化算法和密钥生成算法,得到,选取一个随机的哈希函数。敌手得到公钥

  2. 挑战者为敌手提供两项模拟算法,分别是返回消息的哈希值以及对消息的签名。当敌手请求对消息的签名时,挑战者随机选择,然后向敌手返回

  3. 敌手输出一个消息-签名组,其中在之前的询问中没有请求过消息的签名。如果该消息-签名组满足,则敌手攻击成功。

下面证明该方案可以归约到离散对数问题。

敌手已经获得,其中是均匀随机的。敌手攻击作为子程序,目标是计算出。如果说敌手能够得到某个,使得,那么有,即求解出在生成元的模数离散对数。如果说是某个消息的哈希值,那么就是这个消息的签名。是由敌手生成的,但是哈希函数是由敌手生成的,那么敌手可以假设。在这个过程中,设定为某个消息的哈希函数值,由于不知道最终对哪个消息产生伪造的签名,同时也不知道生成的随机数。因此需要对该消息以及随机数进行猜测。下面假设的第询问即是最终要伪造的结果。

其中游戏的过程中需要满足几个条件:

  • 不会发起两次相同的询问。

  • 如果请求对消息的签名,那么它之前已经对发起过询问。

  • 如果输出消息-签名组,那么它之前已经对发起过询问。

下面是归约的过程。

  1. 将公开材料发送给。假设最多进行询问,选择一个随机数,其中满足相当于是的一个猜测值,相当于的第询问即是最终的伪造结果。

  2. 建立一个列表,初始值为空,元素的类型是四元组,表示已经将设置为,并且。当发起第次询问时,分两种情况进行回答:

    • 如果,那么返回

    • 如果,那么选择两个随机值,满足,并将作为本次询问的应答,将存到列表中。

  3. 请求消息的签名时,其中表示在第询问的询问值。分两种情况进行回答:

    • 如果,那么中断。

    • 如果,则列表中存在一个四元组,将其中的返回。

  4. 输出时,如果,此时中断;如果,并且满足,那么输出签名

如果说的猜测是正确的,并且输出一个伪造的签名,那么就解决了离散对数问题,因为,即求解出在生成元下模数的离散对数。的成功依赖下面3个事件:

  • 的签名询问中不中断。

  • 输出一个有效的消息-签名组

  • 事件发生,并且对应的消息签名组中下标满足

因为

因此的优势为:

签名方案中哈希函数的安全性

方案中采用对消息摘要而不是消息本身进行签名的方式,因此Hash函数的安全性也会影响到该方案的安全性。推荐使用SHA-256或者是MD5等安全的哈希函数。下面给出证明,如果方案中采用对消息本身直接进行签名,即,那么该方案是不安全的。

时,签名生成算法如下:

签名的验证算法与上述方案的验证算法一致。

首先考虑比较简单的情况,攻击者构造一个零消息,即消息值,此时攻击者构造出签名满足,该签名是合法的,因为下面等式成立:

一般的,假设攻击者得到了,攻击者的目标是构造出合法签名。这个过程如下描述,首先攻击者选择任意两个均匀随机的随机数,然后构造出下列消息-签名组

该签名是合法的,因为下面的等式成立:

签名方案中随机数k的安全性

在该方案中由于随机数与消息无关,因此每次签名时,使用随机数可以使得对同一消息的签名结果是不同的。但是如果随机数的选取存在缺陷,或者使用相同的随机数对消息进行签名,那么攻击者有更高的优势恢复出

  1. 如果随机数值比较小,根据,攻击者可以使用暴力穷举搜索来求解出值。

  2. 如果攻击者获得了两个使用相同的值的签名消息,那么可以恢复出

批验证算法的安全性证明

下面给出了该签名方案的批验证算法。

  • 个签名者分别生成消息的签名。首先选择一个随机数,计算,得到签名

  • 签名者将发送给验证者。

  • 验证者收到,首先检查每组签名是否满足。如果不满足则丢弃第组签名,否则选择个相互独立的随机数,检验下式是否成立:

在上述方案中,通过引入随机数来避免敌手发起共谋攻击,降低了在叠加操作和连乘操作中各个参数之间的关联性。如果没有随机数,敌手可以伪造出两组参数,这两组参数对应的签名在单独验证中是不能通过的,但是它们的求和结果能消去随机数,从而通过批认证算法。

攻击者如果要攻破该批验证算法,需要构造组合法签名,相当于求解次离散对数问题,这对于攻击者而言是计算上困难的。我们考虑一个特殊情况,即所有的签名者的私钥是相同的,等效于攻击者只需要求解1次离散对数问题。在这种情况下,上述的验证公式变为:

下面给出两个假设并证明它们是等价的。其中假设1是上面验证公式的子问题,如果敌手能满足假设1或者是满足假设2,则表示敌手攻破了该批验证算法。

  1. 假设存在一个高效率的算法,使得下面的式子成立

    其中

  2. 假设存在一个高效率的算法可以破解DSA方案。

下面证明假设1和假设2是等价的。

  • 假设2假设1:这是显然易见的,因为假设2相当于存在一个高效率的算法可以计算出离散对数,即计算出公钥在模的离散对数(私钥)是计算上高效率的,根据上面DSA的计算过程,假设1中的算法也是计算上高效率的。

  • 假设1假设2。将假设1中的两条式子相除消去变量,可以得到:

    将左右的幂消去得到

    此时求解出是对消息的合法DSA签名。

由于DSA签名方案的安全性归约到计算离散对数的困难问题,因此上述假设1中的算法是计算上困难的,进而得出攻击者要破解批认证算法的优势非常小。

Search

    Table of Contents