Hi, Craig.
If you implement it properly, either solution will work fine. But,
there's a lot of room to not implement things properly. If you just
use SHA1 you might run into some problems.
Neither cryptographic primitive you've mentioned is really going to be
very standard, since the standards right now for password storage are
crypt() (which you should not use) and md5 crypt. MD5 crypt is
probably *okay* for password storage. But it could be a lot better.
It sounds like you can't use MD5 anyway. I'll get to something that
will be somewhat standard, but in a different context from the way it
is normally used.
First, let me alleviate your concerns on using 3DES. There are
several ways to turn a block cipher into a non-reversible hash
function. One way that crypt() uses is to turn the password into a
binary key (which is used to key your block cipher). Then, the
algorithm encrypts all zeros. The real issue with that solution is
how to convert a password into something that is key-sized. The tact
that crypt() takes is very stupid. It requires passwords to be a
fixed size (anything beyond 8 characters is truncated). There are
other constructs that turn a block cipher into a one-way hash
function, which can handle inputs of any length easily. The best
known is Davies-Meyer.
Some key design points:
1) You *need* to make sure to have reasonable salts.
2) You want the difficulty of brute force to be high. For that reason, it
is common to apply salt then to continually rehash the password thousands
of times. This way, calculating the value for comparison a single time
isn't all THAT expensive, but mounting a brute-force attack becomes
ludicrously expensive fairly quickly.
3) The thing I would use is PKCS#5 v.2.0, the "password-based key derivation
function", which I'll call PBKDF2. While PBKDF2 is generally used for
deriving keys used in MACs and block ciphers, the key it produces
is non-reversible, meaning you could easily use it for password storage.
The API handles salts and does the multiple-hash trick, so meets the
above requirements. If you explicitly prefix your salts with some fixed
string like "Password Hash Deriver" then append a sufficient random value,
you don't have to worry, you can also use PBKDF2 to derive keys from the
same password (the trick is making sure the salts are unique).
Here's an implementation of PBKDF2 based on the OpenSSL API's
implementation of SHA1:
pbe.h:
#ifndef PBE_H__
#define PBE_H__
int pbkdf2(unsigned char *pw, unsigned int pwlen, char *salt,
unsigned long long saltlen, unsigned int ic,
unsigned char *dk, unsigned long long dklen);
#endif
pbe.c:
#include <openssl/evp.h>
#include <openssl/hmac.h>
#include "pbe.h"
#define HLEN (20) /*Using SHA-1 */
int pbkdf2(unsigned char *pw, unsigned int pwlen, char *salt,
unsigned long long saltlen, unsigned int ic,
unsigned char *dk, unsigned long long dklen) {
unsigned long l, r, i, j;
unsigned char txt[4], hash[HLEN*2], tmp[HLEN], *p = dk, *lhix, *hix, *swap;
short k;
int outlen;
if(dklen > ((((unsigned long long)1)<<32)-1)*HLEN) {
/* TODO: Call an error handler. */
return 1;
}
l = dklen/HLEN;
r = dklen%HLEN;
for(i=1;i<=l;i++) {
sprintf(txt, "%04u", (unsigned int)i);
HMAC(EVP_sha1(), pw, pwlen, txt, 4, hash, &outlen);
lhix = hash;
hix = hash + HLEN;
for(k=0;k<HLEN;k++) {
tmp[k] = hash[k];
}
for(j=1;j<ic;j++) {
HMAC(EVP_sha1(), pw, pwlen, lhix, HLEN, hix, &outlen);
for(k=0;k<HLEN;k++) {
tmp[k] ^= hix[k];
}
swap = hix;
hix = lhix;
lhix = swap;
}
for(k=0;k<HLEN;k++) {
*p++ = tmp[k];
}
}
if(r) {
sprintf(txt, "%04u", (unsigned int)i);
HMAC(EVP_sha1(), pw, pwlen, txt, 4, hash, &outlen);
lhix = hash;
hix = hash + HLEN;
for(k=0;k<HLEN;k++) {
tmp[k] = hash[k];
}
for(j=1;j<ic;j++) {
HMAC(EVP_sha1(), pw, pwlen, lhix, HLEN, hix, &outlen);
for(k=0;k<HLEN;k++) {
tmp[k] ^= hix[k];
}
swap = hix;
hix = lhix;
lhix = swap;
}
for(k=0;k<r;k++) {
*p++ = tmp[k];
}
}
return 0;
}
Basically, the parameters are as follows:
pw, The plaintext password;
pwlen, the length of pw in bytes;
salt, a string that should be unique (I'd randomly select 8-16 bytes);
saltlen, the length of salt;
ic, the "iteration count"... see below;
dk, the derived key (the password hash); and
dklen, the length you wish dk to be.
Store the salt (at least the random part of it) and the derived key,
as you need these items to validate the password.
The iteration count is as described above. I recommend that you use a
number that causes noticable but not intolerable delays. If it takes
a full second or two to validate a password, that's not too bad.
Remember that in a few years, it might take far less time to calculate
the same password.
A few final comments:
1) You can ask for any length derived key you like, but if you want to
use the full strength of the hash function, ask for a full 20-byte
result. A smaller result will still be reasonably secure, because the
best practical attack is still going to be brute force. An 8-byte
derived key will give 64 bits of security from brute force attacks,
which is more security than you'd expect to get from the natural
entropy of the password, generally. Given a single password, the odds
of finding another password that give the same hash will be
approximately 1 in 2^(8*n), where n is the number of bytes you use for
storage, assuming you're storing in a raw binary format. Choose
appropriately.
2) The other consideration is that you might need to encode the password
"hash" in some sort of printable representation. You can always base
64 encode. There are other ways to encode without such drastic
message expansion, but hopefully you're not in an incredibly
space-constrained environment.
3) I've used the OpenSSL API above because I happened to have the code
lying around. If you're not using OpenSSL, but you have a PKCS#11-ish
interface to SHA1, you can use this implementation of HMAC (which
requires fewer parameters):
/* define uint32 appropriately for your platform. */
typedef unsigned int uint32;
typedef struct {
uint32 a;
uint32 b;
uint32 c;
uint32 d;
uint32 e;
} SHADGST;
#define SHA_BLKSZ (64) /* Internal block size of the algorithm */
void
HMAC(unsigned char *key, unsigned char *in, size_t len, unsigned char *out) {
SHA_CTX ctx;
unsigned char pkey[64];
memset(pkey, 0x36, SHA_BLKSZ);
/* This assumes your compiler will always block-align pkey, or that your
* platform doesn't care (most don't these days). If that's a problem,
* you can always XOR byte by byte.
*/
((SHADGST *)pkey)->a ^= ((SHADGST *)key)->a;
((SHADGST *)pkey)->b ^= ((SHADGST *)key)->b;
((SHADGST *)pkey)->c ^= ((SHADGST *)key)->c;
((SHADGST *)pkey)->d ^= ((SHADGST *)key)->d;
((SHADGST *)pkey)->e ^= ((SHADGST *)key)->e;
SHA1_Init(&ctx);
SHA1_Update(&ctx, pkey, SHA_BLKSZ);
SHA1_Update(&ctx, in, len);
SHA1_Final(out, &ctx);
((SHADGST *)pkey->a ^= 0x6a6a6a6a;
((SHADGST *)pkey->b ^= 0x6a6a6a6a;
((SHADGST *)pkey->c ^= 0x6a6a6a6a;
((SHADGST *)pkey->d ^= 0x6a6a6a6a;
((SHADGST *)pkey->e ^= 0x6a6a6a6a;
SHA1_Init(&ctx);
SHA1_Update(&ctx, pkey, SHA_BLKSZ);
SHA1_Update(&ctx, out, sizeof(SHADGST));
SHA1_Final(out, &ctx);
}
John
On Tue, Nov 05, 2002 at 01:01:28PM -0800, Craig Minton wrote:
> We are considering changing our password storage from a home-grown algorithm to a standard. We are mainframe based and only have triple-DES and SHA-1 algorithms available. However, we many questions about the best way to proceed. We are leaning towards using SHA-1 for a few of reasons. The password being "encrypted" using SHA-1 never need be retrieved, just verified. Indeed, the password should not be retrievable. By not using triple-DES there is no need to secure a key used to encrypt them. Also, with triple-DES, if someone was to obtain the key, by whatever means, retrieving all of the passwords would be trivial. The downside to SHA-1 is that we would have to increase our storage requirements for the encrypted portion from 8 bytes to 20 bytes.
>
> Is there anything inherently wrong with using SHA-1 to hash passwords for verification?
>
> Is there a benefit to using triple-DES instead?
>
> Is SHA-1 any more suseptible to attack, brute-force or cr ypto-analytic, than triple-DES? My 2nd edition copy of Applied Cryptography states that there is no known crypto-analytic attack known for SHA-1, but that book is now several years old.
>
> It was suggested to use SHA-1 and then remove all of the bytes from the hash except for 8 bytes (truncated from the beginning, end ,or somewhere in between) and store this, thus not increasing storage requirements. Would this compromise the algorithm? How much would it increase the chance that two passwords then had the same truncated hash?
>
> I look forward to any insights you can provide and will be glad to answer additional questions where possible.
>
> Craig
>
> _____________________________________________________________
> Fight the power! BlazeMail.com
>
> _____________________________________________________________
> Select your own custom email address for FREE! Get you@yourchoice.com w/No Ads, 6MB, POP & more! http://www.everyone.net/selectmail?campaign=tag
This archive was generated by hypermail 2b30 : Sat Nov 09 2002 - 18:55:33 PST