Sécurité 80 bits et temps dattaque

La question se résume en grande partie à:

Que signifie la sécurité $ n $ -bit en pratique pour une valeur donnée de $ n $ ?

TL; DR: aussi sûr quun bon chiffrement symétrique avec une clé $ n $ -bit.

Il ny a pas une seule définition plus précise, même si nous nous limitons aux attaquants utilisant le classique des ordinateurs (plutôt que des ordinateurs quantiques), comme le fait cette réponse.

Une signification généralement acceptée est que le nombre détapes pour briser le système est supposé être $ 2 ^ n $ ; ou plus précisément que la probabilité de casser le système avec $ s $ « étapes » nest pas connue pour être supérieure à $ s \, 2 ^ {- n} $ par nimporte quelle méthode pour tout $ s $ . Cependant, les « étapes » et « rupture » ne sont pas définies avec précision.

En théorie du chiffrement symétrique, « pas » est généralement considérée comme une exécution du chiffrement avec une nouvelle clé. De cette façon, un chiffrement idéal avec une clé de $ n $ bits a une sécurité de $ n $ -bit, sous la recherche de clé de force brute. Lorsque nous passons à la pratique, les attaquants ne sont pas liés à la recherche de clé par force brute, et la définition dune « étape » doit devenir un nombre de sous-étapes comparables en nombre et en coût de calcul aux sous-étapes requises pour une. exécution du chiffrement avec une nouvelle clé pour un texte en clair de la taille de la clé . Avec cette définition, un chiffrement pratique avec une clé de $ n $ bits a au plus $ n $ – Bit Security, et vise cet idéal.

Lorsque nous passons aux hachages, la définition dune étape pourrait devenir un nombre de sous-étapes comparables en nombre et en coût de calcul aux sous-étapes requises pour hacher un nouveau message de la taille de la sortie de hachage .

Lun des nombreux problèmes avec ce qui précède est quil ny a pas daccord sur le fait de compter ou non le coût des accès à la mémoire et à la mémoire dans le coût de calcul. La chose la plus sûre du point de vue dun utilisateur est de ne pas le compter, mais cela peut être dune importance capitale pour un attaquant.

La définition des « étapes » devient encore plus floue lorsquil sagit de cryptographie asymétrique comme RSA.En théorie, les « étapes » pourraient être un calcul dans la structure algébrique utilisée pour le cryptosystème; comme, pour RSA, une évaluation de la multiplication modulaire $ (a, b) \ mapsto a \, b \ bmod N $ pour un entier arbitraire $ a $ et $ b $ dans $ [0, N) $ , où $ N $ est le module public. Mais il y a des problèmes pour mettre cela en pratique, en particulier pour RSA: lattaque la plus connue est de factoriser le module public $ N $ en utilisant le GNFS , dont le coût de calcul est dominé par des opérations ayant peu de similitude avec la multiplication modulaire, et de coût pratique dominé par la mémoire et les accès à la mémoire. Ce qui remet en cause la définition vague du TL; DR.

comment calculer le temps dattaque de ce schéma de cryptographie de sécurité 80 bits, tel que RSA de sécurité 80 bits utilisant une sorte de CPU?

« RSA de sécurité 80 bits » ne doit pas être compris comme RSA avec un public 80 bits modulus $ N $ , qui est en fin de compte non sécurisé. Si nous avions la taille de $ N $ , nous pourrions estimer la difficulté sur la base de cette expérience et de lexpérience précédente (voir ceci et ses liens). Mais nous ne le faisons pas, et il ny a pas de consensus sur la taille de $ N $ pour RSA avec sécurité 80 bits: 1024 bits est souvent cité, mais selon lhypothèse , et à qui vous demandez, cest grossièrement trop ou pas assez. Ainsi, le mieux est dignorer que nous parlons de RSA, et de revenir à: autant de temps que nécessaire pour casser un bon chiffrement symétrique avec un 80 bits clé.

Ce qui nous amène à: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ où $ n $ est le niveau de sécurité en bits, $ k $ est une estimation du nombre de cycles CPU pour évaluer un bon chiffrement à laide dun algorithme ultra-optimisé, et $ p $ est la probabilité résiduelle de succès dun adversaire. Selon la perspective, nous pouvons prendre $ k = 1 $ (ce qui évite dexaminer les détails), $ k = 32 $ (car cest encore moins que dans les meilleures attaques contre de bons chiffrements utilisant un ordinateur généraliste), ou bien plus. Selon la perspective, nous pouvons prendre $ p = 1 $ (plus prudent du point de vue dun utilisateur légitime), $ p = 1/2 $ (donnant le temps attendu dans le cas dun chiffrement par bloc), ou un $ p $ plus petit si nous voulons une marge de sécurité¹.

Par exemple, avec $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , nous obtenons $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , soit environ 8 ans. En dautres termes, nos 1000 processeurs nont quune très faible probabilité de succès contre la crypto symétrique 80 bits, jusquà ce quils deviennent techniquement obsolètes.

Dun autre côté, 1000 processeurs représentent une infime fraction de les processeurs mondiaux et lextraction de bitcoins montrent de manière concluante que la cryptographie 80 bits ne suffit plus contre des adversaires capables de concevoir des ASIC, de les construire en quantités massives et de supporter les coûts énergétiques de leur fonctionnement; voir ceci .

¹ Le terme $ p $ dans la formule est la plus prudente du point de vue dun utilisateur légitime, mais elle entraîne la sous-estimation de $ \ text {Time} $ dans de nombreux scénarios dattaque. Par exemple, dans recherche de collision, le terme correct ressemblerait plus à $ \ sqrt p $ .