Re: Interesting performance quirk.

["Peter C. Chapin" <pcc482719@gmail.com>]

David Thompson wrote:

>> Considering that cryptography is, almost by definition, used in security
>> sensitive programs it seems like issues of safety and correctness should
>> take priority over raw efficiency. Fast is good, of course, but it's
>> even more important to be both right and secure. Hence Ada and not C
>> (and definitely not assembly language).
>>
> Correctness is certainly vital, but the extreme nonlinearity of any
> good crypto algorithm means that even a small functional error will
> almost certainly show up very quickly and obviously.

I understand your point, but its not necessarily that simple. Take a look at

	http://www.schneier.com/blowfish-bug.txt

which describes a "common" implementation bug where the code
inadvertently overwrites a large number of key bits with 1 bits. Because
encryption and decryption process the key in the same way, this bug does
not reveal itself as a problem with round trip processing.

Now in this case one would expect any reasonable degree of testing to
show the problem... but that assumes the test cases were generated with
an implementation that is free of this issue. If multiple carefully
written implementations all agree that increases one's confidence in the
result, but what does that really prove? They could all be wrong in
exactly the same way. Here "being wrong" might well mean "weakened
security relative to published theoretical results."

For example, consider Blowfish again... the algorithm requires a large
number of digits from the hexadecimal expansion of pi during its
initialization. Where did I get those initial values? I copied them from
Schneier's reference implementation. I'm sure that's probably what a lot
of Blowfish implementors do. Yet what if they are wrong? My test cases
based on Schneier's published test vectors (on the site above) wouldn't
show the problem because we'd both be using the wrong initial values.
Should I believe those are really the digits from the hexadecimal
expansion of pi just because Schneier says so? No... more checking needs
to be done.

What I *should* do is write my own program to compute those values, use
a tool like SPARK to prove my program correct, and then cross check its
output with several other independently computed values for pi. In fact,
it's on my to-do list to do exactly this (but I admit it's fairly low in
priority right now). I'd be very surprised, of course, if Schneier's
value of pi is wrong but, hey, you never know.

> However, in
> modern systems it has become sometimes important to control exactly
> the instructions executed, and CPU's execution of those instructions
> (typically using assembler-dependent special operations), because of
> 'side-channel' (mostly timing and power) attacks that have been
> developed that take advantage of things like scheduling and caching
> behavior of the crypto machine code. So carefully written assembler
> can actually be more secure!

That's interesting. I've heard of these kinds of attacks before but I
admit that I don't know much about them. I'll have to look into it.
Thanks for the heads-up.

Peter