Desim

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. maaliskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Salaustekniikassa Decim on LFSR-pohjainen stream-salaus , jonka ovat kehittäneet Côme Burbain , Oliver Billet, Ann Cantoux, Nicolas Courtois , Blandine Debret, Henry Hilbert, Louis Goubin, Aline Gouget, Louis Grandboulan, Cederic Lardoux, Marin Mignet ja Thomas Pornin. Herv Sibe. Erikoistunut laitteiston toteuttamiseen. Patentoitu . Se otettiin käyttöön eSTREAM- projektissa , jossa se ei mennyt kolmatta vaihetta pidemmälle.

Johdanto

Salauksille tärkein vaatimus on vastustuskyky erilaisille hyökkäyksille . Algebralliset hyökkäykset ovat yksi vakavimmista tietovirtauhkista . Jos salaisten avainbittien yhdistelmän ja sen tuottaman gammabitin välinen suhde on yksinkertainen tai helposti ennustettavissa, niin algebrallisten suhteiden löytäminen salaisten avainbittien yhdistelmän ja avainvirtabitin (gamma) välillä on myös yksinkertainen tehtävä. Salaisen avaimen bittien yhdistelmän (tai salaisen avaimen generoiman LFSR :n alkutilan bittien yhdistelmän ) ja avainvirran (gamma) bittien välisen suhteen vaikeuttamiseksi käytetään epälineaarista suodatustoimintoa . salaisen avaimen bittien yhdistelmä ja desynkronointimekanismit salaisen avaimen bittien yhdistelmän ja avainvirran (gamma) bittien välillä. Molemmat mekanismit (epälineaarinen suodatustoiminto ja LFSR-bittien ja avainvirran bittien yhdistelmän välinen desynkronointimekanismi ) ovat toiminnan perusta ja pääasiallinen keino estää Decim - salauksen kryptanalyyttiset hyökkäykset .

Yleiskatsaus Decimin työhön

Decim - virtasalauksen käytön aloittaminen alkaa syöttämällä 80-bittinen yksityinen avain ja 64-bittinen julkinen avain (Initialization Vector). Sitten lasketaan 192-bittisen LFSR :n alkutila käyttämällä tiettyjä bittien ja bittien lineaarisia yhdistelmiä, epälineaarista suodatintoimintoa ja ABSG- näytteenottomekanismia . Kun kaikki nämä toiminnot on suoritettu, avainvirran [1] generointi alkaa ja se täyttää erityisen puskurin BUFFER , jolla varmistetaan bittien jatkuva ulostulo salauksen lähtöön, jossa ne lisätään modulo kaksi binäärillä. selkeän tekstin merkkijono . $K$ $IV$ $K$ $IV$ $F$ $z=(z_{t})|_{t\geqslant 0}$ $z_{t}$

Tekniset tiedot

LFSR ja suodatustoiminto $F$

LFSR :ään liittyvä primitiivinen polynomi on muodossa:

$P(X)=X^{192}+X^{189}+X^{188}+X^{169}+X^{156}+X^{155}+X^{132}+ X^{131}+X^{94}+X^{77}+X^{46}+X^{17}+X^{16}+X^{5}+1$

Merkitään [2] :lla LFSR -lähdöstä vastaanotettu bittisarja, jolloin LFSR -lähdön bitin laskemisen sääntö on: ${\displaystyle s=(s_{t})|_{t\geqslant 0))$

$s_{192+n}=s_{187+n}\oplus s_{176+n}\oplus s_{175+n}\oplus s_{146+n}\oplus s_{115+n}\oplus s_{98+n}\oplus s_{61+n}\oplus s_{60+n}\oplus s_{37+n}\oplus s_{36+n}\oplus s_{23+n}\oplus s_{ 4+n}\oplus s_{3+n}\oplus s_{n}$

LFSR- bittien ja -bittien välisten riippuvuuksien monimutkaisemiseksi käytetään seitsemän muuttujan epälineaarista suodatusfunktiota . Jokaisessa syklissä sitä sovelletaan kahdesti - bitteihin, jotka ovat eri paikoissa LFSR :ssä . Merkitsee ja toimii siten, että ${\displaystyle s_{t))$ $z_{t}$ $F(x_{1},...x_{7})$ $F$ $F1(x_{i_{1}},...,x_{i_{7}})$ $F2(x_{i_{8}},...x_{i_{14}})$

$F1(x_{i_{1}},...,x_{i_{7}})=F(x_{i_{1}},...,x_{i_{7}})$

$F2(x_{i_{8}},...,x_{i_{14}})=F(x_{i_{8}},...,x_{i_{14}})$ , missä

$F(x_{i_{1}},...,x_{i_{7}})=\sum _{1\leqslant j<k\leqslant 7}{x_{i_{j}}x_{ i_{k}}}$

Päästää

$y1=(y1_{t})|_{t\geqslant 0}=F(s_{i_{1}+t},...,s_{i_{7}+t})$

$y2=(y2_{t})|_{t\geqslant 0}=F(s_{i_{8}+t},...,s_{i_{14}+t})$

$\mathbf {y} =y1_{0},y2_{0},y1_{1},y2_{1},...$ .

LFSR - bittipaikat , jotka ovat argumentteja ja : $F1$ $F2$

: 1, 32, 40, 101, 164, 178, 187; $F1$
: 6, 8, 60, 116, 145, 181, 191. $F2$

Sitten

$\mathbf {y} 1_{t}=F(s_{t+1},s_{t+32},s_{t+40},s_{t+101},s_{t+164}, s_{t+178},s_{t+187})$

$\mathbf {y} 2_{t}=F(s_{t+6},s_{t+8},s_{t+60},s_{t+116},s_{t+145}, s_{t+181},s_{t+191})$ .

ABSG-näytteenottomekanismi

ABSG- näytteenottomekanismia käytetään estämään algebralliset hyökkäykset ja tietyntyyppiset nopeat korrelaatiohyökkäykset desynkronoimalla suodatetut LFSR - bitit ja gammabitit . ABSG- näytteenottomekanismin tehtävänä on jakaa sekvenssi muodon alisekvenssiin , jossa , ja tulostaa jos , ja muuten. $y_{0},y_{1},y_{2},...$ $z_{0},z_{1},z_{2},...$ $\mathbf {y} =y1_{0},y2_{0},y1_{1},y2_{1},...$ $(b,b^{i},{\bar {b)))$ ${\displaystyle b\in {(0,1)))$ $b$ $i = 0$ ${\bar {b}}$

ABSG- algoritmi

Syöte: ( ) $y_{0},y_{1},y_{2},\dots$

Aseta: , $i = 0$ $j=0$

Toista seuraavat vaiheet:

${\displaystyle e=y_{i))$ , ; $z_{j}=y_{i+1}$
$i=i+1$ ;
kun taas ( == ) ; $y_{i}$ ${\bar {e))$ $i=i+1$
$i=i+1$ ;
lähtö ; ${\displaystyle z_{j))$
$j=j+1$ ;

Esimerkki:

anna sitten vastaavalla sekvenssillä ABSG :n lähdössä muoto . $y=(0101001110100100011101)$ $z=(10111010)$

Keskimäärin bitti ABSG :n sisääntulossa vastaa bittiä lähdössä, kuten esimerkistä voidaan nähdä. $3n$ $n$

Puskuri BUFFER

Koska ABSG -bittilähtö ei ole vakio ( keskimäärin kolmea bittiä käytetään yhden bitin luomiseen ), ja koska virtasalauksen on lähetettävä gammabitti jokaista kellojaksoa kohti , BUFFER-puskuria käytetään lähettämään jatkuvasti gammabittejä . $z_{t}$ $y_{t}$

Kun RSLOS:n alkutila on alustettu, BUFFERin täyttö alkaa ja vasta kun BUFFER on täytetty, alkaa selkeän tekstin salaus (lisäksi BUFFER toimii jonon tyypin mukaan - ensimmäinen bitti, joka tulee BUFFERiin on ensimmäisenä poistuva).

On mahdollista, että vaikka BUFFERin olisi pitänyt lähettää vähän, se osoittautui tyhjäksi. Tämä todennäköisyys on pieni, esimerkiksi PUSKURIN , jossa on neljä tuloa, todennäköisyys, että se on tyhjä, kun sen pitäisi emittoi vähän, on . Decim -kehittäjät ehdottavat tämän mahdollisuuden huomiotta jättämistä olettaen, että sen todennäköisyys on nolla. $2^{-89}$

RLOS :n alkutilan alustus

Salainen avain on 80 bittiä pitkä, julkinen avain (Initialization Vector) on 64 bittiä pitkä, mutta täytetty nollasta 80 bittiin. Let bittiä LFSR . Sitten LFSR : n alkutila lasketaan seuraavasti: $K$ $IV$ $x_{0},...,x_{191}$

$x_{i}={\begin{cases}K_{i}\lor IV_{i}~for~0\leqslant i\leqslant 56\\K_{i-56}\lor {\bar {IV_{ i-56}}}~for~56\leqslant i\leqslant 111\\K_{i-112}\oplus IV_{i-112}~for~112\leqslant i\leqslant 191\\\end{cases}}$

Voidaan nähdä, että LFSR :n mahdollisten alkutilojen lukumäärä on . $2^{56+56+24}$

Jotain selitystä Decimin toiminnasta

RSLOS

Aika-muistin kompromissihyökkäysten estämiseksi LFSR :n pituuden on oltava vähintään 160 bittiä. Lisäksi LFSR :n tulisi olla yksinkertainen laitteistototeutuksessa. Näiden tekijöiden perusteella LFSR -kooksi valittiin 192 bittiä.

Primitiivisen polynomin Hamming-painon tulee olla riittävän suuri nopean korrelaatiohyökkäyksen estämiseksi , mutta toisaalta primitiivisen polynomin Hamming-painon ei tulisi olla liian suuri, jotta salauksen aika laitteistossa ei kasvaisi. toteutus. $P(x)$ $P(x)$

Suodatintoiminto $F$

Suodatinfunktion on oltava tasapainossa [3] ja differentiaalisen krypta -analyysin estämiseksi sen on täytettävä etenemiskriteeri : funktion on oltava tasapainoinen. Myös laitteiston toteutuksen yksinkertaistamiseksi on toivottavaa, että funktio on symmetrinen, eli että funktion arvo riippuu vain sen argumentin Hamming-painosta (joukko x_1,…x_7). Kaikki tämä vaatimus täyttyy muodon neliöfunktiolla : $F$ $D_{u}F(x)=F(x)+F(x+u)$ $F$ $F$

$F(x_{i_{1}},...,x_{i_{7}})=\sum _{1\leqslant j<k\leqslant 7}{x_{i_{j}}x_{ i_{k}}}$ ,

jota käytetään Decim- salauksen suodatusfunktiona .

Decim-salauksen vahvuus

Lukuun ottamatta monimutkaisia aikamuistin vaarantamishyökkäyksiä, Decim- salaukseen kohdistuvien hyökkäysten laskennallinen monimutkaisuus on sen tekijöiden mukaan yhtä monimutkainen kuin raa'an voiman hyökkäys, eikä se ole pienempi kuin [4] . $O(2^{80})$

Mutta Hongyang Wun ja Bart Prenilin suorittama riippumaton kryptausanalyysi osoitti Decim-salauksen epäluotettavuuden, ja hyökkäyksen laskennallinen monimutkaisuus osoittautui enintään , mikä on täysin mahdotonta hyväksyä [5] . $O(2^{21})$

Muistiinpanot

↑ - rytmiin luotu gamma $z_{t}$ $t$
↑ - kelloa kohti laskettu bitti ${\displaystyle s_{t))$ $t$
↑ Muuttujien funktiota kutsutaan tasapainoksi, jos sen Hamming-paino on yhtä suuri kuin $n$ $2^{{n-1}}$
↑ [1] Arkistoitu 27. toukokuuta 2011 Wayback Machinessa C. Berbain1, O. Billet1, A. Canteaut2, N. Courtois3, B. Debraize, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C Lauradoux, M. Minier, T. Pornin, H. Sibert Decim – uusi virtasalaus laitteistosovelluksiin
↑ [2] Arkistoitu 27. toukokuuta 2011 Wayback Machinessa Hongjun Wu, Bart Preneel Cryptanalysis of Stream Cipher DECIM Katholieke Universiteit Leuven, Dept. ESAT/COSIC

Linkit

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
Muut	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher