NetworkShop 2004 2004. április 7.
Kriptográfiai algoritmus implementációk időalapú támadása Endrődi Csilla, Csorba Kristóf BME MIT
Bevezetés Ma használt algoritmusok matematikailag alaposan teszteltek
Implementációs sajátosságok kihasználhatóak támadásra Implementáció-függő támadások: végrehajtási idő, EM sugárzás, hődisszipáció, áramfelvétel stb. Idő alapú támadás Kocher módszere (elméleti módszer több algoritmusra), 1996 UCL Crypto Group módszere (RSA törés), 2000 Új modell: RSA implementáció logikai idő alapú támadása
NetworkShop 2004.
2.
Idő alapú támadás Titkos kulccsal való műveletvégzés végrehajtási ideje függ a kulcs értékétől Bizonyos esetekben a mért idők alapján következtetni lehet a titkos kulcs értékére Szükséges az algoritmus részletes ismerete Passzív lehallgatás elegendő a működéséhez Titkos kulcs
Kérdés Eltelt idő
Implementáció
Válasz
NetworkShop 2004.
3.
Idő alapú támadás RSA ellen RSA algoritmus Kulcsgenerálás:
p, q prímek; m = p*q Φ(m) = (p-1) * (q-1) e tetszőleges: 1 ≤ e ≤ Φ(m); (e, Φ(m)) = 1 d * e = 1 mod Φ(m) Nyilvános kulcs: (e, m) Titkos kulcs: (d, m) ! x < m; Kódoló függvény: E(x) = xe mod m; Dekódoló függvény: D(y) = yd mod m
NetworkShop 2004.
4.
Idő alapú támadás RSA ellen RSA algoritmus Modulo m hatványozás Titkos kulcs használata dekódolásnál, aláírásnál Moduláris hatványozás: gyorshatványozó algoritmussal
NetworkShop 2004.
4.
Idő alapú támadás RSA ellen RSA algoritmus Modulo m hatványozás Titkos kulcs használata dekódolásnál, aláírásnál Moduláris hatványozás: gyorshatványozó algoritmussal
Kocher módszere MSB → LSB gyorshatványozás alkalmazásakor Minden lépésben egy kulcsbitet fejt meg
t
{Ti}
Sok megfigyelés kell hozzá Statisztikai alapokon hoz döntést Elméleti jelentőségű módszer Gyakorlatban kevésbé kivitelezhető NetworkShop 2004.
{t1,i} Xi t
{Ti} {t1,i} Xi
4.
Idő alapú támadás RSA ellen UCL Crypto Group módszere
MSB → LSB gyorshatványozás alkalmazásakor Moduláris szorzás: Montgomery algoritmussal Gyakorlati jelentőségű módszer CASCADE smart card esetében
Erdmények: 512 bites kulcs törése percek alatt, 300 ezer megfigyelés alapján 128 bites kulcs törése másodpercek alatt 10 ezer megfigyeléssel Két változat: A szorzás támadása A négyzetreemelés támadása Hibajavító tulajdonság Statisztikai alapon hoz döntést NetworkShop 2004.
5.
Idő alapú támadás RSA ellen A szorzás támadása MSB → LSB gyorshatványozás x13 = x8 * x4 * x = ((((((x)2)*x)2)2)*x)
Montgomery algoritmus -Redukciós lépés
ytemp := x; for (i = 0; i <= m; i++) { if (di == 1) ytemp := (ytemp * x) mod m; ytemp := (ytemp * ytemp) mod m; } return ytemp ;
d első i-1 bitjét, és az üzenetek aktuális értékét ismerjük Tf.: di = 1. Van Ekkor: redukció
X1
TX1
X Nincs redukció NetworkShop 2004.
? > TX2
X2 6.
Új megközelítés Mennyire veszélyes ez az RSA-ra?
Cél: Pontosan definiált keretek közötti általánosítás „Tiszta” modell, a támadás sikerességi feltételének formalizálása A módszer hatékonyságának javítása
Megkötés az algoritmusra - Sok algoritmus ilyen
Előfeldolgozás
Ciklus
if Θ(di, x) then
A
- Gyorshatványozó algoritmusok
B
Utómunkálat
NetworkShop 2004.
7.
Új megközelítés Újdonságok 1. Logikai idők alkalmazása Az utasítások költségértékekkel való ellátása Zajmentes összegzés Tetszőleges implementáció szimulálása Hangolás szükséges! 2. „One Step” mérésének lehetősége Az egyes iterációk végrehajtási idejének pontos ismerete Az előző adatok felhasználhatósága
x1 x2
xN x
3. Konstans számú kulcsjelölt Az exponenciális kulcstér robbanás elkerülése Téves döntés megengedett néhány lépésben Jelöltek száma meghatározza a törés sikerét NetworkShop 2004.
8.
Új megközelítés Megvalósítás Jelenleg: OpenSSL, RSA Kriptográfiai algoritmus cserélhető Szelekciós eljárás: különböző jósági tényezők lehetősége
Továbbfejlesztés
Zaj bevezetése a modellbe További jelöltszelekciós eljárások vizsgálata Még általánosabb kriptográfiai algoritmusok vizsgálata Protokollok vizsgálata (pl. SSL)
NetworkShop 2004.
9.
Összefoglalás Nem minden alkalmazás veszélyeztetett Már van gyakorlatban sikeresen megvalósított támadás – UCL Crypto Group (smart card), 2000. – Stanford University (OpenSSL), 2003.
Lehet ellene védekezni – Vannak algoritmusok a védelemre – Már beépített lehetőségek (pl. OpenSSL: blinding) – Sokszor nem használják őket!
NetworkShop 2004.
10.
Köszönjük a figyelmet!
