¿Puede el aprendizaje automático descifrar los hashes SHA256?

Question

Tengo un hash SHA256 de 64 caracteres.

Espero entrenar un modelo que pueda predecir si el texto plano utilizado para generar el hash comienza con un 1 o no.

Independientemente de que esto sea "posible", ¿qué algoritmo sería el mejor enfoque?

Mis pensamientos iniciales:

• Generar una gran muestra de hashes que empiecen por un 1 y una gran muestra de hashes que no empiecen por un 1
• Establezca cada uno de los 64 caracteres de un hash como un parámetro para algún tipo de modelo de regresión logística no supervisado.
• Entrenar el modelo diciéndole cuándo está bien/mal.
• Espero poder crear un modelo que pueda predecir si el texto plano comienza con un 1 o no con una precisión suficientemente alta (y con un kappa decente)

Answer 1

Esto no es realmente una respuesta de estadísticas, pero:

No No se puede determinar el primer carácter del texto plano a partir del hash, porque no existe "el texto plano" para un hash dado.

SHA-256 es un algoritmo de hash. Independientemente del texto plano, se obtiene una firma de 32 bytes, a menudo expresada como una cadena hexadecimal de 64 caracteres. Hay muchos más textos planos posibles que cadenas hexadecimales de 64 caracteres: se puede generar el mismo hash a partir de cualquier número de textos planos diferentes. No hay ninguna razón para creer que el primer carácter que es o no es un "1" sea uniforme en todos los textos planos que producen un hash determinado.

Answer 2

SHA256 está diseñado para ser lo más aleatorio posible, por lo que es poco probable que puedas separar los hashes que provienen de un texto plano con prefijo 1 de los que no; simplemente no debería haber ninguna característica de la cadena de hash que pudiera dar esa información.

Answer 3

Independientemente de que esto sea "posible", ¿qué algoritmo sería el mejor enfoque?

Lo siento, pero es una pregunta sin sentido. Si algo es imposible, entonces no se puede buscar el mejor enfoque para el problema.

En este caso, esto debería ser definitivamente imposible porque el hashing es una función unidireccional: varias entradas (infinitas, de hecho) pueden producir la misma salida. Si el primer bit de entrada influyera de alguna manera en la probabilidad de un valor hash específico, esto significaría que el algoritmo hash es completamente defectuoso.

Ciertamente, puedes entrenar una red neuronal, un clasificador lineal, una SVM y demás para intentar la predicción. Y si usted será capaz de predecir de forma fiable la entrada de la salida para un determinado algoritmo de hash, esto demostraría que este algoritmo no tiene valor. Yo diría que para un algoritmo ampliamente utilizado como SHA256, tal posibilidad es muy baja. Sin embargo, es un enfoque razonable para descartar rápidamente nuevos algoritmos de hashing no probados ni comprobados.

Answer 4

Aunque no se puede demostrar una negativa con un ejemplo. Aun así, creo que un ejemplo sería sugerente; y quizás útil. Y muestra cómo uno podría (intentar) resolver problemas similares.

En el caso de Quiero hacer predicciones binarias, utilizando características que son vectores binarios , un Bosque Aleatorio es una opción sólida. Supongo que esto responde a la segunda parte de tu pregunta: cuál es un buen algoritmo.

Bien queremos preprocesar las cadenas SHA256, en vectores binarios (booleanos), ya que cada bit es estadísticamente independiente, por lo que cada bit es una buena característica. Así que eso hará que nuestras entradas sean vectores booleanos de 256 elementos.

Demo

Aquí hay una demostración de cómo se puede hacer todo esto usando la Julia DecisionTree.jl biblioteca.

Puedes copiar y pegar lo siguiente en el prompt 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)

Resultados

Cuando hice esto, entrenando en 100.000 cadenas ASCII aleatorias de longitud hasta 10.000. Estos son los resultados que vi:

Entrenar el modelo

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

Precisión del conjunto de entrenamiento:

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

Precisión del conjunto de pruebas:

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

Discusión

Así que eso es básicamente nada. Pasamos del 95% en el conjunto de entrenamiento, a apenas más del 50% en el conjunto de prueba. Alguien podría aplicar pruebas de hipótesis adecuadas, para ver si podemos rechazar la nula
hipótesis, pero estoy bastante seguro de que no podemos. Es una pequeña mejora con respecto a la tasa de adivinación.

Eso sugiere que no se puede aprender. Si un Bosque Aleatorio, puede pasar de estar bien ajustado a acertar sólo la tasa de adivinación. Los Bosques Aleatorios son bastante capaces de aprender entradas difíciles. Si hubiera algo que aprender, esperaría al menos un porcentaje.

Puedes jugar con diferentes funciones hash cambiando el código. Lo que podría ser interesante Obtuve básicamente los mismos resultados al usar el julia in built hash (que no es un hsah criptográficamente seguro, pero sigue siendo un buen hash, por lo que debería separar cadenas similares). También obtuve básicamente los mismos resultados para CRC32c .

Answer 5

Las funciones Hash son (por su diseño) extremadamente inadecuadas para hacer algo de aprendizaje automático con ellas.

El ML es esencialmente una familia de métodos para modelar / estimar localmente continua funciones. Es decir, estás intentando describir algún sistema físico que, aunque puede tener ciertas discontinuidades, es en cierto sentido en la mayor parte del espacio de parámetros lo suficientemente suave como para que sólo una muestra dispersa de datos de prueba pueda utilizarse para predecir el resultado para otra entrada. Para ello, los algoritmos de IA necesitan descomponer de algún modo los datos en una representación de base inteligente, para lo cual el entrenamiento ha sugerido que, por ejemplo, si se ve tal y tal forma (que parece correlacionarse con el resultado de tal y tal convolución), entonces hay una buena probabilidad de que la salida deba tener en la región correspondiente tal y tal estructura (que puede describirse de nuevo mediante una convolución o algo así).

(Lo sé, muchos enfoques de ML no se parecen en absoluto a la convolución, pero la idea general es siempre la misma: se tiene un espacio de entrada que es tan alto dimensional que es imposible muestrear exhaustivamente, así que se encuentra una descomposición inteligente que permite extrapolar los resultados de una muestra comparativamente escasa).

Sin embargo, la idea detrás de una función hash criptográfica es que cualquier cambio en el texto plano debe dar lugar a un completamente diferente. Así que, independientemente de cómo se descomponga la función, los estimadores locales no permitirán extrapolar cómo influyen en el resultado las pequeñas fluctuaciones en torno a esa parte. A no ser, por supuesto, que se procese realmente todo de la información de un conjunto limitado, pero esto no se llamaría aprendizaje automático: sólo se estaría construyendo un mesa arco iris .