Re: Fastcode AES B&V 1.1

From: Dennis (marianndkc_at_home3.gvdnet.dk)
Date: 12/27/04 

Date: Mon, 27 Dec 2004 21:45:49 +0100

> although I have very little time (3 commercial programs at work to
> verify/release until Jan 3, 2005), I want to make some comments:
>
> First of call congratulations to Dennis and John for their new FAST
> CODE. Interestingly I have abandoned a year ago a slightly different
> version like John's which is more directly derived from the standard
> Barreto/Rijmen code in favor for the pointer version, which was much
> faster in the old context.
>
> Dennis wrote in another thread: "I created two versions of the same
> function and results differed a lot. This means that we have a
> parallel to the usual codealignment issue. I believe that
> codealignment is a small issue here because the loops are not narrow
> and the functions are quite big too. This means that we have a
> dataalignment issue."

I still see this problem, but have not been able to find the exact reason.

> Concerning the benchmark problems, I found that code alignment has one
> of the biggest problems, as I wrote on my web site: "optimizing seems
> to be black magic. The cycles/times are heavily dependent on CPU,
> cache, compiler, code position, day of week :-)"

Yes but we try to get control of them all ;-) Usually we are succesfull, but
we still have some work to do in this challenge.

> I had a short email correspondence with Henrick Hellström about his
> very fast OpenStrSecII library available from
> http://sourceforge.net/projects/openstrsecii/
> (his encrypt/decrypt primitives are based on Brian Galdman's code and
> are really fast, chaining modes have optimization potential), here is
> a little snippet with an interesting trick

How fast is it compared to the current Fastcode winner?

> "Henrick,
>
> thank you for your informative answer (in both mails).
> >
> >A couple of other things:
> >
> >The asm implementations contain NOP commands for code alignment. They
> >might be adjusted by the application programmer, and that might affect
> >performance.

We sometimes do this is Fastcode too.

http://dennishomepage.gugs-cats.dk/CodeAlignment.xls

> Clever idea, but it is a pitty that we have to work around the
> missing code alignment features of Delphi and Pascal."

Yes. Vote here

http://qc.borland.com/wc/wc.exe/details?ReportID=6610
http://qc.borland.com/wc/wc.exe/details?ReportID=7560

> Another point may be that fast table driven AES implementations are
> vulnerable to timing attacks, there was a long discussion on sci.crypt
> and I think it is a real issue and not an artefact.

This means we must have a challenge where tables are not allowed !

> I don't have an URL handy but if you are interested, here is an
> abstract:
>
> "Cache-timing attacks on AES
>
> Daniel J. Bernstein
>
> Abstract. This paper warns against the use of S-boxes in cryptography.
> In particular, this paper shows that a simple cache-timing attack
> against AES software reveals some key bits; this paper also discusses
> some of the obstacles to constant-time array access on modern CPUs."
>
> Search the web for the file cachetiming-20041111.pdf or ..dvi or
> google for "Bernstein Cache-timing attacks".

http://cr.yp.to/antiforgery/cachetiming-20041121.pdf

> Merry Christmas and best wishes for the New Year

To you too ;-)

> Wolfgang

Best regards
Dennis