Securing a web service without relying on native authentication schemes

Question

Due to various business and technical circumstances, I have to create an internet-facing .NET 4.5 WCF web service which should be called only by a certain party while not using native authentication schemes (mainly because I don't have an SSL certificate available, which precludes X.509 and user/password authentication).

What I thought is:

1. A shared secret is shared between the server and the client.
2. The client gets a cryptographic nonce from the server.
3. The client computes an HMAC of the payload, the secret and the nonce.
4. The client sends the payload, the nonce and the HMAC to the server.
5. The server checks if the nonce and the HMAC are valid.

Assuming the payloads are not sensitive, I have a couple of questions regarding this implementation:

1. Is there a native authentication scheme I've overlooked (remember that everything will be plaintext).
2. Does this implementation prevent third parties from using the service?
3. Does this implementation prevent replay attacks?
4. Is there something security-wise I'm missing?

How the shared secret is generated:

var buffer = new byte[64];

using (var random = new RNGCryptoServiceProvider())
{
    random.GetBytes(buffer);
}

var secret = Convert.ToBase64String(buffer);

How the server issues and maintains tokens:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;

public class TokenManager
{
    private readonly List<Token> issuedTokens = new List<Token>();
    private readonly RandomNumberGenerator random = new RNGCryptoServiceProvider();

    private readonly static Lazy<TokenManager> Instance =
        new Lazy<TokenManager>(() => new TokenManager());

    private TokenManager()
    {
    }

    public static TokenManager Default => Instance.Value;

    public string IssueToken()
    {
        var now = DateTimeOffset.UtcNow;
        var value = this.GenerateTokenValue();

        lock (Instance)
        {
            this.issuedTokens.RemoveAll(a => a.ExpireMoment < now);
            this.issuedTokens.Add(new Token(value, now.AddSeconds(30)));
        }

        return value;
    }

    public bool IsValidToken(string value)
    {
        Token issuedToken;

        lock (Instance)
        {
            issuedToken = this.issuedTokens.SingleOrDefault(a => a.Value == value);

            this.issuedTokens.Remove(issuedToken);
        }

        return issuedToken != null && issuedToken.ExpireMoment > DateTimeOffset.UtcNow;
    }

    private string GenerateTokenValue()
    {
        var buffer = new byte[64];

        this.random.GetBytes(buffer);

        return Convert.ToBase64String(buffer);
    }

    private class Token
    {
        private readonly string value;
        private readonly DateTimeOffset expireMoment;

        public Token(string value, DateTimeOffset expireMoment)
        {
            this.expireMoment = expireMoment;
            this.value = value;
        }

        public DateTimeOffset ExpireMoment => this.expireMoment;
        public string Value => this.value;
    }
}

How the client and the server compute the payload hash:

using System;
using System.IO;
using System.Runtime.Serialization;
using System.Security.Cryptography;

public static class Hashing
{
    public static string ComputeHash<TGraph>(TGraph graph, string secret, string token)
    {
        using (var stream = new MemoryStream())
        {
            new DataContractSerializer(typeof(TGraph)).WriteObject(stream, graph);

            using (var hasher = new HMACSHA512(Convert.FromBase64String(secret).Concat(Convert.FromBase64String(token)).ToArray()))
            {
                return Convert.ToBase64String(hasher.ComputeHash(stream.ToArray()));
            }
        }
    }
}

How the web service is structured:

using System;
using System.Collections.Generic;
using System.Configuration;
using System.ServiceModel;

[ServiceContract]
public interface ISomething
{
    [OperationContract]
    string GetToken();

    [OperationContract]
    void Do(Payload payload, string token, string hash);
}

public class Something : ISomething
{
    public string GetToken()
    {
        return TokenManager.Default.IssueToken();
    }

    public void Do(Payload payload, string token, string hash)
    {
        if (!TokenManager.Default.IsValidToken(token))
        {
            throw new ArgumentException("token");
        }

        var computedHash = Hashing.ComputeHash(payload, "secret", token);

        if (hash != computedHash)
        {
            throw new ArgumentException("hash");
        }

        // DO THINGS
    }
}

(The previous snippets are meant to be MCVE, various optimizations — like reading the secret from the configuration — have been omitted.)

Answer 1

I'm a fan of extension methods and your ComputeHash method seems like a prime candidate to be made as such:

public static class Hashing
{
    public static string ComputeHash(this object graph, string secret, string token)
    {
        if (graph == null)
        {
            return null;
        }

        using (var stream = new MemoryStream())
        {
            new DataContractSerializer(graph.GetType()).WriteObject(stream, graph);
            using (var hasher = new HMACSHA512(Convert.FromBase64String(secret).Concat(Convert.FromBase64String(token)).ToArray()))
            {
                return Convert.ToBase64String(hasher.ComputeHash(stream.ToArray()));
            }
        }
    }
}

also, I do love your Token class. Done very well. But since you are using C# 6 features, why not go all the way and use read-only properties?

private sealed class Token
{
    public Token(string value, DateTimeOffset expireMoment)
    {
        this.ExpireMoment = expireMoment;
        this.Value = value;
    }

    public DateTimeOffset ExpireMoment { get; }

    public string Value { get; }
}

Answer 2

Security-wise, it looks pretty solid to me. The nonce prevents replays, the secret provides authentication and tamper-resistance. One thing you want to be careful about with cryptographic validation is revealing more information than necessary. In your case, your validation routine tells the client why the message was invalid - the token is no good or the hash fails. You'll want to obscure that. Even with the same exception thrown, you'll leak information about what failed via the timing. You probably want to compute the hash of the input even if the token isn't good, just to avoid revealing if the token is good. Sometimes you'll go so far as to use a constant-time string comparison (for the hash), but I don't think that's necessary in this case.

Code-wise, just a few suggestions:

1) The Lazy<TokenManager> seems like unnecessary complexity. I don't see what all of that buys you over just a normal Singleton implementation.

2) IsValidToken invalidates the token by removing it from the list, which is not suggested by its name. Maybe something like ConsumeToken?

3) A List is fine for a small number of valid tokens, but consider a hash-based container if there are going to be a lot of tokens.

4) You are somewhat vulnerable to a denial-of-service attack on the tokens, since you need to store each one (and they are in a sub-optimal container). No authentication is required to get a token. You could try to require authentication before issuing your token, or you can design your tokens so that they can be validated without being stored. The token would consist of a random part, an expiration time, and a signature (using a separate private key). Now you don't have to track the ones you've issued, though it's harder to prevent replay during the token lifetime.

Like I said in the comment though, you're already sharing a secret with the client. Generating a self-signed SSL cert and trusting it on the client is not fundamentally different, and you get all the benefits of SSL for free.