Sicurezza SHA256: cosa significa che gli attacchi hanno interrotto "46 dei 60 round di SHA256"?

30

Rapporti su Wikipedia

Currently, the best public attacks break 46 of the 64 rounds of SHA-256 or 46 of the 80 rounds of SHA-512.

Che cosa significa questo e quanto è sicuro che SHA-256 si aspetti nel futuro immaginabile? Per un laico, 46 su 64 potrebbe sembrare di "72% di danni". Poichè Bitcoin si basa su SHA-256, è probabile che rimarrà sicuro?

    
posta 10.04.2013 - 01:14
fonte

2 risposte

32

Molti algoritmi crittografici (funzioni di hash, crittografia simmetrica ...) sono organizzati come una sequenza di "round", che sono più o meno simili tra loro. È stato empiricamente notato che per una data struttura dell'algoritmo, di solito , più round implicano più sicurezza; precisamente, alcune classi di attacchi (es. differenziale e crittoanalisi lineare ) vedono la loro diminuzione di efficienza più o meno esponenziale con il numero di round.

Quando i crittografi non sanno come rompere un algoritmo completo, cercano di infrangere versioni ridotte dello stesso algoritmo, con alcune funzionalità rimosse; in particolare meno tondi, per algoritmi che hanno round. Quando si dice che lo SHA-256 è rotto "fino a 46 round", significa che un'altra funzione di hash, ottenuta prendendo SHA-256 ma rimuovendo gli ultimi 18 round, può essere attaccata (almeno in un "modo accademico": l'attacco non deve essere realistico, deve solo essere meno impossibile di attaccare l'intera funzione); ma rimuovere solo gli ultimi 17 round dà una funzione che, per quanto ne sappiamo, è buona come la cosa completa. I crittografi si sentiranno più sicuri se il numero massimo di round attaccati è sostanzialmente inferiore al numero effettivo di round nell'algoritmo completo.

Poiché il comportamento di efficienza degli attacchi tende ad essere esponenziale nel numero di round, non lineare, questo non può (e non deve) essere tradotto, anche intuitivamente, in: "può rompere l'80% del round - > algoritmo rotto a 80 %". Analogia: supponi di voler aumentare la tua fortuna, raddoppiandola dieci volte. Inizi con un dollaro; dopo dieci raddoppiamenti, avresti 1024 dollari; questo è il tuo obiettivo. Dopo i otto raddoppiamenti, hai 256 dollari. Otto raddoppiamenti su dieci: questo è l'80% del lavoro, giusto? Allora come mai hai solo 256 dollari e non l'80% di 1024 dollari (che sarebbero 819,2 dollari)?

Per riassumere , non dovresti cercare di leggere troppo in queste asserzioni. Sono risultati scientifici che sono interessanti per gli scienziati, ma che possono essere facilmente sovrasprettati.

    
risposta data 12.04.2013 - 17:16
fonte
8

In primo luogo, per indirizzare la parte "72%":

No. Sono più o meno allo stesso livello di sicurezza.

Diamo un'occhiata a un'altra citazione su sulla pagina :

There are two meet-in-the-middle preimage attacks against SHA-2 with a reduced number of rounds. The first one attacks 41-round SHA-256 out of 64 rounds with time complexity of 2253.5 and space complexity of 216, and 46-round SHA-512 out of 80 rounds with time 2511.5 and space 23. The second one attacks 42-round SHA-256 with time complexity of 2251.7 and space complexity of 212, and 42-round SHA-512 with time 2502 and space 222.

SHA-256 ha una complessità temporale di 2 256 da incrinarsi normalmente. Ridurlo a 2 253,5 è una differenza trascurabile, e occorrerebbero secoli di tali cambiamenti prima di riuscire a far scattare lo SHA.

Informazioni sui "round":

SHA-256 e SHA-512 sono fondamentalmente una funzione particolare (con costanti differenti per i due algoritmi) applicate ripetutamente su un numero. Ogni volta che lo si applica, viene chiamato "round". Ciò che questi ricercatori sembrano aver fatto è prendere gli algoritmi SHA per un numero ridotto di round e crack che .

    
risposta data 12.04.2013 - 17:18
fonte

Leggi altre domande sui tag