Efficient Cryptographic Password Hardening Services From Partially Oblivious Commitments


Password authentication still constitutes the most widespread authentication concept on the Internet today, but the human incapability to memorize safe passwords has left this concept vulnerable to various attacks ever since. Affected enterprises such as Facebook now strive to mitigate such attacks by involving external cryptographic services that harden passwords. Everspaugh et al. provided the first comprehensive formal treatment of such a service, and proposed the $\mathrm{P{\small YTHIA}}$ PRF-Service as a cryptographically secure solution (Usenix Security’15). $\mathrm{P{\small YTHIA}}$ relies on a novel cryptographic primitive called partially oblivious pseudorandom functions, and its security is proven under a strong new interactive assumption in the random oracle model.
In this work, we first prove that this strong assumption is inherently necessary for the $\mathrm{P{\small YTHIA}}$ construction, i.e., it cannot be weakened without invalidating the security of $\mathrm{P{\small YTHIA}}$. More generally, it is impossible to reduce the security of $\mathrm{P{\small YTHIA}}$ to any non-interactive assumptions. Hence any efficient, scalable password hardening service that is secure under weaker assumptions necessarily requires a conceptually different construction. To this end, we propose a construction for password hardening services based on a novel cryptographic primitive called partially oblivious commitments, along with an efficient secure instantiation based on simple assumptions. The performance and storage evaluation of our prototype implementation shows that our protocol runs almost twice as fast as $\mathrm{P{\small YTHIA}}$, while achieving a slightly relaxed security notion but relying on weaker assumptions.

23rd ACM Conference on Computer and Communications Security (CCS 2016)