Traditional DES scheme in Unix crypt function

Question

In a security context course, we need to reproduce the old DES hashing scheme in the crypt program, on an old unix system.

I am actually reading the crypt page on wikipedia:

The traditional implementation uses a modified form of the DES algorithm. The user's password is truncated to eight characters, and those are coerced down to only 7-bits each; this forms the 56-bit DES key. That key is then used to encrypt an all-bits-zero block, and then the ciphertext is encrypted again with the same key, and so on for a total of 25 DES encryptions. A 12-bit salt is used to perturb the encryption algorithm, so standard DES implementations can't be used to implement crypt(). The salt and the final ciphertext are encoded into a printable string in a form of base64.

I am not sure to well completely understand the above definition, and I would like to use an example to show you my questions.

So, considering I use the password: foobar12345678.

I will work in hexadecimal, so the password is: 66 6f 6f 62 61 72 31 32 1.The password will be truncated to foobar12.

2.I remove the first bit (not sure?) of every password byte, so my new password will be:

01100110 01101111 01101111 01100010 01100001 01110010 00110001 00110010
==>
11001101 10111111 01111110 00101100 00111100 10011000 10110010 

The password in hexadecimal is cd bf 7e 2c 3c 98 b2 and is the 56 bits DES key.

3.The key above is used to encrypt an all-bits-zero block. I imagine the zero block is 56 bits also?

so, using an hypothetical DES scheme encryption function function_DES(hex_message, hex_key), our hash here would be the output of function_DES(00 00 00 00 00 00 00, cd bf 7e 2c 3c 98 b2). imagine that the output is hashOutput1

4.We crypt 25 hashOutput1 with the key cd bf 7e 2c 3c 98 b2 using DES scheme.

A 12-bit salt is used to perturb the encryption algorithm, so standard DES implementations can't be used to implement crypt()

5.What's the 12-bit salt? I imagine it's predefined in linux system? Where can I find it? Imagine the salt is 101010101010 I place it in front of the 25th encrypted DES output?

6.Both hash and salt are comverted to base64 and placed in the /etc/shadow as:

$clearSalt$DEShash

So, during the 56 bits key creation, when we coerce down bits in 64 bits password, is it the first bit of each byte that we need to remove?

Are all-zeros blocks 56 bits (the exact same size than the 56 bits key) ?

What's the salt? Is it predefined in Unix system? Is it the same in all distro?

So, using this technique bruteforce tools should never go over 8 characters?

References:

http://en.wikipedia.org/wiki/Crypt_%28Unix%29 and http://www.kernel.org/doc/man-pages/online/pages/man3/crypt.3.html

edit:

for my salt question, I think I found my answer:

When you change your password, the /bin/passwd program selects a salt based on the time of day. The salt is converted into a two-character string and is stored in the /etc/passwd file along with the encrypted "password."[10] In this manner, when you type your password at login time, the same salt is used again. UNIX stores the salt as the first two characters of the encrypted password.

(From: http://www.diablotin.com/librairie/networking/puis/ch08_06.htm)

Answer 1

As for the salt, it is a two-character string chosen from the set of printable characters leading to an effective 12-bit entropy.

The fact that every eigth bit of the password is dropped is due to the DES itself: from the 64-bit key, only 56 bits are actually used, thereby dropping 8 of the bits of the key. So, you just input the 64-bit password as the encryption algorithm secret key.

As for the all zeros block, it refers to the plaintext input to the encryption algorithm, which in the DES is a 64-bit value.

Thus you load the password as the key, an all zeros block as the plaintext into the encryption algorithm.

Now the only thing is the encryption algorithm is a tweaked version of the DES: the salt is indeed introduced during the expansion function $E$ of the DES as described in section 4 of this paper. Instead of the standard $E$, a tweaked version $E'$ is implemented.

All of this is well described in this paper.