md5/sha1+salt and Bcrypt

Just the day before yesterday, the biggest developer community website in China, CSDN, was cracked, and the database is leaked. In the leaked database, the password was stored in plain text. People are tweeting password and security related message around. I noted a message saying that md5/sha1+salt is unsafe to store password. It strongly suggested…

1

Web服务的性能,和BCrypt性能问题的解决方法

在昨天的研究中,发现BCrypt最大的隐患在于性能。BCrypt的安全性是通过牺牲性能来获取的。BCrypt比传统hash+salt要安全一万倍,但是代价是使用BCrypt做认证对比密码和密文时候,性能也比hash+salt要慢一万倍。 所以,我得出一个结论。如果使用传统hash+salt需要N台认证服务器的话,那用BCrypt就需要添加10000*N台服务器才能达到同样的性能。比如一个邮件系统使用了2台服务器来专门作认证,那使用BCrypt的话就需要再购买2万台。当然,小的应用,如果使用一台服务器1%的性能就可以做完认证的话,使用BCrypt只需要100台服务器。 这个听起来比较吓人,但是我通过另外一种计算方法,也能得出同样的结果。比如说163的邮件系统,峰值的时候每秒钟可能需要处理10000个登陆请求。比如每天早上9点到9点半之间,很多人都会登陆邮件系统。按照BCrypt提到的,每个请求需要花费0.3秒,那么处理10000个请求需要3000秒。这显然是不能接受的。如果要让客户都能在1秒钟登陆,那就需要添加服务器,把登陆请求均分到各个服务器上。对于单CPU的服务器,就一共需要3000台。 我把上面的想法和网友讨论后,得到了不同的意见。有人觉得0.3秒的处理时间其实不多阿,因为通常一个web请求,内存,磁盘数据库转一圈下来,离0.3秒也差不多了吧,所以BCrypt的0.3秒的开销是一个正常值,不会带来什么问题。有人提到普通web服务器每秒处理1000个请求是很常见的。如果按照我上面的计算方法,这就表示每个请求在1ms内完成了,这听起来有点不可能嘛。 根据上面的意见,我又仔细思考了一下。我想借这个话题,先讨论一下Web服务器的性能,再看看BCrypt带来的问题应该如何解决。 注意,下面所叙述的,是根据我现有知识和经验做的逻辑推理。我没有写半行web程序的code来验证,我也没有任何大规模web项目的经验。但是我非常喜欢先做这样“纸上谈兵”的推理,因为这样可以让我先仔细想清楚后再行动。 网页的加载时间,和单个request的处理时间是不一样的。单个网页中往往包含多个子元素,比如图片和AJAX调用。这些子元素的加载都会在额外的request里面完成。另外网页加载的时间除了web服务器的运算处理时间外,还有数据在网络上的传输时间,脚本运行时间,浏览器绘制时间,当然如果是第一次访问,还包括DNS查询和TCP握手时间等等。现在主流网站的页面加载时间都在2秒以内,每个页面大概包含10-50个子元素。客户端脚本和浏览器的处理占用了大概一半时间,所以跟服务器相关的时间大概就是1秒。由于部分子元素可能在浏览器中有cache,所以这1秒钟对应的大概就是5-25个请求。这样算下来每个请求大概在200-40毫秒之间。这里面大概web服务器的运算开销可能只有25%,那大概就是50ms到10ms之间。注意,50ms-10ms这个估算是指平均时间。 由于网络传输和客户端导致的开销不是今天的讨论范围,所以下面就只讨论web服务器运算一个request需要怎样的开销。处理一个web request,通常牵涉到下面一些工作。输出流添加,数据库读写,文件读写,复杂计算。输出流添加是最常见的,比如服务器会把Response.Write里面的内容加入到Response里面。输出流添加是非常快的。速度和string.format或者StringBuilder.Append应该在一个数量级。肯定比毫秒要快多个数量级。复杂计算是指需要CPU密集超过50ms的运算,比如正则表达式运算和BCrypt操作。数据库读写和文件读写所需要的时间往往也超过50ms,但是这两者不一定需要占用web服务器的CPU资源。 由此,在考量web服务器运算一个request所需的开销的时候,先看这个request是不是需要复杂运算。如果需要,那么这个复杂运算肯定是一个瓶颈。 那么数据库和文件操作是不是瓶颈呢。从处理request所需的时间上来说,这两者肯定也是瓶颈。因为再快也得先等到这两者返回。但是和复杂运算相比,复杂运算损害的不单单是request所需的时间,另外还损害了服务器的可伸缩性。 由于数据库和文件操作不占用web服务器的CPU,所以web服务器在等待数据库和文件操作结果的时候,可以把CPU资源用来处理新的request。比如来了100个请求,每个请求都需要2秒钟的数据库操作,不等于说服务器需要200秒才能处理完所有请求的。因为服务器可以让100个请求都进来,然后发送者100个请求的数据库操作,然后让这100个请求同时等待。2秒钟以后,这100个数据库操作的结果都返回回来后,服务器可以把这100个请求的结果都返回了。 但如果请求中牵涉到了复杂运算呢,服务器就没办法并发了。如果来了100个请求,每个请求都需要运算2秒钟,而服务器如果只有一个CPU的话,那就一定需要200秒。 由此可见,请求的平均处理时间和服务器的吞吐量不是简单的比例关系。这牵涉到这个请求具体是如何处理的。如果服务器的吞吐量是1秒钟1000个请求,不能简单地用1000毫秒除以1000,得到每个请求只需要1毫秒来处理。这个运算法则只在没有任何并发可能性的情况下才有效。这也在此证明了,合理使用异步调用,对服务器性能会有多大的提高。 接下来反过来想,对于一个不涉及数据库,不涉及文件,不涉及复杂运算的请求,合理的处理时间应该是多少呢。这个处理时间其实等同于同等复杂程度的函数调用时间。换句话说,如果只是计算出一个几十k的页面,花费的时间肯定在1ms的数量级。你肯能觉得这里没有考虑web服务器的“仪式性”开销,比如说处理TCP报文,分析HTTP头等等。其实,主流的web服务器在这方面已经足够优化,比如从IIS6开始,对于HTTP协议的处理都直接在内核里面做了,所以就算把这些开销都算上,也能做到1ms的数量级。对于计算机来说,1ms其实很长的,1ms表示一秒内调用函数1000次而已。不信你可以估算一下下面的代码,循环了10000次,大概需要多少时间: StringBuilder dummy = new StringBuilder(); for (int i = 0; i < 10000; i++) {                 dummy.AppendLine((string.Format(“this is {0}”, i))); } var len = dummy.Length;     另外,上诉的讨论还没有考虑一个非常重要的武器:Cache。如果使用cache, 整个页面可能根本不需要任何运算,都不需要跑一行处理代码,web服务器就把结果给返回了。如果大量使用cache,别说一千次,一秒钟处理上十万次都可以。大多数的网站已经广泛使用cache了,图片是cache的,blog文章的内容是cache的,甚至评论都是cache的。正因为如此,把包含复杂运算,数据库和文件处理的慢操作跟带cache的块操作一平均,结果落到前面估算的50ms-10ms是很自然的事情。 有了上面的分析后,再来看文章前面的两个问题。第一个问题是,BCrypt的300ms开销,和数据库,磁盘文件兜一圈下来的开销也差不多阿,为什么说BCrypt就更严重呢。原因是BCrypt的300ms都压在了CPU上面,而人家的是可以并发的。当然,动不动就要去兜数据库和磁盘文件的web应用,设计上也有问题的。第二个问题是,我的服务器可以一秒钟处理1000个请求,按照原来的计算方法,就是1ms处理1个了,这个不可能吧。这个问题就要区分情况来回答了。首先,1ms处理1个请求是可能的,比如使用了cache,绝对能。其次,如果考虑并发的话,的确不能简单做除法。但问题关键是,BCrypt是不支持并发的阿。 所以,BCrypt最大的隐患的确就是在性能上。我所做的下列判断是正确的:“如果使用传统hash+salt需要N台认证服务器的话,那用BCrypt就需要添加10000*N台服务器才能达到同样的性能”。 接下来的问题是,BCrypt性能问题有解决办法么。在前面的逻辑推理中,我想到了一个最常见的办法:用空间换时间。我可以在内存中建立cache,把密码原文和用BCrypt计算后的hash缓存起来。这样每次处理认证请求的时候,就不需要计算了。当然,这里其实带来了新的安全隐患。如果有人盗窃了服务器的内存转储(memory dump), 那么就能看到cache里面的东西,那可就是密码的原文明文阿。这有何去何从呢? 引起这片文章的讨论来源: http://weibo.com/1709648133/xDtMxivam http://weibo.com/1709648133/xDy7YjYX0

0

Retrospect different Microsoft technologies from Win8

The Chinese version is available here (中文链接在):http://blogs.msdn.com/b/lixiong/archive/2011/12/03/win8.aspx Learning how things work internally has always been my favorite. The first thing I did was to launch debugger when I got Win8 installed. Based on my research, Win8 is an amazing product. There are many old and new technologies involved in Win8. I’d like to use this blog to…

3

从Win8回顾微软平台的各种技术

我安装好Win8 CTP后做的第一件事情就是用调试器研究Win8各个组件的协作关系. 从我半天的研究结果看来, Win8真是一个让我爱不释手的产品. Win8里面涉及到的很多技术正好也是我的兴趣所在. 这篇文章简单回顾一下这些技术的变迁, 优缺点, 和对Win8的影响. 注意, 下面提到的对Win8的分析, 是基于公开的Win8 CTP来做的. 相信Win8面世的时候, 这些技术和细节, 都会发生重大改变. 所以这篇文章不具备实践上的指导价值. COM -Component Object Model 通用组件模型 COM是上个世纪中期设计出来的伟大产品. COM旨在解决软件复用的问题. 在COM以前, 大家都是用代码级别的复用, 常见的就是C/C++的库, 无论是原代码库还是lib库, 都是需要编译后才能重用的. COM使得技术人员可以在二进制上进行复用. 从Win95, OLE32和Office95系列开始, COM就是微软平台上的一个技术基石, 无论是DirectX API, 还是最常见的剪贴板, 以及后来.NET Framework的host接口, 都离不开COM. 但任何伟大的产品, 都有局限的一面. COM在局限性在下面一些地方 STA/MTA/NTA等等线程模型过于复杂 线程模型, 特别是STA, 设计的目的是方便使用者. 但COM的线程模型严重依赖于太多系统组件, 比如Win32 Message, RPC和Windows系统服务, 使得程序员需要熟悉和了解太多系统知识才可以正确地使用线程模型. 否则用STA导致死锁简直就是家常便饭. 开发工具没有提供足够支持 COM和Visual Studio 6.0的关系,…

2