一种基于自更新哈希链的双向认证签名方案

摘 要:目前,哈希链技术已被广泛地应用于信息安全领域中的实体认证和数据源认证,但是哈希链有限的长度限制了它的应用。为此,提出一种基于自更新哈希链的双向认证签名方案。新方案采用自更新哈希链技术进行认证签名,避免了传统公钥算法的复杂运算,并且实现了哈希链在认证过程中自动平滑更新,达到无限使用的目的,从而显著提高了执行速度。同时,结合双向认证机制,能够有效地抵抗重放攻击和中间人攻击,大大增强了新方案的安全性。

关键词:数字签名; 哈希链; 自更新; 双向认证

中图分类号:TP309.7 文献标识码:A

文章编号:1004-373X(2010)09-0087-04

Two-way Authentication Signature Scheme Based on Self-updating Hash Chains

WENG Li-ping, SHI Rong-hua, WANG Guo-cai

(Central South University, Changsha 410075, China)

Abstract: Hash chains are widely used for entity authentication or data-origin authentication in the field of information safety. However, finite length of a Hash chain limits its implementation. A two-way authentication signature scheme based on self-updating Hash chains is proposed. To avoid the computing complexity of the traditional public key algorithm, the scheme adopts Hash function to perform the authentication signature and significantly improves the speed of execution. The scheme achieves the automatic and smooth self-updating of Hash chain during the authentication process, and realizes the purpose of infinite utilization. In combination with the two-way authentication mechanism, the scheme can effectively resist the attack of replay and go-between, and enhance the security of the scheme.

Keywords: digital signature; Hash chain; self-updating; two-way authentication

0 引 言

数字签名[1-2]是密码学中的重要问题之一,它是对传统文件手写签名的模拟,是提供认证性、完整性和不可否认性的重要技术。目前用于数字签名的加密算法[3-4]主要有对称加密算法(如DES)、非对称加密算法(如RSA,DSA)和哈希函数(如MD5,SHA-1)三类。其中,非对称加密算法的保密性较好,消除了对称加密算法中用户交换密钥的需要,但加密和解密的算法复杂,花费时间长,速度慢。哈希函数能使非对称签名算法得到相对较短的输入,并且能够在验证数字签名的同时,验证签名消息或文件的完整性,大大提高数字签名的效率和安全性。

目前,哈希链技术[5]已被广泛应用于信息安全领域中的实体认证和数据源认证。哈希链具有单向可认证性,公开其链尾,依次逆序出示链节点充当验证材料,这些节点可以被链尾所验证。在实际应用中,传统哈希链有长度限制,哈希链过长则效率低,并且由于攻击窗口更大,其安全性也随之降低。另一方面,如果链的长度过短,则需要经常更新,需要产生一条新链,并重新签发或安全传递链尾,更新操作繁琐。

针对这一问题,采用张浩军于2006年提出的自更新哈希链机制[6](Self-Updating Hash Chains,SUHC),结合双向认证[7-8],提出一种基于自更新哈希链的双向认证签名方案,并对新方案的效率和安全性进行了分析。

1 预备知识

1.1 基本定义

定义1 密码学安全哈希函数[9]。

称一个函数h为密码学安全哈希函数,其具有属性:给定函数h及安全参数k,输入为任意长度二进制串,输出为k位二进制串,记为h:{0,1}*|{0,1}k。

(1) 给定x,计算h(x)容易;但给定h(x),求x计算上不可行;

(2) 对于任意x,找到一个y,且y≠x,使得h(x)=h(y),计算上不可行;同时发现一对(x,y),且x≠y,使得h(x)=h(y),计算上也不可行。

定义2 哈希链[5]。

按定义1选择一个密码学安全哈希函数h,选择┮桓雒孛苤肿s,迭代h共N次,生成一个哈希链,链尾hN(s)记为w,即:

w=hN(s)=h(hN-1(s))=h(h(h…hN(s)))

(1)

定义3 核心断言[10]。

一个核心断言是一个函数f:{0,1}*|{0,1}*的一个布尔断言B:{0,1}*|{0,1},使其对任何概率多项时间算法A′、任意多项式p(•)和所有足够大的n有:

Pr[A′(f(Un))=B(Un)]≤12+1p(n)

(2)

式中:Un代表一个均匀分布在{0,1}n上的随机变量。

1.2 自更新哈希链(SUHC)机制

张浩军等人提出的SUHC机制是一种“肩扛式”更新机制,无需额外协议或过程,在哈希链使用过程中携带更新链的验证锚信息。当旧的哈希链消耗完,新的哈希链开始工作,从而达到哈希链无限使用的目的。具体包括初始化、示证和验证三个过程。

1.2.1 初始化

示证者和验证者协商一个安全哈希函数h,其安全参数为k。哈希函数h输出k比特字符串。选择一个布尔断言函数B:{0,1}*|{0,1}为h的硬核,初始化i=1。示证者做以下步骤:

(1) 从空间{0,1}k中随机选择一个安全种子s(假设s的长度为k比特),按照定义2生成一个哈希链,链尾为w=hk(s)。

(2) 选择另一个安全种子s′∈{0,1}k,构造下一个哈希链,其链尾为w′=hk(s′),本地安全存储s′和w′。

(3) 比特位承诺。选择一个随机数SK1,使得B(SK1)=w′[i],计算PK1=h(SK1),安全存储SK1。

(4) 计算g1=h(k-1)(s),ζ0=h(g1,PK1),存储g1。

(5) 安全分发(w,ζ0)。

1.2.2 示证

示证者产生并释放用于认证的证据。第i次示证者做以下步骤:

(1) 计算gi+1=h(k-i-1)(s);

计算或恢复值gi=h(k-i)(s)=h(gi+1)。

(2) 计算下一个比特位承诺。选择一个随机数SKi+1,使得B(SKi+1)=w′[i+1]。

计算PKi+1=h(SKi+1),安全存储SKi+1。

(3) 计算消息完整性验证ζi=h(gi+1,PKi+1)。

(4) 构造并释放认证帧(gi,PKi,ζi,SKi)。

1.2.3 验证

验证者从示证者处接收到认证帧(gi,PKi,ζi,SKi)后做:

(1) 计算并检查h(gi)=gi-1是否成立,其中:

gi-1是在上一次示证会话中发送并被记录下来的链节点值。

(2) 验证消息完整性,计算h(gi,PKi)并检查是否等于ζi-1。

(3) 获得比特承诺位,如果PKi=h(SKi)成立,那么签名有效,计算并记录比特位值B(SKi);否则报错。

(4) 如果通过所有有效性验证,验证者成功验证了示证者。

经过k次成功示证-验证后,哈希链被消耗完,同时验证者刚好获得下一个哈希链k比特的链尾值w′。示证者将w替换为w′,s替换为s′,并产生下一个哈希链包括秘密种子s″和对应链尾w″,从而使哈希链可以连续无限地工作。

2 方案的实现

下面提出一种基于上述自更新哈希链机制的双向认证签名方案。方案由初始化、身份认证和签名验证┤个阶段组成。假设用户A和用户B需要进行信息交互,且用户A要发送签名的消息为M。

2.1 初始化

用户A和用户B协商一个安全哈希函数h,其安全参数为k(哈希函数h输出k比特字符串)。选择一个断言函数B:{0,1}*|{0,1}为h的硬核。

用户A和用户B分别根据1.2.1节步骤进行初始化,各自产生两条哈希链。用户A将(wA,ζA0)安全地传递给用户B,同时用户B将(wB,ζB0)安全地传递给用户A。

令IDA为用户A的惟一身份标识,IDB为用户B的惟一身份标识。

2.2 身份认证

方案利用单向哈希链进行双向身份认证,这里以┑i次认证为例,过程如下:

(1) 用户A首先发送下列消息给B:

messageA1=(IDA,M,h(k-i)(sA),PKAi,MACA1);其中,MACA1=h(IDA,M,h(k-i-1)(sA))。

(2) 用户B收到这条消息后对A进行身份验证。

B使用与A协商的安全哈希函数h计算h(h(k-i)(sA)),如果h(h(k-i)(sA))=h(k-i+1)(sA),则根据式(1)可知,h(k-i)(sA)和h(k-i+1)(sA)是同一条哈希链上相邻链节点值,可以确认为用户A使用的单向哈希链,所以可以确认对方为A用户。其中,h(k-i+1)(sA)指上一次认证中用户A发送并被用户B记录下来的链节点值。

用户B通过对用户A的身份验证后,向A发送接收成功的回执:

messageB1=(IDB,h(k-i)(sB),PKBi,MACB1)

其中,MACB1=h(IDB,h(k-i-1)(sB),MACA1)。

(3) 用户A收到回执后对B进行身份验证。

A使用和B协商的哈希函数h计算h(h(k-i)(sB)),如果h(h(k-i)(sB))=h(k-i+1)(sB),则认证通过,表明h(k-i)(sB)和h(k-i+1)(sB)是同一条哈希链上的相邻链节点值,所以可以确认用户B收到该消息。

2.3 签名验证

当用户A和B都通过对方的身份认证后,用户A向B发送签名部分,用户B验证A的签名并发送回执,用户A验证整个签名过程是否有效。以第i次签名验证为例,过程如下:

(1) 用户A向B发送签名部分:

messageA2=(h(k-i-1)(sA),SKAi,MACA2)

其中,MACA2=h(IDA,MACB1,i,h(k-i-1)(sA),SKAi),i表示进行的第i次签名。

(2) 用户B收到A的签名消息后,利用收到的SKAi计算h(SKAi)。如果h(SKAi)=PKAi,则签名有效,计算并记录B(SKAi)。其中,PKAi是用户B从messageA1中得到的。因为只有用户A知道SKAi,所以可以验证是用户A的签名。

同时用户B利用收到的h(k-i-1)(sA)和从messageA1中得到的IDA和M用哈希函数h计算h(IDA,M,h(k-i-1)(sA))。

如果h(IDA,M,h(k-i-1)(sA))的值和第一次收到的MACA1相等,则说明通信道正常,A发送的消息正确,B发送接收成功的回执:

messageB2=(h(k-i-1)(sB),SKBi,MACB2)

其中,MACB2=h(IDB,MACA2,i,h(k-i-1)(sB),SKBi),i表示进行的第i次签名。

如果计算出的h(IDA,M,h(k-i-1)(sA))与第一次收到的MACA1不相等,则停止协议。

(3) 用户A接收到B的回执后,利用收到的SKBi计算h(SKBi)。如果h(SKBi)=PKBi,则签名有效,计算并记录B(SKBi)。其中,PKBi是用户A从messageB1中得到的。因为只有用户B知道SKBi,所以可以确定用户B收到签名。

同时用户A利用收到的h(k-i-1)(sB)和从messageB1中得到的IDB及MACA1用哈希函数h计算h(IDB,h(k-i-1)(sB),MACA1)。

如果h(IDB,h(k-i-1)(sB),MACA1)的值与第一次收到的MACB1相等,则完成了一次双向认证的签名过程。相反,如果未收到回执,或利用h(k-i-1)(sB)计算的MACB1与第一次收到的MACB1不相等,则请求仲裁者作废签名。

整个过程如图1所示。

图1 第i次认证签名过程

经过k次认证签名后,用户A和B正好获得对方的下一次(新)哈希链的k位链尾

w′B和

w′A。当旧的哈希链消耗完,新的哈希链开始工作。上述过程可以无限、持续地进行。

3 方案分析

3.1 效率分析

本文提出的签名方案,只涉及哈希函数和核心断言函数的运算,核心断言函数可以配置计算速度较快的函数,意味着具有较高的效率。

方案中,一次签名使用两个哈希值,所以每次签名需要的平均运算次数为(k+1)/2。假设IDA为8 B,使用SHA-1算法,则M和h(k-i-1)(sA)均为20 B,则计算MACA1需要一个哈希运算时间。同理,计算MACA2需要计算一个IDA(8 B),一个计数值i(设为5 B)和三个哈希值(60 B),即总共为73 B,需要两个哈希运算时间。此外,用户A还需要进行两次哈希运算对B进行验证和一次断言函数运算,进行新链的比特位承诺。

同理,对用户B也一样,总共需要4次哈希运算和1次核心断言函数运算。

此外,哈希链在认证的过程中,得到平滑更新,无需额外过程,更新所需的计算和存储量被均匀地分摊到哈希链的工作过程中,消耗很小。

因此,新方案的最大优势在于只需进行哈希运算,无需传统对称、公钥密码运算,验证效率高,特别适合应用到对计算速度要求高,设备处理能力和电池容量有限的移动环境中。

3.2 安全性分析

本文提出的签名方案,只涉及哈希函数和核心断言函数,其安全性完全依赖所配置的哈希函数和核心断言函数。当哈希函数的构造或配置为一个强单向、抗碰撞函数时,即在发现翻转哈希函数或寻找哈希函数碰撞计算上是不可行的。如果强单向函数存在,则核心断言存在[10]。哈希函数用于实现认证的同时也起到了消息完整性保护的作用。核心断言函数用于实现位承诺,保证新哈希链链尾比特位的安全传递。因此,方案的安全性得到了保证,此外方案还具有以下安全性:

(1) 抗重放攻击。若用户A发送了消息messageA1,但未到达用户B(可能敌手干扰)。敌手可能观察到了此消息,但敌手仍然无法提供消息messageA2,因为敌手不知道h(k-i-1)(sA)和SKAi。敌手只能根据已知h(k-i)(sA)和PKAi,通过翻转哈希函数或发现哈希碰撞来伪造h(k-i-1)(sA)和SKAi。而方案配置的哈希函数是一个强单向、抗碰撞的函数,即在发现翻转哈希函数或寻找哈希函数碰撞计算上是不可行的。

(2) 抗中间人攻击。用户A和B的消息都是以明文形式传输的,容易遭受中间人攻击。本文采用双向身份认证机制抵抗中间人攻击,不仅需要用户B认证用户A的合法性,同时也需要用户A认证用户B的合法性。具体使用哈希链技术,敌手想要进行攻击就要打破哈希函数的强单向性和抗碰撞性,而这个在计算上是不可行的。

4 结 语

详细描述了一个基于自更新哈希链的双向认证签名方案,并对该方案进行了效率和安全性分析。新方案使用自更新哈希链机制,使哈希链达到无限使用的目的,从而代替公钥算法,避免了公钥算法的复杂运算,提高签名认证的效率,适用于设备处理能力和电池容量有限的移动环境。此外,新方案结合双向认证,能够有效抵抗重放攻击和中间人攻击,大大增强了方案的安全性。

参考文献

[1]ATREYA Mohun.数字签名[M].贺军,译.北京:清华大学出版社,2003.

[2]RIVEST R J, SHAMIR A L. A method for obtaining digi-tal signature and public-key cryptosystem[J]. Communications of the ACM, 1978, 21(2):120-126.

[3]徐茂智,游林.信息安全与密码学[M].北京:清华大学出版社,2007.

[4][美]梅尼斯.应用密码学手册[M].胡磊,王鹏,译.北京:电子工业出版社,2005.

[5]LAMPORT L. Password authentication with insecure co-mmunication[J]. Communications of the ACM, 1981, 24(11): 770-772.

[6]ZHANG Hao-jun, ZHU Yue-fei. Self-updating Hash chains and their implementations[J]. IEEE Lecture Notes in Computer Science, 2006, 42(55): 387-397.

[7]施荣华.一种基于Harn数字签名的双向认证访问控制方案[J].计算机学报,2001,24(4):400-404.

[8]蔡满春,赵海洋,郭代飞.移动环境下的一种基于双向认证的哈希链签名方案[J].计算机应用研究,2008,25(5):1532-1533.

[9]施荣华.一种基于单向函数的双重认证存取控制方案[J].电子科学学刊,1997,19(2):278-281.

[10]ODED G. Foundations of cryptography: basic tools[M]. Cambridge: Cambridge University Press, 2001.