Early std.crypto

[Piotr Szturmaj]

bcs wrote:
> On 11/04/2011 04:27 AM, Piotr Szturmaj wrote:
>> bcs wrote:
>>> Are you re-implementing the function kernels your self or are you using
>>> an existing implementation? Given what I've heard about things like
>>> side-channel attacks using processing times to recover keys, I'd rather
>>> not see Phobos use anything written by less than the best expert
>>> available.
>>
>> Until now, I implemented some hash functions. There are no branching
>> instructions in their transform() routines, so theoretically processing
>> time is independent of the function input.
>
>  From my very incomplete memory I found the source I was looking for (I
> googled for "aes interperative dance") here
> http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
> Look for "Foot-Shooting Prevention Agreement" in one of the images
> ~20-25% of the way down.
>
> tl;dr; It mentions "cache-based, timing, and other side channel
> attacks". Unless you can explain to me what those are, in painful
> detail, I don't think we should trust you to avoid them. Get a good
> vetted C implementation and wrap it with a nice D API and call it a day.

Sorry for late answer.

I didn't implement AES yet, but it can be implemented without lookup 
tables (countermeasure to cache-timing attacks).

Branch-free code without secret-data dependent memory accesses is free 
from cache-timing vurnelabilities on most architectures. The remaining 
are architectures where instruction execution times (cycles) may depend 
on data (f.i. multiply by 0 may take 1 cycle, and >2 cycles when 
multiplying by other numbers). I don't know any concrete examples but I 
realize such cycle-varying instructions _may_ exist. Of course such 
instructions must be avoided in secure code.

The most hard to avoid side channel attack is Power Analysis. On almost 
all CPUs instruction power drain depends on the operands. Again 
multiplying by 0 consume less power than multiplying by other numbers 
and that may be distinguished on the oscilloscope. There are some 
countermeasures including operand blinding, but not all crypto 
algorithms support that.

I only implemented some hashing functions: MD5, SHA1/224/256/384/512 and 
Tiger1/2. MD5 and SHA have code that is branch-free and does not use any 
data dependent lookups so their execution time should be constant, 
making timing attacks harmless.

Unfortunately Tiger function does lookups based on the source bytes and 
is vurnelable to cache-timing attacks. This may be considered insecure 
and removed (openssl does not support it either) as making it secure may 
be not worth it.

The only problem that remain is the power analysis which require 
physical access to the computer. We need to ask ourselfs to what degree 
we must secure our code. I'm going to argue that no single 
implementation is secure to power analysis on all architectures. I think 
we must stick to cache/branch timing level and forget about power 
analysis as its scope is beyond D's specification. We simply can't avoid 
most power analysis attacks because most of the countermeasures belong 
to the hardware instead of the software level.