SHA-1

✍ dations ◷ 2024-12-25 00:14:19 #密码散列函数,密码学,已攻破的散列函数

SHA-1(英语:Secure Hash Algorithm 1,中文名:安全散列算法1)是一种密码散列函数,美国国家安全局设计,并由美国国家标准技术研究所(NIST)发布为联邦资料处理标准(FIPS)。SHA-1可以生成一个被称为消息摘要的160位(20字节)散列值,散列值通常的呈现形式为40个十六进制数。

2005年,密码分析人员发现了对SHA-1的有效攻击方法,这表明该算法可能不够安全,不能继续使用,自2010年以来,许多组织建议用SHA-2或SHA-3来替换SHA-1。Microsoft、Google以及Mozilla都宣布,它们旗下的浏览器将在2017年停止接受使用SHA-1算法签名的SSL证书。

2017年2月23日,CWI Amsterdam(英语:CWI Amsterdam)与Google宣布了一个成功的SHA-1碰撞攻击(英语:Collision_attack),发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。

2020年,针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。

最初载明的算法于1993年发布,称做安全散列标准(Secure Hash Standard),FIPS PUB 180。这个版本现在常被称为SHA-0。它在发布之后很快就被NSA撤回,并且由1995年发布的修订版本FIPS PUB 180-1(通常称为SHA-1)取代。SHA-1和SHA-0的算法只在压缩函数的消息转换部分差了一个比特的循环位移。根据NSA的说法,它修正了一个在原始算法中会降低散列安全性的弱点。然而NSA并没有提供任何进一步的解释或证明该弱点已被修正。而后SHA-0和SHA-1的弱点相继被攻破,SHA-1似乎是显得比SHA-0有抵抗性,这多少证实了NSA当初修正算法以增进安全性的声明。

SHA-0和SHA-1可将一个最大264比特的消息,转换成一串160位的消息摘要;其设计原理相似于MIT教授Ronald L. Rivest所设计的密码学散列算法MD4和MD5。

在CRYPTO 98上,两位法国研究者提出一种对SHA-0的攻击方式:在261的计算复杂度之内,就可以发现一次碰撞(即两个不同的消息对应到相同的消息摘要);这个数字小于生日攻击法所需的280,也就是说,存在一种算法,使其安全性不到一个理想的散列函数抵抗攻击所应具备的计算复杂度。

2004年时,Biham和Chen也发现了SHA-0的近似碰撞,也就是两个消息可以散列出几乎相同的数值;其中162比特中有142比特相同。他们也发现了SHA-0的完整碰撞(相对于近似碰撞),将本来需要80次方的复杂度降低到62次方。

2004年8月12日,Joux, Carribault, Lemuet和Jalby宣布找到SHA-0算法的完整碰撞的方法,这是归纳Chabaud和Joux的攻击所完成的结果。发现一个完整碰撞只需要251的计算复杂度。他们使用的是一台有256颗Itanium2处理器的超级电脑,约耗80,000 CPU工时。

2004年8月17日,在CRYPTO 2004的Rump会议上,王小云,冯登国(Feng)、来学嘉(Lai),和于红波(Yu)宣布了攻击MD5、SHA-0和其他散列函数的初步结果。他们攻击SHA-0的计算复杂度是240,这意味的他们的攻击成果比Joux还有其他人所做的更好。请参见MD5安全性。

2005年二月,王小云和殷益群、于红波再度发表了对SHA-0破密的算法,可在239的计算复杂度内就找到碰撞。

鉴于SHA-0的破密成果,专家们建议那些计划利用SHA-1实现密码系统的人们也应重新考虑。在2004年CRYPTO会议结果公布之后,NIST即宣布他们将逐渐减少使用SHA-1,改以SHA-2取而代之。

2005年,Rijmen和Oswald发表了对SHA-1较弱版本(53次的加密循环而非80次)的攻击:在280的计算复杂度之内找到碰撞。

2005年二月,王小云、殷益群及于红波发表了对完整版SHA-1的攻击,只需少于269的计算复杂度,就能找到一组碰撞。(利用生日攻击法找到碰撞需要280的计算复杂度。)

这篇论文的作者们写道;“我们的破密分析是以对付SHA-0的差分攻击、近似碰撞、多区块碰撞技术、以及从MD5算法中查找碰撞的消息更改技术为基础。没有这些强力的分析工具,SHA-1就无法破解。”此外,作者还展示了一次对58次加密循环SHA-1的破密,在233个单位操作内就找到一组碰撞。完整攻击方法的论文发表在2005年八月的CRYPTO会议中。

殷益群在一次面谈中如此陈述:“大致上来说,我们找到了两个弱点:其一是前置处理不够复杂;其二是前20个循环中的某些数学运算会造成不可预期的安全性问题。”

2005年8月17日的CRYPTO会议尾声中王小云、姚期智、姚储枫再度发表更有效率的SHA-1攻击法,能在263个计算复杂度内找到碰撞。

2006年的CRYPTO会议上,Christian Rechberger和Christophe De Cannière宣布他们能在容许攻击者决定部分原消息的条件之下,找到SHA-1的一个碰撞。

在密码学的学术理论中,任何攻击方式,其计算复杂度若少于暴力搜索法所需要的计算复杂度,就能被视为针对该密码系统的一种破密法;但这并不表示该破密法已经可以进入实际应用的阶段。

就应用层面的考量而言,一种新的破密法出现,暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生,但确有必要发展更强的散列算法来取代旧的算法。在“碰撞”攻击法之外,另有一种反译攻击法(Pre-image attack),就是由散列出的字符串反推原本的消息;反译攻击的严重性更在碰撞攻击之上,但也更困难。在许多会应用到密码散列的情境(如用户密码的存放、文件的数字签名等)中,碰撞攻击的影响并不是很大。举例来说,一个攻击者可能不会只想要伪造一份一模一样的文件,而会想改造原来的文件,再附上合法的签名,来愚弄持有公钥的验证者。另一方面,如果可以从密文中反推未加密前的用户密码,攻击者就能利用得到的密码登录其他用户的账户,而这种事在密码系统中是不能被允许的。但若存在反译攻击,只要能得到指定用户密码散列过后的字符串(通常存在影档中,而且可能不会透露原密码信息),就有可能得到该用户的密码。

2017年2月23日,Google公司宣布,他们与CWI Amsterdam合作创建了两个有着相同SHA-1值但内容不同的PDF文件,这代表SHA-1算法已被正式攻破。

2020年,针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。在数字签名领域,用更安全的SHA-2或SHA-3替换SHA-1已经变得急迫。

以下是SHA-1算法的伪代码:

h0 := 0x67452301h1 := 0xEFCDAB89h2 := 0x98BADCFEh3 := 0x10325476h4 := 0xC3D2E1F0
append the bit '1' to the messageappend k bits '0', where k is the minimum number >= 0 such that the resulting message    length (in ) is congruent to 448(mod 512)append length of message (before pre-processing), in , as 64-bit big-endian integer
break message into 512-bit chunksfor each chunk    break chunk into sixteen 32-bit big-endian words w, 0 ≤ i ≤ 15
        for i from 16 to 79        w := (w xor w xor w xor w) leftrotate 1
        a := h0    b := h1    c := h2    d := h3    e := h4
        for i from 0 to 79        if 0 ≤ i ≤ 19 then            f := (b and c) or ((not b) and d)            k := 0x5A827999        else if 20 ≤ i ≤ 39            f := b xor c xor d            k := 0x6ED9EBA1        else if 40 ≤ i ≤ 59            f := (b and c) or (b and d) or(c and d)            k := 0x8F1BBCDC        else if 60 ≤ i ≤ 79            f := b xor c xor d            k := 0xCA62C1D6
        temp := (a leftrotate 5) + f + e + k + w        e := d        d := c        c := b leftrotate 30        b := a        a := temp
        h0 := h0 + a    h1 := h1 + b    h2 := h2 + c    h3 := h3 + d    h4 := h4 + e
digest = hash = h0 append h1 append h2 append h3 append h4

上述关于f表达式列于FIPS PUB 180-1中,以下替代表达式也许也能在主要循环里计算f

相关

  • 喉结喉结(adam's apple、laryngeal prominence、喉突出部),指人咽喉部位的软骨突起。人的喉咙由11块软骨作支架组成,其中最主要,体积最大的一块叫甲状软骨。胎儿在2个月时,喉软骨开始
  • 叶绿素ic1叶绿素 c1是六种叶绿素的其中一种,与叶绿素c2有相同的结构。它会使植物形成金黄色或棕色,并且是一种辅助色素。叶绿素c1主要帮助有机体收集光,但不是运用在光合作用上。
  • 中国进出口商品交易会展馆中国进出口商品交易会展馆(英语:China Import and Export Complex),简称广交会展馆(Canton Fair Complex),又名广州国际会议展览中心、广州国际会展中心、琶洲会展中心,位于中国广州
  • 提摩西·崔德威提摩西·崔德威(Timothy Treadwell,1957年4月29日-2003年10月5日),生于纽约长岛,美国自然保育人士、生态纪录片者,以爱好灰熊却被灰熊杀死闻名。1989年夏,崔德威首次到阿拉斯加旅行
  • 张添根张添根(1914年-1996年)生于日治台湾台中厅葫芦墩支厅栜东下堡(今台中市大雅区),为鸿禧企业集团、鸿禧美术馆、国产汽车股份有限公司创办人。1996年逝世于台北市,享寿82岁。1914年张
  • 金腰带金腰带可以指:
  • 阿拉伯叙利亚王国阿拉伯叙利亚王国是中东一个短暂存在的政权。叙利亚王国以费萨尔为国王,在阿拉伯民族主义思潮兴起,奥斯曼帝国衰落的背景下依托英国支持而建立,其目标是在大叙利亚地区建立一个
  • 闪击英雄《闪击英雄》(德语:Erinnerungen eines Soldaten,意为“一个士兵的回忆”;英文版翻译为Panzer Leader,意为“装甲指挥官”)是德意志第三帝国将军海因茨·古德里安的自传。 这本书
  • 斯泰茜·艾布拉姆斯斯泰茜·艾布拉姆斯(1973年12月9日 - )是美国政治家,律师,小说家和作家。2011年,他们当选为佐治亚州众议院的民主党代表。他于2018年在佐治亚的中期选举中成为民主党的州长候选人
  • 符腾堡的弗蕾德里克符腾堡的弗蕾德里克(德语:Friederike von Württemberg,1765年7月27日-1785年11月24日),符腾堡公爵腓特烈二世·欧根的次女。1781年,弗蕾德里克与欧登堡公爵腓特烈·奥古斯特一世的