F-FCSR

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 mars 2013; kontroller kräver 8 redigeringar .

F-FCSR är en familj av strömchiffer baserad på användningen av ett överföringsåterkopplingsskiftregister (FCSR) med ett linjärt filter vid utgången. Idén till chiffret föreslogs av Terry Berger, François Arnault och Cédric Larade. F-FCSR skickades till eSTREAM- tävlingen , ingick i listan över vinnare av tävlingen i april 2008, men senare avslöjades en kryptografisk svaghet och i september 2008 exkluderades F-FCSR från eSTREAM-listan.

Historik

Idén att använda ett överföringsregister (FCSR) för att skapa ett strömningsfilter föreslogs först av Clapper och Goreski 1994 [1] . Senare utvecklade de en algoritm för ett sådant chiffer [1] . En FCSR utan att ansluta en linjekomponent kan inte användas som ett strömchiffer, eftersom det är lätt att dekryptera.

År 2002 föreslogs ett självsynkroniserande strömchiffer baserat på den kombinerade användningen av FCSR och LFSR [2] . Den utsattes senare för en chiffertextvalsattack [3] .

2005 föreslog Arnaud och Berger idén att använda FCSR och ett linjärt filter tillsammans för att skapa ett strömchiffer, som kallades F-FCSR (Filtered FCSR) [4] . Senare föreslog de fyra algoritmer som implementerar denna idé: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 och F-FCSR-DF8 [5] . De två första använde statiska filter, de två sista använde nyckelspecifika filter. Senare avslöjades svagheten hos alla dessa algoritmer mot olika typer av attacker [6] .

2005 skickade Terry Berger, François Arnol och Cédric Laradoud in två F-FCSR [7] -baserade chiffer till eSTREAM-tävlingen: F-FCSR-H för hårdvara och F-FCSR-8 för mjukvara. Som ett resultat av efterföljande tester hittades sårbarheter i de första versionerna av F-FCSR-H och F-FCSR-8 [8] , som senare fixades i versionerna F-FCSR-H v.2 och F-FCSR-16 [9] . En förbättrad version av F-FCSR-H v.2 blev finalist för eSTREAM [10] . Men efter upptäckten av sårbarheten [11] exkluderades den från eSTREAM Portfolio (rev.1) [12] .

Versionsegenskaper

namn	Huvudregistrets längd	Initialisering	Filtrera	Antal bitar vid filterutgången
F-FCSR-8	128	64/128 cykler (beroende på IV)	Beror på nyckeln	åtta
F-FCSR-H	160	160 barer	Statisk	åtta
F-FCSR-8.2	256	258 barer	Beror på nyckeln	16
F-FCSR-16	256	16 + 258 takter	Statisk	16
F-FCSR-H v.2	160	20 + 162 takter	Statisk	åtta

Beskrivning av algoritmen

FCSR

FCSR implementeras i två konfigurationer: Galois och Fibbonacci. F-FCSR använder Galois-konfigurationen eftersom den är mer effektiv. Följande notation introduceras:

q - anslutningsintegritet - ett negativt udda heltal som uppfyller följande villkor:
- ${\displaystyle 2^{|q|-1}=1\mod {q))$
- T = (|q| − 1)/2 är primtal, 2T är perioden för bitsekvensen p/q
- Antalet ettor i den binära representationen av talet (1 − q)/2 av ordningen n/2
p är en nyckelberoende parameter så att 0 < p < |q|
n är storleken på huvudregistret FCSR, |q| i binär notation har n + 1 tecken: 2 n < −q < 2 n+1
d : d = (1 − q)/2, i binär notation, d i = {0, 1}, d n-1 = 1 ${\displaystyle \sum _{i=0}^{n-1}d_{i}\cdot 2^{i))$
M är ett n-bitars huvudregister, värdena för dess i:te bit,. ${\displaystyle m(t)=\sum _{i=0}^{n-1}m_{i}(t)\cdot 2^{i))$
C är ett l-bitars skiftregister, l + 1 är antalet ettor i binär notation d,. $c(t)=\sum _{i=0}^{l-1}c_{i}(t)\cdot 2^{i}$
(m, c) - FCSR-tillstånd

Om (m, c) är FCSR-tillståndet vid tidpunkten t 0 , , , då är den binära representationen av p/q, där p = m + 2c. $m=m(t_{0})$ $c=c(t_{0})$ $(m_{0}(t_{0}+i))_{i\in {N))$

FCSR-exempel

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

Filtrering

Utgångsfiltreringsfunktionen definieras av masken ( ) En utgångsbit definieras enligt följande: ${\displaystyle {f}_{0,}{f}_{1,...,}{f}_{n-1))$ ${\displaystyle {k}=\bigoplus _{i=0}^{n-1}{f}_{i}\cdot {m}_{i))$

Initiering

Med tanke på svagheten hos tidigare F-FCSR-versioner på grund av svag initial bitblandning i huvudregistret, är initieringsproceduren i F-FCSR-H v.2 och F-FCSR-16 följande:

Huvudregistret M initieras genom att sammanfoga den hemliga nyckeln K och IV - (K, IV), nollor skrivs till bärregistret.
Klarar 16 cykler av generatorn för F-FCSR-16 och 20 för F-FCSR-H v.2
De resulterande 256 respektive 160 bitarna skrivs till M
Det tar n + 2 cykler av generatorn, medan utgångsbitarna kasseras

F-FCSR-baserade chiffer

F-FCSR-H v.2

Nyckellängd 80 bitar, IV - 80 bitar
q = −1993524591318275015328041611344215036460140087963
Bärregisterlängd l = 82
d = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E) 16
Sekvensen av bitar i utgången , det vill säga ${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

Nyckellängd 128 bitar, IV - 128 bitar
q = −183971440845619471129869161809344131658298317655923135753017128462155618715019
Bärregisterlängd l = 130
d = (CB5E129F AD4F7E66 780CAA2E C8C9CEDB 2102F996 BAF08F39 EFB55A6E 390002C6) 16
Utdatabitsekvens ${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)$

Beskrivning av attacken

Initialt hittade sårbarheter i F-FCSR-8 och F-FCSR-H associerade med ett litet antal cykler under initiering fixades i F-FCSR-16 och F-FCSR-H v.2. 2008 beskrev och genomförde Martin Hell och Thomas Joansson en attack mot F-FCSR som kunde avslöja FCSR:s tillstånd.

Filtreringsfunktionen är linjär, så F-FCSRs kryptografiska styrka bestäms av icke-linjäriteten hos FCSR, vilket uppstår på grund av närvaron av bärregistret, så systemet måste linjäriseras genom att maximera antalet nollor i bäraren Registrera. Tänk på en situation där tillståndet för transportregistret för 20 cykler kommer att vara följande:

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

Om återkopplingsbiten är 0, förblir bitar i bärregistret som är 0 0, och de som är 1 blir 0 med sannolikhet 1/2. För att (*) ska inträffa, skulle ungefär på varandra följande nollor i återkopplingsbiten krävas . $\log _{2}{82}+19\approx 26$

Genom antagande (*) beror tillstånden i huvudregistret M(t + 1), …, M(t + 19) linjärt på M(t) , och vi känner till detta beroende.

Låt oss beteckna utdatabytes z(t), z(t + 1), … , z(t + 19) .

Låt oss uttrycka z(t), z(t + 1), … , z(t + 19) i termer av bitvärdena i huvudregistret vid tidpunkten t: M(t) = (m 0 … m 159 ) .
Vi får 20 ekvationer med 20 okända , där : … På samma sätt får vi ekvationssystem beroende på , var etc. Totalt 8 system med 20 ekvationer med 20 okända. Vi använder följande notation: , , … . Låt oss beteckna vektorn Då kan systemen skrivas i formen , där är en känd matris som bestäms av filtreringsfunktionen. Algoritmen för att hitta huvudregistrets tillstånd under antagandet (*) kan beskrivas enligt följande: $mi$ $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}}$

$mi$ $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}={\hat {M}}_{j}P_{j}$ $P_{j}$

Vid tidpunkten t får vi byte vid utgången: z(t), z(t +1), . . . , z(t + 19)
för i = 0 till 7 Lös ekvationen $W_{j}={\hat {M}}_{j}P_{j}$ om (inga lösningar) fick 1 annars sparar du möjliga värden ${\hat {M}}_{j}$
för (alla möjliga set ) ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$ if (M av kan utmata z(t), z(t +1), ..., z(t + 19) ) returnera ; ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$
gå till 1

Ovanstående attack kräver 226 byte chiffertext . Det är möjligt att förbättra attacken, vilket kräver 2 24,3 byte. En liknande attack skulle kunna tillämpas på F-FCSR-16.

Anteckningar

↑ 1 2 A. Klapper, M. Goresky, 2-adic shift registers, i Fast Software Encryption'93, ed. av RJ Anderson. Lecture Notes in Computer Science, vol. 809 (Springer, Berlin, 1994), sid. 174-178
↑ F. Arnault, T. Berger, A. Necer, En ny klass av strömchiffer som kombinerar LFSR- och FCSR-arkitekturer, pågår i kryptologi—INDOCRYPT 2002, ed. av A. Menezes, P. Sarkar. Lecture Notes in Computer Science, vol. 2551/2002 (Springer, Berlin, 2002), s. 22-33
↑ B. Zhang, H. Wu, D. Feng, F. Bao, Vald chiffertextattack på en ny klass av självsynkroniserande strömchiffer, in Progress in Cryptology—INDOCRYPT 2004, ed. av A. Canteaut, K. Viswanathan. Lecture Notes in Computer Science, vol. 3348/2004 (Springer, Berlin, 2004), s. 73-83
↑ F. Arnault, T. Berger, Design och egenskaper hos en ny pseudoslumpgenerator baserad på en filtrerad FCSR-automat. IEEE Trans. Comput. 54, 1374-1383 (2005)
↑ F. Arnault, T. Berger, F-FCSR: Design av en ny klass av strömchiffer, i Fast Software Encryption 2005, ed. av H. Gilbert, H. Handschuh. Lecture Notes in Computer Science, vol. 3557 (Springer och Berlin, 2005), s. 83-97
↑ E. Jaulmes, F. Muller, Cryptanalysis of the F-FCSR stream cipher family, in Selected Areas in Cryptography—SAC 2005, ed. av B. Preneel, S. Tavares. Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2005), sid. 36-50
↑ Arkiverad kopia . Hämtad 23 november 2011. Arkiverad från originalet 27 maj 2011. (obestämd)
↑ Arkiverad kopia . Hämtad 23 november 2011. Arkiverad från originalet 27 maj 2011. (obestämd)
↑ Arkiverad kopia . Hämtad 23 november 2011. Arkiverad från originalet 27 maj 2011. (obestämd)
↑ eSTREAM-projektet . Hämtad 23 november 2011. Arkiverad från originalet 5 december 2011. (obestämd)
↑ M. Hell, T. Johansson, Breaking the F-FCSR-H stream cipher in real time, in Advances in Cryptology— ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350/2008 (Springer, Berlin, 2008), s. 557-569
↑ Arkiverad kopia . Hämtad 23 november 2011. Arkiverad från originalet 13 augusti 2012. (obestämd)

Litteratur

M. Hell, T. Johansson, Breaking the F-FCSR-H stream chiffer in real time, in Advances in Cryptology. ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350/2008 (Springer, Berlin, 2008), s. 557-569
F. Arnault och T. P. Berger. F-FCSR: design av en ny klass av strömchiffer. I Fast Software Encryption - FSE 2005, v. 3557 av föreläsningsanteckningar i datavetenskap, sid. 83-97. Springer-Verlag, 2005.
F. Arnault, T. Berger, C. Lauradoux, Uppdatering om F-FCSR-strömchiffer. eSTREAM, ECRYPT Stream Cipher Project, Rapport 2006/025 (2006).

Länkar

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

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer