People ask me what binary reverse engineering is like. It’s tedious, that’s what it is. When it gets right down to it, you just have to concentrate on little (in the sense that they do not do much individually) instructions and carefully trace the bigger picture from huge blocks of these baby steps.

If you want to see what RE really looks like, come inside my notebook. Here are 3 choice pages, illustrating the process I used to figure out one of the inverse transforms that RealVideo 4 (and 3, for that matter; both H.264 prototypes) employ:

page 1, page 2, page 3

In this example, I used a lot of back substitution in order to figure out a series of math formulas. This case was greatly simplified by the fact that there were not very many mystery parameters to deal with. However, the property that complicated matters here is that there were few if any straightforward imul (integer multiplication) instructions. Even though multiplication figures heavily into the transform, most multiplications were performed by sequences of additions, bit shifts, and compound add/shift instructions (lea).

So I had a little carton of chocolate milk with my lunch today (longtime readers have guessed that I must still be in elementary school). On one side of the carton was a word search puzzle that challenged me to find 6 words hidden in the jumble of letters. It occurred to me that this represented an allegory for reverse engineering.

I generally liken RE to an extraordinarily complex, or just tedious, puzzle. This is a more straightforward puzzle.

Task: Find 6 strings of characters. What strings? I wasn’t sure exactly. Lesser word searches explicitly tell you which words to find. Those puzzles can be solved via a brute force algorithm that most of us figure out by the age of 5. I knew that these had to be coherent English words. Eventually, I re-read the instructions and noticed that the words were supposed to pertain to “foods made from grain”. Lesson: Gather all the intelligence you can before delving into the meat of the puzzle.

Next, there is domain knowledge. I have done a few word search puzzles before and so I know that I am supposed to look for strings of characters running left -> right, right -> left, top -> bottom, bottom -> top, and also diagonally. And I have some clue about foods made from grain. So I am off.

Then, I started theorizing about how the original puzzler (or whatever you call a person who develops puzzles) must have put this puzzle together. Since there are 6 words, I hypothesized that 2 would be horizontal (one for each direction), 2 would be vertical (again, one for each direction), and 2 would be diagonal. This would make good use of the parameters of a stock word search. I refined my initial search using these assumptions.

I was correct about the 2 horizontal and 2 vertical. I also found one more horizontal word. I methodically scanned every diagonal possibility, much to the disdain of my overworked eyes. I could not find any word on that orientation. So I revised my original assumption and assumed the remaining word must also be horizontal.

Finally, there’s the matter of validation: determining if one’s RE results are correct. Unlike binary RE, this puzzle makes it easy. So I check and… I don’t believe it! I only got 4 of them correct. I got another partially correct. And yeah, I didn’t think ‘bean’ was a valid grain.