Cryptanalysis of the convex hull click human identification protocol
Cryptanalysis of the convex hull click human identification protocol
复制标题
DOI：
10.1007/s10207-012-0161-x
复制
发表时间：
2013-04-01
影响因子：
3.2
通讯作者：
Wang, Huaxiong
中科院分区：
文献类型：
--
作者：
Asghar, Hassan Jameel;Li, Shujun;Wang, Huaxiong
最近，Sobrado和Birget提出了一种基于凸壳的人类识别协议，该协议的步骤可以由人类在没有额外帮助的情况下执行。该协议的主要部分涉及用户在一组图形图标中形成一个秘密图标的凸包，然后在这个凸包中随机点击。虽然已经讨论了该协议的一些基本安全问题，但还缺乏全面的安全分析。本文对这种基于凸包的协议的安全性进行了分析。特别地，我们展示了两种概率攻击，它们仅在观察少量身份验证会话后就泄露了用户的秘密。这些攻击可以有效地实现，因为它们的时间和空间复杂性大大低于暴力攻击。我们表明，虽然第一次攻击可以通过适当选择的系统参数值来减轻，但第二次攻击以不可忽略的概率成功，即使使用超过可用性阈值的大系统参数值。
Recently, a convex hull-based human identification protocol was proposed by Sobrado and Birget, whose steps can be performed by humans without additional aid. The main part of the protocol involves the user mentally forming a convex hull of secret icons in a set of graphical icons and then clicking randomly within this convex hull. While some rudimentary security issues of this protocol have been discussed, a comprehensive security analysis has been lacking. In this paper, we analyze the security of this convex hull-based protocol. In particular, we show two probabilistic attacks that reveal the user's secret after the observation of only a handful of authentication sessions. These attacks can be efficiently implemented as their time and space complexities are considerably less than brute force attack. We show that while the first attack can be mitigated through appropriately chosen values of system parameters, the second attack succeeds with a non-negligible probability even with large system parameter values that cross the threshold of usability.