1。写在前面，网络安全是一个很重要的领域，今天就和大家一起来了解密码相关的话题。每个人都熟悉密码。我们每个人都有一系列的密码：邮箱密码、社交网站密码、各种APP密码等等，密码就像是每个人网络的一把钥匙。对于我们的用户，我们尽量避免使用123qaz、qazwsx等不良密码，增加密码的复杂度，避免使用生日等基本信息作为密码，并定期修改密码，确保个人信息安全。对于功能服务商来说，密码的妥善保管和保管是一个非常重要的环节。一旦发生密码泄露等事故，影响较大，必须引起高度重视。然而，并非一切都如我们所料。互联网上用户敏感信息泄露事件比比皆是。前面已经铺垫过了，所以本文主题划定：通过本文，你将了解到：密码交互的基本流程密码的明文存储单向无盐哈希存储预计算哈希链集和彩虹表原理哈希+盐存储专业密码加密算法2.密码交互过程密码一般用于用户登录认证。完整的过程包括：用户输入密码、客户端加密、网络传输、服务器认证等。严格来说，每个环节都可能导致密码泄露，而且涉及的过程越多，出错的概率就越大。用户登录认证的基本步骤可以概括为：用户填写帐号、密码、验证码等信息；注册时填写的密码加密存储在数据库中并做持久备份，后续登录验证；服务器从数据库中获取用户名下的加密密码，并使用用户输入的相同加密过程计算结果，并将两者进行比较；如果两者相同，则用户有权登录。当然这里不考虑手机验证码等措施；如果两者不同，则提示失败并限制最大尝试次数；本文主要介绍服务器如何安全地存储密码。3.密码的明文存储这种明文存储密码的方法让人难以置信，但实际上有人这样做，比如直接在MySQL中明文存储密码，如图：一旦密码数据存储inplaintextis被拖到数据库中会导致很大的问题。一些私人小网站可能存在这种情况，所以在日常生活中一定要注意识别。我们认为这些网站的认知度不够，后台漏洞容易被不法分子利用造成泄密，当然也有少数知名站点存储纯文本的情况，所以我只能说我有点无语。现在密码太多了，很多人会在很多网站上使用1-2个常用密码，没有使用一定的规则或者工具，所以就出现了桶效应：只要一个网站的密码泄露，其他网站的密码就都泄露了它不再安全了。大锤密码太多记不住，干脆用一个密码注册登录了很多日常APP。有一天，他注册了一个破烂的小网站玩游戏，然后密码被泄露，他的其他常用应用程序面临被盗的风险。对于这个明文存储的案例，网上有人说灯下黑，让我感觉网剧看多了。我个人认为主要原因是缺乏认识。说到这里，让我想起有一次放假回老家，坐客车的路上还要加油。加油的时候，车里有人接听电话。不一会，车里的不少人就不高兴了，开始大吼大叫，让他别再打电话了。哈哈哈。4.单向无盐哈希存储在讲单向无盐哈希存储之前，先达成一个共识：我们常说的md5/sha其实是一种摘要算法，而不是加密算法。(1)摘要算法和加密算法加密算法和摘要算法有很大的区别。明文虽然变形了，但加密算法必须与解密算法对应，即输入值经过加密算法处理后才能使用。归约，但摘要算法一般被认为是单向不可逆的，没有办法轻易还原出原来的输入。图为加解密的可逆过程（注意加密后的密文是我随便写的）：图为摘要算法的不可逆过程（注意摘要的密文是我写的）：简单理解摘要算法和加密算法的区别接触过后，我们可以知道摘要算法是单向的。我只知道原始输入A的汇总输出是B，但是很难从B推导出A，就像你用一把锁和一把钥匙，却把钥匙扔进了茫茫大海。只能在不损坏盒子的情况下猛烈尝试。当你尝试第20200404把钥匙的时候，你发现它打开了，突然意识到，就是这把钥匙！(2)哈希碰撞与暴力破解前面提到了用钥匙开箱的问题，最后还是打开了。别高兴，原来的key可能不是这个，因为有hash冲突，巧合的是，可以打开。我们先看图：图中，我们对m个输入进行汇总计算后得到相同的汇总值，即开箱，但真正的输入是k。这导致了一个新问题：哈希冲突及其影响。那么什么是哈希冲突呢？为什么会冲突？我们知道摘要算法生成的字符串长度一般是固定的，比如128位和256位。摘要算法的神奇之处在于它可以将任意长度的数据转换为定长的字符串。换句话说，哈希字符串的长度是有限的，因此总集合是有限的。这是一个很容易想到的组合题，但是输入是无限的！极端一点，你写了一个长度为4的十六进制给digest算法，字符串只有65536个空格。其实输入样本的个数不需要65536，几乎不可避免会发生冲突，因为不冲突的要求很高。如果你不相信我，看看生日悖论问题。生日悖论是指不少于23个人中至少有两人生日相同的概率大于50%。例如，在一个有30名学生的小学班级中，有70%的概率有两个人的生日相同。对于一个60人的大班来说，这个概率大于99%。生日悖论不是引起逻辑矛盾意义上的“悖论”。但这个数学事实是如此违反直觉，以至于被称为悖论。应用生日悖论的数学理论设计了一种密码学攻击方法——生日攻击。想想也是一样。无限输入样本和有限抽象集合之间的冲突几乎是不可避免的：如果你还头晕，想想北京13号线的早高峰，车上10个人并不拥挤，瞬间来了200人.你说Nocrowding,noconflicts，如图：(3)One-waysalt-freehashstoragesecurity前面两节介绍了摘要算法和加密算法的区别，以及hash冲突，分别是非常中立。了解了这些必要的知识后，我们不禁要问：用单向无盐哈希存储密码安全吗？安全是相对的，没有绝对的安全。作为防御者，攻击者的时间和机器成本只能高到Unacceptable，我们更安全。也就是说，攻击者理论上可以破解我的密码，但这需要300年的时间，或者如果攻击者想要在可接受的时间内破解，那么他们必须找到一个天文数字的存储空间。作为后卫，你怕什么？害怕的！如果有一个可以被时空接受的方案呢？我们先把它卖了，然后我们将专注于这个可怕的权衡计划。A。在线加解密实验中常见的摘要算法md5和sha1的长度分别为128位和160位。这里的位是二进制的。转为十六进制后，长度分别为32位和40位。在长度上，sha1与md5相比，冲突更小，那就来试试sha1的破解速度吧！笔者随机找了一个网上的sha1加解密网站。这个网站的介绍看着挺厉害的，不过都是针对md5的。看来md5已经被嫌弃了：本站专门对md5等hash算法进行在线解密，可以上传文件进行在线批量破解，最多可以支持上万个密码。仅MD5就有超过3万亿条的64T密码数据库。本站支持十几种常用哈希算法在线解密，查询时间小于0.1秒。准备快速测试：加密很快完成，然后解密：啊，结果很快就出来了。之前跑了几次解密，现在要求登录显示。懒得登录了，不过确实解密成功了，0.01秒说的是真的。这怎么行，我再试试强密码：速度还是很快的，生成了一个长度为40位的十六进制小写字符串。作者还是很有信心的。时隔这么久来破解吧！啊哈哈……果然跪下了，原来提高密码强度是多么的重要啊！b.国内外凭证库研究山东大学王小云教授，我国著名密码学家，在2004年左右对md5和sha1进行了深入研究，取得了大量进展，所以现在对于一些对安全性要求高的场合，更高的摘要算法如：sha224，sha256，sha384，sha512等算法已经被使用，即长度更长，收集空间更大，碰撞池可能更小。Feelit这个长度的变化(左右滑动)：明文输入：1233445TGNVFsha1密文：fc58f924f193654f6388cac13b6061e99c7dbabcsha224密文：97cdfc11422a8311e812809711b3159c4530f5f183841f7fe111fd92sha384密文：2de74b23f770126eb51ec328f591c2290fd3bed8756d0e4dffa32af9296006444c334288bd820b1297d8087977131f0fsha512密文：96be48daec3779f6d83b991a4f281280884578b2b68a2cf5c481838e48c199c8795f89328a85f208d791465bad28acac440be3a1397eafb0bfefd60d6b9f8a9bGPU在进行密码破解领域有绝对的把控力，对于md5和sha1这些算法运算速度非常快，速度达到每秒1亿次，如果多组GPU串联解密，速度会更快。但就目前而言，sha224/256/385/512算法还是安全的。2017年，谷歌公布了其对sha1撞库的最新研究。基于此，它呼吁全球相关组织和公司对算法进行升级。图中显示了谷歌使用两个不同文件获取相同sha1的例子：虽然取得了撞库的进展，但谷歌付出的代价也是巨大的：攻击算法分为两个阶段，第一阶段取单CPU的话要6500年，第二阶段用单GPU要110年，可谓成本高。因此，如果我们使用单向无盐哈希来存储密码，我们应该避免使用已被广泛研究的短摘要，如MD5/sha-1，而使用sha-256这种更安全的摘要算法。比特币目前使用sha-256作为其相关算法。C。关于算法升级的思考更换更安全的摘要加密算法确实有一定的效果，但是算力的进步超出了我们的预料，就像md5和sha-1在刚开始应用的时候是现在的算力无法逾越的。但随着并行计算和量子计算的发展，sha-256/512等更安全的算法何时会被证明是不安全的还不得而知。但是，如果我只是想把我的自行车从摩托车上开出来怎么办？如何使用弱摘要算法如md5来实现强密码存储系统？面对这个简单的诉求，我们继续聊下去。5.彩虹桌攻击攻击是为了更好的防御，相互制约，共同成长。（1）暴力破解暴力破解一般可以分为计算暴力破解和查表暴力破解，如图：说彩虹表之前，先说说字典穷竭。长度为12位，包括字母、数字、特殊符号，这样我们就可以根据这个特性生成所有密码的全排列集，然后进行md5摘要计算得到一个哈希值，然后存储这个映射关系。用字典的方法暴力破解的时候，就像一个巨大的哈希表，可以很快的减少时间，但是随着加密算法的升级，密码复杂度的增加，字典会变得非常非常大，理论上是不能存储和使用的。人们努力寻找时间和空间之间的妥协——彩虹表，它让单一时间的不可接受，或单一空间的可接受。可以说是一件很有用的东西。当我第一次听到这个名字时，我感到很惊讶。为什么叫彩虹表。(2)空间存储效率问题在探索彩虹表之前，我们首先思考这样一个问题：如何用最少的存储空间表达最多的信息？C语言中的例子：想想我们在C语言中传递结构体或者数组，一般只传递首地址，其他元素可以根据首地址和偏移量访问，所以我们可以遍历所有变量同一个地址，存储效率非常高。二叉树的例子：二叉树的链式存储和顺序存储都可以使用根节点来实现对整棵树根据左右子节点关系的检索和遍历，这样我们只需要对外传递二叉树时需要给出根节点。不必全部提供。西游记例子：西游记的主角是师徒5人。白龙马就别想了……，我们可以存储这5个人的信息，但是感觉有点浪费，因为我们知道他们5个人之间是有关系的，存储一个就可以找到其他4个人了。图为全量存储5人信息的场景：图为利用师徒关系的部分存储：简单解释：只存储了唐僧，唐僧是根据获取孙悟空的入口他的大徒弟之间的关系，又从孙悟空根据师徒关系得到另外三个人，这个很像数据库的索引……画外音：有时候很多元素内部是相连的，我们不必须显示和存储所有这些信息，这会造成空间浪费，如果我们使用这些Intrinsicconnection可以使用少量数据作为入口来获取所有数据。这是一个想法！理解这个存储效率问题对理解彩虹表有很大的帮助。想象一下，字典穷尽是在所有的明文和密文之间建立一个映射，相当于把5个和尚师徒各自存储起来，但是如果我们找到一些明文之间的内在联系，我是否可以表达出它们之间的映射关系呢？明文和密文内部连接只存储少量明文？答案是肯定的，但彩虹表与明文的内在联系是基于数学的。下面我们继续探索，彩虹表H函数和R函数。(3)H函数和R函数读者们，坐稳了，打起精神来。H函数和R函数是理解彩虹表的关键。先解释一下H函数和R函数是什么以及它们的内部关系：H函数：H函数也是一种哈希函数，实现了明文到密文的单向不可逆转换；R函数：R函数理解为Reduction函数，看到这里说到Reduction这个词，其实在之前的P和NP问题的文章中，我们都接触过这个词，reduction/reduction的意思.H函数和R函数的关系：一句话：H函数的定义域就是R函数的定义域，H函数的定义域就是R函数的定义域，但是R不是反函数H的函数，因为H的函数是不可逆的。例如：如果密码范围是长度小于10的字母数字组合，且不区分大小写，假设输入明文为abcdfg，则存在如下关系：//哈希函数H实现明文到密文H(abcdfg)=AB8GFTYG//归约函数R实现了密文到'明文相同格式串'的映射R(AB8GFTYG)=erfdtk其中R函数将H函数的输出作为输入，即H的取值范围作为R域的取值，R函数生成erfdtk，一个新的明文串erfdtk，不是原来输入的明文，而是格式相同。在这里可以隐约感受到R函数的重要性。它可以将相同格式的明文生成的密文作为输入，然后输出新的相同格式的明文，从而生成一个相同格式的明文集合链，即找到一类具有内在联系的明文。也就是说，我们只能存储一个明文，将多个H-R串联起来，形成一个明文-密文映射集，即空间减少但信息量没有减少。看来R的功能确实很酷。画外音：这里提到的R函数生成相同格式的新明文。“相同格式”这个词不好理解，需要用数学的手段来实现。我们简单理解一下，长度和组合是相似的！(4)初步计算哈希链和R冲突在彩虹表出现之前，有一个预先计算好的哈希链集合，它是由多组哈希链组成的明文-密文集合。这里简单提一下。前面提到了一组H-R函数。事实上，只有多组H-R函数才有实际意义。例如，如果有2000组H-R组合，那么我们将有2000对明文-密文映射，但只需要存储非常少的一部分，也就是我们要说的哈希链。图中展示了一个由两组H-R函数组成的hash链：上图中两组H-R函数中的R是相同的，我们不能因为存在hash冲突。表示都是独立的明文，所以空间存储率打了折扣，看这张图：上面两条哈希链EDEDED和FEDECE分别通过R函数计算得到222和333，222通过H函数得到FEDEFE，然后R函数也得到333，这样两条哈希链重叠，即R函数冲突。//哈希链中的R函数冲突R(FEDECE)=333R(FEDEFE)=333更重要的是，这种冲突不容易被发现！为什么这么说呢，因为实际中只存储了hash链开头和结尾的两个明文，上图中间有R冲突，但是从重叠的起点来看，上链在下链的后面，下链会继续H-R函数的其余部分，最终生成尾明文为555，而上链生成的尾明文为444，实际存储中是这样的：//Hashchain1111->444//Hashchain2454->555即如果你设计k=2，即每组2个H-R函数，两条hash链可以代表8个明文，但实际上333和444是重复的，所以只有6个有效且不同的明文。由于尾部明文的不同，无法检测到这种重叠。一个均匀分布的R函数看起来很重要，但是要求在数千组H-R函数中完全不冲突是非常困难的，所以出现了多组R函数的新形式。画外音：多组R函数的思想和Bloomfilter的多组hash函数的思想很相似。你可能会问为什么不考虑H函数的冲突，因为H函数是我们需要破解的加密函数，它本身的冲突概率很低，不然也不用费那么大的力气搞一个彩虹表。(5)彩虹表的基本原理彩虹表针对哈希链集合R函数冲突造成的重叠引入了多组不同的R函数系列，使得一条链上各个位置的R函数不同，如图：需要注意的是，引入多个R函数还是不可避免的会产生冲突，但是这种情况下冲突的影响远小于hash链集合中单个R函数的影响，如图图为常见的彩虹表R函数冲突（黑色强调部分）：具体来说，不同位置存在冲突：/不同的s输入不同的R函数产生相同的明文R1(FEDECE)=333R2(FEDEFE)=333但是很快在接下来不同的R函数，在R3和R2的作用下，不会再出现重叠，对能覆盖的明文数量影响不大，只出现333个重叠，后续独立。极端情况下，同一位置的冲突是相同的，因为每个位置的R函数相同，所以最后的明文还是一样的，可以修正删除，减少冗余数据，如图图：综上所述，彩虹表引入了一组多个R函数，保证了在同一个位置发生R冲突时的检测删除，将不同位置R冲突的影响降到最低，相对于hash链集合有一些优势。读到这里，我们对它为什么叫彩虹表有了一种隐隐约约的感觉。大概意思是每组哈希链都有不同的R函数，像这样：(6)简单的攻击彩虹表的过程彩虹表涉及复杂的建表过程，以及不同格式和长度的密码以及不同的哈希函数会有不同的彩虹表。网上有一些现成的彩虹表。有兴趣的读者可以根据自己的情况下载一些彩虹表数据进行验证。100GB以上的实用彩虹表中说。要增加破解的概率，需要完整的彩虹表数据作为支撑。彩虹表的意义在于将计算暴力破解与空间枚举相结合。简单说一下彩虹表的攻击过程：假设有K组H-R函数组合，彩虹表以[head_string,tail_string]的格式存储，如图：假设给定的密文P位于H-R的最后一组，即第K个R函数R(P)=tail_string，如果彩虹表中存在tail_string，则从head_string计算；如果第K个R函数生成的结果不存在，则继续查找第K-1个R函数Calculate，直到最后得到tail_string，再判断是否存在；最坏的结果是第一个R函数计算到最后得到的tail_srting仍然不存在，说明这条链已经匹配失败；到这里，我们基本上有了彩虹表我对原理和流程有了一个粗浅的了解，但是彩虹表并不是无敌的，因为它有一个强大的对手[hash+salt]存储。6、hash+salt组合加密存储一直在讲无盐单向hash存储，但是什么是salt？简单的说，salt就是在用户输入密码的基础上额外增加的一部分数据，这部分数据也参与计算hash来存储密码。H(user_input_string+slat)=new_password就像做饭一样，给存储的密码加盐也是一门技术活。不禁要问：为什么加盐会使单向哈希变得如此强大？其实很简单，因为盐不知道怎么加，也不知道加什么！图为使用彩虹表破解明文登录失败的情况：暴力破解得到的密码为bnghuopyi99，输入后失败，因为用户输入的明文为nghuopyi，salt为b99，混合方法是将salt的第一个字符放在用户输入的顶部，然后将其余字符附加到bnghuopyi99。随意的盐分和不确定的添加方式，让彩虹表的威力大打折扣。换句话说，每个用户可能都有单独的混合方法，这大大增加了破解成本。目前看来，hash+salt的方式还是不错的，但这依然不是最优方案，我们继续往下看。7.专业的密码加密算法我们前面学习的一些算法，比如sha256，并不是为存储密码而设计的。相反，这些摘要算法都有其主要用途，不禁要问：有没有专门为密码设计的加密算法？？答案是肯定的。我们都知道GPU的性能很糟糕，计算速度非常快。想象一下，如果我们放慢加密算法的速度，攻击者的速度也会变慢。例如加密算法需要200ms完成加密存储。这个时间对于用户来说是可以接受的。接受了，但是对于攻击者来说时间成本非常高。听起来像是你故意打晕你的对手。本质上可以设置专业密码加密算法的强度，增加暴力破解的时间成本。比较常见的加密算法如下：bcrypt算法：bcrypt是专门为密码存储而设计的算法，设计的算法是基于Blowfish加密算法的变形，该算法于1999年由NielsProvos和DavidMazières发表在USENIX上。bcrypt的workfactor参数可以用来调整计算强度，workfactor包含在outputsummary中。随着攻击者计算能力的提高，用户可以逐渐增加工作因子PBKDF2算法：PBKDF2(Password-BasedKeyDerivationFunction)PBKDF2是多次重复计算saltedhash，可以设置这个数来提高加密性算法的时间。目前这两种算法都有Python和C/C++版本。有兴趣的读者可以试一试。从专业的角度来说，使用专业的密码加密算法是最好的解决方案。8.写在最后本文以熟悉的密码交互场景为出发点，讲解明文存储密码、单向无盐哈希存储、预计算哈希链集合、彩虹表、哈希+盐存储、专业密码算法存储等几个方面的相关知识。其中单向无盐哈希存储、彩虹表、哈希+盐存储的内容相对较多。由于涉及较多的数学背景知识，篇幅和本人水平有限，没有深入展开。从实用的角度来说，据说开发者推荐使用专业的密码加密算法，作为用户，也要提高密码意识。
