Good Mood

Questo è il primo post in 3 serie di nozioni di base di crittografia. La serie è descritta come segue:

1. Crittografia simmetrica
2. Integrità dei dati & Crittografia autenticata
3. Crittografia asimmetrica con coppie di chiavi pubbliche/private

Immergersi nel mondo dell’informatica può essere un compito arduo. Soprattutto da solo!, In questa serie di blog, mi piacerebbe offrire una panoramica di alto livello sulle basi della crittografia per coloro che cercano di approfondire ulteriormente l’argomento che non sanno necessariamente da dove cominciare. Questa panoramica si basa specificamente sui miei principali takeaway dal corso di crittografia I di Stanford come insegnato da Dan Boneh, disponibile su Coursera.

Ho deciso di seguire questo corso dato che sono uno sviluppatore blockchain che non proveniva da un background tradizionale di comp-sci. Ho studiato economia al college, ma virato più verso la programmazione di computer come ho iniziato la mia carriera., Da quando ho iniziato a codificare, sono stato in missione per avvicinarmi al computer — per staccare gli strati di astrazione che mi sono divertito come sviluppatore web e capire cosa sta succedendo sotto il cofano. La transizione in criptovaluta e sistemi distribuiti dallo sviluppo web è stato un passo selvaggio e meraviglioso in quella direzione in molti modi, non ultimo dei quali stava acquisendo maggiore familiarità con i concetti di crittografia. Tuttavia, volevo una base più solida., Dal momento che è un campo piuttosto vasto, ho pensato che valesse la pena di abbandonare 7 70 per consumare queste informazioni in un forum appositamente curato dalla Stanford University. Puoi anche controllare questo corso senza consegnare incarichi gratuitamente. Le meraviglie di internet!

Cominciamo.

Essenzialmente, la crittografia è la pratica della comunicazione sicura in presenza di potenziali avversari di terze parti. Il concetto di comunicazione sicura consiste in 2 punti principali:

1. Sicurezza contro le intercettazioni: ciò garantisce la riservatezza dei dati.,
2. Sicurezza contro la manipolazione dei dati: ciò garantisce l’integrità dei dati, il che significa che nessuno può manipolare i dati inviati e ingannare il destinatario nell’accettare i dati manipolati come validi.

La riservatezza dei dati è ottenuta attraverso la crittografia, che può assumere due forme: simmetrica e asimmetrica.

• La crittografia simmetrica utilizza una singola chiave che deve essere condivisa tra tutti i partecipanti che stanno comunicando.
• La crittografia asimmetrica utilizza chiavi personali., Ogni partecipante ha la propria chiave pubblica e la propria coppia di chiavi private per crittografare e decrittografare i messaggi durante la comunicazione.

(Nota: Questo blogpost parlerà di crittografia nel contesto della crittografia simmetrica. In un post di follow-up, ci immergeremo nella crittografia asimmetrica.)

Crittografia dei dati: Due tipi di crittografia

La crittografia garantisce la riservatezza dei dati e coinvolge due componenti importanti:

1. Una chiave segreta: nel contesto della crittografia simmetrica, possiamo supporre che i nostri partecipanti, Alice e Bob, abbiano una chiave segreta condivisa.,
2. Un cifrario: un insieme di algoritmi, uno per la crittografia e uno per la decrittografia.

È importante notare che gli algoritmi di crittografia e decrittografia sono noti al pubblico. L’unica cosa tenuta segreta è la chiave.

Due tipi di cifrari sono cifrari stream e cifrari a blocchi. Un potenziale prerequisito per comprendere adeguatamente entrambi questi cifrari è la conoscenza delle operazioni bit a bit (operazioni eseguite su bit). Più specificamente, il concetto di esclusivo-o (XOR). Ho trovato questo blogpost per dare una spiegazione molto chiara delle operazioni bit a bit., Oppure puoi provare a capire il concetto di XOR usando l’immagine qui sotto. Fondamentalmente due bit sono combinati e se sono diversi (uno 0 e uno 1) risultano in 1, e se sono uguali, (entrambi 0 o entrambi 1) risultano in 0. Da qui in poi, assumerò che il lettore comprenda il concetto di XOR e che la notazione universale per XOR sia:

Stream Cipher

Un stream cipher è un cifrario a chiave simmetrica in cui il testo in chiaro (in byte) è XOR’d bit per bit con la chiave (anche in byte) per produrre il testo cifrato., Lo stesso processo viene utilizzato per decifrare il testo cifrato. Data la natura dell’operazione XOR, se XOR il testo cifrato con la chiave, ciò risulta con il testo in chiaro originale.

Un lettore più attento può realizzare da questa descrizione che la chiave (identificato nella figura sopra come “un Cifrario a flusso”) e in chiaro deve avere qualcosa di molto importante in comune. Esatto! La chiave e il testo in chiaro devono avere la stessa lunghezza., Questo ovviamente non è estremamente pratico.

Per rendere più pratico un cifrario di flusso, viene introdotta l’idea di un generatore pseudorandom. Un generatore pseudorandom è una procedura deterministica che prende un input e produce un risultato pseudorandom ancora più lungo. Essendo una procedura deterministica significa che restituirà sempre lo stesso output esatto se dato lo stesso input (cioè “abc123” risulta in “8474f24e0d72e1b949ffd2 every” ogni volta)., La parola pseudorandom significa che mentre l’output non è effettivamente casuale (poiché è determinato in base a un particolare input), è in realtà indistinguibile da una stringa veramente casuale. In altre parole, dato un campione di input e output, non ci sono indizi su quale output corrisponde a un particolare input e viceversa, quindi è pseudorandom. È possibile utilizzare la chiave segreta condivisa come input per produrre una chiave pseudorandom ancora più lunga per fungere da chiave lunga da XOR’d con il testo in chiaro altrettanto lungo.,

Questa implementazione specifica di un codice di flusso che abbiamo illustrato finora è chiamata “one-time-pad”. Una caratteristica estremamente importante del one-time-pad è che il tasto one-time-pad può essere utilizzato solo UNA VOLTA. Una volta utilizzato una seconda volta, la sicurezza di questi messaggi è compromessa.

Nella foto sotto è una diapositiva dal corso. PRG (K) denota la sequenza pseudorandom generata dalla nostra chiave condivisa K. Il simbolo ⊕ denota XOR. c indica il testo cifrato. m indica messaggio (o testo in chiaro).,

in sostanza, questa diapositiva è detto che una volta che la chiave è usato due volte, siamo in grado di XOR le ciphertexts insieme, e che è esattamente uguale a XOR ing i due testi in chiaro insieme. Poiché c’è abbastanza ridondanza in inglese, un utente malintenzionato esperto può utilizzare queste informazioni per recuperare completamente i messaggi.

Per mantenere una chiave segreta condivisa, il concetto di nonce può essere utilizzato per garantire che non ripetiamo mai la chiave one-time-pad., Un nonce è un numero arbitrario che può essere utilizzato solo una volta in una comunicazione crittografica. Quando si invia il testo cifrato, il mittente può anche inviare un nonce da combinare con la chiave segreta da utilizzare come input per produrre una chiave pseudorandom distinta per ogni crittografia.

(Potresti aver notato che la diapositiva sopra dice Attacco 1., Per inciso, per coloro che si chiedono cosa sia l’attacco 2, l’attacco 2 è il fatto che mentre stream cipher offre riservatezza dei dati, NON fornisce l’integrità dei dati come definito nella prima sezione)

Block Cipher

Il secondo tipo di cifrario è un cifrario a blocchi. Un codice a blocchi accetta un input di lunghezza fissa e crittografa iterativamente il testo in chiaro ancora e ancora utilizzando una chiave diversa (una “chiave rotonda”) per ogni round e alla fine emette un testo cifrato della stessa lunghezza. 3DES e AES sono due esempi di cifrari a blocchi che prendono un input di 48 bit e 128 bit rispettivamente.,

La slide qui sopra mostra l’architettura di base di un blocco di cifratura. Si può vedere che un meccanismo di espansione chiave viene utilizzato per avere una nuova chiave per ogni turno. Il testo in chiaro, indicato (m) per il messaggio, viene crittografato ancora e ancora fino a quando finalmente viene restituito il testo cifrato corrispondente (c) della stessa lunghezza.

Per brevità, coprirò AES in questo blogpost., Sebbene DES/3DES sia storicamente significativo, oggi AES è più ampiamente utilizzato e accettato.

AES è costruito come una Sostituzione di Permutazione della Rete. AES opera su un blocco a 128 bit, pari a 16 byte. Come nella foto sopra in alto a sinistra, scriviamo i 16 byte come matrice 4 per 4. Questa matrice funge da struttura dati utile per mescolare i dati., In ogni round, il processo è il seguente:

1. Abbiamo XOR la chiave rotonda, prima (k0), con il messaggio corrente
2. Quindi passiamo attraverso un processo di sostituzione in cui i blocchi di dati vengono sostituiti con altri blocchi basati su una data tabella di sostituzione (nella foto sopra (1) ByteSub).
3. Passiamo attraverso un livello di permutazione in cui i bit vengono permutati e mescolati(nella foto sopra (2) ShiftRow& (3) MixColumn).
4. Quindi ripetiamo questo processo per 10 round.,

Nella foto sopra, noterai che l’ultimo round salta il passo della colonna Mix, XOR è il risultato con la nostra chiave round finale e emette il nostro testo cifrato risultante. Al fine di decifrare, abbiamo semplicemente invertire il processo. Il corso offre una panoramica di alto livello di questo processo di crittografia e incoraggia gli studenti a guardare più in profondità se è di tuo interesse. Pertanto, lascerò il funzionamento interno di AES a questo. Consiglierei alle persone di esaminare la procedura di rete Fiestel di 3DES per un confronto divertente e il contrasto di diversi cifrari a blocchi.,

In termini di hardware, dal lancio di Intel Westmere, Intel ha progettato i propri processori con istruzioni speciali per l’ottimizzazione AES integrate direttamente nel proprio hardware e AMD ha seguito l’esempio poco dopo.

Modalità di funzionamento del cifrario a blocchi

A differenza di un cifrario a flusso, un cifrario a blocchi accetta solo un input a lunghezza fissa. Ovviamente vogliamo gestire dati più grandi di 16 byte alla volta. Quindi è importante capire le modalità di funzionamento in base alle quali possiamo usare i cifrari a blocchi per crittografare grandi insiemi di dati., Per applicare questo cifrario a blocchi a un set di dati di grandi dimensioni, la prima modalità operativa che può venire in mente è chiamata “Electronic Code Book” (ECB). ECB divide semplicemente i dati in blocchi di 16 byte ed esegue la crittografia AES in modo uniforme. Potrebbe anche essere fatto in parallelo. Molto veloce! Ma in realtà non è molto sicuro.

È sicuro, perché se a 16 byte messaggio si ripete, il testo avrà anche dati ripetuti., Questo divulga informazioni sui nostri dati a un potenziale attaccante. Possiamo applicare questa vulnerabilità al caso in cui stiamo crittografando un’immagine con ECB. Come puoi vedere qui sotto, è chiaro che la nostra immagine è un colpo alla testa. Nella zona pesantemente nero, possiamo vedere una silhouette attraverso i capelli scuri e camicia.

È importante che i nostri schemi di crittografia sono semanticamente sicuro., La sicurezza semantica è il concetto che se abbiamo un testo cifrato che corrisponde a uno dei due diversi testi in chiaro, un avversario non può indovinare con probabilità migliore di 1/2 a quale testo in chiaro corrisponde il testo cifrato. Chiaramente, la BCE non è semanticamente sicura. La nostra immagine crittografata ci dà un sacco di informazioni per indovinare la sua immagine normale corrispondente.

ECB è un esempio di una modalità di funzionamento one-time-key (ovvero, come il one-time-pad, una chiave può essere utilizzata solo una volta). Un’altra modalità di funzionamento a chiave singola più sicura è la modalità contatore deterministica. Sei libero di indagare da solo., Passerò alle modalità di funzionamento sicure che abilitano le chiavi a più tempi!

Cifratura a blocchi (CBC) è una modalità di funzionamento che catene ogni blocco di 16 byte di testo in chiaro insieme attraverso XOR’ing il testo cifrato del testo in chiaro precedente nel nostro testo in chiaro corrente prima di eseguire la cifratura a blocchi (cioè AES). L’immagine sottostante chiarisce questo concetto:

prima di iniziare con un casuale IV., IV sta per vettore di inizializzazione che può essere definito come: il valore iniziale utilizzato per avviare un processo iterato. Nel caso di CBC, l’IV deve essere casuale (quindi imprevedibile) quindi deve essere univoco per ogni transazione. Il primo blocco del testo cifrato è semplicemente il IV casuale non cifrato. Per produrre il resto del testo cifrato, in primo luogo, il IV casuale è XOR’d con il primo blocco di testo in chiaro (m). Il risultato viene quindi crittografato con la chiave rotonda k per restituire il primo blocco di testo cifrato crittografato (c)., Quel testo cifrato viene quindi XOR’d con il prossimo blocco di testo in chiaro (m), il risultato viene crittografato con la chiave rotonda k e restituisce il secondo blocco di testo cifrato crittografato (c). Il processo viene continuato fino a quando tutti i blocchi sono stati crittografati.

Per decifrare, abbiamo semplicemente invertire il processo.

Un componente importante della crittografia CBC è che l’IV casuale è imprevedibile., Se l’IV diventa prevedibile, il nostro schema di crittografia diventa vulnerabile agli attacchi in chiaro scelti. Chosen Plaintext Attack (CPA) è un modello di attacco che presuppone che l’utente malintenzionato possa ottenere testi cifrati per testi in chiaro arbitrari e utilizzarli per rivelare informazioni sui messaggi crittografati. Quindi, un IV imprevedibile è necessario per garantire la sicurezza CPA.

Porta con me qui mentre cerco di spiegare come funzionerebbe questo attacco: è possibile eseguire un attacco in chiaro scelto in presenza di IV prevedibili a causa della natura di XOR., Se si XOR lo stesso valore insieme (0101 0 0101) sarà sempre uguale a 0, quindi si annulla. Quindi, se sospetti che un testo cifrato osservato c corrisponda a un particolare testo in chiaro m, puoi testare la tua ipotesi con un IV prevedibile. Se il testo in chiaro in questione è stato crittografato con IV1 in modo tale che c = E(k, m IV IV1) puoi inviare un nuovo testo in chiaro da crittografare e vedere se ottieni un risultato corrispondente: c. Poiché puoi prevedere che IV sarà IV2, invii m IV IV1 IV IV2., Il processo CBC XOR questo input con il prossimo IV, IV2 tale che: c = E(k, m IV IV1 IV IV2 IV IV2) quindi IV2 annulla, e ancora una volta stiamo crittografando E (k, IV1 m m) che risulterebbe ancora una volta con c e se ciò accade, siamo stati in grado di indovinare cosa è stato precedentemente crittografato con IV1.

Lavoro davvero fantastico se hai superato quello — ^

Con quello, mi piacerebbe rivedere un’altra modalità di cifratura a blocchi che concluderà il primo blogpost in questa serie di 3 parti. Se è stato un grande sforzo per arrivare fino a questo punto, ora potrebbe essere un buon momento per una breve pausa prima di continuare!,

Ok, quindi abbiamo esaminato ECB, CBC e le loro vulnerabilità, ma infine, e probabilmente la cosa più importante, introdurrò la modalità contatore randomizzato (CTR). Questa è la modalità operativa più recente e più sicura ed è anche più efficiente di CBC.

Randomizzati in Modalità Contatore prende anche un casuale IV. IV serve uno scopo diverso qui però. La nostra chiave viene combinata (ad es., via AES) con una versione iterata la nostra IV: sopra continuiamo ad aggiungere 1 alla nostra IV per ogni iterazione, altrimenti otterremmo un risultato ripetuto. Lo facciamo fino a quando non abbiamo un pad fino a quando il nostro messaggio in chiaro. Proprio come il cifrario di flusso one-time-pad, ora XOR il nostro messaggio in chiaro con il nostro pad pseudorandom per ottenere un testo cifrato. Se il tuo hardware ha più motori AES, questo è ultra efficiente perché è parallelizzabile. In CBC, ogni testo cifrato dipendeva dal precedente blocco di testo cifrato, quindi era impossibile parallelizzare.,

Non abbiamo nemmeno necessariamente bisogno di un codice a blocchi per combinare il nostro IV e la chiave in un pad pseudorandom. I cifrari a blocchi devono essere reversibili. Se guardi da vicino la meccanica della modalità contatore randomizzato, noterai che la decrittografia non richiede di invertireF(k, IV) . Data la natura di XOR, tutto ciò che dobbiamo fare è rigenerare lo stesso pad pseudorandom e XOR con il nostro testo cifrato. Quindi, per decifrare, dobbiamo ripetere l’operazione, non invertirla.,

Astrattamente parlando (finora ho evitato concetti astratti), ciò significa che la procedura che usiamo per combinare la nostra chiave segreta e IVF(k, IV) deve essere una funzione Pseudorandom (PRF) al contrario di una Permutazione Pseudorandom (PRP). In realtà abbiamo applicato questi concetti in questo blogpost. Sia PRPs che PRFS sono procedure deterministiche che, dato un particolare input, risultano in un output pseudorandom. (cioè AES, XOR). Tuttavia un PRP è più severo nel senso che deve essere reversibile., Infatti, i termini PRP e block cipher (come AES) sono spesso usati come sinonimi. Un PRF tuttavia NON ha bisogno di essere reversibile. Se si torna alle diapositive precedenti visualizzate in questo post, ora capirete la notazione PRF e PRP.

Questo conclude la mia panoramica della crittografia simmetrica! Abbiamo coperto cifrari flusso e cifrari a blocchi. Quindi, poiché i cifrari a blocchi possono essere eseguiti solo su circa 16 byte alla volta, abbiamo coperto le modalità di funzionamento utilizzate per eseguire cifrari a blocchi su grandi testi in chiaro. Abbiamo anche chiarito i concetti di PRPs vs PRFs.