Česky
Kamil Dudka

Study

File detail

Name:Downloadkry.txt [Download]
Location: study > min
Size:61.9 KB
Last modification:2020-05-02 11:43

File content

Copyright (c)  2009  Kamil Dudka.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
Texts.  A copy of the license is included in the section entitled "GNU
Free Documentation License".

Klasická kryptografie
=====================
- používala se k utajení přenášených zpráv (důvěrnost)
- od roku 1948 začínáme mluvit o tzv. moderní kryptografii
    - používá se i pro jiné účely než utajení:
    - zajištění integrity zpráv (že nebyla po cestě měněna)
    - zajištění autentizace (odesílatele)
    - zajištění nepopíratelnosti (doručení)

- původní myšlenka: utajený algoritmus (ukázalo se, že nefunguje)
    --> používají se klíče

- šifrování: otevřený text --> šifrovaný text
- dešifrování: šifrovaný text --> otevřený text

- symetrické šifrování ... tajný klíč
- asymetrické šifrování ... veřejný/privátní klíč
    - algoritmy objeveny kolem roku 1970

kryptoanalýza - dešifrování bez znalosti klíče (lámání šifer)

kryptologie - věda o kryptografii/kryptoanalýze

šifra - algoritmus pro šifrování/dešifrování

Útoky
-----
    1. Ciphertext Only Attack (COA)
       - známe šifrovaný text
       - snažíme se zjistit klíč nebo otevřený text
       - jediný cíl klasické kryptografie

    2. Known Plaintext Attack (KPA)
       - známe šifrovaný text a odpovídající otevřený text
       - snažíme se zjistit klíč
       - někdy stačí část otevřeného textu
            - používají se různé teorie (pravděpodobnosti, ...)
            - různé věci můžeme vyloučit apod.

    3. Chosen Plaintext Attack (CPA)
       - viz. 2., ale obsah zprávy si můžeme zvolit
       - nepřináší velké zlepšení oproti 2.

Typy klasických šifer
---------------------
    1. steganografické postupy
       - ukrytí textu uvnitř jiného textu
       - hlavní nevýhodou je výrazný nárůst objemu dat

        watermark - ukrytí informace uvnitř obrazu (vodoznak)


    2. substituční šifry - nahrazení znaků (symbolů) jinými znaky (symboly)

        Freemason cipher - nemá klíč, ale tabulku

        Caesarova šifra - k ordinální hodnotě každého znaku se přičte
                          konstanta
                        - snadný útok frekvenční analýzou (histogram)

        Monoalfabetická substituční šifra
        - jedna tabulka pro celý text
        - klíčem je permutace písmen abecedy
        - prostor klíče je 26!
        - problém: invariantní k frekvenci znaků (a jiným vlastnostem jazyka)
            --> invariantní vzhledem k monoalfabetické substituci
            - kliky
            - digramy, trigramy
            - vzorky (patterns) --> metoda pravděpodobného slova

    3. transpoziční šifry - mění pořadí znaků v textu (typicky pomocí nějakého
                                                       geometrického obrazce)

--
security through obscurity - něco je bezpečné díky tomu, že o tom nikdo neví
                             (a jenom do té doby dokud to neví)

Kerckhoffův princip
-------------------
- utajování šifrovacího algoritmu nesmí být součástí bezpečnostního konceptu
- předpokládá se, že útočník zná všechny detaily šifrovacího algoritmu
- jediná utajovaná věc je klíč

Zapamatovatelný klíč
--------------------
- klíčem je slovo nebo jen několik slov (keyphrase)
- klíč, který si člověk dokáže zapamatovat po dlouhou dobu

Zvýšení odolnosti monoalfabetické šifry
---------------------------------------
    1. uříznutí vrcholů tabulky frekvencí (homofonní šifry)
       - frekventovaná písmena šifruje jako různé symboly
       - náhodný výběr z několika variant (problém se slovem "náhodně")
       - lze zobtížnit vkládáním symbolů, které nemají význam
       - nomenklátor (16. stol.)

    2. šifrování skupin znaků (polygramové šifry)
       - šifrovací tabulka je mnohem objemnější
       - obvykle pro dvojice/slova, pro trojice znaků silně nepraktické

    3. polyalfabetická substituční šifra
       - pro každý znak zprávy použiji jinou substituční funkci
       - výrazné zlepšení (hlavně odolnosti proti frekvenční analýze)

Kódová kniha
------------
- monoalfabetická polygramová/homofonní šifra
- vypadala skutečně jako kniha
- je bezklíčová (samotná kniha je klíč)

Playfair
--------
- digrafická substituce (šifruje dvojice písmen)
- matice 5x5 (znaků je 26 --> 'j' se nepoužívá)
- matice je chápána jako torus (spojení řádků/sloupců do válce)
- alg.:
    1. pokud se digram nachází v jednom řádku, každý znak digramu se nahradí
       znakem od něj vpravo

    2. podobně pro sloupce ... dolů

    3. jinak je znak nahrazen znakem ve stejném řádku, ale ve sloupci druhého
       znaku

- problém s dvojicemi stejných znaků
- výhody: rozbíjí frekvenční analýzu znaků

Vigenerova šifra
----------------
- první úspěšná polyalfabetická šifra
- vychází z Caesara
- klíč je iterován za sebou (musí být dostatečně dlouhý)
- Vigenerova tabulka je veřejná (aplikace modulo 26)
- existovalo několik variant
    Autokey - doplnění klíče otevřeným textem místo iterace

- prolomení:
    1. nalezni délku klíče
    2. nalezni písmena klíče jedno po druhém
            délka klíče 8 --> 8 monoalfabeticky zašifrovaných zpráv

- zjištění délky klíče:
    A. Kasiskiho test

    B. Test koincidence
    - počítá se index koincidence (pro angličtinu asi 0.065)
    - index je invariantní vzhledem k monoalfabetické substituci
      (ne vůči polyalfabetické)

Vernamova šifra (One Time Pad)
------------------------------
- jedinná(?) z klasických šifer, která se používá až dodnes
- používala se k šifrování telegrafních zpráv (1917)
- polyalfabetická šifra *bez opakování klíče*
- používají se dvě pásky: páska se zprávou, klíčová páska
- mezi páskami se provádí XOR (který se tenkrát nazýval jinak)
- klíčová páska musela být na obou stranách stejná a stejně synchronizovaná
- nevýhoda: klíčovou pásku lze použít pouze jednou
- klíč musí být zcela náhodný

- používalo se v systému ETCRRM
    - spojení Bílého domu s Kremlem za dob studené války
    - klíčové pásky se doručovaly diplomatickou cestou
    - malý objem přenášených dat

- také v systému DEINSTAR
    - převod na číselné symboly
    - přičtení klíče k číslům
    - nesplňovalo všechny požadavky Vernamovy šifry
      (zejména náhodný charakter klíče)

- šifra Autokey není Vernamova šifra!!

PRNG
----
- aby nebyl potřeba nekonečně dlouhý šifrovací klíč, přenese se pouze
  inicializační vektor
- zbytek se generuje generátorem pseudonáhodných čísel
- na obou stranách se generují stejná "náhodná" čísla
- nazývá se proudová šifra
- také není Vernamova šifra

Transpoziční šifry
==================
- v době mechanických šifrovacích strojů se prakticky nepoužívaly
- v době počítačů se používá jako stavební kámen jiných šifer

Scytale
-------
- používala se v Řecku (mechanizovaná)
- papírová páska se namotala na klacek
- na ni se vodorovně napsala zpráva (rovnoběžně s klackem, kolmo na pásku)
- potom se páska poslala bez klacku
- příjemce musel pásku namotat na klacek o stejném průměru
    klíč ... průměr klacku

Rail Fence
----------
- viz. obrázek (taková zubatá čára)
- jednoduchá šifra, snadno prolomitelná
- klíčem je permutace řádků

Sloupcová transpozice
---------------------
- matice
- zprávu napíšu po řádcích
- potom vytáhnu jednotlivé sloupce v *jiném* pořadí (další permutace)
- šifra velmi slabá, proto se používala dvojitá sloupcová transpozice
    - při druhém průchodu musím použít jiné rozměry matice
    - nebo rozměry transponované matice

Složené šifry
-------------
- něco zašifruji vícekrát
- pro jednotlivé průchody lze použít různé šifry (různě složité)
- není příliš přínosné pro monoalfabetické šifry (útočník si ani nemusí
  všimnout, že je zpráva šifrovaná vícekrát)

- přínosné pro kombinaci transpoziční/substituční šifry
  (vznikne nová, silnější šifra)

Rotorové stroje
===============
- prováděly polyalfabetickou substituční šifru
- klíče o "nekonečné délce" ... klíč se nesměl opakovat za dobu životnosti
  šifrovacího stroje

- tři základní přístupy:
    1. horizontálně posouvaná abeceda
    2. vertikálně posouvaná abeceda
    3. rotovaná abeceda - diagonálně pokračovaná
                        - vznikne kombinací 1. a 2.

    - mrknout se na obrázky znázorňující implementaci
      (lineárně rozvinutý rotor)

    - kontakty jedné strany rotoru provádí posuv 1.
    - kontakty druhé strany rotoru provádí posuv 2.
    - dohromady vytváří rotovanou abecedu

- rotorů se umístí několik vedle sebe (funguje na podobném principu jako
  mechanické počítadlo, e.g. vodoměr)
- šifrovaný "znak" jde sériově přes všechny rotory
    - provádí se několik monoalfabetických substitucí
    - výsledkem je jedna monoalfabetická substituce, která se ale s každým
      znakem mění --> polyalfabetická substituce

ENIGMA
------
- nejznámější rotorový stroj
- používal se ve WW2
- pro pozemní účely se používala 3-rotorová
- na ponorce byl 4. rotor, tzv. shark

- klávesnice s 26 znaky, displej s 26 žárovkami
- navíc propojovací deska, která prováděla monoalfabetickou substituci
    (vylepšení)

- další vylepšení: reflexní rotor, který má kontakty jenom z jedné strany
    (vrací signál zpátky)
    --> ušetření rotorů (pro 3 rotory se provádí transformace 7x)
    --> zavádí zásadní chybu (písmeno nemůže být šifrováno samo na sebe)
    --> stejnou Enigmou lze šifrovat i dešifrovat (podívat se na vztah!!)

- klíč se skládal ze 4 částí:
    1. pořadí rotorů /Walzenlage/

    2. počáteční natočení rotorů /Grundstellung/
       - jediná část klíče, která se měnila pro každou zprávu

    3. pootočení číslic na rotoru /Ringstellung/
       - nastavuje offset

    4. zapojení propojovací desky /Steckerverbindung/

- možných propojení rotorů je (26!)^3, ale to je na všech vyrobených strojích
  stejné

- Enigma bez propojovací desky lze prolomit hrubou silou
    - i tužka/papír ve více lidech
    - založené na pravděpodobnosti (pravděpodobné slovo)
    - předpokládáme, že se točí nejrychlejší rotor a další dva stojí (p=0.85)
    - podívat se na Batonův útok

- způsob provozu
    - denní klíč distribuovaný pomocí kódové knihy
    - každá zpráva začíná přenosem klíče zprávy
    - pro zamezení přeslechu se posílal 2x (chyba)
        --> toho využili studenti kryptografie z Polska
        - zapisovali cykly znaků
        - délky cyklů jsou nezávislé na nastavení propojovací desky
        - vyrobili katalog (trvalo jeden rok)
        - potom Němci změnili reflektor a katalog byl k ničemu
        - díky tomu vytvořili "mechanický katalog"

- kontrola cribu:
    - využívá chyby vzniklé zavedením reflexního rotoru
    - žádný znak nemůže být šifrován sám na sebe
    - prolomení založeno na pravděpodobné frázi
    --> řešení cyklu pomocí "Bomby"

ECM Mark II
-----------
- rotory se neposouvaly podle principu mechanického počítadla
- rotory se pohybovalo nezávisle pomocí elektromagnetů
- neexistovalo nic jako "nejrychlejší rotor"


Moderní kryptografie
====================
- rozlišuje se na symetrickou/asymetrickou (viz. ^)

Symetrický algoritmus
---------------------
- dva bloky:
    šifrovací ... otevřený text --> šifrovaný text
    dešifrovací ... šifrovaný text --> otevřený text

- používá se *tajný* klíč (neplést se soukromým nebo privátním)
- klíč nelze posílat stejnou cestou jako se posílají zprávy
- bezpečnostní funkce:
    - důvěrnost ... synonymum pro utajenost
    - autentizace ... ochrana proti podvržení zprávy
                      (prokázání totožnosti odesílatele zprávy)
    - integrita ... neporušenost obsahu (zavedením redundance)
    - nepopíratelnost ... příjemce prokazuje, že zprávu převzal
                          (obě strany ví, jak to bylo, potřebují přesvědčit
                          třetí, nezávislou, stranu - obvykle soud)
        - obvykle pomocí asymetrické kryptografie

- útoky:
    COA = Ciphertext Only Attack
    KPA = Known Plaintext Attack
    CPA = Chosen Plaintext Attack

    - útok silou (brute force attack, exhausting search)
    - útoku silou se zabraňuje zvětšením prostoru klíče
      (prodloužení doby útoku nad únosnou mez)
    - některé algoritmy dokáží útok silou (výrazně) urychlit

    - u asymetrických algoritmů existuje vždy rychlejší útok, než útok silou

    - dnes se jako rozumná hranice bere 80bit klíč (vzhledem k útoku silou),
      což se obvykle zaokrouhluje na 128bit

- v USA byla paušální vývozní licence pro algoritmy RC2, RC4, RC6 (40bit klíč)
- algoritmus DES ... 56bit klíč
    - poprvé prolomen v roce 1997 (tenkrát trvalo 4 měsíce)
    - dnes je nahrazen algoritmem AES

- tři kategorie útočníků
    1. samostatný útočník
    2. útočník se superpočítačem
    3. celý svět - úkol sehnat na internetu hodně PC pracujících pro mě se
                   dnes řeší běžně
                 - př.: útok "čínská loterie"

- symetrické algoritmy:
    DES - 56bit
    3DES - 112bit
    IDEA - 128bit, Švýcarský (neuznávají Američani), v dřívějších verzích PGP
    RC? - proměnlivá délka klíče
    Skipjack - 80bit, původně jako náhrada DES
             - měl existovat jenom v HW variantě, utajovaný
    AES = Advanced Encryption Standard, proměnlivá délka klíče

Asymetrický algoritmus
----------------------
- soukromý/veřejný klíč
- jeden z nich se použije jako šifrovací a druhý jako dešifrovací:
    důvěrnost - šifruje se veřejným, dešifruje se privátním
    autentizace, integrita, nepopíratelnost - šifruje se privátním klíčem,
                                              dešifruje se veřejným

- elektronický podpis ... autentizace, integrita, nepopíratelnost
- asymetrických šifrovacích algoritmů je výrazně méně
- nedají se vymyslet - většinou založené na nějakých matematických jevech
  (faktorizace čísel, knapsack, diskrétní logaritmus, eliptické křivky)

- asymetrické algoritmy:
    Knapsack - na základě problému Knapsack
             - první dvě verze algoritmu byly prolomeny
             - dnes už se nepoužívá

    RSA - využívá faktorizaci čísel
        - nejednoznačné zobrazení: $n = a \cdot b$
        - pracuje se s 1024bit čísly
        - je popsaný matematickým vzorcem
            --> proto nelze v Evropě patentovat
            - v USA byl ale patentován po dlouhou dobu

    DSA - někde označovaný jako DSS (Digital Secure Standard)
        - využívá diskrétní logaritmus
        - nejednoznačné zobrazení: $a = b^c$
        - lze použít pouze pro podpis, ne pro utajení

    DH = Diffie Hellman
       - také založený na diskrétních logaritmech
       - lze použít pouze pro utajení, ne pro podpis

    EC = Eliptic Curves
       - využívá eliptické křivky :-)
       - alg. nikdy nebyl patentován
       - pro dosažení stejné bezpečnosti stačí menší klíč než třeba DSA
       - dnes se příliš nepoužívá

- obvyklé délky klíčů: 768, 1024, 2048 (přepočítává se vzhledem k RSA)
- hlavním problémem asymetrické kryptografie je rychlost
  (nelze použít například pro zašifrování přílohy mailu)

Hašovací funkce
---------------
- také (message) digest, one way function, ...
- je na ni kladeno několik požadavků:
    - je aplikovatelná na argument "libovolné" velikosti
    - výstupní hodnota má konstantní délku
    - lze rychle spočítat
    - její reverzní funkce je výpočetně nezvládnutelná:
        1. F(x)=y, first x=?
        2. F(x')=F(x), x'!=x, x'=? (pro dané x)
        3. F(x')=F(x), x'!=x, x'=? (pro libovolnou kombinaci x, x')
           <-- narozeninový paradox
           --> Birthday attack

- výstupní délka hašovací funkce musí být dostatečná pro odvrácení útoku
  hrubou silou (128b se dnes jeví jako nedostatečné)

- implementace:
    MD2, MD4, MD5
    SHS (Secure Hash Standard)
    SHA

    - některé z používaných algoritmů se ukázaly jako že nesplňují podmínku 2.

Základní schéma
---------------
- dostatečně rychlá je pouze symetrická kryptografie
- tajný klíč je generován "opravdovým" generátorem náhodných čísel
- potom je zašifrován veřejným klíčem příjemce a poslán spolu se zašifrovanou
  zprávou

--> asymetrická šifra je použita pouze 1x pro libovolnou délku zprávy

- problém s doplněním tajného klíče na velikost bloku (nejsou dobré samé nuly)

Generování náhodných čísel
--------------------------
- generované hodnoty na sobě nesmí být ani částečně závislé
- nesmí být možné vynutit generované číslo (např. restartem serveru)
- nesmí být závislé např. na hodnotě data/času

- dobrým generátorem náhodných čísel je radioaktivní zářič (většinou není v PC)
- dalšími variantami jsou šumivé diody, dvojice pomalého/rychlého oscilátoru
- nebo také interakce s uživatelem (časy mezi stisky tlačítek, ...)

- v samotných procesorech většinou nejsou RNG
- někdy součástí čipové sady (většinou pomocí šumivé diody)

Zajištění integrity/autentizace
-------------------------------
- pošle se hash zprávy zašifrovaný privátním klíčem odesílatele
- je jednodušší provést útok na hašovací funkci, než na asymetrickou šifru
- útočník může změnit zprávu tak, aby měla stejný hash
    - např. v platebním příkazu změní číslo příjemce/částku
    - potom zbývá upravit položku "zpráva pro příjemce" tak, aby hash odpovídal
      původní zprávě

    --> jednoduchá úprava: šifrování pomocí "SSL"

- konkrétní implementace se dělí podle toho, jestli je komunikace
  spojovaná/nespojovaná

Blokové vs. proudové šifry
--------------------------
- proudová šifra: zpráva ... posloupnost bytů
    - používá se v mobilech pro šifrování hovorů
    - lépe se implementuje v HW

- bloková šifra: šifrování zprávy po celých blocích
    - z hlediska implementace problém
    - nekompletní bloky je potřeba "něčím" doplňovat
    - minimální velikost bloku je dnes 64bit, což zabraňuje slovníkovému útoku

Blokové šifry
-------------
- bloková šifra ... "krabička"
- blok většinou 64bit --> 2^64! možných zobrazení
- vstupem krabičky je klíč

Feistelova šifra
----------------
- není šifra, ale pouze princip
- předchůdce DES
- skládáním šifer se (někdy) zvyšuje bezpečnost
- substituční/permutační síť - jednotlivé bloky se střídají
- substituce rozdělena do několika bloků (omezení tehdejšího HW)

- princip - jeden blok šifry:
    - rozdělení bloku na dvě části
    - pravý se dá na výstup jako levý nezměněný
    - levý se xoruje s výstupem funkce a dává se na výstup jako pravý
      (vstupy funkce jsou subklíč a pravá, tj. nešifrovaná, část vstupu bloku)
    
    --> jeden blok je nepoužitelný (polovina dat nezašifrovaná)
    - Feistel neříká nic o funkci $F$, ale měla by skrýt vlastnosti
      zprávy/klíče

- otázkou je, kolik kol je potřeba (kolik je dostatečné, kolik je zbytečné)
- důležitou součásti šifry je blok pro generování subklíčů, který lze také
  implementovat různě (třeba i nešikovně)

Algoritmus DES
--------------
- symetrický alg. s tajným klíčem
- respektuje Kerckhoffův princip
- realizovatelný pomocí HW (1976)
- klíč měl 1bit paritu (64 bitů celkem) ... problém
    - oslabení klíče (poskytnutím informace útočníkovi)
    - parita byla v LSB --> klíč 0x0 a 0x1 dává stejný výsledek
    - parita se proto nepoužívá
    - samotný klíč je 56bit

- vychází z Feistelovy šifry (16 cyklů)
- byla přidána počáteční/koncová permutace (která bezpečnost nijak nezvyšuje)
- funkce F ... substituce/permutace, 
    - předtím se ale provádí tzv. expanze (32bit --> 48bit)
    - expanze také nepomáhá zvýšit bezpečnost

- bezpečnost zvyšují S-Boxy
    - tabulky indexované 6 bity, které dávají 4bit výstup
    - zásadní pro bezpečnost
    - nesmí být lineární funkce
    - NSA změnila S-Boxy oproti původní IBM implementaci, ale nezveřejnila jak

- různé způsoby, jak otestovat bezpečnost DES:
    DES Avalanche Efect (lavinový efekt)
    - kolik bitů výstupu se změní při změně jednoho bitu vstupu
    - kolik bitů výstupu se změní při změně jednoho bitu klíče

    útok hrubou silou - problém s 56bit klíčem --> 3DES ... 112bit klíč

- některé klíče jsou slabé
    - samé 0, samé 1, ...
    - různě slabé klíče
    - dohromady 64 slabých klíčů
    - lze řešit lookup tabulkou slabých klíčů
      (pokud se náhodou vygeneruje slabý, vygeneruje se nový)

- hlavní problém je s nezveřejněným návrhem S-Boxů
    - může přinášet výhodu při útoků pro toho, kdo je navrhl (NSA)
    - na druhou stranu náhodně vygenerované S-Boxy jsou méně bezpečné
    - problém s tabulkami naplněnými "kouzelnými hodnotami"
    - tato "zadní vrátka" nejsou použitelná pro 3DES

- nejlepší známý útok na DES je hrubou silou
- méně dobré algoritmy:
    diferenciální kryptoanalýza
    - dokáže prolomit 8-kolový DES ve dvou minutách
    - neporadí si s dobře zvolenými S-Boxy

    lineární kryptoanalýza
    - potřebuje $2^43$ známých zpráv
    - získá se 26bitů klíče, zbytek útokem hrubou silou
    - nelineární transformaci (danou tabulkou) nahradíme lineární (vzorečkem)
    - nechceme najít úplně ideální lineární transformaci, ale aproximaci
    - aproximace je tím lepší, čím více se liší pravděpodobnost od 0.5

EFF DES Cracker
---------------
- efektivní lámání DES
- víc než 40 000 procesorů
- implementace podle zákona nesměla být zveřejněna

--
- životnost šifry lze odhadnout podle délky klíče (Mooreův zákon)

Režimy blokových šifer
----------------------
- jak zakódovat zprávu, která je větší než velikost bloku
- 4 základní režimy, některé se používají dodnes
- platí pro všechny blokové šifry:
    ECB = Electronic CodeBook
        - zprávu rozdělím na bloky
        - každý blok šifruji nezávisle
        - délka zprávy musí být násobkem velikosti bloku
        - není dobré zprávu doplňovat nulami

        - není odolný vůči slovníkovým útokům
        - další možné útoky pomocí repetice/přeskládání bloku
          (příjemce nemá šanci poznat)

        - používá se pro šifrování dat o velikosti 2-3násobku bloku
        - jednoduchá implementace

    CBC = Cipher Block Chaining
        - každý blok zprávy je xorován předchozím zašifrovaným blokem
        - první blok je xorován inicializačním vektorem
        - někde se jako inicializační vektor používají samé nuly
          (není vhodné - IV nemusí být tajný, ale měl by být náhodný)
        - je třeba hlídat integritu IV

        - odolné proti slovníkovým útokům
        - odolné proti repetici/přeskládání bloku (vyžaduje redundanci)
        - díky inicializačnímu vektoru je výsledek zašifrování dvou stejných
          zpráv různý

        - zarovnávání musí být jednoznačné
          (např. doplním číslem, které udává zbytek do celého bloku)
          --> obvykle znamená prodloužení vždy aspoň o 1 byte

    CFB = Cipher FeedBack
        - proudová šifra (nevyžaduje zarovnání na velikost bloku)
        - samo-synchronizující
        - zbylých 48 bitů je zpětná vazba z cipher textu
        - DES pokaždé šifruje pouze 8 bitů cipher textu
        - mrhání výkonem (DES šifru musím pustit 8x více)

    OFB = Output FeedBack
        - stejné jako CFB, ale zpětná vazba se bere z výstupu DES

    CTR = Counter
        - šifrujícím blokem je čítač
        - podobné OFB
        - na obou stranách stejný čítač
        - funguje za předpokladu, že počáteční hodnota čítače je náhodná
        - např. šifrování disku (hodnotou čítače je číslo sektoru)
        - útok vede přes vynucení hodnoty čítače

    EDE = Encrypt-Decrypt-Encrypt
        - používá se pro DES
        - neslouží k šifrování více bloků, ale k prodloužení klíče
        - 3DES, DES-EDE
        - 3DES zvětší efektivní velikost klíče na 112bitů
        - (de)šifruje se 3x (enc. K1, dec. K2, enc. K1)

        - musí se šifrovat 3x, na 2x šifrování existuje útok
          "meet-in-the-middle"
        - složitost útoku $2^{n+1}$
        - útok se vede současně shora a zdola
        - v prvním kole (bloku) mohou být nějaké false-positives
        - dostanu množinu kandidátů, které postupně vyřadím podle pár dalších
          bloků

IDEA = Internation Data Encryption Algorithm
--------------------------------------------
- není mezinárodní standard, vyvinuto ve Švýcarsku
- použita v prvních verzích PGP
- rozzlobilo Americkou státní zprávu (nedovolili používat)
- nejsou žádné S-boxy (žádná zadní vrátka)
- navržena od začátku jako softwarová (efektivní výpočet)
- založena na Feistelově šifře
- subklíč vytvořen pomocí bloku "key expansion" ze 128bit klíče
- pořád funkční, nejsou známy útoky
- v profesionálních aplikacích se nepoužívá (není standardizován)

Blowfish
--------
- šifruje 64bit bloky
- proměnná délka klíče (až do 448bitů)
- skoro Feistelova šifra
  (druhá část se nepouští přímo, ale XORuje se s subklíčem)
- používá S-boxy, které se počítají podle klíče
- také není standardizována

TEA = Tiny Encryption Algorithm
-------------------------------
- 64bit blok, 128bit klíč
- nízké požadavky na HW, 32bit aritmetika (stačí 8bit procesor)
- proměnný počet kol
- v každém kole používá slabou funkci
    --> je potřeba větší počet kol

AES = Advanced Encryption Standard
----------------------------------
- navržen jako náhrada DES (trochu později než se čekalo)
- opak TEA, nehledíme na požadavky, cílem je bezpečnost
- vznikla na základě výběrového řízení z alg., který se původně jmenoval
  Rijndael
- standardní délky klíčů omezeny na 128, 192 a 256bit (10, 12 a 14 kol)
- v každém kole:
    1. ByteSub (něco jako S-box) - nelineární, ale reverzibilní krok
    2. Shift Row - uspořádání do matice, posun
    3. Mix Column (násobení matic)
    4. Add round key (XOR subklíče s blokem)

- pro dešifrování nelze použít stejný HW
    - některé bloky musí být invertované
    - jiná tabulka pro ByteSub


Proudové šifry
==============
- hodně šifer z klasické kryptografie bylo proudových
- dělí se na synchronní a samo-synchronizující:
    (pozor - není úplně intuitivní)

    synchronní
    - pseudonáhodná posloupnost (key stream) je nezávislá na zprávě
    - šifrovaný text je obvykle XOR s key stream

    samo-synchronizující proudové šifry
    - každý byte zprávy je závislý na pevném počtu předcházejících
    - schopnost "resynchronizace"
    - pokud objevíme narušení, nesnažíme se (částečně) opravovat
    - může jít o pokus o útok na šifru
    - př.: Autokey, DES v CFB módu

Generátory PRNG
---------------
- generování pseudonáhodné posloupnosti
- na základě semínka / inicializačního vektoru
- př.: lineární kongruentní generátor ("semínko" je seed)

LFSR - Linear Feedback Shift Registers
--------------------------------------
- posuvný registr
- Tap sequence ... zpětná vazba (XOR buněk registru) se nasune do registru
- maximální perioda ... tabulky primitivních polynomů
- na KPA útok je třeba $2n$ bitů (v čase $O(n^3)$)
- $2n$ bitů jednoznačně určuje zpětné vazby
- lze použít jako základní stavební kámen pro konstrukci bezpečnějších alg.
  (kombinované generátory)
- v praxi jsou tvořeny generátory pomocí 3 až 4 LFSR

Stop-and-Go generátory
----------------------
- také kombinovaný generátor založený na LFSR generátorech
- na nějakou dobu zastavím (některému generátoru) hodiny
- lidská tvořivost může být veliká...

A5
--
- používá se k šifrování hovorů v GSM
- založený na 3 LFSR (XOR)
- existují různé varianty (je jich 16, používají se 3):
    A5/0 - nešifruje se
    A5/1 - pro běžné hovory (útok trvá asi 1minutu na PC)
    A5/2 - oslabená verze šifrovacího alg. pro rozvojové státy

Proudová šifra Bluetooth
------------------------
- délka klíče 128bitů
- útok vede přes "rozpárování" dvojice zařízení
- přesvědčíme zařízení, že není zpárované a snažíme se vyvolat párování

Celulární kryptografie
----------------------
- algoritmy jsou 3:
    1. zajištění důvěrnosti
    2. zajištění autentizace
    3. správa klíčů (?)

PKZIP
-----
- algoritmus, který šifruje komprimovaná data
- proudová šifra, bere text po bytech
- používá se operace CRC32, 3 kouzelná čísla, násobení/sčítání
- návrh vypadá jako zoufalství
- prolomení ale není triviální, časová složitost je $2^27$

RC4
---
- nejjednodušší proudová šifra (jako TEA u blokových)
- název podle Ron rivest Cipher #4
- cifra používá stupidní mechanismy
- S-box s 256 položkami po 1 byte (posloupnost 0..255)
- během činnosti algoritmu se položky prohazují
    --> permutace (ale promíchání je dosti slabé)

- alg. má fázi inicializace (naplnění S-boxu)
- pole se naplní bity klíče
- pokud je klíč krátký, tak se opakuje

- lze snadno implementovat v mikrokontrolérech
- šifra nezajišťuje integritu (stejně jako jiné proudové šifry)

Problémy proudových šifer
-------------------------
- je potřeba vhodně zvolit inicializační vektor
- je potřeba explicitně hlídat integritu zprávy
    <-- častý cíl útoku (viz. PKZIP)

- méně odolné proti chybě programátora než blokové šifry


Asymetrická kryptografie
========================
- přecházíme do jiného světa, kde platí jiné zákony a hodně z toho, co říkal,
  platit nebude :-)

- objevena kolem roku 1976 (Diffie/Hellman) - oba ještě žijí (TODO: update)
- tenkrát se nevědělo, jestli je asymetrická kryptografie realizovatelná

- důležitá vlastnost
    - představme si asymetrickou šifru jako "krabičku"
    - mám k dispozici veřejný klíč (příjemce), vstup a výstup
    - ale nejsem schopný s využitím všech informací (+ mezikroků) šifrovaný text
      dešifrovat

- navíc z veřejného šifrovacího klíče nesmí jít vypočítat soukromý (jasné)
- aplikace:
    - šifrování
    - elektronický podpis
    - výměna klíčů (key exchange)

- úvod do algoritmů: viz. ^
- většinou používá modulární aritmetiku (lze snadno vyrobit HW akcelerátor)

IFC = Integer Factorization Cryptography
----------------------------------------
- problém představuje kvantový počítač

    RSA - reverzibilní (lze použít pro podpis i šifrování)
        - délka klíče se vyjadřuje vzhledem k algoritmu RSA, který chápeme
          jako etalon

DLC = Discrete Logarithm Cryptography
-------------------------------------
- bezpečné, pokud lze obtížně nalézt diskrétní logaritmy

    FFC = Finite Field Cryptography (DSA, Diffie/Hellman)

    ECC = Eliptic Curve Cryptography


--
- průběžně se zkoumá, jak dlouhé klíče jsou ještě bezpečné
- je potřeba počítat s délkou klíče, která není prolomitelná za dobu
  životnosti vyvíjeného systému (může být i několik desítek let)

Modulární aritmetika
--------------------
- provádím jednoduché aritmetické operace
- nad výsledkem "se provádí" operace modulo
- výhodou je, že výsledná čísla nejsou příliš velká

- důležitý pojem je kongruence:
    "dvě čísla $a$ a $b$ jsou kongruentní modulo $n$"
    (označuje se...)
    (platí...)

    (multiplikativní inverze hodnoty $a$)

Algoritmus RSA
--------------
- založený na problému faktorizace velkých čísel
- pozn.: všechny asymetrické algoritmy jsou blokové šifry
- skládá se ze dvou částí

- hodnota $n$ ... veřejný modulus
    --> žádná hodnota, která vznikne nemůže být větší než $n$

- soukromý/veřejný exponent
    - veřejný teoreticky libovolný, ale používají se standardní hodnoty
      (v praxi omezeno na dvě hodnoty)
    - privátní omezit nelze ... to by všichni mohli používat jenom dva
                                soukromé klíče

- činitele $p,q$
    - problém nalezení náhodného prvočísla
    - lze dokázat, že v každém "nějakém" intervalu je prvočíslo

    - musíme se zamyslet nad tím, jestli bude alg. fungovat, když
      $p,q$ nebudou prvočísla
      --> bude fungovat, ale bude snadnější jej prolomit

    - požadavek na prvočíslo je požadavek bezpečnosti, ne nutnosti
    - používá se generování prvočísel s určitou pravděpodobností

    - musí platit vztah: $d \times e mod (p-1)(q-1) = 1$

    - veřejný klíč ... $(n,e)$ (?)
    - privátní klíč ... $(n,d)$ (?)

- postup CRT
    - nějaký Čínský nesmysl
    - umožňuje urychlit výpočet
    - nepoužívá se, protože prodlužuje privátní klíč
    - $p,q$ se nezahazuje

- fáze generování klíčů může trvat různou dobu
    - hodně pomalá (řádově i sekundy)
    - nelze předem odhadnout dobu generování
    - rychlost se odvíjí od rychlosti generátoru náhodných čísel
    - není možné generovat za běhu v rámci protokolu :-)
    - existuje i HW podpora pro generování klíčů, ale není tak důležitá

- proces šifrování/dešifrování je stejný, což může působit problémy
    - dáme někomu něco podepsat a on nám to zašifruje
    - tyto problémy algoritmus nedokáže nijak řešit
    - je potřeba tyto situace pohlídat na vyšší úrovni

    - lze vyřešit dvěma páry klíčů (šifrovací, podepisovací)
    - jsou standardy, které to vyžadují
    - jsou standardy, které to nedovolují (protože s tím nepočítaly)

- příkladům musíme věřit
    - pracují s příliš velkými čísly (i když vstupní čísla jsou malá)
    - s tak velkými čísly má problém i kalkulačka

- modulární umocňování lze nahradit modulárním násobením (po každém násobení
  se provádí $mod n$)

- první algoritmus má problém
    - z doby výpočtu dokážeme spočítat/odhadnout, kolik bitů je jedničkových
    - dokonce může odhadnout které bity jsou jedničkové
      (podle spotřeby čipové karty)
    - "postranní kanály" ... něco přináší informaci aniž by se to
      předpokládalo (neplést s posranými kanály)

- problém se složitostí (3. mocnina)
    --> zdvojnásobení délky klíče nezdvojnásobí dobu vypočtu

- 1024bit klíč RSA odpovídá 80bit symetrickému klíči
    256bit AES ... 15360bit RSA
    (pozor, tento stav se s časem mění)

Útoky na RSA
------------
- pokud útočník umí rozložit $n$, na činitele $p,q$, může dopočítat soukromý
  klíč
- různé pokusy s optickými počítači
- kvantový počítač provádí útok v polynomiálním čase (předem vygeneruje
  všechna řešení)

- dále se útočník může pokusit uhodnout/najít hodnoty (p-1)/(q-1)
- důležitý je úklid (útočník může sledovat, co zbylo v paměti, ...)

- alg. funguje vždycky, ale pro některé hodnoty není bezpečný
    - např. pokud bychom měli hodnotu $e$ příliš malou
    - pokud bych použil $e=1$, tak jsem zprávu nezašifroval vůbec
    - také není dobré používat malé hodnoty $d$

Textbook RSA
------------
- blok šifrující algoritmem RSA
- existuje mnoho útoků na něj
- hodnoty je v praxi potřeba upravovat, aby bylo šifrování bezpečné

- jednoduchý útok na textbook RSA (web browser ... web server)
    - klient pošle zprávu: CLIENT HELLO
    - server pošle jako odpověď: SERVER HELLO (e, N)
      (součástí zprávy je náhodné číslo, veřejný klíč)
    - klient vypočítá náhodný klíč relace
      (klíč sezení zašifrovaný veřejným klíčem serveru)
    - klíč relace je 64bit, doplnění na délku klíče nulami je chyba

    - ve 20% případů je klíč rozložitelný na dva činitele, které jsou menší
      než $2^34$ (stačí okolo 5ti pokusů)

    - klíč lze nalézt v čase $2^34 \cdot 34$, ne $2^64$
    - způsobeno tím, že šifrovanou hodnotu lze chápat jako číslo

- jiný útok na textbook RSA
    - přimějeme odesílatele, aby podepsal (dešifroval) naši zprávu
    - sl. 25/114
    - s náhodným $R$ zacházíme stejně jako se zašifrovanou zprávou

    - vygenerujeme náhodnou hodnotu $R$
    - zašifrujme veřejným klíčem ($e$)
    - vynásobíme hodnotou $C$
    - dostaneme $Y$
    - potom necháme podepsat privátním klíčem ($d$)

    - z $R$ uděláme převrácenou hodnotu
    - zašifrovaný výsledek (privátním klíčem) vynásobíme převrácenou hodnotou
    - dostaneme požadovanou hodnotu

    - funguje díky modulární aritmetice
    - nežádoucí vlastnost (oběť neví, že podepisuje to, co nechce)
    - někdo říká, že to je žádoucí, a staví na tom různé protokoly

    --> algoritmus RSA nelze používat v režimu textbook

- před spuštěním algoritmu RSA se musí provést předzpracování
- většinou ve formě zarovnání/doplňování (padding)

PKCS = Public Key Cryptographic Standard

PKCS1 V1.5
----------
- rozlišuje formát zprávy pro šifrování a pro podpis
- proti mechanismu se objevily nějaké útoky (neznamenaly ale jeho konec)
- použité v SSL
- útok na PKCS1 V1.5:
    - pokud není prvních 16bitů "02", server odpoví chybou
    - tím poskytuje útočníkovi 1bit informaci
    - útočník se může dozvědět 1bit hodnot, kolik chce
    - vhodně volenými "náhodnými čísly" lze postupně testovat jednotlivé bity
      zašifrované zprávy

CCS = Choosen Ciphertext Security

PKCS1 V2.0
----------
- nová funkce pro předzpracování:
    OAEP = Optimal Asymmetric Encryption Padding

- v praxi se používají dvě hašovací funkce
- původní myšlenka: náhodná orákula
    - krabice, do kterých vstoupí nějaká hodnota a vyleze jiná hodnota
    - náhodné orákulum používá generátor náhodných čísel
      (na rozdíl od hašovací funkce)

    - již vygenerované náhodné hodnoty se ukládají do "db"
    - pokud se někdo zeptá 2x na stejnou hodnotu, vrátí se již použitá

    - mezi vstupní hodnotou a výstupní hodnotou není žádný vztah
    - na rozdíl od hašovací funkce orákulum funguje na oddělených koncích různě

- opět poskytuje útočníkovi jednobitovou informaci (různé chybové kódy)
- i pokud vrací stejné chybové kódy, může útočník měřit dobu zpracování
  (postranní kanály)

Implementace RSA
----------------
- jako měřítko se používá počet bitů (ne číslic)
- základní operací je modulární umocňování
    - lze převést na modulární násobení
    - mohou přetékat mezivýsledky

- binární umocňování: zleva-doprava / zprava-doleva
- zprava-doleva
    - vypočtou se pomocné hodnoty: X, X^2 mod n, X^4 mod n, X^8 mod n, ...
    - pod ně se nasypou jednotlivé bity
    - počet násobených hodnot se rovná počtu (jedničkových) bitů hodnoty

- zleva-doprava (funguje naopak...)

- binární umocňování lze řešit HW
- je potřeba dávat pozor na postranní kanály
- algoritmy s různou složitostí (podívat se na přehled)

Knapsack
--------
- jeden z nejstarších algoritmů
- založený na problému Knapsack (NP-úplný problém)
- problém nemusí být NP-složitý za všech okolností
- je potřeba vhodně zvolit množinu prvků

    Superincreasing knapsack
    - každý další prvek má větší hodnotu než součet dvou předchozích
    - lze řešit v lineárním čase
    --> privátní klíč

    Hard kanpsack
    - generuje složitý knapsack problém z jednoduchého
    - pomocí operace modulo: $w \cdot s_i mod n$, $n$ je prvočíslo
    --> veřejný klíč

- lze použít pro šifrování
- teorie elektronického podepisování knapsackem nejsou dotažené do konce
- je otázka, které (všechny) hodnoty je potřeba tajit před útočníkem

- útoky: výpočet privátního klíče z veřejného (s určitou pravděpodobností)
- šifrovací alg. nemá nic společného s původním optimalizačním problémem

- dešifrování ... "útok silou" s lineární složitostí
- alg. začíná být bezpečný někde okolo 200 prvků

DSA = Digital Signature Algorithm
---------------------------------
- založený na problému diskrétních logaritmů
- konečná cyklická grupa o velikosti $n$
- grupa je generovaná generátorem $g$
- násobení je abstraktní operace (např. násobení polynomů)

- problém diskrétního logaritmu:
    - je potřeba najít odpovídající exponent
    - pro útočníka dostatečně obtížný

- navržen jako standard pro digitální podpis
- NIST předepisuje některé parametry alg., které je potřeba dodržet
- nelze použít pro šifrování (někdo říká, že lze, ale nepoužívá se)
- rychlejší než RSA při podepisování, pomalejší při ověření podpisu
  (výhoda i nevýhoda)

- těsná vazba na hašovací funkci SHA (160bit)
- na rozdíl od RSA vyžaduje RNG pro podepisování
- podpis je dvojice čísel $(r,s)$
    - každé získám jinak
    - podívat se jak

    - v této fázi se nepracuje s podepisovanou zprávou (výhoda proti RSA)
    - lze si proto připravit podpisy pro několik zpráv dopředu
      (a potom skladovat v "bezpečné paměti")
    - pro měření rychlosti podpisu DSA je potřeba rozdělit na dvě části

- útok vede vždy na diskrétní logaritmus
- bezpečnost je srovnatelná s RSA
- dalším slabým místem je RNG

Diffie-Hellman
--------------
- umí zajistit utajení, neumí elektronický podpis
- také problém diskrétních logaritmů
- nepoužívá se přímo k utajení zpráv
- umí ale vytvořit sdílené tajemství (klíč relace)
- jsme schopni zajistit důvěrnost, (autentizaci), integritu
- nepopíratelnost zajistit neumí
- jednodušší směr: umocňování

- účastníci dopředu nemusí mít domluvené vůbec nic
- pokud bude někdo komunikaci odposlouchávat, sdílené tajemství se nedozví
- veřejný modulus, hodnota $g$ (dopředu stanovené)
- vyžaduje kryptograficky bezpečný RNG
- alg. viz obrázek (jednoduché)

- základní varianta je nepoužitelná
- existuje útok Man in the middle
- proto je potřeba hlídat identitu stran (certifikáty veřejných klíčů)

- využití: tachograf podle směrnice EU (předpokládá se výměna klíčů v
  "bezpečném" prostředí)

EC = Eliptic Curves
-------------------
- křivky vytvořené ve 2D prostoru
- typy křivek jsou součástí standardu
- podle ID vybereme, která křivka se použije
- operace sčítání, operace zdvojnásobení (podívat se na obrázek)
- nad tímto aparátem se implementuje algoritmus podobný diskrétním logaritmům

- poskytují vyšší míru bezpečnosti na 1bit klíče
- na stejnou míru bezpečnosti stačí menší výpočetní výkon
- další výhodou je, že nejsou (a nikdy nebyly) patentované


Hašovací funkce
===============
- dělí se na dvě velké skupiny
    1. neklíčované - to o čem jsme doteď mluvili (default)
    2. klíčované - do funkce vstupuje také klíč

- neklíčované dříve označované také:
    MDC = Manipulation Detection Codes
    MIC = Message Integrity Codes

- klíčované:
    MAC = Message Authentication Codes
        - může být založená na neklíčované hašovací funkci
        - může být založená na symetrické šifře
        - stačí menší velikost hash (64bit)

- dvě kategorie hašovacích funkcí:
    OWHF = One Way Hash Function
    CRHF = Collision Resistance Hash Function (zpřísnění předchozího)

- úvod viz. ^

Iterovaná hašovací funkce
-------------------------
- dostává na vstup také část výstupu
- výstup o pevné délce
- nad výstupem je možné provádět transformaci (není nutné)

- nutné je provádět předzpracování vstupu
    - zarovnání (padding) na násobek velikosti vstupního bloku
    - někdy se používá připojení délky (explicitně uložena délka hašovaných
      dat na konci bloku)
      --> Merkle-Damgardovo zesílení (aby někdo nemohl doplnit bloky)
      --> nemůžeme už ale použít pro vstup libovolné délky

Merklova meta-metoda
--------------------
- jakákoliv kompresní funkce odolná proti kolizím se dá rozšířit na CRHF
- (?)

Narozeninový útok
-----------------
- složitost útoku: 2^(n/2)
- lze použít pouze za určitých okolností
- používá se sémantický ekvivalentní zpráva
    - změna něčeho, co nemá význam
    - např. "zpráva pro příjemce" na platebním příkazu
    - vytvoříme dvojici přátelská/nepřátelská dohoda

- na konec hašované zprávy se připojuje náhodné číslo v době podepisování

MD5
---
- vytlačil svého předchůdce MD4
- používá se často v prostředí internetu
- velikost hash je 128bit
- vstup se musí zarovnat na 512 bitů
- uvnitř je 40 cyklů
- dnes už není dostatečně bezpečný

SHA-1
-----
- vykradená MD5
- výstup prodloužen na 160 bitů (kompatibilita s DSA)
- počet cyklů je 80
- přidala se na konec délka zprávy
- zatím se nepodařilo nalézt kolize algoritmu SHA1
- vzhledem k podobnosti s MD5 se očekává, že to je otázka několika málo roků

RIPEMD
------
- evropský hašovací alg.
- není moc rozšířený (o bezpečnosti alg. zatím nemůžeme moc říct)

Hašovací funkce z blokové šifry
-------------------------------
- různé varianty
- hašovaná data lze použít buď jako vstup nebo jako klíč blokové šifry
- zjistilo se, že to není správná cesta
  (útočník může přímo/nepřímo ovlivnit klíč)

MD2
---
- dnes se nepoužívá
- akumulační registr pro (mezi)výsledek
- vstup se rozseká na bajty
- každý bajt se prožene XORem a substituční tabulkou
- substituční tabulka z číslic Ludolfova čísla
- velmi úsporné na paměť a čas (používalo se v microkontrolérech)

MD4
---
- základ moderních hašovacích alg.
- 128bit výstup
- není odolný proti kolizím

MD5
---
- autor: Ron Rivest (MIT)
- není odolný proti kolizím
- normální iterační alg.
- napřed zarovnání na délku bloku, rozsekání na 512bit bloky
- kompresní funkce má 2 vstupy (512bit + 128bit --> 128bit)
- poslední hodnota už se nijak netransformuje a prohlásí se za výsledek
- používají se 32bit operace

SHA = Secure Hash Algorithm
---------------------------
- vznikla spolu s DSA
- vykradená MD5
- stavový registr prodloužen o jedno stavové slovo
- počet cyklů se zvýšil z 16 na 20
- přidaly se dvě tabulky
- alg. se v době vzniku jmenoval SHA

- později ho bylo potřeba upravit
    --> SHA-1
        (nebylo přesně zdůvodněno)

- útoky na MD5 ohrozily také SHA
- vznikla nová rodina algoritmů: SHA-2
    SHA-256
    SHA-384
    SHA-512
    (číslo udává velikost výstupu)

- nelze vydávat SHA-2 certifikáty (starší klienti nepodporují)

MAC
===
- různé výklady zkratky
- rodina hašovacích funkcí
- parametrizované klíčem (klíčovaná hašovací funkce)

- snadný výpočet, pokud známe klíč
- umí zpracovat vstup libovolné délky
- výpočetní bezpečnost

- zajišťuje autentizaci/integritu
- nezajišťuje důvěrnost/nepopíratelnost
- používá se ve starších bankovních aplikacích
  (ne v internetovém bankovnictví)

CBC MAC
-------
- šifra běží v módu CBC (?)
- použije se poslední blok výsledku
- zpravidla se vezme pouze jeho 32 bitů, zbytek se zahodí
  (v kryptografii neobvyklá věc)

- je potřeba počítat s dvěma typy útoků:
    1. útok na klíč - útočník se snaží spočítat klíč
                    - tady se ořezávání hodnoty MAC projeví pozitivně
                    - 128bit klíč se počítá špatně, protože existuje hodně
                      klíčů, pro které posledních 32 bitů sedí

    2. útok na hodnotu MAC
       - s určitou pravděpodobností dokáže útočník uhodnout hodnotu MAC

- útok "Existential forgery"
    - pokud útočník zná takovéto dvě dvojice: (x1, H1), (x2, H2)
    - TODO: zjistit, co znamená ((x1||z), M)
    - řeší se 3x zašifrováním výstupu

MAC vytvořené z MDC
-------------------
- pro některé protokoly je elektronický podpis velkým luxusem
- typicky protokoly pro vzdálenou správu síťových prvků
- je potřeba zabezpečit pouze proti modifikaci (?)
- používá se v IPSec, SSL

- je potřeba z neklíčované hašovací funkce vyrobit klíčovanou
- požadavek, aby každý bit klíče ovlivnil každý bit výstupu se stejnou
  pravděpodobností

- varianty secret prefix / secret suffix (ta druhá funguje lépe)

Envelopping
-----------
- základ metody HMAC

HMAC = Hash Function MAC
------------------------
- vyrobení klíčovaného hašovacího algoritmu z běžné hašovací funkce
- používá se "přihašování klíče"
- podívat se na obrázek
- samotný mechanismus HMAC nic neříká o tom, jestli musí být hašovací funkce
  bezkolizní (může/nemusí vadit)

Asymetrická správa klíčů
------------------------
- nesmíme dovolit, aby při zveřejňování byl nahrazen veřejný klíč jiným
  veřejným klíčem (jasné)

- jeden z důvodů, proč je potřeba řešit správu klíčů u asymetrické kryptografie
- není potřeba řešit důvěrnost, ale pouze autentizaci
- řeší se pomocí certifikátů (standard X509)
- doporučení CCITT X.509 má dominantní postavení
  (CCITT už neexistuje, nahradila ji organizace ITU)

- služba X.500 pro distribuce certifikátů zemřela a byla nahrazena službou LDAP

Certifikace veřejných klíčů
---------------------------
- certifikační autoritě se říká důvěryhodná třetí strana (což je ale obecnější
  pojem)

- vezme se veřejný klíč uživatele, jeho jméno a dokument se elektronicky
  podepíše --> vznikne certifikát

- také další užitečné hodnoty jsou v certifikátu:
    - vydavatel (CA)
    - sériové číslo (unikátní v rámci CA)
    - platnost
    - identifikace algoritmu (který bude veřejný klíč používat)

Strom CA
--------
- úplně dole (pod stromem) jsou uživatelé
- úplně nahoře (v kořeni) je kořenová CA
- může mít obecně libovolný počet úrovní
- uživateli potom stačí znát jediný veřejný klíč
  (kořenové certifikační autority)

- je potřeba ověřit několik certifikátů --> sestavení certifikační cesty

- certifikačních stromů dnes existuje větší množství
- jednotlivé certifikační stromy dnes nejsou schopny/ochotny se spojit

Obsah certifikátu X.509
-----------------------
- jazyk ASN = Abstract Syntax Notation (neříká, jak strukturu uložit v paměti)
- další standardy BER/DER (uložení datových struktur v paměti)
- tyto standardy se ve větší míře nikde jinde nepoužívají
- podívat se na struktury
- dva algoritmy:
    1. kterým je certifikát podepsán
    2. pro který alg. je určen veřejný klíč

    - obecně se mohou lišit

- sériové číslo je jedinečné v rámci CA
- dvojice sériové číslo / vydavatel tvoří jedinečnou dvojici na celé zeměkouli

- někteří lidé špatně chápou platnost certifikátu
- certifikát musí být platný v době podepisování dokumentu (ne v době ověřování)

Křížové certifikáty
-------------------
- slouží k propojení dvou nebo více certifikačních stromů
- stromy se propojují pomocí dvojice křížových certifikátů
- uživatelé potom mají pocit, jako by komunikovali v rámci jednoho stromu CA
- výrazně komplikují implementaci
- propojení nemusí být symetrické (tj. na stejné úrovni)
- tím se komplikuje sestavení certifikační cesty
  (už není problém s lineární složitostí)

Certifikační autorita
---------------------
- standard X.509 nedefinuje typy CA
- v praxi se používá kořenová CA, která je pro daný strom jedna
- potom se používají tzv. policy CA, které vydávají certifikáty pouze jiným CA
- nejníže jsou potom uživatelské CA, které vydávají certifikáty uživatelům

- CA by neměla provádět generování klíčů
- to může dělat jenom uživatel (jako *jediný* vlastník privátního klíče)
- při žádosti o certifikát se certifikační autoritě posílá prototypový
  certifikát (Privacy Enhanced Mail)
- prototypový certifikát se potom podepíše privátním klíčem
    ---> tzv. self-signed certifikát
    - podpisem potvrzujeme, že známe odpovídající privátní klíč
    - tohle v X.509 původně nebylo

- v praxi je potřeba oddělit certifikační a registrační autority:
    1. několik málo certifikačních CA někde v bunkru, dobře zabezpečených
    2. hodně registračních CA, kde si chodí lidi žádat o certifikát

Certifikát X.509
----------------
- původní verze je z roku 1988
- dnes se používá X.509 V3 z roku 1997
- umožňuje do certifikátu vkládat rozšíření (další položky certifikátu)
- každé rozšíření má UID, které se musí registrovat

- důležitá je nová položka usage, která říká, k čemu se může certifikovaný
  klíč použít

- součástí je také odkaz na certifikační politiku, podle které byl certifikát
  vytvořen

- X.509 V3 na rozdíl od původní verze nevyžaduje jméno ve tvaru DN
  (oddělené od X.500)

- další verze: X509 V4 (2000) ... atributové certifikáty

Rušení certifikátu
------------------
- např. při odtajnění privátního klíče
- nebo uživatel ztratí práva, která z certifikátu vyplývají
- teoreticky by mohl být prozrazen privátní klíč CA, ale nikdy se to nestalo

- seznam zrušených certifikátů se vydává periodicky (revocation list)
- v poslední době se objevilo on-line řešení pro zjištění zrušených certifikátů
- CRL je seznam neplatných certifikátů, kterým ještě nevypršela platnost
- delta CRL - jednou za čas pošleme celý seznam, potom se posílají změny v CRL
- CRL je náchylný na DOS

- OCSP = On-line Certificate Status Protocol
- internetový přístup k CRL (většinou nezabezpečený)
- má ale pouze informativní hodnotu a nelze použít jako důkaz
- stále náchylné k DOS útokům

Míra důvěry v certifikáty
-------------------------
- používají se 4 třídy, ale není standardizováno:
    1. pouze jedinečnost vlastníka
       - lze získat i anonymně
       - typicky pouze pro testovací účely

    2. identita vlastníka
       - vyžadujeme kontrolu identity třetí stranou
       - nevyžaduje se osobní kontakt
       - většinou notářské ověření
       - není příliš důvěryhodné

    3. vlastník osobně navštívil CA
       - reálně se rozpadá na několik podtříd
       - musí být kontrola dokladu totožnosti

    4. třída 3 + kontrola dalších informací v certifikátu
       - např. vlastník musí prokázat, že je jednatelem banky
       - kromě toho, že prokáže svoji totožnost

Elektronický podpis
-------------------
- pro některé lidi to není to samé jako "digitální popis"
  (v EU je potřeba rozlišovat)

- podle EU stačí napsat Hanáček na konec dokumentu a máme elektronický podpis
- digitální podpis je elektronický podpis, který je bezpečný
- dále se bude pod elektronickým podpisem myslet digitální

- musí zajišťovat autenticitu, integritu a nepopiratelnost
- funkce jsou dosti podobné manuálnímu podpisu
- elektronický podpis neřeší problém double-spendingu
  (množení elektronických peněz)

Bezpečnostní služby ISO 7498-2
------------------------------
- standard definoval víc věcí, než bylo potřeba
- standard už je asi 20let starý

- autentizace stroj-stroj
- řízení přístupu ... úlet

- důvěra
- integrita
- nepopiratelnost

PKCS = Public Key Cryptography Standards
----------------------------------------
- několik firem se domluvilo, začalo 1991
- začala firma RSA DSI, která už neexistuje

    PKCS #1 - RSA (vzorečky, formátování, základní schéma, rozšíření, ...)

    PKCS #7 - Cryptographic Message Syntax
            - máme krabičku, do které vstupuje klíč, otevřený text
            - standard definuje, jak zformátovat binární výstup, aby prošel
              mailem
            - příjemci stačí znát klíč, dokáže zjistit odpovídající alg., ...
            - také správa klíčů pomocí Diffie-Hellman

    PKCS #11 - jednotné API pro čipové karty a jiná zařízení
             - standard poměrně zbytečně složitý
             - navíc nereflektuje reálný svět
             - nepracuje vůbec s pojmem "soubor"

    PKCS #15 - snaží se vylepšit #11
             - už pracuje se soubory

- zbytek viz. sl. 32/80

Bezpečná elektronická pošta
---------------------------
- snaha dopisy kryptograficky zabezpečit
- existují dva konkurenční systémy
    PEM = Privacy Enhanced Mail (definována dokumenty RFC)
        - seriózní pokus o bezpečnou poštu, který zahynul
        - na rozdíl od PGP se napřed napsaly standardy a potom SW
        - umělo pracovat s certifikáty, ale tenkrát nebyly CA
        - součástí návrhu bylo vytvoření celosvětového stromu CA
        - zpracování má několik fází
            1. převod do kanonické podoby
            2. zabezpečení integrity, identity
            3. zašifrování zprávy
            4. konverze do textové podoby (base64)

        - později bylo vytlačeno S/MIME


    PGP = Pretty Good Privacy (téměř zakázané)
        - původně neuměl používat certifikáty veřejných klíčů
        - proto se nedal dobře používat v institucích
        - založený na síti důvěry
        - původně pevně dané algoritmy (IDEA, RSA, MD5)
        - komprese dat, kódování do textové podoby

        - autor PGP byl podstaven před soud za export zbraňových systémů
          (ale vyhrál)

S/MIME
------
- snaha minimálně zasahovat do stávající podoby elektronické pošty
- recyklace průmyslového standardu MIME
- aplikace standardů asymetrické kryptografie PKCS (#1, #7, #10)
- vznikly dva nové standardy:
    S/MIME Message Specification
    S/MIME Certificate Handling

- kde to jde, používá číselníky (např. pro šifrovací alg.)
- nepředepisuje, které algoritmy se mají použít; je hodně flexibilní
- pouze-podepsaná zpráva je rozdělená na čitelný text a podpis
  (čitelný text je vždy čitelný)

SSL
---
- protokol má charakter bezpečné trubky
- https = http + SSL
- původně navržené jako zabezpečení jakéhokoliv protokolu nad TCP/IP
- vyžaduje spolehlivou transportní vrstvu
- není skryto před aplikací (musí mít extra podporu)
- dva protokoly:
    1. SSL Handshake Protocol - vytvoření bezpečné trubky (asymetrická crypto)
    2. SSL Record Protocol - balení přenášených dat (symetrická crypto)

- poskytuje autentizaci, důvěrnost, integritu
- neposkytuje nepopíratelnost
- vyžaduje certifikát serveru (i když není důvěryhodný)

- nejsou předepsány konkrétní kryptografické algoritmy
- registrují se tzv. Cipher Suite - trojice:
    1. asymetrická šifra
    2. symetrická šifra
    3. hash

    - musí být podporovaná oběma stranami
    - musí být k dispozici odpovídající certifikáty

- podívat se na popis protokolu, časové diagramy
- premaster secret - může ovlivnit jenom klient
- master secret - klíč vytvořený oběma účastníky (Client Randrom, Server Random)

SSH = Secure SHell
------------------
- původně pro zabezpečení UNIX služeb, které komunikovaly otevřeným textem
- dnes může tunelovat i jiné služby
- vhodné zejména pro služby, které přenáší jméno/heslo
- autentizace host-host, uživatel-host
- heslo se přenáší v původní podobě přes zabezpečený kanál


Symetrická správa klíčů
=======================
- výměna symetrických klíčů mezi dvěma stranami
- obecně problematická
- není dobré pomocí sdíleného tajemství šifrovat gigabyty dat
- proto se vytváří celá hierarchie klíčů
    - nahoře je KEK (Key Encrypting Key), který má dlouhou platnost
    - potom máme klíč relace, jehož platnost je omezena
    - mezi tím bývá 0 až 1 dalších úrovní klíčů

- autentizace subjektu/klíče (jeden subjekt může vlastnit více klíčů)
- jedno-/obousměrná autentizace
- je potřeba hlídat čerstvost klíče

- útočník může být pasivní/aktivní (jenom odposlouchává / může i něco měnit)

- časové značky dovolují dělat protokoly s jedinou správou klíčů
- vyžadují, ale zabezpečenou synchronizaci času

- používají se také sekvence/čítače, ale tam je problém, že hodnota se dá
  předpovědět

- problém distribuce: O(n^2)
- řeší se pomocí důvěryhodné třetí strany --> O(n)
- používá se push/pull model

    1. KDC - vyrábí symetrické klíče
    2. KTC - pouze přešifrování symetrického klíče

    - důvěra ve třetí stranu musí být v obou případech absolutní
      (může udělat mnohem více škody než CA)

- symetrická správa klíčů má pouze nevýhody (vědět jaké)

- protokol, který využívá časové značky, je bezstavový
- klíč relace musí být různý pro každou relaci, musí být nepředpověditelný
- čítač není vhodný, protože si pak Alice může myslet, že Bob žije, i když Bob
  už nežije (Otways-Rees)

- kryptogram uvnitř jiného kryptogramu ... ticket

Kerberos
--------
- používá se mohutně pro autentizaci a bezpečnou komunikaci
- založený na Needham-Schroeder protokolu
- mechanismus centrálního serveru:
    AS = Atuhentication Server

- ten vydává tickety pro servery nižší úrovně:
    TGS = Ticket Granting Server