Help Needed: My C-Fu is Weak

kludge · 2010-01-23 20:57:54

greetings, fellow archers!

embarassing admission time: i kinda forgot the LUKS passphrase for my old laptop's harddrive.

the bad news is, of course, that it would stupid to imagine i can crack it back open.

the good news is that i mostly remember my passphrase. i know the plain english phrase it was based on, and i know the way i mangle plain english to make passphrases.

the even better news is rephrase. it's almost exactly the help i need. almost.

here's where i need someone else's help. i'm terrible with C, and even after poring over the source code, i'm sad to say i can't quite figure out how rephrase is working it's magic.

i'm confident i can whip up some bash or python to duplicate rephrase's educated-guessing and apply it to a LUKS partition, but i need a plain english description of the pattern parser and the guessing algorithm.

also, since i'm mostly just trying to recover my music collection, i'm not particularly worried about security.

anyone wanna help? i'll send you a whole batch of e-cookies. if i had an oven and you had an address, i'd even send you *real* cookies.

thanks in advance!!!

Profjim · 2010-01-23 21:37:08

I feel your pain. Here's the rephrase.c file with some very simple explanatory comments added. The logic is pretty bare-bones.

http://pastebin.ca/1763293

Last edited by Profjim (2010-01-23 21:42:59)

kludge · 2010-01-23 23:34:30

thanks, profjim!

i've been reading over rephrase.c in light of your comments, and i feel like i've got a better grasp on it now. if you've got a minute or two, though, there are still some really foggy bits.

in particular, i don't understand how the 'passes' are differentiated. the algorithm needs to check every possible combination of alternatives for chunks 2 .. n against all alternatives in chunk 1, right?

what i can't seem to suss out is how rephrase keeps track of which combinations it's tried, and which to try next. more specifically, i just can't seem to understand the structure of 'secrets'. what goes in 'alternatives'? what the heck is 'try' for? a? b? i?

this is why i'm a sys admin, not a coder!

any help? like, a diagram?

Profjim · 2010-01-23 23:52:09

s->b keeps track of which "pass" is current. I think it'd be easiest for you to implement this from scratch in Python or whatever you plan to use, rather than figure out the details of how this program does it. Just think that the task is to turn:
"prefix(pat1|pat2|pat3)middle(pat4|pat5)suffix"
into the Python tuple:
("prefixpat1middlepat4suffix","prefixpat1middlepat5suffix","prefixpat2middlepat4suffix",...). And then you can iterate over trying each of them. If that takes too long you might just write up the list of all the passwords you want to try as literals, with no patterns---since hopefully this is a one-time script!

kludge · 2010-01-23 23:55:44

hopefully, yeah, it will be.

then again, a generalized educated-guesser would be a really useful admin tool to have around.

i think you're right that it would be easier, but when i tried, i got myself all twisted into ridiculous bash knots.

like i said... i'm good at using programs, not writing them!

but i'll give this a shot. ain't got any plans for tonight, anyhow.

Profjim · 2010-01-24 00:39:29

Yeah, this is doable in bash, but if you know Python, as you suggest earlier, that'll be a much more comfortable tool for such a job. Good luck!

Profjim · 2010-01-24 00:43:35

Actually, you _could_ just rely on the bash expansion. If you write a script in whatever language that expects all the possible keys supplied as a list of arguments, then you could just call:

yourscript prefix{pat1,pat2,pat3}middle{pat4,pat5}suffix

And that will automatically call yourscript with the six expansions of the pattern (prefixpat1middlepat4suffix, ...). So all you need yourscript to do is iterate over its arguments, trying to cryptsetup luksOpen... or whatever which each one until it succeeds (or runs out of arguments :-( ).

kludge · 2010-01-26 08:17:24

if anybody's interested:

# crackpipe.py -- may you never need to execute these lines.

#!/usr/bin/python

from sys import argv
from subprocess import *

def parse(pattern):

    chunks = []
    alts = []
    mid_chunk = 0

    for curr_char in pattern:

        if curr_char == '(':
            mid_chunk = 1
            alts = []

        elif curr_char == '|':
            if last_char == '(':
                alts.append('')

        elif curr_char == ')':
            if last_char == '|':
                 alts.append('')
            chunks.append(alts)
            mid_chunk = 0

        elif mid_chunk == 1:
            alts.append(curr_char)

        else:
            chunks.append(curr_char)

        last_char = curr_char

    return chunks

def guesser(chunks,guess=''):

# i seriously spent *all day* trying to write this
# from scratch.  the following is practically copy
# pasta.  grumble, grumble.
#
    chunk = chunks[0]

    if len(chunks) == 1:
        for alternate in chunk:
            yield guess + alternate
    else:
        for alternate in chunk:
            for g in guesser(chunks[1:],guess+alternate):
                yield g

# i really want the actual command to run broken down
# *at least* this much so that crackpipe can be
# easily modified for other applications.
# for whatever reason, though, subprocess.Popen
# is not playing very nicely
#
commandPath = "/usr/sbin/"
commandExe = "cryptsetup"
commandArgs = "--tries=1 luksOpen /dev/sdb2 crypt2"

pattern = argv[1]

chunks = parse(pattern)

returncode = 0

for guess in guesser(chunks):

    print guess

# i can't tell the difference between the result of the
# following and first argument to Popen below, but python
# and/or LUKS can, and i'm too tired right now to deal.
#
#    print commandPath+commandExe+'  '+commandArgs
#
    process = Popen(["/usr/sbin/cryptsetup",
                "--tries=1","luksOpen","/dev/sdb2","crypt2"],
                shell=False,
                stdin=PIPE,
                stdout=PIPE,
                stderr=PIPE)

    if process.returncode != 0:
        output = process.communicate(guess)
        if output[0]: print "Stdout:", output[0],
        if output[1]: print "Stderr:", output[1],
        print "Retcode:", process.returncode
    else:
        print "Gotcha, ya bastid!!! -->",guess
        break

i *think* this'll work... provided the passphrase can be generated by the supplied pattern. we'll see when it's done. (i plan to give it a couple of days.)

big thanks to profjim, and *super* big thanks to my buddy geetsromeo for the generator function tip-off.

Profjim · 2010-01-26 09:43:27

kludge wrote:

def parse(pattern):

    chunks = []
    alts = []
    mid_chunk = 0

    for curr_char in pattern:

        if curr_char == '(':
            mid_chunk = 1
            alts = []

        elif curr_char == '|':
            if last_char == '(':
                alts.append('')

        elif curr_char == ')':
            if last_char == '|':
                 alts.append('')
            chunks.append(alts)
            mid_chunk = 0

        elif mid_chunk == 1:
            alts.append(curr_char)

        else:
            chunks.append(curr_char)

        last_char = curr_char

    return chunks

You forgot to initialize last_char, this will crash if the first char is | or ). Which isn't a valid pattern anyway, so maybe we shouldn't care.

So chunks ends up being a list whose members are either single chars, or alts lists. What do the alts lists look like?

parse("...(a|b|c)...") will produce an alts list ['a','b','c'].
parse("...(ab|c)...") will produce what, the same alts list, no? So these two patterns will be treated identically. Was that your intention?

def guesser(chunks,guess=''):

    chunk = chunks[0]

    if len(chunks) == 1:
        for alternate in chunk:
            yield guess + alternate
    else:
        for alternate in chunk:
            for g in guesser(chunks[1:],guess+alternate):
                yield g

chunk could be a single char, or an alts list of single chars. The if-clauses here cleverly exploit the fact that python will treat "for alternate in list_of_single_chars" and "for alternate in single_char" the same. Inside the for block, alternate will in each case be a single char.

I expect to fix the issue noted above, you'll want to make some change in the parse output. If the structure of your parse() output changes, you'll have to reexamine whether the gyesser function still works. It should still be OK if you make the elements of the alts list be longer than single chars. But it'd break if you make the outside-of-an-alts block part of chunks contain strings longer than single chars.

commandPath = "/usr/sbin/"
commandExe = "cryptsetup"
commandArgs = "--tries=1 luksOpen /dev/sdb2 crypt2"

pattern = argv[1]

chunks = parse(pattern)

returncode = 0

for guess in guesser(chunks):

    print guess

    process = Popen(["/usr/sbin/cryptsetup",
                "--tries=1","luksOpen","/dev/sdb2","crypt2"],
                shell=False,
                stdin=PIPE,
                stdout=PIPE,
                stderr=PIPE)

Popen _should_ work ok if you pass it a single string as the first argument, though then one has to rely on arguments to be simply space-separated, no quotes or "\ " trucks. The first argument should just be a string though, not a string in []s. I'm not sure whether that style is ok when shell=False. But if I remember rightly, the docs allege that Popen("a b c",...) is supposed to be the same as Popen(["a","b","c"],...). I think the latter style is more robust, though, anyway. If you want to do this with your commandPath, etc., you could do:

    process = Popen([commandPath+commandExe]+commandArgs.split(),
                    ...

Arch Linux

#1 2010-01-23 20:57:54

Help Needed: My C-Fu is Weak

#2 2010-01-23 21:37:08

Re: Help Needed: My C-Fu is Weak

#3 2010-01-23 23:34:30

Re: Help Needed: My C-Fu is Weak

#4 2010-01-23 23:52:09

Re: Help Needed: My C-Fu is Weak

#5 2010-01-23 23:55:44

Re: Help Needed: My C-Fu is Weak

#6 2010-01-24 00:39:29

Re: Help Needed: My C-Fu is Weak

#7 2010-01-24 00:43:35

Re: Help Needed: My C-Fu is Weak

#8 2010-01-26 08:17:24

Re: Help Needed: My C-Fu is Weak

#9 2010-01-26 09:43:27

Re: Help Needed: My C-Fu is Weak

Board footer