ianmjones

A little while ago I mentioned that I had initially built the user authentication in CaseDetective so that it used the user’s FogBugz website to do an automated physical login, and then parsed the resulting page for specific variable names that can only be there if the user had logged in successfully. This was a bad idea, and not even my preferred method, but I’d done this way to avoid asking Fog Creek about the encryption they use for user passwords stored in the database. Anyway, once I wised up and asked Michael Pryor if he’d let me in on the secret, he of course told me that it was the UNIX Crypt algorithm (funnily enough, I’ve recently found a discussion forum post where he had already mentioned it, but it was after I released Beta 1).

I was over the moon when Michael told me it was UNIX Crypt because I figured there’d be thousands of ready made modules that I could choose from that would give me instant access to the one-way crypt I needed, it’s so old, so ingrained in the UNIX world that it was surely going to be a breeze.

So I checked out my Einhugur plugins only to find no simple “UNIX Crypt” functions. Not worry, there are a tonne of different algorithms in the e-CryptIt module, it’s probably just down to me not knowing what the underlying cryptographic algorithm is, so I search the net…

I spent a few hours searching the net, eventually finding out that UNIX Crypt is a derivative of the Data Encryption Standard (DES). I learnt a lot about encryption in these few hours, including that UNIX Crypt is pretty weak, but also that it’s pretty easy to password check with because the “salt” is embedded in the encrypted string as the first two characters. I also leant that in a lot of systems the DES algorithm has been superseded by using Blowfish or Twofish.

Back to my plugins … nope, nothing about DES, not a sausage. Bugger! So I sent an email off to the Einhugur list asking if I was right, maybe I’d missed something, but alas, DES and UNIX Crypt are not supported by e-CryptIt, and no-one knew of another plugin that would help. Double bugger! At least e-CryptIt has Blowfish and Twofish, but that doesn’t help me just now as I need the DES version.

There are very few modules out there (”out there” being the internet) that do UNIX Crypt, and most are for Windows and would require that I bundle another dll with my application, which I really didn’t want to do, I already bundle the eSellerate dll and didn’t want to have to bundle any more.

Even if I did buy a dll (most of these dll files require payment) and distribute it for Windows, it would still have left me with having to find a solution on Mac OS X.

I played around with RealBasic Declares on Mac OS X as it comes with a “unistd” library that I found I could potentially call to do a crypt. But I had very sporadic results, and many crashes, and relying on the placement of a library outside of my control gave me the hebees (you’re supposed to be able to just use the sort name for the library without it’s full path, but that never worked for me, I had to use the full path to get anywhere at all).

What next, write my own UNIX Crypt module from scratch, in RealBasic? Surely not, that’s got to be painful!

Well, I had no choice, I either wrote a module to do UNIX Crypt from within my RealBasic application where I had full control and no cross-platform woes, compile up some freely available C code for both Windows and Mac OS X, keep searching fruitlessly for an existing robust cross-platform solution (that isn’t there), or forget the whole thing and go back to looking at building Integrated Windows authentication into my FogBugz web logon code (shivers with dread).

During my research on the web I found various bits of C code that did DES and UNIX Crypt that had BSD or other unencumbered licenses, so I had at least some code I could look at for inspiration. Now, I’m no C coder, I can read it a bit as long as it doesn’t get too hairy, and I’ve even written a few modules and applications for clients where we needed to wrap third-party libraries with C code, and then in some cases wrapped this with Informix 4GL code. I’ve had some great success with that kind of thing. But I’m telling you now, people that devise encryption algorithms are seriously deranged, how on Earth they come up with this stuff beats me, and how some of these C developers got to the place where they do certain things they do I don’t know. It’s just plain scary looking at encryption code.

I’d found via Wikipedia.org a great DES Algorithm Illustrated page (WARNING: if you go to that site, don’t bother looking at other parts unless you’re in the privacy of your own home as your boss may not appreciate the scantily clad ladies) that explained bit by bit (literally) how the DES algorithm worked with a known input and output. Without that site I’d have been right royally stumped, it allowed me to build a stand alone project in which I could test my UNIXCrypt module with a known input and output not only to the entire algorithm, but to each little segment of the calculations.

It took a few days, and a lot of hair loss, but eventually I had straight DES working fine, I could perfectly replicate the inputs and outputs from DES Algorithm Illustrated. Woohoo!

All I had to do then was implement UNIX Crypt. Sounds easy don’t it? I thought so too. The problem is that UNIX Crypt doesn’t use straight DES, oh no, that would be too easy, it has to be mucked about a bit first!

UNIX Crypt sets the DES key in just the same manner as normal DES does using the string (password) passed in. So far so good. Then it runs DES encrypt 25 times using that key, but starting off with a message containing just zeros. This also sounds pretty straight forward doesn’t it? Well, on each of those 25 runs of DES crypt, at each point that the “E-Box” is expanded (you’ll have to go look at that DES Algorithm Illustrated site to see what that means) the resulting bits (which by the way have already been mucked about enough thank you very much) are mucked about again depending on some XOr criteria derived from the two “salt” characters.

Luckily I had various bits of C code to check out, but they don’t really explain anything, and try as I might I just couldn’t get the bloomin’ thing working.

I tried for two weeks to get UNIX Crypt working, it was so frustrating. I had DES working, I knew it, so why could I not get these seemingly small changes to adhere to the UNIX Crypt algorithm working?! I think I must have lost at least half my hair over those two weeks (that’s my story and I’m sticking to it, I haven’t been losing my hair at all before that, not one ).

Finally I sent out a plea to the RealBasic Network Users Group (NUG) for anyone who knows any way of getting UNIX Crypt working reliably cross platform from RealBasic. I was prepared to throw all my work away if anyone came up with anything good. No one had suggestion that would work for me, it seems no one on the group had needed to do it before cross platform, although there was a Mac OS X solution for encrypting passwords.

Eventually a guy called Mark Nutter found some Java code I hadn’t seen before that did UNIX Crypt, I looked at it and found that it very closely matched the C code I’d used as a template for my own development. I followed it through and compared to my own RealBasic code, just like I had the C code, but alas could not find anything that looked wrong.

When I reported back to the NUG that I still couldn’t find the problem Mark then offered to take a look at my code to see if anything jumped out, so I took him up on his offer and sent him my test project. Later that day he wrote back, unfortunately not having been able to find the problem. Here’s a quote from his email:

… I’m checking your RB code against that, and
everything seems to check out, except that the results
aren’t matching. But encryption algorithms are so
twisted! My brain hurts after only a couple hours, I
can imagine you’ve been going bonkers.

At this point I’m fairly stumped also.

I wrote back thanking him for trying and telling him not to try looking at it any more, I didn’t want to be held responsible for his decline into madness! I’d just have to try and step through the code bit by bit and see if I can find the place where it went astray.

When Mark wrote back to say good luck he casually mentioned that I should try and compile up the C code I’d used as a template and output to a buffer every now and then and compare with my RealBasic code. Doh! Why the hell didn’t think of that sooner, I had code that I knew should work, tried and tested, but just in another language.

So I jumped into XCode created a new project and copied in the C code I’d been using and set about creating a command line app that would simply print out the bit strings at various points. I started off by making it simply do the UNIX crypt to make sure it was doing the right thing, outputting the input and output strings. It worked.

Then I decided I’d start off slowly, I just added one intermediate output of a “bit string”, the bits as accepted by the setkey function which is called right at the beginning before doing the real DES stuff. Then did the same in my RealBasic code. Ran the two of them, and guess what, I already had a miss-match! Bugger, bugger bugger! If I had a problem this early on in the process, it was going to take me bloody ages to find and fix all the other errors.

When I looked closely at the two bit strings, that should have been the same, but weren’t, I noticed that my code was creating a string very similar, in fact it was almost identical except for an extra “0″ at the beginning of the string, and then again before the next recognizable pattern of “1″s and “0″s. Damn, my code was passing in 8bits per character rather than the 7bits per character for the key that the C code was using. Checked my code, sure enough, there it was, an extra “0″ in my bit mask when converting the ascii characters to binary!

Oh well, delete one “O”, recompile and run again to find the next error. Except there wasn’t an error, my test project only bloody went and spat out the correct encrypted string! Woohoo! Do a little jigg!

It only took me a couple of minute to import my UNIXCrypt module into my CaseDetective project and hook it up to get it working, finally I could authenticate a user’s FogBugz login id and password against the database, cross platform and without any dependance on external modules or applications. Phew, I can’t tell you how much of a relief that was, I was so happy.

So, after all that hard work, fretting and nearly going insane, I’m going to do one last insane thing, I’m releasing my UNIXCrypt RealBasic module as a free download. You can grab it from my IMiJ Software website, it’s in the “Free Stuff” section.

You can download or check out the UNIXCrypt REALbasic module and test project that I created from the rbunixcrypt Google Code project. It’s under a MIT license, so you can do pretty much anything you like with it.

You can use the UNIXCrypt RealBasic module to simulate UNIX Crypt by simply calling “UNIXCrypt” with a string and two character salt.

Thank you to everyone who helped or tried to help me get this done, hope someone finds it useful.