@@IamLupo right. I think the biggest problem is that this isn't my domain, I'm usually just creating plots for work (data science) and not twiddling bits
A few observations regarding that "diffusion array": 1. The for-k loop is computing a "sum" (mathematicians think of bitwise-xor as a special kind of addition, since it's just addition without carry, and it has many of the same properties) of multiplication pairs. That makes it a dot product! 2. The for-j loop is computing different items in the output array, changing only the constant vector and not the input vector. So it's really doing a bunch of parallel dot products - or a matrix transform. So that "diffusion array" is *really* a "diffusion matrix" - 32x32 with binary entries. :D The inverse of a matrix transform is a transform using the inverse matrix, so you need to find that inverse matrix. First see if the matrix is orthogonal: it must be square (32x32 - yep), its rows must be normal to each other (dot product of every row against every other row is 0 - remember, you must use XOR instead of ADD in your dot products), and its rows must be unitary (all rows' dot product against themselves is 1). If it's orthogonal, the inverse is simply the transpose. If not, it may still have an inverse, but you'll have to try something else. Hope this helps!
@@AJMansfield1 Heck yeah! You got me curious because you didn't say "orthogonal" so I loaded up the array into Python to take a look, and indeed it isn't orthogonal (but the rows/columns ARE unitary). np.linalg.inv doesn't choke on it, so it is invertible, but inv doesn't perform the inversion over GF(2). Which inversion method did you use? Gauss-Jordan?
@@forloop7713 lol I was literally complaining a few weeks ago that I'd never have any use for linear algebra. This is the closest I've gotten to actually opening my textbook for something other than homework.
@@MadDawg010 Cryptography (and similarly, coding theory), quantum computing, and computer graphics are pretty heavy in linear algebra. I don't really see it being used much elsewhere in computing, so you might be fine if you end up forgetting your linalg homework, depending on what you end up doing. (Though I'd strongly argue that linalg is still good for your brain, even if you don't ever use it for something practical.)
I really love how you showed your thought process in this video. Also the constant reminders that saying the stuff out loud, doesn't mean you know how to do it made me feel less alone and lost 🤣
Hahahah I watched till 9:00 , and then thought it was easy so I paused the video and tried it out. I got some breakthrough but not enough to decode everything and then I went back here, and turns out you won't let me give up ! Thank you ! This challenge is amazing, I'll make sure to suggest it to people in the future
Come on guys, you can translate this puzzle in every language wich has an XOR operator xD which has probably 90% of all programing languages. Bytecode is also important xD But you've got my point.
I remember tackling this problem 6 years ago and I felt back then that I wasn't even near to the solution, but after watching this now I'm thinking that maybe I should have kept trying
Hey, awesome video! I really like how it's not just about the challenge, but also about how you approached this problem. And it's reassuring to hear that it took even you a while to solve this, and that it's ok to just take a break sometimes :)
If I had time to solve this, I would definitely try. But I have to work on my school projects and learn for exams so even if I would love to dig deeper, I can't. And I am afraid if I did start, I wouldn't make it until next week. But I am thrilled for the solution, and I can only guess what it could be. As someone already stated, linear algebra is the way to go. I really wish I had the time to do it.
After about 10 hours, I finally managed to solve this puzzle with minimum hints from others. It was a lot of fun! TLDR warning! spoiler warning! You probably don't want to read if you want to solve it by yourself. 1. The puzzle consists of 3 parts, confusion (lookup table replacement), diffusion (double for-loop), and compression (the last step, compress 32 bytes to 16 bytes). The output can be written as compression(diffusion(confusion(...diffusion(confusion(input)))...))). There are 256 alternating rounds of confusion and diffusion. And my idea at a high level is to undo all these operations one-by-one and thus compute the input from a given output. 2. Diffusion is the easiest part as it's essentially a matrix multiplication (32x32 binary matrix) (thanks to the comment here that made me realized that), and that matrix happens to be invertible. So I write an algorithm to find the inverse matrix (using Gaussian-Jordan elimination, basically how you find inverse by hand, except replacing all addition with xor). 3. The confusion array is actually 2 tables, the confusion part uses only the first half, and the compression part uses both. 4. Compression is also pretty straight-forward. However, since it is a 32-byte to 16-byte function, a particular output can have many possible inputs, 2^128 to be exact. To find a particular 32-byte input for a given output, you can just loop over the first table, xor the byte in output with that value, then try to find the result in the second table. Because compression is an element-wise operation, turning 2 bytes to 1 byte, I end up generating a lookup table for each output byte, and there are exactly 256 pairs of values from the 2 tables for each byte. 5. The confusion part is the most difficult part of the entire puzzle. I first assumed it's invertible just as diffusion part. The puzzle would be trivial if it is invertible. Unfortunately, it's not a one-to-one function, which means for a particular byte output, you cannot find a unique input (or even worst, an input). At this point, I was stuck, as I know most symmetrical encryption algorithms either use Feistel structure and one-way-function or reversible S-P (confusion-diffusion) network, which this cipher did neither. I tried to explore some internal properties of the cipher (such as whether commuting the diffusion and confusion operation produce the same output) but get no result. 6. In the end, I decided to brute force it. In each attempt of undoing confusion, although it's possible that it cannot proceed (i.e. no input mapped to a particular output), it's also possible that there are more than 1 possibilities (i.e. more than 1 input mapped to a particular output). Therefore, for a given valid input for the first round of undoing confusion, I use a recursive-backtracking algorithm to iterate through all possibilities and stop either when it reaches the end (i.e. after 256 rounds) or get stuck in every possible path. In the case it gets stuck, I just change an input (remember there is 2^128 possible input that produces a particular 16-byte output at compression). 7. Honestly, I did not expect this to work, as the recursive backtracking algorithm has an exponential worst-case complexity, which may take forever to run. But surprisingly, it's able to find a random input after about 1-2 minutes on average. So I give it a try, and after about 5 minutes, it produced the correct output! Warning spoiler: my answer is the following (base64 encoded, do not decode it if you want to attempt it yourself): Mzc1NWQ2ZmFiMjNlNTI1OWVmOTU3NmJhMDdiZjM0YWUwYzFlMzc5ZTI4MDkwZGQ3NzJmYmM5MDcxODA3MzgzOA== 8. I am pretty sure this is nowhere near the best solution, as it takes a pretty long time. But on the bright side, given enough time, this algorithm can find all possible inputs for a given output possibly more efficiently than brute-force the entire input space (2^256). And more importantly, it makes almost no assumption about the confusion array, which makes it generalizable. I think a more efficient algorithm (constant time) might involve exploiting some internal properties of this particular confusion array. I am too tired (and lazy) to explore that, but I am happy to hear that if anyone which to tell me. Happy coding! PS: I might release my source code (in Python) if anyone needs it, but we will see.
I actually found this challenge recently when I looked up NERD when reading about how Nintendo used emulation for Mario 3D All-Stars. I actually considered solving it, but I was too busy. Very cool to see this one explained in a video.
The "diffusion" step is just a linear transform (think of a 32x32 matrix over GF(2)) that you might be able to simply reverse by computing the inverse matrix. As a side note: I wouldn't take a job with these sorts of "challenges." For starters, they condescending and produced by the sort of people you don't want to work for. Second, if you want to do real DRM (ugh why?) use public key crypto with embedded root of trust certs/etc. You don't need some gibberish off-spec algorithm like this.
I think videos like this are important. In the beginning it feels like every other skilled programmer KNOWS what to do from the get go. But every project requires figuring out. The more complex the problem the more figuring out.
This stuff is way beyond me but I really like the fact that you gave the viewers the diffucult route and won't spoil them with your answer right away. Can't wait for the second Video.
Without diving too deep into it, I'd first deobfuscate the (diff[j]>>k)&1 . Since it is constant, we can replace it with a bool array. I think having that clear array would help a bit. Then I'd take note of the indexes that result in 1, and maybe find a pattern. But again, that's just at first glance. I'll try it tomorrow!
I work for a major tech company. I just make REST services. Spring. Flask. Etc. My team make lot of money just doing CRUD stuff that is, for the most part, handled with just annotations in the code. My coworker just wires Java beans together in XML. He only codes the unit tests related to his wiring up. Just takes the precoded beans and wires them into a batch processer class. Seeing this makes me feel so guilty. There are programmers who tackle more advance stuff like this daily and probably make the same as me and my team who just type in @entity, @table, @id, OK done.
@@chriser5146 Bachelor's in Comp Sci from a US university. Electives in college, which was a bit ago, were focused on architecture and low level programming so you'd think I'd remember some things about how to attack this stuff, but nope! haha. Salary- $125k. Companies near me really only care about how knowledgeable you are on frameworks and APIs now a days. They dont care how many leetcode algorithm problems you can do if you don't know some QT or Spring, etc.
@@1UpBebop Sounds both pretty nice but then again a bit simple? Coupled with the 125k... sounds a bit much for the type of work you described... Im a first year in computer sciences from austria and will very likely start working for some company immediately, maybe as some sort of project manager since thats a heavy fopcus in my studies. Estimated salary will maybe get to be 80k on start so im not sure if you got really lucky with your job or i have no idea what my future will look like. thanks for sharing the info :)
I like solving problems that have many dead ends, it makes solving the problem so much more satisfying and you learn things along the way. Could just be me but I've found watching what the stack is doing to be a nice visual aid. There's been a few albeit light encryption schemes I've gotten around just by looking at the stack and related chunks of memory.
Woooow so cool It's amazing how many puzzles could people make with programming and the best thing is everyone has his own way to solve it And i really love the C# Language
the diffusion is a 32x32 matrix, the code is doing matrix multiplication output=input*(diffusion^256) over abel group of {2^8, xor}, it will can be cracked by finding the reverse matrix of the diffusion, input=output*(reverse(diffusion)^256)
Spoiler (not the literal answer but a good idea) . . . . . . . . One of the first things that comes to my mind as someone with a mathematical background is that the loop that does a bunch of xors reminds me of a matrix multiplication. In fact it *can* be expressed as a matrix multiplication in some finite field in which addition corresponds to xor. So I think some tools from linear algebra would be helpful.
I love how you have a similar approach than I do when it comes to decluttering and simplifying code to reverse engineer it. I don't know what kind of God programmers can just read this and wrap their head around it.
If for a job interview, they asked you to show how you would defend against bear attack, you know that, at a point or another, your job will involve running away from bloodthirtsy bear... runaway from that codebase
Mildly math literate person here, the thing you described in your video where you used linear algebra works here too, but instead of it being about linear dependence, it's about linear maps. If you look at the data the same way, then the part where all the XORing happens just implements a linear operator on the space, with diffusion essentially being the matrix that specifies which linear operator it is. If it's invertible, then that means that another value for diffusion would cause the same process to reverse itself. I'm not sure how viable it is to make the computations necessary, I don't think checking if the operator is invertible would be computationally difficult, but I don't know how good our algorithms our for the process of actually inverting it (computing the new value of diffusion). I'm severely sleep deprived right now, so what I said may not be very well put together (though the essential idea I had is true, I'm sure about that one, but it's only helpful if the operator turns out to be invertible), but I'll keep looking into it after I sleep when I can think better.
What you described in the last section was a linear code. Giving a linear decryption function would be equivalent to computing the left inverse of a Boolean matrix. There are various fast algorithms for doing so.
You can draw dependent relationships for all the bits in the diffusion that equal 1. The bits that equal zero cannot affect the input[j]. You can represent this as a 32x32 matrix and if this matrix is triangular, or close to it the problem can be reduced and brute forced
Its funny how just a couple for loops can contain so much complexity with figuring out what exactly it is doing. Of course, an S-box and encryption algorithms are meant to be confusing, and hard to figure out.
I thought him explaining the code would be helpful and that's why I kept watching, but I literally had no idea what he was talking about when breaking down the code. Guess I'll look into a different hobby.
Notice a line in bits in diffusion (from least 1 to greatest 8). If you align it as a 31 bit array, there are visible lines by which bytes are carried over xorring input in the first cycle. It doesn't look random Confusion array effectively makes a 8 bit input 16 bit and then in the last cycle it's back to 8 bit
Here I am, taking Programming II at my local community college, not knowing a damn thing what is going on in this video. I don't think I will ever find a job at this point. =(
You will, this guys has many many years on you working in IT, also, its a cool video so youtube does tend to reccomend things that look really really advanced, and this is, its not just you, 99.999% of people watching this video might aswell be watching it in another language for all they know. Like watching someone juggle 12 balls, you cant do it yourself but its cool to watch
I would like to highlight that walking the dog and sleeping well are key for this kind of problem solving (and the deep-thinking and knowledge database is obviously a plus)
"But I am lazy" This, or "I should make this part better, but I will improve it later" are actually common coding steps. Prioritizing what code to work on is important, and some things will change based on how other things end up being implemented, so may not be good to fully flesh out at the start.
I might be wrong but the way you described the xor-chaining at 15:30 it sounds to me it should be solvable by using backtrack. Same concept used to create a sudoku solver.
Im not a cipher analyst, just a programer. But to me the complexity of this algorithm caused by two things 1) substitution 2) Outcanceling of bytes 3) the mixture of it
So, the first j-loop is a substitution cypher, and the following j-k-loop is, as pointed out by others in the comments, a vector point product between the above input and the diffusion vector, and then the last i-loop adds extra diffusion with it's self (sort of). And all of these is done 256 times in order to add more confusion, I think. So, the backward function will have to break these three cyphers backwards, 256 times. The most interesting one is the j-k-loop one, as pointed out by others, you'll have to find an inverse matrix, but my guess is that this matrix is actually (out matrix)(diffusion matrix), and that these matrices products are reflective.
Mine essentially used histograms to associate the output and input of the confusion array, then recursively searching down the 256 layers for valid mappings. The other steps are invertible with some basic for loops, so the bulk of the effort is detecting which mappings are valid at each recursion step.
u made it! remember the time in 2012 when u teached our class of business information science fools (ibm class 2011) to develope "moorhuhn" in böblingen - big shoutout
What sort of topics do I need to learn to even attempt this problem? Im only a first year computer science student but I want to try dipping my feet into deep waters; got a lot of free time right now...
Reverse-ing the function is probably what they want since they named it forward but I wish you tried reverse-ing the input array just to see if there's another clue
I understand propabely 5% of the progrmming-stuff and even less of the procedure how to solve such a puzzle. I still like your videos because i feel more inteligent after watching them :D Love your videos
@@roby2k14 They are two of the most pivotal inventions in our field shaping our modern infrastructure and playing a crucial role in virtually every system be it directly or indirectly. Anyone in this field benefits considerably from knowing these two languages thus it is a travesty when people are pushed away from them. When two languages with contradictory philosophies are conflated the result is impossible to understand, needlessly difficult to use, and impossible to appreciate which scares newcomers away from not only where they have experienced the language, but also information technology in general. Be it web dev, games programming, hacking, or anything in-between: the lessons from these languages matter so conflating them therefore obfuscating those lessons worsens our field.
@@TylerStOnge-rz4os okay but why is .cpp file being written in c something bad? you can compile it like u would compile a .c file? or is there any difference? I mean they're pretty similar in some aspects, I dont see the problem :| or not a big deal (for me)
@@roby2k14 The philosophy of C is to write, in a high level (just above assembly), what the computer should do, effectively being portable assembly. C++ on the other hand is about creating a domain specific language for the problem at hand to always be at the correct level of abstraction for that particular problem. One is all about removing abstraction and the other is about creating it. Sure it compiles but that does not make it C++, hence effectively telling people "hey this code is C++" conflates the two and pretends as though they are the same language and you write code for them in the same way which is objectively not true. They have similar syntax but are different in virtually everything else which is why they offer different lessons.
@@chyza2012 There is much, much more to a language than its syntax. Much of C will work in Java, C#, Javascript, so on and so forth, yet these are obviously very different to C. The code provided is _not_ C++, but it is C. A language comes with its standard library, conventions, idioms, et cetera and the code here did not follow those at all hence just because it would compile with a C++ compiler does not mean it is C++. There's an entire subfield on this called software engineering which examines how something happening to work does not mean it is a correct; there is more to code than the binary.
This video title is clickbait and not clickbait at the same time.
MIND BLOWN
@Steve nice one :D
..and also doesn’t like it
@Steve likes and does not at the same time 😎
r/InclusiveOr
Perfect intro to a problem that many of us theoretically can solve but no one has the guts of tackling
You mean like this? github.com/IamLupo/Nintendo-HireMe
@@IamLupo yup that's the solution. He explains his solutions pretty bad though, so I haven't mentally solved the problem yet
@@Yaxqb Well he did this to motivate you to solve it on your own and then that he could make a second video where he accually solves it
@@IamLupo right. I think the biggest problem is that this isn't my domain, I'm usually just creating plots for work (data science) and not twiddling bits
Could not have said this better myself
"but I am lazy..."
The source for all my solutions.
And half my problems
i hate getting lazy I would have been a millionaire I'f I wasnt lazy
Next week: *This is how i got a DMCA from nintendo.*
(as an ex-millionaire)
Ex-google developer
FireMe.cpp
HarvestMe.ccp
@@thetruth9807 The ccp agrees
process returned 0
@@gchinmayvarma9030 compile error, expected ; at line 69
I laughed a bit too hard at this
Never clicked so fast, but that was because I miss read the title
I thought it was "Nintendo Hired me!!!!!"
Love the vids! keep em up
yep same LMAO
should it be "Nintendid hire me" ?
@@bankaa9293 LMAO I read that while being busy and you Sir got me again :D
„Eat children!“ ... Sorry, „Eat, children!“
A few observations regarding that "diffusion array":
1. The for-k loop is computing a "sum" (mathematicians think of bitwise-xor as a special kind of addition, since it's just addition without carry, and it has many of the same properties) of multiplication pairs. That makes it a dot product!
2. The for-j loop is computing different items in the output array, changing only the constant vector and not the input vector. So it's really doing a bunch of parallel dot products - or a matrix transform.
So that "diffusion array" is *really* a "diffusion matrix" - 32x32 with binary entries. :D
The inverse of a matrix transform is a transform using the inverse matrix, so you need to find that inverse matrix. First see if the matrix is orthogonal: it must be square (32x32 - yep), its rows must be normal to each other (dot product of every row against every other row is 0 - remember, you must use XOR instead of ADD in your dot products), and its rows must be unitary (all rows' dot product against themselves is 1). If it's orthogonal, the inverse is simply the transpose. If not, it may still have an inverse, but you'll have to try something else.
Hope this helps!
Real life application of linear algebra
I can verify that the diffusion matrix is invertible, as I just wrote a script that successfully inverted it.
@@AJMansfield1 Heck yeah! You got me curious because you didn't say "orthogonal" so I loaded up the array into Python to take a look, and indeed it isn't orthogonal (but the rows/columns ARE unitary). np.linalg.inv doesn't choke on it, so it is invertible, but inv doesn't perform the inversion over GF(2).
Which inversion method did you use? Gauss-Jordan?
@@forloop7713 lol I was literally complaining a few weeks ago that I'd never have any use for linear algebra. This is the closest I've gotten to actually opening my textbook for something other than homework.
@@MadDawg010 Cryptography (and similarly, coding theory), quantum computing, and computer graphics are pretty heavy in linear algebra. I don't really see it being used much elsewhere in computing, so you might be fine if you end up forgetting your linalg homework, depending on what you end up doing. (Though I'd strongly argue that linalg is still good for your brain, even if you don't ever use it for something practical.)
I would just change the code in //change only this: to print(“hire me”) and enjoy the job
Nice
*Nintendo:* We have an opening for janitor...
haha
Where would you get that function from?
@@CTimmerman void print(msg) {
cout
@@eness379 error: expected '(' for function-style cast or type construction
This is a hidden message. He's stuck working as a hacker in North Korea.
sdounmg oger
@@_vsnwprintf_s_l watching live overflow? cringe.
Redstar LUL
Yep. I've decrypted the message. It reads "I've been forced to work for North Korea intelligence agencies. Please help by sending this to the CIA."
I think it's morse code
I really love how you showed your thought process in this video. Also the constant reminders that saying the stuff out loud, doesn't mean you know how to do it made me feel less alone and lost 🤣
It's people like this, giving clues but not answers, that helps make the career path of security a better place.
@Fuzzy Pixelz updated wording
Hahahah I watched till 9:00 , and then thought it was easy so I paused the video and tried it out. I got some breakthrough but not enough to decode everything and then I went back here, and turns out you won't let me give up ! Thank you ! This challenge is amazing, I'll make sure to suggest it to people in the future
Me : cout
i know just enough c++ to lol at this
@@connorkillmice me too
Come on guys, you can translate this puzzle in every language wich has an XOR operator xD which has probably 90% of all programing languages. Bytecode is also important xD But you've got my point.
@@connorkillmice I just started with it and know it already
@@brennethd5391 nice
What we're taught in school:- *"Inp stands for input and out stands for output"*
What comes in exams:-
Who tf teaches that????
@@HandledToaster2 yeah I also never heard "inp"
Switch school dude.
Michael Cera applies for a job at Nintendo (2020, colourised)
Real
I remember tackling this problem 6 years ago and I felt back then that I wasn't even near to the solution, but after watching this now I'm thinking that maybe I should have kept trying
Hey, awesome video! I really like how it's not just about the challenge, but also about how you approached this problem. And it's reassuring to hear that it took even you a while to solve this, and that it's ok to just take a break sometimes :)
If I had time to solve this, I would definitely try. But I have to work on my school projects and learn for exams so even if I would love to dig deeper, I can't. And I am afraid if I did start, I wouldn't make it until next week. But I am thrilled for the solution, and I can only guess what it could be. As someone already stated, linear algebra is the way to go. I really wish I had the time to do it.
6:03 "...Shannon's property of Confusion." would have been nice to hear, considering it's the Confusion array
"nothing in my brain clicked" - if conf[inp[i]] is odd, xor, otherwise skip it? no?
After about 10 hours, I finally managed to solve this puzzle with minimum hints from others. It was a lot of fun!
TLDR warning! spoiler warning! You probably don't want to read if you want to solve it by yourself.
1. The puzzle consists of 3 parts, confusion (lookup table replacement), diffusion (double for-loop), and compression (the last step, compress 32 bytes to 16 bytes). The output can be written as compression(diffusion(confusion(...diffusion(confusion(input)))...))). There are 256 alternating rounds of confusion and diffusion. And my idea at a high level is to undo all these operations one-by-one and thus compute the input from a given output.
2. Diffusion is the easiest part as it's essentially a matrix multiplication (32x32 binary matrix) (thanks to the comment here that made me realized that), and that matrix happens to be invertible. So I write an algorithm to find the inverse matrix (using Gaussian-Jordan elimination, basically how you find inverse by hand, except replacing all addition with xor).
3. The confusion array is actually 2 tables, the confusion part uses only the first half, and the compression part uses both.
4. Compression is also pretty straight-forward. However, since it is a 32-byte to 16-byte function, a particular output can have many possible inputs, 2^128 to be exact. To find a particular 32-byte input for a given output, you can just loop over the first table, xor the byte in output with that value, then try to find the result in the second table. Because compression is an element-wise operation, turning 2 bytes to 1 byte, I end up generating a lookup table for each output byte, and there are exactly 256 pairs of values from the 2 tables for each byte.
5. The confusion part is the most difficult part of the entire puzzle. I first assumed it's invertible just as diffusion part. The puzzle would be trivial if it is invertible. Unfortunately, it's not a one-to-one function, which means for a particular byte output, you cannot find a unique input (or even worst, an input). At this point, I was stuck, as I know most symmetrical encryption algorithms either use Feistel structure and one-way-function or reversible S-P (confusion-diffusion) network, which this cipher did neither. I tried to explore some internal properties of the cipher (such as whether commuting the diffusion and confusion operation produce the same output) but get no result.
6. In the end, I decided to brute force it. In each attempt of undoing confusion, although it's possible that it cannot proceed (i.e. no input mapped to a particular output), it's also possible that there are more than 1 possibilities (i.e. more than 1 input mapped to a particular output). Therefore, for a given valid input for the first round of undoing confusion, I use a recursive-backtracking algorithm to iterate through all possibilities and stop either when it reaches the end (i.e. after 256 rounds) or get stuck in every possible path. In the case it gets stuck, I just change an input (remember there is 2^128 possible input that produces a particular 16-byte output at compression).
7. Honestly, I did not expect this to work, as the recursive backtracking algorithm has an exponential worst-case complexity, which may take forever to run. But surprisingly, it's able to find a random input after about 1-2 minutes on average. So I give it a try, and after about 5 minutes, it produced the correct output! Warning spoiler: my answer is the following (base64 encoded, do not decode it if you want to attempt it yourself): Mzc1NWQ2ZmFiMjNlNTI1OWVmOTU3NmJhMDdiZjM0YWUwYzFlMzc5ZTI4MDkwZGQ3NzJmYmM5MDcxODA3MzgzOA==
8. I am pretty sure this is nowhere near the best solution, as it takes a pretty long time. But on the bright side, given enough time, this algorithm can find all possible inputs for a given output possibly more efficiently than brute-force the entire input space (2^256). And more importantly, it makes almost no assumption about the confusion array, which makes it generalizable. I think a more efficient algorithm (constant time) might involve exploiting some internal properties of this particular confusion array. I am too tired (and lazy) to explore that, but I am happy to hear that if anyone which to tell me.
Happy coding!
PS: I might release my source code (in Python) if anyone needs it, but we will see.
Thinking about trying to implement this approach in F# as I’ve been meaning to play with that language.
It is my furst time hearing someone say key-gun-me, I always say key-Gen-me as it is key generate me
Did sound like gen imo
Maybe it's because I'm German too? xD
Same as your "furst"
@@strubenh7644 I not even going to edit that
@@KnightOfEvil English "first" does sound surprisingly similar to the German noble title "Fürst" xD
@@Ikxi Totally intentional ofcourse
Great job explaining your thought process of how you approach the problem.
Me pretending to know anything that is happening
I don't have the mental fortitude to watch the video to the end, let alone solve this problem myself.
I actually found this challenge recently when I looked up NERD when reading about how Nintendo used emulation for Mario 3D All-Stars. I actually considered solving it, but I was too busy. Very cool to see this one explained in a video.
"CTF but it's actually a competitive programming lecture"
The "diffusion" step is just a linear transform (think of a 32x32 matrix over GF(2)) that you might be able to simply reverse by computing the inverse matrix.
As a side note: I wouldn't take a job with these sorts of "challenges." For starters, they condescending and produced by the sort of people you don't want to work for. Second, if you want to do real DRM (ugh why?) use public key crypto with embedded root of trust certs/etc. You don't need some gibberish off-spec algorithm like this.
0:00 I've spent four days trying to figure this out and finally decided I'd rather learn what I don't understand than stubbornly stare at it.
I think videos like this are important. In the beginning it feels like every other skilled programmer KNOWS what to do from the get go. But every project requires figuring out. The more complex the problem the more figuring out.
Best part, I got a ad about a company hiring people on this video
I'm a recent graduate trying to find a job, and this just kinda intimidates me...
This stuff is way beyond me but I really like the fact that you gave the viewers the diffucult route and won't spoil them with your answer right away. Can't wait for the second Video.
Without diving too deep into it, I'd first deobfuscate the (diff[j]>>k)&1 . Since it is constant, we can replace it with a bool array.
I think having that clear array would help a bit. Then I'd take note of the indexes that result in 1, and maybe find a pattern.
But again, that's just at first glance. I'll try it tomorrow!
I work for a major tech company. I just make REST services. Spring. Flask. Etc. My team make lot of money just doing CRUD stuff that is, for the most part, handled with just annotations in the code. My coworker just wires Java beans together in XML. He only codes the unit tests related to his wiring up. Just takes the precoded beans and wires them into a batch processer class.
Seeing this makes me feel so guilty. There are programmers who tackle more advance stuff like this daily and probably make the same as me and my team who just type in @entity, @table, @id, OK done.
ok
What sort of stiudy path did you take?
Uni/college or just self learned?
Also how much are you making for reference.
@@Kat21
@@chriser5146 Bachelor's in Comp Sci from a US university. Electives in college, which was a bit ago, were focused on architecture and low level programming so you'd think I'd remember some things about how to attack this stuff, but nope! haha. Salary- $125k. Companies near me really only care about how knowledgeable you are on frameworks and APIs now a days. They dont care how many leetcode algorithm problems you can do if you don't know some QT or Spring, etc.
@@1UpBebop Sounds both pretty nice but then again a bit simple?
Coupled with the 125k... sounds a bit much for the type of work you described...
Im a first year in computer sciences from austria and will very likely start working for some company immediately, maybe as some sort of project manager since thats a heavy fopcus in my studies. Estimated salary will maybe get to be 80k on start so im not sure if you got really lucky with your job or i have no idea what my future will look like.
thanks for sharing the info :)
HIRE THIS MAN
USING C++, ANY WAY HE CAN
CLASHING ART-STYLES
Can I just say that your problem solving techniques are so gooood!
I like solving problems that have many dead ends, it makes solving the problem so much more satisfying and you learn things along the way.
Could just be me but I've found watching what the stack is doing to be a nice visual aid.
There's been a few albeit light encryption schemes I've gotten around just by looking at the stack and related chunks of memory.
Woooow so cool
It's amazing how many puzzles could people make with programming and the best thing is everyone has his own way to solve it
And i really love the C# Language
Me being lazy just throwing a genetic algorithm at it and letting it do the job
does it work ?
works ?
the diffusion is a 32x32 matrix, the code is doing matrix multiplication output=input*(diffusion^256) over abel group of {2^8, xor}, it will can be cracked by finding the reverse matrix of the diffusion, input=output*(reverse(diffusion)^256)
You had me in the first half, not gonna lie
My laundromat attendant used to work at Nintendo until one day he was fired. In general Nintendo has a pretty lousy HR track record.
*NINTENDO! HIRE THIS MAN! NINTENDO! HIRE THIS MAN!*
*HE IS USING UNREAL ENGINE IN ANY WAY HE CAN!...*
*NITENDO HIRE THIS MAN! NITENDO HIRE THIS MAN!*
Spoiler (not the literal answer but a good idea)
.
.
.
.
.
.
.
.
One of the first things that comes to my mind as someone with a mathematical background is that the loop that does a bunch of xors reminds me of a matrix multiplication. In fact it *can* be expressed as a matrix multiplication in some finite field in which addition corresponds to xor. So I think some tools from linear algebra would be helpful.
shush. Spoilers.
I love how you have a similar approach than I do when it comes to decluttering and simplifying code to reverse engineer it.
I don't know what kind of God programmers can just read this and wrap their head around it.
LiveOverflow: leaves only 0x41at 13:19
Me: Understandable have a great day
This is way over my head, but very interesting. #subscribed
Your videos are very enlightening!
If for a job interview, they asked you to show how you would defend against bear attack, you know that, at a point or another, your job will involve running away from bloodthirtsy bear... runaway from that codebase
Solving this on "redstar-winos", seems kinda North Korean
Mildly math literate person here, the thing you described in your video where you used linear algebra works here too, but instead of it being about linear dependence, it's about linear maps. If you look at the data the same way, then the part where all the XORing happens just implements a linear operator on the space, with diffusion essentially being the matrix that specifies which linear operator it is. If it's invertible, then that means that another value for diffusion would cause the same process to reverse itself. I'm not sure how viable it is to make the computations necessary, I don't think checking if the operator is invertible would be computationally difficult, but I don't know how good our algorithms our for the process of actually inverting it (computing the new value of diffusion).
I'm severely sleep deprived right now, so what I said may not be very well put together (though the essential idea I had is true, I'm sure about that one, but it's only helpful if the operator turns out to be invertible), but I'll keep looking into it after I sleep when I can think better.
"...and in the second video..."
Now this is early Christmas for me!
What you described in the last section was a linear code. Giving a linear decryption function would be equivalent to computing the left inverse of a Boolean matrix. There are various fast algorithms for doing so.
You can draw dependent relationships for all the bits in the diffusion that equal 1. The bits that equal zero cannot affect the input[j]. You can represent this as a 32x32 matrix and if this matrix is triangular, or close to it the problem can be reduced and brute forced
Its funny how just a couple for loops can contain so much complexity with figuring out what exactly it is doing. Of course, an S-box and encryption algorithms are meant to be confusing, and hard to figure out.
Das ist der beste und gleich schlechteste Clickbait den ich je gesehen habe xD Aber trotzdem echt geiles Video wie immer halt :D
I just started coding so ill try my beginners luck
Good luck
Me watching the video: "yes.".
Ahhh, dot matrix, my favourite type of notebook paper
Serious Question: Should I quit coding because I haven't even started yet?
nah it starts small and easy and gets harder butt you are better so its the sameish level
so do it
I thought him explaining the code would be helpful and that's why I kept watching, but I literally had no idea what he was talking about when breaking down the code. Guess I'll look into a different hobby.
That one guy: casually brute forces it
All I know is Java and even then I forgot my Java. I am in ✨fear✨
I only have room in my brain for one language at a time, and thanks to assembly I'm forgetting how english to work.
I think that the function shouldn't actually change any of arguments, because arguments aren't passed by reference.
Notice a line in bits in diffusion (from least 1 to greatest 8).
If you align it as a 31 bit array, there are visible lines by which bytes are carried over xorring input in the first cycle. It doesn't look random
Confusion array effectively makes a 8 bit input 16 bit and then in the last cycle it's back to 8 bit
Here I am, taking Programming II at my local community college, not knowing a damn thing what is going on in this video.
I don't think I will ever find a job at this point. =(
You will, this guys has many many years on you working in IT, also, its a cool video so youtube does tend to reccomend things that look really really advanced, and this is, its not just you, 99.999% of people watching this video might aswell be watching it in another language for all they know. Like watching someone juggle 12 balls, you cant do it yourself but its cool to watch
Amazing work. 👏🏻
Hell yeah, that's sounds great.
I will try it at the weekend :D
I thought he had found a bug in the Nintendo Switch and wanted to make Nintendo aware of it: Hire me!
I would like to highlight that walking the dog and sleeping well are key for this kind of problem solving (and the deep-thinking and knowledge database is obviously a plus)
"But I am lazy"
This, or "I should make this part better, but I will improve it later" are actually common coding steps. Prioritizing what code to work on is important, and some things will change based on how other things end up being implemented, so may not be good to fully flesh out at the start.
I might be wrong but the way you described the xor-chaining at 15:30 it sounds to me it should be solvable by using backtrack. Same concept used to create a sudoku solver.
Whuuuut, did you missed the part, that some XORs canceling each other out.
Im not a cipher analyst, just a programer. But to me the complexity of this algorithm caused by two things 1) substitution 2) Outcanceling of bytes 3) the mixture of it
@@quebono100 look at his part 2 video, the "solve_round" function is exactly what I described, a backtrack algorithm.
@@wfzyx Yeah Im sorry you are right :)
So, the first j-loop is a substitution cypher, and the following j-k-loop is, as pointed out by others in the comments, a vector point product between the above input and the diffusion vector, and then the last i-loop adds extra diffusion with it's self (sort of). And all of these is done 256 times in order to add more confusion, I think.
So, the backward function will have to break these three cyphers backwards, 256 times. The most interesting one is the j-k-loop one, as pointed out by others, you'll have to find an inverse matrix, but my guess is that this matrix is actually (out matrix)(diffusion matrix), and that these matrices products are reflective.
I cracked this last year! I'd live to discuss it with you and we can compare our solutions!
Mine essentially used histograms to associate the output and input of the confusion array, then recursively searching down the 256 layers for valid mappings. The other steps are invertible with some basic for loops, so the bulk of the effort is detecting which mappings are valid at each recursion step.
u made it! remember the time in 2012 when u teached our class of business information science fools (ibm class 2011) to develope "moorhuhn" in böblingen - big shoutout
omg. it's so awkward when people I have met IRL watch my videos 🙈
2:54 What i'm wondering is why you're printing variables to the consoles instead of using the VS Code debugger...?
NINTENDO, HIRE THIS MAN!!!!!!!!
Mfw big brain when I add
printf ( "hire me!!!" );
I thought I was decent at programming xD and then I watch these and am humbly grounded
hint: sometimes you can rewrite the same code in a different way, to be more easy to visualize in your brain and understand it
12:20 yeah you're right. I don't understand that ^^
interesting video anyways! stay healthy man, greetings from hannover ;)
I understood what he said until that timestamp and didn't anything after it.😂
Why I quitted my job at Nintendo.
This is surprisingly awesome as a coding student.
I. Clicked. One. Video.
Advertisements about software developing is popping up already.
Being a Nintendo Modder understanding their Yaz0 compression algorithm, it almost looks like they are hiring someone to make a new format
yes.szs
What sort of topics do I need to learn to even attempt this problem? Im only a first year computer science student but I want to try dipping my feet into deep waters; got a lot of free time right now...
C programming and math ;)
@@LiveOverflow a broad question gets broad answers... can you be specific please lol
C programming and linear algebra
We are very happy for you. You are living the dream man. Stay Healthy.
NINTENDO HIRE THIS MAN
NINTENDO HIRE THIS MAN
HE'S USING VISUAL STUDIO IN ANY WAY HE CAN
Reverse-ing the function is probably what they want since they named it forward but I wish you tried reverse-ing the input array just to see if there's another clue
need to check it out like 1 to 2 years later when I understand more about coding
In 0:44 inside of the for loops looks like gibberish
Hmm.. so what is the toughest CTF you have ever solved? And can you make a video about that? :)
I understand propabely 5% of the progrmming-stuff and even less of the procedure how to solve such a puzzle.
I still like your videos because i feel more inteligent after watching them :D
Love your videos
The ad for this video was some weird illness called cpp
Why am I watching this? I have no idea what any of this means.
You are the one when you spoke without background music
If I understand this correctly feel like this a hash function that gives 32 bits of output for your 32 bits of input
> entirely C code
> .cpp
conflating the two very different languages is the number one cause of hating both
huh so what
@@roby2k14 They are two of the most pivotal inventions in our field shaping our modern infrastructure and playing a crucial role in virtually every system be it directly or indirectly. Anyone in this field benefits considerably from knowing these two languages thus it is a travesty when people are pushed away from them. When two languages with contradictory philosophies are conflated the result is impossible to understand, needlessly difficult to use, and impossible to appreciate which scares newcomers away from not only where they have experienced the language, but also information technology in general. Be it web dev, games programming, hacking, or anything in-between: the lessons from these languages matter so conflating them therefore obfuscating those lessons worsens our field.
@@TylerStOnge-rz4os okay but why is .cpp file being written in c something bad? you can compile it like u would compile a .c file? or is there any difference?
I mean they're pretty similar in some aspects, I dont see the problem :| or not a big deal (for me)
@@roby2k14 The philosophy of C is to write, in a high level (just above assembly), what the computer should do, effectively being portable assembly. C++ on the other hand is about creating a domain specific language for the problem at hand to always be at the correct level of abstraction for that particular problem. One is all about removing abstraction and the other is about creating it. Sure it compiles but that does not make it C++, hence effectively telling people "hey this code is C++" conflates the two and pretends as though they are the same language and you write code for them in the same way which is objectively not true. They have similar syntax but are different in virtually everything else which is why they offer different lessons.
@@chyza2012 There is much, much more to a language than its syntax. Much of C will work in Java, C#, Javascript, so on and so forth, yet these are obviously very different to C. The code provided is _not_ C++, but it is C. A language comes with its standard library, conventions, idioms, et cetera and the code here did not follow those at all hence just because it would compile with a C++ compiler does not mean it is C++. There's an entire subfield on this called software engineering which examines how something happening to work does not mean it is a correct; there is more to code than the binary.
Zowies! UA-cam placed 9 ads for me in this video, one was 5 minutes long!
🇨🇦🐧