* FreeSec DES-based crypt(3) @ 2011-05-02 13:43 Solar Designer 2011-05-02 13:49 ` Rich Felker 0 siblings, 1 reply; 5+ messages in thread From: Solar Designer @ 2011-05-02 13:43 UTC (permalink / raw) To: musl Rich, all - musl uses a DES-based crypt(3) implementation called FreeSec - the same one that *BSD's use. Unfortunately, its handling of invalid salt strings (with characters other than from the defined base-64 alphabet) differs from UFC-crypt's (which is standard in glibc) to an extent far greater than desired (yes, some deviations from UFC-crypt are in fact desired, in my opinion). Also, this may have security implications (yes, *BSD's are sort of affected) where lots of different invalid salts are treated as just one. This may affect e.g. some web apps that use PHP's crypt() improperly (their fault, but still). Thus, I propose that you replace the code in musl with my revision of it, which has the above issues corrected: http://cvsweb.openwall.com/cgi/cvsweb.cgi/Owl/packages/glibc/ The files are crypt_freesec.c and crypt_freesec.h. These are also used in PHP 5.3.x, so they receive a lot of testing. Another issue is that somehow the speed of your FreeSec code in musl is extremely poor - it runs about 50 times slower than expected (e.g., than it does in glibc on Owl). This is as tested with "john --test --format=crypt" with JtR 1.7.7 on x86_64. I suggest that you run this test too, both before and after you replace the FreeSec code. Alexander ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: FreeSec DES-based crypt(3) 2011-05-02 13:43 FreeSec DES-based crypt(3) Solar Designer @ 2011-05-02 13:49 ` Rich Felker 2011-05-02 18:03 ` Solar Designer 0 siblings, 1 reply; 5+ messages in thread From: Rich Felker @ 2011-05-02 13:49 UTC (permalink / raw) To: musl On Mon, May 02, 2011 at 05:43:33PM +0400, Solar Designer wrote: > Another issue is that somehow the speed of your FreeSec code in musl is > extremely poor - it runs about 50 times slower than expected (e.g., than > it does in glibc on Owl). This is as tested with "john --test > --format=crypt" with JtR 1.7.7 on x86_64. I suggest that you run this > test too, both before and after you replace the FreeSec code. You are right, and the reason, as suspected, is that the state is reinitialized on each call to crypt (crypt is just a wrapper for crypt_r with state on the stack). I tried eliminating the des_init function and instead just using memcpy from a static const initial_state object, but as this structure is very large, it increased the object size by ~35k. Using a non-const static object would be even worse, as it would increase the non-sharable data size of any process by this amount. I could consider using malloc to obtain a permanent des state, allocated and initialized on first use, with fallback to the stack if malloc fails. But I'm wondering if it's really desirable for crypt to be fast anyway. Surely JtR wants a fast crypt, but my impression was always that slow crypt was a cheap way to get some added defense against brute force login attempts and such... Thoughts? Rich P.S. crypt is in no way integrated with other parts of libc, so linking with -lfastcrypt (separate library) is a potentially viable option for situations where you want a fast one. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: FreeSec DES-based crypt(3) 2011-05-02 13:49 ` Rich Felker @ 2011-05-02 18:03 ` Solar Designer 2011-05-02 19:01 ` Rich Felker 0 siblings, 1 reply; 5+ messages in thread From: Solar Designer @ 2011-05-02 18:03 UTC (permalink / raw) To: musl On Mon, May 02, 2011 at 09:49:52AM -0400, Rich Felker wrote: > I could consider using malloc to obtain > a permanent des state, allocated and initialized on first use, with > fallback to the stack if malloc fails. This makes sense. You might be over-estimating the cost of non-const static storage, though. It will only consume address space, not actual memory, until a process actually invokes crypt(3) for a DES-based hash, in which case the cost will be the same as above. > But I'm wondering if it's > really desirable for crypt to be fast anyway. Surely JtR wants a fast > crypt, but my impression was always that slow crypt was a cheap way to > get some added defense against brute force login attempts and such... There's a difference between inherently slow crypt and merely a slow implementation, and remote attacks are better dealt with in a different way, in my opinion. I don't want to discuss another bikeshed, so I'd rather not go into detail. JtR doesn't actually care much - it has its own optimized DES code (it'd care about SHA-crypt's speed, because it doesn't support that natively yet), but I just thought that you'd want musl not to be 50x slower than glibc at this. > P.S. crypt is in no way integrated with other parts of libc, so > linking with -lfastcrypt (separate library) is a potentially viable > option for situations where you want a fast one. I think you'd want the default to be fast. The approach with malloc sounds fine to me - that way, you initially preserve the address space as well. Thanks, Alexander ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: FreeSec DES-based crypt(3) 2011-05-02 18:03 ` Solar Designer @ 2011-05-02 19:01 ` Rich Felker 2011-05-23 12:50 ` Solar Designer 0 siblings, 1 reply; 5+ messages in thread From: Rich Felker @ 2011-05-02 19:01 UTC (permalink / raw) To: musl On Mon, May 02, 2011 at 10:03:36PM +0400, Solar Designer wrote: > On Mon, May 02, 2011 at 09:49:52AM -0400, Rich Felker wrote: > > I could consider using malloc to obtain > > a permanent des state, allocated and initialized on first use, with > > fallback to the stack if malloc fails. > > This makes sense. > > You might be over-estimating the cost of non-const static storage, > though. It will only consume address space, not actual memory, until a > process actually invokes crypt(3) for a DES-based hash, in which case > the cost will be the same as above. Well actually it's a little bit more complicated than that. What happens is that it can fragment the .data segment. For instance if all the .data being written to in most programs was previously in a single page, but the 35k des state got assigned an address between .data symbols which are commonly used, then with the des state, a minimal program would now take an extra dirty page. In the long term, I plan to isolate the modules which have significant amounts of unlikely-to-be-used static state together in the linking order to avoid this type of problem. There still are a couple issues with the malloc approach. One is that it does use additional memory. Using the stack, the memory is already reserved as commit charge (Linux reserves at least 128k commit charge for stack to each process, in my experience) and will be reused by other function calls immediately. Using malloc, the 35k is permanently reserved for DES use only. The other issue, which I don't care about but some people may, is that valgrind will show this as a memory leak. > way, in my opinion. I don't want to discuss another bikeshed, so I'd > rather not go into detail. Don't worry, I don't consider this a bikeshed. You're an expert on crypto and anti-bloat is my specialty and a major defining aspect of musl, so in a way these topics are closer to the nuclear reactor than the bikeshed. > yet), but I just thought that you'd want musl not to be 50x slower than > glibc at this. I would, but I want to balance it with other considerations and achieve all goals at the same time. :) I wonder... is there any way to cut down on the size of this data without affecting (or perhaps even improving) the performance of the code? Then making the data static const would be reasonable. In my experience giant tables suggest 1980s/early-90s style optimization that's often counterproductive today... Rich ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: FreeSec DES-based crypt(3) 2011-05-02 19:01 ` Rich Felker @ 2011-05-23 12:50 ` Solar Designer 0 siblings, 0 replies; 5+ messages in thread From: Solar Designer @ 2011-05-23 12:50 UTC (permalink / raw) To: musl Rich, I am sorry for not continuing this discussion for so long. On Mon, May 02, 2011 at 03:01:35PM -0400, Rich Felker wrote: > I wonder... is there any way to cut down on the size of this data > without affecting (or perhaps even improving) the performance of the > code? Yes, Eric Young's fcrypt() in OpenSSL uses 2 KB tables. However, it does not readily implement the extended BSDI-style hashes, and you would not be able to add them easily (they use 24-bit salts, whereas fcrypt's 2 KB is possible due to some clever bit rotates to apply the usual 12-bit salts only). Also, there may be licensing issues. The next step is 4 KB, and it lets you do 24-bit salts. This is what JtR uses when it somehow does not use a bitslice implementation (which it normally does) and when 128 KB tables turn out to be slower. I don't mind licensing this code under LGPL or whatever for use in musl. However, there's no crypt(3) interface, and some parts needed for it are not implemented (e.g., instead of doing DES final permutation on computed hashes, JtR's loader undoes it on hashes that it loads for cracking). Overall, you'd spend/waste lots of time on this until you get clean, portable, and reliable code with functionality that is the same as what the FreeSec code currently has. I briefly thought of this before I integrated FreeSec into the glibc package on Owl, but decided that I had better uses for my time. Of course, 35 KB is more of an issue for musl than it is for glibc... I vaguely recall that it was 20 KB, though (16 KB plus 4 KB). Oh, the 2 KB and 4 KB figures above include only the main tables (S-P or S-P-E). There are some additional ones for key setup. I think that in fcrypt() those are tiny, but in JtR they're large (optimized for speed only, not size). So you'd need to implement smaller key setup as well (or take it from elsewhere). It's not hard to do, but it's extra work. Maybe it'd be simpler to re-work FreeSec to make it use smaller tables. I hope this helps. Alexander ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2011-05-23 12:50 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-05-02 13:43 FreeSec DES-based crypt(3) Solar Designer 2011-05-02 13:49 ` Rich Felker 2011-05-02 18:03 ` Solar Designer 2011-05-02 19:01 ` Rich Felker 2011-05-23 12:50 ` Solar Designer
Code repositories for project(s) associated with this public inbox https://git.vuxu.org/mirror/musl/ This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).