Časový útok

V kryptografii je útok načasování útokem postranním kanálem , při kterém se útočník pokouší kompromitovat kryptosystém analyzováním času potřebného k provedení kryptografických algoritmů. Provedení každé logické operace na počítači nějakou dobu trvá a tato doba se může lišit v závislosti na vstupních datech. S přesným měřením času pro různé operace může útočník obnovit vstupní data.

Kryptosystémy často tráví mírně odlišné množství času zpracováním různých vstupů. Důvodem mohou být optimalizace výkonu, které přeskakují zbytečné operace, větvení , čtení dat z mezipaměti , instrukce procesoru (jako je násobení a dělení) prováděné v nedeterministickém čase a další. Výkonové charakteristiky obvykle závisí jak na šifrovacím klíči , tak na vstupních datech. Zároveň se čas strávený vyřizováním určitých požadavků může stát zdrojem úniku informací o systému. Jak moc takové informace mohou útočníkovi pomoci, závisí na mnoha parametrech, jako jsou: design kryptosystému, procesor obsluhující systém, použité algoritmy, příslušné implementační detaily, protiopatření přijatá proti načasovanému útoku, přesnost zpoždění. provedená měření.

Útok na rychlý umocňovací algoritmus

Algoritmus rychlého umocňování používaný algoritmy Diffie-Hellman a RSA provádí následující operaci na tajném klíči , kde n je část veřejného klíče (RSA) nebo konstanta (Diffie-Hellman) a y lze přeslechnout. Cílem útočníka je získat tajný klíč x . Oběť počítá pro více hodnot y . w je bitová délka klíče x . $R=y^{x}{\bmod {n))$ $y^{x}{\bmod {n))$

Pojďme~{{0}}~=~1

Pro~k=0~až~w-1:

Pokud~(bit~k~of~x)~je~1~pak

LetR_{k}=(s_{k}\cdot y){\bmod {n))

Else

Let~R_{{k}}~=~s_{{k}}

Let~s_{k+1}=R_{k}^{2}{\bmod {n))

EndFor

Návrat~(R_{{w-1}})

Útok umožňuje při znalosti bitů 0..(b-1) najít bit b . Chcete-li získat celý exponent, můžete začít s b=0 a pokračovat, dokud není znám celý exponent.

Když útočník zná prvních b bitů x , může vypočítat první biterace smyčky a najít hodnotu . Další iterace používá první neznámý bit x . Pokud je rovna 1, výpočet se provede , pokud je 0, operace se přeskočí. $Pro$ $s_{{b}}$ $R_{b}=(s_{b}\cdot y){\bmod {n}}$

Použití čínské věty o zbytku

K optimalizaci operací tajných klíčů v RSA se často používá čínská věta o zbytku . Nejprve a jsou vypočteny , kde y je zpráva. Nejjednodušší útok je zvolit y blízko p nebo q . Pokud je y menší než p , neudělá nic, a pokud , bude muset od y alespoň jednou odečíst p . Pokud je y o něco větší než p , pak bude mít nejvýznamnější bity rovné nule, což může zkrátit čas prvního násobení. Konkrétní načasování závisí na implementaci. $y{\bmod {p}}$ $y{\bmod {q}}$ $y{\bmod {p}}$ $y>p$ $y{\bmod {p}}$

Příklady útoků na RSA: Načasování útoků na RSA a Načasování útoků na RSA

Časová kryptoanalýza DSS

Algoritmus Digital Signature Standard počítá , kde p a q jsou útočníkovi známé a vypočítané předem, H(m) je hash zprávy, x je tajný klíč. V praxi se nejprve vypočítá a poté vynásobí . Útočník může vypočítat H(m) a podle toho opravit. Protože H(m) má přibližně stejnou velikost jako q , sčítání má malý vliv na operaci redukce v metodě umocňování podle Montgomeryho ( en ). Nejvyšší bity budou nejvýznamnější . Hodnota r je známá. Existuje vztah mezi vysokými bity x a dobou provádění operace Montgomeryho redukce. Pokud je vypočítán předem, podpis zprávy vyžaduje pouze dvě modulonásobení, takže množství přidaného šumu je relativně malé. $s=(k^{-1}(H(m)+x\cdot r)){\bmod {q))$ $k^{{-1}}$ $(H(m)+x\cdot r){\bmod {q))$ $k^{-1}{\bmod {q))$ $x\cdot r$ $k^{{-1}}$

Maskování časování

Nejviditelnějším způsobem, jak zabránit útokům načasováním, je zajistit, aby všechny operace trvaly stejně dlouho. Je však obtížné implementovat takové řešení, zejména na platformě nezávislé, protože optimalizace prováděné kompilátorem, přístupy do mezipaměti, časování instrukcí a další faktory mohou způsobit nepředvídané odchylky v časování. Pokud se ke zpoždění výstupu výsledku použije časovač, odezva systému zůstane pozorovatelná. Některé operační systémy také udávají úrovně zatížení procesoru a spotřeby energie.

Dalším přístupem je udělat měření času tak nepřesné, že útok se stane nesnesitelným. K době provádění se přidávají náhodné prodlevy, což zvyšuje počet šifrovaných textů, které útočník potřebuje.

Prevence útoků

Techniky používané k vytváření slepých signatur (viz také Blinding ) lze upravit tak, aby zabránily útočníkovi vystavit vstup operaci umocňování modulo. Před výpočtem modulárního exponentu zvolíme náhodný pár takový, že . Pro Diffie-Hellmana je snazší nejprve vybrat náhodný a pak vypočítat . Pro RSA je rychlejší zvolit náhodné coprime s n a pak vypočítat , kde e je součástí veřejného klíče. Před provedením umocňování modulo musí být vstupní zpráva vynásobena , a poté musí být výsledek opraven násobením . Systém by měl zahodit zprávy rovné . $(v_{{i}},v_{{f}})$ $v_{f}^{-1}=v_{i}^{x}{\bmod {n))$ $v_{{i}}$ $v_{f}={(v_{i}^{-1})^{x}}{\bmod {n}}$ $VF}}$ $v_{i}={(v_{f}^{-1})}^{e}{\bmod {n))$ $v_{i}{\pmod {n))$ $v_{f}{\pmod {n))$ $0{\pmod {n}}$

Výpočet inverzního modulo je považován za pomalou operaci, takže je často nepraktické generovat nový pár pro každou operaci umocňování. Nelze je však znovu použít, protože samy mohou být napadeny časem. Existuje řešení: aktualizace a před každou operací umocňování výpočtem a . $(v_{{i}},v_{{f}})$ $v_{{i}}$ $VF}}$ $v_{{i}}^{{'}}=v_{{i}}^{{2}}$ $v_{{f}}^{{'}}=v_{{f}}^{{2}}$

Odkazy

Paul C. Kocher. Načasování útoků na implementace systémů Diffie-Hellman, RSA, DSS a dalších . CRYPTO 1996: 104-113.
David Brumley, Dan Boneh. Vzdálené načasované útoky jsou praktické . USENIX Security Symposium, srpen 2003.