Obsessbook — discussion

Spoiler alert! The solution to the puzzle is given below. You have been warned.

(You should read about the submission here first.)

The backdoor works on 32-bit systems. It has been verified on x86 and ARM with Linux and gcc.

The bug hides in the interaction between the two modules. Hence, by submitting each module independently for code review, there is very little risk of discovery.

The hash function (in the derpcon module) normally returns a positive integer. However, for very long account handles the computation overflows and may produce a negative number. This is no error by itself, as the function is declared as returning a signed integer.

In the hash table module, the modulo operator '%' will normally map the hash value onto a valid table index in the range 0..BUCKETS-1. Even seasoned C programmers can be under the impression that the modulo operator always brings the result into this range, which provides plausible deniability. In fact, using '%' in this fashion is a standard design pattern that wouldn't ring any warning bells. It does, however, make the tacit assumption that the hash function always returns a positive value: Negative numbers are brought into the range -BUCKETS+1..0. This is no error by itself provided that the hash function behaves well.

Some suitable time after leaving the company, our rogue contractor creates a new account ("hacker") and an auxiliary account with a specially crafted account handle (e.g. "aayaaaaaaaaaaaaaaaaaaaaaa"), and connects the two accounts. The long handle resolves into table index -1. This causes the program to treat the memory on the stack immediately before the actual hash table as if it were a table entry. The collision counter plays the role of "key", and acts as a null pointer since there hasn't been any collisions. The distance variable in the DERPCON() stack frame plays the role of "value". By following the code, you can see how a recursive traversal of the graph starting at "hacker" causes the distance variable to change from INFINITY to 1. When hashtable_get is called to see how far some other user is from "hacker", the given user cannot be found in the graph, so the distance variable remains 1.

Accidental discovery of the backdoor is unlikely, because nobody in their right mind would choose a login name with more than 24 characters.

Go back