korn (chiffer)

Grain är ett strömchiffer som skickades till eSTREAM 2004 av Martin Hell, Thomas Johansson och Willi Meier. Den har valts ut för den slutliga eSTREAM-portföljen för Profil 2 av eSTREAM-projektet. Grain är främst designad för begränsade hårdvarumiljöer . Den accepterar en 80- bitars nyckel och en 64-bitars IV . Specifikationerna rekommenderar inte en maximal utdatalängd per (nyckel, iv) par. Ett antal potentiella svagheter i chifferet har identifierats och korrigerats i Grain 128a som nu är det rekommenderade chifferet att använda för hårdvarumiljöer som tillhandahåller både 128-bitars säkerhet och autentisering.

Beskrivning

Grains 160-bitars interna tillstånd består av ett 80-bitars linjärt återkopplingsskiftregister (LFSR) och ett 80-bitars icke-linjärt återkopplingsskiftregister (NLFSR). Grain uppdaterar en bit av LFSR och en bit av NLFSR-tillstånd för varje bit av chiffertext som släpps av en olinjär filterfunktion. 80-bitars NLFSR uppdateras med en icke-linjär 5-till-1 boolesk funktion och en 1-bitars linjär ingång vald från LFSR. Den olinjära 5-till-1-funktionen tar som ingång 5 bitar av NLFSR-tillståndet. 80-bitars LFSR uppdateras med en 6-till-1 linjär funktion. Under nycklingsoperationer återkopplas chifferets utdata dessutom som linjära indata till både NLFSR- och LFSR-uppdateringsfunktionerna.

I den ursprungliga Grain Version 0.0-inlämningen av Grain, levereras en bit av 80-bitars NLFSR och fyra bitar av 80-bitars LFSR till en icke-linjär 5-till-1 boolesk funktion (som är vald att vara balanserad, korrelationsimmun för första ordningen och har algebraisk grad 3) och utgången kombineras linjärt med 1 bit av 80-bitars NLFSR och släpps som utgång.

I den uppdaterade Grain Version 1.0-inlämningen av Grain, levereras en bit av 80-bitars NLFSR och fyra bitar av 80-bitars LFSR till en (något reviderad) icke-linjär 5-till-1 boolesk funktion och utmatningen kombineras linjärt med 7 bitar av 80-bitars NLFSR och släpps som utdata.

För att initiera chiffret laddas 80-bitars nyckeln direkt in i 80-bitars NLFSR och 64-bitars IV laddas in i de låga 64-bitar av LFSR och de återstående 16 höga bitarna i LFSR fylls med ettor. Chifferet är förseglat för 160 omgångar där de 160 bitarna av nyckelström som genereras återkopplas linjärt till både LFSR- och NLFSR-uppdateringsfunktionerna. Chifferet släpper ingen nyckelströmsutgång under initieringsprocessen.

Grains författare diskuterar de fullständiga spridningshastigheterna för Grain-initieringsprocessen i Grain version 1.0-specifikationerna: "För initiering med två olika IV:er, som skiljer sig endast med en bit, bör sannolikheten att en skiftregisterbit är densamma för båda initieringarna vara nära 0,5 . Simuleringar visar att detta uppnås efter 160 klockningar."

Prestanda

Chifferet är utformat för att tillåta upp till 16 omgångar att utföras parallellt, vilket möjliggör snabbare implementeringar till priset av större hårdvaruanvändning.

säkerhet

Nyckelstorleken är 80 bitar och IV-storleken är specificerad till 64 bitar. Författarna hävdar att chiffret är utformat så att ingen attack snabbare än uttömmande nyckelsökning bör vara möjlig, därför bör den bästa attacken kräva en beräkningskomplexitet som inte är signifikant lägre än 2 ⁸⁰ .

I den ursprungliga Grain version 0.0-specifikationerna hävdar författarna: "Grain ger en högre säkerhet än flera andra välkända chiffer som är avsedda att användas i hårdvaruapplikationer. Välkända exempel på sådana chiffer är E0 som används i Bluetooth och A5 / 1 som används i GSM . Dessa chiffer, även om de har en mycket liten hårdvaruimplementering, har visat sig vara mycket osäkra. Jämfört med E0 och A5/1 ger Grain högre säkerhet samtidigt som den bibehåller en liten hårdvarukomplexitet."

Författarna citerar attacken mot E0 som kräver en komplexitet på 2 ⁴⁰ och 2 ³⁵ ramar (en ram är 2745 bitar lång). Det ursprungliga Grain Version 0.0-chifferet bröts av en nyckelåterställningsattack som krävde en komplexitet på 2 ⁴³ beräkningar och 2 ³⁸ nyckelströmsbitar för att fastställa 80-bitarsnyckeln.

I de reviderade Grain Version 1.0-specifikationerna har chifferet en något reviderad utdatafunktion och NLFSR-feedbackfunktionen fick en mindre förändring. Specifikationerna hävdar: "Filterfunktionen är ganska liten, endast 5 variabler och olinjäritet 12. Detta kompenseras dock delvis av det faktum att en av ingångarna är hämtade från NLFSR. Ingångsbiten från NLFSR kommer att bero olinjärt [ sic ] på andra bitar i tillståndet, både från LFSR och från NLFSR. Den lilla filterfunktionen kompenseras också genom att addera 7 bitar linjärt [ sic ] från NLFSR vid lämpliga positioner för att bilda utdatafunktionen."

Från och med oktober 2006 är inga nyckelåterställningsattacker bättre än brute force attacker kända mot Grain version 1.0.

En relaterad attack publicerades dock i september 2006 av Ozgul Kucuk i tidningen "Slide Resynchronization Attack on the Initialization of Grain 1.0". Tidningen hävdar: "vi hittar relaterade nycklar och initiala värden för strömchifferet Grain 1.0. För alla (K,IV) par finns det relaterade (K',IV') par med sannolikhet 1/22 som genererar 1-bitars skiftad nyckelström . Även om detta inte resulterar i en effektiv återställningsattack ännu, indikerar det en svaghet i initieringen som skulle kunna övervinnas [ sic ] med lite ansträngning."

externa länkar

• eSTREAM-sida på Grain