变色龙哈希简介

Chameleon Hash 是一类特殊的 Hash 函数,对于绝大多数使用者,其同样满足哈希函数的 collision-resistant。然而,如果某个人知道 Chameleon 哈希的一些秘密,其可以非常容易破坏collision-resistant。也就是说,对于任意 $m$,其很容易能够找到 $m^\prime \neq m$,使得$ChameleonHash(m^\prime) = ChameleonHash(m)$。这看起来破坏了哈希函数的碰撞抵抗性,但同时带来了non-transferablenon-repudiated 的特性。

变色龙哈希

Chameleon Signature Generation -- CHAM-SIG

输入消息$m\in Z_q^*$,签名私钥$S,SK_S$,接收者的$HK_R(i.e.HK_R=y(=g^x mod\ p),g,p,q)$

  1. 选择一个随机数 $r\in Z_q^*$,计算消息 $m$ 的变色龙哈希 $hash=CHAM-HASH_R(m,r)=g^my^rmod\ p$
  2. 生成签名 $sig = SIGN_S(hash, HK_R)$
  3. 则消息 $m$ 的签名为 $SIG(m)=(m,r,sig)$

Chameleon Signature Verufucatuin -- CHAM-VER

输入 $SIG(m)=(m,r,sig)$,公钥 $S,VK_S$, 接收者的$HK_R(i.e.HK_R=y,g,p,q)$

  1. 计算哈希 $hash=CHAM-HASH_R(m,r)=g^my^r mod \ p$
  2. 验证 $VERIFY_S((hash, HK_R), sig) $是否为真,为真则正确,为假则不正确

Generate Collision

输入 一个伪造的签名 $SIG(m^\prime) =(m^\prime, r^\prime, sig)$

  1. 签名者找出计算$sig$时用到的$m,r$
  2. 签名者计算 $x=\frac{m-m^\prime}{r^\prime-r}mod\ q$
  3. 签名者选择任意消息 $\bar{m}\in Z_p^*$然后计算$\bar{r}=\frac{m+xr-\bar{m}}{x}mod\ q$
  4. 签名者给出 $(\bar{m}, \bar{r})$

变色龙哈希的特性

不可转移性(Non-transferability)

签名者S给接收者R一个签名$SIG=(m,r,sig)$,接收者无法让第三方确定$m$的真实性。这是由于对于接收者而言,其可以很简单的通过变色龙哈希函数伪造消息$m$得到一组$(m^\prime,r^\prime)$使得$CHAM-HASH_R(m^\prime,r^\prime)=sig$。计算方法为伪造$m^\prime$,然后计算$r^\prime=\frac{m+xr-m^\prime}{x}mod\ q$。且由于这一特性造成了对于任意的$m$,接受者都可以找到$r$使得满足签名,这就保证了$sig$与$m$无关,即从$sig$中无法获取有关$m$的任何信息。

抗伪造性(Unforgeability)

没有第三方可以找到任意一对$m,r$满足签名,如果接收者不进行伪造的话。

不可否认性(Non-repudiation)

当接收者给出$SIG(m)=(m,r,sig)$时,若接收者没有进行伪造,则签名者$S$无法证明接收者$R$伪造了该消息,也就是说签名者只能承认该消息及签名是真的。

上述构造的缺点

当接收者进行伪造消息$m$时,他同时会暴露自己的私钥$x$,同时,所有用该私钥进行过计算的信息全部都变得不安全了。这一特点抑制了接收者伪造$m$的愿望,但也破坏了不可转移性(Non-transferability)的概念。

无密钥暴露问题的变色龙哈希

Key Generation

输入一个安全参数 $k$,输出一对($SK,PK$),类似于概率函数:

$$ KeyGen: 1^k\rightarrow(SK,PK) $$

Hash

输入一个公钥$PK$,一个标签$L$,一条消息$m$和一个随机参数$r$,输出一个$\tau$位的二进制字符串

$$ Hash: (PK, L, m, r)\rightarrow C\in\{0,1\}^\tau $$

Universal Forge

输入密钥$SK$,标签$L$,消息$m$,和参数$r$,输出满足$Hash(PK,L,m,r)=Hash(PK,L,m^\prime,r^\prime)$的二元组$(m^\prime,r^\prime)$

$$ UForge(SK,L,m,r)\rightarrow(m^\prime,r^\prime),such\ that $$

$$ Hash(PK,L,m,r)=C=Hash(PK,L,m^\prime,r^\prime) $$

Instance Forge

输入公钥$PK$,标签$L$,消息$m,m^\prime$,随机参数$r,r^\prime$,其中满足$Hash(PK,L,m,r)=Hash(PK,L,m^\prime,r^\prime)$,输出另一对$(m^{\prime\prime},r^{\prime\prime})$满足$Hash(PK,L,m,r)=Hash(PK,L,m^{\prime\prime},r^{\prime\prime})$

$$ IForge(PK,L,m,r,m^{\prime},r^{\prime})\rightarrow(m^{\prime\prime},r^{\prime\prime}),such\ that $$

$$ Hash(PK,L,m,r)=C=Hash(PK,L,m^{\prime},r^{\prime})=Hash(PK,L,m^{\prime\prime},r^{\prime\prime}) $$

除此之外,该函数还满足

Collision-Resistance

在只知道$PK,L,m,r$时,不存在高效的算法可以得到$m^\prime,r^\prime$满足$Hash(PK,L,m,r)=C=Hash(PK,L,m^\prime,r^\prime)$

Semantic Security

变色龙哈希值$C$不揭示关于$m$的任何信息。

Message hiding

当接收者使用 $UForge$ 生成碰撞时,签名者在看到$m^\prime,r^\prime$后,可以在无需曝光$m$的情况下,提出一对$(m^{\prime\prime},r^{\prime\prime})$来证明接收者在伪造消息(即使用$IForge$)。

Key Exposure Freeness

如果接收者有公钥$PK$,并从未计算过一个在标签$L$下的碰撞,则当给出$C=Hash(PK,L,m,r)$时,不存在高效的算法可以找到一个碰撞。即便攻击者拥有$UForge$的访问权限,且可以执行多项式次查询,他也无法得知$SK$。

使用RSA和因子的具体设计(key exposure freeness)

这个设计中有两个后门,其一为RSA模型的因子,另一个时RSA环中元素的根

Key Generation

$\tau,k$为安全参数, $H$为一个抗碰撞的哈希函数,其可以将任意长度的消息变成固定长度为$\tau$的二进制串(例如SHA1,md5)。从${2^{k-1}, ..., 2^k-1}$中取出两个质数$p,q$,令$n=pq$。再生成一个随机的质数$e>2^\tau$。私钥$d$计算公式为$ed=1mod(p-1)(q-1)$。接收者的公钥为$n,e$,私钥为$p,q,d$。

Hash Scheme

用$S$代表标识接收者的字符串,$L$作为一个标签。$C:\{0,1\}^*\rightarrow\{0,...,2^{2k-1}\}$是一个安全的哈希编码算法,将二进制字符串映射成小于$n$的整数。通常的讲,这样的算法是概率的,需要一个随机字符串。这里不考虑它。利用$C$计算 $J=C(L)$,则后门则为$B=J^dmod\ n$,例如在$L$上的一个安全的RSA签名。

那么,$Hash(\cdot)$算法为:

$$ Hash(L,m,r)=J^{H(m)}r^emod\ n,where J=C(L) $$

Collision Finding

为了计算一个碰撞$(m^\prime,r^\prime)$,接收者应该选择一个随机的消息$m^\prime$,然后考虑以下等式:

$$ J^{H(m)}r^e=J^{H(m^\prime)}r^{\prime e} $$

然后求解$r^\prime$即可,即:

$$ r^\prime = rB^{H(m-H(m^\prime))}mod\ n $$

Collision-Resistance 和 Key Exposure Freeness

当接收者给出一个碰撞时,任何人都可以获取与$J=C(L)$关联的密钥$B$,即:

$$ J^{H(m)}r^e=J^{H(m^\prime)}r^{\prime e}\Rightarrow r^\prime/r=B^{H(m)-H(m^\prime)} $$

很明显$\Delta=H(m)-H(m^\prime)$小于$2^\tau$,由于$e$是一个大于$2^\tau$的质数,则$gcd(\Delta,v)=1$,使用扩展的欧几里得算法,可以计算出满足$\alpha\Delta+\beta v=1$的$\alpha,\beta$。则$B$可以被得到:

$$ B=(r^\prime/r)^\alpha J^\beta $$

由于B是一个在$L$上的安全的RSA签名,计算碰撞就等同于破坏RSA签名算法。所以我们认为在不知道trapdoor时计算碰撞是困难的。同时,注意到由于给出碰撞等同于计算签名,所以该算法是key exposure safe.

Semantic Security

对于每个消息$m$, 值$C=Hash(L,m,r)$是由 $r$ 唯一确定的。所以是语义安全的。

Message Hiding

用$C$表示承诺值,一旦碰撞被发现,一个不知道后门的人可以选择任意消息$m^{\prime\prime}$来诋毁承诺。从上面的证明中我们知道一对碰撞$(m,r),(m^\prime,r^\prime)$暴露了后门信息$B=C(L)^d$,为了找到另一个碰撞,选择$m^{\prime\prime}$,计算$r^{\prime\prime}=rB^{H(m)-H(m^\prime)}$即可。

举几个例子🌰

  1. 一个简单的例子便于理解
    假设小明和小红达成协议,小明将家族产业10%股份转让给小红。签了合同小名很担心啊,如果小红把这件事告诉别人怎么办?这时候就可以用变色龙函数进行签名。小红生成一个只有她才能找到碰撞的函数交给小明,小明再用这个函数来签电子文档。这下小红把签名后的文件丢给大家也没人相信她了。为什么呢?她掌握着哈希函数的弱点,可以随便生成哈希碰撞啊。她把10%股份改成99%都能保证哈希不会变,进而创造出新文件本来就是小明签的这种假象。因此出自小红之手的文件可信度为零。这个特性叫non-transferability,即两者之间达成的信任不能转到第三方。

    “你知道的太多了” 此时此刻成了真正的包袱。

    问题来了,小明抵赖怎么破?如果小明死死咬定转让10%股份是小红伪造,事实上只有1%呢?事实上小明也不能信口开河,他得提供对应的证据。证据就是哈希碰撞。假设双方达成的最初合同是A,而小红将其篡改成了相同哈希的A’,那么小明看到A’这份伪证之后一定能拿出最早那个A来并表明A和A’形成哈希碰撞,否则A’就是真货了。因为正常情况下小明无论如何也找不到碰撞,他就不能抵赖。这个特性叫non-repudiation。

    注:引用知乎用户@滕亦飞的回答

    原文链接: https://www.zhihu.com/question/38545889

  2. 正版软件授权
    开发商使用变色龙哈希签名,发给购买者,购买者即便分享该软件,其他人也无法信任其有没有对软件进行修改,增加后门,即利用了不可传递性。

参考文献

[1] Krawczyk, H. and T. Rabin. “Chameleon Signatures.” NDSS (2000).

[2] Chen, X., F. Zhang and K. Kim. “Chameleon Hashing Without Key Exposure.” IACR Cryptol. ePrint Arch. 2004 (2004): 38.

[3] Ateniese, G. and B. D. Medeiros. “On the Key Exposure Problem in Chameleon Hashes.” SCN (2004).

最后修改:2020 年 10 月 22 日
如果觉得我的文章对你有用,请随意赞赏