I'm guessing they used something like scallion [0] or Shallot [1].

Bench marking Shallot on an Intel 3350P@3.10GHz:

  time ./shallot ^a      -> 0.09 sec user
  time ./shallot ^aa     -> 0.12 sec user
  time ./shallot ^aaa    -> 0.12 sec user
  time ./shallot ^aaaa   -> 0.47 sec user
  time ./shallot ^aaaaa  -> 5.92 sec user
  time ./shallot ^aaaaaa -> 118 sec user

Unfortunately OpenCL doesn't work with the nouveau drivers so I can't test scallion.

Who knows how much they spent trying to brute force that onion address.

EDIT: Ok looks like they went the backronym route

[0] https://github.com/lachesis/scallion [1] https://github.com/katmagic/Shallot