2010-12-16

Information leakage

Recently there have been allegations that the ipsec implementation of OpenBSD has been tampered with.  I have no idea whether there is any truth to the allegations or not.  I am not a cryptanalyst nor am I an expert in applied cryptography or the branches of mathematics that you ought to know really well to truly understand the underlying theory -- and neither are you.

Now, there has been much speculation and much discussion in various forums around the web.  None of which seems to be burdened by any overwhelming level of insight.  Most people have a very naïve idea of what it takes to "compromise" a cryptosystem and think that we are talking about simple bugs.  Buffer overflows, important bits of information carelessly being exposed to unprivileged parts of the system in plaintext etc.

One concept that seems to be very hard to understand is the idea of a side-channel.  So I figured I'd have crack at (pardon the pun) giving an example of a side-channel leaking information in a security system.

Most of you have an idea of how a rotary combination lock works.   You twiddle a dial in alternate directions, stopping at a predetermined numbers, the rotors inside the lock line up, and eventually will allow the lock to be opened.  On the surface of things this could be a very time-consuming undertaking if you have no idea what sequence of numbers and turns you need to perform.

However, there may be shortcuts.  Depending on the quality of the lock it might have one or more side-channels that can be used to figure out the combination.  Two such side channels are feel and sound.  The feel of the dial, the lock handle and the sounds that the lock makes can impart information about its design and even provide usable information as to what the combination is.

Of course, most safes are fairly good these days so it would take a bit of experience to open them, but the one my parents used to have took less than an hour to crack when i was 12 years old.

I knew it had a 4 number combination and I knew that the sequence called for 3, 2 and then 1 turn between the first and the last number (again, by listening to it being opened by my dad, though not seeing any of the numbers).  The dial had numbers from 1 to 100, so in theory a great number of combinations that it would take a lot of time to go through.

After giving the problem some thought I had a mental model of what must be going on inside the safe -- how you mechanically align a number of rotors by rotating them in an alternating pattern (which I found out years later to be correct when I found a diagram of a similar lock).  Armed with that knowledge plus a theory of how the rotors must work, opening the thing was just a matter of learning how to feel what the rotors were doing and attacking the problem systematically.

And as I indicated earlier: it worked.  Mostly because the combination lock on that safe was poorly designed and leaked information.  Also, my dad opening the safe while I was in the next room was a process that leaked a lot of information.  In fact, the number of turns is what made me understand how the rotors must interact with each other.



Similar leakage of information can occur in cryptosystems due to poor design.  If you deliberately want to leak information about the internal state of the encryption process, or compromise the integrity of the system, it is more than likely that you would be able to sneak it past most people who only have a rough idea of cryptography, the underlying math or the practical reality of the implementations and operating environments. People tend to have very vocal debates over things they feel they understand. But you rarely see people saying "okay, I absolutely don't understand this -- explain it to me" when something more difficult needs to be done. If someone who we think know what he or she is doing does something we rarely question them for fear of coming off as stupid or uninformed. This is an exploitable (social) weakness.

So to those of you who think that we are talking buffer overflows and backdoors with magic passwords: your understanding of the alleged problem in OpenBSD being debated is orders of magnitude off and you could benefit from opining less and reading more.

No comments:

Post a Comment