March 2011 Archives

以前设计API时参考OAUTH针对原有的认证做了改进,  使用了HMAC和OTP等,  但是明显木有下文那么详细的理解和介绍,  转来膜拜一下。

from Changming的blog 

原文地址: https://www.sunchangming.com/blog/post/3684.form

 

昨天有个朋友给我打电话,询问网络协议设计中的安全性问题。他在做一套C/S结构的应用软件,有以下需求 
1、Client在与Server建立连接后,首先需要进行身份认证,只有身份认证通过后,才允许发送其它数据。 
2、身份认证过程应当尽可能高效、安全。这里的安全不仅指防窃听防重放等,还包括防止服务器被DDos。 
3、身份认证过程之后,所有的消息交互必须加密,并且传输中要防止被篡改。

反正我要发给他的东西也没什么私密的,就干脆写这里了。 
在信息安全领域,数据的保密性和完整性是两个不同的目标。 
要达到保密性,选择合适的加密算法对数据加密即可。总的来说,加密算法分为对称加密和不对称加密。对称加密就是加密和解密采用同样的密钥同样的算法,不是对称加密算法的就是不对称加密算法。典型的对称加密算法有:DES\2DES\3DES、IDEA、AES、RC4\RC5\RC6、BLOWFISH、TWOFISH。不对称加密算法有:RSA、DSA。由于不对称加密解密要比对称的复杂且慢,所以一般来说密钥交换阶段可能会采用不对称加密,而通信数据加密主要还是用对称加密。

加密算法未必能同时保证数据完整。 
下面举个例子说明这个问题:假如设计一种简单的查表加密算法,将0-255重新排列得到数组unsigned char seckey[255]。将原文的每个字节作为下标去seckey里查得到密文。这是一种有效的加密算法,但是不能保证数据完整性。例如将密文截去几个字节,接收方是不知道有人动了手脚的。

出于程序员的思维,为了保证数据完整性,最简单的方法就是加个checksum呗。例如CRC32或者奇偶校验位这样的技术。但是从安全需求来说这样做也不行,因为奇偶校验位也可能被篡改啊。所以需要专业点的东西,Message Authentication Codes(MAC)就是为了完整性而设计的。MAC由两个算法组成,签名和校验。假设为Sign(k,x)和Ver(k,x),其中k是共享密钥,x是待签名的数据。传输数据时将原始数据(x)和签名(Sign(k,x)的结果)一起发送,接收方用Ver(k,x)函数验证完整性。所以这两个函数应满足Ver(k,Sign(k,x))=true。

假设用E(k,x)表示加密函数,Sign(k',x)表示签名函数,保密性和完整性我都想要,那么就存在一个问题,先签名还是先加密? 
1、先加密后签名:令y=E(k,x),t=Sign(k',y),然后发送(y,t)。实际例子:IPSec。 
2、先签名后加密:令t=Sign(k',x),y=E(k,t)。然后发送y。实际例子:SSL。 
3、各算各的。令y=E(k,x),t=Sign(k',x),然后发送(y,t)。实际例子:SSH。

这3者的优劣,在10年前已经有人分析过了,http://eprint.iacr.org/2001/045。 第3种肯定是最不安全的,因为如果t相同那么x可能相同,假如x只取很有限的几个值,那么通过大量嗅探很容易猜出来原文。而第二种依赖于具体的加密/Hash算法的选择。按我理解,简单来说就是第一种最好。

MAC只是理论,需要具体的算法给大家用。由于Hash函数的不可逆性,人们很自然的就想到了用Hash函数做MAC。常见的通用Hash函数有:MD5(128位)、RIPEMD-160(160位)、SHA-1(160位)。Hash函数不同于DES之类的,它没有密钥这个概念。于是就想,把密钥和原文直接混在一起然后hash,例如:Sign(k,x)=Hash(CONCAT(k,x))。其中CONCAT是字符串连接函数。但是目前主流的Hash算法都不是为了这种目的设计的,即便不知道k也很容易在x后面再追加一些东西依然能通过Ver。以SHA1为例,在某些特殊情况下,在知道SHA1(CONCAT(secret,message))和rogue的情况下很容易算出SHA1(CONCAT(secret,message,rogue))。这里的特殊情况是指CONCAT(secret,message)的长度恰好是SHA1算法的block size的整数倍。 反过来,Sign(k,x)=Hash(CONCAT(x,k)),也有类似的缺陷。92年的时候G. Tsudik发表了一篇论文“Message authentication with one- 
way hash functions”专门讲述这个问题,可惜我已不在学校,没有电子期刊库,下不到这篇论文。

不是说用Hash函数做MAC不行,而是说需要稍微复杂一点的构造。于是诞生了HMAC(Keyed-Hashing for Message Authentication)算法。HMAC是一个很通用的标准,rfc 2104,ANSI9.71,FIPS PUB 198都是对它的定义。HMAC的公式很简单:HMAC(k,m)=Hash(CONCAT((k XOR opad) , Hash(CONCAT(k XOR ipad),m)))。其中k是密钥,m是需要被签名的消息。ipad/opad是标准中定义好的2个常量。HMAC的特色是它不依赖于特定的Hash算法,也没有对Hash算法提出特殊的要求,即,如果HMAC-SHA1没缺陷但是HMAC-MD5有缺陷,那么一定是MD5作为一个通用的Hash算法是有缺陷的。


我朋友的这些问题,可以分成两个问题: 
1、如何进行身份认证(身份认证的问题) 
2、如何产生一个对称密钥以用于后续数据的加密(密钥交换的问题)

先说身份认证,最简单的方式就是明文认证: 
1、C->S: 用户名,密码(明文) 
2、S->C: 成功或者失败。 
SMTP中的LOGIN/PLAIN就属于这种模式。LOGIN是用户名和密码分两次发送,PLAIN是放一起一次发送。缺陷:密码被窃听后直接重放即可。但是如果信道是安全的,如ssl,那么这么做也不存在问题。PPP中的PAP就是这种模式。

对于明文验证的一种改进是挑战应答认证协议(CHAP):CHAP是一类协议的统称。典型应用是Point-to-Point Protocol中,在网络连接建立后,服务器需要以密码的方式验证客户端的身份。 
通常来说,CHAP协议有4种消息: 
1、Challenge 
2、Response 
3、Success 
4、Failure

交互顺序是: (S代表服务器,C代表客户端) 
1、S->C: Challenge 
2、C->S: Response 
3、S->C: Success/Failure

Challenge通常是一个随机数,Response是f(password,Challenge)得到的。窃听者只能拿到一个一次性的东西。将HMAC应用到CHAP上,可得到这样的协议: 
1、S->C: 一串随机数r 
2、C->S: username,hmac(password,r) 
3、S->C: Success/Failure

实际例子:SMTP认证过程中的CRAM-MD5方式。HMAC CHAP基于这样一个假设,在不知道key的情况无法对r生成正确的MAC。但是这种协议有这么几个缺点: 
1、服务器必须存password的明文。 
2、无法抵挡中间人攻击。 
3、易被窃听后使用字典攻击猜出密码。 
4、客户端不能验证服务器。客户端无法知道服务器是不是真的知道它的密码。

对于中间人攻击,举个例子:在C和S之间加一个Proxy,刚开始它只作单纯的转发,在身份认证成功后立即断开C和P之间的连接。一般来说,C肯定会再去登录S。那么P就要想办法让C登录不上。因为它要把网络一直把持着也比较难,所P就去疯狂的用错误的密码登录。按照一般的设计思路,为防止在线字典攻击,如果密码输入次数错误太多,那么该IP就在一段时间内不得登录。如果P和C在同一个网吧,oh yeah,得手了。然后呢?玩过网游你就知道,盗号者虽然不能把这个账号占为己有(因为拿到的只是一个一次性的密码),但是他可以上去把该角色的所有物品扒光、删除角色、解散帮派或是利用社会工程学进行更大规模的诈骗。所以为防止在线字典攻击,应采用人机识别和运营监控的方式,封IP应该只封短暂的几十秒即可。

针对以上所说的缺点,微软发明了MS-CHAPv2(rfc2759),用于PPP连接中的身份验证: 
首先,服务器不存储原始密码,服务器存储的是密码的hash值。服务器和客户端共享的秘密不是原始的明文密码,而是MD4(plain password),下面把这个记做Kcs。 
1、S->C:  16字节的随机数r1 
2、C->S: 16字节的随机数r2,24字节的NT-Response。 
Client首先生成16字节的随机数r2,然后计算SHA1(CONCAT(r2,r1,username)),然后将散列后的结果的前8个字节用Kcs做对称加密,得到一个24字节的结果(记做NT-Response),将其和r2一起发给服务器。这里对称加密的方式是这样:由于Kcs是MD4得到的,所以是16个字节,给它后面补上5个0,于是就是21个字节,分成3段,就得到3个7字节,作为DES的3个key,然后拿这3个key使用DES算法分别对SHA1(CONCAT(r2,r1,username))的结果加密,于是得到3*8=24个字节的答复。

3、S->C: Success/Failure 
Success包里面有一个20字节的auth_string(HEX编码后以ASCII传输,前面加上“S=”作为前缀,所以实际传输的是42个字节)。它是由r1、r2、NTResponse、username、password合起来生成的:SHA1(CONCAT(SHA1(CONCAT(MD4(Kcs),NTResponse,Magic1)),SHA1(CONCAT(r2,r1,username))的前8个字节,Magic2))。其中Magic1、Magic2是两个字符串常量,前者是“Magic server to client signing constant”,后者是“Pad to make it do more than one iteration”。

通过以上描述,你可以看出MS-CHAPv2简直是一个从头烂到脚的协议,我怀疑这是微软的工程师在睡觉的时候想出来的,或者那人跟Big Bang中的penny是大学校友。首先,r1、r2、username都是明文传输的,拿出来算个SHA1意义何在?其次,算完之后截断到8个字节又是为何?最后,那套山寨版的3次DES算法更是搞笑至极。还有,虽然不用存储密码的原文了,但是密码的原文在身份认证过程中完全用不到,这不就是搞了个变量替换吗?最后那个Success包,更是复杂的莫名其妙,我只看懂了那两个magic是啥意思,我是第一次看见有人拿human language作加密算法中的magic number(江苏联创这种山寨公司的山寨产品除外)。针对MS-CHAPv2的种种毛病,微软并没有推出MS-CHAPv3的计划,而是继续就这么用着吧。

另外一个CHAP的例子就是MySQL。 
1、S->C: public_seed 
2、C->S: username, reply 
3、S->C: Ok or error

对于4.1及以后版本,public_seed是随机生的20个可打印的ASCII字符,4.1之前的版本是8字节。 
4.1之前的协议,客户端这么计算reply: 
storedhash=hash(password) 
reply=scramble_323(storedhash,public_seed); 
4.1之后的协议,客户端这么计算reply: 
passphrase=sha1(password) 
storedhash=sha1(passphrase) 
reply=xor(passphrase, sha1(public_seed,storedhash) 
其中storedhash即是服务器存在数据库中的hash过的密码。

4.1版除了把public_seed和storedhash从8字节增加到20字节外,一个明显的改进就是,4.1以前的版本,即便客户端不知道原始密码,知道storedhash,一样可以通过身份验证。出于这个原因,选择什么样的hash函数,对于安全性几乎已经无关紧要,因为没有人关心原文是什么,所以焦点在于scramble_323做了什么。scramble_323是mysql自己发明的一套算法,难以用文字简短描述,代码实现在sql/password.c中,很短。网上有关于scramble_323的分析,结论就是它很弱,通过嗅探多次之后很快就能算出storedhash。

目前看来,在"服务器必须存password的明文"这个问题上,新版的mysql认证协议是对HMAC CHAP的很不错的改进。

另外一个值得关注的协议就是RFC2945,魔兽世界用的就是这个协议。

我觉得网游公司在协议安全上还是得多下点功夫,首先,盗号已经是玩家流失的主要原因之一。其次,搞一套自己的认证协议、加密算法,然后把它和反外挂结合起来,会加大制作外挂的难度。例如把HMAC所用的hash函数混淆后放到反外挂驱动的sys文件中,哪怕混淆后效率比以前慢10倍我也不在乎,反正就登录的时候才执行那么一次。时不时的换一下算法,足以让他们叫苦不迭。

未必非要自己从头去设计一套算法。拿MAC来说吧,前面通过对SHA1(CONCAT(secret,message))的分析可以看出,虽然它有问题,但是不致命,因为用户的密码一般也不长啊,而且message的长度是server控制的,完全可以绕开那个问题。于是在它上面可以搞点变种继续用,比如把字符串连接之后先按固定的规则shuffle一下再SHA1。再比如HMAC,那两个PAD的选择,其实挺随意的。你想想看,混淆后的代码那么长那么乱,里面就藏2个字节的常量让他去找,我靠,我就不信他唰的一下就碰见了。就算你能找到,那两个数字,我一周换一次总行吧?

但是无论如何,从协议角度避免不了木马。但是至少不会出现像网易那么二的事情,用了硬件OTP卡还被盗号,然后被玩家怀疑有内鬼。唉,明明就是你协议设计就有问题嘛。

 

发信人: draculalord ( 嗯?), 信区: Python
标 题: 也谈链表及其他Re: python标准库貌似没有实现链表?
发信站: 水木社区 (Mon Mar 21 18:49:46 2011), 转信

实际上刚开始学习一些高级语言的时候我也有同样的疑问,而且即使有链表对应物的语言,链表常常也很少被实际使用。
如果是在国外听数据结构的课,老师一般会警告你这只是一个理论概念,实际应用应该实际考察,在通常情况下链表不是一个很好的结构。
通常链表会作为一个很好的反例,告诉大家脱离实际硬件环境来谈论所谓算法复杂度是没有任何意义的。
这是因为,链表已经不适合当今的计算机硬件发展。当今的计算机硬件对内存是否连续更为敏感,而链表恰恰会破坏这种顺序读取。
由于locality很差所以常常造成page fault和cache miss
这也是为什么大多数教师不再推荐使用链表的原因。而且现今的硬件内存拷贝实际相当迅速。
并且python的list算法不是通常的单项表,也不是通常的数组。
具体可以看这里:http://wiki.python.org/moin/TimeComplexity
在List末尾append/pop都是O(1)的,
如果要在头部或者中部插入是O(n),任何破坏连续性的操作都会被要求realloc,所以任何此类操作都是O(n)
但是当今的常用硬件,使用C写的链表和python的list,在insert的时候只有n>50000才让链表比list快那么一点点。
这还没有考虑其他实际操作的复杂度。加上前面说的破坏locality,导致链表完全没有吸引力。在对象特别多的时候通常我们直接抽象它为数据库,也不要去想什么链表了。

在需要用到linked list特性的地方,比如常常需要从头部append或者pop
这时候有python的deque. (这里我记错了,特此更正,deque如果做insert还是会导致内存拷贝/移动,这里面的关键思想就是目前硬件的内存拷贝相当快,不是相当长的东西都可以接受)
deque也不是通常的简单数据结构,它是经过认真权衡过后得到的一种混合式数据结构。
他是一个链式块结构,每个块包含62个对象,以此来平衡对locality的优化和对push, pop的优化。有人问为啥是62个而不是其他数:那是因为deque是个双向链表,一个节点64个指针,一个指向前一个指向后,剩下就是62个指针用来指向对象

要做到对insert到中间的优化是用btree和array结合的办法,有个第三方包blist
但是我估计很少有应用会真正用到这个。insert是O(log n)
http://pypi.python.org/pypi/blist/

其实python是大师设计的语言,他们来决定底层具体的数据结构,作为一般人,你没有必要去质疑大师们精心设计的东西。
如果你真的对性能有很大要求,python也许并不适合你,python不是作为纯粹针对高性能计算诞生的东西,
他是一种胶水语言,它只对常见的List长度,常用的算法结构进行优化。他希望达到的目的是把现实的应用抽象出来,让使用者不用关心具体的数据结构和算法。
pythonic是一种面向大众的编程态度

如果你要用它来做其他事情,可以看看有没有你需要的第三方模块,或者可以用C来实现自己的一个模块,python本来就是C写的,所以这实际上也一点不困难。
比如python里面没有一个数据结构是能用来很好表示数值运算中使用的大型矩阵或者数组的,这时候就诞生了第三方包:numpy

商家刷卡成本

| No Comments | No TrackBacks

via newsmth

1%,银联0.1%,发卡行0.7%,pos行0.2%

电话费另附...