One weakness of many Web services that require authentication, including the ones I’ve built in the past, is that the username and password of the user making the request are simply included as request parameters. Alternatively, some use basic authentication, which transmits the username and password in an HTTP header encoded using Base64. Basic authentication obscures the password, but doesn’t encrypt it.

This week I learned that there’s a better way — using a Hash-based Message Authentication Code (or HMAC) to sign service requests with a private key. An HMAC is the product of a hash function applied to the body of a message along with a secret key. So rather than sending the username and password with a Web service request, you send some identifier for the private key and an HMAC. When the server receives the request, it looks up the user’s private key and uses it to create an HMAC for the incoming request. If the HMAC submitted with the request matches the one calculated by the server, then the request is authenticated.

There are two big advantages. The first is that the HMAC allows you to verify the password (or private key) without requiring the user to embed it in the request, and the second is that the HMAC also verifies the basic integrity of the request. If an attacker manipulated the request in any way in transit, the signatures would not match and the request would not be authenticated. This is a huge win, especially if the Web service requests are not being made over a secure HTTP connection.

There’s one catch that complicates things.

For the signatures to match, not only must the private keys used at both ends of the transaction match, but the message body must also match exactly. URL encoding is somewhat flexible. For example, you may choose to encode spaces in a query string as %20. I may prefer to use the + character. Furthermore, in most cases browsers and Web applications don’t care about the order of HTTP parameters.

foo=one&bar=two&baz=three

and

baz=three&bar=two&foo=one

are functionally the same, but the crypto signature of the two will not be.

Another open question is where to store the signature in the request. By the time the request is submitted to the server, the signature derived from the contents of the request will be mixed in with the data that is used to generate the signature. Let’s say I decide to include the HMAC as a request parameter. I start with this request body:

foo=one&bar=two&baz=three

I wind up with this one:

foo=one&bar=two&baz=three&hmac=de7c9b8 ...

In order to calculate the HMAC on the server, I have to remove the incoming HMAC parameter from the request body and calculate the HMAC using the remaining parameters. This is where the previous issue comes into play. If the HMAC were not in the request, I could simply calculate the signature based on the raw incoming request. Once I start manipulating the incoming request, the chances of reconstructing it imperfectly rise, possibly introducing cases where the signatures don’t match even though the request is valid.

This is an issue that everyone implementing HMAC-based authentication for a Web service has to deal with, so I started looking into how other projects handled it. OAuth uses HMAC, with the added wrinkle that the signature must be applied to POST parameters in the request body, query string parameters, and the OAuth HTTP headers included with the request. For OAuth, the signature can be included with the request as an HTTP header or as a request parameter.

This is a case where added flexibility in one respect puts an added burden on the implementor in others. To make sure that the signatures match, OAuth has very specific rules for encoding and ordering the request data. It’s up to the implementor to gather all of the parameters from the query string, request body, and headers, get rid of the oauth_signature parameter, and then organize them based on rules in the OAuth spec.

Amazon S3’s REST API also uses HMAC signatures for authentication. Amazon embeds the user’s public key and HMAC signature in an HTTP header, eliminating the need to extract it from the request body. In Amazon’s case, the signed message is assembled from the HTTP verb, metadata about the resource being manipulated, and the “Amz” headers in the request. All of this data must be canonicalized and added to the message data to be signed. Any bug in the translation of those canonicalization rules into your own codes means that none of your requests will be authenticated by Amazon.com.

Amazon uses the Authorization header to store the public key and HMAC. This is also the approach that Microsoft recommends. I think it’s superior to the parameter-based approach taken by OAuth. It should be noted that the Authorization header is part of the HTTP specification and if you’re going to use it, you should do so in a way that complies with the standard.

For my service, which is simpler than Amazon S3 or OAuth, I’ll be using the Authorization header and computing the HMAC based on the raw incoming request.

I realize that HMAC may not be new to many people, but it is to me. Now that I understand it, I can’t imagine using any of the older approaches to build an authenticated Web service.

Regardless of which side of the Web service transaction you’re implementing, calculating the actual HMAC is easy. Normally the SHA-1 or MD5 hashing algorithms are used, and it’s up to the implementor of the service to decide which of those they will support. Here’s how you create HMAC-SHA1 signatures using a few popular languages.

PHP has a built-in HMAC function:

hash_hmac('sha1', "Message", "Secret Key");

In Java, it’s not much more difficult:

Mac mac = Mac.getInstance("HmacSHA1");
SecretKeySpec secret = 
    new SecretKeySpec("Secret Key".getBytes(), "HmacSHA1");

mac.init(secret);
byte[] digest = mac.doFinal("Message".getBytes());

String hmac = Hex.encodeHexString(digest);

In that case, the Hex class is the Base64 encoder provided by Apache’s Commons Codec project.

In Ruby, you can use the HMAC method provided with the OpenSSL library:

DIGEST  = OpenSSL::Digest::Digest.new('sha1')

Base64.encode64(OpenSSL::HMAC.digest(DIGEST, 
  "Secret Key", "Message"))

There are also libraries like crypto-js that provide HMAC support for JavaScript.

Kellan Elliott-McCrea has a great post about the high cost of false positives when it comes to building software that detects fraud, spam, abuse, or whatever. The cost of false positives is explained by the base rate fallacy. The BBC explains the base rate fallacy very well. Here’s a snippet:

If 3,000 people are tested, and the test is 90% accurate, it is also 10% wrong. So it will probably identify 301 terrorists – about 300 by mistake and 1 correctly. You won’t know from the test which is the real terrorist. So the chance that our man in the mac is the real thing is 1 in 301.

Anybody who wants to talk about screening systems without an understanding of the base rate fallacy needs to do more homework.

At work, we’re switching things to encrypt a lot of information in our databases for security reasons. The project has been time consuming and painful, and in the end, our database is far less usable from a developer’s standpoint than it was before. Soon the days when I can quickly diagnose issues on the production system with a few well-placed SELECT statements will be a thing of the past.

As far as the implementation goes, I’ll tell Hibernate users who want to implement an encryption system that there’s only one way to go — UserTypes. Don’t bother with anything else.

What this project really has me thinking about, though, is the high cost of security. It ties into something from the Bill James interview that I linked to the other day. Here was his response to the question of whether we overestimate or underestimate the importance of crime:

We underestimate it, because it’s our intent to underestimate it. We only deal with it indirectly. We all do so many things to avoid being the victims of crime that we no longer see those things, so we don’t see the cost of it. Just finding a safe place for us to have this conversation, for example — we needed a quiet place, but before that, we needed to find a safe place. A hotel lobby is what it is because of the level of security. I’ve checked out of this hotel, but I’m still sitting here in the third-floor lobby, because it’s safe. When you buy something, it’s wrapped in seven layers of packaging in order to make it harder to steal.

I think that people are generally excessively afraid of crime but underestimate the day to day costs that crime imposes. In software engineering, we spend a lot of time and effort on security. If everyone were honest, we wouldn’t need passwords, encryption, or any of the other stuff that occupies a lot of time on every project. We’d still need to take precautions against damage caused by user error, but most of the hours we spend on security could be spent on other things.

The other cost of security, beyond implementation time, is the ongoing cost related to the inconvenience of security. Whether it’s the time we take to unlock our screen or set up SSH tunnels or deal with the fact that we have to decrypt data in the database in order to see it, it all counts. Security is almost always a form of technical debt.

In many cases security precautions are necessary (or even mandated by law), but it’s important to be vigilant and not add more of it than is necessary, because it’s almost always painful in the moment and forever thereafter.