Given a byte array hashed with SHA-256 encryption, brute force check all possible password combinations to discover the un-hashed password.
The supplemental project in my Data Structures (CS 271) course was given to illustrate how poor brute force algorithms are in solving problems. In this case however, it is the only solution. At the time of completing my solution no other Computer Science student at UW-Oshkosh had discovered a way to crack the password.
- The password is 8 characters long
- The password is made up of any of the following character combinations
- Uppercase letters (A-Z)
- Lowercase letters (a-z)
- Numbers (0-9)
Since it is known that there are 8 digits to the password and 62 different combinations for each digit (26 uppercase letters + 26 lowercase letters + 10 digits) there are 8^62 different total password combinations equating to a total of ~98 septendecillion or 98,079,714,615,416,886,934,934,209,737,619,787,751,599,303,819,750,539,264 to be precise.
After doing some rough estimations, I discovered a single threaded brute force process thru 98 septendecillion combinations would take roughly 5.5 years to get to the last possible combination. This would obviously work, but take far too long since I was bound by a semester due date. I needed a way to speed things up.
Instead of having one thread check all possibilities, I could solve the problem with many threads each checking a separate portion of the brute force. When I was solving this problem, our Computer Science Linux lab had 32 computers each with a quad-core processor. I decided to split the problem into 124 chunks utilizing 31 computers each running 4 threads - one for each core. Using this method I reduced the runtime of the entire process from 5.5 years to just over 2 weeks, which is doable in a semester's worth of time.
When compiled and run, this program writes 124 different Java programs, each to a separate file. There are 4 programs in a group, each for a different machine. Each group also gets a separate shell script allowing the machines to start the threads easier.
Each day I would SSH into each Linux Lab computer and ensure the process was running with a nice value of 19. After this, it was just a matter of waiting for the un-hashed password to be written to a file.
After about two weeks of waiting and checking my processes daily, my patience paid off and I found the password: DSI5FUN1.