CSAW’18 RTC Quals — Magic 2 Write-up
Write-up for the challenge Magic 2 from the CSAW’18 RTC Qualifiers.
Whilst not being eligible for the finals, me and my CTF team decided to do the CSAW’18 RTC Qualifiers anyway, for the practice, learning, and fun!
Magic 2 was brain teaser for me, and even though it isn’t much to do with InfoSec, or Red Teaming, I still had a lot of fun with it!
Magic 2 is a sequel to Magic 1. Magic 1 is a 9×9 matrix where only some cells are filled in, the goal was to fill in the rest of the gaps in the matrix, so that the matrix will become a 9×9 magic square.
a magic square is a n×n square grid (where n is the number of cells on each side) filled with distinct positive integers in the range 1, 2, . . . , n² […] the sum of integers in each row, column and diagonal is equal. The sum is called the magic constant or magic sum of the magic square. — Wikipedia
Magic 2 was fairly similar to Magic 1, except the magic square was 10×10, adding a whole new layer of difficulty.
We accomplished Magic 1 by happening upon the exact magic square whilst googling for how to solve them, however the same tactic did not work for Magic 2. So whilst my other team members reverse engineered binaries and hacked web pages, I took to solving Magic 2.
After googling (Or in my case, DuckDuckGo-ing) around for ages looking at different tutorials, they made solving a 10×10 magic square seem extremely difficult and time-consuming, I wasn’t prepared to read up on how other people solve it, so I came up with my own method.
Side note: In hindsight, my method is probably also difficult and time-consuming, plus since the number of solves was around 40 I still think there was an easier way, but hey, this is my method not theirs.
Whilst I spent a lot of time digging, it didn’t come completely dry, I found out a pattern which, whilst probably not inherent to all 10×10 magic squares, seemed to apply to Magic 2. Can you spot it?
Can’t spot it? How about now?
If I split the 10×10 grid into a 5×5 grid, where each cell contains 4 numbers, those 4 numbers are consecutive.
If we take a look at the top left group of numbers we can see that sums of the each row are equal, and the sum of each column are two apart from one another. We can make a notation for this, where one vertical line means 2 more than the other column in the smaller group of 4 numbers, and one horizontal means 2 more than the other row. There are also situations where the difference between the two rows or two columns is equal to 4, so I use a double line to 4 more than the other row/column.
Applying this notation to the magic square above gives us:
It may look a bit messy and confusing to begin with, but if you single out the vertical lines in each pair of columns, there are the same amount of lines in both columns, same pattern applies to the rows.
Then, applying this pattern to the starting state of Magic 2’s grid:
Now we have to fill the rest of the boxes with other combinations of 4 consecutive numbers in specific ways such that the lines all cancel out, right? Not only that, no. Since we can only use each number from 1–100 only once, as a rule. So not only do we need to place 4 consecutive numbers in each of these smaller squares, we also need to make sure those 4 consecutive numbers are the correct numbers such that the rows and columns add up to the magic constant, which for a 10×10 magic square is 505. We’re going to start with what sets of 4 consecutive numbers we need to place in the smaller squares, so that we make sure the lines cancel out and give the same value when ultimately added up.
As this is a 10×10 magic square, the numbers we have to choose from are from 1–10², or 1–100. This divides evenly into 25 sets of 4 consecutive integers (As 25×4=100), which are the multiples of 4, and the 3 integers below it (e.g. {1, 2, 3, 4}, {21, 22, 23, 24} and {69, 70, 71, 72}). By thinking of the 10×10 magic square as instead a 5×5 square can simplify the problem down and make it easier to manage, but to do that we must simplify these sets of 4 consecutive numbers down into 1 number, the easiest way to do that is take the 4th number and divide it by 4, leaving us with 1–25 to represent each set.
And so using that, we can simplify it into a 5×5 magic square, and because the numbers are the same relative to one another, as long as we can solve this square, we can get one step closer to solving the 10×10.
Side note: I can fill in the corner numbers as, even though they aren’t completed, they still follow the same rule of sets we discovered earlier. For example the top left one has 65 and 66, which are part of the {65, 66, 67, 68} set, so if we divide the 4th element by 4, we get 17.
When looking up how to solve a 5×5 magic square, I came across this video, which just so happens to be the exact same magic square we have, but flipped. This means our completed 5×5 is:
I added numbers showing the sums of the rows and columns, showing that this is a solved 5×5 magic square, with a magic constant of 65. We can turn this back into the sets of numbers by multiplying the number by 4, and getting the three integers before it, so 5 becomes {17, 18, 19, 20}.
Now that we know the sets of numbers we need to use in the main 10×10 magic square, we need to know the arrangement of them within their smaller 2×2 squares. To do this we must construct a diagram that builds upon the original line diagram of the 10×10 to know what order to put them in, but to do that we need a way of converting the arrangement of the numbers into the lines, and vice-versa.
Armed with this table, we have everything we need to starting filling in Magic 2.
If we take a look at our line diagram from earlier, we can start filling in lines. We should start with the corners, as they already have two numbers filled in.
Looking at the top left one, which already has 65 in the top left, and 66 in the bottom right, we know the set it came from is {65, 66, 67, 68}, so we must refer to our table of lines to see what has 1 in the top left, and 2 in the bottom right.
We can use this one, so we can draw a horizontal line on the picture
We can then apply the same method to the three other corners.
After this, we have to fill in the rest of the spaces, such that in each pair of columns or rows (as split by the black lines) the number of blue lines in each row/column of the pair is equal so that they cancel each other out, using the table of lines we made earlier.
With all the squares filled in with lines, we can now fill it in with numbers using the lines table. We can start anywhere, so let’s go with top left first.
We know that it is already filled with two numbers 65 and 66, so the full set of numbers is {65, 66, 67, 68}, and referring to our table from above we can fill in the fields as shown below.
After these 4, we can move onto the 4 afterwards, which is completely blank, so we must refer to our 5×5 solved magic square.
In the next position is 24, so to get the set of numbers we multiply it by 4 to get 96, so the set is {93, 94, 95, 96}, and then we can refer to our line table and the type of line we chose for this next slot.
By repeating this same process for all the unfilled squares, we should result in a solved 10×10 magic square, and our flag!
We now have the flag, and can claim our 150 points!
flag{y3r_a_wiz3rd_h4rry}
Foot note: This is quite a complex method and it’s one of my first few write-ups, if you have any suggestions or misunderstandings feel free to contact me! I’m assuming the reason this is only 150 points and has many solves is probably due to a 10×10 solver online if you dig deep enough, I don’t know, but I had fun with my method so that’s enough points for me.
