Posted July 13, 20169 yr PATCH IS NOT AN ACCEPTABLE SOLUTION. PATCH IS NOT AN ACCEPTABLE SOLUTION. PATCH IS NOT AN ACCEPTABLE SOLUTION. Difficulty : 5/10 (Professional problem to solve)Language : .NETPlatform : WindowsOS Version : AllProtection : Custom VM + some crypto. Description : Learn something new today! If you already know how to deal with simple Virtual Machines, hopefully the crypto will keep you busy for a while.. However, it's designed to be broken, so better get cracking! Goals : Bronze medal: devirtualize the code. To claim the prize, you must provide human-understandable serial checking code that works exactly the same as original. Short tutorial must be written, explaining how you did that. Silver medal: provide a valid serial for your name. Considering the length of serial, I guess you'll just bruteforce it. All is fair in love and reversing... Gold medal: create a keygen that is able to generate valid serial(-s) for any name. Key generation should not take more than a second. Longer tutorial must be written, explaining how protection works and how you defeated it. Sample serials : kao : QQRR9-DL6JFtuts4you : RU7FB-ZLANC Screenshot : Hall of Fame (in chronological order) :Extreme Coders: Bronze medal for devirtualized code; li0nsar3c00l: Bronze medal for devirtualized code + pseudo-tutorial (posted on RTN forum); ---- perhaps you? --- weasel_by_kao.zip Edited July 16, 20169 yr by kao Updated Hall of Fame
July 13, 20169 yr This should be the devirtualized code in graph form. Spoiler Will write a tutorial when fully completed with keygenning.
July 13, 20169 yr Author Well done, even though the code is still a long way from being "suitable for human consumption". Realistically, if you can't understand it, you can't keygen it. P.S. Thanks for using spoiler tags, I really appreciate that! No need to spoil the fun for others...
July 14, 20169 yr Here is the devirtualized code. Keygenning this will be quite a effort. I will give it a try nevertheless. Spoiler using System; using System.Collections; using System.Security.Cryptography; using System.Text; namespace weasel_vm { internal class Program { private byte[] ans; private int[] arr; private BitArray[] bitarr; // The big array private byte[] hardcoded = hardcodedarray.hardcoded; private byte[] hash; private string username = "kao"; private string password = "QQRR9-DL6JF"; public static void Main(string[] args) { Program obj = new Program(); obj.hash = MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(obj.username)); obj.doIt(); obj.check(); Console.ReadKey(true); } private void check() { if (ans[0] == hash[2] && ans[1] == hash[5] && ans[2] == hash[8] && ans[3] == hash[11] && ans[4] == hash[14]) { Console.WriteLine("Success"); return; } Console.WriteLine("Failure"); } private void doIt() { bitarr = new BitArray[3]; bitarr[0] = new BitArray(hardcoded); arr = new int[64]; ans = new byte[5]; bitarr[2] = new BitArray(56); arr[41] = 0; arr[15] = 0; while (arr[15] < password.Length) { arr[8] = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[arr[15]]); if (arr[8] != -1) { arr[1] = 0; while ((long)arr[1] < 5L) { bitarr[2][arr[41]] = ((arr[8] & 1) != 0); arr[41]++; arr[8] = (int)((uint)arr[8] >> 1); arr[1]++; } } arr[15]++; } bitarr[1] = new BitArray(40); arr[61] = 0; arr[55] = 0; arr[24] = 0; while ((long)arr[24] < 40L) { arr[36] = (bitarr[0][arr[61]] ? 1 : 0); arr[61]++; arr[18] = 0; while ((long)arr[18] < 50L) { arr[19] = (bitarr[0][arr[61]] ? 1 : 0); if (arr[19] != 0) { arr[19] = (bitarr[2][arr[18]] ? 1 : 0); arr[36] += arr[19]; } arr[61]++; arr[18]++; } arr[11] = 0; while ((long)arr[11] < 49L) { arr[47] = arr[11] + 1; while ((long)arr[47] < 50L) { arr[19] = (bitarr[0][arr[61]] ? 1 : 0); if (arr[19] != 0) { arr[19] = (bitarr[2][arr[11]] ? 1 : 0); arr[57] = (bitarr[2][arr[47]] ? 1 : 0); arr[57] *= arr[19]; arr[36] += arr[57]; } arr[61]++; arr[47]++; } arr[11]++; } bitarr[1][arr[55]] = ((arr[36] & 1) != 0); arr[55]++; arr[24]++; } bitarr[1].CopyTo(ans, 0); } } } vm.rar Edited July 14, 20169 yr by Extreme Coders Added attachment
July 16, 20169 yr Just wanted to post a quick update: The problem seems to be NP complete and does not look to be keygennable at least not in polynomial time, 1 second is way too unrealistic.Using boolean logic the algorithm can be converted to a sat instance. Attached are two files. A python sat solver + an smt-lib2 representation of the same problem which tries to find the serial for the name "0xec". However for the computational complexity involved this will take a very very large amount of time. As I said NP complete problems can be verified quickly, but finding a solution to them in reasonable time is infeasible. Bruteforce is also not possible as the size of the keyspace is 250 Ofcourse the above are my personal beliefs, and I would be more than happy to be proved wrong. weaselkg.rar
August 16, 20169 yr As promised, here is the write-up, although I was unsuccessful in fully solving this. Nevertheless this was an interesting challenge. Will wait for others to keygen this. https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html
August 16, 20169 yr 3 hours ago, Extreme Coders said: As promised, here is the write-up, although I was unsuccessful in fully solving this. Nevertheless this was an interesting challenge. Will wait for others to keygen this. https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html Wow thank you for this it was a great read
August 16, 20169 yr Author Hey, I appreciate that you looked into it. In all honesty, I slightly rushed the release due to Labyrenth coming up. My reasoning was (probably) flawed: * Similar challenges have been solved with keyspace up to 280. Currently running challenges are targeting keyspace 2144. * Run-of-the-mill SAT solvers are not suitable for solving this kind of problems. To solve them efficiently, special algorithms are required. Yet, I still underestimated the difficulty of solving challenge with a significantly reduced keyspace. I really apologize for that.
January 3, 20178 yr On 16.08.2016 at 11:58 AM, Extreme Coders said: As promised, here is the write-up, although I was unsuccessful in fully solving this. Nevertheless this was an interesting challenge. Will wait for others to keygen this. https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html Hi. I read your blog post. You cannot use CUDA or OpenCL to speed the compute process?
January 3, 20178 yr I don't think brute-forcing is the correct way to solve the problem. The keyspace is just too big. There must be some mathematical approach beyond my limited knowledge.
January 4, 20178 yr 7 hours ago, mrexodia said: Pretty easy, see my solution... Impressive work!!! Why it didn't occur to me ?
June 4, 20187 yr On 6/2/2018 at 6:21 PM, GautamGreat said: No solution far now @kao can you post a solution too? look above 😛 https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html
June 4, 20187 yr 11 minutes ago, MindSystem said: look above 😛 https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html I already read that, that is not a proper solution.
June 15, 20196 yr System of bilinear equations https://en.wikipedia.org/wiki/System_of_bilinear_equations Bilinear form https://en.wikipedia.org/wiki/Bilinear_form Solution Theory for Systems of Bilinear Equations https://arxiv.org/pdf/1303.4988.pdf https://math.stackexchange.com/questions/1894954/finding-a-solution-to-system-of-bilinear-equations Linear + bilinear = value Edited June 16, 20196 yr by CodeExplorer
June 16, 20196 yr https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html On 6/4/2018 at 6:01 PM, GautamGreat said: I already read that, that is not a proper solution. for (int b = 0; b < 49; b++) for (int c = b + 1; c < 50; c++) if (huge[y++]) if (calc[b] & calc[c]) bit = !bit; the expression will be negated only if calc=1 and calc[c]=1 and huge[y++] this is easier in reverse order from the end to the begin: last time checks last two bits: calc[49]&calc[48] Still trying to find solution. Edited June 16, 20196 yr by CodeExplorer
January 20, 20205 yr Phew! It has been close to 4 years and after a lot of wandering here and there I can proudly announce that I'm now able to calculate a valid serial for any name. Here are a couple. kao GCZ4B-QTD22 0xec FZNUL-THK22 Time taken to generate a key can vary from 2-5 minutes and takes about 12 GB of Physical RAM running on a Nvidia Tesla T4 GPU (2560 CUDA cores). Providing more RAM and CUDA cores may further reduce the time but I ran it on Google Colab and that's what they offer. I plan to do a write-up on my blog later but here it is in short. Initially, I felt the only way to solve the system of equations within a feasible time frame is through a quantum computer using something like Grover's search but the quantum computers available for public use (IBM Q Experience) at this time do not have enough qubits. So this approach had to be discarded. On deeper analysis, I found the system of equations is nothing but a system of Multivariate Quadratic (MQ) Polynomials. There's a field of Crypto related to this - Multivariate cryptography. Such cryptosystems are considered hard even for a Quantum Computer to attack let alone a classical machine. Luckily, there's an ongoing challenge based on the exact same idea - Fukuoka MQ challenge. It turns out small MQ systems particularly which are under-determined (more unknowns than equations) are solvable by classical machines within an accepting time frame and people have posted tools/algorithms to solve them. One of them is libFES . There's also a GPU implementation of FES which I have used here. So that's how it went. Thanks @kao for the challenge. Really learned a lot!!! Its a silver medal for now. Considering such systems of equation are solvable, generating a key within 1 sec could also be possible given the MQ challenge site posts that this cryptosystem is based on a signature scheme (Type -IV). Quote Type I: Encryption, m=2n, F=GF(2) Type II: Encryption, m=2n, F=GF(28) Type III: Encryption, m=2n, F=GF(31) Type IV: Signature, n≈1.5m, F=GF(2) Type V: Signature, n≈1.5m, F=GF(28) Type VI: Signature, n≈1.5m, F=GF(31) Once we calculate the private key, generating the signature within 1s should be possible.
January 22, 20205 yr Now it takes about a couple of seconds to generate a password. On the downside occasionally it may fail to generate one. Instructions to compile and run have been provided in the Git repo. Keygen: https://github.com/extremecoders-re/weasel-keygen Colab Notebook: https://colab.research.google.com/drive/1ncoLENvfWLTMF-7hTzWdBOv9ZpBxEKxC Kaggle Notebook: https://www.kaggle.com/extremecoders/weasel-keygen?scriptVersionId=27419227 Edited January 22, 20205 yr by Extreme Coders
January 22, 20205 yr @Extreme Coders: Will be great if you also post a full tutorial on how to do it.
February 2, 20205 yr Posted a write-up about solving the keygenme. https://0xec.blogspot.com/2020/02/finally-solving-weasel-keygenme.html
February 4, 20205 yr On 2/2/2020 at 5:11 PM, Extreme Coders said: Posted a write-up about solving the keygenme. https://0xec.blogspot.com/2020/02/finally-solving-weasel-keygenme.html Really good write up, thank you for persisting and for posting your work... 👍 Ted.
February 4, 20205 yr 2 hours ago, Teddy Rogers said: Really good write up, thank you for persisting and for posting your work... 👍 Thanks a lot Ted. Also thank to Kao for the KeygenMe. Really an innovative challenge so the time it took was well worth it!
Create an account or sign in to comment