Cryptanalysis of the convex hull click human identification protocol

Hassan Jameel Asghar; Shujun Li; Josef Pieprzyk; Huaxiong Wang

doi:10.1007/978-3-642-18178-8-3

Cryptanalysis of the convex hull click human identification protocol

Hassan Jameel Asghar, Shujun Li, Josef Pieprzyk, Huaxiong Wang

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

Abstract

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. In this paper we show two efficient probabilistic attacks on this protocol which reveal the user's secret after the observation of only a handful of authentication sessions. 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 which cross the threshold of usability.

Original language	English
Title of host publication	Information Security - 13th International Conference, ISC 2010, Revised Selected Papers
Editors	Mike Burmester, Gene Tsudik, Spyros S. Magliveras
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	24-30
Number of pages	7
Volume	6531
ISBN (Print)	9783642181771
DOIs	https://doi.org/10.1007/978-3-642-18178-8-3
Publication status	Published - 2010
Event	13th Information Security Conference, ISC 2010 - Boca Raton, FL, United States Duration: 25 Oct 2010 → 28 Oct 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6531 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	13th Information Security Conference, ISC 2010
Country/Territory	United States
City	Boca Raton, FL
Period	25/10/10 → 28/10/10

Access to Document

10.1007/978-3-642-18178-8-3

Cite this

Asghar, H. J., Li, S., Pieprzyk, J., & Wang, H. (2010). Cryptanalysis of the convex hull click human identification protocol. In M. Burmester, G. Tsudik, & S. S. Magliveras (Eds.), Information Security - 13th International Conference, ISC 2010, Revised Selected Papers (Vol. 6531, pp. 24-30). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6531 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-642-18178-8-3

Asghar, Hassan Jameel ; Li, Shujun ; Pieprzyk, Josef et al. / Cryptanalysis of the convex hull click human identification protocol. Information Security - 13th International Conference, ISC 2010, Revised Selected Papers. editor / Mike Burmester ; Gene Tsudik ; Spyros S. Magliveras. Vol. 6531 Berlin : Springer, Springer Nature, 2010. pp. 24-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a43cd91f1e2d45829ab58bd6b634c1bb,

title = "Cryptanalysis of the convex hull click human identification protocol",

abstract = "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. In this paper we show two efficient probabilistic attacks on this protocol which reveal the user's secret after the observation of only a handful of authentication sessions. 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 which cross the threshold of usability.",

author = "Asghar, {Hassan Jameel} and Shujun Li and Josef Pieprzyk and Huaxiong Wang",

year = "2010",

doi = "10.1007/978-3-642-18178-8-3",

language = "English",

isbn = "9783642181771",

volume = "6531",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "24--30",

editor = "Mike Burmester and Gene Tsudik and Magliveras, {Spyros S.}",

booktitle = "Information Security - 13th International Conference, ISC 2010, Revised Selected Papers",

address = "United States",

note = "13th Information Security Conference, ISC 2010 ; Conference date: 25-10-2010 Through 28-10-2010",

}

Asghar, HJ, Li, S, Pieprzyk, J & Wang, H 2010, Cryptanalysis of the convex hull click human identification protocol. in M Burmester, G Tsudik & SS Magliveras (eds), Information Security - 13th International Conference, ISC 2010, Revised Selected Papers. vol. 6531, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6531 LNCS, Springer, Springer Nature, Berlin, pp. 24-30, 13th Information Security Conference, ISC 2010, Boca Raton, FL, United States, 25/10/10. https://doi.org/10.1007/978-3-642-18178-8-3

Cryptanalysis of the convex hull click human identification protocol. / Asghar, Hassan Jameel; Li, Shujun; Pieprzyk, Josef et al.
Information Security - 13th International Conference, ISC 2010, Revised Selected Papers. ed. / Mike Burmester; Gene Tsudik; Spyros S. Magliveras. Vol. 6531 Berlin: Springer, Springer Nature, 2010. p. 24-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6531 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Cryptanalysis of the convex hull click human identification protocol

AU - Asghar, Hassan Jameel

AU - Li, Shujun

AU - Pieprzyk, Josef

AU - Wang, Huaxiong

PY - 2010

Y1 - 2010

N2 - 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. In this paper we show two efficient probabilistic attacks on this protocol which reveal the user's secret after the observation of only a handful of authentication sessions. 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 which cross the threshold of usability.

AB - 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. In this paper we show two efficient probabilistic attacks on this protocol which reveal the user's secret after the observation of only a handful of authentication sessions. 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 which cross the threshold of usability.

UR - http://www.scopus.com/inward/record.url?scp=79251569573&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18178-8-3

DO - 10.1007/978-3-642-18178-8-3

M3 - Conference proceeding contribution

SN - 9783642181771

VL - 6531

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 24

EP - 30

BT - Information Security - 13th International Conference, ISC 2010, Revised Selected Papers

A2 - Burmester, Mike

A2 - Tsudik, Gene

A2 - Magliveras, Spyros S.

PB - Springer, Springer Nature

CY - Berlin

T2 - 13th Information Security Conference, ISC 2010

Y2 - 25 October 2010 through 28 October 2010

ER -

Asghar HJ, Li S, Pieprzyk J, Wang H. Cryptanalysis of the convex hull click human identification protocol. In Burmester M, Tsudik G, Magliveras SS, editors, Information Security - 13th International Conference, ISC 2010, Revised Selected Papers. Vol. 6531. Berlin: Springer, Springer Nature. 2010. p. 24-30. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-18178-8-3

Cryptanalysis of the convex hull click human identification protocol

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this