Verifying secrets and relative secrecy

Abstract

Systems that authenticate a user based on a shared secret (such as a password or PIN) normally allows anyone to query whether the secret is a given value. For example, an ATM machine allows one to ask whether a string is the secret PIN of a (lost or stolen) ATM card. Yet such queries are prohibited in any model whose programs satisfy an information flow property like Noninterference. But there is a complexity-based justification for allowing these queries. A type system is given that provides the access control needed to prove that no well-tyoed program can leak secrets in polynomial time, or even leak them with nonnegligible probability if secrets are of sufficient length and randomly chosen. However, there are well-typed deterministic programs in a synchronous concurrent model capable of leaking secrets in linear time.