Home People Publications Talks Projects Products Events Courses Theses

Mortemale: the cracking society

(C) 2011 Luca Mella, Svetlozar Orlovski, Federico Santandrea

Table of contents
  1. Idea
  2. Comparison of possible approaches
  3. Analysis of system openness
  4. Model
  5. Technological background
  6. Engineering problems
  7. Implementation and encountered issues
  8. Source code
  9. Binaries
  10. Conclusions

1. Idea
Our idea is to build a society of computational agents that collaborate towards the purpose of cracking password hashes by means of a dictionary-based attack.
By sharing work between multiple agents, one is able to parallelize the massive computational burden associated with this kind of calculation, thus speeding up the whole process. Another possible application is to theorically enable less powerful devices (i.e. mobile phones) to ask the society for an answer that they couldn't produce in an acceptably short time using their own computational power alone. The key here is that splitting the job requires a negligible effort compared to the magnitude of the job itself.

2. Comparison of possible approaches

[distribuited data vs. distributed computing]
At a first glance there seems to be an obvious solution to the problem: that is, for each job (submitted hash) equally divide resources (dictionaries) between agents and let them calculate the contents therein using the appropriate hash function: the first one to find the collision would inform the society and the job would be considered complete. We call this the "distributed computing" approach.
A more thorough investigation of this approach shows that it is rather unelegant and expensive: dictionary data doesn't really change (it merely proliferates) therefore recomputing that huge amount of hashes for every job is silly at the least.
A better approach would be to have agents compute hashes of their share of resources all the time and cache the results in a database. The society can then be considered a distributed (and maybe replicated) database of precomputed dictionary hashes for certain algorithms. Search is quicker and more failure tolerant than using a compact, huger database.
This is a classic example of a time-space tradeoff. Unnecessary computation is avoided and functionality is preserved.
However, in some cases an hybrid approach could be needed, for example when cracking salted hashes. For those cases a possible approach is to merge distributed computing and distribuited data, because these calculations aren't possible by using precalculated tables only.

3. Analysis of system openness
As this is a research project, a proof-of-concept design to be built upon and extended, it's best to leave the system open. The system shows a medium degree of openness: agent behaviour is not defined a priori but is also quite predictable (being based on the technologies outlined in section 5).
In short, the system is open as in number and fine behaviour of the components but it is not as open as to necessitate higher level programming techniques such as reflection and run-time service discovery.

[fault tolerance]
A downside of the
distribuited data approach is that agents are not equal anymore as they have different knowledge bases, and it is not immediate to know what knowledge is lost upon an agent's death.
Replication is therefore imperative in order to statistically lessen the chance of something relevant be lost. Towards this goal, upon a dictionary request we will deliver the one that has been delivered the least. With this approach there is a good chance that dictionaries are uniformly distributed and replicated between agents, granting us a good level of fault tolerance. Adopting this policy also helps in keeping the society simple: a more complex way to tackle the issue would be to use non-anonymous agents with sessions, but this would introduce a whole lot of other problems (such as: when should an agent be considered "dead"? How to redistribute dictionaries upon an agent's death? Should dictionaries still be pulled by the agents?).

[extensibility and heterogeneity]
System's extensibility is a feature that will be basilar for system's evolution in time. A wise approach is to keep concerns separated, for example we think that Mortemale society should only provide a way to coordinate agents and share knowledge, consequentially it should not be involved during the implementation of further extensions, in fact, extensions, are merely a concern of agents behaviour, structure and smartness.
According to this approach, Mortemale Society works similar a real world society, where society results are more efficient and effective the more skilled and educated are the individuals who are part of it.
Of course, agents have no structural constraints too, a part using provided adapters to interact with Mortemale society.

Security problems might be serious in this kind of systems, due to society's open nature remain impossible to preventively mitigate all possible malicious behaviours, in fact, in order to enforce openness, component behaviour is not standard and it might be defined out of our control.
However, a good way to reduce security problems might be realized exploiting interceptor pattern, in detail we think at the deploying of a society's monitor software directly into the mortemale; this piece of software should be able to intercept request like in/rd/out, understand if the operation is potentially dangerous or malicious, neutralize that operation and maybe block further attemps from the sender.
Of course the pratical realization of this kind of feature should be developed as a separated project due to his complexity.

4. Model
Many Crackers connect to a central Society and get dictionaries as often as they wish. They then compute and store the hashes. An User may query the Society for the plaintext corresponding to an hash, and the society will make this query available to the Crackers. If a Cracker knows the solution, it will notify the Society and the User will be able to obtain it. Additionally, one or more Miner agents are always busy searching for new dictionaries (using whatever method they want to, including web spiders and user interface entry) and inserting them into the Society.
Note that a client application can implement more than one role, so it is possible to have a PC client application which contains both a Cracker and an User (allowing people to contribute to the system while asking questions in return) or an User only (to be used on less mighty devices such as cellphones).

use cases
logical architecture
tuples structure
miner agent interaction
user agent interaction
cracker agent/dictionary interaction
cracker agent/task interaction

mortemale society's behaviour

john, a simple cracker agent

manual miner

desktop user agent
mobile user agent

5. Technological background
The sample Society will be implemented as a persistent TuCSoN tuple center, complete with a ReSpecT specification. All information interchange is managed by TuCSoN agents, which are used as adapters by the society agents and provide the shared syntax and semantics. Sample agents are implemented in Java, using the TuCSoN API to create the adapters. A sample mobile client is implemented on the Android platform using the specific TuCSoN library.

6. Engineering problems
[dictionary avaibility]
An interesting aspect that has been analyzed is how to get dictionaries from the outside world. Currently the society does nothing more than store an URL where the wordlist is located. This choice has been made to keep the proof of concept simple, but there is great possibility for expansion. What would happen if the URL is not valid anymore? This problem could be easily solved using existing peer-to-peer technology. For instance, Cracker could have on-board BitTorrent clients and Miners would be able to pubblish a ".torrent" file as dictionary location: that file contains several information about files to download and trackers who know where find seeders.
With these informations Cracker, that act as a bitTorrent peer, could download and then seed dictionaries, contributing to them avaibility.

[society fault tolerance]
Previously we had discussed about fault tolerance of society as his ability to continue working efficiently, even after a premature agent's death.
Now we're extending fault tolerance concept with the ability to survive to a society node death, in other words, how we grant that society will work even after a server crash? We could imagine several approach to solve this problem, but in this paper we will focus on two possible solutions: mirroring and TuCSoN organization exploiting.

One interesting approach to solve this important issue is to keep a mirror society in another safe place and exploit some key technologies to hide the society's switching to agents. A possible implementation of this approach could be realized with 3 components: a probe, a switcher and a synchronizer. Each component has a specific responsability, in detail, probe will check the avaibility of original node, synchronizer will keep in sync society data files (eg. persistence data in TuCSoN), switcher will have to start a new Mortemale society node and make it reachable with the same reference that agents are using for trying to access to the original node. Pragmatically we think to exploit several technologies to enforce high fault tolerance levels, below a short component description and model's pictures:

. Probe, could be realized as a simple java program (*.jar file) that simply use TuCSoN API for ask something to Society, and check if responds.
. Synchronizer, could be done as a script (or better a wrapper) that exploit rsync's features for keeping all data updated with a low network overhead.
. Switcher, maybe more complicated than previous ones, it might be realized with a little script that start a new Mortemale node and with a dynamicDNS client, or also a simple a chunk of code that deregister an A-DNS record and register a new one.

All of these components can be managed by a software (lifeguard) that encapsule the chosen policy, and manage them properly.

lifeguard structure
lifeguard interactions

[TuCSoN organization]
Otherwise, we may exploit the concept of TuCSoN organization through TuCSoN contexts. In detail we could imagine mortemale society as a part of an organization ( Mortemale Inc.) and consequentially agents will not want to interact longer with the society, but rather want to interact with the organization.
Introducing this new abstraction layer permit to agent to be able to ask to Mortemale Inc. wich is his own context, in other words agents will ask to organization in wich tuple center (Mortemale Society) they can operate. So, it become meaningfull to think to mantain a service who monitor several mortemale society and retrive to agents who want to partecipate to mortemale the right context.

7. Implementation and encountered issues

ReSpecT specifications]
Several difficulties has been encountered during the implementation of the ReSpecT
specifications for enforcing society policies and behaviour.
In particular the absence of primitives like in_all , rd_all , out_all has been problematic because no one in the project team have previous experience with logic programming paradigm (in detail Prolog language).

8. Source code

svn co https://mortemale.svn.sourceforge.net/svnroot/mortemale mortemale

9. Binaries


10. Conclusions
During the project's development we had the possibility to touch with our hand the potentialities offered by a data-oriented coordination model like that one implemented in TuCSoN, where all components are glued through a media that does not simply coordinate them, but instead add new features and capabilities to the whole system and permit to enforce a strong separation of concern, thing that is always appreciated in software engineering.
The consequence of this data-oriented approach to distribuited system development stimolate the projecting of smarter systems, in fact, due to strong separation of concern, component's developers are focused on less responsabilities and this naturally stimulates the development of smarter agents, without any architectural constraint forced by the coordination model.  Also, interaction's projecting results more effective, stimulates to care better of coordination problems and make easier to understand the system's states.
Mortemale is actually a demostration of all considerations done above, due to media features we were able to develop an interesting solution for an hard problem, everything keeping simple and clear software components.
Finally, we want to focus on a non trivial aspect of the data-oriented model: this media can also be viewed as a repository of knowledge. In fact, in our sample project, we exploit this feature of the media in order to collect and mantain knowledge about all discovered dictionaries in all over the internet.
So, again, not only a coordination glue, but also a place where agents store knowledge, communicate and collaborate.

[future development]
We think that Mortemale Society is only a piece of something greater. Imagine that several society works together for improve the cracking efficacy, in detail imagine that a task could be propagated though known societies, in this scenario every cracker could be activated and pushed to collaborate. Pragmatically, with a little abstraction upgrade, we could say that a Society become an User of another society. This particular feature of Mortemale Society come naturally due to the characteristics of the system itself, in fact openness and heterogeneity make this new dimension really easy to implement.
Another future development will be the migration from TuCSoN 1.4.5 to 1.9.2, it is a necessary step for leaving alpha stage and developing a beta release.