[the lsd]

Hello guys (and girls)

Une interrogation s'est vu poindre en moi récemment à propos d'un cassage de sha1.
J'ai plusieurs sha1 dont je connais une partie en clair, et une autre partie que je peux deviner, quelque chose du genre :

sample 1 : en[5 caractères aléatoires][13 caractères que je peux deviner][10 caractères aléatoires]
sample 2 : fr[5 caractères aléatoires][13 caractères que je peux deviner][10 caractères aléatoires]
sample 3 : es[5 caractères aléatoires][13 caractères que je peux deviner][10 caractères aléatoires]

etc etc (je peux avoir beaucoup plus de samples)

Sachant que les 13 caractères du milieu ont une entropie faible, je peux les deviner (basés uniquement sur la date et l'heure), au mieux, j'arrive à récupérer la date/heure et du coup, je n'ai que les quelques derniers octets à trouver (parce que je n'aurais pas les secondes et millisecondes), au pire, j'en ai pour faire court la moitié (7 on va dire).

Puisque je connais une partie des caractères et que j'ai plusieurs samples différents, donc que j'ai une Choosen plaintext attack, y a-t-il un moyen de réduire le temps de brute force de façon significative, voire (ô joie, ô bonheur) de ne même plus avoir besoin de bruteforcer ?

Many thanks to all of you

Enjoy

The lsd

[vigenere]

Nope. Sinon les sha1 ne seraient pas ce qu'ils sont.

Si tu trouves un moyen, y'a de quoi ecrire un article universitaire et devenir celebre.

[the lsd]

Bon, ta réponse ne me plait pas, je l'ignore ^^

Nan plus sérieusement, je connais le principe d'un hash, qu'il n'est théoriquement pas possible de l'inverser, tout ça, mais dans la pratique, on sait très bien qu'il peut exister des attaques.
Par exemple, atom (le créateur de Hashcat) a récemment trouve une faiblesse dans le calcul permettant de réduire de 21% le temps d'attaques (en fait, il a réduit de 21% de nombre d'instructions pour le calcul, mais ça revient plus ou moins au même). En 2005, on a pu trouver des collisions sur des hash en sha1 en utilisant2⁶⁴ opérations (à la place des  2⁸⁰). Mettons qu'il soit possible de cumuler ces deux faiblesses (je n'en sais absolument rien hein, ça reste hypothétique), le temps de collision d'un  sha1 serait ridicule (comparé au temps initial).

Bon tout ça pour dire que ça n'est pas parce que sha1 n'est pas directement réversible qu'il n'existe pas d'attaques, et c'est pour cela que je pose la question

Enjoy

The lsd

[_o_]

C'est impossible tant que la fonction respective le principe d'avalanche, qui est essentiel dans le cas d'une fonction de hachage cryptographique. Pour rappel, ça signifie qu'un bit modifié dans le texte de départ doit conduire à une empreinte totalement différente de la précédente.

Les attaques dont tu parles n'ont rien à voir, puisqu'il s'agit d'une part de collisions et d'autre part d'optimisation d'une attaque par force brute (qui ne porte donc pas sur l'algorithme en lui-même). D'ailleurs, je ne sais pas pour SHA1, mais dans le cas de MD5, il n'est pas (encore ?) possible de générer une collision à volonté depuis n'importe quel hash.

Évidemment, cela ne signifie pas qu'il n'existe pas une attaque, mais je rejoins vigenere sur ce point : si tu la trouves, tu es célèbre. :-)

D'ailleurs, sans que SHA1 et SHA2 soient totalement cassés, les faiblesses apparues et l'inéluctable montée en puissance du matériel ont conduit le NIST à trouver un nouveau standard pour les remplacer. Le gagnant, Keccak, a été annoncé il y a quelques mois déjà.

[the lsd]

Bon, si je comprend bien, je n'ai plus qu'à bruteforcer et réduire le guessing, dommage

Je ne mettais pas en lien mes attaques dont je parlais avec ma question initiale, c'etait histoire de montrer qu'il existait des attaques et que sha1 n'était pas infaillible.

Pour les collisions, c'est pas que je mette ta parole en doute, mais tu es bien sur qu'il n'est pas possible de trouver une collision depuis n'importe quel hash ? D'après plusieurs sources (au hasard wiki, parce que c'est le premier résultat de ma recherche), un groupe de chercheurs a pu trouver une collision à partir d'un hash existant (pareil pour Flame et le certif MS). Ou alors j'ai mal compris, ce que est aussi fort possible.

Enjoy

The lsd

[Iansus]

Oui, il faut faire attention, trouver une collision, ou trouver une collision pour un hash donné sont 2 choses totalement différentes. Niveau complexité, le problème 1 est bien moins "complexe" que le 2.
Pour une fonction de hachage avec un output sur n bits, le problème 1 est en O(2^n/2), tandis que le second est en O(2ⁿ) (grâce au paradoxe des anniversaires).

La pour ton problème, comme dit _o_, c'est mis en déroute par le principe d'avalanche. Cependant, SHA1 est de moins en moins digne de confiance, comme le fut MD5 en son temps. Cet article explique comment de simples collisions sont apparues, ça n'est pas exclu que de la même manière on en trouve pour SHA1.

En revanche, j'étais pas au courant qu'ils avaient enfin trouver Mr SHA3, merci pour l'info