F-FCSR

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. marts 2013; checks kræver 8 redigeringer .

F-FCSR er en familie af strømcifre baseret på brugen af et carry feedback shift register (FCSR) med et lineært filter ved udgangen. Idéen til chifferen blev foreslået af Terry Berger, François Arnault og Cédric Larade. F-FCSR blev indsendt til eSTREAM- konkurrencen , blev inkluderet på listen over vindere af konkurrencen i april 2008, men senere blev en kryptografisk svaghed afsløret, og i september 2008 blev F-FCSR udelukket fra eSTREAM-listen.

Historie

Ideen om at bruge et carry feedback shift register (FCSR) til at skabe et streamingfilter blev først foreslået af Clapper og Goreski i 1994 [1] . Senere udviklede de en algoritme til sådan en chiffer [1] . Én FCSR uden tilslutning af en linjekomponent kan ikke bruges som stream-chiffer, da den let dekrypteres.

I 2002 blev en selvsynkroniserende stream-chiffer baseret på den kombinerede brug af FCSR og LFSR [2] foreslået . Det blev senere udsat for et krypteringsvalgsangreb [3] .

I 2005 foreslog Arnaud og Berger ideen om at bruge FCSR og et lineært filter sammen for at skabe en stream-chiffer, som blev kaldt F-FCSR (Filtered FCSR) [4] . Senere foreslog de 4 algoritmer, der implementerer denne idé: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 og F-FCSR-DF8 [5] . De første to brugte statiske filtre, de sidste to brugte nøglespecifikke filtre. Senere blev svagheden af alle disse algoritmer mod forskellige typer angreb afsløret [6] .

I 2005 indsendte Terry Berger, François Arnol og Cédric Laradoud to F-FCSR [7] -baserede cifre til eSTREAM-konkurrencen: F-FCSR-H for hardware og F-FCSR-8 for software. Som et resultat af efterfølgende test blev der fundet sårbarheder i de indledende versioner af F-FCSR-H og F-FCSR-8 [8] , som senere blev rettet i versionerne F-FCSR-H v.2 og F-FCSR-16 [9] . En forbedret version af F-FCSR-H v.2 blev finalist til eSTREAM [10] . Men efter opdagelsen af sårbarheden [11] blev den udelukket fra eSTREAM-porteføljen (rev.1) [12] .

Versionskarakteristika

Navn	Hovedregisterlængde _	Initialisering	Filter	Antal bits ved filterudgangen
F-FCSR-8	128	64/128 cyklusser (afhængig af IV)	Afhænger af nøglen	otte
F-FCSR-H	160	160 barer	Statisk	otte
F-FCSR-8.2	256	258 barer	Afhænger af nøglen	16
F-FCSR-16	256	16 + 258 takter	Statisk	16
F-FCSR-H v.2	160	20 + 162 barer	Statisk	otte

Beskrivelse af algoritmen

FCSR

FCSR er implementeret i to konfigurationer: Galois og Fibbonacci. F-FCSR bruger Galois-konfigurationen, fordi den er mere effektiv. Følgende notation introduceres:

q - forbindelsesintegritet - et negativt ulige heltal, der opfylder følgende betingelser:
- ${\displaystyle 2^{|q|-1}=1\mod {q))$
- T = (|q| − 1)/2 er primtal, 2T er perioden for bitsekvensen p/q
- Antallet af enere i den binære repræsentation af tallet (1 − q)/2 af orden n/2
p er en nøgleafhængig parameter, således at 0 < p < |q|
n er størrelsen af hovedregisteret FCSR, |q| i binær notation har n + 1 tegn: 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 er et n-bit hovedregister, værdierne af dets i-te bit,. ${\displaystyle m(t)=\sum _{i=0}^{n-1}m_{i}(t)\cdot 2^{i))$
C er et l-bit skifteregister, l + 1 er antallet af enere i binær notation d,. ${\displaystyle c(t)=\sum _{i=0}^{l-1}c_{i}(t)\cdot 2^{i))$
(m, c) - FCSR-tilstand

Hvis (m, c) er FCSR-tilstanden på tidspunktet t 0 , , , så er den binære repræsentation af p/q, hvor p = m + 2c. $m=m(t_{0})$ $c=c(t_{0})$ $(m_{0}(t_{0}+i))_{i\i {N))$

FCSR eksempel

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

Filtrering

Outputfiltreringsfunktionen er defineret af masken ( ) En outputbit er defineret som følger: ${\displaystyle {f}_{0,}{f}_{1,...,}{f}_{n-1))$ ${\displaystyle {k}=\bigoplus _{i=0}^{n-1}{f}_{i}\cdot {m}_{i))$

Initialisering

I betragtning af svagheden af tidligere F-FCSR-versioner på grund af svag initial bitblanding i hovedregistret, er initialiseringsproceduren i F-FCSR-H v.2 og F-FCSR-16 som følger:

Hovedregistret M initialiseres ved at sammenkæde den hemmelige nøgle K og IV - (K, IV), nuller skrives til bæreregisteret.
Består 16 cyklusser af generatoren til F-FCSR-16 og 20 for F-FCSR-H v.2
De resulterende henholdsvis 256 og 160 bit skrives til M
Det tager n + 2 cyklusser af generatoren, mens udgangsbittene kasseres

F-FCSR-baserede cifre

F-FCSR-H v.2

Nøglelængde 80 bit, IV - 80 bit
q = −1993524591318275015328041611344215036460140087963
Bæreregisterlængde l = 82
d = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E) 16
Sekvensen af bits i outputtet , dvs ${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

Nøglelængde 128 bit, IV - 128 bit
q = −183971440845619471129869161809344131658298317655923135753017128462155618715019
Bæreregisterlængde l = 130
d = (CB5E129F AD4F7E66 780CAA2E C8C9CEDB 2102F996 BAF08F39 EFB55A6E 390002C6) 16
Output bitsekvens ${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)$

Beskrivelse af angrebet

Oprindeligt fundne sårbarheder i F-FCSR-8 og F-FCSR-H forbundet med et lille antal cyklusser under initialisering blev rettet i F-FCSR-16 og F-FCSR-H v.2. I 2008 beskrev og udførte Martin Hell og Thomas Joansson et angreb på F-FCSR, der kunne afsløre FCSRs tilstand.

Filtreringsfunktionen er lineær, så F-FCSR's kryptografiske styrke bestemmes af ikke-lineariteten af FCSR, som opstår på grund af tilstedeværelsen af carry-registret, så systemet skal lineariseres ved at maksimere antallet af nuller i carry Tilmeld. Overvej en situation, hvor tilstanden for transportregistret i 20 cyklusser vil være som følger:

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

Hvis tilbagekoblingsbitten er 0, forbliver bits i bæreregisteret, der er 0, 0, og dem, der er 1, bliver 0 med sandsynlighed 1/2. For at (*) skal opstå, kræves der omtrent på hinanden følgende nuller i feedbackbitten. . $\log _{2}{82}+19\ca. 26$

Ved antagelse (*) afhænger hovedregistrets tilstande M(t + 1), …, M(t + 19) lineært af M(t) , og vi kender denne afhængighed.

Lad os betegne outputbytes z(t), z(t + 1), …, z(t + 19) .

Lad os udtrykke z(t), z(t + 1), … , z(t + 19) i form af bitværdierne i hovedregisteret på tidspunktet t: M(t) = (m 0 … m 159 ) .
Vi får 20 ligninger med 20 ubekendte , hvor : … På samme måde får vi ligningssystemer afhængig af , hvor osv. I alt 8 systemer med 20 ligninger med 20 ubekendte. Vi bruger følgende notation: , , … . Lad os betegne vektoren Så kan systemerne skrives på formen , hvor er en kendt matrix bestemt af filtreringsfunktionen. Algoritmen til at finde hovedregisterets tilstand under forudsætningen (*) kan beskrives som følger: $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}={\hat {M}}_{j}P_{j}$ $P_{j}$

På tidspunktet t får vi bytes ved udgangen: z(t), z(t +1), . . . , z(t + 19)
for i = 0 til 7 Løs ligningen $W_{j}={\hat {M}}_{j}P_{j}$ hvis (ingen løsninger) goto 1 ellers gem mulige værdier ${\hat {M}}_{j}$
for (alle mulige sæt ) ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$ hvis (M af kan output z(t), z(t +1), . . . , z(t + 19) ) returnere ; ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$
gå til 1

Ovenstående angreb kræver 226 bytes chiffertekst . Det er muligt at forbedre angrebet, hvilket kræver 2 24,3 bytes. Et lignende angreb kunne anvendes på F-FCSR-16.

Noter

↑ 1 2 A. Klapper, M. Goresky, 2-adiske skifteregistre, i Fast Software Encryption'93, red. af RJ Anderson. Lecture Notes in Computer Science, vol. 809 (Springer, Berlin, 1994), s. 174-178
↑ F. Arnault, T. Berger, A. Necer, En ny klasse af strømcifre, der kombinerer LFSR- og FCSR-arkitekturer, under fremskridt i Cryptology—INDOCRYPT 2002, red. af 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, Valgt chiffertekstangreb på en ny klasse af selvsynkroniserende stream-cifre, in Progress in Cryptology—INDOCRYPT 2004, red. af A. Canteaut, K. Viswanathan. Lecture Notes in Computer Science, vol. 3348/2004 (Springer, Berlin, 2004), s. 73-83
↑ F. Arnault, T. Berger, Design og egenskaber af en ny pseudorandomgenerator baseret på en filtreret FCSR-automat. IEEE Trans. Comput. 54, 1374-1383 (2005)
↑ F. Arnault, T. Berger, F-FCSR: Design af en ny klasse af stream-cifre, i Fast Software Encryption 2005, red. af H. Gilbert, H. Handschuh. Lecture Notes in Computer Science, vol. 3557 (Springer og Berlin, 2005), pp. 83-97
↑ E. Jaulmes, F. Muller, Cryptanalysis of the F-FCSR stream cipher family, in Selected Areas in Cryptography—SAC 2005, red. af B. Preneel, S. Tavares. Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2005), s. 36-50
↑ Arkiveret kopi . Hentet 23. november 2011. Arkiveret fra originalen 27. maj 2011. (ubestemt)
↑ Arkiveret kopi . Hentet 23. november 2011. Arkiveret fra originalen 27. maj 2011. (ubestemt)
↑ Arkiveret kopi . Hentet 23. november 2011. Arkiveret fra originalen 27. maj 2011. (ubestemt)
↑ eSTREAM-projektet . Hentet 23. november 2011. Arkiveret fra originalen 5. december 2011. (ubestemt)
↑ 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
↑ Arkiveret kopi . Hentet 23. november 2011. Arkiveret fra originalen 13. august 2012. (ubestemt)

Litteratur

M. Hell, T. Johansson, Breaking the F-FCSR-H stream cipher i realtid, i Advances in Cryptology. ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350/2008 (Springer, Berlin, 2008), s. 557-569
F. Arnault og T. P. Berger. F-FCSR: design af en ny klasse af stream-cifre. I Fast Software Encryption - FSE 2005, v. 3557 af Lecture Notes in Computer Science, s. 83-97. Springer-Verlag, 2005.
F. Arnault, T. Berger, C. Lauradoux, Opdatering om F-FCSR-strømchiffer. eSTREAM, ECRYPT Stream Cipher Project, Rapport 2006/025 (2006).

Links

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

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher