Identify password generation algorithm - Reverse Engineering Stack Exchange most recent 30 from reverseengineering.stackexchange.com 2019-12-13T23:34:38Z https://reverseengineering.stackexchange.com/feeds/question/16509 https://creativecommons.org/licenses/by-sa/4.0/rdf https://reverseengineering.stackexchange.com/q/16509 4 Identify password generation algorithm Neilana https://reverseengineering.stackexchange.com/users/21815 2017-10-08T11:11:38Z 2017-10-09T10:54:39Z <p>I'm a newbie who just started own way through reverse engineering so I apologize if my question is not appropriate. Currently I'm going through different Crackme puzzles and now I'm stuck. I've spend a couple of days trying to solve it but I can't. </p> <p>We enter a login and a password. Then we apply <em>algorithm #1</em> on login. And <em>algorithm #2</em> on password. In both cases we get a number as a result. And if the two numbers are equal, then the password is correct. I'm trying to find a way to generate a correct password for any given login.</p> <p>I've figured out both algorithms with IDA and wrote a program in C++ to test my solutions. </p> <h3>Algorithm For Login</h3> <p>Login should be at least 4 chars.</p> <pre><code>login = "Vasya_Pupkin" </code></pre> <p>1) From login we get two first chars ("Va") and two last ("in") and write its ASCII-code into hex number:</p> <pre><code>V = 0x56, a = 0x61, i = 0x69, n = 0x6e hexVain = 0x5661696e </code></pre> <p>2) We go through the login string and add up all ASCII-codes:</p> <pre><code>for (int j = 0; j &lt; login.length(); j++) asciiSum += login[j]; </code></pre> <p>For <code>Vasya_Pupkin</code> we get <code>asciiSum = 0x4da</code></p> <p>3) We xor those values with some number 0xfec0135a:</p> <pre><code>hexVain ^ asciiSum ^ 0xfec0135a magicValueLogin = 0xa8a17eee </code></pre> <h3>Algorithm For Password</h3> <p>Password should be at least 12 chars and should contain only'a'-'f', 'A'-'F', '0'-'9'. We enter password as string. Then we divide the length by 2.</p> <pre><code>password_str = "011c0d0f090e00"; n = password_str.length() / 2; // n = 7 </code></pre> <p>Then we convert string representation to hex and aplly this algorithm: We go through every byte from left to right and calculate new magic value.</p> <pre><code>password = 0x011c0d0f090e00; magicValuePass = 0xadde; for (int i = 0; i &lt; n; i++) { // we count bytes from left to right passByte = getByte(password, i); // multiplication by 32 is left shift for 5 bytes magicValuePass = passByte ^ (32 * magicValuePass + 1) ^ 0xdeadbeef; } </code></pre> <p>The output of this function is following:</p> <pre><code>Byte: 01 Magic: deb8052f Byte: 1c Magic: 9ad1b12 Byte: 0d Magic: eb0edca3 Byte: 0f Magic: bf762a81 Byte: 09 Magic: 3068eec7 Byte: 0e Magic: d3b06600 Byte: 00 Magic: a8a17eee </code></pre> <p>In the end we get <code>magicValuePass = 0xa8a17eee</code> which is the same value we get for login so the password is correct.</p> <h3>What I've Tried</h3> <p>I thought about reversing <code>magicValuePass</code> generation but but came to conclusion that's a bad idea. </p> https://reverseengineering.stackexchange.com/questions/16509/-/16513#16513 2 Answer by sudhackar for Identify password generation algorithm sudhackar https://reverseengineering.stackexchange.com/users/14622 2017-10-09T08:20:53Z 2017-10-09T08:20:53Z <p>As you have just started into RE, try looking into SAT solvers. <a href="https://github.com/Z3Prover/z3" rel="nofollow noreferrer">Z3</a> is a great tool that will help you in such simple tasks with APIs in all major languages. Here is a solution I tried in python.</p> <pre><code>password = BitVec("password",64) magicValuePass = BitVec("magicValuePass",64) s = Solver() idx = 7 magicValuePass = (((password&amp;(0xff&lt;&lt;(8*idx)))&gt;&gt;(8*idx))^ (32 * 0xadde + 1) ^ 0xdeadbeef) &amp; 0xffffffff for i in xrange(6,0,-1): magicValuePass = (((password&amp;(0xff&lt;&lt;(8*i)))&gt;&gt;(8*i))^ (32 * magicValuePass + 1) ^ 0xdeadbeef) &amp; 0xffffffff s.add(magicValuePass == magicValueLogin) if s.check() == sat: print hex(s.model()[password].as_long()) </code></pre> <p>First declare <code>password</code> to be a 64 bit variable. Then iterate byte by byte calculating the intermediate values and finally set the <code>magicValuePass</code> equal to <code>magicValueLogin</code>. If a solution exists to such conditions Z3 will run for some time and give the solution which is printed. <a href="https://gist.github.com/sudhackar/ccd20ec5b412f8aae4fba651be8e8429" rel="nofollow noreferrer">Full script here</a> which on running gives such output</p> <pre><code>$python test-so.py Vasya_Pupkin 0x11c0d0f090e0000$ python test-so.py ABCD 0x1171f0902111a00 \$ python test-so.py DEfg 0x1150f070b1a0500 </code></pre> https://reverseengineering.stackexchange.com/questions/16509/-/16516#16516 1 Answer by yaspr for Identify password generation algorithm yaspr https://reverseengineering.stackexchange.com/users/4437 2017-10-09T10:54:39Z 2017-10-09T10:54:39Z <p>How about generating many logins from a password?</p> <p>To start, algorithm 1 looks like the weakest link. Algorithm 2 is a one directional hash function and there's no way you can extract the characters by only knowing the magic number and the password bias. It involves some advanced math work and time. I explain the process of breaking Algorithm 2 in the second section.</p> <p>Suppose :</p> <p><strong>log_bias = 0xfec0135a</strong></p> <p><strong>pass_bias = 0xdeadbeef</strong></p> <p>Let's look at algorithm 1:</p> <p>1) <strong>log_chunk = 0xlogin(0)login(1)login(n - 2)login(n - 1);</strong></p> <p>2) <strong>log_checksum = Sum(login, 0, n);</strong> </p> <p>3) <strong>log_magicnumber = log_chunk ^ log_checksum ^ log_bias;</strong></p> <p>This algorithm shows two potential weaknesses. One, if you take the magic number and xor it with the <strong>log_bias</strong> constant you obtain : <strong>log_chunk ^ log_checksum</strong>. Two, <strong>log_chunk</strong> is a concatenation in hex of the first two characters and the last two characters and it provides a frame for the login; therefore, we can generate our own characters and give that variable a value. </p> <p>After getting rid of the bias and choosing a value for the chunk, we can obtain a value for <strong>log_checksum</strong>.</p> <p><strong>log_checksum = (log_magicnumber ^ log_bias) ^ log_chunk;</strong></p> <p>What's left to do is to find a sequence of numbers representing characters which sum is the checksum.</p> <p>How? </p> <p>Well, if you look at the <a href="http://www.asciichars.com/" rel="nofollow noreferrer">ASCII</a> table you'll see that printable characters go from 33 to 126. If we generate a random value <strong>b</strong> between 33 and 126 and subtract it from the checksum we obtain a character value <strong>b</strong> and reduce the checksum value by <strong>b</strong> : <strong>log_checksum -= b</strong>. Repeat this operation until checksum value goes below 126 and only store characters which <strong>diff = (log_checksum - b)</strong> is greater or equal than 33. This way, all characters will be printable. </p> <p>After filling the middle of the login string it can be represented as follows :</p> <p><strong>login</strong> = <strong>A B</strong> <strong>b</strong>0 <strong>b</strong>1 <strong>b</strong>2 ... <strong>b</strong>j <strong>C D</strong></p> <p>with A, B, C, D the characters we chose, and <strong>b</strong>i the characters generated from the checksum. </p> <p>This reverse engineering approach is a cheap smart hack that targets the weakest hash function of the process and it will definitely work and save you time. From one password you'll obtain multiple logins : this is called a hash collision. </p> <p>Here's an example output of this code:</p> <pre><code>Login: Vasya_Pupkin Password: 011c0d0f090e00 Login check : 0xa8a17eee Password check : 0xa8a17eee Check success :) Valid login for pass_magicnumber 0xa8a17eee: Va[JiIUpHBI]in, length = 14 Valid login for pass_magicnumber 0xa8a17eee: VaU[^OnyD^fin, length = 13 Valid login for pass_magicnumber 0xa8a17eee: Va|IkHyi2in, length = 13 Valid login for pass_magicnumber 0xa8a17eee: VaTziSl^oK&gt;in, length = 13 Valid login for pass_magicnumber 0xa8a17eee: VawNzAOGWktin, length = 13 Valid login for pass_magicnumber 0xa8a17eee: Vaeh]bmzbwin, length = 12 Valid login for pass_magicnumber 0xa8a17eee: VaugjXcNEvBin, length = 13 Valid login for pass_magicnumber 0xa8a17eee: VaJoMwQ{p[8in, length = 13 Valid login for pass_magicnumber 0xa8a17eee: VatBZwR`R|Ein, length = 13 Valid login for pass_magicnumber 0xa8a17eee: VaIy[lkZQbKin, length = 13 </code></pre> <p>All the listed valid logins will work for the password "011c0d0f090e00". If you alter the password a bit, say : "011c0d0f090efe", here's what you get : </p> <pre><code>Login: VaNpNa^Twin Password: 011c0d0f090efe Login check : 0xa8a17e10 Password check : 0xa8a17e10 Check success :) Valid login for pass_magicnumber 0xa8a17e10: VaeOTUkOG8in, length = 12 Valid login for pass_magicnumber 0xa8a17e10: VaUDFEzBx&gt;in, length = 12 Valid login for pass_magicnumber 0xa8a17e10: Va|gktoein, length = 10 Valid login for pass_magicnumber 0xa8a17e10: VaaPRTogiin, length = 11 Valid login for pass_magicnumber 0xa8a17e10: VaFEzBpktin, length = 11 Valid login for pass_magicnumber 0xa8a17e10: VafCCzmQrin, length = 11 Valid login for pass_magicnumber 0xa8a17e10: VaFDWMHSNC&lt;in, length = 13 Valid login for pass_magicnumber 0xa8a17e10: VaSvoIgR\in, length = 11 Valid login for pass_magicnumber 0xa8a17e10: Va[{eLdl?in, length = 11 Valid login for pass_magicnumber 0xa8a17e10: VaPaoDPXFDin, length = 12 </code></pre> <hr> <p>Now, let's talk about generating passwords from a login magic number. You'll have to attack this function :</p> <p><strong>log_magicnumber = b ^ ((log_magicnumber &lt;&lt; 5) + 1) ^ pass_bias</strong></p> <p>If you look closely, you'll see that current <strong>log_magicnumber</strong> is computed using the previous <strong>log_magicnumber</strong> value transformed and mixed up with an unknown byte value and a known bias. Iteratively, it looks like this:</p> <p><strong>log_magicnumber(i) = b ^ ((log_magicnumber(i - 1) &lt;&lt; 5) + 1) ^ pass_bias</strong></p> <p>If we xor the <strong>pass_magicnumber</strong> and the <strong>pass_bias</strong> we're left with :</p> <p><strong>b ^ ((log_magicnumber &lt;&lt; 5) + 1)</strong></p> <p>After generating all possible values of <strong>b</strong> (<em>0-9</em> and <em>a-f</em>, 16 possibilities total) and deriving the corresponding value of <strong>log_magicnumber</strong> for each possible value of <strong>b</strong>, we apply the same step on these magic number values to obtain another value &amp; we go on 8 times (the password string being a 64 bit value = 8 bytes with a minimum length of 6 bytes). We discard the two left-most bytes if set to zero and pack all the bytes into a password string; we then verify with the password magic number algorithm if the password's magic number matches the login's. </p> <p>This approach amounts to creating an 8 stage tree where each node has 16 children. This means that we'll have to generate 16 to the power of 8 characters : 16^8 = (2^4)^8 = 2^32 = 4.294.967.296 characters (4GB) and combine them in strings of 6 to 8 characters with each string being checked for validation. It was fun to code :) </p>