Passphrase Cracking

A fellow member of Skullspace forgot a valuable encryption passphrase.
I cracked it with a custom program I wrote in python. Here’s a sample run:

$ python custom_crack_multibit_key_export.py sample.key 
37 words, 33 punctuation choices, 2 constants
up to 196791012 passphrases will be tried
found #tigeran7ysalmon after 17884626 tries
L3E9iJuT298YBoT3m3asSws4Hy9GTTM193w9U4ogtdXGU4zpDifF 2013-08-03T10:51:55Z

Before coding, I conducted a forensic password interview, and he remembered:

• One of four words, “tiger”, “bear”, “salmon”, and “elephant”
• Word is capitalized or lower case
• The use of a four letter constant, “an7y” right after that
• The use of a punctuation mark such as # possibly as a prefix, suffix, or possibly middle separator from the word and constant being used twice.

So he was thinking something like #bearan7y#tigeran7y.

Starting with these four words I built a larger word list, added each of the original words with the first or last letter missing, and took this larger list and added in a capitalized and fully upper case version of each word. Also added in the blank word ('') to cover the case of no word being used at all.

WORDS_ORIGINAL = WORDS = ('tiger', 'bear', 'salmon', 'elephant')

# with last letter missing
WORDS = WORDS + tuple( word[:-1] for word in WORDS_ORIGINAL)
# with first letter missing
WORDS = WORDS + tuple( word[1:] for word in WORDS_ORIGINAL )

WORDS_LOWER = WORDS
WORDS = WORDS + tuple( word.capitalize() for word in WORDS_LOWER)
WORDS = WORDS + tuple( word.upper() for word in WORDS_LOWER)
/WORDS = WORDS + ('',) # word missing

Which gives us

>>> WORDS
('tiger', 'bear', 'salmon', 'elephant',
 'tige', 'bea', 'salmo', 'elephan',
 'iger', 'ear', 'almon', 'lephant',
 'Tiger', 'Bear', 'Salmon', 'Elephant',
 'Tige', 'Bea', 'Salmo', 'Elephan',
 'Iger', 'Ear', 'Almon', 'Lephant',
 'TIGER', 'BEAR', 'SALMON', 'ELEPHANT',
 'TIGE', 'BEA', 'SALMO', 'ELEPHAN',
 'IGER', 'EAR', 'ALMON', 'LEPHANT', '')

I used the builtin punctuation set in python plus blank ('') to include the possibility of not using any punctuation

from string import punctuation
PUNCS = tuple(punctuation) + ('',)

It looks like

>>> PUNCS
('!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.', '/',
 ':', ';', '<', '=', '>', '?', '@', '[', '\\', ']', '^', '_', '`', '{', '|',
 '}', '~', '')

A similar treatment for the four letter constant

FOUR_LETTER_CONSTANTS = ('an7y', '')

In order to try all combinations of punctuation + word + constant + punctuation + word + constant + punctuation, I took advantage of the builtin (cross)product function to try all possibilities:

from itertools import product
for punc_1, punc_2, punc_3, word_1, word_2, four_let_1, four_let_2 in \
        product(PUNCS, PUNCS, PUNCS, WORDS, WORDS,
                FOUR_LETTER_CONSTANTS, FOUR_LETTER_CONSTANTS):
    passphrase = (
        punc_1 + 
        word_1 + 
        four_let_1 +
        punc_2 + 
        word_2 +
        four_let_2 +
        punc_3
        )
    result, plaintext  = try_decrypt(ciphertext, salt, passphrase)

This is much cleaner then nesting eight loops:

for punc_1 in PUNCS:
    for punc_2 in PUNCS:
        for punc_3 in PUNCS:
            for word_1 in WORDS:
                for word_2 in WORDS:
                    for word_3 in WORDS:
                        for four_let_1 in FOUR_LETTER_CONSTANTS:
                            for four_let_2 in FOUR_LETTER_CONSTANTS:
                                passphrase = (punc_1 + 
                                              word_1 + 
                                              four_let_1 +
                                              punc_2 + 
                                              word_2 +
                                              four_let_2 +
                                              punc_3
                                              )
                                 result, plaintext  = try_decrypt(
                                           ciphertext, salt, passphrase)

Here’s a random sample of the passwords this ends up trying

;IGERTigeran7y*
[Lephantan7y}EARan7y&
_lephantan7y{LEPHANT:
{Salmo$lephant:
}tigean7y)Beaan7y?
}LEPHANTan7y+ear]

You can find my full code in a GitHub Gist that also includes a sample .key file this can crack.