A Non-Probabilistic Time-Storage Trade-off for Unsalted Hashes
Resumo
This work proposes a new cryptanalytic non-probabilistic trade-off for unsalted hashes. It presents the main cryptanalytic trade-offs, making a comparison with the proposed method. Although the number of hash operations to recover an element is high compared with the traditional methods, the new method has the advantage of guaranteed success on the recovery of hashes, minimal and sequential disk read operations, unlike the existing probabilistic trade-offs.
Referências
Burns, R. C. and Long, D. D. (1997). Efficient distributed backup with delta compression. In Proceedings of the fifth workshop on I/O in parallel and distributed systems, pages 27–36. ACM.
Information Theory, Hellman, M. E. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on, 26(4):401–406.
Lemire, D., Kaser, O., and Aouiche, K. (2010). Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering, 69(1):3–28.
Mahoney, M. (2013). The zpaq open standard format for highly compressed data level 2. http://mattmahoney.net/dc/zpaq202.pdf. [Online; accessed 10-May2015].
Mogul, J. C., Douglis, F., Feldmann, A., and Krishnamurthy, B. (1997). Potential benefits of delta encoding and data compression for http. In ACM SIGCOMM Computer Communication Review, volume 27, pages 181–194. ACM.
Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. In Advances in Cryptology-CRYPTO 2003, pages 617–630. Springer.
Paulo, J. and Pereira, J. (2014). A survey and classification of storage deduplication systems. ACM Computing Surveys (CSUR), 47(1):11.
Percival, C. and Josefsson, S. (2015). The scrypt password-based key derivation function.
Provos, N. and Mazieres, D. (1999). A future-adaptable password scheme. In USENIX Annual Technical Conference, FREENIX Track, pages 81–91.
Rivest, R. (1992). The md5 message-digest algorithm. https://www.ietf.org/rfc/rfc1321.txt. [Online; accessed 02-May-2015].
Sabharwal, C. L. and Bratia, S. K. (1997). Image databases and near-perfect hash table. Pattern Recognition, 30(11):1867–1876.
Sleator, D. D. and Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686.
Stalings, W. (2005). Cryptography and Network Security. Upper Saddle River, NJ: Prentice Hall.
Zhang, W., Zhang, M., Liu, Y., and Wang, R. (2010). A new time-memory-resource trade-off method for password recovery. In Communications and Intelligence Information Security (ICCIIS), 2010 International Conference on, pages 75–79. IEEE.
Information Theory, Hellman, M. E. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on, 26(4):401–406.
Lemire, D., Kaser, O., and Aouiche, K. (2010). Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering, 69(1):3–28.
Mahoney, M. (2013). The zpaq open standard format for highly compressed data level 2. http://mattmahoney.net/dc/zpaq202.pdf. [Online; accessed 10-May2015].
Mogul, J. C., Douglis, F., Feldmann, A., and Krishnamurthy, B. (1997). Potential benefits of delta encoding and data compression for http. In ACM SIGCOMM Computer Communication Review, volume 27, pages 181–194. ACM.
Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. In Advances in Cryptology-CRYPTO 2003, pages 617–630. Springer.
Paulo, J. and Pereira, J. (2014). A survey and classification of storage deduplication systems. ACM Computing Surveys (CSUR), 47(1):11.
Percival, C. and Josefsson, S. (2015). The scrypt password-based key derivation function.
Provos, N. and Mazieres, D. (1999). A future-adaptable password scheme. In USENIX Annual Technical Conference, FREENIX Track, pages 81–91.
Rivest, R. (1992). The md5 message-digest algorithm. https://www.ietf.org/rfc/rfc1321.txt. [Online; accessed 02-May-2015].
Sabharwal, C. L. and Bratia, S. K. (1997). Image databases and near-perfect hash table. Pattern Recognition, 30(11):1867–1876.
Sleator, D. D. and Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686.
Stalings, W. (2005). Cryptography and Network Security. Upper Saddle River, NJ: Prentice Hall.
Zhang, W., Zhang, M., Liu, Y., and Wang, R. (2010). A new time-memory-resource trade-off method for password recovery. In Communications and Intelligence Information Security (ICCIIS), 2010 International Conference on, pages 75–79. IEEE.
Publicado
07/11/2016
Como Citar
SCHARDONG, Frederico; FORMOLO, Daniel.
A Non-Probabilistic Time-Storage Trade-off for Unsalted Hashes. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 16. , 2016, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 198-211.
DOI: https://doi.org/10.5753/sbseg.2016.19308.
