-
What is Time-Memory Trade Off (TMTO)? Realistically, TMTO can be defined as a Trade Off; As an exchange of one thing
for another. Time to Memory Trade Off: The exchange of Time for Memory. In order to reduce the amount of time
to complete a set task, we exchange physical memory. In laymans thoughts, memory is hard drive space. We willingly
trade hard drive space so that a set task can be completed in less time.
Now, we must step back and take a look at what areas TMTO can be applied. TMTO is applied to many places. Take a look at
the area of databases. Databases are a clear example of trading hard drive space for speed. Then we can take it step
further and say that indexing within the are of database is an even better example of TMTO. We can store terabytes of
data within a database, but without the speed improvement of an index, there is very little difference between the
database and just searching flat-files with a grep. A database with an index will allow you to search millions of lines
in very little time because the index uses hard drive space. Which, in essence is a Time-Memory Trade Off. Websites that
are database driven are dynamic and fast. You can load the information into an indexed database and dynamic content can
be loaded almost as fast, if not faster, than static SHTML files.
Now take TMTO and apply it to tasks other than their common uses, like driving applications that record keep or a
website that every aspect can be updated on the fly and loads quickly. Take TMTO an apply it to password cracking.
Password cracking is done a few different ways. Usually, when you want to break a password you must have the
encrypted version and then attempt to break it by finding the key. With passwords a different method of encryption is
often utilized. Hashing algorithms allow passwords to be encrypted in a manner in which they cannot simply be
unlocked with a key, they are a one way algorithms. The password is encrypted and the resulting product cannot be
reversed back to the original key. In order to know the password a user must know the password and encrypt it, then
compare the resulting hash with the original hash. If they match, then you grant access or decrypt the rest of the
information.
With that in mind, how then can TMTO be applied to password cracking? How then, can TMTO be applied specifically
to password cracking where a hashing aglorithm has been used to encrypt to password? Lets start with the most basic
form of cracking a hashed password. Guess. You can guess over and over until you arrive at the correct password.
This is just unfeasible, because imagine how long it would take to break a complex password. You may guess a million
times, but never guess correctly.
The forementioned scenario of guessing was clearly not an efficient manner of cracking passwords. Now as technology
progressed, CPUs quickly began outpacing the typing speeds of humanity. You could type 100 words per minute, and
after an hour have guessed only 6,000 passwords or you could automate the process and allow the CPU to guess for you.
The CPU can automatically generate strings and hash them, and compare the result to the original. This gives you
the ability to automatically guess as fast as the CPU can process. This not only increases your guessing ability
thousand fold, but as CPUs increase in speed and go multi-core your guessing ability increases million fold. Then
add in a parallel clustering mechanism such as MPICH2. This allow you to process guessing across a multi-core CPU,
but even multiple multi-core CPUs and even multiple multi-core CPUs over multiple PCs. If you code an application
that can guess 1,000 strings per minute per CPU, then with a dual-core CPU you can paralellize the application
and it can then theoretically guess 2,000 strings per minute. Now on a quad-core CPU the same application can
throttle through 4,000 strings per minute. And finally, on a 100 node cluster each with dual quad-core (8 Cores) CPUs,
you can process 8,000 strings per minute per node totaling 80,0000 string per minute. Paralellization has allowed
application developers to overcome a massive speed bottleneck. With many cores of a single CPU available for
processing, a developer can push threads over many cores and arrive at the desired result exponentially faster.
After some time, this automated guessing process was dubbed "Bruteforce". Bruteforcing became the latest and the
greatest method of breaking passwords. Huge untertakings went into coding applications to streamline to code and
make bruteforcing applications as fast as possible. This was good, but in reality the keyspace was just too big
and bruteforcing was just too slow. Let me explain by saying that it may only take 30 seconds to break a four
character password, comparitively it may take 30 years to break a 10 character password. Bruteforcing is simply
not fast enough. Even on a clustered environment, with hundreds of nodes - all multi-core - it would take years to
break a 30 character password.
Years go by, multi-core CPUs become mainstream, open source MPI software and paralellization become mainstream,
shared storage mechanisms such as ATA over Ethernet become readily available and kernel integrated. All of the
technology that the 1984 technology gurus dreamed of, are now readily available. Storage capabilities are through
the roof and cheaper than your mom at a brothel. One terabyte hard drives fall from $600 to $500 to $425, and
faster transfer protocols such as SATA are created. Now, one thing that you must realize is the TMTO is not a
new concept at all. TMTO has been around since the 1980's and many of the things we are accomplishing today we
conceptualize decades ago. Why weren't these wonderful concepts of TMTO applied back then? Ironically, the reason
is because of technology. Technology was simply not up to the task of storing terabytes of information for
a reasonable price. Technology was simply not up to speed with the concepts. Even today, technology is not up
to par with my concepts. I want to be able to use a minority report style computer. Completely gesture driven and
just plain bad ass. Using a monitor that looks more like a massive sheet of glass than a monitor. The ability to
visually see the transfer of files, like when Tom Cruise moves video feeds off his assistants PC to his main
PC. Sliding the glass-like storage mechanism into the slot, drag the files over to it, and then insert into
another PC and simply drag off. All the while the files can be seen on the glass-like storage mechanism. Gone are
the days of putting CD into a drive to see what is on it.
Stand still for a moment and reflect on our era. Technology in some respects has greatly matured and is moving
at an ever increasing pace. Hard drive sizes went from 1Gb to 10Gb to 100Gb to 1Tb, and so forth. Now, a few
people have rendered the TMTO concepts of decades past and realized that they are almost fully implementable
in our era.
Now that I've laid a good groundwork, let us get into what TMTO when applied to password cracking really is.
Bruteforcing was the most successful and fastest method of breaking a password. But, for each password the
computation would have to start over. You could spend five years of CPU time breaking a 10 character password,
and then have to start over and spend another five years of CPU time breaking a second 10 character password.
10 years to break two password. The passwords have long expired and have likely been changed by the time you break
them. What a waste of time. If you could break an 8 character password in a few weeks, that would be more
realistic. Now imagine being able to break an 8 character password in under a second. TMTO[dot]ORG can do it.
