kryptoanalýza druhy útoků proti klasickým šifrám příklad útok hrubou silou frekvenční analýza Kasiskiho metoda index koincidence Jakobsenův algoritmus

© Květuše Sýkorová

• kryptoanalýza – druhy útoků proti klasickým šifrám – usnadnění útoku

• útok hrubou silou – slovníkový, hybridní

• frekvenční analýza


– metoda ad hoc

• Kasiskiho metoda • index koincidence – přirozený jazyk – struktura

• Jakobsenův algoritmus

– příklad

• usnadnění: – apriorní znalost o o.t.: • v jakém jazyce je napsán, • co mohlo být obsahem textu, • členění a struktura textu, …

– redundantní informace v o.t.:


• interpunkce, struktura slov, … • kryptografická zásada = odstranění redundance

– znalost kryptosystému: • • • •

délka a struktura klíče, závislost doby šifrování na délce klíče, odvoditelnost tajného klíče z veřejného, odolnost vůči různým útokům, …

• usnadnění: – porušení kryptografického protokolu: • podepisování bez použití hashování zprávy, • opakované použití stejného začátku o.t., • opakované použití hesla (Vernamova šifra), …

– další specifické znalosti:


• podle daného typu šifry • dostupnost veřejného klíče (RSA – brute force attack), …

• útoky (luštění): – zveřejnění šifrovacího algoritmu • verifikace algoritmu = ověření odolnosti vůči různým útokům • následné zesílení a úprava algoritmu

• cílem: – získat použitý šifrovací klíč © Květuše Sýkorová

• dešifrování všech zachycených zpráv

– využívá znalosti • o šifrovacím algoritmu, klíči, postupu šifrování, otevřeném textu, jazyce zprávy, … • frekvence výskytu znaků, použití vyhlazení frekvence, zmenšení prostoru klíčů, nevhodné použití algoritmu, …

• pendreková kryptoanalýza – pod hrozbou fyzického násilí na jedinci nebo jemu blízkých osobách dojde k prozrazení

• korupční kryptoanalýza


– vhodně zvolená finanční částka nebo jiná výhoda vede k prozrazení

• metody pro zmenšení prostoru klíčů – znalost souvislosti mezi o.t. a š.t., – znalost vlastností klíčů, …

• útok hrubou silou (brute force attack) – nejjednodušší a nejstarší druh útoku • nevýhodou = doba trvání

– jediný vždy možný útok • i proti velmi dobře navrženým šifrám

– útočník zkouší celý prostor klíčů © Květuše Sýkorová

• systematické testování všech možných kombinací hodnot klíčů – dnes snadno zvládnutelné pro klíče délky cca 90 bitů (11 znaků) – klíče = MP + VP + Č + SZ

• šifrování velkého množství zpráv – ověření se š.t.

• hledání vztahu mezi veřejným a soukromým klíčem – RSA – hledá se faktorizace čísla n

• útok hrubou silou (klíče) – možnosti ověření • on‐line útok – pokus o přihlášení k cílovému systému – většina systémů dnes implementovány ochrany proti on‐line útoku – 2‐jádrové PC zvládnou otestování cca 10 000 hesel / sec.


• off‐line útok – porovnání výsledku s uloženým hashem nebo se š.t. – pro útočníka příjemnější » limitován pouze výpočetní složitostí a kvalitou šifrového algoritmu – dnes otestování cca 1 000 000 hesel / sec.

• rozdělení prostoru klíčů a distribuce mezi více PC – využití Internetu

• útok hrubou silou (klíče) – inteligentní útok • optimalizovat na pořadí – pravděpodobnější hesla nejdříve


• znalost statistiky používaných hesel – úniky hesel ze sociálních sítí » např. 2010 RockYou 32,6 mil. hesel – jazykové odlišnosti – průměrná délka hesla = 7,89 znaků » 65% hesel je 6‐8 znakových – množina použitých znaků » klíče = MP + VP + Č + SZ » časté číslice (6‐8 cifer), malá písmena (6‐8 znaků), kombinace

zdroj: Computerworld 2011/05/06

• útok hrubou silou (klíče) – inteligentní útok • množina použitých znaků

doporučení: heslo dostatečně dlouhé (min.11 znaků) min. MP+VP+Č (+SZ)

– klíče = MP + VP + Č + SZ


heslo = 9 znaků Č (10 možností) MP (26 možností) MP+Č (36 možností) VP+MP+Č (62 možností) VP+MP+Č+SZ (96 možností) 2 196 let

1,6 minuty 150 hodin 118 dní 42,9 let

možnosti ověření bezpečnosti hesla: https://howsecureismypassword.net/ http://www.passwordmeter.com/ https://blog.kaspersky.com/password‐check/ http://password‐checker.online‐domain‐tools.com/ zdroj: Computerworld 2011/05/06

• slovníkový útok • doplňuje brute force attack (pro klíče)

– princip: • „silné“ heslo – lidé vymýšlí sami → není to náhodný řetězec znaků


• postupné zkoušení hesel z daného seznamu • vytváří se slovník hesel – slova běžná v daném jazyce » osobní jména a datumy, filmový svět, komixy, slavné osobnosti, známé zkratky, … – úniky hesel možnosti generování náhodného hesla: » nejp. heslo = 123456 http://www.generator‐hesel.cz/ http://www.converter.cz/passgen/pswdgen.php http://www.generate‐password.com/?language=cz http://wall.cz/generator‐hesla zdroj: Computerworld 2011/05/06

• hybridní útok – kombinuje slovníkový a brute force attack pro klíče – princip: • silnější heslo – modifikace existujícího slabého hesla » generuje se v průběhu testování


• modifikace: – – – – – – – –

první písmeno velké (2 nebo i 3) všechna písmena velká heslo pozpátku náhrada znaků za vizuálně podobné (O‐0, i‐1, z‐2, …) náhrada znaků za odpovídající číslice (ě‐2, š‐3, č‐4, …) opakování hesla dvakrát za sebou zřetězení dvou hesel s oddělovačem (mezera, tečka, *, …) připojení prefixu či sufixu (123, abc, 69, …) zdroj: Computerworld 2011/05/06

• frekvenční analýza • vymysleli Arabové už v 9. století

– princip: • porovnání frekvence výskytu znaků o.t. a š.t. – problém ‐ specifická struktura textu

• účinný hlavně proti monoalfabetickým šifrám


– dostatečně dlouhý text znak četnost znak četnost

A

B

C

D

E

F

G

H

I

J

K

L

M

8,2

1,5

2,8

4,3

12,7

2,2

2,0

6,1

7,0

0,2

0,8

4,0

2,4

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

6,7

7,5

1,9

0,1

6,0

6,3

9,1

2,8

1,0

2,4

0,2

2,0

0,1

anglický text - sestavili H. Beker a F. Piper

• index koincidence IC – zjistí počet použitých monoalfabetických substitucí • účinný hlavně proti polyalfabetickým šifrám (Vigenerova šifra)

– vymyslel William F. Friedman kolem roku 1925 • jednoduchý algoritmus řešení


– jeden z nejvýznamnějších statistických testů používaných v kryptologii • Vigenerovu šifru rozluštil Charles Babbage (1791‐1875) – profesor matematiky na Cambridge University

• později nezávisle Friedrich Wilhelm Kasiski – řešení je založené na pozorování (Kasiského test) – nebo na indexu koincidence (jednoduchá algoritmizace)

• Kasiského test ‐ Kdo je vlastně autorem? – Charles Babbage (1791‐1875) – výstřední britský génius, syn bohatého britského bankéře » objevy: rychloměr, lapač krav u lokomotiv, informace z letokruhů, první tabulky úmrtnosti, jednotné poštovné pro danou zemi, …

• objevil asi roku 1854


– nepublikoval, objeveno později » ? projekty nechával nedokončené, závěry nepublikoval (flegmatik) » ? v té době krymská válka, britská rozvědka měla převahu nad Rusy

– Friedrich Wilhelm Kasiski (1805‐1881) – důstojník pruské armády

• publikoval 1863 – „Die Geheimschriften und die Dechiffrirkunst“ » „Tajné šifry a umění je dešifrovat“

– Charles Babbage (1791‐1875) – výstřední britský génius, syn bohatého britského bankéře » oženil se → otec ho vydědil – nedovedl uvést do života většinu svých projektů

• od roku 1821 – matematické tabulky (navigace, technické výpočty) až tisíce chyb » spolu s astronomem Johnem Herschelem » „Kéž by Bůh dal a tyto výpočty mohla pohánět pára!“ © Květuše Sýkorová

• roku 1823 – navrhl tzv. Difference Engine No. 1. » obrovský kalkulátor sestávající z 25 000 mechanických součástek » měl být postaven za vládní peníze

• 10 let nato – sestavil nový plán a zahájil práce na Difference Engine No. 2. » už bez podpory vlády, příliš nákladný

• Kasiského test – pozorování pro periodický klíč:


• Vyskytuje‐li se nějaký bigram xy v otevřeném textu dvakrát a vzdálenost mezi oběma výskyty je násobkem délky klíče, • pak je v obou případech zašifrován stejným bigramem cd. – posunutí jsou totiž definována stejným bigramem kl klíče » klíč: k l . . . . . k l » o.t.: xy . . . . . xy » š.t.: cd . . . . . cd

– Friedrich Wilhelm Kasiski • vysloužilý důstojník pruské armády

• Kasiského test – postup: • odhad délky klíče – v š.t najdeme všechny bigramy, které se vyskytují aspoň dvakrát » spočteme jejich vzdálenosti – číslo, které je nejčastěji dělitelem těchto vzdáleností, je pravděpodobná délka klíče


• pozor! – opakovaný bigram v š.t. může vzniknout i náhodně » některé vzdálenosti opakovaných bigramů nemusí být násobkem délky klíče

• Kasiského test – postup: • odhad posunutí – š.t. napíšeme do tolika sloupců, kolik je odhadovaná délka klíče – spočítáme frekvenci jednotlivých znaků v každém sloupci zvlášť – pro každý sloupec najdeme takové posunutí abecedy, které nejlépe odpovídá frekvenci jednotlivých písmen v jazyce o.t.


• Pak už dešifrujeme text pomocí odhadnutých velikostí posunutí.

– tento test lze obecně použít i pro polygramy

• index koincidence IC – neformální definice: • Index koincidence dvou textů S a T nad stejnou abecedou A je pravděpodobnost, že se v obou textech vyskytne stejný znak na stejném místě.


– definice: • Jsou‐li … a … dva texty téže délky nad stejnou abecedou A, • pak definujeme index koincidence těchto dvou textů jako ∑

, – kde » »

, , ,

,

je Kroneckerovo delta dvou proměnných 1 ↔ 0 ↔ zdroj: http://www.karlin.mff.cuni.cz/~tuma/

• index koincidence IC – definice:


• Jsou‐li … pravděpodobnosti výskytů jednotlivých znaků abecedy A v textu S a • jsou‐li … pravděpodobnosti výskytů jednotlivých znaků abecedy A v textu T, • pak očekávaná hodnota indexu koincidence těchto dvou textů je ∑ , ·

– definice: • Jsou‐li frekvence jednotlivých písmen abecedy v nějakém jazyce L rovné … , • pak očekávaný index koincidence jazyka L (dvou libov. textů) se rovná ∑ , – nezávisí na textech S a T, ale pouze na pravděpodobnostech zdroj: http://www.karlin.mff.cuni.cz/~tuma/

• index koincidence IC – očekávaný index koincidence některých jazyků:


– Kullback 1976

• • • • • •

angličtina němčina francouzština španělština ruština náhodný text

6,61% 7,62% 7,78% 7,75% 5,29% 3,85%

(více znaků v abecedě) (=1/26)

– hodnoty závisí na použitých tabulkách a frekvencích jednotlivých písmen – u různých autorů se mohou lišit

zdroj: http://www.karlin.mff.cuni.cz/~tuma/

• index koincidence IC – očekávaný index koincidence některých jazyků:


– další autor

• • • • • • • • •

angličtina němčina francouzština španělština ruština italština čeština slovenština náhodný text

6,76% 8,24% 8,01% 7,69% 4,70% 7,54% 5,77% 5,81% 3,85%

(více znaků v abecedě)

(=1/26)

– u různých autorů se mohou lišit zdroj: http://www.karlin.mff.cuni.cz/~tuma/

• index koincidence IC – tvrzení:


• Jsou‐li dva otevřené texty S a T zašifrované polyalfabetickou šifrou za použití stejného klíče K a • označíme‐li takto obdržené šifrové texty C a D, • pak platí , , – i‐té místo: – a » , znaky otevřeného textu » , znaky šifrového textu » stejný klíč K → stejná permutace – je permutace → ↔ pro všechna i » tj.

,

∑

,

∑

,

,


• index koincidence IC – označení: • Je‐li T text délky n a r přirozené číslo, • pak označíme text, který dostaneme z T cyklickým posunutím o r míst doprava.

– definice: • Definujeme průměrný index koincidence dvou textů S a T stejné délky © Květuše Sýkorová

n nad stejnou abecedou A jako číslo

,

∑

,

– definice: • Definujeme průměrný index koincidence jednoho textu T délky n jako číslo

∑

,


• index koincidence IC – použití: • Máme šifrový text C délky n zašifrovaný nějakou polyalfabetickou šifrou – chceme najít pravděpodobnou délku klíče

• pro každé

2,3, … ,

1 napíšeme šifrový text do d sloupců

– texty ve sloupcích označíme ,

,…,


– spočítáme průměrné indexy koincidence

pro

1,2, … ,

– a pak spočítáme jejich průměr ∑

• Číslo d, pro které se vypočtená průměrná hodnota nejvíce blíží očekávanému IC jazyka o.t., je nejpravděpodobnější délka klíče. – blíží se IC pro násobky délky klíče – ostatní hodnoty d – blíží se hodnotě IC náhodného jazyka zdroj: http://www.karlin.mff.cuni.cz/~tuma/

• struktura – zpracována spousta statistických údajů • pro luštění jednoduché monoalfabetické substituce • pro každý jazyk a typ textů – frekvence jednotlivých znaků (monogramy) – frekvence skupin po sobě jdoucích znaků (bigramy, trigramy) – frekvence často se vyskytujících slov (polygramů)


– další charakteristiky jazyka: • • • •

průměrná délka slova nejčastější znaky (bigramy) na začátku slov nejčastější znaky (bigramy) na konci slov srovnání frekvence dvojic bigramů – např. XY a YX nebo OU a UO nebo ST a TS atd. zdroj: http://www.karlin.mff.cuni.cz/~tuma/

• struktura – luštění ze znalosti části otevřeného textu • pokud se může v otevřeném textu vyskytovat nějaké slovo, hledáme v šifrovém textu příslušný vzor


– například slovo PENICILIN bude zašifrováno jako ABXZCZDZX – nebo slovo DIVIZIJA je zašifrováno jako AZBZCZDE – apod.

– Strojové luštění šifer je v současné době značně rozpracované


• Jakobsenův algoritmus – určen pro řešení monoalfabetických šifer – tj. jednoduché záměny

• využívá frekvenci jednotlivých znaků + frekvenci bigramů – dvě matice řádu 26 » řádky a sloupce jsou označené písmeny abecedy

• referenční matice © Květuše Sýkorová

– hodnota

udává frekvenci bigramu XY v přirozeném jazyce

» vytvořena předem pro daný jazyk

• matice – hodnota

udává frekvenci bigramu XY v posuzovaném textu

» vytvořena pokaždé pro daný text


• Jakobsenův algoritmus – frekvence jednotlivých znaků • získáme počáteční permutaci – první „přiblížení“ ke klíči

• s její pomocí dešifrujeme šifrový text – dostaneme tak nový text » vytvoříme matici


– vzdálenost dvou matic • spočítáme jako sumu absolutních hodnot rozdílů čísel na stejných místech matice – tj. jako ∑

• ohodnocovací funkce – snažíme se ji minimalizovat přes všechny možné klíče » výstup algoritmu = permutace s nejmenší ohodnocovací funkcí



Nebojte se chyb. Čím více pravopisných chyb, tím těžší luštění.


kryptoanalýza druhy útoků proti klasickým šifrám příklad útok hrubou silou frekvenční analýza Kasiskiho metoda index koincidence Jakobsenův algoritmus

Recommend Documents