Cos'è un oracle crittografico?

Un oracolo è un individuo che conosce il numero di cellulare personale di un dio. Ciò consente a lui (o lei) di ottenere alcune informazioni che di solito sono considerate fuori dalla portata di semplici mortali, come gli scorci del futuro. Nella crittografia, è lo stesso, tranne che non è coinvolta alcuna divinità: un oracolo è un sistema che può fornire informazioni aggiuntive su un sistema, che altrimenti non sarebbero disponibili.

Ad esempio, considera la crittografia asimmetrica con RSA . Lo standard I link indica come un dato dovrebbe essere crittografato con una chiave pubblica. In particolare, la crittografia inizia con un'operazione padding , in cui la parte di dati viene prima espansa aggiungendo un'intestazione, in modo che la lunghezza dei dati riempiti corrisponda alla lunghezza della chiave pubblica RSA. L'intestazione dovrebbe iniziare con i due byte 0x00 0x02 , seguiti da almeno otto byte casuali diversi da zero e quindi un altro 0x00 . Una volta che i dati sono stati riempiti, è il momento di applicare l'operazione matematica che è al centro dell'operazione RSA (esponenziazione modulare). I dettagli del padding sono importanti per la sicurezza.

Il risultato della crittografia è un intero modulo il modulo RSA , un grande numero intero che fa parte della chiave pubblica. Per una chiave RSA a 1024 bit, il modulo n è un valore intero maggiore di 2 ¹⁰²³ , ma inferiore a 2 ¹⁰²⁴ . Un chunk di dati correttamente crittografato, con RSA, produce un valore intero tra 1 e n-1 . Tuttavia, il padding implica una struttura , come mostrato sopra. La parte decrittografia DEVE trovare, dopo la decodifica, un'intestazione PKCS # 1 correttamente formata, iniziando con 0x00 0x02 bytes, seguita da almeno otto byte diversi da zero e deve esserci un 0x00 che contrassegna la fine dell'intestazione . Pertanto, non tutti gli interi tra 1 e n-1 sono validi messaggi crittografati con RSA (meno di 1 ogni 65000 di tali interi produrrebbe un riempimento adeguato alla decrittazione).

Sapere se un dato intero modulo n darebbe, dopo la decrittazione, una struttura di riempimento valida, dovrebbe essere impossibile per chiunque non conosca la chiave privata. Il proprietario della chiave privata (la divinità) ottiene tali informazioni e molto di più: se la decodifica funziona, il proprietario della chiave privata riceve effettivamente il messaggio, che è il punto di decrittazione. Supponiamo che sia un'entità, da qualche parte, che possa dirti se un dato intero modulo n è un pezzo di dati validamente crittografato con RSA; quell'entità non ti darebbe il risultato completo della decrittografia, ti dirà solo se la decifrazione funzionerebbe o meno. Questa è un'informazione a un bit, una visione ridotta di ciò che otterrebbe la divinità. L'entità è il tuo oracolo: restituisce parti delle informazioni che sono normalmente disponibili solo al proprietario della chiave privata.

È risulta che, dato l'accesso a tale oracolo, è possibile ricostruire la chiave privata, inviando integer appositamente creati modulo n (ci vogliono circa un milione di tali valori e un bel po 'di matematica, ma può essere fatto). Si scopre inoltre che la maggior parte delle implementazioni SSL / TLS di quel periodo (nel 1999) hanno involontariamente comportato come oracoli: se hai inviato, come client, un messaggio ClientKeyExchange crittografato con RSA invalido, il server rispondeva con un messaggio di errore specifico ("duh, il tuo messaggio ClientKeyExchange puzza"), mentre se la decrittografia funzionava, il server manteneva il protocollo, usando qualsiasi valore decodificato (in genere sconosciuto al client se il client ha inviato un valore casuale, quindi il protocollo non è riuscito in seguito, ma il client potrebbe vedere la differenza tra un riempimento valido e uno non valido). Pertanto, con tale implementazione, un utente malintenzionato potrebbe (dopo un milione o più di connessioni non riuscite) ricostruire la chiave privata del server, che di solito è considerata una cosa negativa.

Ecco quali sono gli oracoli: una descrizione matematica di una perdita di dati, da utilizzare nelle prove di sicurezza. Nel caso di RSA, questo dimostra che sapere se un valore ha un padding adeguato o meno è in qualche modo equivalente all'apprendimento della chiave privata (se conosci la chiave privata puoi provare la decifrazione e vedere il padding per te stesso: l'attacco Bleichenbacher mostra che funziona anche al contrario)

Un oracolo è qualcosa che può immediatamente ( O(1) ) darti la risposta a qualche problema, di solito un problema impossibile o impossibile. Ad esempio, un "Problema di interruzione di Oracle" potrebbe dirti immediatamente se un certo programma su un determinato input si ferma o meno, anche se il problema dell'arresto è uncomputable a noi semplici mortali. Tuttavia, a volte possiamo dimostrare alcune proprietà utili fingendo che esistano alcuni oracoli.

Nei documenti crittografici, ad esempio, gli oracoli sono spesso utilizzati per dimostrare che, anche se i nostri attaccanti hanno avuto accesso a un oracolo apparentemente impossibile, loro ancora non avrebbero Ho alcun vantaggio (significativo) per rompere la nostra sicurezza. Ad esempio, un'importante proprietà degli algoritmi di crittografia (chiamata resistenza a noti attacchi di testo normale ) è che se a un utente malintenzionato viene dato un messaggio crittografato con la tua chiave m' e vogliono conoscere il messaggio originale m (o capire la tua chiave) , quindi dare loro un altro messaggio n e la sua crittografia con la tua chiave n' non dovrebbe aiutarli a farlo in alcun modo.

Portalo all'estremo ( attacco di testo normale scelto ) : dai un attaccante un oracolo in grado di crittografare o decrittografare qualsiasi messaggio con la tua chiave tranne per m e m' . Anche in queste condizioni estreme, vorremmo mostrare per la nostra crittografia che l'attaccante con l'oracolo non avrà alcun vantaggio nel trovare m (o la tua chiave) rispetto all'attaccante senza l'oracolo. Ciò significherebbe che la nostra crittografia è al sicuro da attacchi di testo in chiaro scelti.

[Edit]
Ecco un altro esempio pratico. Nella domanda un programma potrebbe mai dire se un altro programma gioca a scacchi , mostriamo che nessun programma di questo tipo esiste assumendo innanzitutto che è un oracolo di rilevamento degli scacchi, quindi mostrare la sua esistenza porta a un'impossibilità logica.

Gli oracoli crittografici sono un metodo di input / output della scatola nera.

Risponderà a qualsiasi input con una risposta pseudo-casuale, ma fornirà sempre lo stesso output per uno specifico input.

Sono generalmente utilizzati per funzioni di hash in cui la casualità è importante per una maggiore sicurezza.

Ovviamente ci saranno ancora problemi di sicurezza in quanto è solo una funzione matematica che restituisce numeri apparentemente pseudo-casuali, ma sono ovviamente più forti di alcune delle loro controparti meno casuali.

Ecco un documento completo su di loro e sul loro design: link

Apparendo in molte forme, spesso con un'aria confusa, l'oracolo è essenzialmente una capacità immaginata che può essere attribuita al lato della sicurezza o all'attaccante, ed è usato come uno strumento utile per valutare la sicurezza - se sei attento a distinguere tra l'Oracolo buono e l'Oracolo "Iffy".

Guarda un video di 5 minuti in Crypto Academy

]