caozhengjun的个人博客分享 http://blog.sciencenet.cn/u/caozhengjun

博文

是破绽不是破解 --- 哈希函数释疑

已有 2988 次阅读 2019-10-7 14:29 |个人分类:应用密码学|系统分类:科普集锦| MD5, SHA, 哈希函数, 碰撞攻击, 认证码, MD5, MD5

     

  MD5和SHA是目前使用最为广泛的两个哈希算法,但社会上对它们的认识还有很多疑惑。请看下面这些截图。

01.JPG

03.JPG

   世界上很难找到两个指纹相同的人,因此可以根据指纹来识别人。如何辨别两个电子文件是否相同呢? 对于很长的文件逐个比特进行比较是不明智的。如果能够为每个电子文件创建类似于人类指纹的数字指纹,使得不同的电子文件具有相同的数字指纹的机会非常非常小,那么就可以利用数字指纹来识别电子文件了。 

哈希函数的用法1---数字指纹提取器

哈希函数可以看作数字指纹提取器,又称为杂凑函数、散列函数。它可以把任意长度(实际上是有最大长度限制的)电子文件转换成固定长度(比较短)的输出串,是典型的多到一的映射。给定输入值很容易计算其输出值,但要找到输入值使其输出值等于一个预先给定的值却很难,在计算上是不可行的。也就是说,对给定的哈希函数H以及任意选取的一个指纹c,很难找到文件m,使得H(m)= c.

哈希函数输入的微小变化(哪怕是一个比特发生了改变),其输出也将变得面目全非,输入与输出之间毫无统计规律可循。下面的截图是哈希函数MD5SHA的实例,其结果揭示了这种杂乱无章的变化特征。

 04.JPG

      用户从某个网站下载软件,在下载过程中可能会被下载器内隐藏的木马程序植入病毒。为了防范这种攻击,网站会在网页上标明该软件对应的MD5SHA1数字指纹(一个十六进制的数值),用户下载完成后,可以调用本地机器上的MD5SHA1算法计算安装程序的指纹,比较它与网页上标注的指纹是否是一致的,如果不一致,就可以断定下载到本地的程序是可疑的。 

哈希函数的用法2---认证码

性能好的哈希函数应该是无碰撞的,很难找到两个输入值,使它们映射到同一个数值上。也就是说,无法找到两个不同的m1,m2,使得H(m1) = H(m2)。哈希函数的计算过程是公开的,给哈希函数指定一些输入参数,利用这些参数的机密性,就可以构造消息认证码。

计算机系统常常利用哈希函数来控制用户的登录。为了阻止进入系统后的黑客得到用户注册的口令k,计算机系统不直接存储用户的口令k,而是把哈希值H(k)存储在系统里。每当用户登录时,系统会要求用户输入k',然后调用哈希函数计算哈希值H(k'),如果H(k')=H(k),用户就取得了登录权限。实践中,很多网络用户管理系统还要在用户的口令中掺盐,也就是串接一些随机数,增加暴力破解的难度。

通讯双方可以事先约定,在哈希函数的输入中串接一些彼此共享的密钥s。如果发送消息m时附加上对应的校验码H(m,s),那么对方收到消息m'后,验证H(m',s)= H(m,s),验证通过后,接收方就可以确定发送方的身份,同时也能确定接收到的消息有没有被篡改。 

哈希函数的用法3---构造挑战

哈希函数还常常被用来构造挑战,这种用法是德国密码学家Schnorr最早使用的,在数字签名领域备受重视。为此人们还定义了离散对数知识签名。已知哈希函数H, 消息m,有限群G中的元素g和y。如果(c,s)满足c=H(m,g,y,g^sy^c),则称(c,s)是y关于g及消息m的离散对数知识签名,c称为挑战值。

密码学总是假设哈希函数H的输出是随机的,现在c既出现在H的输入中,也出现在H的输出中,从形式上看就产生了冲突。为了消除这个冲突,必须要求H的真正输入不依赖于c。如果知道了底数y,g之间的陷门x, 满足y=g^x,那么只要选取一个随机数k,计算c=H(m,g,y,g^k), s=k-cx,便可产生合乎要求的签名(c,s)。 

是破绽不是破解

人们很早就找到了哈希函数MD5的碰撞,为什么很多系统至今还一直在使用MD5呢?以百度拼音输入法为例,鼠标对准应用安装程序(后缀.exe),点击右键,查看属性,点击数字签名,然后可以看到所使用的哈希函数及签名算法的名称。

05.JPG

  图中的RSA算法不是用来加密的,而是用来签名的,对指纹做加密运算是毫无意义的。百度公司的技术员对这些基本密码算法的用法尚且迷糊,可见密码知识的普及工作还有很大的发展余地。

近十多年来针对MD5的攻击并没有产生实质性的威胁。理论上利用生日碰撞找到的m1,m2,虽然满足MD5(m1) = MD5(m2),但m1,m2两者都是随机的,对应的文本往往是一串乱码,没什么实际意义。此外,可以通过限制输入串的格式来规避现有的理论攻击。再强调一遍,现有的针对哈希函数的攻击,只是找到了破绽,不是破解,一字之差却有天壤之别。Be flawed, not be cracked.

实际中使用的密码算法都有这样那样的理论破绽,包括美国数字签名标准算法DSA,敌手可以给很多随机消息伪造合法的签名,不过这些随机消息对应的文本往往是一堆乱码,没啥实际意义,无法欺骗验证人而已。

哈希函数的社会功能

人们平时所说的加密算法都匹配了一个解密过程,利用它来恢复加密对象。很显然,哈希函数与加密算法是完全不同的两个概念,它们的用法也完全不同!因此,哈希函数就滋生了一个社会功能: 如果在一篇关于密码知识的科普文章中出现“MD5加密算法”、“SHA加密算法”等字样,那么读者就可以放心地给它贴上伪科普标签了。




http://blog.sciencenet.cn/blog-3224443-1200947.html

上一篇:祝贺央行锚定了数字货币的回归路

1 康建

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-27 15:11

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部