A Multithreaded SHA-512-Based Hashing Algorithm Using Merkle Trees

Today’s hashing algorithms, such as SHA-256 or SHA-512, used to guarantee data security and integrity, are characterized by an iterative design and therefore do not take full advantage of the parallel capabilities of modern multicore processors. In this context, the objective of this thesis is to exploit server-side parallelism to increase the total amount of hashing work performed during password verification while maintaining an acceptable authentication latency. By exploiting Merkle trees, a binary-tree-based data structure that enables hash computations to be distributed across multiple CPU cores, a new hashing algorithm, parallel_sha512, has been developed. This algorithm divides the hashing process among different cores and combines partial results into a single final hash value. The algorithm and its variants are described through pseudocode and are implemented in the C++ programming language and in OpenCL. Their theoretical and experimental performance is evaluated against established iterative approaches. CPU and GPU implementations are compared, and custom hashcat modules and kernels are developed to assess the algorithms in password-cracking scenarios. Finally, the security implications of the Merkle-tree structure are analyzed by estimating the probability that a leaf modification leaves the final Merkle root unchanged.

Gli algoritmi di hashing odierni, come SHA-256 o SHA512, utilizzati per garantire la sicurezza e l'integrità dei dati, sono caratterizzati da una progettazione di tipo iterativo e pertanto non sfruttano le capacità computazionali dei processori multicore moderni. In questo contesto, l'obiettivo di questa tesi è quello di sfruttare il parallelismo lato server per aumentare la quantità di hashing eseguito durante la verifica della password, mantenendo al contempo una latenza di autenticazione accettabile. Utilizzando i Merkle tree, una struttura dati basata su alberi binari che permette di distribuire il calcolo degli hash su molteplici core della CPU, è stato implementato un nuovo algoritmo di hashing, parallel_sha512. Questo algoritmo suddivide il processo di hashing su diversi core e combina i risultati parziali di ciascun core in un unico hash finale. L'algoritmo e le sue varianti sono descritte tramite pseudocodice e implementati in C++ e in OpenCL. Le loro prestazioni teoriche e sperimentali sono state valutate rispetto ad funzioni hash iterative tradizionali. Sono state confrontate le implementazioni su CPU e GPU e sono stati sviluppati moduli e kernel hashcat personalizzati per valutare gli algoritmi in scenari di password cracking. Infine, sono state analizzate le implicazioni di sicurezza dei Merkle tree, stimando la probabilità che una modifica a una foglia lasci invariata la radice finale del Merkle tree.