Skip to content

Instantly share code, notes, and snippets.

@extremecoders-re

extremecoders-re/-finally-solving-the-weasel-keygenme.ipynb

Last active February 4, 2020 08:11
Show Gist options
  • Save extremecoders-re/cc268753b6d25017fe0cff7299ad9be3 to your computer and use it in GitHub Desktop.
Save extremecoders-re/cc268753b6d25017fe0cff7299ad9be3 to your computer and use it in GitHub Desktop.
Download ZIP
(Finally) Solving the Weasel keygenme.ipynb
Display the source blob
Display the rendered blob
Raw
-finally-solving-the-weasel-keygenme.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "(Finally) Solving the Weasel keygenme.ipynb",
"provenance": [],
"collapsed_sections": [],
"authorship_tag": "ABX9TyP1jG4JzB8ouUs62x+CboTB",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/extremecoders-re/cc268753b6d25017fe0cff7299ad9be3/-finally-solving-the-weasel-keygenme.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"metadata": {
"colab_type": "text",
"id": "3zODftqAsfdT"
},
"source": [
"# (Finally) Solving the Weasel keygenme\n",
"\n",
"Back in 2016, kao posted the weasel keygenme on [tuts4you](https://forum.tuts4you.com/topic/38604-weasel-by-kao/). It consisted of two parts - a custom VM in C# and some crypto. The VM implemented the main logic of the keygenme. In my [previous writeup](https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html) about the challenge, I succeeded in partially solving the challenge by devirtualizing the VM. The crypto part was left unsolved. This was mainly because the crypto logic was way too complex and without special algorithms there was no way to have a go at it. As described in my earlier post, even SAT solvers have no luck in cracking the crypto.\n",
"\n",
"However this time after nearly 4 years I am happy to say that I did manage to break the crypto. In this blog post I will describe the process to solve this keygenme along with all the failed attempts."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "eFMHnB09Klji",
"colab_type": "text"
},
"source": [
"## Re-visiting the crypto algorithm\n",
"\n",
"The challenge was based on solving a system of 40 equations in 50 variables. If we denote the variables by $x$, the equations in the system are similar to\n",
"\n",
"$$\n",
"1 + x_1 + x_2 + x_5 + \\ldots + x_{49} + x_1 x_2 + x_1 x_4 + \\ldots + x_1 x_{47} + x_2 x_3 + x_2 x_5 + \\ldots + x_2 x_{49} + \\ldots + x_{47} x_{49} \\equiv 1 \\pmod 2\n",
"$$\n",
"\n",
"There are 40 such equations all over [$GF(2)$](https://en.wikipedia.org/wiki/GF(2)). Each equation have a linear and bilinear part.\n",
"\n",
"$$\n",
"\\underbrace{1 + x_1 + x_2 + x_5 + \\ldots + x_{49}}_{\\textrm{Linear Part}} + \\underbrace{x_1 x_2 + x_1 x_4 + \\ldots + x_1 x_{47} + x_2 x_3 + x_2 x_5 + \\ldots + x_2 x_{49} + \\ldots + x_{47} x_{49}}_{\\textrm{Bilinear Part}} \\equiv 1 \\pmod 2\n",
"$$\n",
"\n",
"Without the bilinear part we could have simply applied Gaussian Elimination or Gauss Jordan Elimination but that is not possible here."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "4YqFxx5LKvNZ",
"colab_type": "text"
},
"source": [
"## Trying with an ANF solver\n",
"\n",
"[Algebraic Normal Form](https://en.wikipedia.org/wiki/Algebraic_normal_form) (ANF) is a way of representing logic formulas using AND and XOR operations only. Our equation system is already in ANF as it comprises of addition and product operations which correspond to XOR and AND operations respectively in $GF(2)$\n",
"\n",
"$$\n",
"1 \\oplus x_1 \\oplus x_2 \\oplus x_5 \\oplus \\ldots \\oplus x_{49} \\oplus x_1 x_2 \\oplus x_1 x_4 \\oplus \\ldots \\oplus x_1 x_{47} \\oplus x_2 x_3 \\oplus x_2 x_5 \\oplus \\ldots \\oplus x_2 x_{49} \\oplus \\ldots \\oplus x_{47} x_{49} = 1\n",
"$$\n",
"\n",
"There are specialized tools which attempts to solve logic systems expressed in ANF. [Bosphorus](https://www.msoos.org/2019/01/bosphorus-an-anf-and-cnf-simplifier-and-converter/) is one of them. It's an open source tool and can be found on [GitHub](https://github.com/meelgroup/bosphorus). It also has a handy [docker image](https://hub.docker.com/r/msoos/bosphorus/) so we don't have to waste time in setting it up.\n",
"\n",
"The input to Bosphorus is a ANF file describing the system in a specific format [as described](https://github.com/meelgroup/bosphorus#anf-simplification-and-solving) on the tools Readme on GitHub.\n",
"\n",
"![alt text](https://i.ibb.co/Vt6vSLd/image.png)\n",
"\n",
"Before we can use Bosphorus, we need to convert the equations into the required form. This can be done by modifying the `doIt` function (from the earlier blog post) as shown below. [[Full code](https://gist.github.com/extremecoders-re/605f86f24f44a4d8413e94ae5a98ed28)]"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "KsfeIRJYK9GQ",
"colab_type": "text"
},
"source": [
"```C#\n",
"private void doIt()\n",
"{\n",
"\tBitArray huge = new BitArray(hardcoded);\n",
"\tBitArray trgt_bitarr = new BitArray(target);\n",
"\n",
"\tfor (int x = 0, y = 0; x < 40; x++)\n",
"\t{\n",
"\t\tint cbit = Convert.ToInt32(huge[y++]);\n",
"\t\tint tbit = Convert.ToInt32(trgt_bitarr[x]);\n",
"\t\t\n",
"\t\tif (tbit == 0 && cbit == 0) {}\n",
"\t\t\n",
"\t\telse if (tbit == 0 && cbit == 1) Console.Write(\"1\");\n",
"\t\t\n",
"\t\telse if (tbit == 1 && cbit == 0) Console.Write(\"1\");\n",
"\t\t\n",
"\t\telse if (tbit == 1 && cbit == 1) {}\t\t\t\n",
"\t\t\n",
"\t\tfor (int a = 0; a < 50; a++)\n",
"\t\t\tif (huge[y++]) Console.Write($\" + x{a}\");\n",
"\t\t\n",
"\t\tfor (int b = 0; b < 49; b++)\n",
"\t\t\tfor (int c = b + 1; c < 50; c++)\n",
"\t\t\t\tif (huge[y++]) Console.Write($\" + x{b}*x{c}\");\n",
"\t\t\n",
"\t\tConsole.WriteLine(\"\");\n",
"\t}\n",
"}\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "UHoewU3yTxSz",
"colab_type": "text"
},
"source": [
"Running the code we get the [ANF output file](https://gist.github.com/extremecoders-re/0359f2ff90939ebac91b8735654d76ce). Each line represents an equation and there are 40 of them in total.\n",
"\n",
"![alt text](https://i.ibb.co/bsb1k5C/2.png)\n",
"\n",
"\n",
"\n",
"Unfortunately, on feeding the 40 equation system to bosphorus, it wasn't able to provide an answer even after running for an hour. Interestingly, reducing the number of equations to 15 ([reduced-system.anf](https://gist.github.com/extremecoders-re/aaf27456730bc4b4daabd3a4d8f3f442)) and below Bosphorus took at most a few seconds to a couple of minutes to come up with a solution.\n",
"\n",
"For example, after keeping only the first 15 equations of the 40 equation system, Bosphorus was able to find a solution within 8 seconds.\n",
"\n",
"```\n",
"$ docker run --rm -v `pwd`/:/dat/ msoos/bosphorus --anfread /dat/reducedsystem.anf --solvewrite solution -s\n",
"c Bosphorus SHA revision 32e79d211071efb0830e915f6caca3ff484d8f4f\n",
"c Executed with command line: /usr/local/bin/bosphorus --anfread /dat/reducedsystem.anf --solvewrite solution -s\n",
"c Compilation env CMAKE_CXX_COMPILER = /usr/bin/c++ | CMAKE_CXX_FLAGS = -std=c++11 -g -Wall -Wextra -Wunused -pedantic -Wsign-compare -fno-omit-frame-pointer -Wtype-limits -Wuninitialized -Wno-deprecated -Wstrict-aliasing -Wpointer-arith | COMPILE_DEFINES = | STATICCOMPILE = ON | ONLY_SIMPLE = | Boost_FOUND = 1 | STATS = | SQLITE3_FOUND = | ZLIB_FOUND = TRUE | VALGRIND_FOUND = | ENABLE_TESTING = | M4RI_FOUND = TRUE | SLOW_DEBUG = | ENABLE_ASSERTIONS = | PYTHON_EXECUTABLE = | PYTHON_LIBRARY = | PYTHON_INCLUDE_DIRS = | MY_TARGETS = | LARGEMEM = | LIMITMEM = | compilation date time = Sep 30 2019 19:40:23\n",
"c --- Configuration --\n",
"c maxTime = 1.00e+20\n",
"c XL simp (deg = 1; s = 30.00+4.00): 1\n",
"c EL simp (s = 30.00): 1\n",
"c SAT simp (10000:100000): 1 using 1 threads\n",
"c Stop simplifying if SAT finds solution? No\n",
"c Paranoid: 1\n",
"c Cut num: 5\n",
"c Karnaugh size: 8\n",
"c --------------------\n",
"c [ANF Input] read in T: 0.04\n",
"c ---- ANF stats -----\n",
"c Num total vars: 50\n",
"c Num free vars: 50\n",
"c Num equations: 15\n",
"c Num monoms in eqs: 9509\n",
"c Max deg in eqs: 2\n",
"c Simple XORs: 0\n",
"c Num vars set: 0\n",
"c Num vars replaced: 0\n",
"c --------------------\n",
"c [ANF hash] Calculating ANF hash...\n",
"c [ANF hash] Done. T: 0.00\n",
"c [boshp] Running iterative simplification...\n",
"c [ANF prop] Running ANF propagation...\n",
"c [ANF prop] Left eqs: 15 T: 0.01\n",
"c [XL] Running XL... ring size: 50\n",
"c [XL] Done. Learnt: 0 T: 0.39\n",
"c [ElimLin] Running ElimLin... ring size: 50\n",
"c [ElimLin] Done. Learnt: 0 T: 0.01\n",
"c [SAT] has found a solution\n",
"c ---- ANF stats -----\n",
"c Num total vars: 50\n",
"c Num free vars: 50\n",
"c Num equations: 15\n",
"c Num monoms in eqs: 9509\n",
"c Max deg in eqs: 2\n",
"c Simple XORs: 0\n",
"c Num vars set: 0\n",
"c Num vars replaced: 0\n",
"c --------------------\n",
"Solving by SAT...\n",
"s SATISFIABLE\n",
"c Solution found is correct.\n",
"v -0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -21 -22 -23 -24 -25 -26 -27 -28 29 -30 -31 -32 33 34 -35 -36 37 -38 -39 -40 -41 -42 -43 -44 45 -46 -47 48 -49\n",
"c Wrote solution to 'solution'\n",
"c Learnt 0 fact(s) in 8.53 seconds using 62.51MB.\n",
"```\n",
"\n",
"The solution to the reduced equation system is \n",
"\n",
"```\n",
"v -0 1 2 -3 4 -5 6 7 -8 9 10 11 12 -13 14 15 16 17 -18 19 20 21 22 -23 -24 25 26 -27 28 -29 -30 31 -32 -33 34 -35 -36 37 -38 -39 -40 -41 -42 -43 44 45 -46 47 48 -49\n",
"```\n",
"\n",
"Here a negated number means the corresponding variable is False or 0. That is the solution to the reduced system is\n",
"\n",
"$x_0 = 0, x_1 = 1, x_2 = 1, x_3 = 0, x_4 = 1, x_5 = 0, x_6 = 1$ and so on.\n",
"\n",
"However on trying with the full system of 40 equations Bosphorus wasn't able to come up with a solution even after an hour.\n",
"\n",
"```\n",
"$ docker run --rm -v `pwd`/:/dat/ msoos/bosphorus --anfread /dat/fullsystem.anf --solvewrite solution -s\n",
"c Bosphorus SHA revision 32e79d211071efb0830e915f6caca3ff484d8f4f\n",
"c Executed with command line: /usr/local/bin/bosphorus --anfread /dat/fullsystem.anf --solvewrite solution -s\n",
"c Compilation env CMAKE_CXX_COMPILER = /usr/bin/c++ | CMAKE_CXX_FLAGS = -std=c++11 -g -Wall -Wextra -Wunused -pedantic -Wsign-compare -fno-omit-frame-pointer -Wtype-limits -Wuninitialized -Wno-deprecated -Wstrict-aliasing -Wpointer-arith | COMPILE_DEFINES = | STATICCOMPILE = ON | ONLY_SIMPLE = | Boost_FOUND = 1 | STATS = | SQLITE3_FOUND = | ZLIB_FOUND = TRUE | VALGRIND_FOUND = | ENABLE_TESTING = | M4RI_FOUND = TRUE | SLOW_DEBUG = | ENABLE_ASSERTIONS = | PYTHON_EXECUTABLE = | PYTHON_LIBRARY = | PYTHON_INCLUDE_DIRS = | MY_TARGETS = | LARGEMEM = | LIMITMEM = | compilation date time = Sep 30 2019 19:40:23\n",
"c --- Configuration --\n",
"c maxTime = 1.00e+20\n",
"c XL simp (deg = 1; s = 30.00+4.00): 1\n",
"c EL simp (s = 30.00): 1\n",
"c SAT simp (10000:100000): 1 using 1 threads\n",
"c Stop simplifying if SAT finds solution? No\n",
"c Paranoid: 1\n",
"c Cut num: 5\n",
"c Karnaugh size: 8\n",
"c --------------------\n",
"c [ANF Input] read in T: 0.13\n",
"c ---- ANF stats -----\n",
"c Num total vars: 50\n",
"c Num free vars: 50\n",
"c Num equations: 40\n",
"c Num monoms in eqs: 25462\n",
"c Max deg in eqs: 2\n",
"c Simple XORs: 0\n",
"c Num vars set: 0\n",
"c Num vars replaced: 0\n",
"c --------------------\n",
"c [ANF hash] Calculating ANF hash...\n",
"c [ANF hash] Done. T: 0.00\n",
"c [boshp] Running iterative simplification...\n",
"c [ANF prop] Running ANF propagation...\n",
"c [ANF prop] Left eqs: 40 T: 0.02\n",
"c [XL] Running XL... ring size: 50\n",
"c [XL] Done. Learnt: 0 T: 0.41\n",
"c [ElimLin] Running ElimLin... ring size: 50\n",
"c [ElimLin] Done. Learnt: 0 T: 0.02\n",
"c ---- ANF stats -----\n",
"c Num total vars: 50\n",
"c Num free vars: 50\n",
"c Num equations: 40\n",
"c Num monoms in eqs: 25462\n",
"c Max deg in eqs: 2\n",
"c Simple XORs: 0\n",
"c Num vars set: 0\n",
"c Num vars replaced: 0\n",
"c --------------------\n",
"Solving by SAT...\n",
"\n",
"<Kept running without any further output>\n",
"```\n",
"\n",
"Although Bosphorus failed to provide a solution to the full system within a reasonable time it is no doubt an impressive feat that it was able to solve the reduced 15 equation system in just 8 seconds."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "tpNxlBqKvNU1",
"colab_type": "text"
},
"source": [
"## Fiddling with Quantum Computing\n",
"\n",
"The basic premises on which Quantum Computing is based is using quantum mechanical phenemona like superposition and entanglement to perform computation. It's an exciting upcoming field and I was interested to know if the crypto challenge can be solved using quantum logic. IBM offers access to real quantum computers for free ([IBM Quantum Experience](https://quantum-computing.ibm.com/)). The Quantum Computers can be programmed using [Qiskit](https://qiskit.org/) in Python.\n",
"\n",
"In a classical system, information is stored in bits. A bit can be either in one of the two possible states (0 or 1) at a time. If we have 4 bits, there are 16 possible states ($2^4$) and a classical system can represent any one of the 16 possible states at a time.\n",
"\n",
"Quantum computers store information in qubits. A qubit can be in 0 state, 1 state or a superposition of the 0 & 1 states. When in superposition, the value of a qubit is undetermined unless it is measured. However once measured, a qubit will lose its quantum property and will result either in 0 or 1 based on the probability of the state. Unlike classical bits, 4 qubits can represent all 16 states at the same time. This is a massive advantage.\n",
"\n",
"For example, in our challenge there are 50 unknowns all of which are bit sized. Thus there are a total of $2^{50}$ possible inputs. If we try to bruteforce, we have to try out all of the $2^{50}$ inputs one by one to find out which one satisfies all the equations. This is when using classical algorithms.\n",
"\n",
"When using quantum logic, 50 qubits can represent all of the $2^{50}$ possible states at one go which means the time to bruteforce will reduce exponentially. However this is not as simple as it sounds and requires special algorithms specifically designed to exploit the quantum behaviour.\n",
"\n",
"For our problem, [Grover's algorithm](https://qiskit.org/textbook/ch-algorithms/grover.html) looks to be the most promising. It attempts to find the input to a blackbox function to produce a particular output. The algorithm can find the solution to the system in roughly $\\sqrt{2^{50}} = 2^{25}$ iterations ie. a quadratic speedup over the classical approach. Unfortunately at present, the quantum computers available for public use are not powerful enough to support atleast 50 qubits (In actual use case we need more than 50 qubits to account for quantum error correction). The largest amount of qubits supported on IBM-Q is 15 bits as shown below. \n",
"\n",
"![alt text](https://i.ibb.co/wJTJVm3/image.png)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "vq72lpQxJVu1",
"colab_type": "text"
},
"source": [
"## Multivariate cryptography\n",
"\n",
"The mathematical problem on which the logic of the keygenme is based is nothing but [multivariate cryptography](https://en.wikipedia.org/wiki/Multivariate_cryptography) where the maximum degree of a polynomial is 2. As the Wikipedia page points out, solving a system of multivariate polynomial equations has been proven to be $NP$ complete. Systems based on multivariate polynomials are thus used in Post Quantum Cryptography algorithms. In fact the problem we are trying to solve is also based on a Post Quantum Crypto algorithm. Other than the Wikipedia entry, the following documents explain Multivariate Cryptography in a better way.\n",
"\n",
"* [Introduction to Multivariate Public Key Cryptography](http://www.ic.unicamp.br/ascrypto2013/slides/ascrypto2013_geovandropereira.pdf)\n",
"* [Multivariate Quadratic Public-Key Cryptography In the NIST Competition](https://www.maths.ox.ac.uk/system/files/attachments/MQ%20Public-Key%20Crypto%20in%20the%20NIST%20competition.pdf)\n",
"* [Multivariate Quadratic Polynomials in Public Key Cryptography](https://www.win.tue.nl/diamant/symposium05/abstracts/wolf.pdf)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "R81SO3fbPetJ",
"colab_type": "text"
},
"source": [
"## The Fukuoka MQ challenge\n",
"\n",
"Interestingly there's an ongoing challenge about solving Multivariate Quadratic Polynomials - [The Fukuoka MQ challenge project](https://www.mqchallenge.org/). The following excerpt is taken from the challenge website.\n",
"\n",
"![alt text](https://i.ibb.co/QmQcgXv/image.png)\n",
"\n",
"If we look closely at the form of the polynomial system, this is the same as the one we are trying to solve - consisting of a linear and a bilinear part. Our system falls under Type-IV, a signature scheme as it has 50 unknowns ($n$) and 40 equations ($m$) over $GF(2)$.\n",
"\n",
"The Hall of Fame lists various researchers over the years that have attempted to solve the challenges and were successful.\n",
"\n",
"![alt text](https://i.ibb.co/Kh5Q7Nw/image.png)\n",
"\n",
"In their papers they have described what approach they took to solve them and in some cases have also provided us with ready made tools which we can re-use for our purpose. Among them, in the [Breaking the Fukuoka MQ Challenges](https://www.win.tue.nl/~tchou/slides/breaking-mq.pdf) slides, the authors pointed out that they were able to solve a Type-IV system using an efficient bruteforce technique (Graycode enumeration) implemented on FPGA's. it's efficient in the sense that instead of blindly bruteforcing which requires an enormous amount of time, the Graycode enumeration technique searches through the space in a specific order. \n",
"\n",
"For example, consider this system\n",
"\n",
"$$\n",
"1 + x_1 + x_2 + x_5 + \\ldots + x_{49} + x_1 x_2 + x_1 x_4 + \\ldots + x_1 x_{47} + x_2 x_3 + x_2 x_5 + \\ldots + x_2 x_{49} + \\ldots + x_{47} x_{49} \\equiv 1 \\pmod 2\n",
"$$\n",
"\n",
"We are trying to find a solution by bruteforcing. A naive implementation would recompute each addition and product for every attempt. However, it can be easily noticed most of the computations are not really required. Suppose on first attempt we try with $x_0 = 0$ and on the next attempt with $x_0 = 1$. Since only the value of $x_0$ changes in between the attempts, all other terms which does not involve $x_0$ will not be affected. Thus there's no need to compute the value of the other part of the equation. If we bruteforce by changing the value of the variables according to the [Gray-code order](https://en.wikipedia.org/wiki/Gray_code), we have to do significantly less computation than the traditional bruteforce approach. The downside of the graycode enumeration technique is it requires increased memory at the expense of reduced computation time.\n",
"\n",
"The authors have provided a [GPU implementation](http://polycephaly.org/projects/forcemq/data/MQForceGPU-20180724.tgz) of the algorithm at http://www.polycephaly.org/projects/forcemq/index.shtml. There's also a CPU implementation known as libFES (Fast Exhaustive Search) available at https://www.lifl.fr/~bouillag/fes/. LibFES requires SageMath but I had to forego it as I was not able to install the package on modern versions of Sage."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "UwYvmOBTZjso",
"colab_type": "text"
},
"source": [
"## Solving the challenge\n",
"\n",
"The GPU implementation of the solver requires to represent the system of equations in a special format as described on [this](https://www.mqchallenge.org/format.html) page. An example is shown below.\n",
"\n",
"![alt text](https://i.ibb.co/jwBSh7p/image.png)\n",
"\n",
"It's worthwhile to note that while the system of equations we are trying to solve has no square terms in it, the input to the tool must include the coefficient of the square terms (which will be zero in our case). In addition the coeffecients must be provided in [Graded reverse lexicographic order](https://en.wikipedia.org/wiki/Monomial_order#Graded_reverse_lexicographic_order).\n",
"\n",
"The same C# code of the VM can be modified to print the coefficients in the graded reverse lex order.\n",
"\n",
"```\n",
"private void doIt()\n",
"{\n",
"\tusername = \"kao\";\n",
"\t\n",
"\tbyte[] hash = MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(username));\n",
"\ttarget_bits = new BitArray(new byte[5]{hash[2], hash[5], hash[8], hash[11], hash[14]});\n",
"\t\n",
"\t// The big array\n",
"\tBitArray huge = new BitArray(hardcodedarray.hardcoded);\n",
"\t\n",
"\tBitArray calc = new BitArray(50);\n",
"\t\n",
"\tfor (int i = 0, j = 0; i < password.Length; i++)\n",
"\t{\n",
"\t\tint pos = \"23456789ABCDEFGHJKLMNPQRSTUVWXYZ\".IndexOf(password[i]);\n",
"\t\tif (pos != -1)\n",
"\t\t{\n",
"\t\t\tfor (int k = 0; k < 5; k++)\n",
"\t\t\t{\n",
"\t\t\t\tcalc[j++] = (pos & 1) != 0;\n",
"\t\t\t\tpos >>= 1;\n",
"\t\t\t}\n",
"\t\t}\n",
"\t}\n",
"\t\n",
"\tfor (int x = 0, y = 0; x < 40; x++)\n",
"\t{\n",
"\t\tint[,] prod_bits = new int[50, 50];\n",
"\t\tint[] sum_bits = new int[50];\n",
"\t\t\n",
"\t\tbool bit = huge[y++];\n",
"\t\tint start_bit = bit?1:0;\n",
"\t\t\n",
"\t\tfor (int a = 0; a < 50; a++)\n",
"\t\t{\n",
"\t\t\tif (huge[y++])\n",
"\t\t\t{\n",
"\t\t\t\tbit ^= calc[a];\n",
"\t\t\t\tsum_bits[a] = 1;\n",
"\t\t\t}\n",
"\t\t\telse\n",
"\t\t\t\tsum_bits[a] = 0;\n",
"\t\t}\n",
"\t\t\n",
"\t\tfor (int b = 0; b < 49; b++)\n",
"\t\t\tfor (int c = b + 1; c < 50; c++)\n",
"\t\t\t{\n",
"\t\t\t\tif (huge[y++])\n",
"\t\t\t\t{\n",
"\t\t\t\t\tbit ^= (calc[b] & calc[c]);\n",
"\t\t\t\t\tprod_bits[b, c] = 1;\n",
"\t\t\t\t}\n",
"\t\t\t\telse\n",
"\t\t\t\t\tprod_bits[b, c] = 0;\n",
"\t\t\t}\t\t\t\t\t\t\t\t\n",
"\t\t\n",
"\t\t//==========================================\n",
"\t\t// Print system\n",
"\t\tfor (int j=0; j<50; j++)\n",
"\t\t{\n",
"\t\t\tfor (int k=0; k<j+1; k++)\n",
"\t\t\t{\n",
"\t\t\t\tConsole.Write($\"{prod_bits[k, j]} \");\n",
"\t\t\t}\n",
"\t\t}\n",
"\t\t\n",
"\t\tfor (int j=0; j<50; j++)\n",
"\t\t{\n",
"\t\t\tConsole.Write($\"{sum_bits[j]} \");\n",
"\t\t}\n",
"\t\tConsole.WriteLine($\"{start_bit^(target_bits[x]?1:0)} ;\");\n",
"\t\t\n",
"\t}\n",
"}\n",
"```\n",
"\n",
"Running the code we can obtain the coefficients of the polynomial system as shown below (Also as a [gist](https://gist.github.com/extremecoders-re/a8f31ff79d0d8c03a7a4ad5b71702daf)).\n",
"\n",
"![alt text](https://i.ibb.co/p0Tnby5/image.png)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "izbhMK_KgnWz",
"colab_type": "text"
},
"source": [
"## The keygen \n",
"\n",
"Feeding the solver with 40 equations in 50 variables quickly exhausts all the memory that is available (12 GiB on a Colab Instance). Fortunately, the authors of the tool have thought of this before and have provided a way to work around the issue. Instead of solving with 50 variables, we can solve a reduced system with fewer variables while fixing the value of the others.\n",
"\n",
"In our case we have more variables than equations i.e. an [under-determined system](https://en.wikipedia.org/wiki/Underdetermined_system). An under-determined system is either inconsistent or have infinitely many solutions. If we fix the value of 10 variables randomly, we are left with solving a system of 40 equations in 40 variables. This reduced system may or may not have any solution but if it does have one the solver will be able to find it within the stipulated memory and time constraints.\n",
"\n",
"The source code of the keygen can be found in my GitHub [repo](https://github.com/extremecoders-re/weasel-keygen). It requires the CUDA library and a compatible Nvidia GPU to run. Colaboratory and Kaggle (both owned by Google) offers free GPU cloud computation for Machine Learning and we can use them for our purpose.\n",
"\n",
"As described to reduce memory and computation time, the keygen fixes the value of 10 variables to reduce the system to 40 equations in 40 variables. This is done in [*keygen.py*](https://github.com/extremecoders-re/weasel-keygen/blob/407d4c336fba9f8db1820acdd9d02af407993414/keygen.py#L127-L128)\n",
"\n",
"```\n",
"def main(username):\n",
" f = io.StringIO()\n",
"\n",
" hsh = hashlib.md5(username.encode(\"utf8\")).digest()\n",
" hash_bytes = [hsh[2], hsh[5], hsh[8], hsh[11], hsh[14]]\n",
" target = \"\"\n",
"\n",
" for h in hash_bytes:\n",
" target += \"{0:08b}\".format(h)[::-1]\n",
"\n",
" target_bits = list(map(int, list(target)))\n",
"\n",
" print (file_header, file=f)\n",
"\n",
" for idx, line in enumerate(coeffs):\n",
" print (line, end = \" \", file=f)\n",
" print (init_bits[idx] ^ target_bits[idx], \";\", file=f)\n",
"\n",
" fixed_bits = \"{0:010b}\".format(random.getrandbits(10))\n",
" fixed_system = fix(fixed_bits, io.StringIO(f.getvalue()))\n",
" f.close()\n",
"``` \n",
"\n",
"After fixing 10 variables with random values we are left with a 40 variable system which is then passed on to the main solver.\n",
"\n",
"```\n",
" p = Popen(['./guess'], stdout=PIPE, stdin=PIPE, stderr=PIPE)\n",
" stdout, stderr = p.communicate(input=bytes(fixed_system.getvalue(), 'utf8'))\n",
" # print (stdout)\n",
" # print (stderr)\n",
"\n",
" try:\n",
" soln = int(stdout.split()[0].strip(), 16)\n",
" output = '{0:040b}'.format(soln)\n",
" print (\"Username: \", username)\n",
" print (\"Password: \", end = \"\")\n",
" parse_output((fixed_bits[::-1] + output)[::-1])\n",
" except:\n",
" print (\"[-] Unable to generate password! Please retry\")\n",
"```\n",
"\n",
"If the solver is able to find a solution to the system, its output is parsed to obtain the password. Since we are fixing the values of 10 variables randomly, occasionally the resultant reduced system may turn out to be inconsistent and in such a case the solver fails. Re-running the keygen should be enough to generate a valid key. A few sample runs are shown below\n",
"\n",
"```\n",
"! cd weasel-keygen && ./keygen.py 0xec\n",
"Username: 0xec\n",
"Password: YBG3T-6EWUG\n",
"```\n",
"\n",
"```\n",
"! cd weasel-keygen && ./keygen.py kao\n",
"Username: kao\n",
"Password: QL9UB-LTKYY\n",
"```\n",
"\n",
"```\n",
"! cd weasel-keygen && ./keygen.py extremecoders\n",
"Username: extremecoders\n",
"Password: RAGWC-XW6VP\n",
"```\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "DYYWN7NBwWUr",
"colab_type": "text"
},
"source": [
"## Links & References\n",
"\n",
"* https://www.win.tue.nl/~tchou/mqchallenge/\n",
"* https://www.mqchallenge.org/\n",
"* https://www.maths.ox.ac.uk/system/files/attachments/MQ%20Public-Key%20Crypto%20in%20the%20NIST%20competition.pdf\n",
"* https://www.win.tue.nl/diamant/symposium05/abstracts/wolf.pdf\n",
"* http://www.polycephaly.org/projects/forcemq/index.shtml\n",
"* https://www.win.tue.nl/~tchou/slides/breaking-mq.pdf\n",
"* https://bitbucket.org/fes/fes/\n",
"* https://github.com/cbouilla/libfes-lite\n",
"* https://github.com/cbouilla/pyfeslite\n",
"* https://arxiv.org/ftp/arxiv/papers/1507/1507.03674.pdf\n",
"* https://www.comp.nus.edu.sg/~meel/Papers/date-cscm19.pdf\n",
"* https://hal.archives-ouvertes.fr/hal-01981516/document\n",
"* http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_sequence.html\n",
"* https://rd.springer.com/content/pdf/10.1007%2F978-3-642-34047-5_18.pdf\n",
"* https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/\n",
"* https://www.lifl.fr/~bouillag/fes/\n",
"* https://www.win.tue.nl/~tchou/papers/forcemp.pdf\n",
"* https://static.aminer.org/pdf/PDF/000/120/383/asymmetric_cryptography_with_a_hidden_monomial.pdf\n",
"* http://doc.sagemath.org/html/en/reference/misc/sage/features/fes.html\n",
"* https://tungchou.github.io/papers/forcemp-fpga.pdf\n",
"* https://www.nayuki.io/page/gauss-jordan-elimination-over-any-field\n",
"* https://brilliant.org/wiki/gaussian-elimination/\n",
"* https://docs.sympy.org/1.5.1/modules/matrices/matrices.html#sympy.matrices.matrices.MatrixBase.gauss_jordan_solve\n",
"* https://cp-algorithms.com/linear_algebra/linear-system-gauss.html\n",
"* https://en.wikipedia.org/wiki/Algebraic_normal_form\n",
"* https://www.fields.utoronto.ca/programs/scientific/07-08/cryptography/amr_youssef.pdf\n",
"* https://pdfs.semanticscholar.org/0296/a72f22f233dd606c0d63a74cd47945027e68.pdf\n",
"* https://en.wikipedia.org/wiki/XSL_attack\n",
"* https://crypto.stackexchange.com/questions/75357/what-is-linearization-attack\n",
"* https://rd.springer.com/content/pdf/10.1007%2F978-3-642-34047-5_18.pdf\n",
"* https://link.springer.com/content/pdf/10.1007%2F3-540-48405-1_2.pdf\n",
"* https://www.rocq.inria.fr/secret/Anne.Canteaut/poly.pdf\n",
"* https://eprint.iacr.org/2012/587.pdf\n",
"* https://www.ee.iitb.ac.in/~vrs/ACofAES.pdf\n",
"* http://www.sagemath.org/files/thesis/weinmann-thesis-2009.pdf\n",
"* https://cse.iitkgp.ac.in/~abhij/publications/XL_SGE-InfoSecHiComNet11.pdf"
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment