See your copy of /usr/src/lib/libcrypt/crypt-md5.c:
/*
* and now, just to make sure things don't run too fast
* On a 60 Mhz Pentium this takes 34 msec, so you would
* need 30 seconds to build a 1000 entry dictionary...
*/
for(i = 0; i < 1000; i++) {
MD5Init(&ctx1);
if(i & 1)
MD5Update(&ctx1, (const u_char *)pw, strlen(pw));
else
MD5Update(&ctx1, (const u_char *)final, MD5_SIZE);
if(i % 3)
MD5Update(&ctx1, (const u_char *)sp, (u_int)sl);
if(i % 7)
MD5Update(&ctx1, (const u_char *)pw, strlen(pw));
if(i & 1)
MD5Update(&ctx1, (const u_char *)final, MD5_SIZE);
else
MD5Update(&ctx1, (const u_char *)pw, strlen(pw));
MD5Final(final, &ctx1);
}
This algorithm is still the default on FreeBSD 8. (Blowfish is available --
but has it been tuned for slowness either? I have not checked.) The purpose
of these functions is to be slow, but the above has not been slow for years.
Hence this patch:
--- crypt.h.orig 2010-01-28 10:14:50.000000000 -0800
+++ crypt.h 2010-01-28 10:17:49.000000000 -0800
@@ -32,6 +32,9 @@
#define MD4_SIZE 16
#define MD5_SIZE 16
+/* As processors get faster, increase this. 1000 was good on a Pentium 60. */
+#define MD5_SLOW 100000
+
char *crypt_des(const char *pw, const char *salt);
char *crypt_md5(const char *pw, const char *salt);
char *crypt_nthash(const char *pw, const char *salt);
--- crypt-md5.c.orig 2010-01-28 10:18:03.000000000 -0800
+++ crypt-md5.c 2010-01-28 10:19:00.000000000 -0800
@@ -107,10 +107,10 @@
/*
* and now, just to make sure things don't run too fast
- * On a 60 Mhz Pentium this takes 34 msec, so you would
+ * On a 60 Mhz Pentium MD5_SLOW = 1000 takes 34 msec, so you would
* need 30 seconds to build a 1000 entry dictionary...
*/
- for(i = 0; i < 1000; i++) {
+ for(i = 0; i < MD5_SLOW; i++) {
MD5Init(&ctx1);
if(i & 1)
MD5Update(&ctx1, (const u_char *)pw, strlen(pw));
I'm sure someone will correct me if I'm wrong, but you can't do this without establishing this as an entirely new algorithm. The hashes generated after your patch will not be compatible with existing password files, thus anyone who applies this will be unable to log in. Have you tried it? In response to Chris Palmer <chris@noncombatant.org>:> See your copy of /usr/src/lib/libcrypt/crypt-md5.c: > > /* > * and now, just to make sure things don't run too fast > * On a 60 Mhz Pentium this takes 34 msec, so you would > * need 30 seconds to build a 1000 entry dictionary... > */ > for(i = 0; i < 1000; i++) { > MD5Init(&ctx1); > if(i & 1) > MD5Update(&ctx1, (const u_char *)pw, strlen(pw)); > else > MD5Update(&ctx1, (const u_char *)final, MD5_SIZE); > > if(i % 3) > MD5Update(&ctx1, (const u_char *)sp, (u_int)sl); > > if(i % 7) > MD5Update(&ctx1, (const u_char *)pw, strlen(pw)); > > if(i & 1) > MD5Update(&ctx1, (const u_char *)final, MD5_SIZE); > else > MD5Update(&ctx1, (const u_char *)pw, strlen(pw)); > MD5Final(final, &ctx1); > } > > This algorithm is still the default on FreeBSD 8. (Blowfish is available -- > but has it been tuned for slowness either? I have not checked.) The purpose > of these functions is to be slow, but the above has not been slow for years. > Hence this patch: > > > --- crypt.h.orig 2010-01-28 10:14:50.000000000 -0800 > +++ crypt.h 2010-01-28 10:17:49.000000000 -0800 > @@ -32,6 +32,9 @@ > #define MD4_SIZE 16 > #define MD5_SIZE 16 > > +/* As processors get faster, increase this. 1000 was good on a Pentium 60. */ > +#define MD5_SLOW 100000 > + > char *crypt_des(const char *pw, const char *salt); > char *crypt_md5(const char *pw, const char *salt); > char *crypt_nthash(const char *pw, const char *salt); > > > --- crypt-md5.c.orig 2010-01-28 10:18:03.000000000 -0800 > +++ crypt-md5.c 2010-01-28 10:19:00.000000000 -0800 > @@ -107,10 +107,10 @@ > > /* > * and now, just to make sure things don't run too fast > - * On a 60 Mhz Pentium this takes 34 msec, so you would > + * On a 60 Mhz Pentium MD5_SLOW = 1000 takes 34 msec, so you would > * need 30 seconds to build a 1000 entry dictionary... > */ > - for(i = 0; i < 1000; i++) { > + for(i = 0; i < MD5_SLOW; i++) { > MD5Init(&ctx1); > if(i & 1) > MD5Update(&ctx1, (const u_char *)pw, strlen(pw)); > > _______________________________________________ > freebsd-security@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-security > To unsubscribe, send any mail to "freebsd-security-unsubscribe@freebsd.org"-- Bill Moran Collaborative Fusion Inc. http://people.collaborativefusion.com/~wmoran/ wmoran@collaborativefusion.com Phone: 412-422-3463x4023 **************************************************************** IMPORTANT: This message contains confidential information and is intended only for the individual named. If the reader of this message is not an intended recipient (or the individual responsible for the delivery of this message to an intended recipient), please be advised that any re-use, dissemination, distribution or copying of this message is prohibited. Please notify the sender immediately by e-mail if you have received this e-mail by mistake and delete this e-mail from your system. E-mail transmission cannot be guaranteed to be secure or error-free as information could be intercepted, corrupted, lost, destroyed, arrive late or incomplete, or contain viruses. The sender therefore does not accept liability for any errors or omissions in the contents of this message, which arise as a result of e-mail transmission. ****************************************************************
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, Chris, On 2010/01/28 10:24, Chris Palmer wrote:> See your copy of /usr/src/lib/libcrypt/crypt-md5.c:I'd appreciate your effort put into this but I feel necessary to say something on this topic. The slowness was useful at the time when the code was written, but I don't think it would buy us as much nowadays, expect the slowness be halved from time to time, not to mention the use of distributed techniques to accelerate the build of dictionaries. Second, recent research has shown MD5 to be vulnerable to collision attacks [1] by the end of 2008. It's time to switch to some better algorithm, maybe something like Skein, etc... [1] http://www.kb.cert.org/vuls/id/836068 - -- Xin LI <delphij@delphij.net> http://www.delphij.net/ FreeBSD - The Power to Serve! Live free or die -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.14 (FreeBSD) iQEcBAEBAgAGBQJLYeveAAoJEATO+BI/yjfBWzkH/icNHpEr5w/ulBlKe/fr/4Uo +ZrGj7SixbL4g6yLPd79JKoJpFZEdMlY9AnLTr3QT0/OwKyySwVXg7Fh+7LA3r+4 DqE4N2pZfIqD6maS7ccF6Yp+2JAN9BJG7O73W6fEhm0mRTPkdLWMnB1gMx6DymQh NQvx41QADmiN3jq6DapFJhQRDwFcxFzCsyg3eZ0nIwaCP+72HBPCEKEPro1JtLSF sm0uf0TIyaGTgMe4xcjtwdlRtMmNA0V5yZwGHOcW09cuxxt3n79BA2RrPVz/+6Tr KIa6LhNzoF1Eb4wfCSrSu2c4a6nM6+FSGT5fdpx/jkfr125W7sQYZuEVNzPWuxU=LuLY -----END PGP SIGNATURE-----
What would be the consequence of having an algorithm that will increase the amount of time needed to check the next password after a failure. In other words, check the first one fast, the second try it will be slower, then the third even slower and then the forth even slower etc. Is this how it is currently implemented? (Sorry I did not read the code). -r
In message <20100128182413.GI892@noncombatant.org>, Chris Palmer writes:> /* > * and now, just to make sure things don't run too fast > * On a 60 Mhz Pentium this takes 34 msec, so you would > * need 30 seconds to build a 1000 entry dictionary... > */A number of points: 1. I'm not sure slowing it down buys very much security, as far as I know, brute-forcing $1$ is still out of the question, mostly because of the wide salt. 2. Most "brute force" attacks are dictionary attacks, and slowing the algorithm down for those is pointless: The bad guys have grids of Nx100k machines to grind. Even making it take half a second will not inconvenience them much. 3. Compatibility: as far as I know, we have a configurable mechanism for choosing preferred crypt algo for new passwords, and autodetection on old passwords. 4. Encoding #rounds: one of the OpenBSD derivatives for $1$ does that, consider adoption, rather than NIH. Increased strength against rainbow and dictionaries can be had by making the low bits in #rounds a salt. 5. Cross system compat: A valid concern in some environments (See #3) and not in others. Certainly not a valid reason to never change algorithm again (see #6). 6. The major point behind $1$ was lost: You can change algorithm with a frequency of twice your password expiry time. My intent back in the middle of the nineties was not to write the "endlösung" for password encryption, but rather to point out that password hashing is "kleenex-crypto" which can, and should, be swapped at regular intervals. Every 15 years may be sufficiently regular. 7. Consider preempting the bike-shed, by asking some card-carrying cryptographers for the correct way to employ a crypto-hash algorithm in a way that does soak up some CPU time. 8. A number of interesting ideas was battered about back when $1$ was introduced, check mail archives and read the OpenBSD paper, even though it is mostly plagarism. Poul-Henning -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence.
On Thu, Jan 28, 2010 at 10:24:13AM -0800, Chris Palmer wrote:> See your copy of /usr/src/lib/libcrypt/crypt-md5.c:[...]> This algorithm is still the default on FreeBSD 8. (Blowfish is available -- > but has it been tuned for slowness either? I have not checked.) The purpose > of these functions is to be slow, but the above has not been slow for years. > Hence this patch:[...] This is wrong approach. It should be done using PKCS#5v2 just like geli(8) does it. It even calculates number of iterations so the operation completes in reasonable amount of time on your machine (eg. 1 second). It also uses HMAC/SHA512. On some recent CPUs (amd64) it should be possible for 2^20 iterations to complete in reasonable amount of time. Even strong passwords have no more than five bits of entropy per character (probably much less if it is something possible to remember), so to brute-force one character you need 2^5 interations, which means that strong eight characters password needs 2^40 iterations for full brute-force. Adding 2^20 iterations of PKCS#5v2 makes it 2^60, which is not bad. Of course if we assume that 2^20 of PKCS#5v2 takes one second, then it will take ~34865 years to fully brute-force it on one machine. Although you can safely assume that if you really have something to hide, an attacker will be able to use 100.000 nodes botnet, which leaves you with only ~127 days to change your password:) Remember that this is login password we are talking about, not password used for encryption, so all you want to protect it against is theft of /etc/master.passwd. <advert> All in all static passwords are for the weak that's why we (Wheel Systems) believe in easy to use one-time passwords:) </advert> -- Pawel Jakub Dawidek http://www.wheel.pl pjd@FreeBSD.org http://www.FreeBSD.org FreeBSD committer Am I Evil? Yes, I Am! -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 187 bytes Desc: not available Url : http://lists.freebsd.org/pipermail/freebsd-security/attachments/20100129/a65c32c4/attachment.pgp