På Eurocrypt presenterades tydligen ett arbete av Alex Biryukov, Dmitry Khovratovich och Ivica Nikoli´c som visar på en ny attack mot AES-256. Deras presentation AES-256 Is Not Ideal ser ut att visa att med kopplade nycklar (related keys) går det att urskilja en sekvens genererad med AES från en slumpmässig sekvens.

Jag begriper för lite av den kortfattade presentationen för att avgöra hur mycket bättre deras resultat är en den bästa kända attacken med 26 related keys, 2**114 data och 2**173 time. Enligt en kommentar på Cryptography-listan hävdade författarna vid sin presentation att det nu finns praktisk möjlighet att bryta hashfunktioner byggda på round-funktionen i AES. Detta gör resultatet intressant för den pågående SHA-3-tävlingen då flera av kandidaterna lånar delar av eller hela round-funktionen.

Författarnas artikel om sin nya attack är tydligen godkänd för CRYPTO 2009, så om inte förr så vet vi mer i slutet av Augusti.

Jag har ägnat nåra timmar åt att gå igenom alla specifikationer för de olika SHA-3-kandidaterna. En sak som blev ganska uppenbar är vilken framgång och vilket inflytande AES som krypto och designstrategin i den bakomliggande algoritmen Rijndael har fått.

Av de 55 kandidater som finns listade på ECRYPTs SHA-3-Zoo återanvänder inte mindre än 21 kandidater koncept, komponenter eller tom hela roundfunktionen från AES och Rijndael. Den lista jag slängt ihop ser ut som följer (det blir engelska nu då jag även klippt citat:

• Abacus: MDS from AES.


• Arirang: S-box from AES. MDS from AES for some versions of the hash.


• Aurora: ShiftRows from AES.


• Cheeta: “Inspired by AES”


• Echo: Stated goal to reuse as much of AES as possible (hence the
  name). Complete AES round reused.


• Ecoh: AES “key wrap” reused.


• Gr0stl. S-box and diffusion directly from AES.


• JH: Differential propagation methodology from AES.


• LANE: SubBytes, ShiftRows and MixColumns reused from AES.


• Lesamnta: Reuse of the AES round as function F.


• Luffa: “Based on Rijndael-like transform”


• NaSHA: “Improved AES S-box.”


• SANDstorm: AES S-box,


• Sarmal: “An AES (or Whirlpool)-like nonlinear subround function g is used.”


• SHAMATA: “uses one of the AES primitive functions MixColumns to incorporate the message into the internal state and a modified version of the AES round function to mix the internal state.”


• SHAvite-3: “Iterates a round function based on the AES round.”


• StreamHash: S-box based on AES S-box.


• Tangle: Reuse of AES S-box.


• Twister: MDS concept from Rijndael and S-box from AES. ShiftRows from AES.


• Vortex: Based on Rijndael rounds.


• Waterfall: Rijndael S-box.

Jag är inte helt säker på om detta är bra eller inte.

Å ena sidan är AES och dess ingående komponenter några av de mest välanalyserade som går att uppbringa. Detta faktum är något flera av kandidaternas skapare tar upp i sin motivering av sin kandidaters säkerhet. Implementationsmässigt är det dessutom bättre om samma programkod (funktioner) går att använda till flera saker. Speciellt för inbyggda system med hårda krav på liten kodstorlek är detta naturligtvis eftersträvansvärt.

Samtidigt kan jag inte släppa känslan av att vi riskerar att hamna i en monokultur – att säkerheten i alla dess olika delar (konfidentialitet, autenticitet, integritet) bygger på en eller ett fåtal algoritmer eller komponenter. Vad händer om S-boxen i AES faktiskt visar sig väldigt svag?

Vidare var den uttalande tanken från NIST att SHA-3-tävlingen skulle stimulera till nytänkande och uppmuntra till att hitta nya koncept för att bygga hashfunktioner. Att det sker ett rejält brott mot Merkle-Damgård är uppenbart, men nu är det istället AES och Rijndael. Är det bra eller dåligt?

Det verkar dock som de flesta verkligen försökt att tänka i nya banor. I min snabbläsning hittade jag för övrigt att tre kandidater (Abacus, Keccak och Luffa) bygger på de nya (relativt färska 😉 svampfunktionerna. Dessutom såg jag bara tre kandidater (Chi, DynamicSHA, DynamicSHA2) är direkta utökningar av SHA-1 och SHA-2.