L'apprentissage automatique peut-il décoder les hachages SHA256?

43

J'ai un hachage SHA256 de 64 caractères.

J'espère former un modèle capable de prédire si le texte en clair utilisé pour générer le hachage commence par un 1 ou non.

Peu importe si cela est "possible", quel algorithme serait la meilleure approche?

Mes premières pensées

  • Générez un grand échantillon de hachages commençant par 1 et un grand échantillon de hachage ne commençant pas par 1
  • Définissez chacun des 64 caractères d'un hachage en tant que paramètre pour une sorte de modèle de régression logistique non supervisé.
  • Entraînez le modèle en lui disant quand il a raison / tort.
  • Espérons pouvoir créer un modèle capable de prédire si le texte en clair commence par un 1 ou non avec une précision suffisante (et avec un kappa décent)
John
la source
22
FYI: Ceci est probablement motivé par l'exploitation minière de Bitcoin.
ClojureMostly
55
"Comment pourrais-je entraîner un modèle qui me permette de voyager dans le temps, que cela soit" possible "?"
Konrad Rudolph
13
@Joshua OP veut inverser SHA-256. Je le laisserai publier même si cela prend mille fois plus de pas que SHA-256. Je vais également cesser d'exister car la solution exploite presque certainement un bogue dans le tissu même de la réalité pour déjouer la logique.
Konrad Rudolph
15
Tous les hachages SHA256 peuvent être générés par une chaîne commençant par "1".
Reactgular le
8
@cgTag Je suis désolé mais c'est tout simplement faux. L'entrée contrôle la sortie, sinon ce ne serait pas une fonction en premier lieu. De plus, le fait que vous ayez une liste infinie d'éléments ne signifie pas que l'un d'eux commence par 1. Vous essayez de prouver une conjecture de cryptographie connue dans un commentaire SE. Note: Je crois aussi que c'est vrai, mais prétendre que c'est vrai est trompeur. Si vous avez raison, il y aura sûrement un papier ou une autre référence.
Pedro Un

Réponses:

98

Ce n'est pas vraiment une réponse statistique, mais:

Non , vous ne pouvez pas déterminer le premier caractère du texte en clair à partir du hachage, car "le texte en clair" n'existe pas pour un hachage donné.

SHA-256 est un algorithme de hachage. Quel que soit votre texte en clair, vous obtenez une signature de 32 octets, souvent exprimée sous forme de chaîne hexagonale de 64 caractères. Il y a beaucoup plus de textes en clair possibles qu'il y a de chaînes hexadécimales de 64 caractères possibles - le même hachage peut être généré à partir de n'importe quel nombre de textes en clair différents. Il n'y a aucune raison de croire que le premier caractère qui soit / ne soit pas un '1' soit uniforme pour tous les textes en clair produisant un hachage donné.

Chris H
la source
21
C’est à ce jour (à mon avis) la seule réponse correcte. Toutes les autres réponses semblent porter davantage sur le problème de l'apprentissage de la fonction de hachage que sur celui d'inverser le hachage (la vraie question). Ils semblent tous ignorer que le hachage n’est pas une fonction injective.
Luca Citi
7
Ne pourriez-vous pas prédire la probabilité que le premier caractère soit un? L’absence de relations individuelles n’est pas un problème rare dans l’apprentissage statistique.
Matthew Drury
16
@MatthewDrury Etant donné que SHA256 est conçu pour rendre toutes les entrées également probables pour un hachage donné, il est à espérer qu'il y aura une infinité d'intrants commençant par 1, pour tout hachage donné . Donc, si vous voulez estimer la probabilité, votre meilleure estimation sera approximativement . 1256±ε
Konrad Rudolph
12
Ouais, d'accord. Je voulais juste noter que le manque d'injectivité n'est pas vraiment un problème structurel avec l'application de l'apprentissage automatique.
Matthew Drury
6
@IMil La raison pour laquelle j'ai mentionné le fait qu'il s'agisse d'une fonction de hachage n'est pas de suggérer qu'aucune fonction de hachage ne pourrait jamais révéler cette information, mais pour motiver l'affirmation qu'il n'existe pas de "texte en clair". Bien sûr, une (mauvaise) fonction de hachage pourrait être partiellement réversible et nous indiquer clairement quelque chose à propos de l'ensemble des textes en clair qui la produirait, mais il n'y a aucune raison de croire celle de SHA-256.
Chris H
51

SHA256 étant conçu pour être aussi aléatoire que possible, il est donc peu probable que vous puissiez séparer les hachages provenant de texte en clair avec un préfixe unique de ceux qui ne le sont pas; il ne devrait tout simplement pas y avoir de caractéristique de la chaîne de hachage qui donnerait cette information.

Pavel Komarov
la source
5
"peu probable" et "devrait" - C'est ce que l'algorithme me dira. À première vue, cela semble impossible, mais je voudrais savoir quel algorithme et quelle approche adopter pour tester cette hypothèse.
John
24
+1 Il est garanti que tout type de "modèle de régression logistique non supervisé" sera incapable de faire mieux que de deviner, à moins de pouvoir fournir un nombre de cas vraiment astronomique. Ce problème pèse sur les moulins à vent.
whuber
44
Vous pouvez l'essayer, mais l'apprenant tentera de trouver une relation statistique conçue intentionnellement pour ne pas exister.
Pavel Komarov
32
"Conçu pour être aussi aléatoire que possible" est un euphémisme. Spécifiquement, la conception vise à avoir une dépendance non linéaire maximale, où chaque bit d'entrée influence environ 50% des bits de sortie et chaque bit de sortie dépend d'environ 50% des bits d'entrée. Ceci est connu sous le nom de confusion et de diffusion . Cela rend la tâche ici (récupérer le premier bit) aussi difficile que de récupérer le message dans son ensemble.
MSalters
12
Je pense que vous pouvez renforcer "peu probable" dans cette réponse. Le PO n'a aucune chance d'appliquer des techniques basées sur des statistiques pour prédire toute partie d'un hachage SHA256 à partir du contenu, ou vice-versa, avec même une amélioration détectable par rapport à une estimation aléatoire. La solution pratique consiste essentiellement à pré-calculer la totalité de la population cible de contenu d'origine.
Neil Slater
43

Peu importe si cela est "possible", quel algorithme serait la meilleure approche?

Désolé, mais c'est une question absurde. Si quelque chose est impossible, vous ne pouvez pas rechercher la meilleure approche du problème.

Dans ce cas, cela devrait être impossible, car le hachage est une fonction à sens unique: plusieurs entrées (infinies, en fait) peuvent produire la même sortie. Si le premier bit seul influait de quelque façon sur la probabilité d'une valeur de hachage spécifique, cela signifierait que l'algorithme de hachage est complètement imparfait.

Vous pouvez certainement former un réseau de neurones, un classifieur linéaire, un SVM et ainsi de suite pour tenter une prédiction. Et si vous êtes capable de prédire de manière fiable l’entrée de la sortie pour un certain algorithme de hachage, cela prouvera que cet algorithme est sans valeur. Je dirais que pour un algorithme largement utilisé tel que SHA256, une telle possibilité est extrêmement faible. Cependant, il est raisonnable d’exclure rapidement de nouveaux algorithmes de hachage non éprouvés et non testés.

IMil
la source
6
sign(x)
11
@ KonradRudolph: "Fonction à sens unique" a une signification spécifique dans ce contexte qui n'est pas la signification à laquelle vous pensez. sign(x)n'est pas une fonction à sens unique dans ce sens, car trouver des images préalables est trivial.
user2357112 prend en charge Monica le
4
Cela dit, je ne pense pas que la réponse utilise correctement la "fonction unidirectionnelle".
user2357112 prend en charge Monica le
1
@ user2357112 Merci, je ne le savais pas. Je ne connaissais que le sens en tant que fonction surjective mais non bijective. C'est aussi la définition donnée dans la réponse, ce à quoi je m'étais opposé.
Konrad Rudolph
1
Oui, désolé, je suis un peu laxiste avec les définitions. Cependant, je pense qu’un sens unique est plus compréhensible pour les novices que les termes plus stricts.
IMil
26

Alors que l'on ne peut pas prouver un négatif avec un exemple. Je pense néanmoins qu'un exemple serait suggestif; et peut-être utile. Et cela montre comment on pourrait (tenter de) résoudre des problèmes similaires.

Dans le cas où je veux faire des prédictions binaires, en utilisant des fonctionnalités qui sont des vecteurs binaires , une forêt aléatoire est un choix judicieux. Je suppose que cela répond à la deuxième partie de votre question: qu'est-ce qu'un bon algorithme?

Nous voulons bien pré-traiter les chaînes SHA256, en vecteurs binaires (booléens), chaque bit étant statistiquement indépendant, chaque bit est donc une bonne fonctionnalité. Cela fera donc de nos entrées 256 vecteurs booléens.

Démo

Voici une démonstration de la façon dont tout cela peut être réalisé à l'aide de la bibliothèque Julia DecisionTree.jl .

Vous pouvez copier coller le ci-dessous dans l'invite de julia.

using SHA
using DecisionTree
using Statistics: mean
using Random: randstring

const maxlen=10_000 # longest string (document) to be hashed.

gen_plaintext(x) = gen_plaintext(Val{x}())
gen_plaintext(::Val{true}) = "1" * randstring(rand(0:maxlen-1))
gen_plaintext(::Val{false}) = randstring(rand(1:maxlen))


bitvector(x) = BitVector(digits(x, base=2, pad=8sizeof(x)))
bitvector(x::AbstractVector) = reduce(vcat, bitvector.(x))

function gen_observation(class)
    plaintext = gen_plaintext(class)
    obs = bitvector(sha256(plaintext))
    obs
end

function feature_mat(obs)
    convert(Array, reduce(hcat, obs)')
end

########################################

const train_labels = rand(Bool, 100_000)
const train_obs = gen_observation.(train_labels)
const train_feature_mat = feature_mat(train_obs)

const test_labels = rand(Bool, 100_000)
const test_obs = gen_observation.(test_labels)
const test_feature_mat = feature_mat(test_obs)


# Train the model
const model = build_forest(train_labels, train_feature_mat)
@show model


#Training Set accuracy:
@show mean(apply_forest(model, train_feature_mat) .== train_labels)

#Test Set accuracy:
@show mean(apply_forest(model, test_feature_mat) .== test_labels)

Résultats

Lorsque j’ai fait cela, je me suis entraîné sur 100 000 chaînes ASCII aléatoires d’une longueur maximale de 10 000. Voici les résultats que j'ai vus:

Former le modèle

julia> const model = build_forest(train_labels, train_feature_mat)
Ensemble of Decision Trees
Trees:      10
Avg Leaves: 16124.7
Avg Depth:  17.9

Précision d'ensemble d'entraînement:

julia> mean(apply_forest(model, train_feature_mat) .== train_labels)
0.95162

Précision de l'ensemble de test:

julia> mean(apply_forest(model, test_feature_mat) .== test_labels)
0.5016

Discussion

Donc, ce n'est fondamentalement rien. Nous sommes passés de 95% sur l'ensemble de formation, à un peu plus de 50% sur l'ensemble de test. Quelqu'un pourrait appliquer des tests d'hypothèses appropriés pour voir si nous pouvons rejeter l'
hypothèse nulle , mais je suis à peu près certain que nous ne le pouvons pas. C'est une infime amélioration par rapport au taux approximatif.

Cela suggère que cela ne peut pas être appris. Si vous êtes une forêt aléatoire, vous pourrez passer de bien aménagé à un taux approximatif. Les forêts aléatoires sont assez capables d'apprendre des intrants difficiles. S'il y avait quelque chose à apprendre, je m'attendrais à au moins quelques pour cent.

Vous pouvez jouer avec différentes fonctions de hachage en changeant le code. Ce qui pourrait être intéressant, j’ai obtenu les mêmes résultats lors de l’utilisation de la hashfonction intégrée de julia (ce qui n’est pas une hsah sécurisée du point de vue cryptographique, mais qui reste un bon hachage, il est donc conseillé d’envoyer des chaînes similaires). J'ai aussi obtenu essentiellement les mêmes résultats pour CRC32c.

Lyndon White
la source
15

Les fonctions de hachage sont (de par leur conception) extrêmement mal adaptées à la réalisation de tout apprentissage automatique.

ML est essentiellement une famille de méthodes de modélisation / estimation de fonctions localement continues . En d’autres termes, vous essayez de décrire un système physique qui, bien qu’il puisse comporter certaines discontinuités, est assez lisse dans l’espace des paramètres pour que seul un échantillon dispersé de données de test puisse être utilisé pour prédire le résultat pour d’autres. contribution. Pour ce faire, les algorithmes d'intelligence artificielle doivent en quelque sorte décomposer les données en une représentation de base intelligente, pour laquelle la formation a suggéré que, par exemple, si vous voyez telle forme (qui semble correspondre au résultat de telle ou telle convolution), une bonne chance que la sortie ait dans la région correspondante telle ou telle structure (qui peut encore être décrite par une convolution ou quelque chose).

(Je sais, beaucoup d’approches ML ne ressemblent pas du tout à de la convolution, mais l’idée générale est toujours la même: vous avez un espace d’entrée tellement dimensionnel qu’il est impossible de faire un échantillonnage exhaustif, de sorte que vous trouvez une décomposition intelligente qui vous permet d’extrapoler. les résultats d'un échantillon relativement rare.)

L'idée derrière une fonction de hachage cryptographique est cependant que toute modification du texte en clair devrait résulter en un condensé complètement différent. Ainsi, quelle que soit la manière dont vous décomposez la fonction, les estimateurs locaux ne vous permettront pas d'extrapoler l'influence des petites fluctuations autour de cette partie sur le résultat. À moins bien sûr que vous ne traitiez réellement toutes les informations d'un ensemble limité, mais cela ne s'appellerait pas l'apprentissage automatique: vous construiriez simplement une table arc-en-ciel .

à gauche autour de
la source
4
En lisant cela, je me suis rendu compte que a) pour construire une table arc-en-ciel, vous devez savoir quelle fonction de hachage utiliser, et b) il serait peut- être possible à un algorithme d'apprentissage automatique d'identifier quel algorithme est utilisé, avec un échantillon d'entrées et de sorties (au moins si l'algorithme a des défauts identifiables). Donc, si le problème initial était reformulé pour concerner une fonction de hachage inconnue qu’il fallait identifier, il serait peut-être plus intéressant.
Senderle
7

C'est une question intéressante car elle soulève des questions sur ce qui est considéré comme un "apprentissage automatique". Il existe certainement un algorithme qui finira par résoudre ce problème s'il peut être résolu. Ça va comme ça:

  1. Choisissez votre langage de programmation préféré et choisissez un codage qui mappe chaque chaîne à un entier (potentiellement très volumineux).

  2. Choisissez un nombre aléatoire et convertissez-le en chaîne. Vérifiez si c'est un programme valide dans votre langue. Si ce n'est pas le cas, choisissez un autre numéro et réessayez. Si c'est le cas, démarrez-le, mettez-le immédiatement en pause et ajoutez-le à une liste de programmes en pause.

  3. Exécutez tous les programmes en pause pendant un petit moment. Si l'un d'entre eux s'arrête sans produire de solution adéquate, supprimez-le de la liste. Si l'on produit une solution adéquate, vous avez terminé! Sinon, revenez à 2 après les avoir tous laissés courir un peu.

Il ne fait aucun doute que si vous avez un stockage infini et une durée infinie, l'algorithme ci-dessus trouvera éventuellement une bonne solution. Mais ce n'est probablement pas ce que vous entendez par "apprentissage automatique".

Voici le hic: si vous considérez tous les problèmes possibles, aucun algorithme d'apprentissage automatique ne peut faire mieux en moyenne! Ceci est connu sous le nom de théorème de non-déjeuner gratuit . Cela prouve que parmi tous les problèmes que l’on peut poser à n’importe quel algorithme d’apprentissage automatique, le nombre qu’il peut résoudre rapidement est infime.

Il ne peut résoudre ces problèmes rapidement que parce qu'ils sont régis par des modèles que l'algorithme peut anticiper. Par exemple, de nombreux algorithmes réussis supposent ce qui suit:

  1. Les solutions peuvent être décrites par des séries complexes de multiplications matricielles et de distorsions non linéaires, régies par un ensemble de paramètres.

  2. Les bonnes solutions seront regroupées dans l’espace des paramètres, de sorte que tout ce que vous aurez à faire sera de choisir un quartier de recherche, de trouver la meilleure solution, de déplacer votre quartier de recherche afin que la meilleure solution soit au centre, puis de répéter.

De toute évidence, aucune de ces hypothèses n’est valable en général. La seconde est particulièrement suspecte. Et le déjeuner gratuit nous dit que ces hypothèses ne tiennent même pas la plupart du temps. En fait, ils ne tiennent presque jamais! C'est notre chance qu'ils tiennent pour certains problèmes qui comptent vraiment.

Le problème que vous avez choisi est conçu dès le début pour enfreindre l'hypothèse 2. Les fonctions de hachage sont spécifiquement conçues pour que des entrées similaires produisent des sorties complètement différentes.

Votre question - quel est le meilleur algorithme d’apprentissage automatique pour résoudre ce problème? - a probablement une réponse très simple: la recherche aléatoire.

senderle
la source
Je me demande comment l'informatique quantique affectera le théorème du «sans déjeuner gratuit». Vraisemblablement, l'informatique quantique est également contrainte.
Max Vernon
1
@ MaxVernon oh, intéressant. Je m'attendrais à ce que tous les algorithmes quantiques aient la même propriété par rapport à d' autres algorithmes quantiques . Je ne sais pas si tous les algorithmes d'optimisation quantique ont une vitesse de traitement moyenne par rapport à ceux classiques. Ils pourraient! J'ai une question et une réponse personnelle qui parle d'un théorème du «repas gratuit» qui pourrait être pertinent. (tldr; le déjeuner n'est gratuit que si vous ignorez une partie du travail effectué ... mais je me demande si cela change dans le cas quantique.)
Senderle
5

C'est presque impossible. Cependant, les gens ont observé dans SHA256 des tendances qui pourraient suggérer que celui-ci ne se différencie pas de façon aléatoire en utilisant Bitcoin (extraction plus rapide en cours de route) . Leur tldr:

"Pour faire la distinction entre un hachage de permutation aléatoire idéal et SHA256, hachez une grande quantité (~ 2 ^ 80) de blocs de 1024 bits candidats, comme dans Bitcoin. Assurez-vous que les bits des blocs candidats sont peu définis (beaucoup moins que le 512 moyenne attendue), selon le protocole Bitcoin, rejetant les blocs candidats qui ne répondent pas à la norme de «difficulté» de Bitcoin (où les hachages résultants commencent par un grand nombre de 0), avec le reste des candidats valides en entrée (467369 cette analyse a été effectuée), observez un ensemble particulier de 32 bits dans le bloc d'entrée (situé là où Bitcoin possède le nonce, bits d'entrée 607-639). Notez que le nombre moyen de bits défini dans le champ nonce est décalé à gauche, c'est-à-dire moins que la valeur attendue de l'ensemble de 16 bits (moyenne estimée à 15,428). "

Voir une discussion sur lobste.rs . Une explication possible est un biais introduit par les mineurs.

IndieSolver
la source
2
C'est intéressant. Mais la réponse sur lobste.rs est probablement juste. C'est un biais énorme, facilement découvrable. La notion qu'il est passé inaperçu pendant si longtemps est assez tirée par les cheveux.
Senderle
1
@senderle Afin d'exploiter le biais (le cas échéant), il convient de concevoir un algorithme (essentiellement un algorithme ML / d'optimisation) qui est peu coûteux du point de vue du calcul, de sorte que ses propres coûts indirects sont implémentés / mesurés sur du matériel de pointe. est compensé par l'accélération qu'il fournit. Mon hypothèse la plus approximative serait que le facteur en termes de #chachtrials devrait être supérieur à 10x pour battre la force brute et ses implémentations suroptimisées. Les implications pourraient être très graves, en particulier pour les personnes qui misent sur les protocoles de cryptographie et de sécurité.
IndieSolver
4

Je vais répondre avec un programme. Pour réduire les besoins en calcul, je vais utiliser une variante de sha256 que j'appelle sha16, qui n'est que les 16 premiers bits de sha256.

#!/usr/bin/python3

import hashlib
from itertools import count

def sha16(plaintext):
    h = hashlib.sha256()
    h.update(plaintext)
    return h.hexdigest()[:4]

def has_plaintext_start_with_1(digest):
    """Return True if and only if the given digest can be generated from a
    plaintext starting with "1" first bit."""
    return True

def plaintext_starting_with_1(digest):
    """Return a plaintext starting with '1' matching the given digest."""
    for c in count():
        plaintext = (b'\x80' + str(c).encode('ascii'))
        d = sha16(plaintext)
        if d == digest:
            return plaintext

for digest in range(0x10000):
    digest = "%04x" % (digest,)
    plain = plaintext_starting_with_1(digest)
    print("%s hashes to %s" % (plain, digest))

Ceci produit la sortie:

b'\x8094207' hashes to 0000
b'\x8047770' hashes to 0001
b'\x8078597' hashes to 0002
b'\x8025129' hashes to 0003
b'\x8055307' hashes to 0004
b'\x80120019' hashes to 0005
b'\x8062700' hashes to 0006
b'\x8036411' hashes to 0007
b'\x80135953' hashes to 0008
b'\x8044091' hashes to 0009
b'\x808968' hashes to 000a
b'\x8039318' hashes to 000b
[...]

Je laisserai la preuve complète comme un exercice pour le lecteur, mais prenez-moi au mot: il y a une entrée qui commence par un "1" pour chaque résumé possible de 0000 à ffff.

Il y a aussi une entrée qui ne commence pas par "1". Et il y en a un qui commence par les œuvres complètes de Shakespeare.

Ceci est valable pour toute fonction de hachage raisonnablement bonne, bien que ma preuve de force brute puisse devenir infaisable en calcul.

Phil Frost
la source
En mathématiques, je n'aime pas croire sur parole . Votre programme démontre que votre fonction sha16 est surjective, mais rien de plus. Vous n'avez pas prouvé formellement que ce programme pouvait prouver la fonction SHA-256 réelle. Selon votre style de conclusion, la conjecture de Collatz serait résolue car elle est déjà résolue pour 32 bits et le programme peut facilement être exécuté plus longtemps.
Roland Illig
4

Ce que vous décrivez est fondamentalement une attaque de pré-image. Vous essayez de trouver une entrée telle que, lorsqu'elle est hachée, la sortie ait une propriété comme "un 1 en tête". *

Les hachages cryptographiques ont pour objectif explicite d'empêcher de telles attaques par pré-image. Si vous pouvez faire une telle attaque, nous avons tendance à considérer cet algorithme comme peu sûr et à ne plus l'utiliser.

Ainsi, bien que cela signifie que ce ne soit pas impossible, cela signifie également que votre algorithme d’apprentissage automatique devrait déjouer une fraction importante des mathématiciens du monde et de leurs super-ordinateurs. Il est peu probable que vous le fassiez.

Cependant, si vous le faisiez, vous seriez reconnu comme quelqu'un qui aurait violé un algorithme de hachage cryptographique majeur. Cette célébrité vaut quelque chose!

* Techniquement, une "première attaque de pré-image" tente de trouver une correspondance pour un hachage spécifique. Cependant, pour montrer qu'un algorithme de hachage a la première résistance à l'attaque avant l'image, ils indiquent généralement que vous ne pouvez trouver aucune information significative sur l'entrée du hachage.

Cort Ammon
la source
2

La plupart des réponses ici vous disent pourquoi vous ne pouvez pas faire cela, mais voici la réponse directe à:

Peu importe si cela est "possible", quel algorithme serait la meilleure approche?

En supposant que l'entrée est suffisamment grande:

  1. Prendre le compte de l'ensemble des caractères valides.
  2. Prenez l'inverse du nombre de l'étape 1.

C'est la probabilité que la chaîne d'entrée commence par '1'. Vous n'avez même pas besoin de regarder l'entrée. Si vous pouvez faire mieux que cela, cela signifierait que le hachage est très cassé. Vous pouvez économiser beaucoup de cycles de traitement en essayant de former un algorithme pour choisir des nombres aléatoires.

Vous pourriez former un algorithme et il pourrait donner une réponse différente à cause d'un surajustement. C'est à moins que quelque chose ne va vraiment pas avec l'algorithme de hachage. L'utilisation de cet algorithme se trompe alors plus souvent que si vous choisissez simplement une valeur aléatoire.

JimmyJames
la source
1

Les fonctions de hachage sont délibérément conçues pour être difficiles à modéliser, donc (comme nous l'avons déjà souligné), cela risque d'être très difficile. Néanmoins, toute faiblesse de la fonction de hachage réduira son entropie, la rendant plus prévisible.

Peu importe si cela est "possible", quel algorithme serait la meilleure approche?

Un exemple utile est la fonction physiquement non clonable , ou PUF, analogue à une fonction de hachage matérielle. Généralement, les variantes de fabrication sont utilisées à dessein pour donner à chaque PUF une réponse légèrement différente, de sorte que leur sortie "hachée" soit différente pour une entrée donnée. Cependant, les faiblesses de conception limitent l'entropie et, avec suffisamment de paires défi-réponse, il est souvent possible de construire un modèle de type boîte noire de la PUF afin de pouvoir prédire la réponse à un nouveau défi jamais vu auparavant.

La régression logistique est l'approche la plus couramment utilisée pour ces attaques de modélisation, comme dans cet article de Rührmair .

Les algorithmes génétiques (ou plus généralement les stratégies évolutives) peuvent constituer une approche alternative, dans la mesure où ils s’appliquent à des problèmes qui ne sont pas différenciables et / ou séparables linéairement. Ils sont également discutés dans le document ci-dessus.

4Oh4
la source
1

251222562256

26402641

2256264(2256264)!

S=(2256264)
C=90100S
CSC

(1S1S11S2...1S(C1))(SC1SCSC2SC1SC3SC2...12)=(SC1)!S!

=(110(2256264)1)!(2256264)!
2(2263.99184665662260.6509677217)
210.13222373912260.6509677217

22562512

utilisateur96549
la source
1

Le problème est que "l'apprentissage automatique" n'est pas intelligent. Il essaie juste de trouver des modèles. Dans SHA-256, il n'y a pas de modèle. Il n'y a rien à trouver. L'apprentissage automatique n'a aucune chance meilleure que la force brute.

Si vous voulez déchiffrer SHA-256 par ordinateur, la seule possibilité est de créer une véritable intelligence, et comme de nombreux humains intelligents n'ont pas trouvé le moyen de créer SHA-256, vous devez créer une intelligence artificielle bien supérieure à celle de nombreux humains intelligents. À ce stade, nous ne savons pas si une telle intelligence surhumaine craquerait SHA-256, prouverait qu'elle ne peut pas être fissurée, ou déciderait qu'elle n'est pas assez intelligente pour faire l'une ou l'autre (comme les humains). La quatrième possibilité est bien sûr qu’une telle intelligence artificielle surhumaine ne se soucierait même pas de penser à des problèmes plus importants.

gnasher729
la source