AES-NI is definitely too specific to AES, not reasonably reusable for DES. Yes, we have achieved a speed for DES comparable to that of AES with AES-NI.

We're actually considering building a password hashing method on top of something like this, where bitslice DES has the advantage of being scalable to arbitrary SIMD vector widths and not requiring specialized instructions for efficient implementation. DES is also FPGA-friendly (more so than AES), and we have a project to implement password hashing for authentication servers equipped with FPGA boards:

http://www.openwall.com/lists/crypt-dev/2011/04/05/2 - project rationale
http://www.openwall.com/lists/crypt-dev/2011/05/09/1 - alternative approach

We're also considering Eksblowfish-like constructions, though - such as to make use of Xilinx Block RAMs (and thus require attackers to use more resources too).

BTW, not sure if I am speaking to the right Matt, but of the two SHA-crypt flavors the SHA-512 based one actually has a practical advantage over the SHA-256 one: more complete use of 64-bit CPUs in servers. So I think Dragonfly BSD's choice was a mistake. GPU implementations for both are being worked on, and the difference should be seen.

6-to-4 is large enough that you can't realistically find a perfect solution (the absolute smallest gate count) on present computers and given present knowledge. You can do it for 5-to-1, though. Also, generic Boolean expression minimization tools produce relatively poor results for DES S-boxes; specialized algorithms are the way to go. IIRC, I tried Espresso - http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer - in late 1990s. It couldn't even get close to Matthew Kwan's results from 1998, where he used a specialized algorithm.

Here are some specific performance numbers for DES-based crypt(3) on GPUs (for comparison, recall that we're reporting over 20M c/s on a CPU):

oclhashcat-plus is reported to achieve 55M on ATI HD 5970, only 25M on NVidia GTX570 at 1600 MHz core clock, 310M on 8x ATI HD 6970, 181M on 7x NVidia GTX580 (1594 MHz). The numbers for oclhashcat-lite are very similar (57M, 26M, 297M, 181M, respectively). These are off the hashcat website. This does not use our new S-boxes yet (I expect that future versions of *hashcat tools will).

Notice how the number for high-end NVidia is on par with that for our CPU, and for ATI is less than 3x better. Of course, GPUs do have an advantage, but it still does make sense to use CPUs as well, which a typical organization has more of and doesn't need to spend extra time to deploy, install drivers for, etc.

Now, our new S-boxes and other optimizations will provide better performance. Per discussions with a tripcode cracker author, I expect all the way up to 400M c/s on ATI HD 5970, which is close to its theoretical peak speed (approx. 80% of it per some estimates). This is a 20x improvement over our figure for the Core i7 CPU, which is significant. (There's a little room for improvement on the CPU as well, though - specifically, if we pre-generate or runtime-patch the code for each salt as opposed to using pointers at runtime like we do now. This kind of optimization is assumed in the 400M figure for the GPU. So with both having the optimization, the GPU's advantage will be less than 20x.)

Curiously, 400M c/s for 25 iterations of DES will mean that a single ATI HD 5970 with proper code will be able to crack 56-bit DES keys in just 42 days on average.

So, yes, GPUs have an advantage, and we have contributed to that as well.

Actually, a lot of people care about CPUs. I spoke to someone from a penetration testing company the other day. They run a lot of password hash cracking. And they have 10x more CPUs (used for other purposes as well) than GPUs (bought specifically for password cracking). Given that performance of DES-based crypt(3) on GPUs is by far not as impressive as it is for other hash types, they typically test this sort of hashes on CPUs and not GPUs.

That said, yes, when we worked on the S-boxes, we thought of GPUs as well. One of our target sets of "logic gates" is specifically that of high-end AMD/ATI GPUs (it also works well for Cell, PowerPC/AltiVec, and AMD XOP, but we deliberately excluded gates/instructions that are present on only some of these four platforms). The author of one of the GPU-based cracking tools (for tripcodes) reported a 20% improvement on Radeon HD 5970 due to our new S-boxes. Andrey Belenko of ElcomSoft wrote in a tweet that "Effect for GPUs might be well above 20%, actually."

We were not the first to generate and try to optimize Boolean expressions for the S-boxes. Other researchers worked on this before, starting 1997 when Eli Biham wrote his classic paper on bitslice DES. 17% is our improvement compared to those previous results. To me, it is impressive that after 14 years and numerous attempts by others, including successful ones, it was still possible to improve on the previous best results by as much as 17% at once. My gut feeling is that further improvements, while definitely possible, will be more limited. But the again, some people I spoke to had thought that our 17% was not possible.

More technical detail on the new S-boxes:
http://lists.randombit.net/pipermail/cryptography/2011-June/000968.html

And on how they were generated:
http://www.openwall.com/lists/john-users/2011/06/24/4

Formal press release:
http://www.openwall.com/press/20110622

reddit:
http://www.reddit.com/r/crypto/comments/idwi8/17_smaller_des_sbox_circuits_found_20m/

Dark Reading story:
http://www.darkreading.com/authentication/167901072/security/vulnerabilities/231000218/john-the-ripper-gets-a-facelift.html

ElcomSoft has already said that they will reuse our S-box expressions in their products.

No, a lot of people read it like that, and this word play was deliberate - it actually helps the marketing by attracting extra blog posts ("hey, I found something stupidly named" and the like). ;-) However, the official spelling is "phpass", with no caps, where "pass" is for password or pass (successful authentication).

I previously made a similar spelling joke in naming popa3d, a POP3 server. Russians get this one.

As to the bug, as other people noted the typical alternatives to not using phpass and crypt_blowfish would have been far worse. This is not an excuse. I do feel embarrassed for the bug. But I am also being realistic such that I and others learn the right lessons from this.

In practice, most uses of phpass that I am aware of don't actually use crypt_blowfish (and thus are not affected) - those choose to use phpass' "portable hashes" instead. For passwords without 8-bit chars, those are weaker than crypt_blowfish, but they do avoid the bug. (And with 8-bit chars it is not obvious which are weaker, even despite of the bug.)

(Apparently, I forgot to submit this comment the first time around. To avoid re-typing, I ptrace(2)-dumped my Firefox process memory to a file, then grepped it for "deliberate" - and here the comment is. I am used to doing things like that, e.g. when investigating abusive processes on compromised shared hosting accounts of customers. Maybe someone will find this tip useful or curious.)

I also briefly thought of where we would be if Ulrich accepted bcrypt into glibc. I have several points to make:

1. It is likely that adjusting the crypt_blowfish code to glibc conventions would happen to remove the bug - just like it happened with Perl's Crypt::Eksblowfish (it's based on crypt_blowfish, but the bug is gone). Yes, this does mean that those coding conventions are maybe superior, although it is easier for them to be such when only a more limited number of platforms is considered. There is a lesson for me to learn here.

2. bcrypt is not only crypt_blowfish. glibc could also use OpenBSD's code (lacking this bug) if it looked more suitable by whatever criteria.

3. I just took another look at Ulrich's SHA-crypt.txt, sha256crypt.c, and sha512crypt.c. I don't see any 8-bit characters in passwords in the test vectors. Unless I have missed those, it looks like a bug in SHA-crypt causing similar misbehavior would go unnoticed. No, I do not find it likely that such a bug exists there, but then I also did not find it likely for crypt_blowfish. Anyone wants to test and confirm that there's no 8-bitness bug in SHA-crypt? Please do. But what to test Ulrich's SHA-crypt against? Does Solaris use the same code or a reimplementation? (I don't know.) If it's the same code, and no reimplementation exists, then you'd have to try causing collisions or something like that, perhaps with low "rounds" (to make this test reasonably quick). Or create that reimplementation for testing. (BTW, I did the latter in phpass, for testing the correctness of my implementation of its "portable hashes".)

4. SHA-crypt is reasonably good, especially for acceptance due to its use of NIST-approved SHA-2 family functions. However, it does have its drawbacks. bcrypt turned out to be GPU-unfriendly, whereas we should see reasonably efficient implementations of SHA-crypt for GPUs soon (this is being worked on and I see no major obstacles). In neither case a GPU is usable for password hashing on an authentication server (there's too little parallelism in one instance of a bcrypt or SHA-crypt hash computation), even if you had a GPU there, so GPU-unfriendliness is an advantage of bcrypt if you compare it against SHA-crypt.

5. Finally, there have been plenty of security bugs in glibc.

Of course. But there are reasons why this didn't happen to a sufficient extent in this case. None of these reasons are valid excuses. There are lessons to learn from this.

There were test vectors, and the implementation behaved exactly like OpenBSD's on those. The code was in John the Ripper, and it was correctly cracking password hashes from OpenBSD. So it felt like the code was working just as it should have, because it actually did (on the tests that were thrown at it). There was no expectation that specifically 8-bit characters would cause any difference.

As to fuzzing vs. OpenBSD's implementation, I wish I did that, and I wish I included 8-bit characters. I felt that JtR essentially was an equivalent of this test, due to people using it to crack password hashes from OpenBSD. The code existed in JtR for 2-3 years before I made it available separately for reuse. Apparently, 8-bit characters in weak passwords (and in wordlists) were just too uncommon for anyone to notice any passwords not getting cracked where they should have been.

We're getting close to an official fix, which includes a quick self-test on every use (not just by "make check"), with both 7- and 8-bit chars: http://www.openwall.com/lists/oss-security/2011/06/21/2

Olaf Kirch's implementation of traceroute, which we use in Owl, does not need a raw socket. It uses Linux 2.4+ features (that is, they've been available in mainstream kernels for a decade) to do exactly what the usual LBNL traceroute did (send UDP packets, detect ICMP errors), only without requiring special privileges. We install it mode 755 and it just works for all users.

I fully agree with you that "anyone can be wrong".

I also agree with your comments on a large percentage of CPU time typically being spent in shared libraries, and I agree that they're normally PIC anyway. So, yes, 6% slowdown on main program code when going PIE does not translate to a 6% slowdown of the entire system. We typically use Owl rebuilds from source as our benchmark, so this is likely what we will use to see the overall effect of going PIE as well (that is, run a second rebuild on a system already rebuilt to use PIE, including gcc, etc.)

Our bzip2 does not use shared libbz2, specifically for the reason you mention. Here's the exact text of the Owl bzip2.spec changelog entry dated Feb 1, 2002: "Package the bzip2 binary that is statically-linked against libbz2 for better performance on register-starved architectures such as the x86." IIRC, we actually ran benchmarks of both kinds of builds of bzip2 at the time. I've just double-checked - the bzip2 binary in Owl 3.0 still uses shared libc only, whereas libbz2 is linked in statically (the version of bzip2 has been updated several times since 2002, of course). :-)

It was nice talking to you. I think you could actually contribute to post-3.0 Owl development if you wanted to (hint). ;-)

Please take a look at our presentation slides, it only takes a few minutes. Then you might have more specific questions on the implementation, which I'd be happy to answer.

http://www.openwall.com/tcb/
http://www.openwall.com/presentations/Owl/mgp00020.html
http://www.openwall.com/presentations/Owl/mgp00021.html
http://www.openwall.com/presentations/Owl/mgp00022.html
http://www.openwall.com/presentations/Owl/mgp00023.html

Please note that what I wrote in my reply to your comment was quite different. I never said anything about your experience. Now that you raised this topic, I can say that you appear to be familiar with Unix security. You simply had not looked at our stuff before you wrote your comment, that's all.

I find your comment re: the cost of PIE interesting, thanks! It leaves many questions, though. 6% on 32-bit x86 is the number I had been aware of before. Your statement that "the affected code was actually running less than 2% of the time" is curious and potentially very useful. However, this, assuming that it's true, does not yield your claimed 0.0012%; it yields 0.12%. Of course, 0.12% may be considered acceptable (far more likely than 6% at least). I am curious about the details of your test; I guess, some systems will actually run "the affected code" 100% of the time - e.g., this happens if I build John the Ripper as PIE and run it for days (which is why I dislike Gentoo building JtR like that, and have to recommend JtR users to make their own builds). ;-) I'd appreciate it if you e-mail me (solar at openwall.com) more details on your test, and we'll discuss from there. We're considering PIE by default for post-3.0 Owl-current (and next release).

Your comments about cron/at are similar to what we thought of when we designed the system. Just like our per-user shadow files, the crontab files are per-user (and they were prior to our changes as well). Our crond does check crontab file ownership, and then it will only run the cron jobs found in the file as the file's owner. Cron and at jobs running as root are supported - of course, as long as the corresponding files are root-owned.