Phelix

Phelix je vysokorychlostní streamová šifra , která používá jednorázový ověřovací kód zprávy . Šifra byla přihlášena do soutěže eSTREAM v roce 2004. Autory jsou Bruce Schneier , Doug Whiting , Stefan Lux a Frederick Müller . Algoritmus obsahuje operace sčítání modulo 2 32 , sčítání modulo 2 a cyklický posun; Phelix používá 256bitový klíč a 128bitové časové razítko . Někteří kryptografové vyjádřili obavy z možnosti získat tajný klíč při nesprávném použití šifry.

Předchůdcem Phelixu byla šifra Helix, postavená na nejjednodušších operacích, ale ukázalo se, že byla prolomena. Vylepšený Helix dostal jméno Phelix, ale byl také odmítnut v soutěži eCrypt. Důvod odmítnutí byl kontroverzní – útoky byly založeny na výběru časového razítka, což bylo slabé místo u jiných šifer, ale vývojáři uvedli, že jejich šifra je vůči tomuto druhu útoku odolná. Ukázalo se, že šifra je prolomena lineární diferenciální kryptoanalýzou, i když to za jiných podmínek neohrožuje sílu šifry. Výsledkem bylo, že Phelix nebyl pro určitou aroganci a nepřesnost autorů připuštěn do třetího kola soutěže. K tomu všemu se objevila řada teoretických prací, ve kterých se tvrdilo, že míchání operací add-xor-shift nedává potřebnou nelinearitu, ale v praxi k žádným hackům nedošlo. Design Phelix je nyní navržen autory pro použití v Skein a Threefish .

Recenze Phelixe

Složitost algoritmu je 128 bitů, což znamená, že pro prolomení šifry je nutné vypočítat alespoň blokové funkce, které tvoří výstupní sekvenci klíče. Phelix používá klíč libovolné délky (od 128 do 256 bitů), doplněný na 256 bitů a 128bitové časové razítko. Klíč je považován za tajný, výchozí časové razítko se považuje za známé všem. Šifra je optimalizována pro 32bitové platformy, protože všechny operace se provádějí na 32bitových slovech. Můžeme říci, že Phelix je „vícekolová jednoduchá šifra“, protože proces vytváření šifrového textu používá poměrně jednoduché sčítání modulo , XOR a permutaci bitů. $2^{128}$ $2^{32}$

Počáteční stav je 9 slov , každé 32 bitů. Slova jsou rozdělena do dvou skupin: 5 „aktivních“, která se účastní operací funkčního bloku, a stará („stará“), která se podílejí pouze na vytváření klíčového výstupního proudu a jsou uložena v vyrovnávací paměť blokové funkce. Šifrovací kolo je znázorněno na obrázku 1. Celkem blok obsahuje 20 kol (obrázek 2). $Z_{i}$

Díky velké podobnosti bloku s pěti spirálami dostala šifra svůj název (penta-helix anglicky five spirals). V každém bloku nastanou následující události: vygeneruje se jedno výstupní slovo toku (gama), přidají se dvě slova klíčového materiálu a jedno slovo prostého textu . Výstupní stav aktuálního bloku je použit jako vstup do dalšího bloku. $X_{i}$ $P_{i}$

V souladu s tím jsou výpočty zobrazené na obrázku 2 dostatečné pro zpracování 4 bajtů zprávy. Stejně jako u jiných proudových šifer je šifrový text v Phelix součtem modulo 2 prostého textu a klíčového proudu. Na začátku šifrování je počáteční stav určen klíčem a časovým razítkem. Klíčová slova závisí na hodnotě a délce klíče, časovém razítku a čísle bloku. Útoky založené na hádání vnitřního stavu jsou ztíženy přidáním klíčového materiálu ve fázi extrakce klíčového proudu. Na konci zprávy je provedeno další zpracování, během kterého je vygenerován 128bitový tag, který je zodpovědný za autentizaci zprávy. $X_{{ij}}$

Definice

Funkce šifrování používá jako vstup klíč U proměnné délky (až 256 bitů), 128bitové časové razítko a prostý text. Funkce dešifrování je klíč, časové razítko a značka a v případě selhání autentizace vytváří buď prostý text, nebo chybu. Dovolit být délka posloupnosti bajtů . Pak <32. Pracovní klíč K, sestávající z osmi 32bitových slov, je generován funkcí keymixing. Časové razítko má velikost 16 bajtů. Pokud je jeho délka menší, musí být štítek doplněn nulami na požadovanou délku. Šifrovaný text a otevřený text mají stejnou délku s limitem . Poslední slovo otevřeného textu je ve výchozím nastavení doplněno nulami na délku 32 bitů, pokud délka slova není násobkem 32 bitů. Funkce šifrování může vzít prázdnou zprávu jako vstup, v takovém případě bude jejím výstupem pouze autentizační kód zprávy (MAC). $L(x)$ $X$ $L(U)$ $2^{64}$

Blokovat funkci

Phelix se skládá z posloupnosti bloků, z nichž každý má přiděleno své vlastní jedinečné číslo, podle pořadí. Na vstupu každého bloku je pět „aktivních“ slov. Výstup bloku také obsahuje pět slov , , , , , která budou představovat vstup dalšího bloku , , , , . th blok také používá jako vstup dvě klíčová slova a , jedno slovo prostého textu a předchozí slovo vnitřního stavu . ${\displaystyle Z_{0}^{i))$ ${\displaystyle Z_{1}^{i))$ ${\displaystyle Z_{2}^{i))$ ${\displaystyle Z_{3}^{i))$ ${\displaystyle Z_{4}^{i))$ $Z_{0}^{i+1}$ $Z_{1}^{i+1}$ $Z_{2}^{i+1}$ $Z_{3}^{i+1}$ $Z_{4}^{i+1}$ $i$ $X_{i,0}$ $X_{i,1}$ $P_{i}$ $Z_{4}^{i-4}$

Obrázek 2 je kompletní ilustrace funkce bloku. Všechny hodnoty jsou 32bitová slova; Podle tradice má exkluzivní OR zápis , permutace - <<< , modulo sčítání - . Bloková funkce může být reprezentována jako sekvence dvou "polobloků" H definovaných následovně. $\oplus$ $+$

Pro slova zapojená do blokových operací tedy platí následující rovnice. Každý blok vytváří jedno klíčové slovo . Šifrovaný text je jako obvykle definován následovně: . $(Y_{0}^{i},Y_{1}^{i},Y_{2}^{i},Y_{3}^{i},Y_{4}^{i}): =H(Z_{0}^{i},Z_{1}^{i},Z_{2}^{i},Z_{3}^{i},Z_{4}^{i},0, X_{i,0});(Z_{0}^{i+1},Z_{1}^{i+1},Z_{2}^{i+1},Z_{3}^{i+ 1 },Z_{4}^{i+1}):=H(Y_{0}^{i},Y_{1}^{i},Y_{2}^{i},Y_{3}^ { i},Y_{4}^{i},P_{i},X_{i,1})$ ${\displaystyle S_{i}=Y_{4}^{i}+Z_{4}^{i-4))$ $C_{i}=P_{i}+S_{i}$

Klíčová slova pro každý blok

Rozšířená klíčová slova jsou definována pracovním klíčem K, časovým razítkem N, délkou vstupního klíče U a číslem bloku. Nejprve se časové razítko rozšíří na osm slov podle pravidla: . Dále se klíčová slova pro blok i vypočítají následovně: $N_{k}:=(kmod4)-N_{k-4}(mod2^{32})$

kde se všechny operace provádějí modulo $2^{32}$

Inicializace

Šifrování začíná nastavením vnitřního stavu:

Poté se provede 8 bloků, v důsledku čehož se vytvoří slova výstupního toku klíče (gama), která jsou nakonec vyřazena a neúčastní se šifrování a teprve poté začíná pracovní cyklus.

Šifrování

Po inicializaci začíná proces šifrování otevřeného textu. Nechť K je počet bajtových slov otevřeného textu, pak počet bloků bude také roven K. Každý blok vytváří jedno slovo výstupního klíčového proudu, které se používá k zašifrování jednoho slova otevřeného textu.

V závislosti na , poslední slovo výstupního toku klíčů používá 1 až 4 bajty. $L(P)mod4$

Autentizační kód

Po zašifrování posledního bajtu prostého textu je čas vygenerovat MAC. Operace XOR se provede pro a 0x912d94f1. Dále je aktualizovaný vnitřní stav zpracován postupně po osmi blocích. Zde se používají slova prostého textu a vygenerovaný výstupní klíčový proud se nijak nepoužívá. Po následném zpracování vnitřního stavu se pomocí stejného . ${\displaystyle Z_{0}^{k))$ $L(P)mod4$ $L(P)mod4$

Funkce generování klíčů s pevnou délkou (keymixing)

Funkce generování klíče pevné délky mapuje klíč libovolné délky na klíč dlouhý 256 bitů. Nejprve se vezme funkce R definovaná takto:

Poté je klíč U doplněn nulami na délku 256 bitů a 32bitovým slovům klíče jsou přiřazeny hodnoty . Pracovní klíč se zadává následovně pro k=7,…,0: $K_{32},...,K_{39}$ $(K_{4i},...,K_{4i+3}):=R(K_{4i+4},...,K_{4i+7})\oplus (K_{4i+8 },...,K_{4i+11})$

Přepis

Dešifrování je téměř identické s šifrováním, pouze se liší:

$S_{i}$ , vygenerovaný při první aplikaci funkce H, se používá k dešifrování šifrovaného textu, čímž vznikne slovo prostého textu, použité později ve druhé aplikaci funkce H.
Po přijetí značky je tato porovnána s očekávanou, a pokud nejsou stejné, je zpráva zničena.

Výkon

Phelix je optimalizován pro 32bitové platformy. Autoři tvrdí, že na moderních 86bitových procesorech může dosáhnout až osmi cyklů na bajt .

Následují metriky výkonu pro hardware FPGA:

Čip Xilinx	Fragmenty	FPGA Mbps	GE skóre	Popis implementace
XC2S100-5	1198	960,0	20404	(A) Plně kulatý 160bitový model
XC2S100-5	1077	750,0	18080	(B) Půlkulatý 160bitový model
XC2S30-5	264	3.2	12314	(C) 32bitové datové spojení

šroubovice

Phelix je mírně upravená forma rané šifry Helix, kterou v roce 2003 publikovali Niels Ferguson , Doug Whiting , Bruce Schneier , John Kelsey , Stefan Lax a Tadayoshi Kono ; Phelix přidá 128 bitů pro vnitřní stav.

V roce 2004 Muller zveřejnil dva útoky na Helix. První má složitost 2 88 a vyžaduje 2 12 adaptivně vybraných slov v otevřeném textu , ale pro opětovné použití vyžaduje náhodná čísla. Souradiuty Paul a Bart Presnel později ukázali, že počet adaptivně přizpůsobených Müllerových útočných slov s otevřeným textem lze v nejhorším případě snížit o faktor 3 pomocí jejich optimálních algoritmů pro řešení adičních diferenciálních rovnic. V následném vývoji Souradiuti Paul a Bart Prenel ukázali, že výše uvedený útok by mohl být implementován s vybranými holými texty (CP) spíše než adaptivně přizpůsobenými holými texty (ACP) s datovou složitostí 2 35,64 CP. Mullerův druhý útok na Helix je výrazný útok, který vyžaduje 2 114 slov zvoleného prostého textu.

Vývoj Phelix je z velké části motivován Mullerovým diferenciálním útokem.

Zabezpečení

Autoři radí, že Phelix by neměl být používán, dokud neprojde další kryptoanalýzou.

Hongjun Wu a Bart Prenel, autoři diferenciálního útoku, vyjadřují obavy, že každé slovo otevřeného textu ovlivňuje klíčový proud a obchází dostatečné vrstvy zmatku a šíření. Tvrdí, že se jedná o neodmyslitelnou chybu ve struktuře Helix a Phelix. Autoři dospěli k závěru, že Phelix není bezpečný.

Implementace hardwaru

Phelix lze implementovat mnoha různými způsoby. Obrázek níže ukazuje jednu možnou implementaci na ASIC (Application Specific Integrated Circuit ).

n_expand: Převede časové razítko libovolné délky na časové razítko o délce 192 bitů.
key_mix: Převede klíč proměnné délky na 256bitový klíč.
sub_key_gen: Generuje klíčová slova pro každý blok. $X_{i,0},X_{i,1}$
ini_dp: Inicializace.
H_func: Implementace logiky H-funkce.
FIFO: První dovnitř, první ven FIFO paměť .

Chcete-li zvýšit rychlost algoritmu, můžete změnit funkci H přidáním nových sčítaček a XOR, které by mohly fungovat paralelně, ale toto zvýšení počtu prvků v obvodu by také znamenalo znatelný nárůst v obvodu samotném, protože sčítačka je největší prvek obvodu.

Poznámky

Literatura

D. Whiting, B. Schneier, S. Lucks a F. Muller, Phelix: Rychlé šifrování a autentizace v jediném kryptografickém primitivu (zahrnuje zdrojový kód)
T. Good, W. Chelton, M. Benaissa: Přehled kandidátů na proudové šifry z pohledu hardwaru s nízkými zdroji (PDF)
Yaser Esmaeili Salehani, Hadi Ahmadi: Vybraný klíčový rozlišující útok na Phelix, předloženo eSTREAM [staženo 2006-10-14]
Niels Ferguson, Doug Whiting, Bruce Schneier, John Kelsey, Stefan Lucks a Tadayoshi Kohno, Helix: Rychlé šifrování a ověřování v jediném kryptografickém primitivním, rychlém softwarovém šifrování - FSE 2003, str. 330-346 (PDF) .
Frédéric Muller, Differential Attacks against the Helix Stream Cipher, FSE 2004, str. 94-108.
Souradyuti Paul a Bart Preneel , Řešení systémů diferenciálních rovnic sčítání, ACISP 2005. Plná verze ( PDF )
Souradyuti Paul a Bart Preneel , Téměř optimální algoritmy pro řešení diferenciálních rovnic sčítání s dávkovými dotazy, Indocrypt 2005. Plná verze ( PDF )

Odkazy

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher