I also tried to crack exactly this program a while ago. The company (I believe it is MilSoft, one of the most reputable software companies in Turkey) sent this challenge to university students to hire a part-time CS student. Nevertheless, this was the first time I've ever attempted to crack something and while I had little to no idea what was going on, it was a very thrilling experience. I think I went on 14 hours without taking a break.

I began by trying to run the program in GDB, got SIGSEGV'd. Afterwards I inspected the faulty address and tried to avoid it by changing its value, instead it crashed at somewhere else. After trying this hopeless catch-and-run for several hours, I decided I needed a better disassembly tool and went on to IDA Pro.

This particular program contains a trick that intrigued me very much, and it is the reason why I was getting SIGSEGV'd at different locations when altering the program code.

The main payload of this program is simply XOR-encrypted by some key. The whole thing begins by decrypting the payload and then begins its execution as normal. The gist is, the particular key that encrypted the main payload is the decryption code itself (for the unacquainted, assembly code is also just a byte stream). Here, this exact part:

   0x804762d:   mov    $0xaa,%dl
   0x804762f:   mov    $0x8048480,%edi
   0x8047634:   mov    $0x8048cbc,%ecx
   0x8047639:   mov    %edi,0x80476f3
   0x804763f:   mov    %ecx,0x80476f7
   0x8047645:   sub    %edi,%ecx
   0x8047647:   mov    $0x804762f,%esi
   0x804764c:   push   $0x80476c1
   0x8047651:   pusha  
   0x8047652:   mov    $0x55,%al
   0x8047654:   xor    $0x99,%al
   0x8047656:   mov    $0x8047656,%edi
   0x804765b:   mov    $0x80476e5,%ecx
   0x8047660:   sub    $0x8047656,%ecx
   0x8047666:   repnz scas %es:(%edi),%al
   0x8047668:   je     0x804770a
   0x804766e:   mov    %edi,0x80476eb
   0x8047674:   popa   
   0x8047675:   add    0x80476eb,%edx
   0x804767b:   ret

As far as I can remember, the key was a bit more than that, but I'm sure it was including this part.

At the end of every iteration (of something involving this loop which I can't precisely recall now) the program checks whether it is running under debug mode (essentially makes a PTRACE call and reads its output, the OP also talks about it) If this is the case, it makes a jump to random address, so even if you are just neatly watching the program run under debug mode, you weren't going to achieve anything.

The next thing that occured to me is to manipulate how PTRACE returns its value, but I thought it would involve some kernel code fiddling and running the program under the modified kernel, which is WAY beyond my ability for now. I didn't know how to do it, but later by some very stupid trick I managed to pass this decryption part and the program made a jump to something like "__glibc_start". I needed to save the altered program and run it under gdb again (I don't remember why), but I was using the trial version of IDA Pro which prohibits me of such a thing. After making a few more desperate attempts I gave up.

But this "using the code as the key".. I think spending 14 hours to see this done was well worth it.