Kubattack
Kubattacken är en metod för kryptoanalys som är tillämplig på en mängd olika symmetriska nyckelalgoritmer, publicerad av Itai Dinur och Adi Shamir i ett förtryck i september 2008.
Ge sig på
En reviderad version av detta förtryck lades ut online i januari 2009, och uppsatsen har också accepterats för presentation på Eurocrypt 2009.
Ett chiffer är sårbart om en utgående bit kan representeras som ett tillräckligt låggradigt polynom över GF(2) av nyckel- och ingångsbitar; i synnerhet beskriver detta många strömchiffer baserade på LFSRs . DES och AES tros vara immuna mot denna attack. Det fungerar genom att summera ett utmatningsbitvärde för alla möjliga värden för en delmängd av offentliga inmatningsbitar, valda så att den resulterande summan är en linjär kombination av hemliga bitar; upprepad tillämpning av denna teknik ger en uppsättning linjära relationer mellan hemliga bitar som kan lösas för att upptäcka dessa bitar. Författarna visar att om chifferet liknar ett slumpmässigt polynom av tillräckligt låg grad kommer sådana uppsättningar av publika inmatningsbitar att existera med hög sannolikhet, och kan upptäckas i en förberäkningsfas genom "svarta lådans undersökning" av sambandet mellan ingång och utdata för olika val av offentliga och hemliga inmatningsbitar som inte använder någon annan information om chiffrets konstruktion.
Uppsatsen presenterar en praktisk attack, som författarna har implementerat och testat, på ett strömchiffer på vilket ingen tidigare känd attack skulle vara effektiv. Dess tillstånd är en 10 000 bitars LFSR med ett hemligt tät återkopplingspolynom, som filtreras av en array av 1000 hemliga 8-bitars till 1-bitars S-boxar , vars inmatning är baserad på hemliga tappningar till LFSR-tillståndet och vars utdata är XORed tillsammans. Varje bit i LFSR initieras av ett annat hemligt tätt kvadratiskt polynom i 10 000 nyckel- och IV- bitar. LFSR klockas ett stort och hemligt antal gånger utan att producera några utdata, och sedan görs endast den första utdatabiten för en given IV tillgänglig för angriparen. Efter en kort förbearbetningsfas där angriparen kan fråga utdatabitar för en mängd olika nyckel- och IV-kombinationer, krävs endast 2 30 bitars operationer för att upptäcka nyckeln för detta chiffer.
Författarna hävdar också en attack på en version av Trivium reducerad till 735 initialiseringsrundor med komplexitet 2 30 , och gissningar att dessa tekniker kan sträcka sig till att bryta 1100 av Triviums 1152 initialiseringsomgångar och "kanske till och med det ursprungliga chiffer". I december 2008 är detta den bästa attacken kända mot Trivium.
Attacken är dock indragen i två separata kontroverser. För det första Daniel J. Bernstein påståendet att ingen tidigare attack mot det 10 000-bitars LFSR-baserade strömchifferet existerade, och hävdar att attacken på trivium med reducerad runda "inte ger någon verklig anledning att tro att (hela) Trivium kan attackeras”. Han hävdar att Cube-tidningen misslyckades med att citera ett existerande papper av Xueja Lai som beskriver en attack på chiffer med smågradiga polynom, och att han tror att Cube-attacken bara var en ny uppfinning av denna befintliga teknik.
För det andra krediterar Dinur och Shamir Michael Vielhabers "Algebraic IV Differential Attack" (AIDA) som en föregångare till Cube-attacken. Dinur har uttalat vid Eurocrypt 2009 att Cube generaliserar och förbättrar AIDA. Vielhaber hävdar dock att kubattacken inte är mer än hans attack under ett annat namn. Det är dock erkänt av alla inblandade parter att Cubes användning av ett effektivt linjäritetstest som BLR-testet resulterar i att den nya attacken tar kortare tid än AIDA, även om hur betydande denna förändring är förblir omtvistad. Det är inte det enda sättet som Cube och AIDA skiljer sig åt. Vielhaber hävdar till exempel att de linjära polynomen i nyckelbitarna som erhålls under attacken kommer att vara ovanligt glesa. Han har ännu inte tillhandahållit bevis för detta, men hävdar att sådana bevis kommer att dyka upp i ett kommande dokument av honom själv med titeln "The Algebraic IV Differential Attack: AIDA Attacking the full Trivium". (Det är inte klart om denna påstådda sparsamhet gäller för några andra chiffer än Trivium.)
