Triple DES encryption on C# and PHP yields differe

I'm writing a simple encryption system for logging in but I've got small issue. C# encrypt function:

public static string EncryptString(string Message, string Passphrase)
{
    byte[] Results;
    System.Text.UTF8Encoding UTF8 = new System.Text.UTF8Encoding();

    // Step 1. We hash the passphrase using MD5
    // We use the MD5 hash generator as the result is a 128 bit byte array
    // which is a valid length for the TripleDES encoder we use below

    MD5CryptoServiceProvider HashProvider = new MD5CryptoServiceProvider();
    byte[] TDESKey = HashProvider.ComputeHash(UTF8.GetBytes(Passphrase));

    // Step 2. Create a new TripleDESCryptoServiceProvider object
    TripleDESCryptoServiceProvider TDESAlgorithm = new TripleDESCryptoServiceProvider();

    // Step 3. Setup the encoder
    TDESAlgorithm.Key = TDESKey;
    TDESAlgorithm.Mode = CipherMode.ECB;
    TDESAlgorithm.Padding = PaddingMode.PKCS7;

    // Step 4. Convert the input string to a byte[]
    byte[] DataToEncrypt = UTF8.GetBytes(Message);

    // Step 5. Attempt to encrypt the string
    try
    {
        ICryptoTransform Encryptor = TDESAlgorithm.CreateEncryptor();
        Results = Encryptor.TransformFinalBlock(DataToEncrypt, 0, DataToEncrypt.Length);
    }
    finally
    {
        // Clear the TripleDes and Hashprovider services of any sensitive information
        TDESAlgorithm.Clear();
        HashProvider.Clear();
    }

    // Step 6. Return the encrypted string as a base64 encoded string
    return Convert.ToBase64String(Results);
}

EncryptString("test", "123456") returns "Yjaqhc7RFds=".

The same code in php:

  <?php
    $key = "123456";
    function pkcs7_pad($text, $blocksize)
    {
        $pad = $blocksize - (strlen($text) % $blocksize);
        return $text . str_repeat(chr($pad), $pad);
    }

    $input = pkcs7_pad("test", 16);
    $key = md5(utf8_encode($key), true);
    $td = mcrypt_module_open('tripledes', '', 'ecb', '');
    $iv = mcrypt_create_iv (mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
    mcrypt_generic_init($td, $key, $iv);
    $encrypted_data = mcrypt_generic($td, $input);
    mcrypt_generic_deinit($td);
    mcrypt_module_close($td);

    echo base64_encode($encrypted_data);
?>

returns "dybhiZYdKG8pNCgCFkbV6g=="? What am I doing wrong?

You're running into this problem because Triple DES's key size is 168 bits (21 bytes), but MD5 generates hashes that are only 16 bytes (128 bits) long.

This means the key will have to extended to 168 bits so Triple DES can work. It turns out that this derivation from 128 bits to 168 bits works differently in C# than it does in PHP, so the key that's effectively used is different, resulting in different encrypted data.

Now you have two options:

Option 1: Pick a cipher that supports 128-bit keys outright

You can avoid all the problems related to key size differences if you use a cipher that supports 128-bit keys. This would require minimal changes to your code. You can use Rijndael (AES), for example.

C#: Change TripleDESCryptoServiceProvider to RijndaelManaged.
Everything else can stay pretty much the same. (Demo)

PHP: Use MCRYPT_RIJNDAEL_128 instead of tripledes (Demo):

function encrypt_pkcs7($str, $key)
{
    $key = md5(utf8_encode($key), true);
    $block = mcrypt_get_block_size(MCRYPT_RIJNDAEL_128, MCRYPT_MODE_ECB);
    $pad = $block - (strlen($str) % $block);
    $str .= str_repeat(chr($pad), $pad);

    $ciphertext = mcrypt_encrypt(MCRYPT_RIJNDAEL_128, $key, $str, MCRYPT_MODE_ECB);
    return base64_encode($ciphertext);
}

echo encrypt_pkcs7('test', '123456');

Note that the effective key size of AES is larger than Triple DES. Although Triple DES' key is 168-bit long, it only offers 112 bits of security. I would pick this option if I were you.

Option 2: Use a 192-bit key instead of a 128-bit key

If you use a larger key than Triple DES actually uses, C# and PHP seem to agree on how to reduce it to 168 bits. You can do this by using a hash function like SHA-256, which generates a 256-bit hash and trim it to 192 bits (24 bytes):

C#: Use SHA256CryptoServiceProvider and Array.Copy to get a 192-bit key, and use that with the rest of your program: (Demo)

SHA256CryptoServiceProvider HashProvider = new SHA256CryptoServiceProvider();
byte[] temp = HashProvider.ComputeHash(UTF8.GetBytes(Passphrase));
byte[] key = new byte[24];
Array.Copy(temp, key, 24);

PHP: Use hash() with SHA-256 and substr() to get the 192-bit key

function encrypt_pkcs7($str, $key)
{
    // derive 192-bit key using SHA-256
    $key = substr(hash('sha256', $key, true), 0, 24);
    $block = mcrypt_get_block_size(MCRYPT_3DES, MCRYPT_MODE_ECB);
    $pad = $block - (strlen($str) % $block);
    $str .= str_repeat(chr($pad), $pad);

    $ciphertext = mcrypt_encrypt(MCRYPT_3DES, $key, $str, MCRYPT_MODE_ECB);
    return base64_encode($ciphertext);
}

echo encrypt_pkcs7('test', '123456');

It doesn't look like I can supply a 168-bit key to TripleDESCryptoServiceProvider, I don't know why.

Other considerations:

Consider using SSL; even if it's a self-signed cert. It beats re-inventing the wheel, a particularly dangerous task when cryptography is involved.
Consider using a mode of operation other than ECB (eg: CBC). Using ECB increases security risks. Read the Wikipedia article on block cipher modes of operation.
Unless you absolutely need to have a plaintext password (rarely the case), you should hash your passwords. Read this article on securing passwords.
Consider using a proper password-based key derivation function, like PBKDF2 instead of a general purpose hash function like MD5 or the SHA family. This will make cracking the key harder. For more information, read the article in the previous bullet point.