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 #include 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 --------------------------------------------------------------------------- X-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-X Another file downloaded from: NIRVANAnet(tm) & the Temple of the Screaming Electron Jeff Hunter 510-935-5845 Rat Head Ratsnatcher 510-524-3649 Burn This Flag Zardoz 408-363-9766 realitycheck Poindexter Fortran 415-567-7043 Lies Unlimited Mick Freen 415-583-4102 Specializing in conversations, obscure information, high explosives, arcane knowledge, political extremism, diversive sexuality, insane speculation, and wild rumours. ALL-TEXT BBS SYSTEMS. Full access for first-time callers. We don't want to know who you are, where you live, or what your phone number is. We are not Big Brother. "Raw Data for Raw Nerves" X-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-X