Secousses cryptographiques

[jtz]

Veille sécu

Le CNRS annonce avoir fait des percées dans la résolution des logarithmes discrets, ce qui pourrait mettre à mal certains algos utilisés en cryptographie.

Ce résultat, publié sur le site de l'International association of cryptologic research et sur l'archive ouverte HAL sera présenté lors de la conférence internationale Eurocrypt 2014 qui se tiendra à Copenhague du 11 au 15 mai 2014 et publié dans Advances in cryptology. [...]

La sécurité d'une variante du logarithme discret, réputé très difficile, a été battue en brèche par quatre chercheurs du CNRS, d'Inria et du Laboratoire d'informatique de Paris 6 (CNRS/UPMC) : Pierrick Gaudry, Răzvan Bărbulescu, Emmanuel Thomé et Antoine Joux (3).  [...]

Ces travaux sont encore à un stade théorique et l'algorithme doit encore être affiné avant de pouvoir fournir une démonstration pratique de la faiblesse de cette variante du logarithme discret. Néanmoins, ces résultats ouvrent une faille dans la sécurité cryptographique et la voie à d'autres recherches. En effet, il pourrait être adapté afin de tester la solidité d'autres solutions cryptographiques.

Source : http://www2.cnrs.fr/presse/communique/3543.htm

Comme chacun sait, ECDSA (donc BTC) est un algo discret qui compte deux méthodes de résolution publiées et documentées : Baby-step giant-step et L'algo de rho Pollard.

On aimerait bien savoir de quelle variante il s'agit.

[Meuh6879]

ils feraient mieux de faire du folding@home plutôt que du mining ...  (ton supra ironique, hein ... les chercheurs, c'est des gens assez sincères et humbles).

[davout]

Watching.

[jtz]

Il semblerait que leur découverte affecte bien la résolution d'ECDSA et permet sensiblement de réduire la complexité d'origine de L(1/3) à L(1/4+ε)  pour une courbe sur un corps F_q^k.

Je suppute de l'abstract,  n'ayant pas accès à l'article complet.

The difficulty of computing discrete logarithms in fields  F_q^k depends on the relative sizes of k and q. Until recently all the cases had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In 2013, Joux designed a new algorithm with a complexity of L(1/4 + ε) in small characteristic. In the same spirit, we propose in this article another heuristic algorithm that provides a quasi-polynomial complexity when q is of size at most comparable with k. By quasi-polynomial, we mean a runtime of n O(logn) where n is the bit-size of the input. For larger values of q that stay below the limit Lqk(1/3) , our algorithm loses its quasi-polynomial nature, but still surpasses the Function Field Sieve. Complexity results in this article rely on heuristics which have been checked experimentally.

Source : http://link.springer.com/chapter/10.1007/978-3-642-55220-5_1#page-1

[binaryFate]

https://anonfiles.com/file/1031ce8965409e0b80117e30a50b3a58 

[bitcoin.fr]

Emmanuel Thomé, un des 4 chercheurs impliqués dans ce travail, m'a confirmé que cela n'impactait en aucune façon ECDSA.

Jluc

[jtz]

Vous a t'il donné des détails ? Je suppose [à vérfiier] que BTC utilise des courbes recommandées par le NIST ou autre, or on prend des courbes sur des corps différents et en général il y a toujours quelques courbes sur le corps F_q^k qui me semble être le corps impacté par le papier, justement.

[junetwo]

Au final, c'est craignos pour le Bitcoin ou pas ?