Re: Patch: cprng_fast performance - please review.

[Thor Lancelot Simon <tls%panix.com@localhost>]

On Fri, Apr 18, 2014 at 04:26:19PM +0000, Taylor R Campbell wrote:
>
> Closer inspection of HC-128 reveals that it uses secret-dependent
> array indices[*], so for that reason alone I don't think we should
> adopt it.  It also has a very large state, which is going to hurt the
> cache on big systems and hurt the stack on little systems.

I'm willing to split the changes as you suggest (though I am running
out of time to work on this, so I have no idea when we'll get anywhere
practicaly useful any more).  However, I note that:

        1) The state doesn't have to go on the stack.

        2) Small requests (which are the preponderance) won't
           touch the whole state.  Large requests already touch
           enough memory to -- inevitably -- blow cache lines
           all on their own; this is a data-generating function
           after all.

        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?

           The very small number of ciphers selected for the portfolio
           (from literally hundreds of candidate submissions)
           were extensively cryptanalyzed by the best cryptographers
           in the world for almost five years.  If they gave HC-128 the
           nod -- expressly for software use -- I am not inclined to
           second-guess them.

        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.

        5) Do please recall that the application here is not generation
           of key material, but, rather, generation of initialization
           vectors, randomization of memory addresses, etc.

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.

Thor