F-FCSR

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2013. március 13-án áttekintett verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

Az F-FCSR egy adatfolyam -rejtjel-család, amely egy átviteli visszacsatolási eltolási regiszter (FCSR) használatán alapul , lineáris szűrővel a kimeneten. A rejtjelezés ötletét Terry Berger, François Arnault és Cédric Larade javasolta. Az F-FCSR-t beküldték az eSTREAM versenyre , 2008 áprilisában felkerült a verseny nyerteseinek listájára, de később kiderült egy kriptográfiai gyengeség, és 2008 szeptemberében az F-FCSR kikerült az eSTREAM listáról.

Történelem

Clapper és Goreski először 1994-ben vetette fel az ötletet, hogy egy átviteli visszacsatolási eltolási regisztert (FCSR) használjunk streaming szűrő létrehozásához [1] . Később kidolgoztak egy algoritmust egy ilyen titkosításhoz [1] . Egy FCSR vonalkomponens csatlakoztatása nélkül nem használható adatfolyam titkosításként, mivel könnyen visszafejthető.

2002-ben javasoltak egy önszinkronizáló adatfolyam-rejtjelet, amely az FCSR és az LFSR kombinált használatán alapul [2] . Később titkosított szövegválasztási támadásnak vetették alá [3] .

2005-ben Arnaud és Berger felvetette az FCSR és a lineáris szűrő együttes alkalmazásának ötletét egy adatfolyam titkosítás létrehozására, amelyet F-FCSR-nek (Filtered FCSR) hívtak [4] . Később 4 algoritmust javasoltak, amelyek megvalósítják ezt az ötletet: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 és F-FCSR-DF8 [5] . Az első kettő statikus, az utolsó kettő kulcsspecifikus szűrőket használt. Később kiderült, hogy ezeknek az algoritmusoknak a gyengesége a különféle típusú támadásokkal szemben [6] .

2005-ben Terry Berger, François Arnol és Cédric Laradoud két F-FCSR [7] alapú titkosítót nyújtott be az eSTREAM versenyre: F-FCSR-H hardverre és F-FCSR-8 szoftverre. A későbbi tesztelések eredményeként az F-FCSR-H és az F-FCSR-8 [8] kezdeti verzióiban sebezhetőséget találtak , amelyeket később az F-FCSR-H v.2 és F-FCSR-16 verziókban javítottak. [9] . Az F-FCSR-H v.2 továbbfejlesztett változata az eSTREAM döntőse lett [10] . A sérülékenység felfedezése után [11] azonban kizárták az eSTREAM portfólióból (rev.1) [12] .

A verzió jellemzői

Név	Főregiszter hossza	Inicializálás	Szűrő	Bitek száma a szűrő kimenetén
F-FCSR-8	128	64/128 ciklus (IV-től függően)	Kulcstól függ	nyolc
F-FCSR-H	160	160 bar	Statikus	nyolc
F-FCSR-8.2	256	258 bar	Kulcstól függ	16
F-FCSR-16	256	16 + 258 bar	Statikus	16
F-FCSR-H v.2	160	20 + 162 bar	Statikus	nyolc

Az algoritmus leírása

FCSR

Az FCSR két konfigurációban valósul meg: Galois és Fibbonacci. Az F-FCSR a Galois konfigurációt használja, mert az hatékonyabb. A következő jelölés kerül bevezetésre:

q - kapcsolat integritása - negatív páratlan egész szám, amely megfelel a következő feltételeknek:
- ${\displaystyle 2^{|q|-1}=1\mod {q))$
- T = (|q| − 1)/2 prím, 2T a p/q bitsorozat periódusa
- Az egyesek száma az n/2 rendű (1 − q)/2 szám bináris ábrázolásában
p egy kulcsfüggő paraméter, így 0 < p < |q|
n az FCSR főregiszter mérete, |q| bináris jelölésben n + 1 karakter van: 2 n < -q < 2 n+1
d : d = (1 − q)/2, bináris jelöléssel, d i = {0, 1}, d n-1 = 1 ${\displaystyle \sum _{i=0}^{n-1}d_{i}\cdot 2^{i))$
M egy n bites főregiszter, i-edik bitjének értékei,. ${\displaystyle m(t)=\sum _{i=0}^{n-1}m_{i}(t)\cdot 2^{i))$
C egy l-bites eltolási regiszter, l + 1 az egyesek száma d, bináris jelölésben. ${\displaystyle c(t)=\sum _{i=0}^{l-1}c_{i}(t)\cdot 2^{i))$
(m, c) - FCSR állapot

Ha (m, c) az FCSR állapota t 0 , , időpontban , akkor a p/q bináris reprezentációja, ahol p = m + 2c. $m=m(t_{0})$ $c=c(t_{0})$ ${\megjelenítési stílus (m_{0}(t_{0}+i))_{i\in {N))}$

FCSR példa

q = -347, d = 174 = (10101110) 2 , n = 8, l = 4.

Szűrés

A kimeneti szűrési funkciót a maszk ( ) határozza meg egy kimeneti bit a következőképpen: ${\displaystyle {f}_{0,}{f}_{1,...,}{f}_{n-1))$ ${\displaystyle {k}=\bigoplus _{i=0}^{n-1}{f}_{i}\cdot {m}_{i))$

Inicializálás

Tekintettel a korábbi F-FCSR-verziók gyengeségére, amely a fő regiszter gyenge kezdeti bitkeverése miatt következett be, az F-FCSR-H v.2 és F-FCSR-16 inicializálási eljárása a következő:

Az M főregiszter inicializálása a titkos kulcs K és IV - (K, IV) összefűzésével történik, a hordozóregiszterbe nullákat írunk.
Átmegy a generátor 16 ciklusán az F-FCSR-16 és 20 az F-FCSR-H v.2 esetében
Az így kapott 256, illetve 160 bitet M-be írjuk
A generátor n + 2 ciklusát vesz igénybe, miközben a kimeneti biteket eldobják

F-FCSR alapú titkosítások

F-FCSR-H v.2

Kulcshossz 80 bit, IV - 80 bit
q = −1993524591318275015328041611344215036460140087963
A hordozóregiszter hossza l = 82
d = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E) 16
A kimenet bitsorozata , azaz ${S(t)}={(s}_{0}{(t),}{s}_{1}{(t),...}{s}_{7}{(t )),}s_{j}(t)=\bigoplus _{i=0}^{19}d_{8i+j}\cdot m_{8i+j}(t)$

z \u003d (m 8 + m 24 + m 40 + m 56 + ... + m 136 , m 1 + m 49 + ..., ..., m 23 + ...) F-FCSR-16

Kulcshossz 128 bit, IV - 128 bit
q = −183971440845619471129869161809344131658298317655923135753017128462155618715019
A hordozóregiszter hossza l = 130
d = (CB5E129F AD4F7E66 780CAA2E C8C9CEDB 2102F996 BAF08F39 EFB55A6E 390002C6) 16
Kimeneti bitsor ${S(t)}={(s}_{0}{(t),}{s}_{1}{(t),...}{s}_{15}{(t )),}s_{j}(t)=\bigoplus _{i=0}^{15}d_{16i+j}\cdot m_{16i+j}(t)$

A támadás leírása

Az F-FCSR-8 és F-FCSR-H kezdetben talált sebezhetőségeit, amelyek az inicializálás során néhány ciklushoz kapcsolódnak, az F-FCSR-16 és F-FCSR-H v.2 verziókban javították. 2008-ban Martin Hell és Thomas Joansson leírt és végrehajtott egy támadást az F-FCSR ellen, amely felfedheti az FCSR állapotát.

A szűrési függvény lineáris, ezért az F-FCSR kriptográfiai erősségét az FCSR nemlinearitása határozza meg, ami a hordozóregiszter jelenléte miatt következik be, ezért a rendszert linearizálni kell a hordozóban lévő nullák számának maximalizálásával. Regisztráció. Vegyünk egy olyan helyzetet, amikor a hordozóregiszter állapota 20 cikluson keresztül a következő lesz:

C(t) = C(t + 1) = … = C(t + 19) = (С l-1 , …, С 0 ) = (0, 0, . . . , 0, 1) (*)

Ha a visszacsatoló bit 0, akkor a hordozóregiszter 0 bitjei 0 maradnak, az 1-esek pedig 0-vá válnak 1/2 valószínűséggel. Ekkor a (*) előfordulásához körülbelül egymást követő nullák kellenek a visszacsatoló bitben . $\log _{2}{82}+19\kb. 26$

A (*) feltevés szerint az M(t + 1), …, M(t + 19) főregiszter állapotai lineárisan függenek M(t) -től , és ismerjük ezt a függést.

Jelöljük a z(t), z(t + 1), … , z(t + 19) kimeneti bájtokat .

Fejezzük ki z(t), z(t + 1), … , z(t + 19)-t a főregiszter bitértékeivel a t időpontban: M(t) = (m 0 … m 159 ) .
20 egyenletet kapunk 20 ismeretlennel , ahol : … Hasonlóképpen egyenletrendszereket kapunk attól függően , hogy hol stb. Összesen 8 20 egyenletből álló rendszer 20 ismeretlennel. A következő jelölést használjuk: , , … . Jelöljük a vektort Ekkor a rendszereket felírhatjuk alakba , ahol a szűrési függvény által meghatározott ismert mátrix. A főregiszter állapotának megállapítására szolgáló algoritmus a (*) feltevés mellett a következőképpen írható le: $m_i$ $i\equiv 0\mod 8$

$z_{0}(t)=m_{8}\bigoplus {m_{24}}\bigoplus {...}\bigoplus {m_{136}}$

$z_{7}(t+1)=m_{24}\bigoplus {m_{40}}\bigoplus {...}\bigoplus {m_{152}}$

$z_{5}(t+19)=m_{32}\bigoplus {m_{48}}\bigoplus {...}\bigoplus {m_{152}}$

$m_i$ $i\equiv 1\mod 8$

$W_{0}=(z_{0}(t),z_{7}(t+1),...,z_{5}(t+19))$
$W_{1}=(z_{1}(t),z_{0}(t+1),...,z_{6}(t+19))$

$W_{7}=(z_{7}(t),z_{6}(t+1),...,z_{4}(t+19))$
${\hat {M}}_{j}$ $(m_{j},m_{j+8},...,m_{j+152})$
$W_{j}={\kalap {M}}_{j}P_{j}$ $P_{j}$

A t időpontban bájtokat kapunk a kimeneten: z(t), z(t +1), . . . , z(t + 19)
ha i = 0-7Oldja meg az egyenletet $W_{j}={\kalap {M}}_{j}P_{j}$ ha (nincs megoldás ) 1 egyébként mentse a lehetséges értékeket ${\hat {M}}_{j}$
( minden lehetséges készlethez ) ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$ if (M of can output z(t), z(t +1), . . . , z(t + 19) ) return ; ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$
megy 1

A fenti támadás 226 bájt titkosított szöveget igényel . Lehetőség van a támadás javítására, ehhez 2 24,3 bájt szükséges. Hasonló támadást lehetne alkalmazni az F-FCSR-16-nál is.

Jegyzetek

↑ 1 2 A. Klapper, M. Goresky, 2-adic shift regiszterek, in Fast Software Encryption'93, szerk. írta RJ Anderson. Lecture Notes in Computer Science, vol. 809 (Springer, Berlin, 1994), pp. 174-178
↑ F. Arnault, T. Berger, A. Necer, Az LFSR és FCSR architektúrákat kombináló adatfolyam-rejtjelek új osztálya, folyamatban van a kriptológiában – INDOCRYPT 2002, szerk. A. Menezes, P. Sarkar. Lecture Notes in Computer Science, vol. 2551/2002 (Springer, Berlin, 2002), pp. 22-33
↑ B. Zhang, H. Wu, D. Feng, F. Bao, Választott titkosított szöveges támadás az önszinkronizáló adatfolyam-rejtjelek új osztálya ellen, In Progress in Cryptology – INDOCRYPT 2004, szerk. A. Canteaut, K. Viswanathan. Lecture Notes in Computer Science, vol. 3348/2004 (Springer, Berlin, 2004), pp. 73-83
↑ F. Arnault, T. Berger, Szűrt FCSR automatán alapuló új pszeudovéletlen generátor tervezése és tulajdonságai. IEEE Trans. Comput. 54, 1374-1383 (2005)
↑ F. Arnault, T. Berger, F-FCSR: Az adatfolyam-rejtjelek új osztályának tervezése, Fast Software Encryption 2005, szerk. szerző: H. Gilbert, H. Handschuh. Lecture Notes in Computer Science, vol. 3557 (Springer és Berlin, 2005), pp. 83-97
↑ E. Jaulmes, F. Muller, Cryptanalysis of the F-FCSR stream cipher család, Selected Areas in Cryptography – SAC 2005, szerk. B. Preneel, S. Tavares. Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2005), pp. 36-50
↑ Archivált másolat . Letöltve: 2011. november 23. Az eredetiből archiválva : 2011. május 27.. (határozatlan)
↑ Archivált másolat . Letöltve: 2011. november 23. Az eredetiből archiválva : 2011. május 27.. (határozatlan)
↑ Archivált másolat . Letöltve: 2011. november 23. Az eredetiből archiválva : 2011. május 27.. (határozatlan)
↑ Az eSTREAM projekt . Letöltve: 2011. november 23. Az eredetiből archiválva : 2011. december 5.. (határozatlan)
↑ M. Hell, T. Johansson, Breaking the F-FCSR-H stream cipher in real time, Advances in Cryptology – ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350/2008 (Springer, Berlin, 2008), pp. 557-569
↑ Archivált másolat . Letöltve: 2011. november 23. Az eredetiből archiválva : 2012. augusztus 13.. (határozatlan)

Irodalom

M. Hell, T. Johansson, Breaking the F-FCSR-H adatfolyam titkosítás valós időben, Advances in Cryptology. ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350/2008 (Springer, Berlin, 2008), 557-569.
F. Arnault és T. P. Berger. F-FCSR: az adatfolyam-rejtjelek új osztályának tervezése. In Fast Software Encryption – FSE 2005, v. Számítástechnikai előadásjegyzetek, 3557. o. 83-97. Springer-Verlag, 2005.
F. Arnault, T. Berger, C. Lauradoux, Frissítés az F-FCSR adatfolyam titkosításáról. eSTREAM, ECRYPT Stream Cipher Project, 2006/025 jelentés (2006).

Linkek

http://www.ecrypt.eu.org/stream/index.html

Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam	A3 A5 A8 Decim F-FCSR Gabona HC-256 KCipher-2 MICKEY MUGI CSUKA Phelix RC4 Nyúl FÓKA HÓ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel hálózat	GOST 28147-89 (Magma) blowfish Kamélia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra ÜZLET DES DESX DFC E2 EnRUPT FEAL HPC ÖTLET KASUMI Khafre Khufu LOKI97 MacGuffin MARS HÁLÓ MISTY1 NewDES NDS RC5 RC6 MAG Simon Sinopoli skipjack SM4 Folt TEA XTEA XXTEA Raiden RTEA Tripla DES Kéthal
SP hálózat	Szöcske 3 út ABC ÁRIA AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Öv CRYPTON Gyémánt2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer jelenlegi Szivárvány BIZTONSÁGOSBAN CÁPA NÉGYZET Kígyó háromhal
Egyéb	BÉKA NUSH REDOC SC2000 SHACAL CS-Cipher