Paper 2017/603
Cryptanalytic Time-Memory Tradeoff for Password Hashing Schemes
Donghoon Chang, Arpan Jati, Sweta Mishra, and Somitra Kumar Sanadhya
Abstract
A cryptanalytic technique known as time-memory tradeoff (TMTO)
was proposed by Hellman for finding the secret key of a block cipher. This technique allows sharing the effort of key search between the two extremes of exhaustively enumerating all keys versus listing all possible ciphertext mappings produced by a given plaintext (i.e. table lookups). The TMTO technique has also been used as an effective cryptanalytic approach for password hashing schemes (PHS).
Increasing threat of password leakage from compromised password hashes demands a resource consuming algorithm to prevent the precomputation of the password hashes.
A class of password hashing designs provide such a defense against TMTO attack by ensuring that any reduction in the memory leads to exponential increase in runtime. These are called \textit{Memory hard} designs. However, it is generally difficult to evaluate the ``memory hardness" of a given PHS design.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- Time-Memory tradeoffpasswordhashinggraph traversalbit-reversal graphdouble butterfly graph
- Contact author(s)
- swetam @ iiitd ac in
- History
- 2017-06-23: received
- Short URL
- https://ia.cr/2017/603
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/603, author = {Donghoon Chang and Arpan Jati and Sweta Mishra and Somitra Kumar Sanadhya}, title = {Cryptanalytic Time-Memory Tradeoff for Password Hashing Schemes}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/603}, year = {2017}, url = {https://eprint.iacr.org/2017/603} }