Decim

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. március 15-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A kriptográfiában a Decim egy LFSR-alapú adatfolyam-rejtjel , amelyet Côme Burbain , Oliver Billet, Ann Cantoux, Nicolas Courtois , Blandine Debret, Henry Hilbert, Louis Goubin, Aline Gouget, Louis Grandboulan, Cederic Lardoux, Marin Mignet és Thomas Pornin fejlesztett ki. Herv Sibe . Hardveres implementációra specializálódott. Szabadalmaztatott . Az eSTREAM projektben vezették be , ahol nem jutott túl a harmadik szakaszon.

Bevezetés

A rejtjelekkel szemben támasztott legfontosabb követelmény a különféle típusú támadásokkal szembeni ellenállás . Az algebrai támadások az egyik legsúlyosabb biztonsági fenyegetés az adatfolyam-rejtjelekkel szemben . Ha a titkos kulcsbitek kombinációja és az általa generált gammabit közötti kapcsolat egyszerű vagy könnyen megjósolható, akkor a titkos kulcsbitek kombinációja és a kulcsfolyam bit ( gamma ) közötti algebrai kapcsolatok keresése is egyszerű feladat. A titkos kulcs bitjeinek kombinációja (vagy a titkos kulcs által generált LFSR kezdeti állapotának bitjeinek kombinációja ) és a kulcsfolyam bitjei (gamma) közötti kapcsolat bonyolítására egy nemlineáris szűrőfüggvényt használnak . a titkos kulcs bitjeinek és a titkos kulcs bitjeinek kombinációja és a kulcsfolyam bitjei közötti deszinkronizációs mechanizmusok kombinációja (gamma ). Mindkét mechanizmus (a nemlineáris szűrési funkció és az LFSR bitek és a kulcsfolyam bitek kombinációja közötti deszinkronizációs mechanizmus) a működés alapja és a Decim titkosítás kriptoanalitikus támadásainak megelőzésének fő eszköze .

Decim munkásságának áttekintése

A Decim adatfolyam-rejtjel használatának megkezdése egy 80 bites privát kulcs és egy 64 bites nyilvános kulcs (inicializálási vektor) megadásával kezdődik. Ezután a bitek és bitek bizonyos lineáris kombinációival , egy nemlineáris szűrőfunkcióval és az ABSG mintavételezési mechanizmus alkalmazásával kiszámítják a 192 bites LFSR kezdeti állapotát . Mindezen műveletek végrehajtása után megkezdődik a kulcsfolyam [1] generálása, és egy speciális puffert tölt meg BUFFER , amely biztosítja a bitek folyamatos kimenetét a titkosító kimenetére, ahol azokat modulo kettes hozzáadásával egy binárissal. egyszerű szöveges karakterek sorozata . $K$ $IV$ $K$ $IV$ $F$ $z=(z_{t})|_{t\geqslant 0}$ $z_{t}$

Specifikáció

LFSR és szűrési funkció $F$

Az LFSR - hez kapcsolódó primitív polinom alakja a következő:

$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$

Jelölje [2] -vel az LFSR kimenetről kapott bitsorozatot , akkor az LFSR kimeneten lévő bit kiszámításának szabálya : ${\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}$

Az LFSR bitek és bitek közötti függőségek bonyolítására hét változóból álló nemlineáris szűrőfüggvényt használnak . Minden ciklusban kétszer kerül alkalmazásra az LFSR különböző pozícióiban lévő bitekre . Jelölje és olyan függvényeket, hogy ${\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}})$

és

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

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

Hadd

$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 bitpozíciók , amelyek argumentumai és argumentumai : $F1$ $F2$

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

Akkor

$\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})$ .

Az ABSG mintavételi mechanizmus

Az ABSG mintavételi mechanizmus az algebrai támadások és bizonyos típusú gyors korrelációs támadások megelőzésére szolgál a szűrt LFSR bitek és a gamma bitek deszinkronizálásával . Az ABSG mintavételi mechanizmusának feladata, hogy a sorozatot a form részsorozataira bontsa , ahol , és kimenet , ha , és egyébként. $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$ ${\bár {b}}$

ABSG algoritmus

Bevitel: ( ) $y_{0},y_{1},y_{2},\dots$

Készlet: , $i=0$ $j=0$

Ismételje meg a következő lépéseket:

${\displaystyle e=y_{i))$ , ; $z_{j}=y_{i+1}$
$i=i+1$ ;
míg ( == ) ; $y_{i}$ ${\bar {e))$ $i=i+1$
$i=i+1$ ;
kimenet ; ${\displaystyle z_{j))$
$j=j+1$ ;

Példa:

legyen , akkor az ABSG kimenetén lévő megfelelő sorozat alakja . $y=(0101001110100100011101)$ $z=(10111010)$

Átlagosan az ABSG bemenetén lévő bit a kimeneten lévő bitnek felel meg , amint az a példából látható. $3n$ $n$

Puffer BUFFER

Mivel az ABSG bitkimenet nem állandó ( átlagosan három bitet használnak egy bit létrehozásához ), és mivel a stream titkosítónak minden órajelciklushoz egy gamma bitet kell kiadnia, a BUFFER puffert használjuk a gamma bitek folyamatos kibocsátására . $z_{t}$ $y_{t}$

Az RSLOS kezdeti állapotának inicializálása után megkezdődik a BUFFER kitöltése , és csak a BUFFER kitöltése után kezdődik meg a nyílt szöveg titkosítása (a BUFFER ráadásul a sor típusának megfelelően működik - az első bit, amely a BUFFER -be kerül, a először kilépni).

Lehetséges, hogy bár a BUFFER -nek ki kellett volna bocsátania egy kicsit, üresnek bizonyult. Ez a valószínűség kicsi, például egy négy bemenettel rendelkező BUFFER esetén annak a valószínűsége, hogy üres, amikor egy kicsit ki kellene adnia . A Decim fejlesztői azt javasolják, hogy hagyják figyelmen kívül ezt a lehetőséget, feltételezve, hogy annak valószínűsége nulla. $2^{-89}$

Az RLOS kezdeti állapotának inicializálása

A titkos kulcs 80 bites, a nyilvános kulcs (Initialization Vector) 64 bites, de nullától 80 bitig párnázott. Legyen az LFSR bitjei . Ezután az LFSR kezdeti állapotát a következőképpen számítjuk ki: $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{esetek}}$

Látható, hogy az LFSR lehetséges kezdeti állapotainak száma . $2^{56+56+24}$

Néhány magyarázat a Decim működéséről

RSLOS

Az időmemória kompromisszumos támadások elkerülése érdekében az LFSR hosszának legalább 160 bitnek kell lennie. Ezenkívül az LFSR -nek egyszerűnek kell lennie a hardveres megvalósításban. Ezen tényezők alapján az LFSR méretet 192 bitre választottuk.

A primitív polinom Hamming súlyának elég nagynak kell lennie ahhoz, hogy megakadályozza a gyors korrelációs támadást , de másrészt a primitív polinom Hamming súlyának nem szabad túl nagynak lennie, hogy ne növelje meg a rejtjelezés idejét a hardverben. végrehajtás. $P(x)$ $P(x)$

Szűrő funkció $F$

A szűrőfüggvénynek egyensúlyinak kell lennie [3] , és a differenciális kriptoanalízis elkerülése érdekében meg kell felelnie a terjedési kritériumnak : a függvénynek egyensúlyinak kell lennie. Ezenkívül a hardveres megvalósítás egyszerűsítése érdekében kívánatos, hogy a függvény szimmetrikus legyen, azaz a függvény értéke csak az argumentumának Hamming-súlyától függjön (x_1,…x_7 halmaz). Mindezt a követelményt az alak másodfokú függvénye teljesíti: $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}}}$ ,

amelyet a Decim titkosítás szűrési funkciójaként használnak .

A decim titkosítás erőssége

Az időmemória -kompromittáló támadások összetett eseteit figyelmen kívül hagyva a Decim titkosítás elleni támadások számítási összetettsége a szerzők szerint megegyezik a nyers erejű támadás összetettségével, és nem kisebb, mint [4] . $O(2^{80})$

De egy Hongyang Wu és Bart Prenil által végzett független kriptográfiai elemzés kimutatta a Decim titkosítás megbízhatatlanságát, és a támadás számítási bonyolultsága nem több, mint , ami abszolút elfogadhatatlan [5] . $O(2^{21})$

Jegyzetek

↑ - ütemre generált gamma $z_{t}$ $t$
↑ - órajelenként számított bit ${\displaystyle s_{t))$ $t$
↑ Egy változók függvényét egyensúlynak nevezzük, ha Hamming-súlya egyenlő $n$ $2^{{n-1}}$
↑ [1] Archiválva : 2011. május 27. a Wayback Machine -nél 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 – új adatfolyam-rejtjel hardveres alkalmazásokhoz
↑ [2] Archivált : 2011. május 27., a Wayback Machine Hongjun Wu, Bart Preneel Cryptanalysis of Stream Cipher DECIM Katholieke Universiteit Leuven, Dept. ESAT/COSIC

Linkek

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