I'm trying to secure a REST API, our situation is that every client connecting to this API will also have a certificate signed by our own CA. Because of this, I think we can use the client certificate as an authentication mechanism, and install our root certificate on the webserver for verification and then use mutual authentication through HTTPS. We intend to do this with nginx so it's as simple as requiring nginx to have client verification on. However, I'm unclear about whether I should still timestamp and sign each request, should I still worry about message integrity and replay attack? Is there anything other attacks I should guard against?
I highly suspect this is a self rolled, or at least very outdated method.  It is very weak by modern standards and should not be used to protect anything important.

Short passwords could be cracked with no more than 2^64 brute force attempts, which is quite possible with even a normal computer.  If both halves of the result are independent, even with fairly long passwords, 2*2^64 brute force attempts could crack it (so 2^65 attempts). There are likely further weaknesses in the algorithm that make it weaker than described here.

Another interesting point to test would be 2111111111 and see if the second part of the result remains the same.  If the second part doesn't change, this is definitely a weak algorithm.

Edit: 

Seeing that the results of the 2111111111 test are the same for the second half, this is definitely a weak algorithm and should not be used to protect anything sensitive!  I have included the relevant comparison below:


  
  1111111111 : FIcx3a00R4evxqEuQkZZtg==
  2111111111 : GPwnH80qEACvxqEuQkZZtg==
  


Edit:

Another interesting test would be what Ricky Demer suggests below:


  The next thing to check is that it handles the 8-byte blocks identically. ​ What are the "hashes" of aaaaaaaabbbbbbbbc and bbbbbbbbaaaaaaaac? ​ ​ ​ ​ – Ricky Demer Feb 25 at 6:44 


If it handled the 8-byte blocks identically, it is even worse for even long passwords, no matter what the length.  It would require just 2^64 brute force attempts as pointed out by Neil in the comments. Once someone made a table of what each possibility calculates to, this algorithm would be practically useless.  There are probably even more weaknesses to this algorithm remaining to be discovered.  

Bottom line:

I do not recommend using this algorithm regardless of the results of the last test.  We have already seen enough to know it is weak.  Something with a higher bit encryption / hash scheme, salt, long computation time etc... would be much better, and I would recommend going with one of the existing thoroughly tested methods.  Self rolled encryption / hashing has not had the benefit of extensive testing that most of the main stream methods have.
