Date: Wed, 7 May 2014 03:34:18 +0400 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: Oracle Bitslice DES Hi Deepika, On Tue, May 06, 2014 at 10:59:11AM -0700, deepika wrote: > Hi, I am working on oracle DES bitslicing. Since I have to use CBC encryption mode here, what should be the right strategy of doing it? In this statement in oracle_fmt_plug.c, memcpy((char *)cur_salt + salt_length, &cur_key[i], key_length[i]); salt is being appended with key. Here keys can have different lengths. So for n cur_salt's, should I find out the maximum length L and make other n-1 cur_salt's equal to L by appending 0's or if something else need to be done? > > I doubt if doing as above will be right, as I read that DES_ncbc_encrypt() zero pads the last block of input to make the total length of input multiple of 8. Lengths of n cur_salt's should be thus some multiple of 8 rather than equal to some L. For doing bitslicing I need all inputs to be of same length, which ofcourse won't happen here. How to tackle this issue? This is an out-of-context reply since I don't recall the details of Oracle's hashing and don't currently have time to look into it, but in general: The memcpy() line in question is inside crypt_all(), and there's just one salt for all of the candidate passwords that crypt_all() was called to hash. (Other salts, if any, will be provided to other crypt_all() calls.) So it sounds like you don't really have the problem. You need "all inputs to be of same length", and you readily have that for the salt portion of these strings for each given crypt_all() call. However, it does appear that you may need to group candidate passwords by combined salt_length+key_length, or rather it'd be sufficient to group by the resulting DES block count. You'd process these groups separately, from within the same crypt_all() call. To achieve good efficiency (nearly full groups almost all of the time), max_keys_per_crypt needs to be many times higher than bitslice vector width. Please take a look at trip_fmt.c in 1.8+ or bleeding-jumbo, which does similar grouping, albeit by crypt(3) salt, which for tripcodes is based on some characters of the candidate password (whereas tripcodes themselves are saltless). While the basis for tripcodes' grouping of candidate passwords is very different, the concept of grouping is the same. Here's a problem, though: computing Oracle hashes is so fast that the overhead of grouping can be substantial, especially if you do the grouping from within crypt_all(), which you'd need to if you choose to group by DES block count (since salt lengths may vary across crypt_all() calls, and thus the block boundaries may be at different password lengths). Maybe it's better to group by plaintext password length (in other words, with byte granularity), which you can do on the very first crypt_all() call after a set_key() sets a "keys changed" flag. Then further crypt_all() calls don't need to perform any grouping (they'd reuse the grouping made by the very first such call after a "keys changed" event). The price for that is a higher number of buckets (by exact length, not by block count) and thus a higher optimal scaling factor (but still acceptable). Upon a second thought, I think it may be better to put the keys into different buckets right in set_key(). Then you don't need a "keys changed" flag and don't need any check/re-grouping in crypt_all(). Alexander
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.