Sok tervező azt állította, hogy a kriptográfiai sémájuk 80 bites biztonsággal rendelkezik. Tehát hogyan lehet kiszámolni ennek a 80 bites biztonsági kriptográfiai sémának, például a 80 bites biztonsági RSA-nak egyfajta CPU használatával történő letöltés idejét?
Megjegyzések
- 80 bites RSA egy pillanat alatt megtörhető, pl GMP-ECM . Az RSA faktorizációs rekordokkal kapcsolatos információkért lásd: ezt . A 80 bites biztonságról a ezt találja. A kulcs méretének kiválasztásához lásd: ezt .
- Köszönjük válaszát. Most 128 bites biztonságot veszek fel. Azt szeretném kérdezni, hogy a 128 bites biztonság 2 ^ 128 alapműveletet jelent e séma megtámadásához. Ez igaz？ És az alapművelet általános szorzást vagy összeadást jelent? És hogyan lehet kiszámítani a séma támadásának konkrét idejét? 2 ^ 128 megsokszorozza az általános szorzás vagy összeadás idejét?
- á, szóval a kérdésed: mit jelent a $ n $ -bit biztonság? ' próbálok Q / A-t találni ezzel kapcsolatban. Dióhéjban: ez azt jelenti, hogy $ 2 ^ n $ lépésekre van szükség a rendszer megszakításához, ahol a " lépés " lazán meg van határozva. A szimmetrikus titkosítás esetében általában " annyi munka, mint egy titkosítás vagy hash ". Az aszimmetrikus kriptográfia elméleti munkáihoz " lépés " általában " egy csoport ( vagy mező) művelet vagy egy hash ". Az RSA esetében ez lehet 1 moduláris szorzási mod N (a nyilvános kulcs) vagy 1 hash. De a gyakorlatban a $ n $ -bit biztonságot gyakran használják: annyi (számítógépes) munka, mint egy szimmetrikus rejtjel megszakítása $ n $ -bit biztonsággal.
- Kérdés merült fel a 64 bites bizonytalanság . Az olyan szuperszámítógépek, mint a Summit, egy év alatt elérhetik a 2 ^ {72} $ -t. Azonban egy olyan dedikált csoport, mint a Bitcoin-bányászok, egy év alatt elérheti a $ 2 ^ {92} $ -ot, így a 80 bites nem biztonságosabb. Ha elérhető többcélú támadás, még az AES-128 sem biztonságos az összes célpont számára, lásd itt és Mi a többcélú támadás? és itt Teljesen megszakadt az AES-128?
- @fgrieu Köszönjük válaszát. Azt is szeretném tudni, hogy a 2 ^ {128} óraciklusnak tekinthető-e? Mint látom, a futási idő óraciklusokkal is mérhető.
Válasz
A kérdés nagyrészt felborul. :
Mit jelent a $ n $ -bit biztonság a gyakorlatban egy adott értékhez $ n $ ?
TL; DR: olyan biztonságos, mint egy jó szimmetrikus rejtjel egy $ n $ -bit kulcs.
Nincs még egy pontosabb definíció, még akkor sem, ha a klasszikusan használt támadókra korlátozódunk számítógépek (nem kvantumszámítógépek), mint ez a válasz.
Az egyik általánosan elfogadott jelentés az, hogy a rendszer megszakításához szükséges „lépések” száma . $ 2 ^ n $ ; pontosabban az, hogy annak valószínűsége, hogy $ s $ “lépésekkel” megtörik a rendszert, nem ismert, hogy nagyobb, mint $ s \, 2 ^ {- n} $ bármilyen módszerrel a következőhöz: bármely $ s $ . A “lépések” és a “törés” azonban nincsenek pontosan meghatározva.
A szimmetrikus titkosítás elméletében a “lépést” általában a titkosítás egy végrehajtásával hajtják végre egy új kulccsal. Így egy ideális rejtjel, amelynek kulcsa $ n $ bit, $ n $ bites biztonsággal rendelkezik, nyers erő alatt kulcskutatás. Amikor gyakorlásra lépünk, a támadók nem kötelesek nyers erővel keresni a kulcsot, és a “lépés” meghatározásának számos olyan al-lépésnek kell lennie, amely számban és számítási költségben összehasonlítható az egyikhez szükséges al-lépésekkel a rejtjel végrehajtása egy új kulccsal, a kulcs méretének sima szövegért . Ezzel a definícióval egy $ n $ bit kulcsú praktikus rejtjel legfeljebb $ n $ – bites biztonság, és arra az ideálra törekszik.
Ha áttérünk a hashokra, akkor egy lépés meghatározása számos olyan részlépéssé válhat, amely számában és számítási költségében összehasonlítható a szükséges részlépésekkel új hash-kimenet méretű hash hoz.
A fentiek egyik problémája az, hogy nincs egyetértés abban, hogy számolnunk kell-e a memória és a memória-hozzáférések költségeit. a számítási költségben. A felhasználó szempontjából nem biztos, hogy megszámolja, de ez kiemelkedő fontosságú lehet egy támadó számára.
A “lépések” meghatározása még homályosabbá válik, amikor aszimmetrikus kriptográfiáról van szó. mint az RSA.Elméletileg a “lépések” egy számítást jelenthetnek a kriptorendszerhez használt algebrai struktúrában; mint például az RSA esetében a moduláris szorzás egy értékelése $ (a, b) \ mapsto a \, b \ bmod N $ tetszőleges egész számra $ a $ és $ b $ a $ [0, N) $ -ban , ahol a $ N $ a nyilvános modulus. De vannak problémák ennek átültetése a gyakorlatba, különösen az RSA esetében: a legismertebb támadás a nyilvános modulus $ N $ tényezőjének figyelembe vétele a GNFS algoritmus, amelynek számítási költségeit a moduláris szorzással kevéssé hasonlító műveletek uralják, a gyakorlati költségeket pedig a memória és a memóriához való hozzáférés uralja. Ez visszaadja a felhasználást a TL homályos meghatározásához; DR.
hogyan lehet kiszámítani ennek a 80 bites biztonsági kriptográfiai sémának a támadásának idejét, mint pl. A 80 bites biztonsági RSA egyfajta CPU-t használ?
A “80 bites biztonsági RSA” nem 80 bites nyilvános RSA-ként értendő. modulus $ N $ , amely véglegesen nem biztonságos. Ha a $ N $ méretünk lenne, akkor a korábbi tapasztalatok alapján megbecsülhetnénk a nehézséget (lásd ezt és linkjei). De nem tesszük, és nincs egyetértés a $ N $ méretével kapcsolatban a 80 bites biztonsági RSA esetében: gyakran hivatkoznak 1024 bitesre, de a hipotézistől függően , és kit kérdez, ez durván túl sok vagy kevés. Ezért a legjobb az, ha figyelmen kívül hagyjuk, hogy az RSA-ról beszélünk, és térjünk vissza: annyi időre van szükség, hogy egy jó szimmetrikus rejtjelet megszakítsunk egy 80 kulcs.
Ez a következőket eredményezi: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {CPU-k száma}} $$ ahol $ n $ a biztonsági szint bitekben, $ k $ a CPU-ciklusok számának becslése a jó rejtjel kiértékeléséhez egy ultraoptimalizált algoritmus és $ p $ használatával az ellenfél sikerének fennmaradó valószínűsége. A perspektívától függően vehetünk $ k = 1 $ -ot (ami menti az adatok vizsgálatát), $ k = 32 $ (mert ez még mindig kevesebb, mint az általános célú számítógépet használó jó rejtjelek elleni legjobb támadásoknál), vagy még sok más. A perspektívától függően vehetünk $ p = 1 $ -ot (legapróbb a jogos felhasználó szemszögéből), $ p = 1/2 $ (blokk titkosítás esetén megkapja a várható időt), vagy egy kisebb $ p $ , ha biztonsági tartalékot akarunk¹.
Például $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ kb2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {CPU-k száma} = 1000 \ kb2 ^ {10} $ , $ \ text {Time} \ kb2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , ez körülbelül 8 év. Más szóval, az 1000 CPU-nknak csak nagyon kicsi a valószínűsége a sikernek a 80 bites szimmetrikus titkosítással szemben, amíg azok technikailag elavulnak.
Másrészt az 1000 CPU a töredéke világszerte működő processzorok és a bitcoin bányászat meggyőzően azt mutatja, hogy a 80 bites kriptográfia már nem elegendő az ellenfelekkel szemben, akik képesek ASIC-eket megtervezni, hatalmas mennyiségben megépíteni és fenntartani működésük energiaköltségeit; lásd ezt .
¹ A $ p $ kifejezés itt: a képlet a legmegfelelőbb egy jogos felhasználó szempontjából, de a $ \ text {Time} $ alábecsülését okozza sok támadási forgatókönyv esetén. Például ütközéses keresés, a helyes kifejezés inkább hasonlít a $ \ sqrt p $ kifejezésre.