A secure human identification protocol aims at authenticating human users to a remote server when even the users' inputs are not hidden from an adversary. Recently, the authors proposed a human identification protocol in the RSA Conference 2007, which is loosely based on the ability of humans to efficiently process an image. The advantage being that an automated adversary is not effective in attacking the protocol without human assistance. This paper extends that work by trying to solve some of the open problems. First, we analyze the complexity of defeating the proposed protocols by quantifying the workload of a human adversary. Secondly, we propose a new construction based on textual CAPTCHAs (Reverse Turing Tests) in order to make the generation of automated challenges easier. We also present a brief experiment involving real human users to find out the number of possible attributes in a given image and give some guidelines for the selection of challenge questions based on the results. Finally, we analyze the previously proposed protocol in detail for the relationship between the secrets. Our results show that we can construct human identification protocols based on image evaluation with reasonably quantified'' security guarantees based on our model.
@cite_14: 
@cite_11: Can we secure user authentication against eavesdropping adversaries, relying on human cognitive functions alone, unassisted by any external computational device? To accomplish this goal, we propose challenge response protocols that rely on a shared secret set of pictures. Under the considered brute-force attack the protocols are safe against eavesdropping, in that a modestly powered adversary who fully records a series of successful interactions cannot compute the user's secret. Moreover, the protocols can be tuned to any desired level of security against random guessing, where security can be traded-off with authentication time. The proposed protocols have two drawbacks: First, training is required to familiarize the user with the secret set of pictures. Second, depending on the level of security required, entry time can be significantly longer than with alternative methods. We describe user studies showing that people can use these protocols successfully, and quantify the time it takes for training and for successful authentication. We show evidence that the secret can be maintained for a long time (up to a year) with relatively low loss.
@cite_7: One interesting and important challenge for the cryptologic community is that of providing secure authentication and identification for unassisted humans. There are a range of protocols for secure identification which require various forms of trusted hardware or software, aimed at protecting privacy and financial assets. But how do we verify our identity, securely, when we don't have or don't trust our smart card, palmtop, or laptop? In this paper, we provide definitions of what we believe to be reasonable goals for secure human identification. We demonstrate that existing solutions do not meet these reasonable definitions. Finally, we provide solutions which demonstrate the feasibility of the security conditions attached to our definitions, but which are impractical for use by humans.
@cite_9: At Eurocrypt'91, Matsumoto and Imai presented a human identification scheme for insecure channels, which is suitable for human ability of memorizing and processing a short secret. It prevents an intruder from peeping user in typing password on terminal connected to the central computer. However, in this paper, we are going to propose a new attack, called the replay challenge attack, where a malicious terminal pretends to be the host and replays the host's challenges to reveal the secret password. A modified scheme will be proposed to avoid this attack.
@cite_6: Human-machine identification is an important problem in cryptography that has applications in network access, electronic commerce, and smart-card design. It is a hard problem largely because human users have a very limited capacity in memorizing secrets and in performing protocols. Therefore, in addition to the requirement that a human-machine identification scheme must be provably secure, the scheme has to be practical in the sense that it must be feasible for a human user to participate. In this paper, we develop a new scheme for this problem. Our scheme improves upon some of the previously proposed human-machine identification schemes. We present a vigorous security analysis of our scheme. We also present some attacks to show previously proposed schemes could be vulnerable.
@cite_5: It is an interesting problem how a human can prove its identity to a trustworthy (local or remote) computer with untrustworthy input devices and via an insecure channel controlled by adversaries. Any input devices and auxiliary devices are untrustworthy under the following assumptions: the adversaries can record humans’ operations on the devices, and can access the devices to replay the recorded operations. Strictly, only the common brain intelligence is available for the human. In this paper, such an identication system is called SecHCI as the abbreviation Secure Human-Computer Identication (or Interface). In the real world, SecHCI means the peeping attacks to widely-used xed passwords: an adversary can observe your password via his own eyes or some hidden device (such as min-camera) when your input them on your keyboard or with your mouse. Compared with human-computer identications with the aid of trustworthy hardware devices, only a few contributions have devoted to the design and analysis of SecHCI. The most systematic works are made by N. J. Hopper & M. Blum recently: some formal denitions are given and the feasibility is shown by several SecHCI protocols with acceptable security (but usability is not very good because of their inherent limitations). In this paper, we give comprehensive investigations on SecHCI, from both theoretical and practical viewpoint, and with both system-oriented and usercentered methods. A user study is made to show problems of xed passwords, the signicance of peeping attack and some design principles of human-computer identications. All currently known SecHCI protocols and some related works (such as visual graphical passwords and CAPTCHAs) are surveyed in detail. In addition, we also give our opinions on future research and suggest a new prototype protocol as a possible solution to this problem.
@cite_16: We present attacks against two cognitive authentication schemes [3] recently proposed at the 2006 IEEE Symposium on Security and Privacy. These authentication schemes are designed to be secure against eavesdropping attacks while relying only on human cognitive skills. They achieve authentication via challenge response protocols based on a shared secret set of pictures. Our attacks use a SAT solver to recover a user’s key in a few seconds, after observing only a small number of successful logins. These attacks demonstrate that the authentication schemes of [3] are not secure against an eavesdropping adversary.
@cite_17: Can you securely prove your identity to a host computer by using no dedicated software at your terminal and no dedicated token at your hands? Conventional password checking schemes do not need such a software and hardware but have a disadvantage that an attacker who has correctly observed an input password by peeping or wiretapping can perfectly impersonate the corresponding user. Conventional dynamic (one-time) password schemes or zero-knowledge identification schemes can be securely implemented but require special software or hardware or memorandums. This paper develops human-friendly identification schemes such that a human prover knowing a secret key in her or his brain is asked a visual question by a machine verifier, who then checks if an answer sent from the prover matches the question with respect to the key. The novelty of these schemes lies in their ways of displaying questions. This paper also examines an application of the human identification schemes to human-computer cryptographic communication protocols.
The first work on human identification dates back to @cite_14 . Since then a lot of other schemes have been proposed in literature @cite_9 , @cite_17 , @cite_6 , @cite_7 , @cite_5 , @cite_11 . Some of them were broken in @cite_9 , @cite_16 . While most of them involve some numerical calculations like @cite_14 and the HB protocol @cite_7 , they can be implemented using some graphical interface employing pictures as memory aids. We can categorized the human identification protocols into two broad categories: Protocols built to be secure against general eavesdropping adversaries and protocols secure against only guessing adversaries'' i.e. Adversaries who do not see the user's input and hence try to guess the secret or impersonate the user without any apriori knowledge. Protocols mentioned so far fall in the first category. They have a drawback, however, that they involve extra computation from the user. As an example, in the HB protocol @cite_7 , the user is required to compute bit-wise binary multiplication for some number of bits in every iteration. This may not seem much but to obtain a higher level of security, the number of computations increase significantly.