Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
136 lines (127 sloc) 6.98 KB
---
layout: post
title: 'A less error prone HMAC-based hash construction'
subtitle: 'or how to avoid shooting yourself in the foot with HMAC'
permalink: '/salted_hmac/'
tags: ['crypto', 'security', 'engineering']
---
<div class="lead">
<p>
HMAC is a cryptographic construction that combines a hash function (e.g. md5 or sha256) and a key. The result of an HMAC function cannot be guessed by an attacker. Web applications therefore typically use HMACs for tokens in emails, tamper proof sessions or hidden form values, csrf protection nounces, OTP, etc.
</p>
<p>
Over the years, I have seen three common types of mistakes when computing/validating HMACs. I will go over each one of these mistakes and propose a construction which is less error prone when used by engineers with insufficient security knowledge.
</p>
<p>
The ideas here are applicable to all MAC functions, I picked HMAC because it's the most commonly used function in web applications.
</p>
<p>
Credits to Erling for helping me on the first iteration of this hash construction.
</p>
</div>
<section>
<div class="page-header"><h3>Why use HMAC in the first place?</h3></div>
<p>
I have seen keyed hashes being built with code like <code>hash = md5(secret + data)</code>, which
is prone to length extension attacks. Marginally better is <code>hash = md5(secret + ':' + data + ':' + secret)</code> at
which point why not just use an HMAC and benefit from the years of cryptographic research that has gone into
trying to break the hash construction?
</p>
</section>
<section>
<div class="page-header"><h3>Non-constant time comparison</h3></div>
<p>
The most common error I have seen is code using string comparison to validate the HMAC: <code>if (input.hash != hmac(algo, secret, input.data) { throw some exception }</code>.
</p>
<p>
The problem with using a string comparison function is that it does not run in constant time and leaks knowledge about how many bytes in the hash are correct. An attacker can deduct the value for the HMAC by sending a handful of requests to the web server.
</p>
</section>
<section>
<div class="page-header"><h3>Weakly typed programming languages</h3></div>
<p>
There are cases where an attacker can control the type of the hash. The simplest case is when the hash is extracted from a piece of JSON data: <code>{"hash":"fc4696cc79...","data":"hello world"}</code>. An attacker can trick the web application to treat the hash as an integer, boolean, or other data types by sending: <code>{"hash":0,"data":"hello world"}</code>.
</p>
<p>
In some weakly typed programming languages (e.g. PHP), when a string is compared to a boolean, the string is converted to a boolean (in PHP, most strings are true). An attacker could therefore simply provide <code>{"hash":true,...}</code> and bypass whatever was being protected by the HMAC.
</p>
<p>
Weakly typed languages usually offer a type preserving comparison function (e.g. === in PHP).
</p>
</section>
<section>
<div class="page-header"><h3>Difficulty to manage keys</h3></div>
<p>
The third issue is not a security issue, but if at some point you want to rotate the keys used to generate HMACs, it is not easy to tell which calls to HMAC are being used to generate hashes vs which ones are being used to validate them.
</p>
</section>
<section>
<div class="page-header"><h3>Creating a pair of keyed-hash functions</h3></div>
<p>
Here is a proposal for a pair of keyed-hash functions (one function to generate the hash, the other to validate it). The pair of functions does not suffer from the three issues mentioned above. The idea is to salt the HMAC function and fail attempts to use a string comparison function (with a probability of 99.6%). A nice side effect of using a pair of functions is to contain the hash validation logic in a single place, instead of having potential string comparisons in multiple places in the codebase.
</p>
<p>
The salt acts as a forcing factor for engineers to do the right thing.
</p>
<p>
Pseudo-code:
</p>
<pre class="prettyprint linenums lang-c">
/**
* Generates a salted HMAC for a given piece of data.
*
* Note: the string returned by this function is one byte longer
* than the result of hmac.
*/
function generate_salted_hmac (algo, key, data) {
h = hmac(algo, key, data);
// Use an IV to "salt" the hmac result
// The IV does not need to be cryptographically strong since it does not
// affect the strenght of the hmac
iv = random(0, 255);
r = String.fromCharCode(iv);
for (i=0; i&lt;h.length; i++) {
r += String.fromCharCode(h.charCodeAt(i) ^ iv);
}
return r;
}
/**
* Validates if a given piece of data and its
* salted HMACs have been tampered with.
*/
function validate_salted_hmac(algo, key, data, hash) {
// Recreate the expected HMAC value
h = hmac(algo, key, data);
iv = hash.charCodeAt(0);
r = String.fromCharCode(iv);
for (i=0; i&lt;h.length; i++) {
r += String.fromCharCode(h.charCodeAt(i) ^ iv);
}
if (hash.length != r.length) {
// Assumption is that an attacker knows the length of a valid hash.
return false;
}
// Compare r with hash in constant time
ok = 0;
for (i=0; i&lt;r.length &amp; i&lt;hash.length; i++) {
ok = ok | r.charCodeAt(i) ^ hash.charCodeAt(i);
}
return ok == 0;
}
</pre>
</section>
<section>
<h3>Links</h3>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Hash-based_message_authentication_code" class="external">Wikipedia page</a> about HMAC</li>
<li><a href="http://en.wikipedia.org/wiki/Length_extension_attack" class="external">Wikipedia page</a> about hash length extension attacks</li>
<li><a href="http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf" class="external">Opportunities and Limits of Remote
Timing Attacks</a> by Scott A. Crosby, Dan S. Wallach and Rudolf H. Riedi (Rice University, 2009)</li>
<li><a href="http://php.net/manual/en/types.comparisons.php#types.comparisions-loose" class="external">PHP's loose comparison table</a></li>
<li><a href="http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf" class="external">Remote Timing Attacks are Practical</a> by David Brumley, Dan Boneh (Stanford University, 2003)</li>
<li><a href="https://www.isecpartners.com/blog/2011/february/double-hmac-verification.aspx" class="external">Double HMAC Verification</a> by iSec's Brad Hill</li>
<li><a href="http://www.security-assessment.com/files/documents/presentations/TimingAttackPresentation2012.pdf" class="external">Login Timing Attacks For Mischief and Mayhem</a> (applicable only in the non-MAC case)</li>
<li><a href="http://codahale.com/a-lesson-in-timing-attacks/" class="external">codahale's post</a> (don't use java.security.MessageDigest before Java SE 6 Update 17)</li>
<li><a href="https://gist.github.com/sneves/10845247" class="external">ct32.c</a> (sometimes you need to fight the compiler... See also <a href="http://rt.openssl.org/Ticket/Display.html?id=3558#txn-48922" class="external">openssl patch</a>)</li>
</ul>
</section>