Può una rete neurale ritagliare algoritmi di hashing?

16

Ho letto un po 'di reti neurali e la loro capacità di approssimare molte funzioni complesse.

Una rete neurale non sarebbe in grado di crackare un algoritmo di hashing come SHA256?

Ad esempio, diciamo che vogliamo addestrare la nostra rete a crackare stringhe di 8 caratteri che sono state sottoposte a hash. Potremmo passare attraverso tutte le permutazioni e addestrare la rete poiché conosciamo gli input e le uscite previste. La rete sarebbe tecnicamente in grado di crackare una quantità relativamente buona di hash SHA256 che si associano a stringhe di 8 caratteri? È stato fatto in precedenza?

    
posta Omega 29.08.2016 - 07:32
fonte

6 risposte

31

No.

Le reti neurali sono combinazioni di pattern. Sono degli abbinamenti di pattern buoni , ma gli abbinamenti di pattern sono uguali. Non più avanzati dei cervelli biologici che intendono imitare. Più approfondito, più instancabile, ma non più sofisticato.

Gli schemi devono essere lì per essere trovati. Ci dev'essere un pregiudizio nei dati da prendere in giro. Ma gli hash crittografici sono esplicitamente ed estremamente attentamente progettati per eliminare qualsiasi pregiudizio nell'output. Nessun bit è più probabile di altri, non è più probabile che un output sia correlato a un dato input. Se tale correlazione fosse possibile, l'hash sarebbe considerato "rotto" e un nuovo algoritmo avrebbe preso il suo posto.

I difetti nelle funzioni di hash sono stati trovati prima , ma mai con l'aiuto di una rete neurale. Invece è stato con l'attenta applicazione di alcuni principi matematici.

    
risposta data 29.08.2016 - 08:07
fonte
8

AGGIORNAMENTO dato il tuo commento:

I know that it would be computationally unfeasible. I just wanted to know if it would be theoretically possible (it seems not according to tylerl)

Sì, dato il tempo infinito e l'energia infinita, una rete neurale potrebbe incrinare SHA256 . MA (e penso che questo sia il punto che sta facendo @tylerl) perché le funzioni di hash non hanno pattern discernibili, una rete neurale non sarebbe in grado di fare qualcosa di meglio dell'ingenua forza bruta di costruire una tabella di ricerca calcolando l'hash di ogni possibile stringa. Tale tabella di ricerca avrebbe più voci (~ 2 256 ) di quanti atomi sul pianeta terra (~ 2 166 ) - quindi almeno con il nostro livello attuale di tecnologia è "impossibile" tenere un tale tavolo in memoria o memorizzarlo su qualsiasi disco. Allo stesso modo, affinché la tua rete neurale abbia prestazioni sensibilmente migliori di un lancio di dadi, il numero di neuroni di cui avresti bisogno probabilmente supererebbe anche il numero di atomi del pianeta.

Quindi sì, è computazionalmente impossibile, ma ancora teoricamente possibile. In realtà è vero per la crittografia in generale che è sempre possibile per forza bruta in teoria, ma diciamo "abbastanza buono" quando possiamo dimostrare che così facendo richiederà più tempo della vita del universo e più energia di quella contenuta nel sole.

Penso che il contro-argomento sia in risposta a:

We could through all the permutations and train the network since we know the inputs and expected outputs.

1) Questo è fondamentalmente diverso da una tabella di ricerca?

2) SHA256 ha uno spazio di output di 2 256 e uno spazio di input che è essenzialmente infinito. Per riferimento, il tempo trascorso dal big bang è stimato in 5 miliardi di anni, che è di circa 1.577 x 10 27 nanosecondi, che è di circa 2 90 ns. Quindi, supponendo che ogni iterazione di addestramento richieda 1 ns, occorreranno 2 166 età dell'universo per addestrare la rete neurale.

Il punto qui è che SHA256 ha 2 256 possibili output, e 2 256 è davvero un gran numero veramente .

    
risposta data 29.08.2016 - 17:46
fonte
7

Da una diversa angolazione:
Potresti ridurlo al problema aperto "esiste un algoritmo efficiente per la scomposizione in fattori interi ". Se esiste un tale algoritmo, un NN potrebbe scoprirlo tramite ricerca di prove guidate , e questo potrebbe essere usato per minare tutta la sicurezza .

    
risposta data 03.10.2017 - 20:05
fonte
4

"Una rete neurale può diventare la 'funzione inversa' di una funzione hash?" Può essere. Non c'è alcuna prova matematica che una determinata funzione di hash, sia essa SHA o qualsiasi altra, manchi di schemi tra Dominio e Immagine. Come altri analisti hanno sottolineato, le funzioni di hash sono progettate esplicitamente in modo tale che non ci siano qualità preservate conosciute. Se esiste una sorta di schema, in teoria una rete neurale potrebbe trovarlo, ma sono sicuro che è stato provato prima e SHA esiste ancora, quindi possiamo supporre che non abbiano avuto successo. Potrei menzionare che dovresti provare questa 'mancanza di schema' per ciascuna funzione di hash individualmente.

Ho messo la "funzione inversa" tra virgolette perché le funzioni di hash devono essere suriettive (tuttavia la suriettività di solito non è formalmente dimostrata) e come tale può avere due numeri mappati sullo stesso numero, quindi non esiste una vera inversa. Tuttavia, la funzione inversa non deve essere una funzione vera, nel senso che può restituire un Set di numeri o una funzione che descrive un insieme di numeri. La funzione inversa di forza bruta di una funzione di hash restituirebbe semplicemente il dominio (ad esempio i numeri naturali) e una funzione inversa più sofisticata restituirebbe un sottoinsieme reale del dominio.

Questo sarebbe davvero interessante per addestrare una rete neurale su: L'NN restituisce una funzione come output. La funzione ha una certa densità all'interno dell'immagine che si potrebbe approssimare, minore è la densità, maggiore è la ricompensa. Ora per addestrare il NN, si inserirebbe f (x) e si verifica se x < - {g (c) | c < - | N} mentre g è la funzione che NN restituisce come output.

    
risposta data 11.08.2017 - 03:50
fonte
3

La rete neurale o qualsiasi altro algoritmo di apprendimento automatico non sono magici, anche se potrebbe sembrare così. Alla fine questi metodi sono solo un insieme di equazioni (vale a dire la matematica) per mappare l'input in output e l'apprendimento sta regolando i parametri per queste equazioni in modo che il risultato rifletta i dati di addestramento nel miglior modo possibile. In questo modo cerca di imparare la struttura intrinseca dei dati nella speranza che questa struttura sia la stessa anche per la maggior parte degli altri possibili input. O in sintesi: è solo matematica.

Se esistesse una struttura intrinseca che consenta una mappatura relativamente facile dal valore hash al valore originale o anche se ciò comportasse una riduzione significativa dello spazio di ricerca per rendere possibile la forza bruta, questo hash non sarebbe considerato un hash strong crittografico. E poiché non è necessario utilizzare una rete neurale o simili per indagare su tali problemi, sono abbastanza sicuro che ciò sia fatto e che le reti neurali non impongano nuovi pericoli.

    
risposta data 29.08.2016 - 08:01
fonte
3

No, Le reti neurali utilizzano fondamentalmente l'ottimizzazione del gradiente decente. Le reti neurali sono un'interessante famiglia di funzioni e in pratica riusciamo a ottimizzarle piuttosto bene nonostante non si tratti di un problema convesso.

Affinché una tale tecnica di ottimizzazione funzioni, abbiamo bisogno di una minima quantità di scorrevolezza, abbiamo bisogno di una nozione quasi corretta. Non abbiamo questo con funzioni hash crittografiche. Ci aspettiamo che un singolo bit capovolga la metà delle uscite, nella maggior parte dei casi abbiamo piccoli cambiamenti che portano a piccoli cambiamenti, non così nella crittografia. Questo è il motivo per cui le reti neurali possono imparare a invertire le primitive crittografiche.

    
risposta data 03.10.2017 - 21:18
fonte

Leggi altre domande sui tag