Qual è il modello matematico dietro le affermazioni sulla sicurezza dei cifrari simmetrici e degli algoritmi di digest?

Non posso darti una risposta che ti lascerà perfettamente soddisfatto, perché non esiste una risposta del genere. Come sappiamo che i nostri algoritmi sono sicuri? A rigor di termini, non lo facciamo. Non abbiamo alcuna prova che SHA256, o AES, o RSA siano sicuri: è ampiamente creduto che siano sicuri, ma non potrei darti una prova matematica di questo fatto, e chissà, è sempre possibile che le convinzioni diffuse siano sbagliata.

La nostra convinzione nella sicurezza di questi algoritmi deriva dal fatto che molte persone davvero intelligenti e ben informate hanno provato davvero molto a rompere questi algoritmi, senza incidere in alcun modo. Naturalmente, non è una garanzia che non esista alcun attacco intelligente: è sempre possibile che ci sia un attacco di scorciatoia matematico incredibilmente subdolo che nessuno è stato abbastanza intelligente da trovare, ma più persone cercano di trovarne uno e falliscono, meno probabile che sembri. A fini pratici, sembra improbabile che un attaccante di varietà da giardino scoprirà un attacco che decine di persone davvero intelligenti hanno cercato di trovare e fallito.

La tua reazione immediata potrebbe essere, che diamine? Perché quei crittografi sono così zotici? Perché non riescono a provare nessuno dei loro algoritmi sicuri? Sono numbskulls? La risposta è, ci sono ragioni fondamentali che rendono molto difficile dimostrare che un algoritmo di crittografia o una funzione di hash è sicuro (tranne in casi speciali). In parole povere, dimostrare che un algoritmo come AES o RSA o SHA256 è sicuro sembra essere almeno altrettanto difficile come prova che P ! = NP (un problema infamemente difficile in informatica). Abbiamo pochissimi strumenti per dimostrare che un compito algoritmico può non essere completato in modo efficiente. Al suo interno, questo è ciò che rende difficile dimostrare che SAT non può essere risolto in tempo polinomiale (cioè, difficile da provare che P ! = NP ), e rende difficile dimostrare che non esiste un attacco di scorciatoia su AES (cioè che AES non può essere rotto). Quindi non è solo che i crittografi sono zoppi, è che ci troviamo di fronte a problemi molto difficili che nessuno sa come progredire.

Si noti che nulla di ciò che ho detto sopra è specifico delle funzioni di hash o della crittografia a chiave simmetrica. Si applica a tutti i sistemi di crittografia computazionale, tra cui la crittografia a chiave simmetrica, la crittografia a chiave pubblica, le firme digitali, le funzioni di hash e molte altre primitive standard che diamo per scontate.

La tua ultima domanda è stata: qualcuno può insegnarmi la teoria di come gli algoritmi a chiave simmetrica vengono analizzati e crittografati? Come li analizzano i crittografi? Come funzionano gli attacchi? No, non posso insegnarti questo entro i limiti di tempo e spazio qui. C'è un intero campo di ricerca costruito attorno a queste domande, con una letteratura intellettualmente profonda sulle tecniche per l'analisi degli algoritmi a chiave simmetrica. (Vedi, ad es., Le conferenze FSE , CRYPTO e EUROCRYPT . Ci vogliono anni di studio dedicato per imparare questo materiale. Sfortunatamente, non posso insegnarti tutto ciò nello spazio disponibile qui. La versione molto breve è: i crittografi hanno sviluppato una vasta suite di tecniche di attacco e, come punto di partenza, ogni nuovo primitivo viene analizzato per vedere se uno di questi attacchi funzionerà. Se il primitivo resiste a tutte le tecniche di attacco conosciute, allora i crittografi passano il tempo cercando di progettare attacchi ad-hoc o personalizzati contro la primitiva. I crittografi studiano anche versioni indebolite artificialmente del primitivo (ad esempio, con meno colpi), per conoscere i migliori attacchi a quelle versioni indebolite nel tentativo di estrapolare il tutto. Se dopo molti anni di sforzi, nessuno ha successo nell'attaccare lo schema, allora la gente inizia a guadagnare più sicurezza. Più di recente, c'è stata anche qualche ricerca per ottenere la certezza che la struttura di alto livello sia solida, o che tutti gli attacchi di una determinata classe abbiano esito negativo, usando le idee della comunità di sicurezza dimostrabile.

Ma alla fine della giornata, è un'arte tanto quanto una scienza. La valutazione di una nuova primitiva è estremamente costosa : richiede decenni di sforzi da parte di specialisti di talento intenso. Per questo motivo, gli utenti intelligenti della crittografia in genere cercano di utilizzare i primitivi esistenti e controllati, piuttosto che inventarne di propri. Se inventi il tuo schema, è estremamente improbabile che tu possa essere in grado di organizzare l'analisi e il controllo del tuo schema come quelli standard già ricevuti, quindi non farlo. Non "tira il tuo". Piuttosto, costruisci su primitive esistenti, standard, accettate, come AES, SHA256, RSA, ecc.

@ D.W. lo dice bene; in parole più brevi: l'unico modo per ritenere un algoritmo crittografico è di avere centinaia di crittografi che lo rodono per alcuni anni. Questo non è in definitiva soddisfacente, intellettualmente parlando, ma si può ancora lavorare con quello (l'intera Medicina, per esempio, è costruita su basi ancora più scialbe, ma è comunque un'arte molto utile).

Per le specifiche (vale a dire come viene scelta una S-box, cos'è "l'effetto valanga", come studiare le cose con l'algebra ...), vedi (come sempre) il Handbook of Applied Cryptography , che inizia ad essere un po 'vecchio ma comunque un ottimo riferimento e può essere scaricato gratuitamente. Un altro buon libro è Cryptanalysis algoritmico di Antoine Joux.

One of my questions still remains unresolved. I still don't know why XOR, bit shifting and the like are used for hashes and ciphers in the first place - if there is any mathematical reasoning behind this, why it's exactly these operations and nothing else?

Uno dei motivi per cui si usa esattamente XOR è perché XOR ha una proprietà importante: la reversibilità. Se esegui XOR un numero con un tasto e poi XOR il risultato con lo stesso tasto, otterrai il tuo numero originale.