Unable to Connect to Remote WCF Service - SecurityNegotiationException

See more:

C#

WCF

I am starting off with WCF and i am following the samples from MSDN. I managed to run the Getting Started sample on one machine as well as by deploying the client & service on separate machines and remotely accessing the service.

My goal is to implement the Publish/Subscribe design pattern. I have managed to run it on one machine without any big issues. But when i am deploying client & service on different machine, my client is unable to connect to the service. I get the following exception:

System.ServiceModel.Security.SecurityNegotiationException was unhandled
  Message=The caller was not authenticated by the service.
  Source=mscorlib

(I can share the stack trace if necessary)

Here are my configurations:

Service - web.config

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <system.serviceModel>
    <protocolMapping>
      <add scheme="http" binding="wsDualHttpBinding"/>
    </protocolMapping>
    <behaviors>
      <serviceBehaviors>
        <behavior>
          <serviceMetadata httpGetEnabled="True"/>
          <serviceDebug includeExceptionDetailInFaults="False" />
        </behavior>
      </serviceBehaviors>
    </behaviors>
  </system.serviceModel>
</configuration>

Client - app.config

<?xml version="1.0" encoding="utf-8"?>
<configuration>
  <system.serviceModel>
    <bindings>
      <wsDualHttpBinding>
        <binding name="WSDualHttpBinding_ISampleContract" clientBaseAddress="http://<SERVICE MACHINE PUBLIC IP>:8000/myClient/"
                 closeTimeout="00:01:00"
                  openTimeout="00:01:00" receiveTimeout="00:10:00" sendTimeout="00:01:00"
                  bypassProxyOnLocal="false" transactionFlow="false" hostNameComparisonMode="StrongWildcard"
                  maxBufferPoolSize="524288" maxReceivedMessageSize="65536"
                  messageEncoding="Text" textEncoding="utf-8" useDefaultWebProxy="true">
          <readerQuotas maxDepth="32" maxStringContentLength="8192" maxArrayLength="16384"
              maxBytesPerRead="4096" maxNameTableCharCount="16384" />
          <reliableSession ordered="true" inactivityTimeout="00:10:00" />
          <security mode="Message">
            <message clientCredentialType="Windows" negotiateServiceCredential="true"
                algorithmSuite="Default"/>
          </security>
        </binding>
      </wsDualHttpBinding>
    </bindings>
    <client>
      <endpoint address="http://<SERVICE MACHINE PUBLIC IP>/ServiceModelSamples/service.svc"
          binding="wsDualHttpBinding" bindingConfiguration="WSDualHttpBinding_ISampleContract"
          contract="ISampleContract" name="WSDualHttpBinding_ISampleContract">
        <identity>
          <servicePrincipalName value="host/<SERVICE MACHINE PUBLIC IP>" />
        </identity>
      </endpoint>
    </client>
  </system.serviceModel>
</configuration>

I have searched for a solution but nothing has worked for me. I have tried to find a way to disable the security/authentication on the service side (just to get it work), but haven't been successful in that as well.

Any suggestions/solutions would be Hoping to get some positive feedback.

Regards.