About

A Case for Rainbow Tables in 2019 and Beyond

Rainbow tables went out of style a few years ago when GPU-accelerated password cracking became popular. With tools like hashcat, it no longer made sense to invest the effort to obtain the existing obsolete tables. Furthermore, no GPU-accelerated open-source tools existed to create new tables with. For these reasons, the world of rainbow tables was forgotten by the infosec community.

However, rule-based cracking and rainbow table cracking were never exclusive strategies. They were (and still are, in fact), complementary. Rules are great at finding patterns, which are commonly set by users; rainbow tables are effective against fully random passwords, which can exist for highly sensitive accounts.

For example, if the database of NTLM password hashes for a Windows domain were obtained, the optimal strategy would be:

  1. Use hashcat to brute-force all 1-7 character passwords (this can be done quickly).
  2. Use hashcat to crack passwords based on rules (variable time).
  3. Use rainbow tables to break complex 8-character passwords (a few hours).
  4. Use rainbow tables to break complex 9-character passwords (a few days).

While brute-forcing 8-character passwords is very much possible with hashcat, it is inefficient to do so for smaller numbers of hashes:

Hashcat arguments used: "-m 1000 -a 3 -w 3 -O hashes.txt ?a?a?a?a?a?a?a?a"

As shown in the graph above, on a machine with an AMD Ryzen 1900X CPU and two AMD Vega 64 GPUs, hashcat takes roughly 38 hours to brute-force one hundred 8-character NTLM passwords, whereas the Rainbow Crackalack software (with the NTLM-8 tables) achieves a 93% success rate in just under 2 hours!

To further drive the point home, consider 9-character NTLM passwords (which are generally considered to be very strong). With the equipment above, brute-forcing just 25% of the 9-character space would take over 37 days. Once created, however, rainbow tables are estimated to achieve the same results in under 19 hours!

Overview of the Rainbow Crackalack Project

The Rainbow Crackalack project began in late 2018 with the following goals:

  1. Create high-quality, multi-platform, open-source software to generate rainbow tables and perform hash lookups with GPU acceleration. (done!)
  2. Create 8-character NTLM tables and distribute them for free. (done!)
  3. Create 9-character NTLM tables and distribute them for free. (ongoing)
  4. Add support for MD5, SHA-1, SHA-256 hashes, as these are actively used by custom web applications. (planned)

Without additional corporate & community support, tables covering 10% of the NTLM 9-character space can be generated by the end of 2019. A Kickstarter project has been created to seek additional funds to accelerate this goal and push towards the 50% range. Individual and corporate sponsorship levels are available!

Usage Examples

The following example shows one hundred NTLM 8-character password hashes being cracked by the crackalack_lookup tool:

# ./crackalack_lookup /NTLM8_Master/ random_ntlm_hashes_8_chars_101.txt Rainbow Crackalack v1.0 Copyright 2018-2019 Positron Security LLC <https://www.positronsecurity.com/> Make Rainbow Tables Great Again Found 1 platforms. Found 2 devices on platform #0. Device #0: Vendor: Advanced Micro Devices, Inc. Name: gfx900 Version: OpenCL 2.0 Driver: 2862.0 (HSA1.1,LC) Max compute units: 64 Max work group size: 256 Global memory size: 8573157376 Device #1: Vendor: Advanced Micro Devices, Inc. Name: gfx900 Version: OpenCL 2.0 Driver: 2862.0 (HSA1.1,LC) Max compute units: 64 Max work group size: 256 Global memory size: 8573157376 Binary searching will be done with 32 threads. Loaded 101 of 101 uncracked hashes from random_ntlm_hashes_8_chars_101.txt. Pre-computing hash #1: a7c002406a080278885e47da3909187f... Note: optimized NTLM8 kernel will be used for precomputation. Completed in 16.4 secs. Pre-computing hash #2: bb53c0cb3a8cf0f71f0d6b170ff6b622... Completed in 16.5 secs. Pre-computing hash #3: 8e7c7397e513cee2cb50c2fc174ca7b3... Completed in 16.5 secs. Pre-computing hash #4: c260b99e3b87dfd7538acae873f99291... Completed in 16.6 secs. Pre-computing hash #5: 6055c3fc48f8260ece230fe8b599375e... Completed in 16.6 secs. Pre-computing hash #6: bdabd5d2332764e0f15a8dc7ee0c1d3a... Completed in 16.6 secs. [...] Pre-computation finished in 28 mins, 11 secs. Processing compressed table: /NTLM8_Master/ ntlm_ascii-32-95#8-8_0_422000x67108864_206.rtc... Table loaded in 2.0 secs. Searching table for matching endpoints... Table searched in 8.8 secs. Checking 79462 potential matches... HASH CRACKED => f417de201da2836457d3d893281e6b0f:2M*CD'HD Completed false alarm checks in 7.0 secs. Processing compressed table: /NTLM8_Master/ ntlm_ascii-32-95#8-8_0_422000x67108864_1.rtc... Table loaded in 1.5 secs. Searching table for matching endpoints... Table searched in 8.1 secs. Checking 51869 potential matches... HASH CRACKED => 4591f8e93ac153282059b5629607aceb: fdrp_<t HASH CRACKED => 4175d41bb49cd4fd42069435228f0135:`A7&tlSo Completed false alarm checks in 4.0 secs. Processing compressed table: /NTLM8_Master/ ntlm_ascii-32-95#8-8_0_422000x67108864_116.rtc... Table loaded in 1.5 secs. Searching table for matching endpoints... Table searched in 6.1 secs. Checking 61776 potential matches... HASH CRACKED => 52cc18d2dc77f80601532e41cb6738a9:)s&pw3"w HASH CRACKED => defc96c4f1290e15ac71e35a78625246:E/6""r}] Completed false alarm checks in 4.0 secs. Processing compressed table: /NTLM8_Master/ ntlm_ascii-32-95#8-8_0_422000x67108864_119.rtc... Table loaded in 1.5 secs. Searching table for matching endpoints... Table searched in 5.7 secs. Checking 60337 potential matches... HASH CRACKED => c260b99e3b87dfd7538acae873f99291:=R\XHZ5P HASH CRACKED => 39b00f4aaebaf614da751a26ae92f209:G|r=sM.r HASH CRACKED => 03d5353a16d89732e540b38126c35bd9:2}MOJGy5 HASH CRACKED => d4e323ec73f7475571e2b82600e86b73:c0w[U'a: Completed false alarm checks in 4.0 secs. [...] RAINBOW CRACKALACK LOOKUP REPORT * Crack Summary * Of the 101 hashes loaded, 92 were cracked, or 91.09%. Results ------- a7c002406a080278885e47da3909187f ?0.'{!'I bb53c0cb3a8cf0f71f0d6b170ff6b622 ]U$AG:YJ 8e7c7397e513cee2cb50c2fc174ca7b3 4D2(KIX! c260b99e3b87dfd7538acae873f99291 =R\XHZ5P [...] ------- Results have been written in JTR format to: rainbowcrackalack_jtr.pot Results have been written in hashcat format to: rainbowcrackalack_hashcat.pot * Time Summary * Precomputation: 28 mins, 11 secs I/O: 25 mins, 50 secs Searching: 23 mins, 28 secs False alarm checks: 39 mins, 57 secs Total: 1 hours, 57 mins * Statistics * Number of tables processed: 745 Number of false alarms: 14,895,354 Number of chains processed: 49,966,924,469 Time spent per table: 9.5 secs False alarms checked per second: 6,212.5 False alarms per no. chains: 0.02981% Successful cracks per false alarms: 0.00062% Successful cracks per total chains: 0.00000018%

For additional examples, please see here.

News

June 11, 2019

Today marks the launch of the project! The source code for table generation and lookup is now available, along with tables targeting NTLM 8-character passwords. Our Kickstarter project aims to raise funds for more equipment so we can generate NTLM 9-character tables!

Bounty Program

Get paid to work on open-source code! Below are tasks that we could use help with, along with the bounty attached to each (be sure to read carefully!).

Please contact us prior to submission to handle payment logistics.

1.) Improve FPGA Performance: $1,000.00

A proof-of-concept for running NTLM 8-character table generation on Amazon's EC2 F1 instances can be found here. Unfortunately, in its current state, its performance is utterly abysmal. Apply any optimizations necessary to the code and/or build system to improve the chains-per-second generation rate to over 125,000.

2.) Improve GPU Performance By 10%: $250.00 Claimed!

Improve the performance of NTLM 8-character generation on GPU hardware by 10% through optimization of the OpenCL kernel code, C host program, and/or build system. In order to claim the prize, performance must increase on at least one of the following machine setups:

Additionally, performance must not degrade on any of the above systems, including Ubuntu 18.04 + AMD Vega 64 (with latest open-source ROCm driver).

3.) Improve GPU Performance By 20%: $500.00 Claimed!

Requirements and goals are the same as above, but with at least 20% increase in performance. Note: even if the 10% bounty is unclaimed, achieving the 20%+ improvement gets you only $500, not $500 + $250.

Volunteer

Are you interested in helping us generate NTLM 9-character tables? Do you have modern GPU equipment?

Generate 5 tables for us, and we'll list your name here as a supporter. Generate 200 tables, and we'll mail you a free magnetic hard drive containing all NTLM 9-character tables (targeting 50% efficiency) as soon as they become available. Ships world-wide!

Please contact us to coordinate efforts!

Sponsors

Interested in sponsoring the project and getting your company logo listed here? Our Kickstarter project page has the options and pricing information.

Download

The source code for table generation and lookup is available on Github. Pre-compiled executables for Windows are available as well.

NTLM 8-character tables can be downloaded for free via BitTorrent (486 GB).

Alternatively, for convenience, they can be purchased on an SSD hard drive with a USB 3.0 enclosure for just $99. Free standard shipping within the US. Expedited shipping options are available, as well as international shipping.

Contact

You may contact us using this form or by reaching out to @therealjoetesta on Twitter.