passwd- changing from 56-bit DES to 64-bit IDEA ?

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Pariah Gre » Sun, 10 Jul 1994 02:16:50



I've been reading Bruce Schneier's _Applied Cryptography_, and
about DES in particular. Doesn't the passwd verification in
UNIX use the 56-bit DES algorithm? It seems that 56-bit DES is
easily breakable via brute force by resources available to NSA
or anyone else with $1 million.

Schneier recommends 64-bit IDEA as being much harder to break.
(IDEA is also used in PGP 2.x) Has anyone hacked a version of
passwd which uses IDEA rather than DES? Sorry if this has been
asked already. I know that a lot of UNIX flavors have secondary
authentication methods, but I'd rather just use one very solid
method.

--

 
 
 

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Ollivier Robe » Mon, 11 Jul 1994 22:54:11




>I've been reading Bruce Schneier's _Applied Cryptography_, and
>about DES in particular. Doesn't the passwd verification in
>UNIX use the 56-bit DES algorithm? It seems that 56-bit DES is

It uses a modified version of the DES. It uses  25 rounds instead of the 16
in  DES. It is also perturbed  by the addition of  the salt (4096 possibles
values) and last  but   not the  least, the  DES  used  in  passwd  is  NOT
reversible.

Password checking is done by encrypting the password given  by the user and
comparing the encrypted versions.

Quote:>Schneier recommends 64-bit IDEA as being much harder to break.
>(IDEA is also used in PGP 2.x) Has anyone hacked a version of
>passwd which uses IDEA rather than DES? Sorry if this has been
>asked already. I know that a lot of UNIX flavors have secondary
>authentication methods, but I'd rather just use one very solid
>method.

For the reason given above (non reversability), it is not useful. If you're
really paranoid, you can replace the DES by MD5 or SHS.

--


PERL / MIME / PGP 2.6ui         FreeBSD keltia 1.1.5(RELEASE) RELEASE#0 i386

 
 
 

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Casper H.S. D » Tue, 12 Jul 1994 17:51:46





>>I've been reading Bruce Schneier's _Applied Cryptography_, and
>>about DES in particular. Doesn't the passwd verification in
>>UNIX use the 56-bit DES algorithm? It seems that 56-bit DES is
>It uses a modified version of the DES. It uses  25 rounds instead of the 16
>in  DES. It is also perturbed  by the addition of  the salt (4096 possibles
>values) and last  but   not the  least, the  DES  used  in  passwd  is  NOT
>reversible.

Correction, the Unix password algorithm uses

        - 25 runs of DES (for a total of 25*16 = 400 DES rounds)
        - uses the password as key (which makes it retrieving the
          password through reversing the algorithm impossible)
        - DES modified with the salt (as you said)

Casper

 
 
 

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Morten Welind » Tue, 12 Jul 1994 18:18:41






>>>I've been reading Bruce Schneier's _Applied Cryptography_, and
>>>about DES in particular. Doesn't the passwd verification in
>>>UNIX use the 56-bit DES algorithm? It seems that 56-bit DES is
>>It uses a modified version of the DES. It uses  25 rounds instead of the 16
>>in  DES. It is also perturbed  by the addition of  the salt (4096 possibles
>>values) and last  but   not the  least, the  DES  used  in  passwd  is  NOT
>>reversible.
>Correction, the Unix password algorithm uses
>    - 25 runs of DES (for a total of 25*16 = 400 DES rounds)
>    - uses the password as key (which makes it retrieving the
>      password through reversing the algorithm impossible)
>    - DES modified with the salt (as you said)
>Casper

        - A 64-bit string of 0's to be decoded.  (So guessing a
          password could be argued not to reveal anything secret.)

Morten

PS: When the salt was introduced, why was it made to have only 4096
combinations?  This means that it is not more difficult for a cracker
to attack 50000 passwords (from N sites) than it is to attack 4000
passwords.   (Well, a few percent harder due to uneven distribution.)
--
------------------------------------------------------------------------
For information on the free Republic of Macedonia, ftp to ftp.uts.edu.au
Australia and check out the /pub/MAKEDON directory.

 
 
 

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Alec Muffe » Tue, 12 Jul 1994 19:54:56



Quote:>I've been reading Bruce Schneier's _Applied Cryptography_, and
>about DES in particular. Doesn't the passwd verification in
>UNIX use the 56-bit DES algorithm?

No. The Unix algorithm goes thusly:

* take the 8 character "Unix login password"
* reduce it to 56 bits, call this the "key"
* take the first two characters from the relevant pw_passwd field
  from /etc/passwd
* reduce these two characters to a 12 bit number, the "salt"
* use the salt to tweak the "E" expansion of your DES engine
  ie: so we are not using standard DES
* take a block of NULLs, call this the plaintext
* run your modified DES on the plaintext, 25 times, using your
  "key" from the above.
* take the result.
* prepend the salt and munge into ASCII
* match pw_passwd field against the string thus produced.

so:

1) yes, the crypt(3) algorithm is based on DES, but is not DES.

2) even if you could reverese the encryption described above
   you'ld only wind up with a block of NULLs (the plaintext)

Bruce, if you're reading this, I don't suppose it could be clarified in
the next edition ?

Quote:>It seems that 56-bit DES is
>easily breakable via brute force by resources available to NSA
>or anyone else with $1 million.

3) if I can get at your /etc/passwd (/etc/shadow ?) files, I can
very-probably brute-force my way into your machine using resources
available in my back-bedroom, or anyone else with $500.

An Amiga A500 does nicely to run Crack. A Linuxed '486 moreso.

<realisation strikes>

God! The NSA ought to hire me! I could save them billions!  8-)

Quote:>I know that a lot of UNIX flavors have secondary
>authentication methods, but I'd rather just use one very solid
>method.

Buy a smartcard or install S/Key. Get out of the password game. Now.
Passwords are dead technology. The NSA probably doesn't give a toss
what is on your machine, but if you're at all interested in keeping
*them* out, then give up on passwords entirely.

                                - alec

---
The views expressed above are the author's *personal* opinions
and are not necessarily shared by his employers or anyone else

... I love the smell of acid flux in the morning...

 
 
 

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Jonathan M. Bresl » Wed, 13 Jul 1994 01:38:24




>It uses a modified version of the DES. It uses  25 rounds instead of the 16
>in  DES. It is also perturbed  by the addition of  the salt (4096 possibles
>values) and last  but   not the  least, the  DES  used  in  passwd  is  NOT
>reversible.

        excuse me if i'm picking nits here, but....

        how is the des used by passwd more irreversible than standard 16 round
des.  just as 16 round has a decryption key, doesnt 25 round also have a key?
i thought that the additional rounds were to make software passwd cracking a
more expensive (timewise) operation, a consideration that has lost a lot
over the years.

        the salt is the real kicker.  due to salt storing a dictionary of
precomputed passwds requires 4K times the space.

jmb

--

                                                | 2341 Jeff Davis Hwy
play go.                                        | Arlington, VA 22202
ride bike. hack FreeBSD.--ah the good life      | 703-418-2800 x346

 
 
 

passwd- changing from 56-bit DES to 64-bit IDEA ?

Post by Roberto Shironoshi » Thu, 14 Jul 1994 01:58:03





> >It uses a modified version of the DES. It uses  25 rounds instead of the 16
> >in  DES. It is also perturbed  by the addition of  the salt (4096 possibles
> >values) and last  but   not the  least, the  DES  used  in  passwd  is  NOT
> >reversible.

>    how is the des used by passwd more irreversible than standard 16 round
> des.  just as 16 round has a decryption key, doesnt 25 round also have a key?
> i thought that the additional rounds were to make software passwd cracking a
> more expensive (timewise) operation, a consideration that has lost a lot
> over the years.

>    the salt is the real kicker.  due to salt storing a dictionary of
> precomputed passwds requires 4K times the space.

I don't know if the modified DES used in the UNIX passwd program is
reversible or not, but I think that is immaterial.  The password is the
encryption key, not the encrypted data.  The encrypted data is a block of
zeroes.

Now, if you can go from the encrypted text and the known encrypted data to
the encryption key (other than by exhaustive search), then we have a
problem.
--

------------------------------------------------------------------------------
DISCLAIMER: The opinions expressed here are my own; they in no way reflect the
            opinion or policies of Harris Corporation.

        In-Real-Life:   Roberto Shironoshita
                        Harris Computer Systems Division

        UUCP:           ...!uunet!mail.csd.harris.com!Roberto.Shironoshita