it-swarm-eu.dev

Co je kryptografický věštec?

Narazil jsem na termín „kryptografický Oracle“ ai přes trochu googlingu jsem nebyl schopen najít jasnou a stručnou definici. Co je to kryptografická společnost Oracle a co dělá? Může někdo dát příklad?

35
josh-cain

Oracle je jednotlivec, který zná osobní číslo mobilního telefonu boha. To mu umožňuje získat některé informace, které jsou obvykle považovány za mimo dosah pouhých smrtelníků, jako jsou záblesky budoucnosti. V kryptografii je to stejné, kromě toho, že se nejedná o žádné božstvo: Oracle je jakýkoli systém, který může poskytnout nějaké další informace o systému, které by jinak nebyly dostupné.

Zvažte například asymetrické šifrování s RSA . Standardní odkaz I uvádí, jak má být část dat šifrována veřejným klíčem. Zejména šifrování začíná operací vycpávky , ve které je část dat nejprve rozšířena přidáním záhlaví, takže délka vycpaných dat odpovídá délka veřejného klíče RSA. Záhlaví by mělo začínat dvěma bajty 0x00 0x02, následované nejméně osmi náhodnými nenulovými bajty a poté dalším 0x00. Jakmile jsou data vyplněna, je čas aplikovat matematickou operaci, která je jádrem operace RSA (modulární exponentiace). Podrobnosti o čalounění jsou důležité pro zabezpečení.

Výsledkem šifrování je celé číslo modulu RSA , velké celé číslo, které je součástí veřejného klíče. Pro 1024bitový klíč RSA je modul n celé číslo větší než 21023, ale menší než 21024. Správně šifrovaný datový blok s RSA poskytuje celočíselnou hodnotu mezi 1 a n-1 . Výplň však předpokládá nějakou strukturu , jak je ukázáno výše. Dešifrovací strana MUSÍ po dešifrování najít správně vytvořenou hlavičku PKCS # 1, počínaje 0x00 0x02 bajtů, následovaných nejméně osmi nenulovými bajty a musí existovat 0x00, která označuje konec záhlaví. Proto ne všechna celá čísla mezi 1 a n-1 jsou platná RSA - šifrovaná zpráva (méně než 1 každých 65 000 takových celých čísel by po dešifrování poskytla správné vycpávky).

Vědět , zda daný celočíselný modul n by po dešifrování poskytl platná struktura čalounění má být neuskutečnitelná pro kohokoli, kdo nezná soukromý klíč. Vlastník soukromého klíče (božstvo) získává tyto informace a ještě mnohem více: pokud dešifrování funguje, vlastník soukromého klíče skutečně dostane zprávu, což je místo dešifrování. Předpokládejme, že je někde entita, která vám může sdělit, zda dané celočíselné modulo n je platně šifrovaná část dat s RSA; tato entita by vám nedala úplný výsledek dešifrování, pouze by vám řekla, zda by dešifrování fungovalo nebo ne. To je informace o jednom bitu, snížený pohled na to, co by božstvo získalo. Subjekt je váš Oracle: vrací části informací, které jsou běžně dostupné pouze vlastníkovi soukromého klíče.

dopadá , že při přístupu k takovému Oracle je možné znovu vytvořit soukromý klíč zasláním speciálně vytvořených celých čísel modulo n (trvá přibližně milion takovýchto hodnot a docela dost matematiky, ale dá se to udělat). Ukazuje se také, že většina SSL/TLS implementace té doby (která byla v roce 1999) se nedobrovolně chovala jako věštci: pokud jste jako klient odeslali neplatně zašifrovanou zprávu ClientKeyExchange RSA, server odpověděl konkrétní chybovou zprávou („duh, vaše zpráva ClientKeyExchange smrdí“), zatímco pokud dešifrování fungovalo, server pokračoval v protokolu, používal jakoukoli hodnotu, kterou dešifroval (klientovi obvykle neznámá, pokud klient odeslal náhodnou hodnotu) , takže protokol selhal později, ale klient viděl rozdíl mezi platným a neplatným polstrováním). Proto by s takovou implementací mohl útočník (po asi milionu neúspěšných připojení) znovu vytvořit soukromý klíč serveru, což je obvykle považováno za špatnou věc.

To jsou oráky: matematický popis úniku dat, který se použije v bezpečnostních důkazech. V případě RSA to ukazuje, že vědět, zda hodnota má správné vycpání nebo ne, je nějak ekvivalentní učení soukromého klíče (pokud znáte soukromý klíč, můžete se pokusit o dešifrování a vidět vycpávky pro sebe; útok Bleichenbacher ukazuje že to také funguje opačně).

67
Thomas Pornin

Oracle je něco, co vám může okamžitě (O(1)) poskytnout odpověď na nějaký problém, obvykle neuskutečnitelný nebo nemožný problém. Například a "Oracle s problémem zastavení" vám může okamžitě sdělit, zda se určitý program na určitém vstupu zastaví nebo ne, i když problém zastavení je nepočítatelný to nás pouhé smrtelníky. Někdy však můžeme ukázat některé užitečné vlastnosti předstíráním, že existují nějaké věštce.

Například v kryptografických papírech se nejčastěji používají oracles, který ukazuje, že i , pokud naši útočníci měli přístup k nějaké zdánlivě neuvěřitelné Oracle, still by nemělo žádnou (významnou) výhodu pro porušení naší bezpečnosti. Například jedna důležitá vlastnost šifrovacích algoritmů (nazývá se rezistence na známé útoky prostého text ) je to, že pokud útočníkovi bude dána zpráva zašifrovaná klíčem m' a chtějí znát původní zprávu m (nebo zjistit svůj klíč), pak jim dají další zprávu n a její šifrování pomocí vašeho klíče n' by jim neměl nijak pomoci.

Vezmeme-li to do extrému ( vybraný útok prostého text ): dejte útočníkovi Oracle, který může zašifrovat nebo dešifrovat libovolný zprávu s vaší zprávou klíč kromě pro m a m'. I za těchto extrémních podmínek bychom chtěli ukázat pro naše šifrování, že útočník s Oracle nebude mít výhodu při hledání m (nebo váš klíč) než útočník bez Oracle. To by znamenalo, že naše šifrování je bezpečné před útoky typu prostý text.


[Upravit]
Zde je další praktický příklad. V otázce Mohl by program kdykoli zjistit, zda jiný program hraje šachy , ukážeme, že žádný takový program neexistuje tím, že budeme předpokládat, že existuje je šachová detekce Oracle, pak ukázání jeho existence vede k logické nemožnosti.

Kryptografické výrazy jsou metoda vstupu/výstupu černé skříňky.

Bude reagovat na jakýkoli vstup pomocí pseudonáhodné odpovědi, ale vždy poskytne stejný výstup pro konkrétní vstup.

Obvykle se používají pro hašovací funkce, kde je pro vyšší bezpečnost důležitá náhodnost.

Je zřejmé, že stále existují bezpečnostní otázky, protože je to jen matematická funkce, která vrací zdánlivě pseudonáhodná čísla, ale jsou zjevně silnější než některá z jejich méně náhodných protějšků.

Zde je solidní dokument o nich a jejich designu - http://cseweb.ucsd.edu/users/mihir/papers/ro.pdf

1
doyler