Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Optimerade implementationer av DES och AES » Kryptoblog

Optimerade implementationer av DES och AES

June 26th, 2008 by Joachim Strömbergson Leave a reply »

EE Times har publicerat en artikel om effektiv implementation av DES och AES i programvara.

Artikeln Acceleleration of Symmetric-Key Algorithms in Software, skriven av två anställda på DSP-tillverkaren Analog Devices (ADI) visar hur de får upp prestandan hos DES/3DES och AES på en Blackfin-DSP.

BlackFin
En ADI BlackFin.

S-boxen i DES accelereras genom att man använder en speciell instruktion kallad EXTRACT som gör det möjligt att extrahera ett valbart antal bitar i ett ord. I det här fallet används det för att få ut de sex bitar som används som adress till S-boxen.

Ett var i DES.
Vänstervarvet i DES med åtta S-boxar.

Även den slutgiltiga konkateneringen av det nya 32-bitvärdet från de åtta S-boxarna görs om till att bli ren addition mellan åtta 32-bitars tal, dvs bitarna läggs ej samman genom skift och OR. Resultaten är en implementation av DES som går två till tre gånger snabbare än referensimplementation.

För AES använder författarna en något annorlunda metod. Där är det inte specialinstruktioner som används, istället görs AES-funktionerna SubBytes(), ShiftRows() och MixColumns() om till en gemensam, tabellbaserad funktion. Lösningen är alltså att byta ALU-operationer mot minne.

Genom att expandera GF-multiplikationen i MixColumns(), applicera den på S-boxen i SubBytes() och de radskiftningar som skall utföras i ShiftRows() får de fram en tabell på 1024 Bytes. Denna tabell kan för varje Byte i AES 16 Byte stora tillståndsmatris kan ta fram nästa tillstånd inför AddRoundKey().

För att anropa den kombinerade funktionen krävs ett modifierat accessmönster för matrisen, ett mönster där fyra Bytes separerade fyra Bytes ifrån varandra plockas ut tillsammans som indata till den modifierade funktionen.

Den kombinerade funktionen.

Det jag saknar i artikeln är siffror på hur bra den modifierade AES-implementationen blev, motsvarande det som finns för DES. Räknar man på det borde det iaf bli en 3 * 4 = 12-dubblad prestanda jämfört med en implementation med separata funktioner, en implementation där varje Byte i matrisen behandlas separat. (Vilket dom iofs inte skulle göras för ShiftRows() även i en enkel referensimplementation.)

Jag saknar även en kommentar/tanke om hur känsliga de presenterade implementationerna är för sidoattacker. Hur stor varians i effektförbrukning finns det vid exekvering av EXTRACT-instruktionen beroende på inparametrar? Hur stor är variansen vid den ADD-baserade konkateneringen?

På samma sätt kan man resonera om AES-implementationen. Nu borde tabellen på 1024 Bytes få plats i internminnet i processorn (inte i en dynamisk cache), vilket skall eliminera varianser i accesstid.

En kul artikel. Speciellt tricket i AES-implementationen var spännande att se. För de som kan bränna 768 Bytes extra i interntillstånd är detta ett klart alternativ.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

Leave a Reply

You must be logged in to post a comment.