<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Panggi Libersa J.A on Medium]]></title>
        <description><![CDATA[Stories by Panggi Libersa J.A on Medium]]></description>
        <link>https://medium.com/@panggi?source=rss-1f10b6cc9b68------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*7zPCEy51Bo0SAFTw0ysVkA.jpeg</url>
            <title>Stories by Panggi Libersa J.A on Medium</title>
            <link>https://medium.com/@panggi?source=rss-1f10b6cc9b68------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 20:48:16 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@panggi/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Password Cracking Basics: Exhaustive Search vs Time-memory Tradeoff]]></title>
            <link>https://medium.com/prismapp/password-cracking-basics-exhaustive-search-vs-time-memory-tradeoff-93d1b6132508?source=rss-1f10b6cc9b68------2</link>
            <guid isPermaLink="false">https://medium.com/p/93d1b6132508</guid>
            <category><![CDATA[passwords]]></category>
            <category><![CDATA[security]]></category>
            <dc:creator><![CDATA[Panggi Libersa J.A]]></dc:creator>
            <pubDate>Mon, 14 Nov 2016 08:53:18 GMT</pubDate>
            <atom:updated>2016-11-14T08:53:18.635Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I6AQkyjIW2xq6SkrIJ-28Q.jpeg" /></figure><p>In this article i try to explain how password-cracking works in two different basic ways.</p><h3><strong>Limitations</strong>:</h3><ul><li>Password algorithm to test: <a href="https://en.wikipedia.org/wiki/MD5">MD5</a></li><li>Two password-cracking algorithms to compare: <a href="https://en.wikipedia.org/wiki/Brute-force_search">Exhaustive Search</a> and <a href="https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff">Time-memory Tradeoff</a>.</li><li>This tutorial will use <a href="http://www.ruby-lang.org/">Ruby programming language</a> to make it easy to understand.</li><li>Password combination: numeric from 1–15,000,000.</li><li>No concurrency or parallelism only serial programming.</li></ul><h3><strong>Introduction</strong></h3><p>Password storing generally works like this:</p><p>Let say you register to a website using username: “<em>myusername</em>” and password: “<em>qwerty</em>”, it’s going to look like this in in their database:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7dae4e1bf34b61720346ce8a3b4a9a82/href">https://medium.com/media/7dae4e1bf34b61720346ce8a3b4a9a82/href</a></iframe><p>So, what happens right there? your password is being transformed to one-way hash form, in this case using <em>MD5 algorithm</em> so that in case of there is a system breach and the database is being stolen, the thief will not get the correct plain text.</p><p>What does a one-way hash algorithm do? let me give you a few examples:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2b403b808ca03e8e8102eec1edbb4ceb/href">https://medium.com/media/2b403b808ca03e8e8102eec1edbb4ceb/href</a></iframe><p>From the examples above, we can see that:</p><blockquote>Different length of plain texts produce the same length of hashed text. That is how one-way hash algorithm works, after the plain text is hashed, there is no mathematical way to reverse it to the origin plain text form.</blockquote><p>How is this algorithm can be implemented in password storing mechanism? let see another example:</p><p>Stored credentials:</p><ul><li>username: “<em>myusername</em>”</li><li>password: “<em>qwerty</em>”</li></ul><p>Database record:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7dae4e1bf34b61720346ce8a3b4a9a82/href">https://medium.com/media/7dae4e1bf34b61720346ce8a3b4a9a82/href</a></iframe><p>Let say you forgot the password and login using:</p><ul><li>username: “<em>myusername</em>”</li><li>password: “<em>qwerty1234</em>”</li></ul><p>The flow will be like this:</p><ul><li>Look at the “<em>users</em>” table where username equals to “<em>myusername</em>”</li><li>If there is a record with that username, hash the password using MD5 function, in this case <em>md5(“qwerty1234”) = “ec4e2d27630b3859bda056931ae79fbf”</em></li><li>Match the record with the generated hash <em>“ec4e2d27630b3859bda056931ae79fbf” == “d8578edf8458ce06fbc5bb76a58c5ca4”</em> and the result is <strong><em>not matched</em></strong>.</li><li>Because of the generated hash and stored hash is not matched, the <strong>permission is not granted</strong> and vice versa.</li></ul><p>Feel secure already by using non-reverseable algorithm to secure you password? wait a minute, let me show you how to crack it using lookup techniques.</p><p><strong>What is lookup technique?</strong> in finding plain text of a hashed text all you have to do is :</p><blockquote><em>generating the hashed text from a known plain text and compare the generated hashed text with the target hashed text, if the hashed text matched then we know the origin plain text of it.</em></blockquote><h3>Password-Cracking</h3><h4>Exhaustive Search</h4><p>This is a brute force way that is basically trying all the combinations to find the correct plain text from hash text.</p><p><strong>Algorithm:</strong></p><ul><li>Given the hash “eccbc87e4b5ce2fe28308fd9f2a7baf3”</li><li>Do a loop from first character, in this case “1” to infinite and stop until the plain text is found.</li></ul><blockquote><strong>1st iteration </strong>= md5(1) = “c4ca4238a0b923820dcc509a6f75849b” == “eccbc87e4b5ce2fe28308fd9f2a7baf3” ? not matched</blockquote><blockquote><strong>2nd iteration</strong> = md5(2) = “c81e728d9d4c2f636f067f89cc14862c” == “eccbc87e4b5ce2fe28308fd9f2a7baf3” ? not matched</blockquote><blockquote><strong>3rd iteration</strong> = md5(3) = “eccbc87e4b5ce2fe28308fd9f2a7baf3” == “eccbc87e4b5ce2fe28308fd9f2a7baf3” ? <strong><em>matched</em></strong></blockquote><blockquote><strong>The plain text of “eccbc87e4b5ce2fe28308fd9f2a7baf3” is “3”</strong></blockquote><p>Let’s implement them in Ruby:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ae21e887650324ec87ea145a24897a92/href">https://medium.com/media/ae21e887650324ec87ea145a24897a92/href</a></iframe><p><strong>Run the script</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ea2691e9f960d88e3d8c93ef2e9e715d/href">https://medium.com/media/ea2691e9f960d88e3d8c93ef2e9e715d/href</a></iframe><p>So, that’s it we cracked the hashed text in <strong>0.008171 second!</strong></p><p>Let’s try again with larger number such as “10000000”</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/09316cb6311ad602a45accd8b436c7ce/href">https://medium.com/media/09316cb6311ad602a45accd8b436c7ce/href</a></iframe><p>Cracked in <strong>14.8 seconds</strong> just by <strong>using interpreted language with no optimization like concurrency and parallelism!</strong></p><p>What is the drawback of using this method? <strong>in each iteration we need to do calculation and matching procedure and this is not efficient</strong>. That’s why we will tweak the lookup a bit by using the technique called “Time-memory tradeoff”.</p><h4>Time-memory tradeoff</h4><p>“Time-memory tradeoff” or “Space-time tradeoff” in this case is basically by <strong>using pre-calculated lookup table so we don’t need to do calculation and just searching when doing password cracking.</strong></p><p>There is a great implementation of this method called “<a href="http://project-rainbowcrack.com/">RainbowCrack</a>” that is using lookup table called “<a href="http://project-rainbowcrack.com/table.htm">Rainbow Tables</a>”. In this article we will create lookup table that is loosely inspired by how rainbow tables work.</p><p>Lets jump in to the algorithm:</p><p><strong>Preprocessing</strong></p><ul><li>Set the range for combination generation. e.g (1..10,000,000)</li><li>Create all the hash possibilities and store it with the plain text in a file with this structure:</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/83e9eeefe567f63f8e87e43e544f78c2/href">https://medium.com/media/83e9eeefe567f63f8e87e43e544f78c2/href</a></iframe><ul><li>Slice the cipher to 8 characters and sort them by cipher:</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/53e254fd17c2d7e1bf2a1d9e756a1fd9/href">https://medium.com/media/53e254fd17c2d7e1bf2a1d9e756a1fd9/href</a></iframe><p><strong>Plain text searching process:</strong></p><ul><li>Load the sorted table to the memory and structure them in key-value type.</li></ul><p><em>{“0cc175b9” =&gt; “1”, “4a8a08f0” =&gt; “3”, “92eb5ffe” =&gt; “2”}</em></p><ul><li>Slice the target hash to 8 characters (eg: “<em>4a8a08f09d37b73795649038408b5f33</em>” become “<em>4a8a08f0</em>”).</li><li>Search “<em>4a8a08f0</em>” in the memory.</li><li>If the record is found, calculate the md5 of the value (eg: md5(3))</li><li>If the calculated hash is matched with the target hash, the plain text is found</li><li>If the calculated hash is not matched with the target hash, continue the searching.</li></ul><p>Now let see the code:</p><p>The first one is the code to generate the table, simply run the code using <em>ruby generate_table.rb</em> and it will generate the table in <em>tables</em> directory.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/64d5fcdc9b255ba9d68eb19c73bdcf0b/href">https://medium.com/media/64d5fcdc9b255ba9d68eb19c73bdcf0b/href</a></iframe><p>After the table is generated, let’s run the password-cracker</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8ffc4a5dbc9c16e2605f36883099931f/href">https://medium.com/media/8ffc4a5dbc9c16e2605f36883099931f/href</a></iframe><p>Let see how it performs:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/008c462a7454298b14ce91a2989e07a4/href">https://medium.com/media/008c462a7454298b14ce91a2989e07a4/href</a></iframe><p>In <strong>5.5 seconds</strong> it cracked the password, faster than the exhautive search one that cracked it in<strong> 14.8 seconds</strong>.</p><p>The drawback of using Time-memory tradeoff is that <strong>the table generation takes time and for this implementation it needs to load the table to memory which takes a lot of time as well</strong>, but once it’s loaded it can search for multiple hashed text until you tipe “stop”.</p><h4>Performance Comparison</h4><p>Time needed to lookup the plain text</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/776/1*biqh6zJvGkjQiDAST6WaIw.png" /></figure><p>Steps required to lookup the plain text</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/773/1*8Dvbuw5hhselmEx6kLMLMw.png" /></figure><h3>Key Takeaways</h3><ol><li>Don’t use MD5, use stronger algorithm such as <a href="https://en.wikipedia.org/wiki/Bcrypt">Bcrypt</a> instead.</li><li>If you still want to use MD5, modify the flow such as by using <a href="https://en.wikipedia.org/wiki/Salt_(cryptography)">salt</a>.</li><li>Don’t use simple password that is easy to break.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=93d1b6132508" width="1" height="1" alt=""><hr><p><a href="https://medium.com/prismapp/password-cracking-basics-exhaustive-search-vs-time-memory-tradeoff-93d1b6132508">Password Cracking Basics: Exhaustive Search vs Time-memory Tradeoff</a> was originally published in <a href="https://medium.com/prismapp">prismapp</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>