153 lines
4.9 KiB
Markdown
153 lines
4.9 KiB
Markdown
---
|
|
created_at: '2013-06-27T21:15:01.000Z'
|
|
title: AES timing variability at a glance (2005)
|
|
url: http://cr.yp.to/mac/variability1.html
|
|
author: ColinWright
|
|
points: 59
|
|
story_text: ''
|
|
comment_text:
|
|
num_comments: 7
|
|
story_id:
|
|
story_title:
|
|
story_url:
|
|
parent_id:
|
|
created_at_i: 1372367701
|
|
_tags:
|
|
- story
|
|
- author_ColinWright
|
|
- story_5954743
|
|
objectID: '5954743'
|
|
year: 2005
|
|
|
|
---
|
|
AES timing variability at a glance [D. J. Bernstein](../djb.html)
|
|
[Authenticators and signatures](../antiforgery.html)
|
|
[A state-of-the-art message-authentication code](../mac.html)
|
|
|
|
# AES timing variability at a glance
|
|
|
|
[Introduction](#intro)
|
|
[Understanding the pictures](#understanding)
|
|
[AMD Athlon](#athlon)
|
|
[Intel Pentium III](#piii)
|
|
[Intel Pentium M](#pm)
|
|
[IBM PowerPC RS64 IV](#sstar)
|
|
[Sun UltraSPARC III](#ultrasparciii)
|
|
|
|
## Introduction
|
|
|
|
The Rijndael designers and the NIST AES selectors claimed that it was
|
|
easy to make AES---in particular, the AES table lookups---run in
|
|
constant time. That claim was, and is, incorrect. The following pictures
|
|
demonstrate, in a visually obvious way, that common AES implementations
|
|
have data-dependent timings on a wide variety of platforms, even when
|
|
the timing software makes no special effort to knock AES table entries
|
|
out of cache.
|
|
|
|
These pictures also include my own AES software, which goes to a
|
|
tremendous amount of CPU-specific effort to reduce the timing
|
|
variability. I say \`\`reduce'' rather than \`\`eliminate'' for three
|
|
reasons: first, without help from the operating system, it's impossible
|
|
to guarantee that the AES tables are in cache throughout the AES
|
|
computation; second, even if the AES tables are in cache, there may be
|
|
timing variability too small to appear in these pictures and too obscure
|
|
to be documented by the CPU manufacturers; third, even if the in-cache
|
|
timings really are data-independent for these CPUs, other CPUs may pose
|
|
new problems. On the bright side, my software clearly has much less
|
|
timing variability than other AES libraries.
|
|
|
|
To understand why this is important, read my paper [Cache-timing attacks
|
|
on AES](../papers.html#cachetiming).
|
|
|
|
## Understanding the pictures
|
|
|
|
Each picture is a 256x256 array of 4x3 blocks, occupying 1024x768 pixels
|
|
overall. The inline images on this page are the first 512x384 pixels;
|
|
click to see the full pictures.
|
|
|
|
Each row of the picture is an AES key. Each column of the picture is an
|
|
AES input. Each key was applied repeatedly to each input, 3100 times on
|
|
average, in a random order. Each 4x3 block reflects the distribution of
|
|
AES cycle counts for one key and one input.
|
|
|
|
The 36 color intensities in each block (3 colors for 4x3 pixels) are
|
|
assigned, in a complicated order, to 36 AES cycle counts surrounding a
|
|
typical AES cycle count. Cycle counts outside this 36-cycle range are
|
|
clipped to the bottom and top.
|
|
|
|
\`\`Good'' pictures are regular 256x256 lattices, showing that every
|
|
(key,input) pair has the same distribution of cycle counts. Warning:
|
|
browsers that scale pictures to the screen size are likely to spoil the
|
|
pattern; make sure to view each picture at 1 dot per pixel.
|
|
|
|
\`\`Bad'' pictures are irregular, showing that different (key,input)
|
|
pairs have different distributions of cycle counts. Three examples, in
|
|
increasing order of irregularity: OpenSSL on the UltraSPARC has varying
|
|
colors in each column, showing key-dependent timings, and occasional
|
|
variance within rows, showing data-dependent timings for each key;
|
|
OpenSSL on the PowerPC RS64 IV is a complicated red-green pattern,
|
|
showing that half of the (key,input) pairs have one cycle count and the
|
|
other half have another; the OpenSSL and Gladman implementations on the
|
|
Athlon are random jumbles of dots, showing a tremendous amount of
|
|
data-dependent variability.
|
|
|
|
Here's how to generate your own pictures:
|
|
|
|
```
|
|
./v1 > v1.out
|
|
pnmcolormap 256 < v1.out > v1.palette
|
|
pnmremap -map=v1.palette < v1.out | ppmtogif > v1.gif
|
|
```
|
|
|
|
## AMD Athlon
|
|
|
|
OpenSSL:
|
|
[](v1-thoth-openssl.gif)
|
|
|
|
Gladman:
|
|
[](v1-thoth-gladman.gif)
|
|
|
|
Gladman, using 1K tables:
|
|
[](v1-thoth-gladman1k.gif)
|
|
|
|
My `aes_athlon`:
|
|
[](v1-thoth-athlon.gif)
|
|
|
|
## Intel Pentium III
|
|
|
|
OpenSSL:
|
|
[](v1-silverton-openssl.gif)
|
|
|
|
My `aes_ppro`:
|
|
[](v1-silverton-ppro.gif)
|
|
|
|
## Intel Pentium M
|
|
|
|
OpenSSL:
|
|
[](v1-whisper-openssl.gif)
|
|
|
|
Gladman:
|
|
[](v1-whisper-gladman.gif)
|
|
|
|
Gladman, using 1K tables:
|
|
[](v1-whisper-gladman1k.gif)
|
|
|
|
My `aes_ppro`:
|
|
[](v1-whisper-ppro.gif)
|
|
|
|
## IBM PowerPC RS64 IV
|
|
|
|
OpenSSL:
|
|
[](v1-tigger-openssl.gif)
|
|
|
|
My `aes_aix`:
|
|
[](v1-tigger-aix.gif)
|
|
|
|
## Sun UltraSPARC III
|
|
|
|
OpenSSL:
|
|
[](v1-icarus-openssl.gif)
|
|
|
|
My `aes_sparc`:
|
|
[](v1-icarus-sparc.gif)
|