Fondamenta della crittografia Prof. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair Professor International Institute of Information Technology – Bangalore Collezione – 31 Random Oracle Model – Parte I (Riferirsi Slide Time: 00.30) Ciao a tutti, benvenuti a questa lezione. Solo un breve recap. Nell'ultima lezione abbiamo discusso di alcuni degli attacchi generici che possono essere lanciati sulle funzioni hash, ovvero gli attacchi di compleanno, e abbiamo anche discusso alcune applicazioni delle funzioni hash come catene di Block, alberi di Merkel e così via. In questa lezione proseguiremo la nostra discussione sulla funzione hash crittografica. In sostanza, introdurremo un modello di prova molto interessante quello che chiamiamo modello Random - Oracle. (Riferimento Slide Time: 00 :58) Quindi, iniziamo con la nostra discussione su modello Random - Oracle chiamato anche ROM. Ci sono quindi diversi scenari in cui progettiamo primitivi crittografici dove si utilizzano le funzioni di hash resistenti alle collisioni e quelle costruzioni sono altamente pratiche in natura e sono altamente efficienti. Alcuni esempi di tali primitivi sono la funzione di derivazione chiave, lo schema di impegno, i primitivi a chiave pubblica e così via, ma purtroppo si scopre che non possiamo dimostrare la sicurezza di questi primitivi crittografici in base alle proprietà standard della funzione hash. Quello che intendo per proprietà standard della funzione hash è la proprietà di resistenza alle collisioni, giusto. Quindi quello che fa esattamente Random - Oracle modello ti dà un modello in cui puoi provare la sicurezza dei primitivi crittografici progettati in base alle funzioni hash in cui non è possibile dare i test di sicurezza appena basati sulla proprietà di resistenza alla collisione della funzione hash sottostante e ciò che facciamo in questo modello Random - Oracle stiamo facendo un presupposto molto forte sulla funzione hash sottostante. Ovvero, facciamo una supposizione idealizzata e l'assunzione esatta che facciamo della funzione hash sottostante verrà discussa presto e ciò che questo modello Random - Oracle fa è che agisce da terra di mezzo per te dove non hai alcuna prova di sicurezza in una mano e mentre l'altra mano hai una rigorosa prova di sicurezza proprio in base alle ipotesi di crittografia standard. Dato che non si può dare la prova di sicurezza delle costruzioni in base alle proprietà standard della funzione hash crittografica. Quindi ipotizziamo che siamo nel modello Random - Oracle serve tipo un terreno di mezzo dove facendo supposizioni idealizzate sulla vostra funzione hash sottostante, è possibile completare la prova di sicurezza. (Riferimento Slide Time: 02.47) Così andiamo nei dettagli sottostanti del cosiddetto modello Random - Oracle. Quindi quello che facciamo in questo modello Random - Oracle è supporre che stiamo progettando un primitivo crittografico basato su una funzione hash mapping arbitrario di lunghezza bit a stringhe di dimensioni fisse delle stringhe di bit. Quindi quello che facciamo è ipotizza che le funzioni di hash sottostanti si comportino come una funzione casuale mappando l'input di lunghezza arbitraria alle uscite a lunghezza fissa e immaginate di progettare una primitiva crittografica dove utilizziamo questa funzione hash sottostante modellata come una funzione davvero casuale. Supponiamo che ogni partecipante del sistema abbia accesso oracolo alla funzione hash. Ciò significa che nessun partecipante al sistema incluso l'utente genuino così come l'avversario non conoscerà i dettagli interni e il codice e la logica della funzione hash sottostante. Quindi, questo è un presupposto molto forte che stiamo facendo in merito alla funzione hash sottostante in questo modello perché in realtà quando progettiamo una primitiva crittografica, stiamo per istanziare questa funzione hash per qualche funzione di hash pratico. Quando utilizziamo una qualche funzione hash pratico ogni entità del sistema sarà conoscendo il codice esatto o la logica della funzione hash, ma quando stiamo dando la prova nel modello Random - Oracle, supponiamo che nessuna entità nel sistema conosca i dettagli esatti della funzione hash sottostante. Anche le chiamate tra l'oracolo e i partecipanti sono private. Questo significa, immaginate se ho un primitivo crittografico che coinvolge l'utente 1, l'utente 2 e l'utente 3 e ognuno di essi deve utilizzare questa funzione hash a dire l'utente 1 vuole valutare la funzione hash sottostante su alcuni input x. Poi supponiamo che nel modello Random - Oracle l'interazione tra l'utente 1 e l'interfaccia o l'oracolo H sia attraverso un canale privato tra l'utente 1 e l'oracolo H. Così l'utente 2 e l'utente 3 non starebbero conoscendo gli input esatto su cui l'utente 1 sta andando a valutare la funzione hash sottostante o l'oracolo. Si ipotizza inoltre che l'oracolo H sia mantenuto come una tabella composta da diversi x, y value e il modo in cui questa tabella è mantenuta è la seguente. Se qualche entità interroga questo oracolo su un input x, allora quello che la tabella fa o l'oracolo fa è sostanzialmente verifica nella tabella esistente che è un elenco di diversi valori (xi, yi) se esiste una voce xi con il valore essere x. Questo significa in sostanza, la tabella verifica se il valore dell'oracolo sull'input x è già presente in tavola o meno. Se c'è già, allora i corrispondenti yi vengono restituiti indietro come l'uscita dell'oracolo sull'input x, mentre se non c'è una voce esistente xi con corrispondente il valore x, allora cosa fa l'oracolo? Crea una nuova voce nella tabella in cui memorizza il valore della x e contro quella x memorizza un valore y uniformemente casuale dove il valore y è una stringa di bit uniformemente casuale e che serve come riferimento o l'output della funzione o il valore oracolo o l'uscita oracolo per l'input x per le successive chiamate verso l'oracolo. Quindi mantenendo questo oracolo come un tavolo (x, y) come questo, è garantito che effettivamente l'oracolo soddisfi le proprietà richieste da una funzione davvero casuale, giusto. (Riferimento Slide Time: 06 :06) Quindi ci sono alcune importanti proprietà nel modello Random - Oracle e questo sarà cruciale quando daremo prove nel modello Random - Oracle. Quindi la prima proprietà è che se qualche input x non è stato querizzato all'oracolo H, allora il valore dell'oracolo su questo input x sarà un valore pari a un bit uniformemente casuale e questo vale anche se l'input x è noto a un'entità o ad una parte della x è noto all'entità o anche se x non è uniformemente valore casuale. Questo significa anche se x è qualche input dove tutti i bit dell'input tranne l'ultimo bit sono noti e se l'oracolo non è stato querizzato su quell' input x, allora l'uscita dell'oracolo su quell' input x sarà un valore uniformemente casuale l bit, e sottolineo che questo è diverso dalla proprietà pseudo casualità del generatore di pseudorandom. Diciamo che se abbiamo un generatore di pseudo casualità G, allora la proprietà pseudo casualità ci richiede che la produzione del generatore di pseudorandom G su qualche input x debba essere quasi uguale a un valore uniformemente casuale solo se l'input x per il generatore di pseudorandom è un valore uniformemente casuale e sconosciuto, mentre nel contesto del modello Random - Oracle ci sono proprietà pseudo casualità che richiediamo sono diverse. Qui, qui, richiediamo che se l'oracolo non viene querizzato per l'input x e anche se l'x non è un valore uniformemente casuale ed è noto a voi, il valore di uscita H (x) sarà un valore uniformemente casuale dal co - dominio. Ecco allora una delle proprietà importanti. (Riferimento Slide Time: 07 :41) La seconda proprietà importante nel modello Random - Oracle è di proprietà estrattiva che sarà una proprietà molto cruciale successivamente quando vedremo le prove dei primitivi crittografici nel modello Random - Oracle. Quindi supponiamo di avere una costruzione di crittografia di qualche primitivo, diciamo che questo primitivo C che coinvolge determinate entità, potrebbe essere una comunicazione sicura, un protocollo o potrebbe essere solo qualsiasi tipo di protocolli di crittografia. Ad esempio, immaginate che questa crittografia primitiva C coinvolga 3 entità e questo primitivo richieda anche chiamate ad una funzione hash sottostante e supponiamo di dare una prova di riduzione basata su una prova di riduzione che effettivamente questa primitiva crittografica soddisfa qualche proprietà, qualche proprietà di sicurezza come per qualche definizione, e diciamo che stiamo dando una prova di riduzione a base di riduzione e sostanzialmente quando stiamo dando una prova di riduzione per dimostrare che effettivamente i cosiddetti primitivi di crittografia soddisfano determinate proprietà di sicurezza come per qualche data definizione nel modello Random Oracle allora quando diamo la riduzione sonda a base di sonda quello che in sostanza stiamo andando a fare è che ipotizziamo che diciamo che abbiamo un avversario Un attaccante della tua primitiva crittografica C, poi usando quell' avversario il nostro obiettivo sarà quello di progettare un altro avversario dire che attacca un altro primitivo, giusto. Ecco cosa tiriamo tipicamente nella prova di riduzione a base di riduzione. Ora come parte della sua strategia di attacco, questo avversario A potrebbe aver bisogno di chiamare la funzione hash sottostante, giusto, perché potrebbe essere una parte della sua strategia di attacco sottostante. Ma visto che ora siamo nel modello Random - Oracle, questo avversario ha bisogno di fare oracolo chiamate alla funzione H. Così quando questo avversario A che stiamo progettando come parte della riduzione, sta richiamando questo avversario già esistente A come subroutine, arriverà a sapere che l'avversario A o l'avversario esistente A ha bisogno di invocare l'oracolo H su diversi input x della sua scelta. Quindi quegli input, l'uscita dell'oracolo su quegli input che l'avversario A vuole interrogare sarà ora imparato dall'avversario A come parte della riduzione. Ecco, questo è ciò che intendiamo per la proprietà estrattiva. Questo significa che l'avversario A ora può vedere le x query che l'avversario esistente A vorrebbe fare all'Oracolo H. Questo non contraddice la proprietà che come accennato prima dove ho detto che le chiamate tra ogni entità e oracolo si mantengono o sta accadendo attraverso un canale privato. Nella prova di riduzione, l'avversario A sta praticamente invocando l'avversario A nella sua mente. Questo significa che quando si richiama l'avversario esistente A come subroutine, arriverà automaticamente a sapere che come parte della sua strategia di attacco, quali sono le x query o i valori x per cui l'avversario esistente A vorrebbe fare le chiamate di oracolo H, giusto. Quindi non sta violando la proprietà esistente del modello Random - Oracle, ma il punto importante qui è che in quanto parte della riduzione, il nuovo avversario che stiamo cercando di costruire precisamente A, può estrarre gli input x per i quali l'avversario esistente vorrebbe fare le oracole chiamate. Ecco allora che si tratta di una delle proprietà importanti del modello Random - Oracle e della seconda proprietà. (Riferirsi Slide Time: 11.02) La terza proprietà del modello Random - Oracle che di nuovo sarà molto cruciale quando faremo delle prove dei primitivi crittografici nel modello ROM è la proprietà di programmabilità, e cosa intendo esattamente per la proprietà di programmabilità come ho accennato che se stiamo dando una riduzione basata su dimostrazioni, poi il nuovo avversario A che stiamo progettando quando richiama l'avversario esistente A, imparerà le query H cioè gli input x per cui l'avversario esistente vorrebbe fare le chiamate all'oracolo, giusto. Ma visto che ora stiamo facendo una riduzione qui a destra, non esiste una funzione H che sia effettivamente disponibile sia all'avversario A che all'avversario A perché ora non stiamo invocando un'istanza del primitivo C, giusto. Quando in realtà stiamo istanziando un richiamo del primitivo C, le parti avranno accesso ad un oracolo H, ma ora quello che stiamo facendo qui è che stiamo dando una prova di riduzione basata sulla prova, quindi non c'è alcuna istanziazione del primitivo C. Così, non c'è oracolo disponibile né all'avversario A né all'avversario A, ma dal momento che come parte della riduzione la nostra strategia avversaria A è quella di fare oracolo chiamate per l'oracolo H a diversi input x input fondamentalmente il nostro avversario A deve simulare l'interazione dell'avversario esistente con H. Basically, l'avversario A deve impostare l'output della oracolo H a questi x input che l'avversario A è esigente. Quindi, quello che l'avversario A può fare come parte della riduzione che essa stessa può impostare o può fingere come se la sua stessa abbia l'accesso all'oracolo e ciò che può fare è poter selezionare casualmente alcuni valori di y dal co - dominio dell'oracolo H sottostante e restituirlo come output della query oracolo che l'avversario A ha chiesto. Ecco cosa intendiamo per la proprietà di programmabilità. La chiamiamo come proprietà di programmabilità perché nella riduzione, il nuovo avversario A può programmare, può impostare l'uscita dell'oracolo agli input x per cui l'avversario A ha chiesto la risposta dall'oracolo. Ecco, questa è un'altra importante proprietà del modello Random Oracle che utilizzeremo quando otterremo le prove basate sulla riduzione per i primitivi crittografici nel modello Random - Oracle. (Riferimento Slide Time: 13 :21) Quindi ora confrontiamo una prova data o prova di sicurezza per qualche primitivo crittografico dato nel modello Random - Oracle versus la prova di sicurezza indicata nel modello standard. Quindi ancora immaginare di avere dei primitivi crittografici dire C e implica dire più entità e dove richiediamo a ogni entità di utilizzare alcune funzioni di hash sottostanti. Quindi nel modello standard quando diciamo che abbiamo una prova di sicurezza nel modello standard, non astringiamo la funzione hash sottostante come Random - Oracle. Supponiamo invece che si tratti di una funzione hash standard e di ogni entità ha libero accesso alla funzione hash sottostante. Questo significa, conosce il codice completo, la descrizione completa della funzione hash sottostante. Non facciamo che supponiamo che le entità interagiscono con la funzione hash per oracolo, mentre nel modello Random - Oracle quando ci assumiamo che se si progetta si dice un altro primitivo C che coinvolge la funzione hash. Se diciamo che stiamo dando una prova nel modello Random - Oracle, allora cosa intendiamo esattamente con questo è che ogni volta che stiamo instancando il primitivo C all'inizio una nuova funzione casuale H sarà istanziata e nessuna delle entità saprà cosa esattamente è quella particolare funzione hash, a destra. Ecco, questa è una grande differenza per una prova di sicurezza data nel modello Random Oracle. Questo significa che ogni volta che instanziamo il primitivo C non sarebbe il caso che lo stesso Random - Oracle o la stessa istanziazione dell'oracolo H saranno disponibili come era presente nel precedente richiamo. In ogni successiva invocazione in ogni nuova invocazione o un richiamo indipendente di C °, un oracolo indipendente H sarà fissato all'inizio e ogni istanza avrà accesso a quell' oracolo tramite canali privati in cui nessuna entità saprà cosa esattamente sia la descrizione del sottostante o l'oracolo instanziato. La definizione di sicurezza nelle 2 prove che abbiamo dato qui differirà come segue. Così, daremo una certa definizione di una certa sicurezza, quindi in sostanza la definizione di sicurezza nel modello standard sarà che per tutti i tempi polinomiali avversari o cercando di attaccare il primitivo C, la definizione sarà che la probabilità di un determinato evento dovrebbe essere trascurabile che sarà la definizione di sicurezza per il primitivo C, giusto, nel modello standard e più o meno lo stesso vale anche per una definizione di sicurezza data nel modello Random - Oracle. Ovvero, la definizione di sicurezza sarà che per tutti gli avversari a tempo determinato che tentano di attaccare il modello C primitivo nel modello Random - Oracle, la probabilità di certi eventi dovrebbe essere trascurabile. Ciò che esattamente quell' evento è che dipende dal sottostante primitivo C e sottostante primitivo C che stiamo cercando di costruire. Ad esempio se il primitivo C è un processo di crittografia sicuro, allora sostanzialmente quell' evento è l'evento di distinguibilità. Mentre se il primitivo C è una crittografia molto complicata, allora quell' evento che definisce se l'avversario è in grado di vincere il gioco o meno potrebbe essere un evento complicato, ma indipendentemente da questo, l'intuizione sottostante è che nella definizione standard di sicurezza del modello significa che la probabilità di avversari avversari o la rottura certa o la probabilità che un avversario garantisca che un determinato evento si verifichi con qualche probabilità è trascurabile mentre nel modello ROM la definizione di sicurezza più o meno rimane la stessa. La differenza è che nel modello standard la probabilità viene presa sulla scelta casuale delle parti e non sulla funzione hash sottostante perché la funzione hash sottostante sarà una funzione hash fissa perché ogni volta che andremo a instanziare il primitivo C nel modello standard, la stessa funzione hash verrà utilizzata ancora e ancora, ma quando stiamo valutando la probabilità che quel determinato evento sia trascurabile nel modello Random Oracle allora la probabilità viene presa non solo sulle query casuali sulle parti ma anche sulla scelta casuale dell'oracolo H che è istanziato all'inizio dell'istanziazione del primitivo C. Quindi, ecco un'altra differenza importante nella prova di sicurezza nel modello Random - Oracle contro una prova di sicurezza nel modello standard. (Riferimento Slide Time: 17 :29) Quindi questo significa che nel modello Random - Oracle, la sicurezza è garantita non per ogni possibile istanziazione Oracle. Significa che la sicurezza non può essere garantita per una particolare istanziazione di H, ma potrebbe essere garantita per altre istanziazioni di H, mentre nella definizione standard quando stiamo dando la prova appena basata sulla proprietà di resistenza alla collisione della funzione hash sottostante, la prova di sicurezza detiene per qualsiasi istanziazione di H che sia garantita collisione resistente, ma che non sia il caso nel modello Random Oracle. Il che significa che potrebbe essere difficile argomentare che qualsiasi istanziazione concreta dell'oracolo H da parte di specifiche funzioni hash del mondo reale che siano deterministiche in natura produrrà uno schema sicuro, giusto, e il punto importante è che anche se diamo una prova di sicurezza nel modello Random Oracle quando effettivamente distribuiamo quel regime nel mondo reale, l'oracolo H sottostante deve essere istanziato da una funzione hash deterministica concreta e non appena instanziamo l'oracolo H da una funzione hash deterministica ogni entità nel sistema, il mittente, il destinatario, il partito onesto e l'avversario anche avere accesso al codice dell'istanziazione sottostante dell'H. Che significa avversario non può essere limitato ad un semplice accesso oracolo a H, a destra. Ecco quindi le importanti proprietà del modello Random - Oracle. (Riferimento Slide Time: 18 :48) Ora, vediamo rapidamente un esempio per capire come funzionano esattamente le cose nel modello Random Oracle. Immaginate quindi di avere una funzione hash che impiega input di dimensioni di lino e vi dà output di dimensioni lout e utilizzando questa funzione hash supponiamo di progettare una funzione G che prenda un input di dimensioni in lino e vi dia un output di dimensioni lout e sostanzialmente ciò che questa funzione G fa è solo valuta la funzione hash sull'input x. Ora, affermo che se siamo nel modello Random - Oracle e se interpretiamo questa funzione hash sottostante come Random - Oracle che viene istanziato all'inizio di ogni istanziazione della funzione G, allora questa funzione G può essere vista come un generatore di pseudorandom e dimostrare che effettivamente la funzione G che abbiamo costruito qui è un generatore pseudo - Oracle nel modello Random - Oracle, dobbiamo modificare il gioco indistinguibile, il gioco indistinguibile standard che usiamo per definire la sicurezza del generatore di pseudo - Oracle per incorporare il modello Random - Oracle. Il cambiamento che sta per accadere qui è che se si ricorre nel gioco indistinguibile standard per PRG, la sfida per l'avversario è quella di distinguere un campione di pseudorandom da un campione davvero casuale, ma ora dato che stiamo per dare una prova nel modello Random - Oracle, dobbiamo anche modellare l'accesso oracolo alla funzione hash sottostante del Random - Oracle a cui il distinguo potrebbe avere accesso. Quindi, vediamo il gioco indistinguibile modificato per il PRG nel modello Random - Oracle. Immagina che ci sia un avversario A seduto tra il mittente e il destinatario, e visto che ora siamo nel modello Random - Oracle, quello che l'avversario sta per fare è, l'avversario starà ora a fare numero polinomiale di query oracolo a questo H e avversario non starebbe sapendo cosa esattamente è l'oracolo sottostante H. Quindi, fino e a meno che l'avversario non interroga questo oracolo H sul valore esatto, che è pre - condiviso tra il mittente e il destinatario, il valore di, che sender e ricevente sono outmettendo qui sarà uniformemente casuale dal punto di vista dell'avversario. Ora, qual è la probabilità che l'avversario abbia effettivamente queriato per H di, dato che ha fatto numero di query all'oracolo? Ebbene, se la mia distribuzione di probabilità o se i dati che sono stati pre - condivisi tra il mittente e il destinatario hanno big - bit di min - entropia, allora quello che l'avversario può sperare è che ogni volta possa chiedere il valore di questo oracolo H sui dati più favoriti che sente che il mittente e il destinatario potrebbero aver scelto come per questa distribuzione di probabilità Così, la probabilità che in ogni singola query, abbia effettivamente queriato per l'esatto, è di 12, perché questo è arrivato dalla definizione di -bit di min - entropia e dato che l'avversario ha fatto numero di query, con massima probabilità 2, avversario A potrebbe hanno querizzato per l'input H di dall'oracolo H. E se supponiamo che il big sia sufficientemente grande ed è qualsiasi come polinomicamente delimitato nel parametro di sicurezza, questa è una qualche funzione trascurabile nel parametro di sicurezza. Così, dal momento che l'avversario non ha querizzato per H di, salvo con probabilità trascurabile, dal punto di vista dell'avversario, il tasto resultante sarà una stringa uniformemente casuale l - bit e che assicura che ora mittente e ricevente possano tranquillamente utilizzare la chiave derivata per qualsiasi primitivo crittografico come la chiave. Diciamo per esempio se vogliono usare la chiave come chiave per AES, possono tranquillamente usarlo. Quindi, ora, potete vedere che come questa funzione di derivazione altamente efficiente basata sulla funzione hash possa essere dimostrata sicura se andiamo nel modello Random - Oracle. Ma se andiamo semplicemente in modello standard e utilizziamo le proprietà standard delle funzioni hash, ovvero la resistenza agli urti, non possiamo dimostrare che la funzione di derivazione così chiamata sia effettivamente una funzione di derivazione sicura. Così questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione, abbiamo continuato la nostra discussione sul modello Random - Oracle. Abbiamo visto che abbiamo certi argomenti a favore del modello Random - Oracle, abbiamo certi argomenti contro il modello Random - Oracle e così via. Così questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione, abbiamo introdotto un modello Random - Oracle. Questo in sostanza viene utilizzato per dare la prova di sicurezza dei primitivi crittografici in base ad alcune funzioni hash dove non possiamo completare una prova di sicurezza di quel primitivo proprio utilizzando le proprietà standard delle funzioni hash ovvero la proprietà di resistenza agli urti e abbiamo visto anche una dimostrazione del modello Random - Oracle, ovvero abbiamo visto che se prendiamo una funzione hash e la modelliamo come un Random Oracle, allora possiamo utilizzarlo per costruire un generatore di pseudorandom. Grazie.