Re: password crypt consideration: simple question

[Marcus Watts <mdw_(_at_)_umich_(_dot_)_edu>]

Gustavo Vieira Coelho Rios <gustavo_(_dot_)_rios_(_at_)_terra_(_dot_)_com_(_dot_)_br> writes:
> > 
> > But why the attraction to using symmetric encryption?  What you're
> > really looking for here is a one-way password hash; as used for Unix
> > authentication there's no value to reversibility.
> 
> OneWay hash functions?

A one-way hash is a compression function that takes input and reduces
it to a (usually) smaller fixed size, in such a manner that it is
difficult to take the output and reconstruct the input.

SHA-1, MD5, etc., are all examples of such hashes.  So is the blowfish
password hash algorithm.  It's possible to take any symmetric
encryption algorithm and convert it into a one-way hash; simply come up
with some way to bash the input into a key and use it to encrypt a
constant.  It is also possible to take any one-way hash and convert it
into a symmetric encryption algorithm, for instance by using a
"feistal" network which uses a clever set of xor's between successive
half-blocks to produce a reversible transform.  Most symmetric block
algorithms are in fact based on feistal networks and very simple
one-way functions.

For much much more on this, get Schneier's _AC_; it's a standard
reference you should already have.  Borders will have it.

> 
> > There are plenty of one-way hashes that are better at taking in and
> > outputing a wide swath of data, so they should be more attractive.  One
> > useful advantage is there's no reason to have any particular password
> > length limit (blowfish has an obscure 72 character limit.)  The old md5
> > password hash that's in openbsd is relatively ad-hoc, but a
> > recognizable ancestor of pkcs#5 pbkdf2.  Rather than using md5, you
> > could use sha-1, sha-256, or tiger.  Pbkdf2 includes a variable
> > iteration count, so mostly plugging it into openbsd would involve
> > base64 & such.  Blowfish's iteration count is specified log base 2;
> > that's a useful idea to preserve.
> 
> Yes! This was my first initial ideia! SHA1 or even RMD160!
> 
> But according to some feedback i got from this list. I should forget
> about them.
> Hashing like md5/sha1/rmd160 are very in terms of cpy cycles, what lets
> you open to dict attacks. Is that true? This is really strange! Some,
> like you suggest hashing, other an symetric crypto approach! What is the
> way to go.

Careful what you ask and what your answer means.  The sha-1 transform
itself should be quite invariant CPU-wise.  RC6 and MARS, which use
multiplication, should exhibit some timing variation.  RC5, which uses
variable shifts, will show timing variation on old or small processors,
such as the mc68000, 8088, but should run in constant time on mc68020
or pentium.  Any of these algorithms may behave less predictably on
newer hardware which has cache memory and therefore may exhibit
data sensitive timing based on memory reference locality.

Any algorithm that can deal with arbitrary length passwords is going to
exhibit *some* timing variation (given a sufficiently large password).
Using what Todd says is a "plain one-way hash" may show quite a bit of
timing variation.  It may be less obvious than you think for real
passwords because sha-1 (and md5) work on 64-byte blocks, so the
difference between a 1-byte password and a 60-byte password is mostly
the difference between "memcpy" and "memset" - might be very hard to
measure.  A 65-byte password will show a big jump (and the split
between depends on padding & other algorithm details.)  But very few
users willingly tolerate passwords longer than 60 bytes.

You might find it interesting to see if you can measure CPU speed
differences vs. password length (or password data) for a straight md5
and for the existing blowfish crypt code.  md5 should have a nice step
function every 64 bytes of password length.  I saw something in
blowfish at a quick glance that looked dependent on key length, but I
could be wrong.  Quite aside from all else, the timing support that's
in openbsd may not be detailed enough to permit you to get good
data on this, even with a very cooperative program that doesn't
do anything else.

Most people would do something more than a simple way-way hash
on a password.  A simple enhancement is to use hmac.  A more
complicated solution is to do the multiple iterations that
the md5 crypt stuff does.  A slight simplification is what
pkcs#5 pbkdf2 does -- the core of this is just a bunch of nested
hmac functions.  This is going to average out any data
sensitive timing - I doubt the result is going to be useful
to an attacker.  The input function is sensitive to password
length -- given an iteration count of 40,000; a password
of length 65 might take 1/40,000 longer than one of length 60.
Even that may be hard to measure.  This is what Todd was really
trying to tell you -- not "don't use a one-way hash", but
"do something else on fixed size data a whole bunch too".

David Norman <norny_(_at_)_yahoo_(_dot_)_com> writes:
> ...or don't use dictionary passwords, then a dictionary attack is
> pointless anyway.

Vandals who know your constraints can probably make a good guess as to
what words to put in their "dictionary" - obviously they won't be in
Merriam-Webster if you don't allow your users to pick them.  You won't
be able to keep your constraints very secret either; if you haven't
already told your users what they are, your users will deduce them on
their own, and besides, any vandal who can steal your password shadow
database can probably steal your password constraints too.  You should
probably count yourself lucky they haven't installed a network sniffer
or patched system binaries, but went for the slow offline dictionary attack.

You should do some form of password quality checking, and that should
certainly exclude dictionary words.  But that doesn't make people pick
True Random passwords.  It merely makes them pick something harder to
remember.  The theory of course is that the harder to remember
passwords occupy a larger space so have more entropy.  This is not
necessarily safe but it's the best we can do; people don't pick true
random numbers and don't remember true random junk.  If you doubt this,
run the "die hard" random number test on numbers you pick out of your
head (people turn out to be very bad random number generators), and try
memorizing some machine generated "random" base-32 passwords of length
8 (only 40 bits of entropy / password there!)  Assigning people "true
random" passwords would get passwords with arbitrary amounts of entropy
in them.  But that has obvious consumer resistance obstacles.

					-Marcus Watts