Some guy posted his work on solving it on github. - Some HR guy from Nintendo asked him to take it down 4 years ago, still up there. github.com/IamLupo/Nintendo-HireMe/issues/1
@@AnglosArentHuman Just gonna say there were leaked documents from Nintendo detailing their plans to effectively stalk Homebrew developers. So a nice powermove indeed, but let's hope it doesn't put him on some kind of list.
You can leave the matrix as the given 32x32 form and calculate its inverse. That's all that is required to reverse the diffusion part of the challenge (I have implemented it this way - just invert the 32x32 matrix and apply the inverse on bytes in the same way the challenge code applies the forward operation). As an aside - xor operations performed on bytes can be linear or not; they're not inherently non-linear. Whether xoring bytes is linear or not depends on our view of what the bits which make up the bytes mean. If the bytes are 8 bit positive integers then it's non-linear. If we consider the bits as coefficients of a polynomial over GF(2) - e.g. b[7]x^7 + b[6]x^6 + ... + b[0]x^0 then the bitwise xor of two bytes is linear. That's how CRCs (a type of linear checksum) are calculated and the maths behind LFSRs etc.
Plot twist : this is just for you to submit your CV The real challenge is when Mario asks you do to it again, but this time, whitout any libs, using your own writen compiler for Assembly language targeting the original NES system.
I'd love to see the alternate solution that you found out. This rather interesting to watch, and shows even seemingly complex problems don't necessarily require overly complex solutions as long as you're able to think outside the box.
From www.nerd.nintendo.com/files/HireMe /* The solutions to this challenge belong to different levels : Level 1 : an iterative algorithm which typically takes more than a second to find a solution (for any given output). Most people stop here, which is fine, but if you want to go further, there is : Level 2 : a non-iterative algorithm which typically takes less than a millisecond to find a solution (for any given output). Very few people have reached this level. But if you want to beat it completely, there's yet another castle... Level 3 : an algorithm which can provide any of the 2^128 solutions (for any given output). No-one has reached this level yet ! */
maybe someone could use an SMT solver for level3. Model the bitvector equations and it will probably give one random solution. I'm sure there is a way by iteratively adding constraints to get more solutions, maybe all (?). I'm not an expert on solving problems with SMT, it was just an idea. For those interested "SAT/SMT by example" by Dennis Yurichev may be useful.
I reached a level 3 solution after continuing to work on my level 2 solution from the last video comments, I even got contact from the author of the challenge from Nintendo and he confirmed I was the first to get there so that's nice! I emailed LiveOverflow my solution but he hasn't got back to me yet, I guess he's busy.
You don’t need to solve linear equations to get the input array if you have the output array, heres what you can do: so if you have the input array and run the code in the loop of the forward method once you get the out array which is the xor of bytes in the input array chosen according to a mask in the diffusion array, now if you have the output array lets say you want to get the first byte in the input array well if you can find a combination of masks in the diffusion array that xor together to give you 0x1 then xoring together the bytes in the output array that correspond to those masks will give you the first byte in the input array and so on, finding the masks that xor together to get you 0x1, 0x2, 0x4 ... took me about 5 min of brute force search and in they end I discovered something weird the masks that you need to get 0x1 were described by the value in the first mask in the diffusion array and so on, if anyone is interested i can explain further
From what I understand, for a given c_i, only a single diffusion value p_i is used to determine which bytes from d_i to XOR together. How did you come up with the approach of XORing values from the diffusion array together to get 0x1, 0x2, 0x4, 0x8, 0x10, etc.? Why does xor'ing the values corresponding to these combinations yield the i-th input value? I tested it myself and it's true that XORing the bytes in d corresponding to the indices of diffusion values in p that XOR together to yield 0x1, 0x2, 0x4, ... yields the first byte of c, the second byte of c, the third byte of c, etc. However I'm just wondering how you arrived at this conclusion? I'm clearly missing something since it seems to me the elements of the diffusion array are independent from one another when it comes to calculating c values. Many thanks in advance.
please note that in the real world you would never invert to solve a system of linear equations, you use something like gauss elimination instead since it‘s much more efficient owing to its better runtime complexity :)
interpolation scales with a degree of loss of accuracy over the real problem. What ninty says is "use a different aproach that hypotesis to solve this, it's the key of our work"
Instead of using fancy math to reverse the diffusion step, I just xor'd all combinations of rows of the matrix until one was equal to 1, 2, 4, etc. (As xor'ing the values corresponding to these combinations would then yield the i-th input value.) After doing this for the first input value, I noticed that the "mask" of output values to xor was the same as the first entry in the diffusion array (i.e. the mask of input values to xor to receive the first output value). When the second value also matched, I tried doing the diffusion step twice on some input. And sure enough, after two diffusions the values were the same as the input again. So oddly enough, "diffusion" appeared to be its own inverse. Now, I could have obviously made some silly mistake. Can anyone confirm that this is actually the case? I then gave up on brute forcing the 16^256 combinations of possible outputs, because I thought that even enumerating all of them without doing any other computations would take more time than the universe had left to live.
I always wonder if companies actually make these challenges just so they don't want to take the trouble of solving it. Then when you submit your answer they just take the code and hit you with a "We regret to inform you but we will not be proceeding with your application"
I didn't solve the challenge completely, but I rewrote the original algorithm in Haskell. Given that Haskell is purely functional, it also really brought the mathematical side of this algorithm to view. All in all a fun challenge and I enjoy your videos!
Well, in some schools they do teach matrixes in 8th or 9th class (my friend that was in math oriented school said they learned them). I learned them in 1st year in uni so 3 years later.
@@Animas42 In india this kind of maths was taught in 8th or 9th class and there are more advance versions of that as you move towards higher classes 😅😅
This looks like a simple code mapping, the mux selection just throws off the whole game, but honestly, any symbol can be identified for output at any position. If you expand out the bitstream of the initial input as positions instead of bits, then recreate the code as such in a DAG tree, pruning as you go through each round, you will find the endpoint will be a identification map. You want a letter, it tells you what bits to flip for it in that spot.
Very very interesting. Whenever I see your videos, I really learn something new. Thanks dude, your channel subscription is so Worth it!! Great job dude!
Very nice!!! Since i've been watch the first video that you talk about this nintendo "hire.me" puzzle, I'm get curious and read something about algebra (on the same path to solve), looking for something like eigenvectors and eigenvalues, now i see that the solution method it's more different then I thought.
This is so cool! Currently taking a course in cryptography at uni and the course has a project about linear shift registers, and the tasks are very similar to this! Very nice
There was no need to separate bytes into bits, because the "diffusion" matrix itself only contains single bits, and is a perfectly valid invertible matrix over GF(2), and this is enough. "Linearity" has nothing to do with bitwise "xor", as it's not a unary operation... Inverse of a matrix does not exist when it is singular (determinant is zero), this is why your 3x3 GF(2) matrix example did not work.
Just brainstorming here C[0] ^= D[0:32] * ((P[0] >> 0:32) & 1) D[0:32] is a 32 element vector P[0] >> 0:32 is a 32 element vector with P[0] bit shifted by index ((P[0] >> 0:32) & 1) does per element least-significant bit (LSB) on shifted P[0] D[0:32] * ((P[0] >> 0:32) & 1) performs vector-vector multiplication, resulting in a scalar C[0] ^= D[0:32] * ((P[0] >> 0:32) & 1) xors scalar with current index of C Generalize the above. From my understanding, it essentially masks each of the 32 bits of P[0] by D (forall i. D[i] * bit(P, i)), then applies an XOR at C[0]. TL;DR: C is the xor of itself and a mask D applied to P.
There should be a much faster solution to the xor part: you recognize that each integer in the diffusion array indicates how one byte from d is XORed onto each byte of c. However, this operation is the same for all bits of this byte of d. Therefore we notice something interesting when modifying d bitwise and applying the diffusion operation: When we change(XOR) the mth bit of the nth d, the nth diffusion integer is effectively XORed onto all the mth bits of c vertically. From this, we recognize due to the nature of XOR, when changing the mth bit of both the element i and j of d, the XOR of the ith, and the jth diffusion integers is XORed onto all the mth bits of c vertically. Because there are 32 diffusion operators and 32 bits, we should be able to find a combination that effectively maps directly onto c, and you can therefore effectively reverse the operation in linear time by solving the linear system of diffusion operators once and hardcoding the values into your program(or calculate it at compile time). I came up with this by thinking for an hour or so about the problem, so it might run into complications during implementation. I have no time to implement that, but an interesting puzzle and I am just going to leave my thoughts here for anyone who wants to give it a go.
You should have implemented the GF2 version of Gaussian Elimination in C. Now that would be an exciting video. approach would be to convert the system of equations portion and the store an array of bitvectors, one for each row of the matrix corresponding to that array. Then use bitwise elementary row operations. to invert.
3 роки тому
I tried myself the challenge before watching this video. At the time I didn't find any code to find the inverse of a GF2 matrix. Maybe because I didn't know they were called GF2, I was searching for binary matrix. I'll post the code of inverse Gaussian elimination soon in GitHub, it's quite simple
Computers usually don't invert matrices because it's numerically unstable. Instead, you usually find some smart trick that lets you write the matrix A on a different form. A simple example of this would be the LU decomposition.
@@ArizeOW Technically, the solution to this challenge isn't what he proposes. It's outlined in the program that you can solve it in 3 ways, and each with increasing difficulty. From the code itself: /* The solutions to this challenge belong to different levels : Level 1 : an iterative algorithm which typically takes more than a second to find a solution (for any given output). Most people stop here, which is fine, but if you want to go further, there is : Level 2 : a non-iterative algorithm which typically takes less than a millisecond to find a solution (for any given output). Very few people have reached this level. But if you want to beat it completely, there's yet another castle... Level 3 : an algorithm which can provide any of the 2^128 solutions (for any given output). No-one has reached this level yet ! */ On top of it, the solution would have to be packaged along with the source code, I'm guessing. If the solution he proposes works exclusively for the "Hire me" string, then he's technically failing at lv1
@@artstrange3230 those comments were added after I made my video. And I don't know why you think my solution only finds "Hire me". The code at 11:42 sets the constraints for "Hire me" but could be set to anything else ;)
@@LiveOverflow OH! Senpai has noticed me. Well, good sir, I do *not* think your solution only finds "Hire me". I am merely stating an if clause, which is separate from my line of thought.
I found a better solution (although not as fast as the non-iterative one advertised in the code comment). You can use the fact that only some input bytes impact a given final output byte to choose which byte to change in the next attempt of your brute force. Typically, when the diffusion has two 1 in binary for bits 2n and 2n+1 it means changing intermediate output byte 2n will also change 2n+1 but will not change the final output byte n, so don't try to change it. Maybe (probably) z3 is smart enough to detect it or maybe not, but in my case it made the solving much faster (I didn't let it complete without it but I thought it wouldn't considering the upper bound of 2^128). I feel that using z3 is a bit cheating because I have no idea what crazy optimization it has internally and how smart it is. It make it feel like you solve the problem but may not really understand everything about it.
If you would to print the inverse linear transformation matrix you will also find out that it is inverse to itself :) Also, there is a way to greatly improve the performance of the linear transformation using lookup tables due to its linear nature (such things are done in AES optimizations when you choose speed over memory usage). Also, you can slightly optimize the input selection process by just choosing a random 16 bytes for the input, and than taking a valid, random value from inside the sbox (so you know it obviously has an inverse value, since you chose it from the sbox itself).
It's basically the same way how I solved it (see my comment in the last video). My code is still brute force, (although maybe slightly more efficient, takes about 5 minutes). Someone in the last video commented a very good solution exploiting the internal structure of confusion array that can solve this problem very efficiently (constant time) for any 16 byte output.
I'm still trying to do this, maybe if you bring the sbox operation to the matrix realm and precompute the whole loop and obtain a single matrix you can do it in one step.
@@lab-at-homeI thought about that approach, but the problem is that sbox is not a one-to-one function, which means it's impossible to find the inverse for that (Imagine f(x)=x^2, for each x, there is an unambiguous value for it. However, if we try to find the inverse for it, say for what value x such that f(x) = 1? Both x=-1 and x=1 satisfies the condition, but we don't know which one exactly, confusion matrix in this case is the same deal). You might be tempted to think that we can try to guess all possible values, but the fact that it iterates for 256 rounds makes it very difficult (i.e. very likely to find a value that you cannot reverse the sbox operation). You can verify this fact by using a random 32 byte value as input after the last diffusion round and see how far you can go without hitting a dead end.
@@yuxin7440 I know, I made a video about it ua-cam.com/video/A5uPVXDY8tU/v-deo.html :D . No matter what solution you make, it is going to have some free variable, since there are multiple inputs that outputs "Hire me!!!!!!!!\x0" (I got more then 200 in some minutes of calculation). The end matrix will have a bunch of free variables in it, after all the calculations you just need to choose values for this free variables. In a simplified example, lets suppose that you make the precomputation and the resulting matrix is [[x,0],[0,1]], since the problem is in GF(256), x can be from 0-255. Choosing a x (lets say x=1 to make it easy to reverse) would give us one possible solution, any other value for x (that match some criteria like the inversability of the matrix) would give another correct solution. This is the only way I can see to achieve constant time (and level 2), do you have any other ideas?
@@lab-at-home Here is my solution: github.com/lewisxy/hireme-challenge, which is NOT a constant time solution. The constant time solution does not attempt to reverse the operation. It simply constructs the input based on pre-computed lookup table. Apparently there is a specific set of bytes that are closed under confusion lookup and diffusion (i.e. like a subspace of GF(256)). If you just happen to find these bytes, you can simply undo all operations confusion and diffusion as if it is invertible. And if you are lucky, the subspace of at least 16 bytes will allow you to construct any of 256 bytes, which means you can compute a 32 byte input for all possible 16 byte output in constant time. The problem is how to find such subspace. There is a very good comment in the first part video talking about this approach (unfortunately I don't know how to get the link to a specific comment in a video, so you will need to find that)
Math is a subject that if you drop out of the loop at any time in your education, you have to do a lot of extra work to get back into it. This is one of the reasons why many people hate math, because they cannot just open a math book and read to learn. You have to continuously work on it.
Great job on solving and explaining it! I have a small suggestion though... I understand that this is a single use kind of code and maintainability is not a big concern here. However given the educational value of your videos could you clean your code a bit? I mean like 's1' for even stuff and 's2' for odd stuff... I didn't want to be rude, but I hope my suggestion could help you make even better content! Keep it up! I really enjoy your channel!
Well the problem is to even know that Sage , Z3 and so exists my approach would properly been trying to program my own matrix system. You don't learn such stuff in school or even university except you take a modul in encoding an such stuff. The most fanciest stuff related to work I ever programmed was a function which analyse matching pattern between 2 string to filter things out which are different. In studium yes I did program an encoder as duty project you know it f... up when you read c[p[i]][u[j]][m[i-k]]. 3d array and your indizies are in another array.
If you have python printing stuff, it would take more time to execute the whole code for some reasons. It's better not to use print() when bruteforcing.
@@LiveOverflow You should try Google Colab, it is completely free jupyter notebook and has NVIDIA Tesla GPU's for acceleration. Great for accelerated brute-forcing!
you rate cryptographic algorithms on how long they take to brute force. If you can sufficiently reduce the length of time it takes to brute-force (even to the order of years) the algorithm is no longer effective and thus has been broken.
If I wanted to be a cryptographer, then yes, math matters. In most software engineering jobs today, it's about how well you can architect a system to increase productivity of your team and reduce future maintenance costs rather than if you can reverse hack an encryption algorithm. Have you had a different experience? Is this math used in your day to day job?
LiveOverflow: "This looks like the math you had to learn in, like, the 8th or 9th grade or so" Me, some PHP webdeveloper schmuck that does not even recognize basic maths: "Why yes of course. I had a fluke it would be linear algebra all along since part 1, kudos LiveOverflow, kudos" Story of my life ladies and gentlemen :D
I think this is more like a backdoor. An algorithm that also has an algorithm to reverse it is usually intentional. If it wasn't reversible, there would be no purpose because you could just use an existing hashing algorithm. This is more like asymmetric encryption where the client has a simple deterministic decryption algorithm (forward) and the host would use this complex encryption algorithm to generate a valid input for the client to use.
from the site, there is apparently a non-iterative solution... that sounds crazy. and level 3? what is this even? 2^128 is the square root of possible inputs of the function. it's also a number in the 38 digits which makes it probably not so fun to calculate... but just to let it sink in - there are ~3.4*10^38 valid solutions to this problem, and we can't just stumble across one randomly, FML this sounds stupid. my initial idea was to make some kind of inverse for the diffusion array itself but I'm not smart enough for this sort of thing. especially when I'm trying this at 1am.
2:21 must a new record for advert placement (this after getting 20sec of unskippable adverts pre-roll). Then 13 unskippable sec of ads 6:40 and 8:20. 22sec at 14:20. Someone stop Google before all videos become nothing but adverts.
Sagst du absichtlich "we have now a (...)"? Klingt im englischen sehr antiquiert, (besonders temporale) Adverbien zwischen ein Verb und ein Objekt zu schieben.
Nintendo HR on Monday : Hey we got a lot of applications over the weekend!
Some guy posted his work on solving it on github. - Some HR guy from Nintendo asked him to take it down 4 years ago, still up there. github.com/IamLupo/Nintendo-HireMe/issues/1
@@TheCakeLie ngl, leaving Nintendo HR on read is a nice powermove.
@@AnglosArentHuman Just gonna say there were leaked documents from Nintendo detailing their plans to effectively stalk Homebrew developers. So a nice powermove indeed, but let's hope it doesn't put him on some kind of list.
😂😂😂
Basically you just have enough tenacity and willpower to solve this.
that's a good summary of working in IT security :P
You can leave the matrix as the given 32x32 form and calculate its inverse. That's all that is required to reverse the diffusion part of the challenge (I have implemented it this way - just invert the 32x32 matrix and apply the inverse on bytes in the same way the challenge code applies the forward operation).
As an aside - xor operations performed on bytes can be linear or not; they're not inherently non-linear. Whether xoring bytes is linear or not depends on our view of what the bits which make up the bytes mean. If the bytes are 8 bit positive integers then it's non-linear. If we consider the bits as coefficients of a polynomial over GF(2) - e.g. b[7]x^7 + b[6]x^6 + ... + b[0]x^0 then the bitwise xor of two bytes is linear. That's how CRCs (a type of linear checksum) are calculated and the maths behind LFSRs etc.
I wish that math teachers would show this video and say: "Learning math is important to do cool stuff like this!"
Plot twist : this is just for you to submit your CV
The real challenge is when Mario asks you do to it again, but this time, whitout any libs, using your own writen compiler for Assembly language targeting the original NES system.
no he wants you to write it so it can run on a abakus
I'd love to see the alternate solution that you found out. This rather interesting to watch, and shows even seemingly complex problems don't necessarily require overly complex solutions as long as you're able to think outside the box.
Could you do a video on Z3? Finally might be able to register that WinRAR.
From www.nerd.nintendo.com/files/HireMe
/*
The solutions to this challenge belong to different levels :
Level 1 : an iterative algorithm which typically takes more than a second to
find a solution (for any given output).
Most people stop here, which is fine, but if you want to go further, there is :
Level 2 : a non-iterative algorithm which typically takes less than a
millisecond to find a solution (for any given output).
Very few people have reached this level. But if you want to beat it completely,
there's yet another castle...
Level 3 : an algorithm which can provide any of the 2^128 solutions (for any
given output).
No-one has reached this level yet !
*/
maybe someone could use an SMT solver for level3. Model the bitvector equations and it will probably give one random solution. I'm sure there is a way by iteratively adding constraints to get more solutions, maybe all (?). I'm not an expert on solving problems with SMT, it was just an idea. For those interested "SAT/SMT by example" by Dennis Yurichev may be useful.
I reached a level 3 solution after continuing to work on my level 2 solution from the last video comments, I even got contact from the author of the challenge from Nintendo and he confirmed I was the first to get there so that's nice! I emailed LiveOverflow my solution but he hasn't got back to me yet, I guess he's busy.
I'm looking forward to the next video on this topic :)
@@binaryagenda I'm still working on my level 2 and people are already on level3
what those level mean?,
is what Liveoverflow did just a Level 1 solver?
I love Jupyter Notebook. I typically use it for data science. It's also very useful for some python visualization and other python operations.
I love how your intro is literally a live overflow visualized.
Do not down play yourself, that was pretty awesome to follow-you-through.
You don’t need to solve linear equations to get the input array if you have the output array, heres what you can do: so if you have the input array and run the code in the loop of the forward method once you get the out array which is the xor of bytes in the input array chosen according to a mask in the diffusion array, now if you have the output array lets say you want to get the first byte in the input array well if you can find a combination of masks in the diffusion array that xor together to give you 0x1 then xoring together the bytes in the output array that correspond to those masks will give you the first byte in the input array and so on, finding the masks that xor together to get you 0x1, 0x2, 0x4 ... took me about 5 min of brute force search and in they end I discovered something weird the masks that you need to get 0x1 were described by the value in the first mask in the diffusion array and so on, if anyone is interested i can explain further
From what I understand, for a given c_i, only a single diffusion value p_i is used to determine which bytes from d_i to XOR together. How did you come up with the approach of XORing values from the diffusion array together to get 0x1, 0x2, 0x4, 0x8, 0x10, etc.? Why does xor'ing the values corresponding to these combinations yield the i-th input value? I tested it myself and it's true that XORing the bytes in d corresponding to the indices of diffusion values in p that XOR together to yield 0x1, 0x2, 0x4, ... yields the first byte of c, the second byte of c, the third byte of c, etc. However I'm just wondering how you arrived at this conclusion? I'm clearly missing something since it seems to me the elements of the diffusion array are independent from one another when it comes to calculating c values. Many thanks in advance.
please note that in the real world you would never invert to solve a system of linear equations, you use something like gauss elimination instead since it‘s much more efficient owing to its better runtime complexity :)
interpolation scales with a degree of loss of accuracy over the real problem. What ninty says is "use a different aproach that hypotesis to solve this, it's the key of our work"
than*
Instead of using fancy math to reverse the diffusion step, I just xor'd all combinations of rows of the matrix until one was equal to 1, 2, 4, etc. (As xor'ing the values corresponding to these combinations would then yield the i-th input value.) After doing this for the first input value, I noticed that the "mask" of output values to xor was the same as the first entry in the diffusion array (i.e. the mask of input values to xor to receive the first output value). When the second value also matched, I tried doing the diffusion step twice on some input. And sure enough, after two diffusions the values were the same as the input again. So oddly enough, "diffusion" appeared to be its own inverse. Now, I could have obviously made some silly mistake. Can anyone confirm that this is actually the case?
I then gave up on brute forcing the 16^256 combinations of possible outputs, because I thought that even enumerating all of them without doing any other computations would take more time than the universe had left to live.
can confirm. the diffusion matrix is an involution i.e. its own inverse
I found out the same thing
Yep, I used this method too.
yup. this works
I did the same in my solution. Yes it works like this.
I always wonder if companies actually make these challenges just so they don't want to take the trouble of solving it. Then when you submit your answer they just take the code and hit you with a "We regret to inform you but we will not be proceeding with your application"
Whaaat, it is harder to desine those challenges as to solve them. Yeah it depends, this one is a mixture of easy and hard solveable puzzles
MathIsFun has a bit of a goofy name but the information it provides is super clear and helpful. Totally saved me on a couple of exams.
I didn't solve the challenge completely, but I rewrote the original algorithm in Haskell. Given that Haskell is purely functional, it also really brought the mathematical side of this algorithm to view. All in all a fun challenge and I enjoy your videos!
Your new studio setup looks stunning! A little bit of edge/back light on your left would be great though, right behind you
Oh yeah I definitely learned this math in 8th or 9th grade. Definitely yes I totally remember that
Well, in some schools they do teach matrixes in 8th or 9th class (my friend that was in math oriented school said they learned them). I learned them in 1st year in uni so 3 years later.
@@Animas42 In india this kind of maths was taught in 8th or 9th class and there are more advance versions of that as you move towards higher classes 😅😅
This looks like a simple code mapping, the mux selection just throws off the whole game, but honestly, any symbol can be identified for output at any position. If you expand out the bitstream of the initial input as positions instead of bits, then recreate the code as such in a DAG tree, pruning as you go through each round, you will find the endpoint will be a identification map. You want a letter, it tells you what bits to flip for it in that spot.
2:17
>what do you see here
me: logic gates?
>looks like the math that we learn in 8 grade
>this is a system of leaner equations
me: cries in bad math
Very very interesting. Whenever I see your videos, I really learn something new. Thanks dude, your channel subscription is so Worth it!! Great job dude!
Very nice!!! Since i've been watch the first video that you talk about this nintendo "hire.me" puzzle, I'm get curious and read something about algebra (on the same path to solve), looking for something like eigenvectors and eigenvalues, now i see that the solution method it's more different then I thought.
4:22 Funny story. I actually got that video (about firmware update) recommend this morning before this upload. How did you trick UA-cam to do that :D.
He used the same technique to reverse youtube's alghoritm
This is so cool! Currently taking a course in cryptography at uni and the course has a project about linear shift registers, and the tasks are very similar to this! Very nice
There was no need to separate bytes into bits, because the "diffusion" matrix itself only contains single bits, and is a perfectly valid invertible matrix over GF(2), and this is enough. "Linearity" has nothing to do with bitwise "xor", as it's not a unary operation... Inverse of a matrix does not exist when it is singular (determinant is zero), this is why your 3x3 GF(2) matrix example did not work.
Just brainstorming here
C[0] ^= D[0:32] * ((P[0] >> 0:32) & 1)
D[0:32] is a 32 element vector
P[0] >> 0:32 is a 32 element vector with P[0] bit shifted by index
((P[0] >> 0:32) & 1) does per element least-significant bit (LSB) on shifted P[0]
D[0:32] * ((P[0] >> 0:32) & 1) performs vector-vector multiplication, resulting in a scalar
C[0] ^= D[0:32] * ((P[0] >> 0:32) & 1) xors scalar with current index of C
Generalize the above.
From my understanding, it essentially masks each of the 32 bits of P[0] by D (forall i. D[i] * bit(P, i)), then applies an XOR at C[0]. TL;DR: C is the xor of itself and a mask D applied to P.
There should be a much faster solution to the xor part: you recognize that each integer in the diffusion array indicates how one byte from d is XORed onto each byte of c. However, this operation is the same for all bits of this byte of d. Therefore we notice something interesting when modifying d bitwise and applying the diffusion operation: When we change(XOR) the mth bit of the nth d, the nth diffusion integer is effectively XORed onto all the mth bits of c vertically.
From this, we recognize due to the nature of XOR, when changing the mth bit of both the element i and j of d, the XOR of the ith, and the jth diffusion integers is XORed onto all the mth bits of c vertically.
Because there are 32 diffusion operators and 32 bits, we should be able to find a combination that effectively maps directly onto c, and you can therefore effectively reverse the operation in linear time by solving the linear system of diffusion operators once and hardcoding the values into your program(or calculate it at compile time).
I came up with this by thinking for an hour or so about the problem, so it might run into complications during implementation. I have no time to implement that, but an interesting puzzle and I am just going to leave my thoughts here for anyone who wants to give it a go.
at 2:19
P,Q and R
SPQR
You should have implemented the GF2 version of Gaussian Elimination in C. Now that would be an exciting video.
approach would be to convert the system of equations portion and the store an array of bitvectors, one for each row of the matrix corresponding to that array. Then use bitwise elementary row operations. to invert.
I tried myself the challenge before watching this video. At the time I didn't find any code to find the inverse of a GF2 matrix. Maybe because I didn't know they were called GF2, I was searching for binary matrix.
I'll post the code of inverse Gaussian elimination soon in GitHub, it's quite simple
Computers usually don't invert matrices because it's numerically unstable. Instead, you usually find some smart trick that lets you write the matrix A on a different form. A simple example of this would be the LU decomposition.
So you've been hired?
Nintendo probably isn't that big of a challenge for him.
@@ArizeOW
Technically, the solution to this challenge isn't what he proposes. It's outlined in the program that you can solve it in 3 ways, and each with increasing difficulty.
From the code itself:
/*
The solutions to this challenge belong to different levels :
Level 1 : an iterative algorithm which typically takes more than a second to
find a solution (for any given output).
Most people stop here, which is fine, but if you want to go further, there is :
Level 2 : a non-iterative algorithm which typically takes less than a
millisecond to find a solution (for any given output).
Very few people have reached this level. But if you want to beat it completely,
there's yet another castle...
Level 3 : an algorithm which can provide any of the 2^128 solutions (for any
given output).
No-one has reached this level yet !
*/
On top of it, the solution would have to be packaged along with the source code, I'm guessing.
If the solution he proposes works exclusively for the "Hire me" string, then he's technically failing at lv1
@@artstrange3230 those comments were added after I made my video. And I don't know why you think my solution only finds "Hire me". The code at 11:42 sets the constraints for "Hire me" but could be set to anything else ;)
@@LiveOverflow
OH! Senpai has noticed me.
Well, good sir, I do *not* think your solution only finds "Hire me". I am merely stating an if clause, which is separate from my line of thought.
@@LiveOverflow it.s ok, im failing at lvl 0 which means im not even understanding the question itself :")))
I found a better solution (although not as fast as the non-iterative one advertised in the code comment). You can use the fact that only some input bytes impact a given final output byte to choose which byte to change in the next attempt of your brute force. Typically, when the diffusion has two 1 in binary for bits 2n and 2n+1 it means changing intermediate output byte 2n will also change 2n+1 but will not change the final output byte n, so don't try to change it. Maybe (probably) z3 is smart enough to detect it or maybe not, but in my case it made the solving much faster (I didn't let it complete without it but I thought it wouldn't considering the upper bound of 2^128).
I feel that using z3 is a bit cheating because I have no idea what crazy optimization it has internally and how smart it is. It make it feel like you solve the problem but may not really understand everything about it.
If you would to print the inverse linear transformation matrix you will also find out that it is inverse to itself :)
Also, there is a way to greatly improve the performance of the linear transformation using lookup tables due to its linear nature (such things are done in AES optimizations when you choose speed over memory usage).
Also, you can slightly optimize the input selection process by just choosing a random 16 bytes for the input, and than taking a valid, random value from inside the sbox (so you know it obviously has an inverse value, since you chose it from the sbox itself).
ist mir echt zu anstrengend, aber geil, dass du es gelöst hast
You had me at "math"
It's basically the same way how I solved it (see my comment in the last video). My code is still brute force, (although maybe slightly more efficient, takes about 5 minutes). Someone in the last video commented a very good solution exploiting the internal structure of confusion array that can solve this problem very efficiently (constant time) for any 16 byte output.
I'm still trying to do this, maybe if you bring the sbox operation to the matrix realm and precompute the whole loop and obtain a single matrix you can do it in one step.
@@lab-at-homeI thought about that approach, but the problem is that sbox is not a one-to-one function, which means it's impossible to find the inverse for that (Imagine f(x)=x^2, for each x, there is an unambiguous value for it. However, if we try to find the inverse for it, say for what value x such that f(x) = 1? Both x=-1 and x=1 satisfies the condition, but we don't know which one exactly, confusion matrix in this case is the same deal). You might be tempted to think that we can try to guess all possible values, but the fact that it iterates for 256 rounds makes it very difficult (i.e. very likely to find a value that you cannot reverse the sbox operation). You can verify this fact by using a random 32 byte value as input after the last diffusion round and see how far you can go without hitting a dead end.
@@yuxin7440 I know, I made a video about it ua-cam.com/video/A5uPVXDY8tU/v-deo.html :D . No matter what solution you make, it is going to have some free variable, since there are multiple inputs that outputs "Hire me!!!!!!!!\x0" (I got more then 200 in some minutes of calculation). The end matrix will have a bunch of free variables in it, after all the calculations you just need to choose values for this free variables. In a simplified example, lets suppose that you make the precomputation and the resulting matrix is [[x,0],[0,1]], since the problem is in GF(256), x can be from 0-255. Choosing a x (lets say x=1 to make it easy to reverse) would give us one possible solution, any other value for x (that match some criteria like the inversability of the matrix) would give another correct solution. This is the only way I can see to achieve constant time (and level 2), do you have any other ideas?
@@lab-at-home Here is my solution: github.com/lewisxy/hireme-challenge, which is NOT a constant time solution. The constant time solution does not attempt to reverse the operation. It simply constructs the input based on pre-computed lookup table. Apparently there is a specific set of bytes that are closed under confusion lookup and diffusion (i.e. like a subspace of GF(256)). If you just happen to find these bytes, you can simply undo all operations confusion and diffusion as if it is invertible. And if you are lucky, the subspace of at least 16 bytes will allow you to construct any of 256 bytes, which means you can compute a 32 byte input for all possible 16 byte output in constant time. The problem is how to find such subspace. There is a very good comment in the first part video talking about this approach (unfortunately I don't know how to get the link to a specific comment in a video, so you will need to find that)
I wish i had as bright and determined colleagues as you are! Great job and nicely explained.
By the way, NERD trolled all of us. The inverse of the diffusion part is ... the diffusion part itself!
I was hate math since i start studying engineering but now , after i watched this video , i hated it even more.
i feel you bro.
Math is a subject that if you drop out of the loop at any time in your education, you have to do a lot of extra work to get back into it. This is one of the reasons why many people hate math, because they cannot just open a math book and read to learn. You have to continuously work on it.
Solving with matrices are also used for FFTs, quite possibly the most useful algorithm of modern society.
Nice Ive been wating for this video =)
Im waiting for nintendo to hire him xdd
They won't his solution is slow and he missed the GF2 part.
@@WarrenBey jk
@@adytm You didn't know
@@mreazl6227 what is that i dont know?
Great job on solving and explaining it! I have a small suggestion though... I understand that this is a single use kind of code and maintainability is not a big concern here. However given the educational value of your videos could you clean your code a bit? I mean like 's1' for even stuff and 's2' for odd stuff... I didn't want to be rude, but I hope my suggestion could help you make even better content! Keep it up! I really enjoy your channel!
Great solution! I would not have been able to solve it, at least not this way. Good job!
Well the problem is to even know that Sage , Z3 and so exists my approach would properly been trying to program my own matrix system. You don't learn such stuff in school or even university except you take a modul in encoding an such stuff. The most fanciest stuff related to work I ever programmed was a function which analyse matching pattern between 2 string to filter things out which are different. In studium yes I did program an encoder as duty project you know it f... up when you read c[p[i]][u[j]][m[i-k]]. 3d array and your indizies are in another array.
Hey great video waiting for it.
Ich wusste nicht dass du Deutsch bist sehr cool👍 tolle Videos
If you have python printing stuff, it would take more time to execute the whole code for some reasons. It's better not to use print() when bruteforcing.
That’s why I don’t do that ;)
@@LiveOverflow You should try Google Colab, it is completely free jupyter notebook and has NVIDIA Tesla GPU's for acceleration. Great for accelerated brute-forcing!
Reason is I/O
well, this is a lot nicer than the idea I had...
So he's didn't reversed anything. He just came up with really powerful way to optimize brute force
It's basically a cryptographic algorithm, without a weakness in the algorithm this is pretty much the most appropriate way. (That's just my opinion)
@@taba1950 Every algorithm has it's weakness :)
you rate cryptographic algorithms on how long they take to brute force. If you can sufficiently reduce the length of time it takes to brute-force (even to the order of years) the algorithm is no longer effective and thus has been broken.
Loved this video!
If I wanted to be a cryptographer, then yes, math matters. In most software engineering jobs today, it's about how well you can architect a system to increase productivity of your team and reduce future maintenance costs rather than if you can reverse hack an encryption algorithm.
Have you had a different experience? Is this math used in your day to day job?
The Course This Math Is Taught In Is Linear Algebra
In college!
Meh, kind of. Typically you don't do finite field arithmetic in linear algebra.
In my country we learn matrix math in high school.
Great to see you utilizing jupyter. Notebooks are rather old now, the kool kids use Jupyter Lab instead (jupyter notebook with a skin and addons)
omg I never heard of it
My Java solution (lvl 1) wihout using any library github.com/razoralv89/nintendohiremesolutionjava. Big thanks to @LiveOverflow for the inspiration.
Was refreshing just for this.
Same name
how to you find out about such challenges early enough to participate?
LiveOverflow: "This looks like the math you had to learn in, like, the 8th or 9th grade or so"
Me, some PHP webdeveloper schmuck that does not even recognize basic maths: "Why yes of course. I had a fluke it would be linear algebra all along since part 1, kudos LiveOverflow, kudos"
Story of my life ladies and gentlemen :D
Nintendo hire him.
beautiful!!!!!
Great second video!
I don't understand a thing.. but I keep watching the vids~
I did a bit of matrix maths in year 10
Someone at Nintendo is probably annoyed they have to make a new challenge now
Other people online have posted solutions. They don't just automatically hire people if they solve this, it's a sorta foot in the door type thing
@@awk4722 yeah I'm sure a company like Nintendo has plenty of tests like this just waiting in queue
Pausing at 2:11, because I think that might have been the epiphany I needed. At least to get it narrower...
Me at 4am watching this
I completely understand nothing that is being presented and im ok with that
Th0mas the savage
Execllent !
would love to see you revisit this for another pass at making it faster
Wait, so what would the vulnerability be in this case, next time don't use matrices with inverse ?
I think this is more like a backdoor. An algorithm that also has an algorithm to reverse it is usually intentional. If it wasn't reversible, there would be no purpose because you could just use an existing hashing algorithm. This is more like asymmetric encryption where the client has a simple deterministic decryption algorithm (forward) and the host would use this complex encryption algorithm to generate a valid input for the client to use.
shouldnt this be pretty simple with python angr?
Would another way of solving it use the XOR proporties? Where A ^ A = 0 and A ^ 0 = A ?
from the site, there is apparently a non-iterative solution... that sounds crazy.
and level 3? what is this even? 2^128 is the square root of possible inputs of the function. it's also a number in the 38 digits which makes it probably not so fun to calculate...
but just to let it sink in - there are ~3.4*10^38 valid solutions to this problem, and we can't just stumble across one randomly, FML this sounds stupid.
my initial idea was to make some kind of inverse for the diffusion array itself but I'm not smart enough for this sort of thing. especially when I'm trying this at 1am.
level 3 is the inverse of level 2 against level 1
@abdulabar4964 and the sky is blue. That doesn't make this any less impressive.
2:21 must a new record for advert placement (this after getting 20sec of unskippable adverts pre-roll). Then 13 unskippable sec of ads 6:40 and 8:20. 22sec at 14:20. Someone stop Google before all videos become nothing but adverts.
Adblock
PiHole. If you wanna support the content, don't watch ads. They're not paying the creators like they used to.
"What do you see here?"
*proceds to see ads* :o
how fast has to be 3rd level program to show all solutions?
2:17 - What did I see there? That moment I saw grammarly ad.. :D
Could you explain the levels please. This was Level 1, right? Or is this Level 2? What is Level 3?
l1 because it tries lots of paths
This was level 1, he bruteforced one solution.
@@cgmarch2359 Thank you :)
@@marcuspeixoto4871 Thank you :)
linear algebra was, mostly, college for me in the US
shouldn't out[i] be always out*[0] ??
i wasn't taught about systems of equations until college
recursive with dictionary for repetitive values.
Discrete math XOR computer systems (embedded) engineering = this equation
and level 3 is !idea
Sagst du absichtlich "we have now a (...)"? Klingt im englischen sehr antiquiert, (besonders temporale) Adverbien zwischen ein Verb und ein Objekt zu schieben.
hat er bestimmt nur wortwörtlich aus dem deutschen übersetzt. "wir haben jetzt ein..." klingt schließlich richtig.
Reverse s-box function! :)
I looked on their website and the algorithm should only take about one second to find the solution o_o
I was very confused when I saw the german texts XD
I don't do programming so I didn't really understand a whole lot but it was interesting nonetheless.
Is it another world
Not understand everything , but enjoy watching
How do bovines do math? With a cowculator
What is your intro/outro music?
Can you give me hard encryption simple script.
Maths son!, maths son!
nintendo HIRE THIS MAN
How is that highschool math? This is the math I learned in 4th or maybe 5th grade.
You didnt go to gymnasium did you?
Wow, only 1 in 5 people went onto the second video?
please make another video