passwds and crypt(3)... (LONG)

[Joe Gaudreau]

>Jonathan Kamens:
>  No, that's the whole point of the seed.  The seed is *different* for
...
>encrypted in each possible seed before they can be compared to encrypted
>passwords.

True true.  The set of characters for the salt & encrypted string is
[a-zA-Z0-9./], which is 64 characters total.  A two character salt results
in 64^2 == 4096 different salts.

Let's check how safe we really are.  What if you know how long a
password is?  How do you find out?  Well, maybe you *heard* them type
it in?  No, then worst case is to try all lengths (but check common
lengths first, etc).  Do you know what the salt is?  No, then worst
case test.  So:

Disclaimer: I'm not a real mathematician, so I could maybe ;-) have
           made a mistake.  I hope not.

1) 256 element set - worst case search:

  Len  Combinations (known salt)             Combinations * 4096
  ---  -----------------------------------   ------------------------------
  1    256^1  =                        256                        1,048,576
  2    256^2  =                     65,536                      268,435,456
  3    256^3  =                 16,777,216                   68,719,476,736
  4    256^4  =              4,294,967,296               17,592,186,044,416
  5    256^5  =          1,099,511,627,776            4,503,599,627,370,496
  6    256^6  =        281,474,976,710,656        1,152,921,504,606,846,976
  7    256^7  =     72,057,594,037,927,936      295,147,905,179,352,825,856
  8    256^8  = 18,446,744,073,709,551,616   75,557,863,725,914,323,419,136
                --------------------------  -------------------------------
       Total  = 18,519,084,246,547,628,288   75,854,169,073,859,085,467,648

2) 96 element set - based on ascii 32-127 set, common keyboard set:

  Len  Combinations (known salt)             Combinations * 4096
  ---  -----------------------------------   ------------------------------
  1    96^1   =                         96                          393,216
  2    96^2   =                      9,216                       37,748,736
  3    96^3   =                    884,736                    3,623,878,656
  4    96^4   =                 84,934,656                  347,892,350,976
  5    96^5   =              8,153,726,976               33,397,665,693,696
  6    96^6   =            782,757,789,696            3,206,175,906,594,816
  7    96^7   =         75,144,747,810,816          307,792,887,033,102,336
  8    96^8   =      7,213,895,789,838,336       29,548,117,155,177,824,256
                     ---------------------       --------------------------
       Total  =      7,289,831,534,994,528       29,859,149,967,337,586,688

3) 36 element set based on single case alphabet and digits:

  Len  Combinations (known salt)             Combinations * 4096
  ---  -----------------------------------   ------------------------------
  1    36^1   =                         36                          147,456
  2    36^2   =                      1,296                        5,308,416
  3    36^3   =                     46,656                      191,102,976
  4    36^4   =                  1,679,616                    6,879,707,136
  5    36^5   =                 60,466,176                  247,669,456,896
  6    36^6   =              2,176,782,336                8,916,100,448,256
  7    36^7   =             78,364,164,096              320,979,616,137,216
  8    36^8   =          2,821,109,907,456           11,555,266,180,939,776
                         -----------------           ----------------------
       Total  =          2,901,713,047,668           11,885,416,643,248,128

4) 26 element set set on just single case alphabet.

  Len  Combinations (known salt)             Combinations * 4096
  ---  -----------------------------------   ------------------------------
  1    26^1   =                         26                          106,496
  2    26^2   =                        676                        2,768,896
  3    26^3   =                     17,576                       71,991,296
  4    26^4   =                    456,976                    1,871,773,696
  5    26^5   =                 11,881,376                   48,666,116,096
  6    26^6   =                308,915,776                1,265,319,018,496
  7    26^7   =              8,031,810,176               32,898,294,480,896
  8    26^8   =            208,827,064,576              855,355,656,503,296
                         -----------------           ----------------------
       Total  =            217,180,147,158              889,569,882,759,168

Well, the numbers are still pretty big even for set #4 but are they big
enough?  Do you have enough protection should someone know that the root
password is 5 characters long and only made up of letters (a common practice
as a site I visited).  Fast crypt(3) routines are available.  So THEY changed
the constant string - it can be found out.  Looks like shadow passwds
are VERY convincing...

YADisclaimer: I may have made some really bad mistakes here, I hope not.
             If you should happen to find some, let me know.  Helpful
             criticism is quite useful.  Flames without substance help
             nobody and don't bother someone who lives in hell =:->...

---
Joe Gaudreau              "Juggling, not just a way of life"
ZePhone: (617)890-2888
ARPA:    joeg at polygen.com
UUCP:    {princeton,mit-eddie,bu.edu,sunne}!polygen!joeg
UsSnail: Polygen Corporation, 200 5th Ave, Waltham, MA 02254