New Stanford paper on DJB's AES timing attack
karl malbrain
attack:
www.stanford.edu/~jbonneau/AES_timing.pdf
karl m
Tom St Denis
Cool. I wonder why people haven't investigated slotting as a fix to
this? My earlier attempt had some success but I didn't take into
account the 16-byte windows which killed alignment.
I don't see why if you manage to get all memory accesses in the same
pipeline that you'd have any cache attack to speak of.
Tom
D. J. Bernstein
attacks isn't new in this context, but I don't think anyone realized
that a few thousand timings would be enough to deduce an AES key.
The main research questions regarding AES vulnerability---see, e.g.,
http://cr.yp.to/talks.html#2006.06.15---are the same now as they were
before:
(1) convincing a remote program, such as the Linux kernel, to knock
selected lines out of cache;
(2) understanding how many packets are needed to eliminate network
noise and see a small timing signal.
Regarding countermeasures, the paper is a step backwards. The special
last-round table was already eliminated in the AES implementation that I
published in February 2005. My implementation also handles
* compressing the AES tables down to just 2K,
* controlling memory accesses to avoid associativity limits,
* controlling stack positions to avoid load-store conflicts, and
* controlling load timing to avoid cache-bank throughput limits.
I'm not aware of any cache-timing attacks on an OS-kernel AES call that
(1) disables interrupts/hyperthreading/etc.,
(2) loads the AES tables into cache,
(3) waits for the loads to complete, and then
(4) uses my implementation.
On the other hand, without adequate CPU documentation, I'm certainly not
going to make any guarantees. My implementation relies on quite a lot of
CPU-specific work; I wouldn't be at all surprised to see another source
of time variability on existing CPUs or on future CPUs.
The bottom line is that S-boxes (arrays with input-dependent indices)
create absurdly complex, fragile, vulnerability-prone cryptographic
systems. The obvious way out of this mess is to stop using S-boxes. All
of the ``focus'' ciphers in eSTREAM, the ECRYPT Stream Cipher Project,
are faster than AES, and three of them---Trivium, Phelix, and my own
Salsa20---avoid S-boxes entirely.
---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago
jt...@tele2.se
"BR JT (Yóu know the one with the full entropy ciphers) No shitty
S-box
here no man it is not for me. They are masterpieces in ignorance and
stupidity."
Tom St Denis skrev:
jt...@tele2.se
Oh no it is all trustworthy streambuddy...
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int keysize=0;
int ordered[256];
int reversed[256];
int streamout[256];
/*PRNG*/
int streambuddy()
{
int mixpad[256];
int slot_1,slot_2,slot_3,slot_4;
int i;
for(i=0;i<256;i++)
{
if(i==255){
/*WRAPAROUND CASE*/
slot_1 = ordered[0];
slot_2 = ordered[slot_1];
ordered[slot_1] = ordered[i];
ordered[i] = slot_2;
slot_3 = reversed[0];
slot_4 = reversed[slot_3];
reversed[slot_3] = reversed[i];
reversed[i] = slot_4;
} else {
slot_1 = ordered[i+1];
slot_2 = ordered[slot_1];
ordered[slot_1] = ordered[i];
ordered[i] = slot_2;
slot_3 = reversed[i+1];
slot_4 = reversed[slot_3];
reversed[slot_3] = reversed[i];
reversed[i] = slot_4;
}
}
for(i=0;i<256;i++)
{
mixpad[i] = reversed[i] ^ ordered[i];
}
for(i=0;i<256;i++)
{
streamout[i] ^= mixpad[i];
}
return 0;
}
/*KEYXPAND*/
int keyexpander(int key[], int keysize)
{
int serie[256];
int i=0,j=0,k=0;
int stop=0;
int found=0;
for(i=0;i<256;i++)
{
stop=0;
while(!stop)
{
found = 0;
for(k=0;k<i;k++)
{
if(key[j]==serie[k]){found=1;}
}
if(!found)
{
serie[i]=key[j];stop=1;
} else
{
key[j] = key[j]+1;
}
if(key[j] > 255) {
key[j]=0;
}
}
j++;
if(j > keysize-1) {j=0;}
}
for(k=0;k<42;k++)
{
for(i=0;i<255;i++)
{
int slot_1,slot_2;
slot_1 = serie[i+1];
slot_2 = serie[slot_1];
serie[slot_1] = serie[i];
serie[i] = slot_2;
}
}
for(i=0;i<256;i++)
{
ordered[i]=serie[i];
}
return 0;
}
int ireverse()
{
int i;int j=0;int slot1;int slot2;
for(i=255;i>-1;i--)
{
reversed[j] = ordered[i];
j++;
}
/*A mechanism to make the reversed block out of phase*/
for(i=0;i<7;i++){
slot1 = reversed[i+1];
slot2 = reversed[slot1];
reversed[slot1] = reversed[i];
reversed[i] = slot2;
}
return 0;
}
int saltIV(int keyread[]){
int i;
srand(clock());
for (i=0;i<4;i++){
keyread[i]=rand()%256;
}
return 0;
}
int IDkeyfix(int keyread[]){
int s,r,j,k;
int sum=128;int dup;
r=keysize;
for(k=0;k<r;k++){
dup=0;
s=keyread[k];
for(j=0;j<r;j++){
if
((s==keyread[j])&&(j!=k)&&(dup!=1)){dup=1;sum=sum+s*k;keysize=keysize+1;keyread[keysize]=sum%256;
printf("%d",keyread[keysize]);printf(",");}
}
}
return 0;
}
int decrypt()
{
int keyread[256];
int text[256];
int i,j,k;
FILE* in;
FILE* out;
printf("\n\n\nInput password for decode: ");
keysize=4;
in=fopen("cipher.txt","rb");
/*GET KEY SALTIV+PASSWD*/
for(i=0;i<4;i++){keyread[i]=getc(in);}
while ((keyread[keysize]=getchar())!=10){keysize++;}
printf("\n\nIV+password:");
for(i=0;i<keysize;i++){printf("%d",keyread[i]);printf(",");}
/*EXPAND KEY AND CREATE REVERSED SHADOW*/
IDkeyfix(keyread);
keyexpander(keyread,keysize);
ireverse();
/*MAKE SURE ARRAY DONT GET FUCKED UP*/
for(i=0;i<256;i++){
streamout[i]=0;
}
printf("\n\n\nWait while decrypt 102 MB to disk...+-1min");
/*DECRYPT FILE*/
out=fopen("decipher.txt","wb");
for(k=0;k<20;k++){
for(j=0;j<20000;j++){
streambuddy();
for(i=0;i<256;i++){
text[i]=getc(in);
text[i]^=streamout[i];
fputc(text[i],out);
}
}
}
fclose(in);
fclose(out);
printf("\n\n\nFINISHED!!");
return 0;
}
int encrypt()
{
int keyread[256];
int text[256];
int i,j,k;
FILE* in;
FILE* out;
/*CREATE ZEROFILLED PLAINTEXT*/
printf("\n\n\nWait!! while 102 MB zerofilled plaintext created
+-1min");
out=fopen("plain.txt","wb");
for(k=0;k<20;k++){
for(j=0;j<20000;j++)
{
for(i=0;i<256;i++)
{
fputc('0',out);
}
}
}
fclose(out);
out=fopen("cipher.txt","wb");
keysize=4;
/*CREATE KEY ->IV+PASSWORD*/
saltIV(keyread);
printf("\n\n\nInput password for encode:");
for(i=0;i<4;i++){fputc(keyread[i],out);}
while ((keyread[keysize]=getchar())!=10){keysize++;}
printf("\n\nIV+password:");
for(i=0;i<keysize;i++){printf("%d",keyread[i]);printf(",");}
/*EXPAND KEY AND CREATE REVERSED SHADOW*/
IDkeyfix(keyread);
keyexpander(keyread,keysize);
ireverse();
for(i=0;i<256;i++){streamout[i]=0;}
/*ENCRYPT FILE*/
in=fopen("plain.txt","rb");
printf("\n\n\nWait while encrypt 102 MB to disk...+-1 min");
for(k=0;k<20;k++){
for(j=0;j<20000;j++){
streambuddy();
for(i=0;i<256;i++){
text[i]=getc(in);
text[i]^=streamout[i];
fputc(text[i],out);
}
}
}
fclose(in);
fclose(out);
return 0;
}
int main(void){
encrypt();
decrypt();
return 0;
}
Tom St Denis skrev:
jt...@tele2.se
ideas and acknowledge the geniality "simple, scalable, fast and with
full entropy".
Unfortunatly there is to many parrots...
D. J. Bernstein skrev: