Date: Mon, 17 Jun 2013 23:20:23 +0100 From: Rafael Waldo Delgado Doblas <lord.rafa@...il.com> To: john-dev@...ts.openwall.com Subject: Re: Parallella: scrypt Hello, I was using the reference code to make my own fmt file because it was the easier one to understand. Should I use other?. My apologies because I coundn't speak to much, I was finishing my project. BTW, I'm using a personal github repo to store my code, should I move to other?. Best regards, Rafa. 2013/6/17 <jfoug@....net> > ---- Solar Designer <solar@...nwall.com> wrote: > > On Wed, Jun 12, 2013 at 02:27:42PM +0200, magnum wrote: > > > We actually have Colin's reference implementation in bleeding-jumbo, > added by Dhiru for the "scrypt" format (with format_name django-scrypt). > And Jim optimized it to 2x. I haven't looked at it but maybe it should be > renamed to django-scrypt (and your revisions merged)? > > > > Ouch! Dhiru - you should start announcing your additions to the tree in > > here. At least new formats. Somehow I missed this one in git. > > > > It's a pity that Jim spent time on this. The reference implementation, > > by definition, was not optimized. Colin, the original author, also > > provides two other implementations, which are much faster (more than 2x > > over reference). There's no point in us optimizing the reference > > implementation in any way - we simply should drop and replace it. > > Little time spent on this (but I do have little 'real' free time, so point > taken). It was trivial changes. 90% of the improvement was removal of > ridiculous memsets/memcpys, etc in a couple of areas in the deep inner > loop. But I did also put in quite a bit of time studying the algo, and > then digging in, and spending some time studying salsa, and starting to get > personal insights on how to do salsa 'right', and where the SIMD is within > that algo (there is a lot of opportunity) . I have yet to start putting > any of that knowledge into code, however. But yes, you are very right. > There probably is an easy 10x gain to be had by attacking the problem from > the performance direction instead of the current extreme readability > direction of the current reference code. But I did want to look at it. > > Just because something is reference code, does not mean it can not be > highly optimal. Take for instance when I re-wrote the reference code for > DCC2 (mscash2) found on the wiki, when I was looking to first port DCC2 to > SIMD and needed to get it figured out. Before I started this, PBKDF2 was a > total mystery to me, I had no clue at all. I found the original ref code > authored by S3nf, to be pretty opaque, with the algorithm hard to see, due > to all of the crypt code being inline within the ref piece. I threw away > all of the MD4/SHA1 stuff, and replaced with simply calls into oSSL. I had > already made some changes in other places, and knew to try to reduce the > amount of times the ipad/opad part of the HMAC being computed from > iteration times to 1 time. And the code itself was greatly reduced > (probably 20% or so line count, compared to original ref piece), AND the > actual logic of the DCC2 was tightly grouped and very easy to follow. > Once I got the code into that state, and could really wrap my brain around > it, it jumped right out at me, that the first 1/2 of each crypt (ipad/opad) > within each HMAC was being done over a constant. It was not only the > ipad/opad 'building' that could be eliminated, but the actual crypt also. > That change itself got put INTO the reference code on the wiki: > http://openwall.info/wiki/john/MSCash2_simple_code since I felt that the > reduction of that part of the crypt did not change the easy of > understanding with the ref code (it did need a comment to explain things a > little). And now, 2 or 3 years later, the logic from that ref code, with > VERY little change is still fully being used as the best code within most > of the JtR formats doing PBKDF2 logic, and I cringe when I see oSSL's > PBKDF2 code being used. > > But yes, you are certainly write about Colin's code, here. And it does > seem to be his habit in his ref pieces, that he almost seems to purposely > write code that is designed to run slowly. I wish he would not 'try' to do > things that way, but I have seen this on several things over the last > decade or so. It is too bad, because often that horribly sub-optimal > method gets into projection, and sometimes into HIGHLY used production > code, because a product needs some functionality, but the production team > has no one that is a crypto guru and there is no time for a team member to > study up to become one. They simply get tasked with 'add feature X' to the > product, find some code that they CAN read, and that 'works', and put it > in. Now, it DOES work, gets the job done, tests well, and ends up being > released. A prime example of this was php for at least a couple of years, > and it's MD5. Solar, I think even you felt the wrath of that one, when you > wrote PhPass and had logic in there (along with comments), that if run on > php prior to version XYZ, use the $P9$ (I think) which significantly > reduced the key stretching, because the the logic in those early versions > was SOOO dismal. Now I am not 100% sure that this was due to the php team > using some gawd awful slow ref piece implementation, but I would be willing > to bet a burger and a coke, that it was such a situation. > > [/rant] > > WOW, looking back on what I wrote, I am REALLY sorry for that strange off > the wall rant. I guess I should try to get more sleep, but I had to send > it, after spending he time to write it. All I really meant to say was > > "Solar, not much time was wasted optimizing that code, possibly an hour or > so. But I did spend some time 'learning' about the what/how of scrypt, so > that later I can help when we write it properly for our needs" > > But things went their own way, within my taxed brain. Guess I felt like > sharing a little of the insanity this morning, LOL. > > Jim. > Content of type "text/html" skipped
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.