  Using the computational resources of an untrusted third party to crack a
password hash can pose a high number of privacy and security risks. The act of
revealing the hash digest could in itself negatively impact both the data
subject who created the password, and the data controller who stores the hash
digest. This paper solves this currently open problem by presenting a
Privacy-Preserving Password Cracking protocol (3PC), that prevents the third
party cracking server from learning any useful information about the hash
digest, or the recovered cleartext. This is achieved by a tailored anonymity
set of decoy hashes, based on the concept of predicate encryption, where we
extend the definition of a predicate function, to evaluate the output of a one
way hash function. The protocol allows the client to maintain plausible
deniability where the real choice of hash digest cannot be proved, even by the
client itself. The probabilistic information the server obtains during the
cracking process can be calculated and minimized to a desired level. While in
theory cracking a larger set of hashes would decrease computational speed, the
3PC protocol provides constant-time lookup on an arbitrary list size, bounded
by the input/output operation per second (IOPS) capabilities of the third party
server, thereby allowing the protocol to scale efficiently. We demonstrate
these claims both theoretically and in practice, with a real-life use case
implemented on an FPGA architecture.
