Skip to content

Instantly share code, notes, and snippets.

@syncom
Last active May 9, 2018 17:21
Show Gist options
  • Save syncom/d3550af8272975d4f43dc8d728559b24 to your computer and use it in GitHub Desktop.
Save syncom/d3550af8272975d4f43dc8d728559b24 to your computer and use it in GitHub Desktop.
Memo: PIS-RT, Rainbow Table Search Processing in Storage

PIS-RT: Processing In Storage - Rainbow Tables

The idea described in this tech memo is to accelerate rainbow table searches inside the SSD SoC.

A "rainbow table" is a data structure containing precomputed "chains" for reversing cryptographic hash functions, usually for cracking password hashes. A good yet simple instruction of the rainbow table by Kestas can be found at http://kestas.kuliukas.com/RainbowTables/.

RainbowCrack (http://project-rainbowcrack.com/) is a project that generates rainbow tables (for various hash algorithms) and creates tools for cracking hashes using rainbow tables. As can be seen from the page http://project-rainbowcrack.com/buy.php, rainbow table files are generally big, if not enormous, in size (the aforementioned page contains several TB of data). Because of this, rainbow tables are usually stored in non-volatle memory, and (partially) loaded to the host PC's main (volatile) memory when cracking hashes.

As far as rainbow table search is concerned, a rainbow table contains (unliked "reduced") hash values, and the bulk of a search operation is to find a match between the hash value to crack and existing hash values in the rainbow table. Note that a rainbow table can be sorted so that a binary search can be facilitated.

PIS-RT (Processing In Storage-Rainbow Table) is the approach that performs the above table lookup operation (i.e., matching a hash in the rainbow table) inside the disk (SSD in particular), possibly with a hardware module that does a linear (if rainbow table is not sorted) or binary (if rainbow table is sorted) search. This will significantly save I/O cost between the device (SSD) and the host (PC), and thus seems to be an architecture that fits the hash cracking application.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment