Nyúl

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. november 12-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A Rabbit  egy nagy sebességű adatfolyam-rejtjel , amelyet először [1] 2003 februárjában mutattak be a 10. FSE szimpóziumon. 2005 májusában benevezték az eStream versenyre , amelynek célja az adatfolyam-titkosítási rendszerek európai szabványainak létrehozása volt.

A Rabbitot Martin Boesgaard , Mette Vesterager , Thomas Pedersen , Jesper Christiansen és Ove Scavenius fejlesztette ki .

A Rabbit 128 bites kulcsot és 64 bites inicializálási vektort használ. A rejtjelező szoftvert nagy titkosítási sebességre tervezték. Ugyanakkor a titkosítási sebesség elérheti a 3,7 ciklust bájtonként ( CPB ) a Pentium 3 processzor és a 10,5 ciklust bájtonként az ARM7 esetében. A titkosítás azonban gyorsnak és kompaktnak is bizonyult, amikor hardveresen implementálták.

A titkosítás fő összetevője egy bitfolyam -generátor , amely iterációnként 128 bitet titkosít egy üzenetből. A titkosítás előnye abban rejlik, hogy két egymást követő iteráció között alaposan összekeveri belső állapotait. A keverési funkció teljes egészében a modern processzorokon elérhető aritmetikai műveleteken alapul, vagyis nincs szükség helyettesítő S-boxokra és keresőtáblákra a titkosítás megvalósításához.

A titkosítás készítői a Cryptico honlapján [2] egy teljes adatlapot biztosítottak . A titkosítást az RFC 4503 is leírja . A titkosítás szabadalma a Cryptico birtokában volt, és sok éven át a titkosítás kereskedelmi felhasználásához engedély kellett. 2008. október 6-án azonban engedélyezték a rejtjelezés bármilyen célra történő ingyenes használatát [3] .

Rabbit és eStream [4]

eStream Contest

Az eSTREAM projekt adatfolyam titkosításai két profilból állnak. Az 1. profil szoftverorientált rejtjeleket tartalmaz, a 2. profil pedig hardverorientált rejtjeleket.

A projekt legjobb rejtjelei:

1. profil 2. profil
HC-128 F-FCSR-H v2
Nyúl Gabona v1
Salsa 20/12 MICKEY v2
Sosemanuk Trivium

Az 1. profil szimmetrikus adatfolyam-rejtjeleket tartalmaz, jó szoftvermegvalósítással. Annyira jó, hogy a gammagenerálási módokban felül kellett volna múlniuk az AES blokkszimmetrikus titkosítási algoritmust. A profil fő követelménye a 128 bites biztonsági szint biztosítása volt.

A nyúl titkosítás érdemei és hátrányai

A Rabbit az eSTREAM projekt egyik legrégebbi terve. Ezt az adatfolyam-rejtjelet nem módosították vagy kiegészítették. Specifikációja 2003-tól napjainkig változatlan maradt. A rejtjel túlélte a projekt mindhárom szakaszát, és egyikben sem érte kriptanalitikai támadás. Többek között ez az algoritmus nagyon jól implementálható az Intel család új processzorain. Hátrányaként az a tény látható, hogy a Rabbit titkosítás mindössze 128 bites biztonsági szintet biztosít.

Az eSTREAM projekt 1. profilra vonatkozó zárószavazásának eredménye.

1. profil szemüveg
Nyúl 2.80
Salsa20 2.80
Sosemanuk 1.20
HC-128 0,60
NLS v2 -0,60
LEXv2 −1.20
CryptoMT v3 −1.40
Sárkány −1,60

Algoritmus

A stream titkosítás belső állapota 513 bitet tartalmaz. Ezek közül 512 nyolc 32 bites állapotváltozóra és nyolc 32 bites számlálóra van felosztva , ahol  az alrendszer állapotváltozója az iteráció során , és  a megfelelő változószámláló. Az 513. bit a hordozó bit , amelyet az iterációk között tárolni kell. Ez a bit nullára van inicializálva. 8 állapotváltozó és 8 számláló függ a kulcstól az inicializálás során.

Állapotbeállítás diagram

Az algoritmus inicializálása a 128 bites kulcs 8 állapotváltozóra és 8 számlálóra való kiterjesztésével történik úgy, hogy a kulcs, a kezdeti állapotváltozók és a kezdeti számlálók között egy az egyhez való megfelelés legyen . A kulcs 8 alkulcsra van osztva: , , … , , az állapotváltozók és a számlálók inicializálása alkulcsokkal történik

hol  van az összefűzési művelet.

A rendszer 4-szer fut le az alább definiált következő állapotfüggvény szerint, hogy csökkentse a kulcsbitek és a belső állapotváltozó bitek közötti korrelációt. A végén a számlálókat a következőképpen inicializálja újra:

hogy a számlálórendszer megfordításával megakadályozzuk a kulcs helyreállítását.

Következő állapotfüggvény

Itt minden kiegészítés modulo 2 32 . A és függvények egy 64 bites szám alsó és felső négy bájtját adják vissza ,  - ciklikus eltolás balra.

Számlálórendszer

A számlálók rendszerének változását meghatározó egyenletek:

ahol a hordozó bitszámot az adja meg

Ezenkívül az állandók a következőképpen vannak definiálva

Kivonási séma

Minden iteráció után 128 kimeneti bit jön létre a következő képletekkel:

ahol  a titkosítási adatfolyam 128 bites blokkja az iterációnál.

Titkosítási és visszafejtési séma

A titkosításhoz/dekódoláshoz XOR műveletet hajtanak végre a kivont bitek és a szöveg/titkosszöveg között.

ahol és jelöli a titkosított szöveg és a szöveg edik blokkját.

Kulcsbeállítási séma tulajdonságai

A kulcs telepítése három szakaszra osztható: kulcsbővítés, iterációs rendszer, számláló módosítása.

Biztonság

A Rabbit 128 bites védelmet biztosít azon támadók ellen, akiknek egyetlen egyedi kulcs a célja. Ha a támadás egyszerre több kulcson történik, és nem mindegy, hogy melyiket törik fel, akkor a biztonság 96 bitre csökken [5] .

Támadások a kulcslétrehozási funkció ellen

A kulcs beállítása után a számláló és állapotbitek szigorúan és nagyon nem lineárisan függenek a kulcsbitektől. Ez megnehezíti a feltörést a részkulcs kitaláló támadásaihoz, még akkor is, ha a számlálóbitek ismertek voltak a számláló módosítása után. Természetesen a számlálók ismerete megkönnyíti a más típusú feltöréseket.

Ütközéses támadás

A Rabbit titkosítás kétértelmű leképezést használ, a különböző kulcsok potenciálisan ugyanahhoz a tartományhoz vezethetnek. Ez a probléma alapvetően arra a kérdésre vezethető vissza, hogy a különböző kulcsok ugyanazt a számlálóértéket eredményezik-e, mivel a különböző számlálóértékek szinte biztosan különböző gammagenerációkat eredményeznek. Vegye figyelembe, hogy a kulcsbővítési és iterációs rendszert úgy tervezték meg, hogy minden kulcs egyedi számlálóértékeket eredményezzen. A számláló módosítása azonban egyenlő számlálóértékeket eredményezhet két különböző kulcshoz. Feltételezve, hogy négy kezdeti iteráció után a belső állapot lényegében véletlenszerű, és nem korrelál a számlálórendszerrel, az ütközések valószínűségét a "születésnapi paradoxon" adja meg, vagyis minden billentyű esetén egy ütközés várható egy 256-ban. bitszámláló[ adja meg ] . Így a számlálórendszer ütközése nem okozhat problémát a gyakorlatban.

Kapcsolódó kulcstámadás

A támadás a következő állapot szimmetriatulajdonságainak használatán és a kulcsbeállítási funkciókon alapul. Tekintsünk például két kulcsot , amelyeket egy reláció kapcsol össze mindenre . Ez az és a relációhoz vezet . Most fontolja meg, hogy mikor és mikor  ugyanaz a kulcs. Ha a feltétel teljesül, akkor a következő állapotfüggvény megtartja a szimmetriatulajdonságot. De könnyen ellenőrizhető, hogy a konstansok úgy vannak megválasztva, hogy . Így a következő állapotfüggvény nem érzékeny a kapcsolódó kulcstámadásra.

Partial Key Guess Attack

Találd ki és ellenőrizd a támadást

Egy ilyen támadás akkor lehetséges, ha a kimeneti biteket a belső állapotbitek kis halmazával meg lehetne jósolni. A támadónak ki kell tippelnie az állapotváltozók megfelelő részét, meg kell jósolnia a kimeneti biteket, és össze kell hasonlítania azokat a kimenetben közvetlenül megfigyelt bitekkel, hogy megbizonyosodjon arról, helyes-e a sejtése. A támadónak legalább 2*12 bemeneti bájtot kell kitalálnia a különböző g-függvényekhez, hogy egy bájttal szemben tesztelhessen. Ez 192 bit kitalálásával egyenértékű, ami nehezebb, mint az összes billentyű kipróbálása .

Találd meg és határozd meg a támadást

Ennek a módszernek az a lényege, hogy ki kell tippelnie több ismeretlen titkosítási változót, és ezek felhasználásával le kell vezetnie a fennmaradó ismeretleneket. Ezt követően a rendszert többször lefuttatják, és a kimenetet összehasonlítják a titkosítás valós kimenetével, hogy ellenőrizzék a feltételezést. A támadó 512 bites belső állapotot próbál meg újra létrehozni, azaz 4 egymást követő 128 bites adatot figyel meg a titkosítás kimenetén, és a következőket teszi:

  1. A 32 bites számlálót és a 32 bites állapotváltozót 8 bites változókra osztja.
  2. Egyenletrendszert ír, amely modellezi a számlálók és állapotváltozók változását, valamint a kimeneti adatokat. Az eredmény 160 egyenlet és 160 ismeretlen.
  3. A lehető legtöbb ismeretlen kitalálásával oldja meg ezt a rendszert.

Ennek a megközelítésnek a hatékonysága a kitalált változók számától függ. Ezt a számot alulról a legkevesebb bemeneti változót tartalmazó 8 bites alrendszer határolja. Ha figyelmen kívül hagyjuk a számlálókat, a következő állapotfüggvény minden bájtja 12 bemeneti bájttól függ. Ha figyelembe vesszük a számlálókat, akkor az alrendszer kimenetén minden bájt már 24 bemeneti bájttól függ. Ezért a támadónak 128 bitnél többet kell kitalálnia, így lehetetlenné téve a támadást.

Algebrai támadások

A g-függvény algebrai normálformája (ANF)

Adott egy logikai függvény , az ANF egy többváltozós polinom (vagyis a bemeneti változókból származó monomok összege) reprezentációja. A nagyszámú monom és azok jó teljesítményeloszlása ​​fontos tulajdonsága a nemlineáris blokkok titkosításában.

Egy 32 változóból álló véletlenszerű Boole-függvény esetén a monomok átlagos száma , az összes adott változót tartalmazó monomok átlagos száma pedig . Ha 32 ilyen, véletlenszerűen kiválasztott függvényt tekintünk, akkor a 32 függvény egyikében sem szereplő monomok átlagos száma 1, és a megfelelő szórás is 1.

A Rabbit-rejtjelben lévő g-függvény esetén a 32 logikai alfüggvény ANF-jének hatványa legalább 30. A monomiumok száma tól -ig változik , ahol egy véletlen függvény esetén ennek lennie kell . A monomiálisok eloszlását a fok függvényében az ábra mutatja. Ideális esetben a fő résznek a szaggatott vonalak között kellett volna lennie, amelyek eltéréseket mutatnak az ideális véletlen függvény átlagától. Egyes logikai függvények jelentősen eltérnek a véletlen függvény eredményeitől, azonban mindegyiknek nagyszámú nagyfokú monomija van.

Ezenkívül 32 funkció részleges egybeesését vizsgáltuk. Az egyszer előforduló monomiumok száma összesen , míg a egyáltalán nem előforduló monomiumok száma . Egy véletlen függvényhez képest ezek meglehetősen nagy eltérések. Ez az információ hasznos lehet a rejtjel jövőbeni elemzéséhez.

Algebrailag normálforma (ANF) a teljes titkosításhoz

Gyakorlatilag lehetetlen kiszámítani az ANF-értéket a kimenet összes bitjére egy teljes titkosításhoz. De a kulcs méretének 128 bitről 32 bitre való csökkentése lehetővé teszi a 32 logikai kimeneti függvény megtanulását egy 32 bites kulcs függvényében.

A Rabbit titkosítás lecsupaszított változatánál a beállítási funkciót különböző számú iterációra vizsgáltuk. Az ANF 0, 1, 2, 3, 4 iteráció és egy további iteráció után kerül meghatározásra a kinyerési sémában. 0+1 iteráció esetén a monomok száma körülbelül 2^31 volt, amint az a véletlen függvénynél várható volt. De két iteráció után az eredmény stabilizálódott. Ez azt jelenti, hogy nincs több ingadozás a kimenetben. A hiányzó polinomok száma rendre 0, 1, 2, 3, 1 iterációban (0+1), ..., (4+1). Nyilvánvaló, hogy ezek az adatok megfelelnek a véletlen függvények eredményeinek.

Korrelációs támadások

Lineáris közelítés

A lineáris támadás magában foglalja a legjobb lineáris közelítés megtalálását a következő állapotfüggvény bemenetén lévő bitek és az extrakciós áramkör kimenetén lévő bitek között. Ehhez használja a Walsh-Hadamard transzformációt , feltételezve, hogy minden bemeneti adat lineárisan független. Megállapítást nyert, hogy a legjobb lineáris korrelációnak van egy korrelációs együtthatója , ami azt jelenti, hogy az iterációkból kimenetet kell generálni egy véletlen függvénnyel való összehasonlításhoz.

Másodrendű közelítés

Az ANF levágása a második rend feletti tagok g-függvényére nagyban javítja a közelítést megfelelő feltételek mellett.

Jelölje az ANF másodrendű közelítésével . A kísérleti eredmények szerint a és közötti korrelációs együttható kisebb, mint , a és közötti korrelációs együttható pedig megközelítőleg egyenlő . Ez azt jelenti, hogy néhány magasabb fokú tag levágásra kerül, amikor a modulo 2-t hozzáadjuk két szomszédos bithez. Ezekre az adatokra építve egy másodrendű közelítésű titkosítás a legjobb esetben is egy korrelációs korrelációs együtthatót ad . A korrelációs együtthatónak ez az értéke nem elegendő egy támadáshoz. Ha a számlálókat is figyelembe vesszük, akkor az elemzés sokkal bonyolultabb. https://vk.com/tibber

Jegyzetek

  1. M. Boesgaard, M. Vesterager, T. Pedersen, J. Christiansen, O. Scavenius. Rabbit: A nagy teljesítményű adatfolyam titkosítás. Proc. FSE 2003. Springer LNCS 2887, pp. 307-329 ( PDF )
  2. M. Boesgaard, T. Pedersen, M. Vesterager, E. Zenner. A Rabbit Stream Cipher – Tervezési és biztonsági elemzés. Proc. SASC 2004. ( PDF archiválva : 2011. május 17. a Wayback Machine -nél )
  3. Phorum :: ECRYPT fórum :: A Rabbit közkinccsé válik . Letöltve: 2010. december 18. Az eredetiből archiválva : 2009. június 30.
  4. Az eSTREAM portfólió Steve Babbage, Christophe De Canni`ere, Anne Canteaut, Carlos Cid, Henri Gilbert, Thomas Johansson, Matthew Parker, Bart Preneel, Vincent Rijmen és Matthew Robshaw6 ( PDF archiválva 2012. augusztus 13. a Wayback Machine -nél )
  5. Christophe De Cannière, Joseph Lano és Bart Preneel , "Comments on the Rediscovery of Time Memory Data Tradeoffs", 2005. ( PDF archivált 2015. július 6-án a Wayback Machine -nél )

Linkek