TUCoPS :: General Information :: longpass.txt

How useful ARE longer passwords?

                           Longer Passwords
                           ================


    On Password Security
    --------------------

    Dr. (Bob) Wallis, recently commented on having faster implementations
    of DES available and suggested using a site dependant number of iterations
    of the DES algorithm as a secoundary keying variable to aid in stopping
    dictionary or brute force attacks.  Having implemented a faster DES
    algorithm, and being extremely interested in the security aspect of
    passwords, I have a different suggestion.

    As I see it, their have been no published cases of cryptographic attack
    on passwords.  There have been known cases of successful dictionary
    attacks.  A dictionary attack is a successful match with the resulting
    syndrome from iterating the DES algorithm based on a known plaintext
    value ( all ZEROs ), and a suspected key ( from a dictionary of common
    passwords).  There is a secoundary keying variable involved, a salt
    value providing modification to the E permutation, exchanging the
    first twelve and third twelve entries in a lookup table for finding
    the source location in the R register used as input to f(R,K).

    Secondary Keying Features
    -------------------------

    The salt value is intended to defeat the use of faster chip implementations
    of the DES algorithm.  Having designed Gate Arrays, and drawn a set
    of schematics for the DES algorithm, the salt adds twelve dual, 2:1 Muxes
    and a 12 bit register to the basic algorithm.  Even in an MSI
    implementation, and including the hardware for translating a block
    from the syndrome (passwd entry) and comparator for a match, the
    16 pin equivalent count is less than 120.  For hardware, salt is not
    relevant.

    Using tri-ranked registers for the R and L blocks, a 30 MHz clock,
    a dictionary held in a cache RAM, you could make 1.875 Million attempts
    per second on a single value.  By comparing against the syndrome, instead
    of ZEROs, and adding the capability to change the target syndrome (from
    a RAM cache) the rate can be sustained for as many entries as you
    have syndrome cache.  The problem is not the complexity of the DES
    algorithm, but instead the simplicity of the keys involved.

    Simple Passwords
    ----------------

    In The UNIX System: UNIX Operating System Security, AT&T Bell Laboratories
       -----------------------------------------------
    Technical Journal, Vol. 63, No. 8, Part 2 (Oct. 1984) pp. 1649-1672,
    F.T. Grampp and Robert H. Morris.  The authors describe trying 20 of
    the most common female names, followed by a single digit, for a total
    of 200 passwords.  At least one of these 200 was valid on each target
    machine.

    In Password Security: A Case History by Robert Morris and Ken Thompson,
       ---------------------------------
    the authors describes collecting 3,289 passwords over a period of time.

    Of those 15 were single characters, 72 were two char strings, 464 were
    three char strings, 477 were four char strings, 706 were 5 char strings
    and 605 were six char strings.  Additionaly, 492 passwords appeared
    in various available dictionaries.  2,831 or 86 percent could be solved
    with a combination of dictionary and rule attacks.  There have been two
    results of this:

       1) more complex rules for acceptable passwords have been adopted.

       2) an attempt has been made to either hide the algorithm (such as
          use of RSA) or hide the passwords (shadow password files).

    When combined with limiting attempts, hiding the algorithm or hiding
    the syndrome seriously slows down the time to enter a system.

    I have a graphics version of lock.c for my system, that can caste the
    required password to be that of any user.  This allows real lock up of
    the console (using root or system password).  It seems a shame to hide
    such stuff.

    These depend on scarcity of information, site security, and absolute
    control over machine access, which with the myrid of bugs, which seem
    to drift in and out of releases and various producers of UNIX compatible
    software and systems, secondary keying variables (including the number
    of iterations of DES), restrictions in password compostion, and otherwise
    proprietary algorithms do not seem to be an absolute guarantee against
    dictionary attack.  The single biggest threat appears to be the size of
    the password.  There should be some upper limit as to the size of a
    dictionary for a password attack.  Pushing this limit should be a serious
    deterrent.

    Longer Passwords
    ----------------

    Using longer passwords should require a lower bound on the size
    (which could be measured without included common pronouns and adjectives.)



    There are several requirements for longer passwords:

       1) longer passwords must produce distinct syndromes  (their syndromes
          should not match those for partial products).

       2) The syndromes should not map into syndromes from existing
          dictionary attack.

       3) retention of present password system  (Increasing the size  and
          complexity of the dictionary and rule attack systems).

    Instead of a set of rules for a password of at most 8 characters, we
    now have two set of rules, including a set for passwords of more than
    8.  If rules are included for longer passwords to prevent the use of
    simple phrases, as is done for shorter passwords,  A dictionary attack
    can become more than linearly larger.

    To prevent detection of the size of the password, entries in the password
    file should be of identical length.

    Implementation
    --------------

    A sample crypt routine with modifications for longer passwords is
    appended.  This is for use with my implementation of DES, but shows
    how longer passwords can be handled.  Also appended is lmakekey.c
    which generates password file passwd_entries for longer passwords.
    The input has not been blanked.  It also allows multiple passwords
    with the same salt to executed and output to a file.  A sample of
    its execution for strings length 8 34 using -
    "mississippi riverboat gambling man" as an input.  The salt used
    is the null salt "..".

    I may well publish my DES implementation in the future.  It is 3.4
    times faster than the DES found in libcrypt.  I can get approximately
    10 Kbytes/sec on my IRIS 4D-25/G when implemented in a program
    doing read() and write()'s in 8 byte chunks.  The progam also supports
    a test vector file for implementation verification.

    The implementation is present system compatible for passwords 8 or
    fewer characters long.  The salt value is always used.

    For passwords greater than 8 characters, The last 8 characters are used
    as key.  The initial block is cleared to zeros, and the first byte
    of key is EXORed with the first byte of the 8 byte block string.
    A DES iteration is performed.  For all remaining password bytes not
    involved in the key, each is then EXORed with location[0] of the byte
    string, followed by an iteration of DES.  If less than 25 iterations of
    DES have taken place, DES is iterated until 25 iterations have taken
    place.  Note, that in the character array implementation of DES used,
    the password bytes used as data are not left shifted to leave bit 0
    blank, as is done by the routine loadkey().  To produce the results
    shown appended, the following mapping equivalency is helpful.

    The mapping equivalency is:

      L/R[  ]      data.string[0]      ([3] for little_endian)

       L[31]           Bit 0
       R[31]           Bit 1
       L[23]           Bit 2
       R[23]           Bit 3
       L[15]           Bit 4
       R[15]           Bit 5
       L[ 7]           Bit 6
       R[ 7]           Bit 7


    My system performs big_endian byte in long ordering: byte order is 0123.
    This is motorola compatible.  Little endian systems should use
    data.string[3] instead.   My implementation of DES can be compiled for
    any _endian system.

    Note that Bit 7 (R[7]) can be expected to be a ZERO for ascii, resulting
    in at most 7 bits of divergence from the value of the current block
    for each byte of the password.

    System Impact
    --------------

    A new getpass() routine is needed.  This appears to be a good place
    to do some rule checking based on length.

    A new passwd and login program are needed for longer passwords.

    A maximum size password need be specified for writing portable code.

    A new crypt(pw,salt) routine for longer passwords is needed.

    libPW may be immune from impact.


APPENDS
-------

=============
crypt routine  - based on a long aligned char string block
=============
char * lcrypt(pw,salt)
char   *pw, *salt;
{
    int i,c,e, bit, ci, pw_len;
    static char outbuf[16];
    union LR_block  data;            /* long aligned char array[9] */

    for (pw_len = 0; pw[pw_len];pw_len++)    /* pw_len = strlen(pw) */
           ;
    for (i = 0; i< 8;i++)          /* strncpy(data.string,pw,8);   */
       if ( pw_len > 8)
           data.string[i] = pw[i + pw_len-8] ;     /* last 8 chars */
       else
           data.string[i] = pw[i];

    loadkey(data.string,1);        /* first 8 chars nulled         */
    data.string[8] = 0;                    /* needed for outbuf conversion */

    toggle_E(salt);                /* for new implementation des   */

    if ( pw_len < 9)
       for(i= 0; i < 25; i++)
           des(&data,0);           /* faster encrypt()             */

    else {
       for(i=0; i < pw_len - 8; i++) {
           data.string[1] ^= pw[i];
           des(&data,0);
       }
       if ( (i = (25 - (pw_len-8)) > 0))  /* at least 25 iterations */
           while ( i-- )
               des(&data,0);
    }

       toggle_E(salt);         /* undo for sucessive crypt() calls  */

    for (i = 2,ci = 0, bit = 7; i < 13;i++) {
       c = 0;
       for ( e = 5; e >= 0 ; e--){
           if (bit < 0 ) {
               ci++;
               bit = 7;
           }
           if (BIT(bit--) & data.string[ci])
               c |= BIT(e);
       }
       c += '.';
       if (c > '9')
           c += 7;
       if (c > 'Z')
           c +=6;
       outbuf[i] = c;
    }
    outbuf[i] = 0;
    outbuf[0] = salt[0];outbuf[1] = salt[1];
    if (outbuf[1] == 0)
       outbuf[1] = outbuf[0];
    return(outbuf);
}
==========
lmakekey.c
==========
#include <stdio.h>
#include <string.h>

extern char *lcrypt();

#define STRLEN 128

main(argc, argv)
int    argc;
char   *argv[];
{
int i;
char key[BUFSIZ], salt[BUFSIZ], *password;
FILE *outfile;
int firstpass = 1;
    if ( argc == 2) {
       if ( (outfile = fopen(argv[1],"a")) == NULL) {
           fprintf(stderr,"ERROR: %s, can't open %s for append\n",
               argv[0],argv[1]);
       }
    }

    while ( argc == 2 || firstpass){


    fprintf(stdout,"Password? ");
    fgets(key,STRLEN,stdin);

    if( strlen(key) > STRLEN)
       key[STRLEN] = 0;

    for (i = 0; i < STRLEN; i++)
       if (key[i] == '\n')
           key[i] = 0;

   if (firstpass) {
       fprintf(stdout,"Salt? ");
       fgets(salt,STRLEN,stdin);
   }

    if ( strlen(salt) > 2)
       salt[2] = 0;

    password = lcrypt( key, salt);
    fprintf(stdout,"%s\n",password);

    if (argc == 2)
       fprintf(outfile,"length = %3d, passwd= %s, in: %s\n",
                   strlen(key),password, key);
    firstpass = 0;
    fflush(outfile);
    }
    return(0);
}
=======================
sample longer passwords
=======================
length =   8, passwd= ..7kVXGzGEb7Y, in: mississi /* crypt() compatible */
length =   9, passwd= ..C8v9PtCB.0Y, in: mississip
length =  10, passwd= ..qjDDYqQvBlA, in: mississipp
length =  11, passwd= ..cSxjNmzNjEI, in: mississippi
length =  12, passwd= ..bPSqz0AtIu6, in: mississippi
length =  13, passwd= ..hAmDw39a32k, in: mississippi r
length =  14, passwd= ..3enRY0SxJCs, in: mississippi ri
length =  15, passwd= ..tid0WYNoPrs, in: mississippi riv
length =  16, passwd= ..RCEkliTOVH6, in: mississippi rive
length =  17, passwd= ..C/GbzVyN5Hc, in: mississippi river
length =  18, passwd= ..3/rSfkQ5nDs, in: mississippi riverb
length =  19, passwd= ..FWryDwutGyQ, in: mississippi riverbo
length =  20, passwd= ..J8KOcjnnn6Y, in: mississippi riverboa
length =  21, passwd= ..tMv7dg6ksbE, in: mississippi riverboat
length =  22, passwd= ..cpUzQd3uyuQ, in: mississippi riverboat
length =  23, passwd= ..kO8JORivC8g, in: mississippi riverboat g
length =  24, passwd= ..ypuS9WWIJc2, in: mississippi riverboat ga
length =  25, passwd= ..XGZDJsPLNic, in: mississippi riverboat gam
length =  26, passwd= ..niG1hl1tjW2, in: mississippi riverboat gamb
length =  27, passwd= ..AB8aRp181jA, in: mississippi riverboat gambl
length =  28, passwd= ..zr068aSaFE2, in: mississippi riverboat gambli
length =  29, passwd= ..6UY6NO.J6R., in: mississippi riverboat gamblin
length =  30, passwd= ..w0m5AQ2XxFw, in: mississippi riverboat gambling
length =  31, passwd= ..sYSNGs6qUww, in: mississippi riverboat gambling
length =  32, passwd= ..xZ0//Llq3Ck, in: mississippi riverboat gambling m
length =  33, passwd= ..MFsadQbW1LA, in: mississippi riverboat gambling ma
length =  34, passwd= ..riGwJEykDBQ, in: mississippi riverboat gambling man
---------------------------------------------------------------------------



TUCoPS is optimized to look best in Firefox® on a widescreen monitor (1440x900 or better).
Site design & layout copyright © 1986-2024 AOH