Cube attack

Krychle útok je metoda dešifrování použitelná pro širokou škálu symmetric-klíčové algoritmy , vydané Itai Dinur a Adi Shamir v preprintu září 2008. Revidovaná verze této preprintu byl umístěn on-line v lednu 2009, ^[ 1 ] , a papír byl také přijat k prezentaci na Eurocrypt 2009.

Šifra je zranitelný, pokud se výstupní bit může být reprezentován jakodostatečně nízké studia polynomu nad GF (2) klíčové a vstup bitů; zejména to popisuje mnoho proudových šifer založených na LFSRs . ^[ 2 ] DES a AES jsou věřil být imunní na tento útok. ^[ 2 ] Působí jako součet výstupní bitovou hodnotu pro všechny možné hodnoty podmnožiny veřejných vstupních bitů, volí tak, aby výsledný součet je lineární kombinace tajných bitů, opakované použití této techniky uvádí soubor lineárních vztahů mezi tajných bitů, které mohou být řešeny objevovat tyto bity. Autoři ukazují, že v případě, že se podobá šifra náhodný polynom dostatečně nízké úrovni pak takové sady veřejných vstupních bitů bude existovat s vysokou pravděpodobností, a mohou být objeveny vpředpočítání fázi podle "černé skříňky sondování" vztahu mezi vstupem a výstupem pro různé možnosti veřejných a tajné vstupních bitů nevytvářejících použití jakékoli další informace o stavbě šifry.

Příspěvek prezentuje praktický útok, který autoři zavedli a testovány, na proudová šifra, na kterém žádná předchozí známý útok by byly účinné. Jeho stav je 10.000 trochu LFSR s tajným hustou zpětné vazby polynom, který je filtrován polem 1000 tajně 8-bit na 1-bit S-boxů, jehož metoda je založena na tajných kohoutky do LFSR státu a jejichž produkce je XORed společně. Každý bit v LFSR je inicializován jiným tajným husté kvadratické polynomu v 10, 000 klíče a IV bitů. LFSR je taktován velké a tajné kolikrát bez vytváření jakýchkoli výstupů, a pak jen první výstup bit pro daný IV je k dispozici na útočníka. Po krátkém předzpracování fázi, ve které může útočník dotaz výstupní bity pro různé klíče a IV kombinace, pouze 2 ³⁰ jsou bitové operace musí objevit klíč k tomuto kódu.

Autoři také tvrdí, útok na verzi Trivium snížena na 735 inicializační kol se složitostí 2 ³⁰ , a domnívají se, že tyto techniky mohou rozšířit na lámání 1100 o 1152 Trivium tyto inicializační kol a "možná i na původní kód". V prosinci 2008 je to nejlepší útok známý proti Trivium.

Útok je však zapletl do dvou samostatných diskusí. Za prvé, Daniel J. Bernstein^[ 3 ] zpochybňuje tvrzení, že žádná předchozí útok na 10000-bit LFSR založené proudová šifra existoval, a tvrdí, že útok na sníženou kole Trivium "nevěnuje žádnou skutečný důvod, proč se domnívat, že ( full) Trivium může být napadena ". Tvrdí, že Cube papír neuvedla stávající dokument o Xuejia Lai podrobně útok na šifry s malou stupně polynomů, a že věří, že Cube útok jen přerod tohoto stávajícího techniky.

Zadruhé, Dinur a Shamir úvěrové Michaela Vielhaber tyto " Algebraická IV Diferenciální útoku "(AIDA) jako předchůdce Cube útoku. ^[ 4 ] Dinur konstatoval v Eurocrypt 2009, že Cube generalizuje a vylepšuje AIDA. Nicméně, Vielhaber tvrdí, že kostka útok není nic víc než jeho útok pod jiným jménem. ^[ 5 ] To je, nicméně, uznáván všemi zúčastněnými stranami, že Cube je použití účinného linearity testu jako jsou výsledky testů BLR v novém útoku potřebují méně času než AIDA, i když, jak je podstatná tento konkrétní změna zůstane v sporu. Je to jediný způsob, jak Cube a AIDA liší. Vielhaber tvrdí, například, že lineární polynomy v klíčových bitů, které se získají při útoku bude neobvykle řídká. On ještě dodává důkazy, ale tvrdí, že takový důkaz se objeví v nadcházejícím dokumentu sám s názvem "algebraické IV Differential útok: AIDA Útok na plný Trivium". (To není jasné, zda tato údajná řídkost se vztahuje na všechny šifry než Trivium.)