Untargeted Near-collision Attacks on Biometrics: Real-world Bounds and Theoretical Limits

A biometric recognition system can operate in two distinct modes: identification or verification. In the first mode, the system recognizes an individual by searching the enrolled templates of all the users for a match. In the second mode, the system validates a user's identity claim by comparing the fresh provided template with the enrolled template. The biometric transformation schemes usually produce binary templates that are better handled by cryptographic schemes, and the comparison is based on a distance that leaks information about the similarities between two biometric templates. Both the experimentally determined false match rate and false non-match rate through recognition threshold adjustment define the recognition accuracy, and hence the security of the system. To our knowledge, few works provide a formal treatment of security in case of minimal information leakage, i.e., the binary outcome of a comparison with a threshold. In this paper, we focus on untargeted attacks that can be carried out both online and offline, and in both identification and verification modes. On the first hand, we focus our analysis on the accuracy metrics of biometric systems. We provide the complexity of untargeted attacks using the False Match Rate (FMR) and the False Positive Identification Rate (FPIR) to address the security of these systems. Studying near-collisions with these metrics allows us to estimate the maximum number of users in a database, given a chosen FMR, to preserve the security and the accuracy. These results are evaluated on systems from the literature. On the other hand, we rely on probabilistic modelling to assess the theoretical security limits of biometric systems. The study of this metric space, and system parameters (template size, threshold and database size), gives us the complexity of untargeted attacks and the probability of a near-collision.