kao Posted July 13, 2016 Share Posted July 13, 2016 (edited) 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, 2016 by kao Updated Hall of Fame 4 Link to comment Share on other sites More sharing options...
Extreme Coders Posted July 13, 2016 Share Posted July 13, 2016 This should be the devirtualized code in graph form. Spoiler Will write a tutorial when fully completed with keygenning. Link to comment Share on other sites More sharing options...
kao Posted July 13, 2016 Author Share Posted July 13, 2016 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... Link to comment Share on other sites More sharing options...
Extreme Coders Posted July 14, 2016 Share Posted July 14, 2016 (edited) 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, 2016 by Extreme Coders Added attachment 8 Link to comment Share on other sites More sharing options...
kao Posted July 14, 2016 Author Share Posted July 14, 2016 Verrry nice! All thumbs up! Link to comment Share on other sites More sharing options...
Kurapica Posted July 14, 2016 Share Posted July 14, 2016 Excellent work Link to comment Share on other sites More sharing options...
Extreme Coders Posted July 16, 2016 Share Posted July 16, 2016 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 2 Link to comment Share on other sites More sharing options...
Extreme Coders Posted August 16, 2016 Share Posted August 16, 2016 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 6 Link to comment Share on other sites More sharing options...
cawk Posted August 16, 2016 Share Posted August 16, 2016 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 Link to comment Share on other sites More sharing options...
kao Posted August 16, 2016 Author Share Posted August 16, 2016 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. Link to comment Share on other sites More sharing options...
GIV Posted January 3, 2017 Share Posted January 3, 2017 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? Link to comment Share on other sites More sharing options...
Extreme Coders Posted January 3, 2017 Share Posted January 3, 2017 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. Link to comment Share on other sites More sharing options...
mrexodia Posted January 3, 2017 Share Posted January 3, 2017 Pretty easy, see my solution... Spoiler 3 2 Link to comment Share on other sites More sharing options...
Extreme Coders Posted January 4, 2017 Share Posted January 4, 2017 7 hours ago, mrexodia said: Pretty easy, see my solution... Impressive work!!! Why it didn't occur to me ? Link to comment Share on other sites More sharing options...
GautamGreat Posted June 2, 2018 Share Posted June 2, 2018 No solution far now @kao can you post a solution too? Link to comment Share on other sites More sharing options...
MindSystem Posted June 4, 2018 Share Posted June 4, 2018 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 Link to comment Share on other sites More sharing options...
GautamGreat Posted June 4, 2018 Share Posted June 4, 2018 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. Link to comment Share on other sites More sharing options...
CodeExplorer Posted June 15, 2019 Share Posted June 15, 2019 (edited) 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, 2019 by CodeExplorer Link to comment Share on other sites More sharing options...
CodeExplorer Posted June 16, 2019 Share Posted June 16, 2019 (edited) 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, 2019 by CodeExplorer Link to comment Share on other sites More sharing options...
Extreme Coders Posted January 20, 2020 Share Posted January 20, 2020 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. 3 1 Link to comment Share on other sites More sharing options...
Extreme Coders Posted January 22, 2020 Share Posted January 22, 2020 (edited) 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, 2020 by Extreme Coders 3 Link to comment Share on other sites More sharing options...
CodeExplorer Posted January 22, 2020 Share Posted January 22, 2020 @Extreme Coders: Will be great if you also post a full tutorial on how to do it. Link to comment Share on other sites More sharing options...
Extreme Coders Posted February 2, 2020 Share Posted February 2, 2020 Posted a write-up about solving the keygenme. https://0xec.blogspot.com/2020/02/finally-solving-weasel-keygenme.html 4 1 Link to comment Share on other sites More sharing options...
Teddy Rogers Posted February 4, 2020 Share Posted February 4, 2020 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. 1 Link to comment Share on other sites More sharing options...
Extreme Coders Posted February 4, 2020 Share Posted February 4, 2020 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! Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now