首页
阅读
  • 安全资讯
  • 安全知识
  • 安全工具
活动
招聘
安全导航
内容精选
  • 专栏
  • 精选专题
  • 安全客季刊
  • 360网络安全周报

密码学基本原理(上)

阅读量344559

发布时间 : 2018-06-08 16:15:24

连载系列——It works,why?
在做密码学相关项目的时候,经常可以看到很多程序员,对密码学有哪些技术,每个技术怎么用一无所知。在选择合适的密码学技能来达成目标的时候,总是选择自己最熟悉的方案,这不一定是最好的方案,甚至不一定是合格的方案。后果往往有两个:一个是很多代码潜伏着安全隐患;另一个则是,很多算法并不如想象中那样工作。我们时时可以见到程序员对着电脑沉思,这个算法不能工作,Why?又时时可以见到,这个算法能工作,Why?因此我将在「It works,why?」系列文章中,论述常见的算法和常见应用,其中的“Why”。


本文简述了传统密码学的常见算法和相关特征。

 

Digest

摘要为一个函数H,对任意数据d,有h=H(s)。同时至少满足下面特性1,其余特性为额外要求。

  1. 对相同的数据d1=d2,计算得到h1=H(d1)和h2=H(d2),必然有h1=h2,但不要求h1=h2的情况下,必然有d1=d2;
  2. 根据h计算任意一个可能的d极其困难(安全性);
  3. d服从随机分布的情况下,h的分布足够随机(均匀性)。

 

hash系列函数

hash系列中最著名的即MD5,其后继者为SHA1,SHA2,SHA3等,但实际上这几个都是密码学hash函数,非密码hash常用于快速计算均匀散列值(例如hashtable),代表有CRC (实际上CRC主要的目地是校验,而不是散列), FNV,Murmur。

以上几个非密码hash函数的对比可以看这里: https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed#145633 。

hash函数需要注意长度。一般来说,长度越长越安全(越难被找到一个碰撞值),但是过于长的值会在保存和使用上产生困难。

 

Rainbow table

Rainbow table是一种通过预先计算来碰撞的手段。

从粗略的角度来说,你可以认为这就是一个巨大的反向hash表,保存了所有计算过的hash和对应的碰撞数据,但通过计算可知,这样的反向表会占用巨大的存储空间。

而彩虹表采用巧妙的算法缩减了空间消耗。其基础思想是,对某个碰撞数据,计算其hash,随后通过某个算法R,将这个目标hash再映射到另一个碰撞数据上去。通过这种方式,一个碰撞数据可以持续的计算出一串不同的hash,假设这个长度为n,我们最后保留最终一个hash和最初一个碰撞数据。

在检索某个hash的原始碰撞数据时,我们可以利用R将其映射为碰撞数据(但不是我们需要的那个碰撞数据),进而计算hash串并检测是否在反向表里。如果表里存在这个hash的碰撞数据,那么在生成n步的hash串的过程中,必然能在反向表里发现命中,而当发现命中后,就可以通过原始碰撞数据算出整个碰撞链,从而找到该hash的对应碰撞数据。

从算法分析的角度来说,这是一个空间换时间和时间换空间同时存在的巧妙算法,利用反向表计算原始碰撞是用空间换时间,用hash串来压缩空间消耗是用时间换空间。

另一个细节是hash链的碰撞。当hash链在某个节点相同,后续链条必然完全相同。这大大降低了hash串的效率,因此彩虹表采取了一个变形,算法R在n步中每一步都各不相同(实际一般是将n当作参数),这样使得hash碰撞只发生在一个点上,由于算法在每个步骤上各自不一,因而得名彩虹表。

 

KDF

密钥生成算法( KDF )是一类算法的统称,用于将一个密码/密钥变换成另一个(或多个)密码/密钥。在这个过程中,会提供很多额外特性,例如:符合特定格式、防御暴力穷举攻击、保存后难于破解原始密码等。

KDF的最知名场景,就是密码保存问题。用户的密码不应直接保存,这样在万一数据库泄漏时就会泄漏原始密码,而单纯hash会导致用户密码遭受彩虹表攻击,一般解决这个问题的方法是对密码加盐。

但是盐是加在前面还是后面呢?以我个人的分析来看,似乎是没有区别的。即s+salt和salt+s都能保证安全,当然,更好的方法是用scrypt或bcrypt,他本身就有专门的函数保证密码安全保存,这可比加盐好使多了。

 

最佳实践

相信大部分读者都可能知道MD5和SHA1不安全的事了,这两者虽然还能完成摘要的用途,但是并没有安全保证了。如果你需要一个安全的hash算法,我推荐sha2,sha3目前并没有进入主流系统,而且执行速度还是略慢。

另外,如果可以选择的话,在sha2算法族里我推荐SHA-512/256或SHA-512/224,这两个算法有助于避免长度扩展攻击。

 

Encryption and Decryption

对称加密解密为一对函数,加密为E,解密为D。对任意数据d和密钥p,满足下面要求1和2。

  1. 加密为e=E(d, p),解密为d=D(e, p);
  2. 攻击者得知E,D,e的情况下,无法反推d和p;
  3. 在条件2的基础上,攻击者能得知d和对应e的情况下,无法反推p(已知明文攻击);
  4. 在条件2的基础上,攻击者能构造d并得知对应e的情况下,无法反推p(选择明文攻击)。

对称加密有几种可能的变形情况,例如E和D为同样的函数,一次加密第二次解密,或者由生成算法构造出密钥p和解密密钥p’,在其中密钥p可以推算变换为解密密钥p’,但这其实仍然符合上面的描述。因为解密时可以使用d=D(e, p’),而p’=G(p),因此d=D(e, G(p)),即可认为d=D’(e, p)。对于密钥p无法推算出解密密钥p’的情况,请参考下面的“非对称加密”。

 

DES/AES加密解密算法

加密算法中最有名的是DES和AES。关于这两个,我们不赘述。

 

密码模式

加解密算法一般都是以块模式运作的。即每个加密算法都有一个特定的长度,他只能处理这个长度的数据。块密码模式算法将基于某个特定的块算法,将其应用于流上。

最简单的用法是重复进行加密。取明文的前N字节加密,得到N字节密文,重复直到得到最后一块数据,数据的长度必然大于0小于N,对尾部的数据补足0,最后将所有密文联合起来,得到最终密文,这种模式叫做ECB模式。

ECB模式的好处是简单,但ECB并不能防御内容替换攻击。攻击者可以通过某种方式获得一个数据的加密形式(选择明文)B’,然后将某个加密后的块B’替换原始块B。以此,虽然攻击者并不知道原始内容,但是可以替换其中的部分内容。

人们对ECB做了一点改进,使用上一个块的加密结果,对下一个块做干扰(具体使用XOR),如此一来,对任意一个块的变更会导致后续块全部都无法解密。第一个块没有上一个块,也就没有加密结果,所以CBC需要一个初始向量IV来初始化干扰,而先加密上一个块的结果,再和当前数据XOR的算法,被称为CFB。CFB和CBC仅仅顺序上有区别,但是CFB可以用于流式加密,而CBC不行,因为CBC必须得到一个完整块,才能计算加密,而CFB是预先算出mask,用XOR获得结果。

CFB再略变化一点,就可以构成OFB。OFB取的是XOR前的结果,因此加密序列并不受明文的影响,只受IV和key的影响。你可以想像,OFB是一个由IV和key已经决定好的,无限长的mask,逐步XOR到明文上。

但是CFB和OFB都有一些缺陷,例如明文和密文的异或对应性。在确定模式为CFB或OFB的前提下,对某些特定位置遍历所有可能空间,就能在不了解解密结果的前提下遍历所有明文可能性。这个问题被用于ss的主动探测上。

 

Salsa20

Salsa20原来叫Chacha20,是一种经过特别设计的密码系统,在未经优化的CPU上拥有非常快的执行速度。

 

最佳实践

可能和大家想像的相反,一般没事不会推荐直接使用加密函数本身,而是推荐使用AEAD算法。这里有一份2015年密码学最佳实践,按照推荐,是使用AES-GCM或Chacha20-Poly1305最好,这两种都是AEAD。

如果一定要用加密算法,而非AEAD的话,推荐使用NaCl( https://nacl.cr.yp.to/stream.html ),它的加密算法默认选择是XSalsa20/20(Salsa20的一个变形)。

 

Message authentication code

消息验真,不同于摘要,要求的是拦截者无法伪造,其前提条件是发送者和验证者有一个共同的秘密p。本质上看,这个就是签署(sign),但是一般我们讲sign都是指非对称的sign,MAC是对称式的,对称签署为两个函数,签署为S,校验为V,对任意数据d和密钥p。

  1. 对于签署获得的v=S(d, p),可以用V(d, v, p)来检验d和v是否成对;
  2. 攻击者在得知S,V,v,d的情况下,无法反推p。

签署算法经常和摘要算法合用,即对数据d先使用摘要H得到摘要,再计算签署,即v=S(H(d), p),验证时使用V(H(d), v, p)来验证。

主流消息验证算法往往会使用hash或加密算法来完成。

 

HMAC签署算法

HMAC( https://en.wikipedia.org/wiki/HMAC )算法是对称签署中最著名的一个系列,HMAC不是一个算法,而是一类算法,这个算法基于一个hash函数(而且显然,要求是安全的hash函数),根据hash选择不同,HMAC也会有所不同。HMAC的基本想法是,将p拼接在数据d前面,做hash。根据安全的hash函数的性质,攻击者无法从v反推原始数据,即使他们拥有部分的明文(被签署数据d),而在不知道p的前提下,也无法构造出签名v。细节来说,HMAC要求对密钥p进行变形,得到两个密钥,并重复“拼接-hash”过程两次。

 

CMAC系列

MAC系列的介绍可以看这里: https://en.wikipedia.org/wiki/Message_authentication_code 。这里我们特别介绍一下CBC-MAC这种算法。这种算法是使用加密算法来完成验证的典型代表,拥有很多衍生,例如OMAC/CMAC/XMAC等。

上面我们简要介绍过CBC,这个模式循环使用前面块的数据来扰乱下一个块,然后再完成加密,而CBC-MAC通过密钥构造一个k1,配合IV=0来计算输出,取最后一个块输出,再用密钥构造一个k2,加密最后一个块,形成MAC数据。基于基本知识我们知道,对任意一个数据输入改变,最后的输出会发生变化,并且在没有密钥时无法构造MAC数据。

 

最佳实践

首先,最普及的算法是HMAC,有条件的话尽量选择这种。

既然MD5和SHA1不安全了,那么尽量不要选择HMAC-MD5和HMAC-SHA1,尽管我只看到了SHA1碰撞的实例报告,还没见过HMAC-SHA1的。但是还是尽量不要冒险,使用HMAC-SHA2。

另一个就是,不要试图自己实现MAC算法,这类算法实现的难度比你想象的要高很多,如果你需要的话,推荐使用NaCl。

 

AEAD

AEAD是近代的一个密码模式,主力解决这么一个问题。我们上面介绍了加密和MAC,但是在日常使用中,我们既需要加密,也需要MAC,例如Alice可能写了一封情书给Bob,那么,她同时需要保证情书不会被第三方看到(加密),又要保证Bob不会以为她写了一堆乱码(签署验真),虽然听起来很愚蠢,正常人看到一堆乱码的时候,当然知道是被人替换了,但我们就当作Bob是一个智商不足的傻瓜(恋爱中的人都是傻瓜)。

解决这个需求,我们有三种模式。

Encrypt-then-MAC (EtM),首先加密,然后用另一个密钥对密文进行签署;

Encrypt-and-MAC (E&M),首先加密,同时用同一个密钥对明文进行签署;

MAC-then-Encrypt (MtE),首先签署,然后用同一个密钥对总和数据进行加密。

然后,据说这些模式都是有缺陷的。缺陷具体笔者未参透。有兴趣的朋友,这里有本九阳神功( https://cseweb.ucsd.edu/~mihir/papers/oem.pdf )送给你,欢迎交流。

总之,为了解决上面的问题,产生了一个新的概念,AEAD( https://en.wikipedia.org/wiki/Authenticated_encryption )。在一个算法中进行加密和验证。

 

GCM

GCM是一种CTR算法。CTR是一种密码模式,这种模式利用数据的块计数作为扰动变量,来使得同样的输入不产生同样输出。这样做的最大好处在于,每个块的计算彻底变成了互相不关联的过程,因而可以在分布式系统上进行计算。其他模式,即便是OFB,其输出流也是串行的。当输入速度高于mask流时,就会出现算法无法利用CPU的问题。

http://blog.csdn.net/t0mato_/article/details/53160772

最佳实践

AEAD的选择不算太多,这份推介( https://www.cnblogs.com/windydays/p/2015_modern_crypto_practice.html )上推荐的是使用AES-GCM或Chacha20-Poly1305。NaCl的默认选择是XSalsa20-Poly1305。预订要有AES256GCM,但是目前未实现。

Public-key cryptography

公钥密码体系是一个非常复杂的系统,这个系统基本涵盖以下几个领域:

key exchange

public key encryption

public key signature

 

Key exchange

密钥协商,也叫密钥交换 ,简称Kx,为一个过程。假设Alice和Bob可以通讯,此时算法需要确定一个协商序列同时满足:

  1. Alice和Bob能够得到一个共享的秘密s;
  2. 可以监听通讯内容的监听者Eve无法通过监听内容推算出s;
  3. 前向安全。所谓前向安全,指未来的密钥泄漏不会泄漏之前的通讯内容(可选要求)。

注意,虽然被动式的Eve并不一定能够躲避序列,但是主动攻击者Mallory是一定可以截听内容的,无论协商算法如何复杂,Mallory可以分别和Alice和Bob进行协商过程,使得Alice相信自己是Bob,Bob相信自己是Alice。(MITM attack)这个攻击无法通过密钥协商机制进行躲避,需要在密钥协商之上进行身份交叉认证才行。

Public-key encryption

公钥加解密为三个函数:生成为G,加密为E,解密为D。对任意数据d,满足下面要求1-3:

  1. G可以生成私钥和公钥,即s,p=G(),其中s为私钥,p为公钥。公钥可以公开;
  2. 加密为e=E(d, p),解密为d=D(e, s);
  3. 攻击者在得知G,E,D,p,e的情况下,无法反推s和d。

注意,关于p和s只是说,p无法推出s,并没有说,通过s可以推出p,只要通过函数G能够生成成对的s和p即可。ECC和DH体系中可以用s推导出p,但是RSA中单有s是不行的,实际是通过另两个数(质数pq)生成,两者无法互相推导。


【It works,why?】系列更多内容,请见饿了么SRC微信公众号!

天下网TXWEB四平建网站报价光明阿里店铺运营报价南阳seo按天计费多少钱惠州市网站搭建价格乌海市网站开发推荐商洛seo价格中卫市网页制作报价湛江市网站建设价格锦州市seo按天计费哪家专业保定做网站公司天水建网站多少钱芜湖市网站定制公司抚州市seo按天计费哪家专业芜湖优化推荐宜春市做网站推荐延安市阿里店铺运营宁德网站设计多少钱榆林市企业网站改版多少钱三亚网站搭建宁德做网站哪家好南山阿里店铺运营报价山南市模板网站建设多少钱茂名品牌网站设计价格吉安市网页制作东营市网页制作推荐舟山企业网站建设推荐肇庆市品牌网站设计价格黄石阿里店铺运营价格乐山市seo按天计费鸡西市模板网站建设价格香港通过《维护国家安全条例》两大学生合买彩票中奖一人不认账让美丽中国“从细节出发”19岁小伙救下5人后溺亡 多方发声卫健委通报少年有偿捐血浆16次猝死汪小菲曝离婚始末何赛飞追着代拍打雅江山火三名扑火人员牺牲系谣言男子被猫抓伤后确诊“猫抓病”周杰伦一审败诉网易中国拥有亿元资产的家庭达13.3万户315晚会后胖东来又人满为患了高校汽车撞人致3死16伤 司机系学生张家界的山上“长”满了韩国人?张立群任西安交通大学校长手机成瘾是影响睡眠质量重要因素网友洛杉矶偶遇贾玲“重生之我在北大当嫡校长”单亲妈妈陷入热恋 14岁儿子报警倪萍分享减重40斤方法杨倩无缘巴黎奥运考生莫言也上北大硕士复试名单了许家印被限制高消费奥巴马现身唐宁街 黑色着装引猜测专访95后高颜值猪保姆男孩8年未见母亲被告知被遗忘七年后宇文玥被薅头发捞上岸郑州一火锅店爆改成麻辣烫店西双版纳热带植物园回应蜉蝣大爆发沉迷短剧的人就像掉进了杀猪盘当地回应沈阳致3死车祸车主疑毒驾开除党籍5年后 原水城县长再被查凯特王妃现身!外出购物视频曝光初中生遭15人围殴自卫刺伤3人判无罪事业单位女子向同事水杯投不明物质男子被流浪猫绊倒 投喂者赔24万外国人感慨凌晨的中国很安全路边卖淀粉肠阿姨主动出示声明书胖东来员工每周单休无小长假王树国卸任西安交大校长 师生送别小米汽车超级工厂正式揭幕黑马情侣提车了妈妈回应孩子在校撞护栏坠楼校方回应护栏损坏小学生课间坠楼房客欠租失踪 房东直发愁专家建议不必谈骨泥色变老人退休金被冒领16年 金额超20万西藏招商引资投资者子女可当地高考特朗普无法缴纳4.54亿美元罚金浙江一高校内汽车冲撞行人 多人受伤

天下网TXWEB XML地图 TXT地图 虚拟主机 SEO 网站制作 网站优化

本文由本地生活安全响应中心原创发布

转载,请参考 转载声明,注明出处: https://www.anquanke.com/post/id/147255

安全客 - 有思想的安全新媒体

分享到:微信
  • 密码学
  • 技术分享
+14赞
收藏
本地生活安全响应中心
分享到:微信

发表评论

本地生活安全响应中心

这个人太懒了,签名都懒得写一个

  • 文章
  • 17
  • 粉丝
  • 8

TA的文章

  • 活动 | 完美收官,本地生活安全沙龙成功举办!

    2020-01-13 18:30:47

  • 活动 | 饿了么+口碑,本地生活SRC官宣!

    2019-07-09 17:30:54

  • 活动|饿了么SRC端午“集市”来啦!

    2019-06-01 21:04:14

  • 活动|本地生活安全沙龙—上海站,等你加入!

    2019-05-17 18:28:04

  • 众测|饿了么合作伙伴众测活动第二期开启!

    2019-04-25 18:30:13

相关文章

  • 如何通过 5 个步骤阻止 DDoS 攻击

    2024-02-05 11:05:24

  • 【AI首战】仅需一分钟,360安全智能体(AI Agent)完成了智能化APT猎杀

    2024-01-26 12:03:36

  • 可以装进口袋的强大网络武器

    2024-01-22 11:44:31

  • GrapheneOS 团队建议通过设置自动重启智能手机来对抗黑客攻击

    2024-01-16 10:45:55

  • 针对 Wi-Fi 网络的 5 种最危险的攻击

    2024-01-04 12:17:06

  • 恶意软件能否绕过沙箱?它们是如何做到的?

    2024-01-03 12:05:30

  • ASP.NET 中的 AsyncRAT:黑客如何通过两次点击绕过防病毒保护并秘密收集密码

    2023-12-13 11:11:30

热门推荐

文章目录
  • Digest
  • hash系列函数
  • Rainbow table
  • KDF
  • 最佳实践
  • Encryption and Decryption
  • DES/AES加密解密算法
  • 密码模式
  • Salsa20
  • 最佳实践
  • Message authentication code
  • HMAC签署算法
  • CMAC系列
  • 最佳实践
  • AEAD
  • GCM
  • 最佳实践
  • Key exchange
安全客
  • 关于我们
  • 联系我们
  • 用户协议
商务合作
  • 合作内容
  • 联系方式
  • 友情链接
内容需知
  • 投稿须知
  • 转载须知
  • 官网QQ群8:819797106
  • 官网QQ群3:830462644(已满)
  • 官网QQ群2:814450983(已满)
  • 官网QQ群1:702511263(已满)
合作单位
  • 安全客
  • 安全客
Copyright © 北京奇虎科技有限公司 360网络攻防实验室 安全客 All Rights Reserved 京ICP备08010314号-66

天下网TXWEB四平建网站报价光明阿里店铺运营报价南阳seo按天计费多少钱惠州市网站搭建价格乌海市网站开发推荐商洛seo价格中卫市网页制作报价湛江市网站建设价格锦州市seo按天计费哪家专业保定做网站公司天水建网站多少钱芜湖市网站定制公司抚州市seo按天计费哪家专业芜湖优化推荐宜春市做网站推荐延安市阿里店铺运营宁德网站设计多少钱榆林市企业网站改版多少钱三亚网站搭建宁德做网站哪家好南山阿里店铺运营报价山南市模板网站建设多少钱茂名品牌网站设计价格吉安市网页制作东营市网页制作推荐舟山企业网站建设推荐肇庆市品牌网站设计价格黄石阿里店铺运营价格乐山市seo按天计费鸡西市模板网站建设价格香港通过《维护国家安全条例》两大学生合买彩票中奖一人不认账让美丽中国“从细节出发”19岁小伙救下5人后溺亡 多方发声卫健委通报少年有偿捐血浆16次猝死汪小菲曝离婚始末何赛飞追着代拍打雅江山火三名扑火人员牺牲系谣言男子被猫抓伤后确诊“猫抓病”周杰伦一审败诉网易中国拥有亿元资产的家庭达13.3万户315晚会后胖东来又人满为患了高校汽车撞人致3死16伤 司机系学生张家界的山上“长”满了韩国人?张立群任西安交通大学校长手机成瘾是影响睡眠质量重要因素网友洛杉矶偶遇贾玲“重生之我在北大当嫡校长”单亲妈妈陷入热恋 14岁儿子报警倪萍分享减重40斤方法杨倩无缘巴黎奥运考生莫言也上北大硕士复试名单了许家印被限制高消费奥巴马现身唐宁街 黑色着装引猜测专访95后高颜值猪保姆男孩8年未见母亲被告知被遗忘七年后宇文玥被薅头发捞上岸郑州一火锅店爆改成麻辣烫店西双版纳热带植物园回应蜉蝣大爆发沉迷短剧的人就像掉进了杀猪盘当地回应沈阳致3死车祸车主疑毒驾开除党籍5年后 原水城县长再被查凯特王妃现身!外出购物视频曝光初中生遭15人围殴自卫刺伤3人判无罪事业单位女子向同事水杯投不明物质男子被流浪猫绊倒 投喂者赔24万外国人感慨凌晨的中国很安全路边卖淀粉肠阿姨主动出示声明书胖东来员工每周单休无小长假王树国卸任西安交大校长 师生送别小米汽车超级工厂正式揭幕黑马情侣提车了妈妈回应孩子在校撞护栏坠楼校方回应护栏损坏小学生课间坠楼房客欠租失踪 房东直发愁专家建议不必谈骨泥色变老人退休金被冒领16年 金额超20万西藏招商引资投资者子女可当地高考特朗普无法缴纳4.54亿美元罚金浙江一高校内汽车冲撞行人 多人受伤

天下网TXWEB XML地图 TXT地图 虚拟主机 SEO 网站制作 网站优化