International Association for Cryptologic Research

International Association
for Cryptologic Research


Philippe Golle


Machine Learning Attacks Against the ASIRRA CAPTCHA
Philippe Golle
The ASIRRA CAPTCHA [EDHS2007], recently proposed at ACM CCS 2007, relies on the problem of distinguishing images of cats and dogs (a task that humans are very good at). The security of ASIRRA is based on the presumed difficulty of classifying these images automatically. In this paper, we describe a classifier which is 82.7% accurate in telling apart the images of cats and dogs used in ASIRRA. This classifier is a combination of support-vector machine classifiers trained on color and texture features extracted from images. Our classifier allows us to solve a 12-image ASIRRA challenge automatically with probability 10.3%. This probability of success is significantly higher than the estimate given in [EDHS2007] for machine vision attacks. The weakness we expose in the current implementation of ASIRRA does not mean that ASIRRA cannot be deployed securely. With appropriate safeguards, we believe that ASIRRA offers an appealing balance between usability and security. One contribution of this work is to inform the choice of safeguard parameters in ASIRRA deployments.
Cryptanalysis of a Cognitive Authentication Scheme
Philippe Golle David Wagner
We present attacks against two cognitive authentication schemes [W06] 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 [W06] are not secure against an eavesdropping adversary.
Tamper-Evident Digital Signatures: Protecting Certification Authorities Against Malware
We introduce the notion of tamper-evidence for digital signature generation in order to defend against attacks aimed at covertly leaking secret information held by corrupted network nodes. This is achieved by letting observers (which need not be trusted) verify the absence of covert channels by means of techniques we introduce herein. We call our signature schemes tamper-evident since any deviation from the protocol is immediately detectable. We demonstrate our technique for RSA-PSS and DSA signature schemes and how the same technique can be applied to Feige-Fiat-Shamir (FFS) and Schnorr signature schemes. Our technique does not modify the distribution of the generated signature transcripts, and has only a minimal overhead in terms of computation, communication, and storage. Keywords. covert channel, malware, observer, subliminal channel, tamper-evident, undercover