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
