hons.un-excogitate.org/category/research

pilot experiment results

after finishing my initial pilot test (read: Pilot Experiments on Clustered Password Cracking) i compiled a report/assignment/paper for my supervisor, beneath is a copy of the report from the method until the end..

RESEARCH METHOD

Hardware Configuration

Two separate hardware configurations were used for the experiments. Both of these configurations were trying to bring the effect of different hardware to a minimum. The basis of the setup relied on x86 Intel based processors, inter-connected with 100Mbps networking hardware.

The Beowulf configuration used for testing John the Ripper-MPI was comprised of 13 nodes. One of the 13 nodes was used as the head-node and did not perform any of the work, but was required in the configuration as all the program and data files were hosted on this machine.

Beowulf Node Configuration:

Processor Make: Intel Pentium III
Processor Clock Speed: 866MHz
Motherboard:
Memory: 256MB SDRAM
Hard Drive: 20GB IDE
Network: 100Mbps

The head-node was configured with an extra 128MB of memory, providing it with 384MB of SDRAM, and also a faster disk drive .

The nodes were inter-connected with a Baystack 10/100 24 port managed switch.

Combining the processor speed and memory of the 12 compute-nodes resulted in a Beowulf cluster which had approximately 10.4GHz clock speed, and 3GB of memory.

The OpenMosix configuration used for testing Cisilia was comprised of 14 nodes, a head-node, 6 compute-nodes with hard drives and 7 compute-nodes without hard drives. Even though there was a head-node, computational work was still performed on this machine as well.

OpenMosix Node Configuration:

Processor Make: Intel Pentium III
Processor Clock Speed: 733MHz
Motherboard:
Memory: 256MB SDRAM
Hard Drive: 20GB IDE
Network: 100Mbps

The disk-less nodes had the same configuration, just without the 20GB hard drive.

Combining the processor speed and memory of the 14 nodes resulted in an OpenMosix cluster which had approximately 10.3GHz clock speed, and 3.5GB of memory.

Software Configuration

Two different software configurations were used for the experiments. Both of these relied on the use of the Linux operating system, not just because that is what the software was designed on, but also because the separate clustering-systems, Beowulf and OpenMosix, relied on the use of Linux.

The Beowulf clusters operating system was built using the Rocks Cluster distribution (NPACI Rocks, 2004) version 3.1.0 which is based on top of the Red Hat Enterprise Linux 3 Advanced Workstation distribution. The software installation allowed the setup of the head-node, followed by a network boot and auto configuration of the remaining 12 compute-nodes. The kernel version of the system was 2.4.21, compiled for i686.

The research used a modified version of John the Ripper called John the Ripper-MPI (JtR-MPI) (Lim, 2004) and Cisilia to perform its tests because both utilities perform brute-force attacks, both can crack Microsoft Windows LAN Manager or Samba based passwords, and both can perform these attacks using a cluster of computers. One of the differences between the two utilities and their style of breaking passwords is their parallel paradigm. JtR-MPI is designed specifically to use message passing between computers to run in a parallel way. Cisilia uses a different method of parallelisation, it is designed to spawn multiple copies of itself, which when run on a load-balancing cluster will split the load between computers and therefore run in a parallel way.

The version of JtR-MPI used was 1.6.36-mpi which is John the Ripper version 1.6.36 which has been modified to work in a Beowulf environment using MPICH for inter-node communication.

MPICH version 1.2.5.2 was used for both the compilation and the execution of JtR-MPI.

SSH version 3.7.1 was used to start the individual JtR-MPI processes on each of the nodes in the Beowulf cluster.

The OpenMosix clusters operating system was built using CHAOS version 1.2 (FIAT & Gobbledok, 2004) on the compute-nodes, and ClusterKnoppix (Vandersmissen, 2003) version 3.3-2003-11-19 on the head-node. The software installation allowed the setup of the head-node and compute-nodes from live CDs, which meant that the operating-system ran entirely off RAM disks and CD-ROMs. The kernel version of the system was 2.4.22-openmosix-2, compiled for i386.

Cisilia version 0.7.3 was used for the tests on the OpenMosix cluster.

Password samples

To test a common set of passwords required the use of a password format that both Cisilia and JtR-MPI could crack. The only matching password format was Microsoft’s LAN Manager (LANMAN) or Samba based passwords. The algorithm used to create these passwords has been proven to be quite weak, and is only being used for backwards compatibility with older Microsoft operating systems (Shaffer, 2004). LANMAN passwords are created by:

• Converting all alphabetic characters to their uppercase equivalent


• Truncating or padding the password to 14 characters (bytes)


• Splitting the password into two 7 character (byte) halves


• Using each 7 character half as a key to encrypt a known string using the DES encryption algorithm


• The two cipher-texts are then concatenated and stored on file

To test the two cracking utilities the password samples had to represent the broad spectrum of passwords from weak to strong. To create random passwords that represented this spectrum required the use of a method to create and determine a password and its strength.

The method used to create the password samples was taken from a system previously implemented in IBM’s Lotus Notes and Domino (2004) software. Williams’ (2001) article on the algorithms used to determine a passwords quality was used as the guidelines for creating passwords which had a rating from 5 to 14. Some of the factors of the algorithm include the passwords strength, its fallibility to dictionary-attacks and if it contains one or more mixed-case, numeric or punctuation characters. Some example rules for a password of quality eight (8) might include:

• A password that contains at least six (6) characters and includes at least two (2) number, mixed-case or punctuation character


• A password that contains at least seven (7) characters and includes at least one (1) number and one (1) mixed-case character


• A password that contains at least eight (8) characters and does not include words from the dictionary

Tests Performed

The first test was performed by JtR-MPI on the Beowulf cluster. A maximum time was set to 3 days to ensure that the results from all the tests could be compared, and also to ensure that the tests could be finished on time. The results collected from this test included:

• Half the cipher-text password


• Half the plain-text, cracked password


• The username


• A digit representing which half of the password was cracked (a 1 or 2)


• A time in the format D:HH:MM:SS

Following this first test, a second test was performed with the same configuration. This test was used to measure the reliability of the utility.

The third test was performed by Cisilia on the OpenMosix cluster. Similar to the JtR-MPI tests, results which took longer than 3 days were discarded. Cisilia was configured to return results which contained:

• A time in the format HH:MM:SS.SS


• The username


• The plain-text, cracked password

During all the tests, no other processor-intensive tasks were being performed on the nodes. For the full 3 day period the only processes running on the clusters, apart from operating-system tasks, were the cracking utilities.

RESULTS

Initial results from the JtR-MPI tests looked to be very impressive, with the cracking tool reporting 22 cracks within the first hour. In the next two hours of execution, the software successfully performed 8 more cracks. During the next 21 hours a further 4 more hashes were cracked, which meant after the first 24 hours JtR-MPI had broken 34 hashes. After the first day the software slowed down substantially, only cracking a further 4 more hashes in the next 2 days.

At the end of 3 days the utility had cracked 38 hashes.

Number of LM Hashes Cracked vs Time

Problems with Cisilia caused the program to run inconsistently. After decreasing the number of nodes down to 8, the test eventually started correctly. Unfortunately, after 5 hours and 37 minutes, the program stopped working only after having cracked 4 passwords.

A second test on 8 nodes ran for longer, but was manually stopped after having run for 3 days. During this time Cisilia only managed to crack 4 passwords, 2 of which were different from the first test.

Due to instability and inconsistency of Cisilia the results were discarded and a comparison between Cisilia and John the Ripper could not be performed.

Analysis

Analysis of the results from the successful John the Ripper test show that only 12 passwords were cracked in their entirety, meaning that both of the two separate hashes were cracked correctly. A further 27 passwords had their first half correctly cracked, meaning that the first 7 characters of the password were cracked correctly. This left a final 11 passwords which did not have either half cracked.

Of the 12 passwords which were completely cracked, 10 were cracked within the first 3 hours. The final 2 passwords took an additional 37 hours to be cracked. Of the 26 half-passwords which were successfully cracked, 24 were cracked within the first day.

An inspection of the time each password took to crack and its relative strength rating, according to the article by Williams (2001), revealed that in the case of the test, the rating did not have a strong effect on the order and time each password was cracked. An example of this is in the 2nd and 3rd passwords which were cracked, both which were rated quite highly.

Password Strength vs Time to Crack

These results could be explained by the method in which LANMAN passwords are created. By first splitting the password in half, LANMAN passwords are effectively reduced to two passwords, each with a maximum length of 7. After inspecting the 2nd and 3rd passwords it is easy to see that each is made up of two separate, 7 character-long strings, each consisting of only alphabetic characters. Due to the fact that each separate half was easily cracked, it meant that the entire password could be cracked in no time.

The passwords which took longer to crack, even though they had weaker password strength ratings than others, took longer because of their use of non-alphabetic characters such as a “(“ character or “+” character. This is the case in the 2 passwords which took longer than 1 day to crack.

Limitations

The main limitation during this research was due to the instability of Cisilia. Without results from Cisilia, a comparison of two different clustered, password cracking utilities could not be performed. This also hindered the research into the method of parallelisation used by Cisilia to break passwords using multiple computers.

Another limitation to the research was the use of LANMAN passwords instead of a different password encrypting algorithm, such as MD5 or even DES based passwords. The LANMAN password format could explain why so many of the passwords were not cracked. Upon inspection of the log files produced by each node in the cluster, it would appear that the 3 day test should have produced many more positive cracks. Some possible answers to this problem could be that during the creation of the LANMAN passwords, the truncating and padding was done incorrectly, or else the method by which John the Ripper pads and truncates possible passwords was done incorrectly. After inspecting the list of cracked passwords this is confirmed, as 95.35% of the passwords had a length of 7 characters. Of the remaining 11 un-cracked passwords, none were a length of 7 characters.

ASMCrack

ASMCrack - another one of those cracking utilities that slipped through my finger-tips.

<quote>
ASMCrack is a unix password security tool. It checks the password file by trying whether a given word matches an encrypted password that was within the password file. To do so it uses very speed optimized 386 assembly routines, with pentium alignment and command order optimisations. It consists of three program subversions, that use differently sized look-up tables. The speed of those versions depends on the hardware, especially on the RAM speed and the CPU cache's size.
</quote>

What's interesting about this program is it's (dumb/simple/clever) way of working on multiple computers - in fact - the same way that JTR-MPI (a peek inside jtr) works in an MPI environment.

First: Determine an approximate speed rating for each computer u want to use

asmcrack -test

Second: Create a file for each of the computers - and their rating

Computer0 : speed
Computer1 : speed
..
etc

Third: Run the program on each node with it's appropriate node-number

asmcrack -multi:config.file,0

..

Now, even though the author claims it's all optimised and that jazz, it is quite out-dated compared to JTR, so whether or not it would perform up to par is yet to be seen.

pilot experiments on clustered password cracking

Short after igneous was finished i started my pilot test on John the Ripper-MPI (john-1.6.36-mpi) using a precompiled samba password list containing 50 passwords.

These passwords we're meant to contain a nice cross-section of differing password strengths, from weak passwords to strong passwords. For lack of a better system the metric used for password strength was a slightly modified version of that specified here which is targeted towards Lotus Notes/User management or something.

Anyway, the system is humming along great. All 12 compute-nodes running at about 0.99 - 1, after the first day a majority of the passwords were already cracked, approximately. JTR splits LanManager (Samba) passwords in half to crack them, which is fine because the LM passwords are initially split in two before they are encrypted anyway. At the end of about 4-5 days running, the test is close to having checked all passwords up to length 7, comprised of a 69-characterset.

This may sound (or may not sound) impressive in its own right, but because this is almost every-single possible LM password .. it's quite impressive.

A bit of history behind LM hashed-passwords (google will have heaps more information that i can be bothered typing out here) .. LM hashes are the password-type for win9x systems, and for backwards compatibility over networks, they are *also* by default included in winNT+ .. this would be fine, if they were in fact a strong password type.. but they are not.

A LM password is truncated (or padded) to 14 characters, then all the alphabetic characters are converted to upper-case, then the 14 characters are split-in-two, and each half is encrypted seperately. Concatenated back together at the end again. So what we have, is for each password, 2 seperate password hashes of length 7.

Back to the supposed-password-metric. Password 50 was meant to be a fairly strong password (relatively) .. unfortunately both-halves of password50 were cracked in about 3-4minutes.

Reasoning? .. JTR's brute-force attack goes as follows.

Character-length 1, Character-set-size 1
Character-length 1, Character-set-size 2
etc.
(Intersparsed in here are differing locking mechanisms, so for longer passwords they'll lock the first 4 characters and only iterate the rest)

With small password lengths it's very easy to crack passwords. Even when getting to the larger character-sets. The problem with password50 was that it was comprised of nothing BUT characters, which means as soon as the "character-set-size" reached 26 (or thereabouts because password50 did not have one of every alphabetic character) .. this large password could be cracked.
This speed is multiplied by n when n computers are splitting the load.
So by 3-4mins, JTRMPI had reach passwords of length 7, character-set-size about 22-26, and even though the password was 14-characters long, each half was still only 7.

....

So, for all this good-luck, naturally something had to screw up. IE: my comparison with Cisilia (a different clustered password cracking utility).

My plan was to run a live-CD version of OpenMosix (OM) on igneous, then run cisilia on the same password file. Therefore, same hardware, same passwords, different os/parallel-paradigm/cracking-tool. But for the sake of JTR finishing it's job, i had to run the tests in a different lab. A lab with a fairly homogenous hardware configuration .. but still the software did not want to play.
Only once did it want to run with the full amount of nodes available. Other times it crashed. I eventually got it running on a sub-set of the comptuers, only to discover the next day that it had stopped after 5hours after only cracking 4 passwords!

I'm guessing that the system has to be a bit more homogenous for this tool to work, my supervisor is recommending waiting for the semester to end so i can shift into a lab which will allow me greater freedom.

supervisor reviews

last tuesday (the 23rd) we had our first lit-review meeting 1-on-1 with our supervisor, and i've found since then the going has been slow.

Every single paragraph that i write comes out at a crawling pace, i have a feeling my filtering system is getting all messed up and i'm over-concentrating on some details, just sometimes when u need to just write something out but it has to be legit (ie: proven and published somewhere) .. and that is HARD.

For ages i've been a semi-creative writer. One of my best classes in highschool was english lit (yes, not maths) and i've always had a passion for things related to that (i read a lot of fiction, i listen and get emotional with a lot of things like music etc) so to find myself having to conform with this rigid, almost lifeless, writing style is definately getting to me in a way which is completely stressing out.

As dan says, it's only March.. there will be plenty of time to stress later .. but god this is hard.

I can't wait til this phase is over and the gist of this writing-style has gelled a bit.

I can't wait.

getting on 40-50% complete

Felt like i got a lot of work done today, not just in my lit-review (which i did spend heaps of time on) but also in general house-work and cleaning up the backyard etc.

Somehow i managed to not pass out trying to clean up the dog's mess (out the backyard. not inside:P) in the middle of the day, around 40degrees.

Today was hard hard going. Even though i felt i did a lot of work, i have a feeling that because of the heat, and because of how uncomfortable i was feeling all day my standard of work might have been a bit below par. I mean it is difficult to discuss the problems and weaknesses of password systems when sweat is pouring down your face.. i mean the last thing on my mind would've been the consequences of some "evil" attacker gaining access to a computer system because someone had decided to use their pet's name-reversed as a password. ..

Apart from the lit-review, the prospect of my experiments are looking finer and finer by the day.. as mentioned .. JTR has an x86-64 header file (global configuration to setup all the rest of the modules used for algorithms etc) .. initially i was looking at the possibility that i would have to come up with this file myself, in a combination of trial-and-error and seeking out the other header files which were aimed/geared for 64-bit environments. .. ahh thank GOD.. Realistically i think this has cut a HUGE part of my prep for my experiments .. i can't wait to get some opteron time to bench it against itself (x86 compile vs x86-64 compile) ..

The rest of the week is going to be just as hot .. thank god i'll either be a) at uni , or b) at work.

Ooo shocker

Orite, from the last post i've made some progress.

Most of my Sunday was spent finding, printing, reading, reviewing articles and periodicals, i felt like i got a ton of work done which was great.

Came to uni on Monday, and after my CSec class (read: 9pm) my supervisor said that he'll want to see some of my lit-review tomorrow (EEEP) .. so, i had some of my background, and a shitload of notes that i'd taken, but no real-structure.

So from 9.30p until now (1.30a) i hammered out the first draft of some of my lit-review sub-sections. I got a lot of the "password" topic stuff first (policies, weaknesses, why passwords are still used) .. and i'm quite proud of it, unfortunately because i'm so god-damned exhausted, i can't really determine if it's right or not, I guess i'll find out tomorrow when i either a) get my head ripped-off, or b) get a pat on the back..

Anyway, i'll post some of it later, as i'm much to tired to copy + paste it now!

Turns around, starts walking backwards

Hahaha.. naturally from wednesdays meeting and after talking to dan about some stuff i've changed a lot of what i'd started ..

Mostly it's that a lot of my background will be converted (ever so slightly) into my actual lit-review .. the process which i used for the background being more suited to lit-review.. then i'll revise my questions, my abstract, my background, my significance.

And to get myself into the swing of things i consumed 4 articles tonight.. 2 of which were really good (gold-mines if u will) I've written up nice little summaries, taken LOTS of interesting quotes .. hopefully I'll keep on running on this little high because the last fortnight has felt like a bit of a dampener...especially with all the work stuff that's been going (ie: moving, and finishing up some large projects)

I also picked up a copy of mitnick's art of deception, and as soon as i've finished schneier's secrets & lies .. it's onto this book (which craig recommended to the class in csec)

Slow going

The research proposal is coming along.. okay. Come tomorrow morning i'm going to have to start putting my lit-review into the 1st draft, which i'm expecting to be hard-going.. especially with how slow sometimes it feels to make progress .. even just doing the background.. it's not enough to just assume that what you perceive as general knowledge is in fact general knowledge..

I suppose it's the same with everything.. someone who knows about music trying to explain it to someone who knows nothing for example.. it feels like your hitting your head against a well..

but at least my proposal doesn't make me bleed from the head (yet :P) .. most of the background is done.. significance and litreview .. tomorrow shall be your beginnings.

First Background, then Significance

Did approximately 1/3rd of my research proposal background, after that i'll quickly write up the significance.. then it's the fun stuff.. onto the lit review.

For each section i've been writing up a what, why and relevance, as discussed with my supervisor, important topics will be re-iterated all over the place (even though redundancy is meant to be kept to a minimum). So even though they will be briefly discussed in the background (to get all readers to the same level approximately) .. they then will be discussed in much more depth, being affirmed via literature.

Research Proposal

So this weekends goal was to get a chunk out of the preliminary research proposal, unfortunately yesturday i was stuck helping the new boss shift to the new office. Anyway after doing my reading for CompSec i realised none of my lit had been focussed on password policies. So, i searched through proquest, have a stack of links to have a read, and a few books which i'll have to try and grab from uni.

My structure so far goes something like this:
Background
Password Policies
One-Way hashing algorithms
Password cracking tools
Beowulf's and Cluster Hardware
Parallel Algorithm techniques
John the Ripper MPI

Significance
Passwords as a weakpoint
Other methods of authentication
Other methods of testing weak passwords
The significance might not be aimed at individual organisations, but for computer security firms?

MPICH Why Must You Spite Me?

As a form of procrastination whilst waiting for class, I tried to get MPICH (1.2.5.2) running on 2 machines at uni, to no avail. What's funny is when i got MPICH running at home on a pair of machines, the only problem they had was that ssh didn't let them login without passwords, so when i ran any of the test applications it would ask me for passwords.

This time around i'm in the inverse boat, SSH isn't asking for passwords, but MPICH appears to be broken!

Note to self: What happens if i can't even get JtRMPI to work?

[Edit]
Played around with my setup at home (see: forcing SSH to work at Version 1 not Version 2) .. and actually got mpich example programs to work PERFECTLY at home..

Hopefully i'll be able to recreate what i did when i get back to uni.

No Net Leads to Conversations and SRC Dissection

The labs proxy server had a hdd failure yesturday. The poor box was feebly printing out HDD I/O Errors on the console in a vain attempt to warn us that it was about to reach some sort of critical point. That point must have occured around the same time the whole lab had a brief-power out.

Anyway, this left the lab internet-less so my day of planned research and reading was reduced to conversations with pete about AMD64 and JtR. Which led me to another look inside the details of this password cracking tool. (READ ON FOR TECHNICAL SUMMARY)

What i don't know about Mandrake-AMD64
What AMD64 mode does this installation run in? Long 64-bit mode? Long Compatibility mode? Legacy Mode? (i really hope not the latter)

Pete made the observation that OpenOffice(OO) loaded just as quick on his single CPU axp2400 if not quicker, compared to this Dual Opteron 244 (2xOpteron's at 1.8GHz). I was quick to suggest that it's because the installed OO was still the 32-bit version, that is, the packaged OO that came with the MandrakeAMD64 installation files was just the default 32-bit version. So does that also lead on to imply that this installation of Mandrake forces the Opteron to run in Compatibility mode? (ie: 64-bit OS with the ability to run existing 16/32-bit x86 applications.) .. even if OO is running as a 32-bit app, with the extra benefits of a SCSI drive and much faster memory system, it should still run faster on an Opteron than on a vanilla AthlonXP. Is this because the mandrake kernel is still not truly optimised for AMD64? Or are a lot of the core linux libraries still running in 32-bit mode?

I'm wondering what sort of affect this will have on JtR running as a 32-bit compiled binary vs a 64-bit compiled binary? .. Will all the dependant libraries be 64-bit?

Linux password files, MD5 Algorithms

Apart from reading more of Schneier's "Secrets & Lies" did some googling on

• Linux Passwords


• Linux Shadow


• Linux Password Algorithm


• Linux MD5


• Linux Password MD5 Algorithm

And some other searchings using different iterations of the above mentioned terms.

What are the benefits of the Shadow File
Because usernames and uid/gid's are stored within the passwd file it is required to be read by the system. This allows anyone to easily gain access to the hashed passwords stored in the /etc/passwd file. To remedy this the /etc/shadow file is used, which is set to read-only for a few authorised users (usually only root by default).
This means the username's and uid/gid's are still stored in /etc/passwd but the hashed password is stored in a stronger-permissioned file. ie /etc/shadow.
There are more benefits, such as specifying when a password has to be updated and the specified maximum age of a password too.

Benefits of MD5 hashed passwords compared to DES hashed passwords
DES's plaintext has a maximum of 8 characters, MD5 can accept much larger lengths. (In fact, isn't MD5 not limited by length at all, md5sum being able to return a 128-bit hash on any file length input?)

"Foiling the Cracker: A Survey Of, and Improvements to, Password Security" by Daniel V. Klein (1990)
This text was too old to be of any use. The author discusses the potential security benefits of using shadow'd password files instead of shared password files, but then follows on saying that most systems won't upgrade their software.. when in fact most modern unix/linux OS's enable Shadow'd password files by default.

RFC1321 on MD5 Algorithm
Very interesting, the Memo sent out about the new MD5 algorithm, this text document also includes the c code down the bottom of the page, and on initial inspection seems very similar to the MD5 code used by John. (although some changes appear to have been made, are these optimisations for JtR? or for other systems? .. )

RSA Lab's Bulletin "On Recent Results for MD2, MD4 and MD5" by M.J.B. Robshaw (1996)
This mentions that the weakness of the MD5 hashing algorithm isn't so much that collisions are discovered easily, it's more that pseudo-collisions occur. Where these are collisions which happen because of the compression part of the MD5 algorithm as opposed to the actual hashing itself. Dobbertin's article (2 pager) describes the situation used to cause this pseudo-collision.

"Cryptanalysis of MD5 Compress" by Hans Dobbertin (1996)
As mentioned, this outlines the conditions used to force pseudo-collisions by the MD5 hashing algorithm.

Relevant Links