Simulando el cifrado PASSWORD() de MySql usando .NET en Windows 8

Finalmente encontré la solución :), espero que te ayude:

        /// <summary>
        /// Reverse a string
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string ReverseString(string s)
        {
            char[] arr = s.ToCharArray();
            Array.Reverse(arr);
            return new string(arr);
        }

        /// <summary>
        /// MySQL PASSWORD encryption
        /// </summary>
        /// <param name="strMsg"></param>
        /// <returns></returns>
        public String HashMsg(String strMsg)
        {
            // Convert the message string to binary data.
            IBuffer buffUtf8Msg = CryptographicBuffer.ConvertStringToBinary(strMsg, BinaryStringEncoding.Utf8);

            // Create a HashAlgorithmProvider object.
            HashAlgorithmProvider objAlgProv = HashAlgorithmProvider.OpenAlgorithm(HashAlgorithmNames.Sha1);

            // Hash the message.
            IBuffer buffHash = objAlgProv.HashData(objAlgProv.HashData(buffUtf8Msg));

            // Verify that the hash length equals the length specified for the algorithm.
            if (buffHash.Length != objAlgProv.HashLength)
            {
                throw new Exception("There was an error creating the hash");
            }

            byte[] arrByteNew;
            CryptographicBuffer.CopyToByteArray(buffHash, out arrByteNew);
            StringBuilder myBuilder = new StringBuilder(arrByteNew.Length);

            foreach (var b in arrByteNew)
                myBuilder.Append(b.ToString("X2"));

            // Concat with the STRING REVERSED
            String stringReversed = "*" + myBuilder.ToString() + ReverseString(strMsg);

            buffUtf8Msg = CryptographicBuffer.ConvertStringToBinary(s3, BinaryStringEncoding.Utf8);
            buffHash = objAlgProv.HashData(objAlgProv.HashData(buffUtf8Msg));

            if (buffHash.Length != objAlgProv.HashLength)
            {
                throw new Exception("There was an error creating the hash");
            }

            CryptographicBuffer.CopyToByteArray(buffHash, out arrByteNew);
            myBuilder = new StringBuilder(arrByteNew.Length);

            foreach (var b in arrByteNew)
            {
                myBuilder.Append(b.ToString("X2"));
            }

            stringReversed = "*" + myBuilder.ToString();

            return stringReversed;
        }