Thursday, January 20, 2011

Creating Dictionaries & Cracking Passwords on Mac OS X

If you've forgotten your password on a Mac OS X machine, for either a disk image (sparse bundle, sparse image, etc.) or keychain, you know a feeling of hopelessness. If you're going to attempt to break into your own encrypted store, you have two difficulties:
  1. Generating a minimal password dictionary
  2. Adapting a dictionary password test driver to OS X password-checking 
Test Drivers: Simple Examples Rarely Suffice 
When, frantically, I realized that I was unable to manually guess my image password back in 2008, I wasn't satisfied with what image-cracking utilities Google search returned. The simplified-for-demonstration-purposes test drivers provided in forums didn't handle the kinds of characters my passwords contained (redirects '<', '>' and pipes '|').

I created two Bash scripts to drive unlock attempts from a created password dictionary:
  • unlock_image (using hdiutil attach)
  • unlock_keychain (using security unlock-keychain)
Each conforms to shell scripting norms, returning 0 on success (and printing the successful password), returning 1 on failure, and returning 2 on error.  

Optimizing Minimal Dictionary Creation
Worse, because my passwords typically use a large variety of character sets, I feared coming up with a minimal dictionary would prove too difficult. Back-of-the-napkin estimations on 1) cost per password attempt (time) and 2) dictionary size indicated success would demand some tricks.

Generating an inclusive dictionary proved impossible quickly. The image I was trying to crack had a twelve (12) to fourteen (14) character password, containing (what I believe to be) some combination of fourteen (14) unique characters. This produced, without compression or clever storage solutions, a multi-hundred gigabyte dictionary that would require 48 years to exhaustively attempt using my four-machine set-up.

Robust rule-based password dictionary creation utilities exist but I found these projects a false-optimization to cracking one's own password. You know some aspects of your passwords character set and structure but I found that including too many rules into dictionary creation (creating few-minute or few-hour) attempts always came up empty--my dictionaries were too restrictive.

As a result, I created a simple dictionary creation utility that allowed its user to specify a few password qualities:
  • User-specified password dictionary character set
  • Minimum password length
  • Maximum password length
  • Are password characters unique (or may they be repeated?)
  • Fixed password preface
  • Fixed password suffix

With this utility I created dictionaries inclusive-enough to find the passwords I'd forgotten while (I believe) striking a decent balance between complexity of dictionary specification and resulting password dictionary size.

Download
To download, build, and use the utilities, please go to its Google Code Repository:

Google Code - dmg_password_crack

Prerequisites
  • Mac OS X
  • Maven2
Notes
  • Implementation requires only modest memory, requiring 384K of RAM at steady-state under default settings
  • Implementation appears I/O bound, not bound by syscalls (malloc/free), memory, or computation
  • Password dictionary creation code does not guard explicitly against bad or malicious input. Even careless values (such as negatives) create unexpected results.
  • Recursion and memory allocation, as implemented, lessen LoC but will not perform as well as a well set-up fixed array and iteration
  • hdiutil attach remains the 'long pole' (critical path, most onerous step, etc.) in utilities
  • Code compiles error-/warning-free on Apple's gcc 4.2.1, i686 and performs well on Valgrind leak check, but fails to conform to OOA/D and style conventions
  • Code passes four included integration-level tests on OS=OS X 10.6.6 arch=x86_64