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] .
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 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 |
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.
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.
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.
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
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.
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.
A kulcs telepítése három szakaszra osztható: kulcsbővítés, iterációs rendszer, számláló módosítása.
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] .
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ásA 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ásA 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.
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ástEnnek 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:
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.
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áshozGyakorlatilag 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.
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ésAz 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
Szimmetrikus titkosítási rendszerek | |
---|---|
Rejtjelfolyam adatfolyam | |
Feistel hálózat | |
SP hálózat | |
Egyéb |