[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140506233418.GA18498@openwall.com>
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][0], 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.
