Do test vectors ensure a cipher is free of backdoors? If a cipher implementation passes unit tests using test vectors from some trusted source (these for AES, for example), then can we say that it is fully conforming to the specification, and must have been implemented correctly?

Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher?

This question was motivated by the advice given by figlesquidge in his answer to the question AES column mixing and S-Box confusion, where he says:


  Standard AES disclaimer: Given the questions you've asked, you should
  not implement AES yourself in a real-world system because there are
  lots of security considerations when implementing ciphers.
can we say that it is fully conforming to the specification, and must have been implemented correctly?


No.


  Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher?


Certainly.

Say I have an function AES(k,m)=c where variables k and m are the key and the message respectively and c is the resulting ciphertext.

Now I could write my own AES as follows:


def mikeazo_AES(k,m):
    if k==0x12abed347816981812abed3478169818:
        return m
    else:
        return AES(k,m)


Thus, given a specific key, it will simply return the plaintext. Since that key is not part of the test vectors, they will all pass.

This will be compatible with all other implementations unless that key is hit. Since they are randomly generated, the probability of that happening is slim. This may not seem super useful at first glance, but as an attacker you could add in some sort of trigger mechanism to force keys to be the special key. You can presumably do this as you have already got your software on their system.

There are better back doors that could be inserted. See example in comments from CodesInChaos.