Necesito consumir un servicio web que requiere WS-Security basado en certificados X.509 de la aplicación ASP.NET 4.5. Hasta ahora he creado la referencia web pero no sé cómo implementar WS-Security. No tengo ningún problema para obtener el certificado, pero no sé cómo usarlo en este caso, necesito obtener consejos sobre cómo proceder.

Mi código hasta ahora es muy básico, necesito agregarle WS-Security:

var tere = new serviciotereSoapClient(); 
tere.ClientCredentials.ClientCertificate.Certificate = myCert;
var response = tere.agregarGuia( guia );

Configuración del servicio:

  <system.serviceModel>
    <bindings>
      <basicHttpBinding>
        <binding name="serviciotereSoapBinding" >
          <security mode="Transport">
            <transport clientCredentialType="None" proxyCredentialType="None"
              realm="" />
            <message clientCredentialType="Certificate" algorithmSuite="Default" />
          </security>          
        </binding>
      </basicHttpBinding>
    </bindings>
    <client>
      <endpoint address="https://secure.aduana.gov.py/test/tere/serviciotere"
        binding="basicHttpBinding" bindingConfiguration="serviciotereSoapBinding"
        contract="TEREReference.serviciotereSoap" name="serviciotereSoap" />
    </client>
  </system.serviceModel>

EDITAR 1

Basado en la respuesta de @TrevorBrooks, llegué con la siguiente implementación:

Crear un proxy de servicio usando SvcUtil.exeAgregue wsHttpBinding a web.configCambió el punto final para usar el enlace agregado en el paso 2.Cambió el código para usar el nuevo cliente WCF.

El web.config ahora se ve así:

<system.serviceModel>
    <bindings>
      <wsHttpBinding>
        <binding name="WSHttpBinding_TereService" >
          <security mode="Transport">
            <transport clientCredentialType="None" proxyCredentialType="None"
              realm="" />
            <message clientCredentialType="Certificate" algorithmSuite="Default" />
          </security>
        </binding>
      </wsHttpBinding>
    </bindings>
    <client>
      <endpoint address="https://secure.aduana.gov.py/test/tere/serviciotere"
        binding="wsHttpBinding" bindingConfiguration="WSHttpBinding_TereService"
        contract="serviciotereSoap" name="WSHttpBinding_TereService" />
    </client>
  </system.serviceModel>

Ahora, al invocar el servicio, obtengo ProtocolException con el mensaje:

El tipo de contenido text / xml; charset = UTF-8 del mensaje de respuesta no coincide con el tipo de contenido del enlace (application / soap + xml; charset = utf-8). Si usa un codificador personalizado, asegúrese de que el método se implemente correctamente IsContentTypeSupported. Los primeros 372 bytes de la respuesta fueron:

        <env:Envelope xmlns:env='http://schemas.xmlsoap.org/soap/envelope/'> 
            <env:Header> </ env: Header> 
            <env: Body > 
                <env: Fault xmlns:env='http://schemas.xmlsoap.org/soap/envelope/'>
                <faultcode>env:Server</faultcode>
                <faultstring> org.jboss.ws.core.CommonSOAPFaultException: 
This service requires <wsse:Security>, which is missing </ faultstring>. </ Env: Fault> 
            </env:Body> 
        </env:Envelope>

Este error es un paso adelante para mí porque con basicHttpBindingla excepción fue más horrible
El problema se debe a que el Servicio requiere WS-Security y necesita firmar el mensaje con un certificado, ese es mi problema y todavía no puedo entender cómo hacerlo. Enesta otra pregunta También di los detalles.

EDITAR 2: Ahora recibí un sobre de muestra que funciona para el servicio.

<soapenv:Header>
  <wsse:Security xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd" xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
    <wsse:BinarySecurityToken EncodingType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-soap-message-security-1.0#Base64Binary" ValueType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-x509-token-profile-1.0#X509v3" wsu:Id="X509-B259DAB3D28E48CB6A140000796019094">MIIC9TCCAd2gAwIBAgIIUiM4nWs8kfcwDQYJKoZIhvcNAQEFBQAwNzERMA8GA1UEAwwIQWRtaW5DQTExFTATBgNVBAoMDEVKQkNBIFNhbXBsZTELMAkGA1UEBhMCU0UwHhcNMTQwMzIwMTkxMTIwWhcNMTgxMjIwMTQzNzEzWjBBMRQwEgYDVQQDDAtjb3VyaWVyLnRudDEOMAwGA1UECwwFc29maWExDDAKBgNVBAoMA2RuYTELMAkGA1UEBhMCcHkwgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAOS71x5+ChwGzWs4VlLgkePbU8/zFHUrrE8nFNVsukMCc5q5hCK8/CeNM+mxImilLdJrGoC2/000lQetB9B3AqIrAdOfBFU4/qsAlgWI+kt2jnUsJMLRjQfxhAKMeX4RUb0CmTcsnXtWlFvYFFjiUi9nUJVSxCsmldVFgLIAHRPjAgMBAAGjfzB9MB0GA1UdDgQWBBTCwBBmU7f/4SmNz7GNJ25ILkPuhjAMBgNVHRMBAf8EAjAAMB8GA1UdIwQYMBaAFDF+1hOSdgg2DFOUofnnXdx9TxjeMA4GA1UdDwEB/wQEAwIE8DAdBgNVHSUEFjAUBggrBgEFBQcDAQYIKwYBBQUHAwIwDQYJKoZIhvcNAQEFBQADggEBAALVVGGNsTSMcfDBwkkNQH3MpfiNTo/mhH8ahqUVN1+5BIwWstv8fH0Sl9ea1XShKLPDfDIx8WSzUUIt/93f74B3a3oMpBtbVEiku2BKUp5cJfkYe2c5zPOxk3nzmQwcEoB++RgX9DJOtUkKA/It2IM9/8ggUyjceJQCpBRiA9Kg7+h3HfmOKNn+9/pNu498JXhSRKa8Jr4pp/1udYRk+W8sKGEBtAU9MvL3y0AbvLhUD+MZyvpHGB17fslC8Nnd5EBQH8hQD+DWGepyCBIlb0NA13YEoLMcRKDcWvSPd0UGWo2G0IOeUZaGuzzIz2n04QrXvnqQKAOFd9yH2VfGtWE=</wsse:BinarySecurityToken>
    <ds:Signature Id="SIG-96" xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
      <ds:SignedInfo>
        <ds:CanonicalizationMethod Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#" xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
          <ec:InclusiveNamespaces PrefixList="soapenv web" xmlns:ec="http://www.w3.org/2001/10/xml-exc-c14n#"></ec:InclusiveNamespaces>
        </ds:CanonicalizationMethod>
        <ds:SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1" xmlns:ds="http://www.w3.org/2000/09/xmldsig#"></ds:SignatureMethod>
        <ds:Reference URI="#id-95" xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
          <ds:Transforms xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
            <ds:Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#" xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
              <ec:InclusiveNamespaces PrefixList="web" xmlns:ec="http://www.w3.org/2001/10/xml-exc-c14n#"></ec:InclusiveNamespaces>
            </ds:Transform>
          </ds:Transforms>
          <ds:DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1" xmlns:ds="http://www.w3.org/2000/09/xmldsig#"></ds:DigestMethod>
          <ds:DigestValue xmlns:ds="http://www.w3.org/2000/09/xmldsig#">whvAdAkypsWVXHXbIz/T54n0dBw=</ds:DigestValue>
        </ds:Reference>
      </ds:SignedInfo>
      <ds:SignatureValue>
        MdHy5mceNtQWUD5WmVOzZU8roxD3EQkQmcZA9LsfhBcp3cFAD3P1qJJ9EyrRFBs5yCiYDY716Wzh
        M+tFybt1+EujXZZ3ytk4XaahkexNAG51iup1wvw0Km+nsj4u/x8DzTA/J9EG3ZdTSUrIVBsFcEQa
        TF4BwUAgGBS87xqL5zc=
      </ds:SignatureValue>
      <ds:KeyInfo Id="KI-B259DAB3D28E48CB6A140000796019095">
        <wsse:SecurityTokenReference wsu:Id="STR-B259DAB3D28E48CB6A140000796019096" xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
          <wsse:Reference URI="#X509-B259DAB3D28E48CB6A140000796019094" ValueType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-x509-token-profile-1.0#X509v3" xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd"></wsse:Reference>
        </wsse:SecurityTokenReference>
      </ds:KeyInfo>
    </ds:Signature>
    <wsu:Timestamp wsu:Id="TS-94">
      <wsu:Created xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">2014-05-13T19:06:00.188Z</wsu:Created>
      <wsu:Expires xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">2014-05-13T19:07:00.188Z</wsu:Expires>
    </wsu:Timestamp>
  </wsse:Security>
</soapenv:Header>

Este es el que estoy pasando que no funciona:

<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/" xmlns:u="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
  <s:Header>
    <VsDebuggerCausalityData xmlns="http://schemas.microsoft.com/vstudio/diagnostics/servicemodelsink">uIDPowmum40QT95GqsY7XPKT7LIAAAAAvMwgorinWU+AVOWH+3TPjP6NBU03AZtHqle8GLRYcYAACQAA</VsDebuggerCausalityData>
    <o:Security s:mustUnderstand="1" xmlns:o="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
      <u:Timestamp u:Id="_0">
        <u:Created>2014-05-15T21:30:20.723Z</u:Created>
        <u:Expires>2014-05-15T21:35:20.723Z</u:Expires>
      </u:Timestamp>
      <o:BinarySecurityToken u:Id="uuid-16d1441d-2f30-40a0-ae4e-ec5d557d2261-2" ValueType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-x509-token-profile-1.0#X509v3">MIIC9jCCAd6gAwIBAgIINNZyZplkQHgwDQYJKoZIhvcNAQEFBQAwNzERMA8GA1UEAwwIQWRtaW5DQTExFTATBgNVBAoMDEVKQkNBIFNhbXBsZTELMAkGA1UEBhMCU0UwHhcNMTQwMzIwMTgzMjQ3WhcNMTgxMjIwMTQzNzEzWjBCMRUwEwYDVQQDDAxjb3Vycmllci5kaGwxDDAKBgNVBAsMA09QUzEOMAwGA1UECgwFREhMUFkxCzAJBgNVBAYTAlBZMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCGoP0dxByIfto/hqJCOhobTdwQJ3AxJkqUeSNFnprAH8zi6HjBJhzkXptqXiR9GZR1H4U3UaN6aczKVh2PaPqU8ooTxjST0ywWBgXA1WP3ukrybUKxpSvqmiRJ/cANAYLovL+gmh2v/fqPiLs7vsgT+zj1330wRGqtrokYPMjlbQIDAQABo38wfTAdBgNVHQ4EFgQU6IHB4XfP7+rbryy1Ru8kFcfSDqcwDAYDVR0TAQH/BAIwADAfBgNVHSMEGDAWgBQxftYTknYINgxTlKH5513cfU8Y3jAOBgNVHQ8BAf8EBAMCBPAwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMA0GCSqGSIb3DQEBBQUAA4IBAQB3NQC+0/VmC7A1MStKdc2NctTo7P+mhvIBe54U/Vs8I5vXiatKz01BzHIbl7chjP063V4YTtehDCGkwUTtARqpkua7RfdlMqsmcr1s3qnD4lUpGuAeVW0Wsrhu1xGjPf02fTBdD3yyGWCeUiNvKuoweeATlGyB/VlHJaZHN4HuJCnWlPic6uUUMBYqrOOa+wJr/OCFHqkEiBsUihD6ergj7AeAAFcG41GI2ZjVWK/PEB71sbQqqGgLpigAS9f8PNMm+TnQuizrvLPKm3hanOKYr9ORrbWjZCL3dva1YobK4ykvUYpncj6YsOtuDi62RcHYjT7IF9UoeZHBE2vePc+K</o:BinarySecurityToken>
      <Signature xmlns="http://www.w3.org/2000/09/xmldsig#">
        <SignedInfo>
          <CanonicalizationMethod Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/>
          <SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1"/>
          <Reference URI="#_0">
            <Transforms>
              <Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/>
            </Transforms>
            <DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/>
            <DigestValue>pM8KraJSLZumo77gD9+JF2f8eBU=</DigestValue>
          </Reference>
        </SignedInfo>
        <SignatureValue>MZ9ZTKeGj5KNUEn4R6cQhRhOdK0frNK1O5KRGbM+YqfvzlVwVKQ6n7p9rncbtrdGsLg3CVwUVwB7PBF78tDx3p0LjF/Eg015t6qouSyK/92qL3oRz/8TbqLKpe/1uySdmGhrqPrVlTDF2rHuFGwmQVSILyUVLg/nW7K+EDwS/Lg=</SignatureValue>
        <KeyInfo>
          <o:SecurityTokenReference>
            <o:Reference URI="#uuid-16d1441d-2f30-40a0-ae4e-ec5d557d2261-2"/>
          </o:SecurityTokenReference>
        </KeyInfo>
      </Signature>
    </o:Security>
  </s:Header> 
</s:Envelope>