Back to search

University of York

Hash-Dependent Passwords and Memory Hard Functions

Abstract

dc:description.abstract

Hash rates provided by specialized hardware such as ASICs render schemes based on iterated hashing ineffective in protecting password storage, and hence memory-hard functions (MHFs) are recommended for modern password storage. The study of MHFs so far has mainly focused on providing provable guarantees on their minimum expected time--memory complexity cost per evaluation. However, this does not tell us to what degree passwords remain unrecoverable if password banks protected using MHFs are compromised. This thesis aims to answer this question in the context of up to date password security models. This means proving unrecoverability bounds for a large class of MHFs: graph-based data-independent MHFs (iMHFs). Specifically, we prove upper bounds on the \emph{multi-instance} unrecoverability of any graph-based iMHF, based on the unguessability of stored passwords, the number of hash evaluations it carries out, and crucially the cumulative memory complexity of the adversary. To prove this result, we extend the standard definitions of both guessability, and of memory-hardness to strictly stronger \emph{hash-dependent} settings. We prove reductions from unrecoverability to unguessability in the hash-dependent setting and show that, unlike the hash-independent setting, unpredictable salting is essential in the hash-dependent setting. We then prove that, in contrast to general MHFs, graph-based iMHFs are memory-hard in the hash-dependent setting. In the last part of the thesis, the analysis is extended to prove indifferentiability results for iMHFs in a large class of multi-stage games, i.e., games which follow a sample, salt and use structure. We show that in this class of games, an iMHF is as secure as a random oracle. Importantly, we give a treatment of adversaries with access to preprocessing information.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of York
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dodd, Charles
Advisor dc:contributor.advisor
  • Siamak, Shahandashti

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Dc Identifier Grantnumber
EP/T518025/1

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Dodd, Charles. Hash-Dependent Passwords and Memory Hard Functions. doctoral thesis, University of York, 2025.