For us it was an iterative process that started with making a commitment to
do our best to do the right thing-- accepting that we don't control how the
users us the software and that to do a good job we must defend against a
very broad class of attacks... and that it's a good investment of time to
really refine the tools here so that the users have the least time lost
to worrying about the details of the underlying behavior. The earlier work on cache sidechannel attacks against OpenSSL also helped convince other people that this was important.
Pieter did a cache timing attack project against DES at his university in
2004. I had experience with modeling fine scale algorithm delays as part of
ultra-low latency audio codec work. So we had a little bit of additional background
beyond regular systems programming and mathematical experience.
We spent time studying other implementations and academic papers on the
subject-- just a product of searching and following citations-- and we implemented and measured (both in timing form and 'read
the assembly' form). Pieter had to do some algebraic work to adapt
a 'unified' group law approach to our curve and coordinate system.
[Then all of this also presented additional verification work to
validate that the new group law was algebraically correct.]
Because we accepted that this was going to be a considerable amount
of work, we didn't refrain from trying multiple ideas and throwing
things away. The libsecp256k1 codebase is written in a clean (IMO),
typesafe, heavily tested way that makes iteration easier.
We initially implemented a bit-slicing approach to achieve memory
access uniformity. After we thought we were at least a strict
improvement over OpenSSL, we contacted an outside expert (Yuval
Yarom, one of the authors of this paper, in fact) and they were
kind enough to give our implementation a look-- and pointed
out some additional research that showed our particular bit
slicing approach was not quite constant time on common hardware.
So we fixed that too.
I don't consider our work done on this-- we are likely vulnerable
to differential power analysis on at least some hardware. We've
implemented a basic level of blinding to harden against that-- but
without a good measurement setup it's hard to tell if our efforts are
helping (or maybe hurting, though that's unlikely). I loaned Thomas
Daede a USRP, and he's been attempting to set up a DPA continuous
integration rig for us (https://bitcointalk.org/index.php?topic=1319848.0);
but it's effort that is competing with a lot of other projects for
attention for all of us. Similarly some (now uncommon) hardware has things like data-variable time multipliers, and on that hardware little can be done beyond blinding; but again, without more analysis it's hard to know exactly where that stands.