Exhaustive search is generally a last resort for solving a problem: each possible state of a system is generated and evaluated against a condition to find if the problem solution is attained. In some cases, for example in the reversal of cryptographic hash functions that make use of the salting technique, there are very few valid alternatives. However, the set of candidate solutions can be extremely large and therefore very substantial computing resources are needed to walk through the search space in a reasonable time. On the other hand, exhaustive search is very often embarrassingly parallel and so the task can be easily accelerated by distributing the work on a multitude of devices. In this paper we propose a pattern to parallelize general exhaustive searches on a heterogeneous and hierarchical network of computing nodes. We validate this pattern by applying it to the reversal of MD5 and SHA1 hash functions, both at coarse grain (work dispatching among nodes) and at fine grain (work made by each thread), reaching linear scalability with increasing computing power of the participating nodes. In particular, we show how to implement and optimize the hash key search on a GPGPU, achieving near-maximal throughput on various models of NVIDIA devices programmed with CUDA.

Barbieri, D., Cardellini, V., Filippone, S. (2014). Exhaustive key search on clusters of GPUs. In 2014 28th IEEE International Parallel & Distributed Processing Symposium Workshops (pp.1160-1168). IEEE [10.1109/IPDPSW.2014.131].

Exhaustive key search on clusters of GPUs

CARDELLINI, VALERIA;FILIPPONE, SALVATORE
2014-01-01

Abstract

Exhaustive search is generally a last resort for solving a problem: each possible state of a system is generated and evaluated against a condition to find if the problem solution is attained. In some cases, for example in the reversal of cryptographic hash functions that make use of the salting technique, there are very few valid alternatives. However, the set of candidate solutions can be extremely large and therefore very substantial computing resources are needed to walk through the search space in a reasonable time. On the other hand, exhaustive search is very often embarrassingly parallel and so the task can be easily accelerated by distributing the work on a multitude of devices. In this paper we propose a pattern to parallelize general exhaustive searches on a heterogeneous and hierarchical network of computing nodes. We validate this pattern by applying it to the reversal of MD5 and SHA1 hash functions, both at coarse grain (work dispatching among nodes) and at fine grain (work made by each thread), reaching linear scalability with increasing computing power of the participating nodes. In particular, we show how to implement and optimize the hash key search on a GPGPU, achieving near-maximal throughput on various models of NVIDIA devices programmed with CUDA.
15th IEEE International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC 2014)
Phoenix, Arizona
2014
Rilevanza internazionale
contributo
mag-2014
2014
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
https://ieeexplore.ieee.org/document/6969513
Intervento a convegno
Barbieri, D., Cardellini, V., Filippone, S. (2014). Exhaustive key search on clusters of GPUs. In 2014 28th IEEE International Parallel & Distributed Processing Symposium Workshops (pp.1160-1168). IEEE [10.1109/IPDPSW.2014.131].
Barbieri, D; Cardellini, V; Filippone, S
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/93500
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 2
social impact