Mnoho návrhářů tvrdilo, že jejich kryptografické schéma má 80bitové zabezpečení. Jak tedy vypočítat čas sledování tohoto 80bitového bezpečnostního kryptografického schématu, například 80bitového bezpečnostního RSA pomocí jakési CPU?
Komentáře
- 80bitový RSA je rozbitný v mrknutí, např GMP-ECM . Informace o záznamech faktorizace RSA najdete toto . Informace o 80bitovém zabezpečení najdete toto . Volbu velikosti klíče naleznete toto .
- Děkujeme za odpověď. Jako příklad si vezmu 128bitové zabezpečení. Chci se zeptat, že 128bitové zabezpečení znamená 2 ^ 128 základní operace k útoku na toto schéma. Je to pravda？ A znamená základní operace obecné násobení nebo sčítání? A jak vypočítat konkrétní čas útoku na toto schéma? 2 ^ 128 znásobuje čas provádění obecného násobení nebo sčítání?
- ach, takže vaše otázka zní: co znamená zabezpečení $ n $ -bit. ' Snažím se najít Q / A o tom. Stručně řečeno: znamená to, že k rozbití systému je zapotřebí $ 2 ^ n $ kroků, kde je volně definován " krok ". U symetrického kryptoměny to obvykle " funguje stejně jako jedno šifrování nebo hash ". Pro teoretické práce na asymetrických kryptoměnách má " krok " " jednu skupinu ( nebo pole) operace nebo jeden hash ". Pro RSA to může být 1 modulární multiplikační mod N (veřejného klíče) nebo 1 hash. V praxi se ale často používá zabezpečení $ n $ -bit pro: tolik (počítače) funguje jako rozbití symetrické šifry se zabezpečením $ n $ -bit.
- Došlo k otázce o 64bitová nejistota . Superpočítače jako Summit mohou za rok dosáhnout 2 $ {72} $. Specializovaná skupina, jako jsou bitcoinoví horníci, však může za rok dosáhnout $ 2 ^ {92} $, takže 80bitová verze již není bezpečnější. Pokud je k dispozici vícecílový útok, dokonce ani AES-128 není zabezpečený pro všechny cíle, podívejte se zde a Co je to vícecílový útok? a zde Byla AES-128 zcela porušena?
- @fgrieu Děkujeme za odpověď. Také bych chtěl vědět, že lze 2 ^ {128} považovat za hodinové cykly? Jak vidím, čas běhu lze měřit také hodinovými cykly.
Odpověď
Otázka se z velké části zmenšuje to:
Co v praxi znamená $ n $ -bit zabezpečení pro danou hodnotu z $ n $ ?
TL; DR: stejně bezpečné jako dobrá symetrická šifra s $ n $ -bitový klíč.
Neexistuje jediná přesnější definice, i když se omezíme na útočníky používající klasické počítače (spíše než kvantové počítače), jak to dělá tato odpověď.
Jedním z obecně přijímaných významů je, že se předpokládá, že počet „kroků“ k rozbití systému je $ 2 ^ n $ ; přesněji řečeno, není známo, že pravděpodobnost rozbití systému pomocí $ s $ „steps“ je více než $ s \, 2 ^ {- n} $ libovolnou metodou pro jakýkoli $ s $ . „Kroky“ a „přerušení“ však nejsou přesně definovány.
V teorii symetrického šifrování se „krok“ obvykle považuje za jedno provedení šifry s novým klíčem. Tímto způsobem má ideální šifra s klíčem $ n $ bitů zabezpečení $ n $ -bit, při hledání klíče hrubou silou. Když přejdeme k procvičování, útočníci nejsou povinni hledat klíčové slovo hrubou silou a definice „kroku“ se musí stát množstvím dílčích kroků srovnatelných počtem a výpočetními náklady s dílčími kroky požadovanými pro jeden provedení šifry s novým klíčem pro prostý text o velikosti klíče . S touto definicí má praktická šifra s klíčem $ n $ bitů maximálně $ n $ – bitová bezpečnost a zaměřuje se na tento ideál.
Když přejdeme k hašování, definice kroku by se mohla stát řadou dílčích kroků srovnatelných počtem a výpočetními náklady s požadovanými dílčími kroky pro hašování nové zprávy o velikosti hash výstupu .
Jedním z mnoha problémů s výše uvedeným je, že neexistuje dohoda o tom, zda bychom měli počítat nebo ne náklady na paměť a přístupy do paměti ve výpočetních nákladech. Bezpečné z pohledu uživatele není spočítat to, ale to může mít pro útočníka zásadní význam.
Definice „kroků“ se stává ještě temnější, pokud jde o asymetrickou kryptografii jako RSA.Teoreticky mohou být „kroky“ jedním výpočtem v algebraické struktuře používané pro kryptosystém; jako pro RSA jedno vyhodnocení modulárního násobení $ (a, b) \ mapsto a \, b \ bmod N $ pro libovolné celé číslo $ a $ a $ b $ v $ [0, N) $ , kde $ N $ je veřejný modul. Existují však problémy s přesunem do praxe, zejména u RSA: nejznámějším útokem je ovlivnění veřejného modulu $ N $ pomocí GNFS , kterému výpočetním nákladům dominují operace, které mají malou podobnost s modulárním násobením, a praktickým nákladům dominuje paměť a přístupy do paměti. Což dává zpět použití nejasné definice v TL; DR.
jak vypočítat čas útoku na toto 80bitové bezpečnostní kryptografické schéma, jako například 80bitové zabezpečení RSA využívající jakýsi procesor?
„80bitové zabezpečení RSA“ nelze chápat jako RSA s 80bitovým veřejným modul $ N $ , který je terminálně nezabezpečený. Pokud bychom měli velikost $ N $ , mohli bychom odhadnout obtížnost na základě této a předchozí zkušenosti (viz toto a jeho odkazy). Ale my ne, a neexistuje shoda ohledně velikosti $ N $ pro RSA s 80-bitovým zabezpečením: často se uvádí 1024-bit, ale v závislosti na hypotéze „a koho se ptáte, to je hrubě příliš mnoho nebo příliš málo. Proto je nejlepší ignorovat, že mluvíme o RSA, a vrátit se k: tolik času, kolik je potřeba k rozbití dobré symetrické šifry s 80bitovým klíč.
Což nás přivádí k: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ , kde $ n $ je úroveň zabezpečení v bitech, $ k $ je odhad počtu cyklů CPU k vyhodnocení dobré šifry pomocí ultraoptimalizovaného algoritmu a $ p $ je zbytková pravděpodobnost úspěchu protivníka. V závislosti na perspektivě můžeme použít $ k = 1 $ (což šetří zkoumání podrobností), $ k = 32 $ (protože to je stále méně než u nejlepších útoků na dobré šifry pomocí univerzálního počítače) nebo mnohem více. V závislosti na perspektivě můžeme vzít $ p = 1 $ (nejrozumnější z pohledu legitimního uživatele), $ p = 1/2 $ (získá se očekávaný čas v případě blokové šifry), nebo menší $ p $ , pokud chceme bezpečnostní rezervu¹.
Například s $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ cca2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ cca2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1 000 \ cca2 ^ {10} $ , dostaneme $ \ text {Time} \ cca2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , to je asi 8 let. Jinými slovy, našich 1000 procesorů má jen velmi malou pravděpodobnost úspěchu proti 80bitovému symetrickému krypto, dokud nebudou technicky zastaralé.
a druhou stranu, 1000 CPU je malý zlomek celosvětové CPU a těžba bitcoinů přesvědčivě ukazují, že 80bitové krypto již nestačí proti protivníkům se schopnostmi navrhovat ASIC, budovat je v obrovských množstvích a udržovat energetické náklady na jejich provoz; viz toto .
¹ Termín $ p $ v vzorec je z hlediska legitimního uživatele nejobezřetnější, ale způsobí, že $ \ text {Time} $ je v mnoha scénářích útoku podceňován. Například v vyhledávání kolizí, správný výraz by vypadal spíše jako $ \ sqrt p $ .