Re: Patch: cprng_fast performance - please review.

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

   Date: Fri, 18 Apr 2014 12:38:38 -0400
   From: Thor Lancelot Simon <tls%panix.com@localhost>

           3) If the algorithm's use of state-dependent array indices
              presents a real weakness in practice, why aren't there any
              published results on this and why was it chosen as, and
              does it still remain in, the eSTREAM software portfolio?

Hardly anyone uses HC-128, so there's no glory in publishing a
practical timing attack on it.  It has been clear since 1996, and it
has become abundantly clear in the past year with multiple practical
timing attacks on OpenSSL and GnuPG, that timing side channels are a
serious issue.  It would be irresponsible of us to make new choices
that invite timing side channels, and secret-dependent array indices
do precisely that.

For what it's worth, there has been some work on cache-timing attacks
on HC-128/256: <http://erikzenner.name/docs/2008_cache_sac.pdf>.

           4) If you've got a better suggestion of a stream cipher to use
              for this purpose, please make it.  I looked at all the eSTREAM
              ciphers and this one really looks like the best suited to me.

I would still suggest Salsa20 or ChaCha.  My measurements with naive C
code suggest that, if you buffer the output for short outputs, these
take on average 40-50 Ivy Bridge cycles per request.  (If you don't
buffer the output, it's 300 cycles.)  Long requests get ~4 cpb.  In
contrast, libc random(3) takes on average 50-60 Ivy Bridge cycles per
request, and long requests get ~13 cpb.

There's high public confidence in Salsa20 and ChaCha, we don't have to
worry about cache-timing side channels, we don't have to worry about
hurting the cache, and we don't have to worry about using an obscure
algorithm even if eSTREAM did select it.

   Here's what I don't want to do: adjust the bookkeeping and leave us
   using RC-4.  It is dangerously broken.  I am very hesitant to commit
   any changes to HEAD which overhaul this code in any way but leave RC-4
   in use.

We certainly need to get rid of RC4.  We don't need to get rid of it
in one single commit, though.  A commit that makes it easier to get
rid of RC4 by separating the algorithm from the bookkeeping is still
worthwhile.