AES Codeoptimierung auf at91sam7x256 (ARM7TDMI)

[Marcel B. (cable545)]

Juten Abend,

ich hab zu Übungszwecken mal eine AES Implementierung für mein 
at91sam7x256 gebastelt. Die Implementierung hällt sich ziemlich streng 
an die ganzen Referenzimplementierungen, die vom AES so im Netz 
rumschwirren. Nun bin ich die ganze Zeit am Testen und habe irgendwie 
das Gefühl das die Verschlüsselung echt lange dauert. Der Code ist 
komplett in C geschrieben. Die Daten die ich verschlüssele bzw. 
entschlüssele werden blockweise über den SPI Bus von einer SD Karte 
gelesen und dort auch wieder geschrieben. Nach einigen Tests kann ich 
jedoch sagen, dass die Lese- bzw. Schreibvorgänge eine Verschlüsselung 
von größeren Dateien nicht stark beeinflusst. Als Blockchiffren Modi 
nutze ich den ECB bzw. CBC Mode. Beide nehmen sich nicht sonderlich 
viel, was die Geschwindigkeit angeht. Ich kann letzten Endes behaupten, 
dass wenn es irgendwas zu optimieren gibt, es irgendwo im eigentlichen 
Algorithmus sein muss.

Um es mal auf den Punkt zu bringen, eine Verschlüsselung einer bmp 
Bilddatei mit der Größe von ca. 198 kByte dauert knapp 63,5 s. Jetzt 
frage ich mich, inwiefern ich auf der Ebene von dem C-Code noch was 
optimieren könnte.

Ich poste hier mal den Code vom AES. Vielleicht fällt ja jemanden auf 
was ich hier besser machen kann. Ich bin für jeden Tipp dankbar!!!

/*---------------------------------------------------------------
                                helper 
-----------------------------------------------------------------*/

static uint8_t getSBoxValue(uint8_t num)
{
    return SBox[num];
}

static uint8_t getRSBoxValue(uint8_t num)
{
    return RSBox[num];
}

static uint32_t galoisMulti(uint8_t fact_1, uint8_t fact_2)
{
  uint32_t product = 0;
  uint8_t i, hi_bit_set;
        
  //for(i = 0; i < 8; i++)
  for(i = 8; i > 0; i--)
  {
    if((fact_2 & 1) == 1)
    {
      product ^= fact_1;
    }
    
    hi_bit_set = fact_1 & 0x80;
    fact_1 <<= 1;
      
    if(hi_bit_set == 0x80)
    {
      fact_1 ^= 0x1B;
    }
    
    fact_2 >>= 1;
  }
    
  return product;
}

static void createRoundKey(uint8_t* expandedKey, uint8_t* roundKey)
{
  uint8_t i, j;
  
  // Iterate over the columns
  for (i = 0; i < 4; i++) 
  {
    // Iterate over the rows
    for (j = 0; j < 4; j++) 
    {
      roundKey[(i + (j * 4))] = expandedKey[(i * 4) + j];
    }
  }
}

/*---------------------------------------------------------------
                                Sub Bytes 
-----------------------------------------------------------------*/

static void subBytes(uint8_t* block)
{
  uint32_t i;

  for(i = 0; i < BLOCK_SIZE; i++)
  {
    block[i] = getSBoxValue(block[i]);
  }
}

static void iSubBytes(uint8_t* block)
{
  uint32_t i;

  for(i = 0; i < BLOCK_SIZE; i++)
  {
    block[i] = getRSBoxValue(block[i]);
  }
}

/*---------------------------------------------------------------
                               Shift Rows
-----------------------------------------------------------------*/

static void shiftRow(uint8_t* row, uint8_t rNumber)
{
  uint8_t i, j, tmp;
  
  //for(i = 0; i < rNumber; i++)
  for(i = rNumber; i > 0; i--)
  {
    tmp = row[0];
    
    for(j = 0; j < 3; j++)
    {
      row[j] = row[j + 1];
    }
    
    row[3] = tmp;
  }
}

static void shiftRows(uint8_t* block)
{
  uint8_t i;
  
  for(i = 1; i < 4; i++)
  {
    shiftRow(block + (i * 4), i);
  }
}

static void iShiftRow(uint8_t* row, uint8_t rNumber)
{
  uint8_t i, j, tmp;
  
  //for(i = 0; i < rNumber; i++)
  for(i = rNumber; i > 0; i--)
  {
    tmp = row[3];
    
    for(j = 3; j > 0; j--)
    {
      row[j] = row[j - 1];
    }
    
    row[0] = tmp;
  }
}

static void iShiftRows(uint8_t* block)
{
  uint8_t i;
  
  for(i = 1; i < 4; i++)
  {
    iShiftRow(block + (i * 4), i);
  }
}

/*---------------------------------------------------------------
                               Mix Columns
-----------------------------------------------------------------*/

static void mixColumns(uint8_t* block)
{
  uint32_t i, j;
  uint8_t columnNumber = 4;
  uint8_t tmp[16];

  for(i = 0; i < columnNumber; i++)
  {
    tmp[i] =
      galoisMulti( block[i], 0x02 ) ^ galoisMulti( block[columnNumber + i], 0x03 )
        ^ galoisMulti( block[2 * columnNumber + i], 0x01 ) ^ galoisMulti( block[3 * columnNumber + i], 0x01 );
    tmp[columnNumber + i] =
      galoisMulti( block[i], 0x01 ) ^ galoisMulti( block[columnNumber + i], 0x02 )
        ^ galoisMulti( block[2 * columnNumber + i], 0x03 ) ^ galoisMulti( block[3 * columnNumber + i], 0x01 );
    tmp[2 * columnNumber + i] =
      galoisMulti( block[i], 0x01 ) ^ galoisMulti( block[columnNumber + i], 0x01 )
        ^ galoisMulti( block[2 * columnNumber + i], 0x02 ) ^ galoisMulti( block[3 * columnNumber + i], 0x03 );
    tmp[3 * columnNumber + i] =
      galoisMulti( block[i], 0x03 ) ^ galoisMulti( block[columnNumber + i], 0x01 )
        ^ galoisMulti( block[2 * columnNumber + i], 0x01 ) ^ galoisMulti( block[3 * columnNumber + i], 0x02 );
  }
        
  //for (j = 0; j < BLOCK_SIZE; j++)
  for (j = BLOCK_SIZE; j > 0; j--)
  {
    block[j] = tmp[j] & 0xf0ff;
  }
}

static void iMixColumns(uint8_t* block)
{
  uint32_t i, j;
  uint8_t columnNumber = 4;
  uint8_t tmp[16];

  for (i = 0; i < columnNumber; i++)
  {
    tmp[i] =
      galoisMulti(block[i], 0x0e) ^ galoisMulti(block[columnNumber + i], 0x0b)
        ^ galoisMulti(block[2 * columnNumber + i], 0x0d) ^ galoisMulti(block[3 * columnNumber + i], 0x09);
    tmp[columnNumber + i] =
      galoisMulti(block[i], 0x09) ^ galoisMulti(block[columnNumber + i], 0x0e )
        ^ galoisMulti(block[2 * columnNumber + i], 0x0b) ^ galoisMulti(block[3 * columnNumber + i], 0x0d);
    tmp[2 * columnNumber + i] =
      galoisMulti(block[i], 0x0d) ^ galoisMulti(block[columnNumber + i], 0x09)
        ^ galoisMulti(block[2 * columnNumber + i], 0x0e) ^ galoisMulti(block[3 * columnNumber + i], 0x0b);
    tmp[3 * columnNumber + i] =
      galoisMulti(block[i], 0x0b) ^ galoisMulti(block[columnNumber + i], 0x0d)
        ^ galoisMulti(block[2 * columnNumber + i], 0x09) ^ galoisMulti(block[3 * columnNumber + i], 0x0e);
  }
  
  //for (j = 0; j < BLOCK_SIZE; j++)
  for (j = BLOCK_SIZE; j > 0; j--)
  {
      block[j] = tmp[j] & 0xf0ff;
  }
}

/*---------------------------------------------------------------
                               Add Round Key
-----------------------------------------------------------------*/

static void addRoundKey(uint8_t* text, uint8_t* roundKey )
{
  uint8_t i;
  
  //for(i = 0; i < 16; i++)
  for(i = 16; i > 0; i--)
  {
    text[i] ^= roundKey[i];
  }
}

/*---------------------------------------------------------------
                               Key expansion
-----------------------------------------------------------------*/

static void rotate(uint8_t* column)
{
  uint8_t i, tmp;
  
  tmp = column[0];
  
  for(i = 0; i < 3; i++)
  {
    column[i] = column[i + 1];
  }
  
  column[3] = tmp;
}

static void keyScheduleCore(uint8_t* word, uint32_t rconIteration)
{
  rotate( word );
  subBytes( word );
  word[0] ^= R_CON[rconIteration];
}

static void expandKey(uint8_t* expandedKey, uint32_t expandedKeySize, uint8_t* cipherKey, uint8_t keySize)
{
  uint32_t i, currentSize = 0, rconIteration = 1;
  uint8_t tmp[4] = {0};

  //for(i = 0; i < keySize; i++)
  for(i = keySize; i > 0; i--) 
  {
    expandedKey[i] = cipherKey[i];
  }
  
  currentSize += keySize;
  
  
  while(currentSize < expandedKeySize)
  {
    //asign the previous 4 byte to tmp
    for(i = 0; i < 4; i++) 
    {
      tmp[i] = expandedKey[(currentSize - 4) + i];
    }
    
    // every 16, 24, 32 ... bytes call keyScheduleCore
    if((currentSize % keySize) == 0) 
    {
      keyScheduleCore(tmp, rconIteration++);
    }
    
    if(keySize == Bits256 && ((currentSize % keySize) == 16)) 
    {
      //for(i = 0; i < 4; i++) 
      for(i = 4; i > 0; i--) 
      {
        tmp[i] = getSBoxValue(tmp[i]);
      }
    }
    
    for(i = 0; i < 4; i++) 
    {
      expandedKey[currentSize] = expandedKey[currentSize - keySize] ^ tmp[i];
      currentSize++;
    }
  }
}

static void round(uint8_t* block, uint8_t* roundKey)
{
  subBytes(block);
  shiftRows(block);
  mixColumns(block);
  addRoundKey(block, roundKey);
}

static void finalRound(uint8_t* block, uint8_t* roundKey)
{
  subBytes(block);
  shiftRows(block);
  addRoundKey(block, roundKey);
}

/*---------------------------------------------------------------
                               AES Encryption
-----------------------------------------------------------------*/

void aesEncrypt(uint8_t* block, uint8_t* cipherKey, uint8_t keySize)
{
  uint8_t roundKey[16];
  uint8_t expandedKey[240] = { 0 };
  uint8_t i, expandedKeySize, rounds;
  expandedKeySize = GET_EXP_KEYSIZE(keySize);

  setLED(LED_YELLOW);

  expandKey(expandedKey, expandedKeySize, cipherKey, keySize);

  if(keySize == Bits128)
    rounds = 10;
  else if(keySize == Bits192)
    rounds = 12;
  else
    rounds = 14;

  createRoundKey(expandedKey, roundKey);
  addRoundKey(block, roundKey);
  
  for (i = 1; i < rounds; i++) 
  {
    createRoundKey(expandedKey + 16 * i, roundKey);
    round(block, roundKey);
  }

  createRoundKey(expandedKey + 16 * rounds, roundKey);
  finalRound(block, roundKey);
  
  resetLED(LED_YELLOW);
}

/*---------------------------------------------------------------
                               AES Decription
-----------------------------------------------------------------*/

void aesDecrypt(uint8_t* block, uint8_t* cipherKey, uint8_t keySize)
{
  uint8_t roundKey[16];
  uint8_t expandedKey[240] = { 0 };
  uint8_t i, expandedKeySize, rounds;
  expandedKeySize = GET_EXP_KEYSIZE(keySize);
  
  setLED(LED_YELLOW);

  expandKey(expandedKey, expandedKeySize, cipherKey, keySize);
  
   if(keySize == 16)
    rounds = 10;
  else if(keySize == 24)
    rounds = 12;
  else
    rounds = 14;
  
  createRoundKey(expandedKey + 16 * rounds, roundKey);
  addRoundKey(block, roundKey);
  iShiftRows(block);
  iSubBytes(block);
  
  for (i = rounds - 1; i > 0; i--) 
  {
    createRoundKey(expandedKey + 16 * i, roundKey);
    addRoundKey(block, roundKey);
    iMixColumns(block);
    iShiftRows(block);
    iSubBytes(block);
  }
  
  createRoundKey(expandedKey, roundKey);
  addRoundKey(block, roundKey);
  
  resetLED(LED_YELLOW);
}

[Frank K. (fchk)]

Compiliere das Zeugs mal auf einem PC und lass dann einen Profiler 
mitlaufen. Der sagt Dir dann, wo die "Hotspots" sind, d.h. welche 
Funktionen und Codezeilen besonders viel Rechenzeit brauchen.

Falls Du noch nichts von Profilern gehört hast:
http://www.codeplanet.eu/tutorials/cpp/68-c-cpp-profiler.html

Auf den ersten Blick empfehle ich Dir die beiden ersten Funktionen 
getSBoxValue() und getRSBoxValue() entweder inline zu machen oder in 
Form von Makros zu implementieren. Das ist einfach und macht nicht viel 
Arbeit.

fchk

[(prx) A. K. (prx)]

uint8_t bei Skalaren nur dann verwenden, wenn mit nicht mehr als 8 Bits 
gerechnet werden darf - unsigned oder uint_fast8_t verwenden. ARM 
rechnet mit 32 Bits schneller als mit 8 Bits. Return-Werte ebenfalls 
nicht als uint8_t deklarieren.

Diesen zeitkritischen Code ins RAM legen und als ARM Code übersetzen, 
nicht als Thumb, ggf. Interworking verwenden. Der Durchsatz vom AT91 
Flash ist für Thumb optimiert und für nativen ARM Code zu gering.

Optimierung des Compilers einschalten, mindestens -O2.

[Frank K. (fchk)]

weitere Überlegungen:

1. Schleifenvariablen als unsigned int anstelle uint8_t deklarieren. x86 
kann in Registern direkt mit Bytes arbeiten, andere Architekturen wie zB 
ARM nicht.

Beispiel:
in R5 steht ein uint8_t a=0xe0.
in C: a+=0x40; -> ASM: add r5,#40h
in R5 steht jetzt 0xe0+0x40=0x120
Da R5 ja nur ein uint8_t ist, muss normalisiert werden
mov r0,#ffh
and r5,r0
Jetzt steht das drin, was gemäß C Standard drin stehen sollte: 0x20

mit int statt short oder int8_t vermeidest Du das.

2. Vergleiche
if((fact_2 & 1) == 1)
hier kann nur 0 oder 1 rauskommen. Statt auf ==1 zu prüfen, prüfe besser 
auf !=0. Das kann der Prozessor einfacher.
Ändern in:   if((fact_2 & 1) != 0)
oder kürzer: if(fact_2 & 1)

genauso:
    hi_bit_set = fact_1 & 0x80;
    fact_1 <<= 1;

    if(hi_bit_set == 0x80)
->  if(hi_bit_set) // das kann ja auch nur 0 oder 0x80 sein, und der 
Vergleich auf Null oder nicht NUll ist schneller gemacht als der 
Vergleich mit einer Konstante.

Das sind alles Kleinigkeiten, aber die summieren sich.

fchk

[Marcel B. (cable545)]

ui, das sind ne Menge Tipps. Ich danke Euch. Ich werde dann meine 
Ergebnisse erläutern.

[Frank K. (fchk)]

Ich habe eben durch Zufall noch einen möglichen Fehler entdeckt:

  for (j = BLOCK_SIZE; j > 0; j--)
  {
    block[j] = tmp[j] & 0xf0ff;
  }

block[j] und tmp[j] sind uint8_t. Der andere Operand des bitweisen Unds 
ist aber ein 16 Bit Wert. Die obere Hälfte wird weggeworfen, die untere 
Hälfte ist 0xff, und tmp[j] & 0xff ist eben immer tmp[j]. Das wirst Du 
wohl kaum so beabsichtigt haben.

fchk

[Christian V. (michse)]

hab den code jetzt aufgrund von Uhrzeit und alkohol nicht gelesen, aber 
zumindest auf einem PC ist eine lookup-table für die galoiMulti 
überlegenswert.

[123 (Gast)]

So hört sich das langsam an? Mal ein bischen rechnen.

198*1024*8/128=12672 AES Blöcke

63500ms/12673=5ms je block

So ich nahm jetzt mal 30MHz an.

Macht dan 150000 CPU cycles. Im Vergleich zu avr crypt deutlich 
langsamer. Da stehen 22000 bzw. 40000 je Durchgang.
In ASM lässt sich am avr noch deutlich was rausholen 2600 bzw 6700 
cycles je Durchgang.

Ich würde sagen da geht noch was.
CPU tackt (auf was war der bisher eingestellt)
Code aus RAM ausführen.
Compiler Optimierung aktivieren. (Speed)
Die sboxen auch im RAM halten. Ist schneller als aus dem langsamen 
flash.
Ggf 8 bit code auf 32 bit umbauen. Z.b. copier schleifen, ...

Gruß

[123 (Gast)]

So da sind ja noch einige Sachen drin....

Den block ggf als 4*32bit verarbeiten. Nicht als 8*8bit.
Alle XOR als32 bit aus führen. Den rotate als >>> definieren nicht als 
byte swap.
Die ganzen kurzen loops vermeiden. Die verursachen einen neu füllen der 
Pipeline.

(Aufpassen mit dem endien Format. Nicht geprüft ob das Probleme machen 
könnte)

Gruss

[Andreas (Gast)]

passt nicht ganz rein in deine HW Platform aber als Referenz:

ich habe mir Samples vom neuen SAM4C geholt da dieser auch einen Crypto 
Coprocessor. Auf diesem erreiche ich für 1KByte Daten 15uS.

[Nosnibor (Gast)]

Als erstes würde ich ja die Schlüsselexpansion nicht für jeden Block neu 
berechnen; die ändert sich nämlich nicht, solange der Schlüssel gleich 
bleibt.
Also: expandKey() einmal am Anfang aufrufen, und aesDecrypt() bekommt 
dann direkt expandedKey übergeben anstatt cipherKey.

Schlüsselexpansion bei jedem Block macht man nur, wenn der Speicher so 
knapp ist, daß man die ca. 200 Bytes zwischendurch dringend anderweitig 
braucht. Oder bei akademischem proof-of-concept-Code, der mit 
Flußdiagrammen und Schaubildern übereinstimmen muß.

[Marcel B. (cable545)]

Okay, ich habe nun endlich mal Zeit gefunden mich dem Thema wieder 
einmal auseinander zusetzen. Der ganze AES Code inklusive der Block 
Modis CBC bzw. ECB (hab ich hier nicht gepostet) liegt nun nicht mehr im 
Flash sondern im Ram. Ich führe außerdem die Schlüsselausdehnung (danke 
für den Tipp :) ) nur noch beim ersten Datenblock durch. Alle danach 
folgenden Blöcke nutzen ja den gleichen Schlüssel -> also gleicher 
expandedKey. Ich habe auch einige Schleifen geändert, sprich Prüfung auf 
index >= 0. Das gleiche auch bei den wenigen If -Else Bedingungen.
Die Datentypen von byte/char zu int(also 32 bit) habe ich noch nicht 
geändert...kommt aber noch. Ach so, die Compiler Optimierung auf Zeit, 
ist nun auch dabei.

Im Endeffekt benötigt nun der Vorgang wie er Eingangs von mir erklärt 
wurde nur noch 16 Sekunden :) WOW kann ich da nur sagen. Vielen Dank für 
die vielen Tipps. Ihr habt mir echt geholfen.

@ Frank K.
Ähm ja, keine Ahnung wo das & 0xf0ff herkam. War auf jeden Fall falsch 
und gehört dort nicht hin. Vielen Dank!!

123 schrieb:
> Alle XOR als32 bit aus führen. Den rotate als >>> definieren nicht als
> byte swap.
Den rotate als >>> definieren? Das versteh ich nicht. Kann mir das 
jemand erläutern?

Viele Grüße

Marcel