November 4, 2014

Thought experiment on protocols and noise

Filed under: Crypto,Network,Protocols,Security — Nate Lawson @ 10:42 am

I hesitate to call this an interview question because I don’t think on-the-spot puzzle solving equates to a good engineering hire. On the other hand, I try to explore some simple thought experiments with candidates that have a security background.

One of these involves a protocol that has messages authenticated by an HMAC. There’s a message (with appropriate internal format) and a SHA-256 HMAC that covers it. As the implementer, you receive a message that doesn’t verify. In other words, your calculated MAC isn’t the same as the one in the message. What do you do?

“Throw an error” is a common response. But is there something more clever you could do? What if you could tell whether the message had been tampered with or if this was an innocent network error due to noise? How could you do that?

Some come up with the idea of calculating the Hamming distance or other comparison between the computed and message HMACs. If they are close, it’s unlikely that the message had been corrupted, due to the avalanche property of secure hash functions. If not, it may be a bit flip in the message, possibly due to an attack.

Ok, you can distinguish whether the MAC had a small number of errors or the message itself. Is this helpful, and is it secure? Consider:

  • If you return an error, which one do you return? At what point in the processing?
  • Does knowing which type of error occurred help an attacker? Which kind of attacker?
  • If you chose to allow up to 8 flipped bits in the MAC while still accepting the message, is that secure? If so, at what number of bits would it be insecure? Does the position of the bits matter?

There comes a moment when every engineer comes up with some “clever” idea like the above. If she’s had experience attacking crypto, the next thought is one of intense unease. The unschooled engineer has no such qualms, and thus provides full employment for Root Labs.


  1. I would fail this question. If it was asked on Hacker News or Twitter I would have raised objections. As an already hired employee I would put the requester through a two hour meeting and make him or her come up with good reasons before I even thought about coding something like this. In an interview situation, if the interviewer asked a question like this I would assume it was because they wanted an answer about how to solve it. It would be a bad assumption on my part in this case, but arguing with the interviewer about the validity of the question will in the majority of the interviews not get you the job.

    Comment by Tony — November 4, 2014 @ 12:14 pm

    • I don’t ask it as a pass/fail question, it’s more of “here’s something fun to explore together”. It’s not really an interview question in the traditional sense as I don’t usually ask it of interviewees. I don’t like the the “solve this puzzle for points” method of interviewing and our interviews are quite different.

      What happens more often is we find things like this during audits. It’s usually not as clever/interesting, though the developer usually thinks it is. “Hey, I found a safe way to reuse an IV” or “check out my 15 options to provide algorithm agility” are more like what we find. Nobody in their company found it because there are lots of these kinds of issues, lurking in nearly every piece of code there.

      What’s even more difficult is trying to convince them to change it. Once you think something is clever, it’s many times harder to reverse your opinion. But removing “clever” deviations and replacing them with boring, less functional substitutes is what it takes to secure a design. And that’s why I sometimes sound like a curmudgeon to said developers.

      Comment by Nate Lawson — November 4, 2014 @ 5:39 pm

  2. You say curmudgeon, I say mature, responsible professional engineer :)

    Comment by Anonymouse — November 11, 2014 @ 4:43 pm

RSS feed for comments on this post.

Blog at WordPress.com.