【转】哈希碰撞与生日攻击

最近在思考关于哈希表二次探测再散列后如何查找的问题。暂时没找到解释。先转一篇有趣的科普文,以供后续研究。

原文来自: http://www.ruanyifeng.com/blog/2018/09/hash-collision-and-birthday-attack.html

一、哈希碰撞是什么?

所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称”哈希值”)。它是最常见的软件运算之一。

如果不同的输入得到了同一个哈希值,就发生了”哈希碰撞”(collision)。

举例来说,很多网络服务会使用哈希函数,产生一个 token,标识用户的身份和权限。


AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8

上面这个字符串就是一个哈希值。如果两个不同的用户,得到了同样的 token,就发生了哈希碰撞。服务器将把这两个用户视为同一个人,这意味着,用户 B 可以读取和更改用户 A 的信息,这无疑带来了很大的安全隐患。

黑客攻击的一种方法,就是设法制造”哈希碰撞”,然后入侵系统,窃取信息。

二、如何防止哈希碰撞?

防止哈希碰撞的最有效方法,就是扩大哈希值的取值空间。

16个二进制位的哈希值,产生碰撞的可能性是 65536 分之一。也就是说,如果有65537个用户,就一定会产生碰撞。哈希值的长度扩大到32个二进制位,碰撞的可能性就会下降到 4,294,967,296 分之一。

更长的哈希值意味着更大的存储空间、更多的计算,将影响性能和成本。开发者必须做出抉择,在安全与成本之间找到平衡。

下面就介绍,如何在满足安全要求的前提下,找出哈希值的最短长度。

三、生日攻击

哈希碰撞的概率取决于两个因素(假设哈希函数是可靠的,每个值的生成概率都相同)。

  • 取值空间的大小(即哈希值的长度)
  • 整个生命周期中,哈希值的计算次数

这个问题在数学上早有原型,叫做”生日问题“(birthday problem):一个班级需要有多少人,才能保证每个同学的生日都不一样?

答案很出人意料。如果至少两个同学生日相同的概率不超过5%,那么这个班只能有7个人。事实上,一个23人的班级有50%的概率,至少两个同学生日相同;50人班级有97%的概率,70人的班级则是99.9%的概率(计算方法见后文)。

这意味着,如果哈希值的取值空间是365,只要计算23个哈希值,就有50%的可能产生碰撞。也就是说,哈希碰撞的可能性,远比想象的高。实际上,有一个近似的公式。

上面公式可以算出,50% 的哈希碰撞概率所需要的计算次数,N 表示哈希的取值空间。生日问题的 N 就是365,算出来是 23.9。这个公式告诉我们,哈希碰撞所需耗费的计算次数,跟取值空间的平方根是一个数量级。

这种利用哈希空间不足够大,而制造碰撞的攻击方法,就被称为生日攻击(birthday attack)。

四、数学推导

这一节给出生日攻击的数学推导。

至少两个人生日相同的概率,可以先算出所有人生日互不相同的概率,再用 1 减去这个概率。

我们把这个问题设想成,每个人排队依次进入一个房间。第一个进入房间的人,与房间里已有的人(0人),生日都不相同的概率是365/365;第二个进入房间的人,生日独一无二的概率是364/365;第三个人是363/365,以此类推。

因此,所有人的生日都不相同的概率,就是下面的公式。

上面公式的 n 表示进入房间的人数。可以看出,进入房间的人越多,生日互不相同的概率就越小。

这个公式可以推导成下面的形式。

那么,至少有两个人生日相同的概率,就是 1 减去上面的公式。

五、哈希碰撞的公式

上面的公式,可以进一步推导成一般性的、便于计算的形式。

根据泰勒公式,指数函数 ex 可以用多项式展开。

如果 x 是一个极小的值,那么上面的公式近似等于下面的形式。

现在把生日问题的1/365代入。

因此,生日问题的概率公式,变成下面这样。

假设 d 为取值空间(生日问题里是 365),就得到了一般化公式。

上面就是哈希碰撞概率的公式。

六、应用

上面的公式写成函数。


const calculate = (d, n) => {
  const exponent = (-n * (n - 1)) / (2 * d)
  return 1 - Math.E ** exponent;
}

calculate(365, 23) // 0.5000017521827107
calculate(365, 50) // 0.9651312540863107
calculate(365, 70) // 0.9986618113807388

一般来说,哈希值由大小写字母和阿拉伯数字构成,一共62个字符(10 + 26 + 26)。如果哈希值只有三个字符的长度(比如abc),取值空间就是 62 ^ 3 = 238,328,那么10000次计算导致的哈希碰撞概率是100%。


calculate(62 ** 3, 10000) // 1

哈希值的长度增加到5个字符(比如abcde),碰撞的概率就下降到5.3%。


calculate(62 ** 5, 10000) // 0.05310946204730993

现在有一家公司,它的 API 每秒会收到100万个请求,每个请求都会生成一个哈希值,假定这个 API 会使用10年。那么,大约一共会计算300万亿次哈希。能够接受的哈希碰撞概率是1000亿分之一(即每天发生一次哈希碰撞),请问哈希字符串最少需要多少个字符?

根据上面的公式倒推,就会知道哈希值的最短长度是22个字符(比如BwQ1W6soXkA1PU120r0yMA),计算过程略。

22个字符的哈希值,就能保证300万亿次计算里面,只有1000亿分之一的概率发生碰撞。常用的 SHA256 哈希函数产生的是64个字符的哈希值,每个字符的取值范围是0~9和a~f,发生碰撞的概率还要低得多。

七、参考链接

给网站添加https安全证书

众所周知,Chrome的68版会将未使用 https 加密的网站标记为「不安全」。可以说 Google 是在不遗余力地推广传输层安全协议。 响应 Google 的号召。当我得知 https 证书也有一些免费版本可用时,就决定给自己的博客加上 https。 略过各种方案的比较和选择,这里直接记录(我认为)个人博客网站添加 https 证书的最佳实践:

服务器添加安全证书

我参考了这篇:Let’s Encrypt 给网站加 HTTPS 完全指南 但你不用按那篇文章里的步骤来,因为它已经是2年前的文章了,现在可是8102年,事情变得很简单: 只需在服务器上安装 certbot, 它自动帮你完成一系列的证书配置和验证操作。(需要对服务器有足够权限) 网址在:https://certbot.eff.org/ 我选择了 Apache on Ubuntu 16.04 (xenial) ,页面的提示如下: 不一定跟我一样,选择你自己的操作系统服务器软件,certbot 页面上会提供对应的安装方法。 安装后继续按照 certbot 页面的说明 get start ,程序的交互式界面会引导你进行选择和配置。 跟随引导进行操作,完成后网站就被 Let’s Encrypt 提供的 SSL/TLS 证书保护起来了。是不是很有安全感!
(完成证书配置后,certbot 会提示你到 https://www.ssllabs.com/ssltest/index.html 网站去检测 SSL web server 的安全性。最终的评价等级其实取决于你的证书授权机构、它使用的加密协议、能被哪些平台兼容… 作为安全通信方面的小白,我其实不太清楚怎么去确认自己的网站足够安全。这个检测至少提供了一些有效参考信息。) 由于 Let’s Encrypt 提供的免费证书只有3个月有效期,每次到期前需要 renew。certbot 支持自动 renew。 关于 renew 的 config ,你能在 /etc/letsencrypt/renew/ 路径下找到。用下面这个命令测试自己的 renew 设置是否有效:
sudo certbot renew --dry-run

一点清扫工作

现在你应该能通过前缀 https:// 的网址来访问自己的网站了。再回头试一下 http:// 访问,看会不会自动跳转到 https:// 。(如果没有,就要检查网站的重定向设置了) 不过,你也许会遇到,其他的 https 网站在浏览器里都有一把小绿锁显示,为什么我的网站只有小灰锁呢? 在浏览器的小锁(或灰色叹号)上点击,可以看到它对网站潜在隐患的提示。 对于个人博客来说,问题通常出现在站内的图片和链接上。它们的地址可能不是 https 的,没有被 SSL/TLS 保护,所以会被中间人截获。
参考这篇这篇文章,可以编辑当前 WordPress 主题下的 function.php 文件,强制将站内图片的地址转换为 https : 在 function.php 文件的尾部添加以下代码(修改其中两处 YOUR_DOMAIN 为你自己的域名)
/* 替换图片链接为 https */
function my_content_manipulator($content){
    if( is_ssl() ){
        $content = str_replace('http://www.YOUR_DOMAIN.com/wp-content/uploads', 'https://www.YOUR_DOMAIN.com/wp-content/uploads', $content);
    }
    return $content;
}
add_filter('the_content', 'my_content_manipulator');
若还有错,参照这篇文章,利用浏览器的功能来排查错误。 找到错误原因后:如果是通向站外的链接,直接把它们改成 https 就行了(现在几乎所有正经网站都支持https了)。 如果是 WordPress 插件的问题,找找插件设置里能否修改相关地址。插件不支持的话,就看你愿不愿意忍痛寻找替代品了。

Python Tkinter 进阶实践

之前简单介绍过Tkinter:Python 可视化图形界面简单实践
这次来记点进阶心得。


Tkinter实现标签页效果

用 Python 和 Tkinter 写过一些小工具。现在想把它们整合到一起,以类似“标签页”的形式来切换。

具体参考:Tkinter 8.5 reference: a GUI for Python
用到的是 Notebook 控件,这方面网上比较少提,所以记录一下。

举例:

MyNotebook1 = Notebook(top)
MyNotebook1.place(relx=0.022, rely=0.062, relwidth=0.956, relheight=0.876)

之后你就可以将 Notebook 作为 parent 来构建 Frame,承载你的标签页:

Tab1 = Frame(MyNotebook1)
....
MyNotebook1.add(Tab1, text='First tab name')

与普通的 Frame 不同,完成构建的 Tab1 不是通过 pack、grid、place 来布局,而是用 Notebook 的 add 方法,并指定标签名。

再来一个例子:

#about tab
self.TabX = Frame(self.Notebook1)
self.TabXLbl = Label(self.TabX, text="Listen's Swiss Army knife")
self.TabXLbl.pack()
self.TabXLb2 = Label(self.TabX, text="ver 1.3.0")
self.TabXLb2.pack()
self.Notebook1.add(self.TabX, text='About')
#about tab end

上面这个标签页实际效果大致是:

简单来说,你只要先建立了 Notebook 控件,然后往里面 add Frame 就行了,每个 Frame 都会呈现为1个独立的标签页,名字在 add 时指定。


GUI 界面与逻辑分离

如果只是一个功能简单的小工具,随便怎么写都没问题。但我在把多个小工具整合成一套时发现,东西一多了会很难管理。
在网上看到别人的做法,是将界面和逻辑分离开:

class Application_ui(Frame):
#这个类仅实现界面生成功能,具体事件处理代码在子类Application中。
def __init__(self, master=None):
Frame.__init__(self, master)
self.master.title("Listen's Victorinox")
self.master.geometry('880x380')
self.createWidgets()

def createWidgets(self):
....

class Application(Application_ui):
#这个类实现具体的事件处理回调函数。界面生成代码在Application_ui中。
def __init__(self, master=None):
Application_ui.__init__(self, master)
....

上面的做法是从 TK 继承了 Frame,然后重写成自己的 UI (Application_ui)。这个 Application_ui 只生成界面,之后再用 Application 类去继承它,在 Application 里面进行逻辑处理。

单独调试 UI :

if __name__ == "__main__":
top = Tk()
Application_ui(top).mainloop()

这样的好处是,在设计 UI 时,可以只考虑控件和布局。若画面呈现不如预期,就可以直接调整。

而 UI 里的每个控件其实都是空的,它们不实现任何功能,功能都在 Application 类里去添加。
例如:

self.Tab1varWL = StringVar()
self.Tab1varWL.set("WL")
self.TabStrip1__Tab1WLNum['textvariable'] = self.Tab1varWL
self.TabStrip1__Tab1WLNum.bind("Return",self.WL2Page)

self.TabStrip1__Tab1WLNum 这个控件之前是空的,现在我给它设置了 StringVar() ,并且绑定了一个事件是 Return,这个控件收到回车键时会触发 self.WL2Page 方法。
另一个 tab 的实例:
 # Tab4 var
self.Tab4path = StringVar()
self.Tab4pathEntry['textvariable'] = self.Tab4path
self.Tab4ButtonSelect['command'] = self.Tab4selectPath
self.Tab4ButtonConfirm['command'] = self.Tab4ReadFile

相比于把 GUI 各种按钮的函数摆得到处都是,现在则可以按tab分割,都放在 Application 类的私有方法里。

对这部分进行调试:

if __name__ == "__main__":
top = Tk()
Application(top).mainloop()

开发时,可以先在 Application_ui 类里面调试界面,完成后,再到 Application 类给控件们分配变量、绑定方法,验证逻辑功能。
两部分工作分割开,这样就清晰很多。制作复杂界面的 GUI 程序时,界面和逻辑的分离很有必要。


将编译好的程序打包成安装程序来发布

我在上一篇Python 可视化图形界面简单实践里介绍过,用 pyinstaller 简单快速地打包 python 程序,生成不依赖 python 的可执行文件 exe。

当时有说 -F 参数是将程序打包成一个单独的exe文件,不加则会生成一整个目录的文件。 同时也因为速度原因不建议添加这个参数。
可是程序发布时,这么多零散的文件是很不方便的,你只能将目录压缩成zip、发给别人,让别人自己去找里面的 .exe 文件。

一个合理的发布方式是提供安装文件,收到的人执行安装文件就能完成部署。
这里我们用到的工具是 NSIS(Nullsoft Scriptable Install System)。具体步骤参照这篇教程,写的很详细,我就不搬过来了:程序打包成exe文件

原则上任何语言的程序都可以这样发布。NSIS用压缩算法把你的程序那一大堆文件压成一个包,套了个安装向导的壳。
用户拿到后一运行,安装向导像所有程序一样,引导他们选择安装路径等等,然后把压缩包解压到用户路径,再为这个路径创建桌面/开始菜单的快捷方式。

NSIS 可以提供不同语言的安装向导,你甚至可以给它添加奇怪的用户协议~


这篇文章涉及的内容都是我在开发 Victorinox 小工具时遇到的。这是一把全世界只对我1个人有用的瑞士军刀。。。。。。
源码已push到GitHub:https://github.com/MamaShip/Victorinox

Git Flow实践

工作上一直使用git作为代码版本管理工具,但从来没掌握好它。最近我负责的这部分代码管理越来越混乱,掌握一套正确成熟的git工作流程几乎是迫在眉睫的事情。

git 的基础使用就不赘述了。大概每个程序员都会花几个小时掌握 git 的基础操作,再花几周去实践和熟悉吧。
首先推荐两篇文章:

如果你没有遇到过多人协作下代码管理混乱、想要 release 新版时却交不出一份能 work 的代码,读这两篇文章可能不会很有 sense。但你只要遇过一次版本危机,再硬着头皮连续加班到凌晨一两点,回头来看就会很有感受。

上面两篇文章其实讲了2件重要的事:

  • 根据你的项目性质来决定工作流(git flow / github flow / gitlab flow)
  • 在一个固定模式下,git如何规范地工作


由于我在一家制造业企业,RD 只需隔一段时间 Release 一个 FW 版本给产线即可。比起敏捷地迭代,版本的稳定性更重要。传统的 git flow 是适合我们的。

在 git flow 框架下,有2个长期分支:

  • 主分支master
  • 开发分支develop

master名为master,却并不是日常工作的基础分支,而是一个经过验证的稳定分支。随时可以用来发布。
与master平行存在,内容几乎相同但又略有超前的,就是develop分支。平日的开发必须基于develop分支进行。在git flow框架下,当一个新的需求产生时,你基于最新的develop拉出一个 feature/xxx 分支,进行开发,功能完成后,再合并回 develop。(合并后 feature/xxx 分支自然消亡)

3种短期分支(完成开发后,合并进长期分支,然后删除):

  • 功能分支(feature branch)
  • 补丁分支(hotfix branch)
  • 预发分支(release branch)

feature 只能从 develop 拉出,然后合并进 develop。
hotfix 只能从 master 拉出,然后合并进 master 和 develop。
release 则是从 develop 拉出,进行测试,完成验证后合并进 master。

当 git flow 进行 release 时,它实际做了2件事:把从上一次 release 至今的 develop 改动经过验证后合入 master,再反向把 master 合并回 develop 确保两边同步。
为什么要反向 merge 一遍,因为 release 过程中若测试出一些问题,就可以直接在 release/xxx 分支上进行修改,而这个改动是没有发生在 develop 上的。所以 release 分支在删除时会保证这些改动也被同步到develop。

在这样的设计下,master 是稳定的,它受到 release 规则的保护,除非发生 hotfix,就只有经过测验的 release 分支才能合进 master。
而 develop 分支则相对比较敏捷,根据需求拉出 feature branch 后,开发者可以专注于自己的子任务,把兼容性等全局测试交给 release 分支去负责。

使用 git flow 相关工具,可以帮助规范这个流程。例如,工具会禁止你基于 master 拉出一个新的 feature 分支,因为新 feature 总是应该基于 develop 分支来开发,若要紧急修补某个bug,你应该使用 hotfix。
一些git flow工具(如gitflow-toolkit),还可以规范你的commit,确保commit信息清晰有效,能被script解析。这样你就能使用现成的工具(git-chglogconventional-changelog),自动生成change log。这在 release 正式版本的时候是很有用的:


以上是我理解的 git flow 实践。在应用中发现它也对使用者提出了一些要求:

  • 无论是否使用工具辅助,所有人都需要按规范格式进行commit(参考: Angular 社区规范
  • 每一项逻辑上独立的改动,应归属于一次单独的commit
    (不要在一个feature分支下进行多项任务的开发;若有多次commit都是关于同一个修改项目,应先squash再合进develop;尽量让每个 commit 都是一项独立、完整的改动,可以方便debug/release时进行cherry-pick和rebase)
  • git flow tool 大多是基于 Linux 系统。win下的开发者需要自我约束。

git flow 仍在实践中学习。有新的理解会再更新。