一种基于消息摘要的人机验证应用研究
An approach to captcha based on message digests
刘振兴1 / Liu Zhenxing
摘要：自动识别机器或真人的服务（CAPTCHA）被广泛应用在网络空间的很多场景。传统的人机验证机制为系统随机地生成一段消息保存在服务器端，然后发送给用户终端以扭曲的形式展示给用户，以此区分用户终端是来自机器或真人。本文详细分析了常用人机验证机制的优劣，然后提出一种基于消息摘要（单向哈希）的方式进行人机验证。与传统方法相比，不需要额外的存储随机消息，在部署方式和成本方面有更好的表现。[1]
关键词：消息摘要，人机验证，验证码，CAPTHCHA
Abstract: Applications of telling computers and humans apart (CAPTCHA) have been widely-implemented and deployed in several scenarios on cyberspace. Traditional man-machine verification is to generate a random message stored in server-side, and then send a distorted representation of the message to client-side in order to distinguish the client from the machine or human being. This paper explains the widely-used method in great detail and shows some of its merits and demerits. This paper analyzes the merits and demerits of this commonly-used man-machine verification mechanism, and then presents a new approach to man-machine verification based on message digest (one-way hash). Compared with the traditional method, no additional storage of random messages, in terms of deployment and cost, it has a better performance.
Keywords: Message Digest, Man-machine Verification, Verification Code, CAPTCHA
- 背景及问题
- 背景
人机验证被广泛应用于各种在线网络服务中，如预防垃圾内容、保护用户注册和登录、保护在线投票、预防词典攻击等各种需要阻止机器自动进行的各种暴力破坏性行为。
人机验证（识别）也即全自动区分计算机和人类的公开图灵测试（Completely Automated Public Turing test to tell Computers and Humans Apart，CAPTCHA） [1] [2]。在实际应用中也被通俗地称之为“验证码”，它是一种区分终端用户（客户端）是计算机或人类的公共全自动程序。在CAPTCHA测试中，作为服务器的计算机会自动生成一个问题由用户来解答。这个问题可以由计算机生成并评判，但是必须只有人类才能解答。由于计算机无法解答CAPTCHA的问题，所以回答出问题的用户就可以被认为是人类。
一种常用的CAPTCHA测试是让用户输入在一个扭曲变形的图片上所显示的字符，扭曲变形是为了避免被光学字元识别（Optical Character Recognition，OCR）之类的终端机器自动辨识图片上的字符而失效。由于这个测试是由计算机来考人类，而不是标准图灵测试中那样由人类来考计算机，人们有时称CAPTCHA是一种反向“图灵测试”。为了满足无法看到图像的身心障碍者，替代的方式使用语音读出字符，进一步地为了防止终端机器进行语音辨识分析出声音所代表的字符，声音的内容会伴有干扰音以加大机器识别的难度。
人机验证过程涉及到问题生成、传输、呈现和校验。人机验证的安全性在各个实现环节进行深入分析并各有针对性的解决方法，其中多数的攻防思路集中对扭曲展现形式的生成与破解上。实际上，供应链上的每一个环节都值得注意并赋予同等重要性地位。目前对图形图像识别的机器辨识讨论较多，但对人机验证过程及环节较少，本文尝试分析和研究的是后者这一领域的问题。
- 问题
根据CAPTCHA测试的定义，产生用于验证的图片或其他扭曲展示的算法必须公开，比如常见的随机（或伪随机）生成。这样做是为了证明想破解就需要解决一个不同的人工智能难题，而不是依靠发现原来的算法。即便这种随机过程是伪随机 [3]，由于其与终端（客户端）Id不存在任何映射（算法）关系，其被认为是符合CPATCHA定义，要破解这样的验证码的任务就等同于解决类似计算机识图、计算机辨音等人工智能任务。这一应用领域的研究大多集中在如何破解及反破解这一类似人工智能问题上 [4] [5] [6]。
实际应用中，服务器端生成随机码并与客户端Session Id做配对并保持这一状态，多数情况下是在HTTP(S)等无状态的应用协议下实现和维护一种“对话”状态，需要额外的部署一种服务，也即Session会话管理服务。这种服务能够进行完成上述目标——对新终端用户生成Session Id并保持相应的状态信息，如果该终端用户没有通过人机验证，则还需要为用户生成一对问题、答案配对，并维持其与Session Id的对应关系。这需要一种额外的存储开支需求，同时存在应用服务器与Session会话管理服务的通信成本。
另外，这种维护在服务器端的关系对，可能会被截获并重复利用 [7] [8]，Session列表可能被Flooding攻击。
针对人机验证在服务器端的部署和应用问题，我们开展了相关研究，通过一系列对比分析和综合实验，我们找到一种基于消息摘要的人机验证新方法。
本文提出一种无需在服务器端维持“对话”状态人机验证服务的实现方法，通过基于消息摘要（单向哈希）的算法来保证其达到通用验证码服务的功能要求。
余下全文分为四章。第二章列举和分析了多数现行人机验证实现的方式方法，第三章提出本文主题，一种基于消息摘要的人机验证应用设计，第四章进行安全性、实用性等分析与讨论，第五章进行简要小结。
- 相关研究及应用
- 人机验证机制
现行的人机验证服务通常由三部分组成：用户终端（客户端）、服务器端（应用服务）和Session服务端（会话服务）。用户终端（客户端）发起人机验证请求；服务器端收到验证请求，进一步联系Session服务器端；Session服务器端根据用户请求生成对应的Session ID、问题Q和答案A，并以队列的形式将Session ID等信息保存在Session服务器端，并将Session ID和问题Q的配对返回给应用服务器端；服务器收到Session ID和问题Q后，进一步地前转返回给用户终端。
用户终端收到Session ID和问题Q后，进行作答，完成作答后客户端将Session ID和答案A’发送给应用服务器端进行检验请求；服务器端收到Session ID和答案A’后，以Session ID向Session服务器端查询对应的问题Q和答案A，在获得答案A后，对比终端用户的答案A’和Session服务器端的答案A。
如果用户答案A’与Session服务器端答案A相一致，则验证通过，成功完成进行下一步；反之，则验证不通过，失败返回重试。
传统的人机验证机制的服务架构如下图（Figure 1）所示。
| 用户终端 | 应用服务器端 | Session服务器端 | ||
| 发起验证请求 | ||||
| 从Session服务器端获得Session ID、问题Q,
返回给客户端 |
||||
| 生成Session ID，问题Q、答案A，以队列形式保存在服务器端 | ||||
| 根据问题Q作答
发送答案A’、Session ID进行检验 |
||||
| 根据Session ID获取问题Q和答案A,
检验答案A’与答案A |
||||
|
|
根据Session ID从保存队列返回问题Q和答案A | |||
| 收到检验结果
对 或 错 |
||||
Figure 1 传统人机验证流程
在一些小微的网络应用或解决方案中个，也有将服务器端和Session服务器端合二为一，集成到一起，但在稍微复杂或者大中型网络应用中，都需要依靠单独的Session服务端来完成人机验证服务。无论是集成到一起还是单独部署，Session服务的功能和角色成为必选项。
- 复合图形图像验证码
在前述人机验证的机制下，网络上出现各种各样的具体实现和应用部署方式，其中影响较为广泛的应用有Google reCAPTCHA [3]和中国铁路总公司12306网站人机验证服务的验证码 [10] [11]。
reCAPTCHA借助于人类对计算机难以识别的字符的辨别能力，进行对古旧书籍中难以被OCR识别的字符进行辨别的技术。也就是说，reCAPTCHA不仅可以反垃圾邮件、预防机器人注册登录等，而且同时还可以帮助进行书籍的数字化工作。
每次reCAPTCHA会显示两个单词让人来识别，其中一个是需要用户识别的难认词，另外一个是答案已知的真正的CAPTCHA 词。软件将能够正确识别CAPTCHA词的用户看作是人类，当CAPTCHA 词被正确识别出来后，程序会纪录用户对无法阅读的词的回答并将其添加到它的数据库中。这样就完成了一次人工的光学字符识别（OCR）过程。这一过程的核心人类对图形图像的识别，其部署方式仍需要独立的第三方的Session会话管理。由于人工智能领域的进步，计算机识图能力大幅提升，其改进版的“No CAPTCHA reCAPTCHA”已经推出。
也是基于计算机识图能力的提升，改进的中国铁路总公司将问题也进行了图示化，同时加大了对识图能力和逻辑推理能力的考察。这些是在对人工智能的深层次的验证，其背后的服务器端的部署，仍沿用较传统的应用服务器和Session服务器配合使用的方式。只不过验证从考察识别字符到识别图像并能够“理解”图像再进行作答。
- 一种基于消息摘要的人机验证
- 消息摘要、单向哈希
消息摘要是一段消息的“指纹”，通常使用单向哈希函数完成一种固定的映射y=f(x) [6] [7]，其主要特征是根据摘要信息不可逆推出消息原文。这些单向哈希函数方法MD（Message Digest），可能是MD5，MD6，SHA1，SHA128等其中的一个，设若m为消息原文，d为消息摘要，对于任意给定消息m，有且只有唯一对应的d生成；对于任意给定的d无法逆向还原消息原文m，也即，
d = MD(m)，
可以根据m生成对应的消息摘要d，而不能根据d反向推导出消息原文m来。消息摘要的另外一个特征是，任意发生在原文m中的改动必将引起在消息摘要d上的变化。因此也被广泛应用在安全领域，做私密性、完整性和鉴权（CIA）的多种实现技术手段之一。
下图（Figure 2）展示一种消息摘要在安全通信中的应用情况 [14]。在左侧消息发送方（Originator）在消息原文使用私钥加密后，再使用消息摘要方式对加密后的消息生成相应的“摘要”。摘要信息连同密文一起发送给右侧接收方（Recipient），接收方使用发送方的公钥对消息进行解密，揭秘后的原文只能说明是来自于发送方的私钥加密后的内容（私密性），而不能保证在这一过程中没有被改动。满足这一“一致性”需求的实现方式是附带在密文后面的“摘要”，在成功解密原文后，按约定的单向哈希函数生成新的消息摘要，如果新生成的消息摘要也与所附摘要相一致，则说明原文在传输过程中没有被修改。
Figure 2 消息摘要在安全通信中的应用 [7]
根据其这一特征，我们可以将这种一致性保证应用在我们所设计的一种新的人机验证方法中。
- 一种人机验证的新方法
在应用服务器端常量K作为预设私有密钥保存在服务器端，变量U为终端用户动态信息，如IP地址、浏览器（User-Agent）名称和访问时间等信息，也即，
U ≈ (IP, User-Agent, Time) ，
变量R为伪随机函数RD所生成的伪随机字符串，也即，
R = RD () ，
问题Q通过消息摘要方式使用上述内容生成，也即，
Q = MD(R, U|K) ，
在终端用户发起验证的请求中，服务器端将问题Q扭曲、封装为图形图像验证码或图像推理题等展现形式返回给终端用户，同时附带返回随机消息R给客户端。
终端用户根据问题Q完成作答，将答案A连同随机消息R一同发回至服务器端，服务器根据终端用户进行检验的请求，做如下判断：
获取用户动态信息，使用与上述相同的算法，也即，
U’ ≈ (IP, User-Agent, Time) ，
根据已生成的U’、检验请求中附带的随机消息R和服务器端私有常量K，使用与发起验证请求处理过程中相同的算法生成新的问题Q’，也即，
Q’ = MD(R, U’|K) ，
由于终端用户在发起验证和进行验证中是同一个客观对象，U’应完全等同于U，根据上述公式分析可知，新问题Q’ 应该完全等同于原问题Q，此时对比答案A与问题Q’，如果答案A与问题Q’相一致，答案正确，人机验证成功完成；如果答案A与问题Q’不相一致，答案不正确，人机验证失败，非真人或者真人答错情况。
上述基于消息摘要的人机验证的机制描述如下图（Figure 3）所示。
| 用户终端 | 应用服务器端 | |
| 发起验证请求 | ||
| 根据K、U生成R、Q,
返回给终端用户 |
||
| 根据问题Q作答
发送答案A、R进行检验 |
||
| 根据K、U’、R生成Q’,
检验答案A与问题Q’ |
||
| 收到检验结果
对 或 错 |
||
Figure 3 基于消息摘要的人机验证流程
新式的这种人机验证方式中，对话和通信发生在用户终端和应用服务器之间，与此前方案相比，减少了与Session会话管理服务的角色。在这样的人机验证过程中，不需要Session会话管理服务的介入。
应用服务器在这一过程中承担获取用户动态信息，构建人机验证问题，校验用户答案等任务，当通过人机验证后的请求再进一步继续后面的服务流程。
这一过程中，应用服务器的私钥保密，生成问题的算法可以公开，符合前述CAPTCHA测试不依赖算法的要求。将求解问题答案的过程等价于根据消息摘要逆推导消息原文的过程。
- 人机验证实验
在通用管理信息系统应用软件（-gMIS, -吉密斯） [15]中，我们进行了一项基于消息摘要的人机验证服务的实验。gMIS的用户登录模块行使在用户进行身份验证之前，此时我们并不知道终端用户是否是合法、被授权的用户，因此需要进行基于账号的登录验证。
在进行登录验证之前，为预防机器人登录或者暴力攻击账号等行为，我们首先需要知道终端用户是真人而非机器人。自然这里要用上CAPTCHA测试，以探明终端用户首先是人类，然后再进行账号校验。
在设计中，我们在服务器端预设了密钥常量K，并在登录界面使用隐式HTML表单字段的形式，将问题的“消息摘要”以明文的方式列在登录表单项中。
在生成的伪随机数R时，我们使用了如下含有65个字符的字符集
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz._,
所生成的伪随机字符串长度为100字节，则其探测和计算空间为
S = 65100 = 1.9558505399828548460859657546779e+181
也即，1后面181个零这么一个天文数字。
基于这一随机消息R，我们通过一定的算法使用其中一部分，以图形验证码的方式将问题Q发给终端用户。
在终端用户填写用户名、用户密码信息后，对所展示的人机验证问题进行作答；完成作答后，用户点击“递交”，此时HTML登录表达将用户信息（用户名、密码）、问题信息（答案和问题摘要）一并递交给应用服务器端。
应用服务器端接收到登录请求后，按前述方法进行人机验证。显而易见，随机数R所使用部分越长，也即验证码越长，暴力攻击的可能性就越小。
这一实现的源代码公布在源码托管网站GitHub上（-R/12SP）。
- 分析与讨论
- 安全性分析
对比传统人机验证流程（Figure 1）与新式基于消息摘要的人机验证流程（Figure 3），其中一个主要变化是Session服务器端不再参与验证流程。在传统方式下，需要Session服务器端生成用户Session ID，问题Q、答案A并将这些数据以列表的形式存储在Session服务器端。新式人机验证的流程中，通过预设常量K、随机数R动态生成的问题Q可以通过用户验证请求中的随机数R进行重现，从而节省了在Session服务器端保存列表数据的步骤，这是新式人机验证主要特征之一。
单向不可逆的哈希函数为这一流程提供了安全保证。客户端无法根据已经曝露的公开消息摘要逆变还原出消息原文，从而也无法获得用于人机验证的验证码。只有具备较高识图、读题能力的“人类”依靠真人的能力对验证码、验证问题进行识别，人机验证功能得以实现。消息摘要无法逆向的前提是搜索空间巨大，无法在现有计算能力的基础上在可接受时间范围内实现逆向搜索，进而无法根据消息摘要d找到消息原文m。
这种验证方式的主要应用思想是基于明文连接实现安全通信，相应地做法已经得到证明 [8]。其理论依据是消息摘要的不可逆性，而不是私有的替换、交换或置换、加长或截断等变通技巧，也不是加上时间因子、随机数因子等，尽管这些技巧也能够起到增大了破解、逆向难度的作用。
随着计算能力的提升尽管偶尔有针对哈希碰撞的安全性突破，多数是以海量计算条件为前提条件。 [16]叙述了针对MD5的碰撞， [17]报告了第一例成功的针对SHA1的碰撞攻击。
当求解较大数配对所耗费资源较大（较长时间或（与）较宽广的计算空间），就可能将之视同于求解一个人工智能任务，从而在应用层面满足CAPTCHA的规范性要求，也即，无法找到从问题到答案的映射函数y=f(x)。解决这个问题Q，寻求映射函数算法的计算空间近视于解决一个人工只能问题的计算空间，则CAPTCHA约束继续成立。
此外值得注意的是短时间内的二次应用的防范。一次成功的人机验证之后，客户端以“人类”的能力获得公开消息摘要和验证码的配对，可能将这一成功配对进行二次应用。一个可能的场景是，人类识别出某个伪随机数R与某个验证码相匹配成功时，可以做二次应用，针对这样的情况，可以在时间、空间等维度进行做限定，比如给每个R赋予一个有效期，然后维护一个有效R的“池”，以使得每个R与验证码的成功配对能用且只用一次。
- 部署便捷性与成本
人机验证过程中无需Session会话服务的接入，可以在一定成都上预防基于Session的拦截攻击 [12]，同时，也避免Session服务的单点故障，任一应用服务器可以独立地进行人机验证的部署，在终端用户被验证之前，无需联系Session进行ID及问题和答案的生成。
这种应用服务器单独承担人机验证功能的部署适合在多点负载均衡系统中应用，每个负载均衡的前端节点可以依靠自有的资源完成人机验证全过程。
另外，新式人机验证服务还能够节省Session服务，在终端用户未被识别为人类之前，不占用Session服务资源，无需在服务器端维护终端用户Id与问题对应列表。从而避开了基于应用层的Session Flooding攻击 [18]。
然而，计算机识图能力（或其他“智力”）的提升将加剧人机验证矛盾升级。目前的人机验证，基于人类识图能力这一基本特征展开，随着人工智能的发展机器识图能力逐年提升，在可见的未来，机器可能具备和人类一样的识图能力，甚至在某些专门领域机器的识图能力将超过人类的水平。届时，单纯基于识图能力的人机验证将面临新的挑战，这是本文所讨论议题的延续，人机验证必将基于另外一些人类所特有的特征开展新的人机验证的方式方法，而其中的实现原理是不变的，随机生成一条消息，以一种扭曲、不易或不被机器识别的形式展现给客户端，从而实现人机验证。当其理论所依据的“图灵测试”被机器所攻破时，人类还会继续寻找其他可行的人机识别的新思路。
- 小结
本文先后梳理和回顾了图灵测试、人机验证相关历史背景及其应用发展问题，分析了现存人机验证在服务器端请求处理方面的优劣。我们发现多数人机验证领域研究集中在对问题编排和破解，研究重点越来越多涉及到人工智能领域。然而在人机验证应用的部署和使用上，大多数依赖Session会话管理服务这一必需的角色，循此我们对人机验证的服务器部署及使用流程进行深入分析。
在此基础上提出了一种基于消息摘要的人机验证新设计，并对该机制安全性、实用性等方面进行了充分讨论。相比较此前传统人机验证设计，新的基于消息摘要的人机验证方法不需要额外的消息对存储，无需Session会话管理服务器端维护“对话”信息，与HTTP无状态匹配较好，在部署成本、易用性和便捷性方面有一定的优势。
References
| [1] | A. e. a. Turing, “Can automatic calculating machines be said to think?(1952),” B. Jack Copeland, 2004, p. 487. |
| [2] | M. B. N. H. L. Luis von Ahn, “The Offical CAPTCHA,” Carnegie Mellon University, 2000. [联机]. Available: http://www.captcha.net/. [访问日期: 03 2017]. |
| [3] | P. C. v. O. S. A. V. Alfred J. Menezes, “Pseudorandom Bits and Sequences,” 出处 Handbook of Applied Cryptography, CRC Press, 1996, p. 173. |
| [4] | M. M. J. M. Elie Bursztein, “Text-based CAPTCHA strengths and weaknesses,” 出处 CCS ’11 Proceedings of the 18th ACM conference on Computer and communications security, Illinois, 2011. |
| [5] | L. v. A. B. J. H. Langford, “CAPTCHA: Using Hard AI Problems for Security,” 出处 Advances in Cryptology — EUROCRYPT 2003, Berlin, 2003. |
| [6] | P. Golle, “Machine learning attacks against the Asirra CAPTCHA,” 出处 CCS ’08 Proceedings of the 15th ACM conference on Computer and communications security, Virginia, 2008. |
| [7] | 李爽, “Session安全性研究及应用,” 电子世界, 卷 2013, 编号 23, 2013. |
| [8] | M. W. Y. Y. J. M. J. W. Nikiforakis N., “SessionShield: Lightweight Protection against Session Hijacking,” 出处 Engineering Secure Software and Systems, Berlin, 2011. |
| [9] | G. Developers, “What is reCAPTCHA?,” Google, [联机]. Available: https://developers.google.com/recaptcha/. [访问日期: 03 2017]. |
| [10] | 中国铁路客服服务中心, “12306登录,” 中国铁路客服服务中心, [联机]. Available: https://kyfw.12306.cn/otn/login/init. [访问日期: 03 2017]. |
| [11] | J. L. a. J. Z. W. Ritendra Datta, “IMAGINATION: A Robust Image-based CAPTCHA Generation System,” 出处 Proceedings of the ACM Multimedia Conference, Singapore, 2005. |
| [12] | H. S. L. L. L. Y. Z. K. W. Zhenxing Liu, “A hash-based secure interface on plain connection,” 出处 Communications and Networking in China (CHINACOM), 2011 6th International ICST Conference on, Shanghai, 2011. |
| [13] | A. Kahate, “Digital Signatures,” 出处 Cryptography and Network Security, New Delhi, Tata McGraw-Hill Education, 2013, p. 165. |
| [14] | TechNet, “Message Digest Functions,” Microsoft, [联机]. Available: https://technet.microsoft.com/en-us/library/cc962033.aspx. [访问日期: 03 2017]. |
| [15] | Z. Liu, “gMIS, general Management Information System,” 10 2011. [联机]. Available: https://ufqi.com/dev/gmis/. [访问日期: 03 2017]. |
| [16] | X. W. a. D. F. a. X. L. a. H. Yu, “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD,” Cryptology ePrint Archive, p. 199, 2004. |
| [17] | E. B. P. K. A. A. Y. M. Marc Stevens, “The first collision for full SHA-1,” 02 2017. [联机]. Available: https://shattered.it/static/shattered.pdf. [访问日期: 03 2017]. |
| [18] | Z. L. H. C. X. C. Jie Yu, “A Detection and Offense Mechanism to Defend Against Application Layer DDoS Attacks,” 出处 Networking and Services, 2007. ICNS. Third International Conference, Athens, Greece, 2007. |
[1] 作者简介：刘振兴，原人民网研究院网络技术研究员，主要研究领域包括计算机网络通信协议、互联网后台支撑技术和网络架构与安全等，先后在Journal of Cloud Computing、IEEE Conferences、《计算机应用与软件》、《中国计算机学会通讯》、《互联网天地》等刊物发表多篇中英文论文，是Base62x、NatureDNS、GWA2、gMIS和GTAjax的主要创建者。
原文刊登于<<网络安全技术与应用>>, 2017年7月号.
