home *** CD-ROM | disk | FTP | other *** search
/ The Hacker's Encyclopedia 1998 / hackers_encyclopedia.iso / hacking / general / longpass.txt < prev    next >
Encoding:
Text File  |  2003-06-11  |  13.5 KB  |  346 lines
  1.                            Longer Passwords
  2.                            ================
  3.  
  4.  
  5.     On Password Security
  6.     --------------------
  7.  
  8.     Dr. (Bob) Wallis, recently commented on having faster implementations
  9.     of DES available and suggested using a site dependant number of iterations
  10.     of the DES algorithm as a secoundary keying variable to aid in stopping
  11.     dictionary or brute force attacks.  Having implemented a faster DES
  12.     algorithm, and being extremely interested in the security aspect of
  13.     passwords, I have a different suggestion.
  14.  
  15.     As I see it, their have been no published cases of cryptographic attack
  16.     on passwords.  There have been known cases of successful dictionary
  17.     attacks.  A dictionary attack is a successful match with the resulting
  18.     syndrome from iterating the DES algorithm based on a known plaintext
  19.     value ( all ZEROs ), and a suspected key ( from a dictionary of common
  20.     passwords).  There is a secoundary keying variable involved, a salt
  21.     value providing modification to the E permutation, exchanging the
  22.     first twelve and third twelve entries in a lookup table for finding
  23.     the source location in the R register used as input to f(R,K).
  24.  
  25.     Secondary Keying Features
  26.     -------------------------
  27.  
  28.     The salt value is intended to defeat the use of faster chip implementations
  29.     of the DES algorithm.  Having designed Gate Arrays, and drawn a set
  30.     of schematics for the DES algorithm, the salt adds twelve dual, 2:1 Muxes
  31.     and a 12 bit register to the basic algorithm.  Even in an MSI
  32.     implementation, and including the hardware for translating a block
  33.     from the syndrome (passwd entry) and comparator for a match, the
  34.     16 pin equivalent count is less than 120.  For hardware, salt is not
  35.     relevant.
  36.  
  37.     Using tri-ranked registers for the R and L blocks, a 30 MHz clock,
  38.     a dictionary held in a cache RAM, you could make 1.875 Million attempts
  39.     per second on a single value.  By comparing against the syndrome, instead
  40.     of ZEROs, and adding the capability to change the target syndrome (from
  41.     a RAM cache) the rate can be sustained for as many entries as you
  42.     have syndrome cache.  The problem is not the complexity of the DES
  43.     algorithm, but instead the simplicity of the keys involved.
  44.  
  45.     Simple Passwords
  46.     ----------------
  47.  
  48.     In The UNIX System: UNIX Operating System Security, AT&T Bell Laboratories
  49.        -----------------------------------------------
  50.     Technical Journal, Vol. 63, No. 8, Part 2 (Oct. 1984) pp. 1649-1672,
  51.     F.T. Grampp and Robert H. Morris.  The authors describe trying 20 of
  52.     the most common female names, followed by a single digit, for a total
  53.     of 200 passwords.  At least one of these 200 was valid on each target
  54.     machine.
  55.  
  56.     In Password Security: A Case History by Robert Morris and Ken Thompson,
  57.        ---------------------------------
  58.     the authors describes collecting 3,289 passwords over a period of time.
  59.  
  60.     Of those 15 were single characters, 72 were two char strings, 464 were
  61.     three char strings, 477 were four char strings, 706 were 5 char strings
  62.     and 605 were six char strings.  Additionaly, 492 passwords appeared
  63.     in various available dictionaries.  2,831 or 86 percent could be solved
  64.     with a combination of dictionary and rule attacks.  There have been two
  65.     results of this:
  66.  
  67.        1) more complex rules for acceptable passwords have been adopted.
  68.  
  69.        2) an attempt has been made to either hide the algorithm (such as
  70.           use of RSA) or hide the passwords (shadow password files).
  71.  
  72.     When combined with limiting attempts, hiding the algorithm or hiding
  73.     the syndrome seriously slows down the time to enter a system.
  74.  
  75.     I have a graphics version of lock.c for my system, that can caste the
  76.     required password to be that of any user.  This allows real lock up of
  77.     the console (using root or system password).  It seems a shame to hide
  78.     such stuff.
  79.  
  80.     These depend on scarcity of information, site security, and absolute
  81.     control over machine access, which with the myrid of bugs, which seem
  82.     to drift in and out of releases and various producers of UNIX compatible
  83.     software and systems, secondary keying variables (including the number
  84.     of iterations of DES), restrictions in password compostion, and otherwise
  85.     proprietary algorithms do not seem to be an absolute guarantee against
  86.     dictionary attack.  The single biggest threat appears to be the size of
  87.     the password.  There should be some upper limit as to the size of a
  88.     dictionary for a password attack.  Pushing this limit should be a serious
  89.     deterrent.
  90.  
  91.     Longer Passwords
  92.     ----------------
  93.  
  94.     Using longer passwords should require a lower bound on the size
  95.     (which could be measured without included common pronouns and adjectives.)
  96.  
  97.  
  98.  
  99.     There are several requirements for longer passwords:
  100.  
  101.        1) longer passwords must produce distinct syndromes  (their syndromes
  102.           should not match those for partial products).
  103.  
  104.        2) The syndromes should not map into syndromes from existing
  105.           dictionary attack.
  106.  
  107.        3) retention of present password system  (Increasing the size  and
  108.           complexity of the dictionary and rule attack systems).
  109.  
  110.     Instead of a set of rules for a password of at most 8 characters, we
  111.     now have two set of rules, including a set for passwords of more than
  112.     8.  If rules are included for longer passwords to prevent the use of
  113.     simple phrases, as is done for shorter passwords,  A dictionary attack
  114.     can become more than linearly larger.
  115.  
  116.     To prevent detection of the size of the password, entries in the password
  117.     file should be of identical length.
  118.  
  119.     Implementation
  120.     --------------
  121.  
  122.     A sample crypt routine with modifications for longer passwords is
  123.     appended.  This is for use with my implementation of DES, but shows
  124.     how longer passwords can be handled.  Also appended is lmakekey.c
  125.     which generates password file passwd_entries for longer passwords.
  126.     The input has not been blanked.  It also allows multiple passwords
  127.     with the same salt to executed and output to a file.  A sample of
  128.     its execution for strings length 8 34 using -
  129.     "mississippi riverboat gambling man" as an input.  The salt used
  130.     is the null salt "..".
  131.  
  132.     I may well publish my DES implementation in the future.  It is 3.4
  133.     times faster than the DES found in libcrypt.  I can get approximately
  134.     10 Kbytes/sec on my IRIS 4D-25/G when implemented in a program
  135.     doing read() and write()'s in 8 byte chunks.  The progam also supports
  136.     a test vector file for implementation verification.
  137.  
  138.     The implementation is present system compatible for passwords 8 or
  139.     fewer characters long.  The salt value is always used.
  140.  
  141.     For passwords greater than 8 characters, The last 8 characters are used
  142.     as key.  The initial block is cleared to zeros, and the first byte
  143.     of key is EXORed with the first byte of the 8 byte block string.
  144.     A DES iteration is performed.  For all remaining password bytes not
  145.     involved in the key, each is then EXORed with location[0] of the byte
  146.     string, followed by an iteration of DES.  If less than 25 iterations of
  147.     DES have taken place, DES is iterated until 25 iterations have taken
  148.     place.  Note, that in the character array implementation of DES used,
  149.     the password bytes used as data are not left shifted to leave bit 0
  150.     blank, as is done by the routine loadkey().  To produce the results
  151.     shown appended, the following mapping equivalency is helpful.
  152.  
  153.     The mapping equivalency is:
  154.  
  155.       L/R[  ]      data.string[0]      ([3] for little_endian)
  156.  
  157.        L[31]           Bit 0
  158.        R[31]           Bit 1
  159.        L[23]           Bit 2
  160.        R[23]           Bit 3
  161.        L[15]           Bit 4
  162.        R[15]           Bit 5
  163.        L[ 7]           Bit 6
  164.        R[ 7]           Bit 7
  165.  
  166.  
  167.     My system performs big_endian byte in long ordering: byte order is 0123.
  168.     This is motorola compatible.  Little endian systems should use
  169.     data.string[3] instead.   My implementation of DES can be compiled for
  170.     any _endian system.
  171.  
  172.     Note that Bit 7 (R[7]) can be expected to be a ZERO for ascii, resulting
  173.     in at most 7 bits of divergence from the value of the current block
  174.     for each byte of the password.
  175.  
  176.     System Impact
  177.     --------------
  178.  
  179.     A new getpass() routine is needed.  This appears to be a good place
  180.     to do some rule checking based on length.
  181.  
  182.     A new passwd and login program are needed for longer passwords.
  183.  
  184.     A maximum size password need be specified for writing portable code.
  185.  
  186.     A new crypt(pw,salt) routine for longer passwords is needed.
  187.  
  188.     libPW may be immune from impact.
  189.  
  190.  
  191. APPENDS
  192. -------
  193.  
  194. =============
  195. crypt routine  - based on a long aligned char string block
  196. =============
  197. char * lcrypt(pw,salt)
  198. char   *pw, *salt;
  199. {
  200.     int i,c,e, bit, ci, pw_len;
  201.     static char outbuf[16];
  202.     union LR_block  data;            /* long aligned char array[9] */
  203.  
  204.     for (pw_len = 0; pw[pw_len];pw_len++)    /* pw_len = strlen(pw) */
  205.            ;
  206.     for (i = 0; i< 8;i++)          /* strncpy(data.string,pw,8);   */
  207.        if ( pw_len > 8)
  208.            data.string[i] = pw[i + pw_len-8] ;     /* last 8 chars */
  209.        else
  210.            data.string[i] = pw[i];
  211.  
  212.     loadkey(data.string,1);        /* first 8 chars nulled         */
  213.     data.string[8] = 0;                    /* needed for outbuf conversion */
  214.  
  215.     toggle_E(salt);                /* for new implementation des   */
  216.  
  217.     if ( pw_len < 9)
  218.        for(i= 0; i < 25; i++)
  219.            des(&data,0);           /* faster encrypt()             */
  220.  
  221.     else {
  222.        for(i=0; i < pw_len - 8; i++) {
  223.            data.string[1] ^= pw[i];
  224.            des(&data,0);
  225.        }
  226.        if ( (i = (25 - (pw_len-8)) > 0))  /* at least 25 iterations */
  227.            while ( i-- )
  228.                des(&data,0);
  229.     }
  230.  
  231.        toggle_E(salt);         /* undo for sucessive crypt() calls  */
  232.  
  233.     for (i = 2,ci = 0, bit = 7; i < 13;i++) {
  234.        c = 0;
  235.        for ( e = 5; e >= 0 ; e--){
  236.            if (bit < 0 ) {
  237.                ci++;
  238.                bit = 7;
  239.            }
  240.            if (BIT(bit--) & data.string[ci])
  241.                c |= BIT(e);
  242.        }
  243.        c += '.';
  244.        if (c > '9')
  245.            c += 7;
  246.        if (c > 'Z')
  247.            c +=6;
  248.        outbuf[i] = c;
  249.     }
  250.     outbuf[i] = 0;
  251.     outbuf[0] = salt[0];outbuf[1] = salt[1];
  252.     if (outbuf[1] == 0)
  253.        outbuf[1] = outbuf[0];
  254.     return(outbuf);
  255. }
  256. ==========
  257. lmakekey.c
  258. ==========
  259. #include <stdio.h>
  260. #include <string.h>
  261.  
  262. extern char *lcrypt();
  263.  
  264. #define STRLEN 128
  265.  
  266. main(argc, argv)
  267. int    argc;
  268. char   *argv[];
  269. {
  270. int i;
  271. char key[BUFSIZ], salt[BUFSIZ], *password;
  272. FILE *outfile;
  273. int firstpass = 1;
  274.     if ( argc == 2) {
  275.        if ( (outfile = fopen(argv[1],"a")) == NULL) {
  276.            fprintf(stderr,"ERROR: %s, can't open %s for append\n",
  277.                argv[0],argv[1]);
  278.        }
  279.     }
  280.  
  281.     while ( argc == 2 || firstpass){
  282.  
  283.  
  284.     fprintf(stdout,"Password? ");
  285.     fgets(key,STRLEN,stdin);
  286.  
  287.     if( strlen(key) > STRLEN)
  288.        key[STRLEN] = 0;
  289.  
  290.     for (i = 0; i < STRLEN; i++)
  291.        if (key[i] == '\n')
  292.            key[i] = 0;
  293.  
  294.    if (firstpass) {
  295.        fprintf(stdout,"Salt? ");
  296.        fgets(salt,STRLEN,stdin);
  297.    }
  298.  
  299.     if ( strlen(salt) > 2)
  300.        salt[2] = 0;
  301.  
  302.     password = lcrypt( key, salt);
  303.     fprintf(stdout,"%s\n",password);
  304.  
  305.     if (argc == 2)
  306.        fprintf(outfile,"length = %3d, passwd= %s, in: %s\n",
  307.                    strlen(key),password, key);
  308.     firstpass = 0;
  309.     fflush(outfile);
  310.     }
  311.     return(0);
  312. }
  313. =======================
  314. sample longer passwords
  315. =======================
  316. length =   8, passwd= ..7kVXGzGEb7Y, in: mississi /* crypt() compatible */
  317. length =   9, passwd= ..C8v9PtCB.0Y, in: mississip
  318. length =  10, passwd= ..qjDDYqQvBlA, in: mississipp
  319. length =  11, passwd= ..cSxjNmzNjEI, in: mississippi
  320. length =  12, passwd= ..bPSqz0AtIu6, in: mississippi
  321. length =  13, passwd= ..hAmDw39a32k, in: mississippi r
  322. length =  14, passwd= ..3enRY0SxJCs, in: mississippi ri
  323. length =  15, passwd= ..tid0WYNoPrs, in: mississippi riv
  324. length =  16, passwd= ..RCEkliTOVH6, in: mississippi rive
  325. length =  17, passwd= ..C/GbzVyN5Hc, in: mississippi river
  326. length =  18, passwd= ..3/rSfkQ5nDs, in: mississippi riverb
  327. length =  19, passwd= ..FWryDwutGyQ, in: mississippi riverbo
  328. length =  20, passwd= ..J8KOcjnnn6Y, in: mississippi riverboa
  329. length =  21, passwd= ..tMv7dg6ksbE, in: mississippi riverboat
  330. length =  22, passwd= ..cpUzQd3uyuQ, in: mississippi riverboat
  331. length =  23, passwd= ..kO8JORivC8g, in: mississippi riverboat g
  332. length =  24, passwd= ..ypuS9WWIJc2, in: mississippi riverboat ga
  333. length =  25, passwd= ..XGZDJsPLNic, in: mississippi riverboat gam
  334. length =  26, passwd= ..niG1hl1tjW2, in: mississippi riverboat gamb
  335. length =  27, passwd= ..AB8aRp181jA, in: mississippi riverboat gambl
  336. length =  28, passwd= ..zr068aSaFE2, in: mississippi riverboat gambli
  337. length =  29, passwd= ..6UY6NO.J6R., in: mississippi riverboat gamblin
  338. length =  30, passwd= ..w0m5AQ2XxFw, in: mississippi riverboat gambling
  339. length =  31, passwd= ..sYSNGs6qUww, in: mississippi riverboat gambling
  340. length =  32, passwd= ..xZ0//Llq3Ck, in: mississippi riverboat gambling m
  341. length =  33, passwd= ..MFsadQbW1LA, in: mississippi riverboat gambling ma
  342. length =  34, passwd= ..riGwJEykDBQ, in: mississippi riverboat gambling man
  343. ---------------------------------------------------------------------------
  344.  
  345.  
  346.