Paper 2017/225

Bandwidth Hard Functions for ASIC Resistance

Ling Ren and Srinivas Devadas

Abstract

Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC's area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC's energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC's energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2017
Contact author(s)
renling @ mit edu
History
2017-09-30: last of 2 revisions
2017-03-08: received
See all versions
Short URL
https://ia.cr/2017/225
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/225,
      author = {Ling Ren and Srinivas Devadas},
      title = {Bandwidth Hard Functions for ASIC Resistance},
      howpublished = {Cryptology ePrint Archive, Paper 2017/225},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/225}},
      url = {https://eprint.iacr.org/2017/225}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.