Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 27 Dec 2011 22:43:23 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Bit slice implementation of DES based hashes

On Tue, Dec 27, 2011 at 10:08:58PM +0530, Piyush Mittal wrote:
> Earlier I thought function DES_bs_get_binary() is simply converting cipher
> text into binary form but some more tasks are also associated with it.

It tries to do as much preprocessing as it can, to reduce the amount of
work done on computed hashes while cracking.

> Can you please elaborate me what actually this function is trying to do?

It converts a hash represented in ASCII to binary, and it also undoes
DES final permutation such that we don't need to do it for computed hashes.

> However I tried to understand it but specifically I am not getting some
> portion of DES_raw_get_binary() linked with it. i.e
> 
> if (ciphertext[13]) ofs = 9; else ofs = 2;
> 
>     block[0] = block[1] = 0;
>     dst = 0;
>     for (chr = 0; chr < 11; chr++) {
>         value = DES_atoi64[ARCH_INDEX(ciphertext[chr + ofs])];
>         mask = 0x20;
> 
>         for (src = 0; src < 6; src++) {
>             if (value & mask)
>                 block[dst >> 5] |= 1 << (dst & 0x1F);
>             mask >>= 1;
>             dst++;
>         }
>     }

This is simply decoding of specific kinds of ASCII strings - namely,
those produced by two kinds of DES-based crypt(3).  For other types of
DES-based hashes, you'll need to implement different kinds of decoding.

> Why here ciphertexr[13] is taken

ciphertext[13] is NUL for the traditional DES-based crypt(3) (because
the string is exactly 13 characters long), but is not NUL for BSDI-style
extended crypt(3) hashes (these are 20-character strings).

> and ignored first 8 bit of cipher text.

The code skips over either 2 or 9 characters (not bits) of the
ciphertext.  Those skipped characters contain the salt and hash type
identifier (a single underscore character for the extended hashes).

> Is that because of optimisation (i.e we don't need to compare whole of cipher
> text).

No.

> Also I have seen Matthew Kwan's code and in that he have not used initial
> permutation for Bit slicing DES

IIRC, Matthew Kwan's sample code was originally written for one of RSA's
DES cracking challenges.  Obviously, DES final permutation would not be
done for each computed ciphertext.  I don't recall if you see it in
Matthew's sample code or not, but obviously the final permutation would
be undone on the known ciphertext, similarly to what JtR does.

> then what is the concept behind using IP here in binary function code?

I've addressed this in the first two paragraphs of this reply.  Here
they are again:

"It tries to do as much preprocessing as it can, to reduce the amount of
work done on computed hashes while cracking."

"It converts a hash represented in ASCII to binary, and it also undoes
DES final permutation such that we don't need to do it for computed hashes."

Please note that DES initial permutation is the exact inverse of the
final permutation.  So the DES_do_IP() call actually undoes the final
permutation that we assume had been done on the DES ciphertext before it
was encoded in ASCII.

Alexander

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ