[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 31 Jan 2013 20:33:04 -0500
From: <jfoug@....net>
To: john-dev@...ts.openwall.com
Subject: RE: Speeding up WPAPSK, by leveraging salt shortcomings
Ok, I have been able to do this, VERY easily. I am doing this as a POC, before digging into bleeding (since it is a change to every format file out there).
So, here was what I have done.
1. made a new function: static void ldr_sort_salts(db_main *db); This is called in the visible function ldr_fix_database(), right after it calls ldr_remove_marked (i.e. when we know we have only the salts left to detect).
2. in ldr_sort_salts, if there is less than 2 salts, or the format does not have a salt_compare method (***) then it simply returns, since no sort was needed, or possible. (*** in this POC, the check for salt_compare is to strncmp the format name with "wpapsk")
3. the db->salt_count lists number of salts, and db->salts is the linked list of salts. The only thing that happens within ldr_sort_salts() is the linked list will be re-built with a different order. These are all simply pointers that need to be re-assigned.
4. since this is a single linked list, it is hard to sort efficiently. So, I made a simple structure (could just be a pointer, but a structure was useful during debugging).
5. We allocate an array of these structures. Each structure holds a pointer to a db_salt structure. This is the structure type that makes up the salts linked list.
6. so now, we have an array of pointers, that is in same order as our linked list. We pass this array to qsort.
7. a function: int ldr_salt_cmp(const void*, const void*) was created in loader. This is the function passed into qsort.
8. this ldr_salt_cmp function, converts the 2 pointers passed in, into the new structure type we have been using (what our array is). ldr_salt_cmp, then digs into these, down to the salt It calls the db->format->methods.salt_compare(). passing in the 2 salts. salt_compare in the format should return <0, 0 or >0 depending upon order wanted (just like qsort wants). ldr_salt_cmp is being called BY qsort, so it simply returns the value returned by salt_compare. Thus, qsort does it's magic.
9. at this POC time, the salt_compare is simply a tiny static function in loader. But this would be the same function as to be placed into wpapsk_fmt.c (or cuda or opencl).
10 this function simply does this: int salt_compare(const void *x, const void *y) { return strcmp((const char*)x, (const char*)y); } i.e. pretty trivial for this example, but it is all that is needed, since the essid item is the first thing in our wpapsk structure.
11 once the array is sorted, we now re-created the db->salts linked list. All of the data items in this list are the same, but they are now in different order.
12 free up our array and return, with the linked list in the order that the format wanted it in.
Like I said, right now, I have this running, without making any format changes. Later, we would want to add a new method to all formats. All formats (except wpapsk formats), would have this method pointing to the default method, thus no sorting would be done.
But all in all, this was a pretty easy change. I just had to step code for a while, looking for where to put it, and then dump some structures, looking for how it was all put together. I'm not quite sure where to go with this code right now. It needs a little cleaning, but might not be bad for J8. It would only execute right now, for wpapsk formats, that have more than 1 salt, so 'should' be safe. But I will wait for instructions from others.
Jim.
---- jfoug <jfoug@....net> wrote:
> From: magnum [mailto:john.magnum@...hmail.com]
> >
> >Here's a beautyfully simple thought: If we could force John to serve the
> salts (the current code's salt structs) in essid order, so any same-essid
> salts would always be *consecutive*, we'd do fine with this one-line change
> to crypt_all:
>
> Been thinking a little on this one. This is the first time (that I am aware
> of), where order of salts makes a difference. so up to this point, I think
> there has been no thought put into it. How about this:
>
> 1. make an array of pointers into the salt data (it may, or likely is done
> this way already).
>
> 2. the salt loading currently does load_salts, strike_out_pot,
> build_final_salt. It is not exactly like this, but I think this explanation
> is close enough so that solar (or magnum) would know the exact mechanics.
>
> 3. I propose we add an optional step to this loading. It will be 'similar'
> to a qsort.
>
> This would require changing the format. There will be an 'optional' (almost
> always set to default) method added. This method will be like the function
> used by qsort, and hell, we even COULD use qsort to actually do it. qsort
> is:
>
> qsort(void *_Base, size_t _NumElements, size_t _sizeOfElement, int(__cdecl
> *_ptFuncCompare(const void *, const void*))
>
> So, I propose we add a new function to format methods. This function is:
>
> int salt_sort(const void*, const void*);
>
> Then if this function is not set to default_salt_sort, we call qsort on our
> data, using that function as the compare function. That function would have
> to be either given a pointer to the salt itself, or would have to be smart
> enough to convert the pointers given into the proper structure, so that the
> salt could be located.
>
> However, is 'should' be the format, that is in charge of ordering salts. The
> format designer will need to know that it DOES matter, and know exactly how
> to order things. That way common CRTL functions like qsort would properly
> order this data, even if we had several formats needing this work. JtR
> would not need to know anything to do this, the format would own any logic
> on what is needed.
>
> On a side thought, would this same method be beneficial for sorting input
> words??
>
> Jim.
>
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
