Questi hash sono talvolta denominati "hash delle password", perché sono progettati per proteggere esattamente dal modello di minaccia che hai menzionato: qualcuno che riceve una copia del tuo database di password e lo impone. Un sottoinsieme è anche noto come "funzioni di derivazione chiave basata su password (PBKDF)".
Scrypt è uno strumento relativamente nuovo, ma ampiamente conosciuto e ampiamente utilizzato creato per correggere i difetti negli algoritmi PBKDF2 e bcrypt più consolidati che possono essere drasticamente velocizzati da ASIC o FPGA personalizzati e facilmente parallelizzabili su una GPU .
L'innovazione centrale in scrypt è un bitvector pseudo-casuale molto grande, a cui si accede molto spesso in modo pseudo-casuale. Ciò significa che lo "trucco" standard per la modifica delle caratteristiche di prestazione del codice, lo spazio-tempo-compromesso è costoso in entrambe le direzioni . In particolare, il bitvector molto grande rende l'algoritmo difficile da parallelizzare, dal momento che si avranno molti elementi di calcolo che battono il bus di memoria (limitando l'accelerazione parallela), o molte copie del bitvector molto grande nei singoli elementi di calcolo (rendendo parallelismo costoso). Il pattern di accesso pseudo-casuale garantisce inoltre che la previsione delle branch, la previsione della cache, il prefetching della memoria e tali ottimizzazioni che riducono la cache siano inutili, e la dimensione del bitvector assicura che soffierete ogni cache che lanciate.
Teoricamente, poiché sia il bitvector che il pattern di accesso sono "solo" pseudo-casuali, sono ancora determinati algoritmicamente.
Ergo, potresti ridurre i requisiti di memoria semplicemente calcolando tutto al volo e non mantenendo affatto il bitvector in memoria. Tuttavia, l'algoritmo è progettato in modo tale che questo calcolo sia ancora molto lento e l'algoritmo è progettato per accedere ripetutamente agli stessi elementi (ma non è possibile prevedere facilmente quando e in quale ordine), quindi è necessario ri-calcolare gli elementi più e più volte. OTOH, è possibile ridurre il tempo richiesto pre-calcolando tutti i valori possibili, ma si otterrebbe un'esplosione nei requisiti di memoria.
In ogni caso, il trade-off è proibitivamente costoso: non hai altra scelta che usare sia memoria di grandi dimensioni che molti cicli di CPU.
Fondamentalmente, puoi pensare alle due sequenze pseudo-casuali come una singola sequenza pseudo-casuale molto complessa, e al bitvector come a una cache. Ma la "cache" è progettata in modo tale che non puoi né rimuoverla e cercare di compensare ciò con maggiore velocità di elaborazione o parallelismo, né puoi espanderla e così risparmiare tempo di elaborazione e pagalo con un maggiore utilizzo della memoria.