Det var inte så länge sedan jag bloggade om att det varit mycket attacker på det symmetriska blockkryptot AES det senaste dryga året. Och nu kommer ett par nya attacker.

Den första attacken är en attack på AES-algoritmen i sig och knyter därmed an direkt till de attacker jag bloggade om. Återigen är det Orr Dunkelman, Nathan Keller och Adi Shamir som ligger bakom den kryptanalytiska attacken.

Det intressanta med den här attacken är att till skillnad från de flesta attacker på AES-algoritmen kräver den här inte ett stort antal nycklar, utan bygger på en enskild nyckel. Just att de senaste årens attacker krävt ett stort antal relaterade (kopplade) nycklar har varit dessa attacker svaghet. Eller som EU-projektet ECRYPT II skriver i sin årliga rapport om nyckellängder och kryptoprimitiver:

We note that related-key attacks’ practical relevance depends on context, and these attacks are unlikely to affect practical uses of the AES algorithm.

Shamirs, Dunkelmans och Kellers nya attack, Improved Single-Key Attacks on 8-round AES kan därmed ses som ett svar på detta, Författarna skriver:

AES is the most widely used block cipher today, and its security is one of the most important issues in cryptanalysis. After 13 years of analysis, related-key attacks were recently found against two of its flavors (AES-192 and AES-256).

However, such a strong type of attack is not universally accepted as a valid attack model, and in the more standard single-key attack model at most 8 rounds of these two versions can be currently attacked. In the case of 8-round AES-192, the only known attack (found 10 years ago) is extremely marginal, requiring the evaluation of essentially all the 2**128 possible plaintext/ciphertext pairs in order to speed up exhaustive key search by a factor of 16.

In this paper we introduce three new cryptanalytic techniques, and use them to get the first non-marginal attack on 8-round AES-192 (making its time complexity about a million times faster than exhaustive search, and reducing its data complexity to about 1/32,000 of the full codebook).

In addition, our new techniques can reduce the best known time complexities for all the other combinations of 7-round and 8-round AES-192 and AES-256.

Fortfarande är det på AES-versioner med ett färre antal iterationer än det som normalt används. Men det är ännu ett sår i AES-bygget.

Den andra attacken är inte på algoritmen, utan en sidoattack på implementationen av AES - mer exakt på en datorplattform som exekverat AES och som sedan stängts av(!). Genom att använda verktyg för att lösa Boolean SAT-problem (svensutvecklade MiniSat) anpassad kryptoproblem – CryptoMiniSat. Detta verktyg har använts för att lösa en Boolesk beskrivning av nyckelschemaläggningen i AES kan dom återskapa nyckeln även från ett minne som varit avstängt och därmed tappat en stor del av sitt innehåll.

SRAM-minnen och till viss del även DRAM-minnen tappar sin information när strömmen kopplas bort, men kan behålla informationen under en längre tid – kallas data remanence. Speciellt i kalla förhållanden kan ett SRAM-minne behålla sin information under lång tid.

I artikeln Applications of SAT Solvers to AES key Recovery from Decayed Key Schedule Images visar Abdel Alim Kamal och Amr M. Youssef att dom för 10000 nycklar där 72% nycklen har förstörts (bitarna har ändrat värden slumpmässigt) kan dom återskapa 92% av nycklarna på mindre än 10 sekunder. Nu gäller detta inte enbart AES, utan som författarna skriver:

In this work, we modelled the problem of key recovery of the AES-128 key schedules from its corresponding decayed memory images as a Boolean SAT problem and solved it using the CryptoMiniSat solver. Our experimental results confirm the versatility of our proposed approach which allows us to efficiently recover the AES-128 key schedules for large decay factors.

The method presented in this work can be extended in a straightforward way to AES-192, AES-256 and other ciphers with key schedules that can be presented as a set of Boolean equations and, hence, lend themselves naturally to SAT solvers.

För den som vill läsa mer om data remanence rekommenderas Peter Gutmanns klassiska Data Remanence in Semiconductor Devices.