====== 6. Kryptoútoky ======
Útoky na kryptografické systémy a protokoly. Faktorizace a rozpoznání prvočísel.
====== Vypracování ======

Good source of info:
http://www.win.tue.nl/~berry/2WC13/LectureNotes.pdf

=== Protocol attacks: ===
  * Man-in-the-middle attack (Diffie-Hellman MITM)
     * A a B ustavují klíč. Útočník E mezi nimi se vydává střídavě za A,B a odpovídá jim podle D-H. 
     * Řešení - použití autentizace před samotným ustavením klíčů (např. pub. key krypto) 
  * Reflection/replay attack (ISO-SC 27 protocol reflection attack)
     * replay attack, například na primitivní autentizaci pomocí HASHe. Pokud posílám jen hash hesla, útočník ho může odchytit a později použít celý hash k autentizaci.
     * Řešení Replay Challange-response s použitím Nonce nebo session keys (one-time pads, timestamps)
     * Reflection - přeposílání zpráv určených pro A Bčku.
     * Řešení Reflection- vázat identitu do zpráv, použití symetr. asym. krypto.
  * Interleaving attack (Lowe's attack on Needham Schroeder protocol - asymetrickou verzi, s použitím důvěryhodného serveru, který distribuuje klíče)
     * Mixování packetů z předchozích běhů, s možností změn v aktuálním.
     * Loweho útok je forma MITM útoku na slabé místo protokolu. Lowe navrhl fix úpravou protokolu tak, že v 6. kroku protokolu se neposílají jen 2 nonce šifrovaně, ale také identita B.
     * Obecné řešení podle handbook of aplied crypto: chained nonces 
  * Chosen-text attack on challenge-response protocols (oracle attacks)
     * Útočník je schopen vytvářet challange a z odpovědí se snaží vyčíst klíč.
     * Řešení může být použití Zero-Knowledge protokolů
  * Forced-delay attack (zprávy mají sekvenční čísla)
     * DoS attack
     * Řešení použití TimeOutů pro spojení
  * Forward search attack
     * pre-compute all possible encryptions c_i = P_k(x_i) for whole space of x_i
     * find captured ciphertext in pre-computed database 
     * suitable if x_i space is small
     * Patří sem rainbow tables? Asi jo
        * Útoky na hashovací funkce, předpočítání mnoha Hashů pro předpokládané vstupy (nebo pro vstupy 0-n bytů)
        * Dají se koupit celé disky s rainbow tables.
        * Ochrana je použítí dlouhých vstupů (pokud to jde, například vstup jsou hesla), nebo solení vstupů.
     * Zřejmě brute force attack

=== Hash function attacks: ===
  * Hrubou silou - závisí hlavně na délce výstupu. Pro 128b výstup musím vypočítat max <math>2^128 </math> výstupů, abych našel kolizi 2. řádu (ne vstup, pokud neznám množinu vstupů).
  * Díky Birthday paradoxu mi ale stačí  <math>2^{n/2}</math>. Útočilo se tak na MD5, ale dřív byl MD5 prolomen díky kryptoanalýze.
    * Řešení - použití velké množiny dostatnečně dlouhých vstupů (solit hesla) a dlouhých výstupů.
  * Rainbow tables !
  * Útok pomocí kryptoanalýzy se u hashovacích fcí provádí s cílem najít kolizi u komprimační fce. (např. diferenciální kryptoanalýza)
  * Birthday-paradox attack (see http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf)
  * Pseudo-collision attack
  * Chaining attack (meet-in-the-middle, fixed-point, differential), zřejmě druh kryptoanalýzy pomocí útoku na kompresní funkci f.


=== Cryptosystem attacks - 1 division: ===
  * Chosen-plaintext (attacker chooses plaintext, access to encryption function, obtains ciphertext encrypted under unknown key)
  * Chosen-ciphertext (attacker chooses ciphertext, access to decryption function, obtains plaintext)
  * Known-plaintext (weaker, only known (plaintext, ciphertext) pairs encrypted under same key)
  * Ciphertext-only (weakest, only known ciphertexts - e.g. collected encrypted traffic - WEP crack uses this method)

=== Cryptosystem attacks - another division: ===
  * Brute-force attack
  * Dictionary attack
  * Meet-in-the middle attack (Triple/Double DES)
  * Side channel attack
     * timing analysis, power consumption analysis, electromagnetic emissions analysis
     * mainly targets asymmetric cryptography, modular exponentiation - time is linearly dependent on number of 1's in exponent (key)
  * Linear cryptanalysis 
    *  known plaintext útok
    *  Na blokové šifry
    *  Hledá lineární závislosti (aproximace) k jednotlivým akcím (S-boxy) šifer.
    *  útok na DES (asi jen částečný úspěch, pořád je potřeba dost plaintextů, záleží na velikosti klíče)
  * Differential cryptanalysis (high-order, truncated, impossible)
     * Chosen plaintext útok
     * Statistická analýza rozdílů v plaintextových párech a v jejich příslušných
ciphertextech (Po jednotlivých kolech)
     * Př. AES kontruován, aby odolal Lineární i Dif kryptoanalýze
  * Podle mě navíc:
  * Interpolation attack 
     * represent S-box and whole cipher as an algebraic function
     * Lagrange interpolation to determine coefficients
  * Integral attack (square attack; chosen plaintext attack)

===== Útoky na kryptografické systémy a protokoly. =====

==== Meet-in-the-middle ====
  * útok na symetrickou šifru
  * Předpokladem je, že útočník má k dispozici plaintext a cyphertext zašifrovaný dvakrát, pokaždé jiným klíčem.
     * <math>C=ENC_{k_2}(ENC_{k_1}(P)) </math>
     * <math>P=DEC_{k_1}(DEC_{k_2}(C)) </math>
  * Následně útočník zašifruje zprávu P všemi možnými klíči a získá množinu cyphertextů.
  * Pak postupně dešifruje zprávu C všemi kombinacemi klíčů a výsledné zprávy vyhledává v množině zpráv z předchozího bodu

SSL Stripping
https://nfsen.ics.muni.cz/public/presentations/sslstrip.pdf
  * MITM attack. Odchytávám komunikaci a všechny HTTPS downgraduju na HTTP.
  * Lze použít technik k donucení uživatele, který používá ustavené HTTPS spojení, aby se relogoval a pak použít předchozí bod.
  * Je potřeba uživatele přesvědčit, že je na bezpečné stránce (zelený zámeček v adresním řádku jako ikonka...)

Attacker can...
     * Record messages
     * Replay them later
        * Possibly in different order
        * Some repeatedly
        * Some not at all
     * Modify a part of or whole message

===== Faktorizace a rozpoznání prvočísel. =====

=== Primality testing ===
Proving that number is **composite**. Usually probabilistic proofs, either gives witness of compositeness or with high probability the number is prime.

  * Miller-Rabin primality testing (used for example by OpenSSL when generating primes for RSA key-pair). Widely used
  * Solovay-Strassen

=== Primality prooving ===
Prove that given number is prime (proof in mathematical sense).

  * AKS deterministic primality-proving algorithm running in polynomial time (with the hell of huge factor).
  * Pocklington-Lehmer primality test.
  * Elliptic curve test - very fast method for proving primality, Atkin test. 

=== Factorization ===
Factorization of number N to its prime factors is indeed prove it is composite.
Metody:
  * Trial division (up to sqrt(N))
  * Euler's fact. method - cíl napsat n jako součet dvou čísel 2 různými způsoby <math> n = a^2 + b^2 = c^2 + d^2 </math>
  * Fermat's factorization
  * Lenstra elliptic curve
  * Pollardův algoritmus
  * Quadratic sieve
    * data collection, hledání čísel se speciální vlastností = sieving
    * data processing, lineární kongruence na základě faktorizací z data collection.
  * General number field sieve
  * Shor's quantum algorithm
  * Na kvantových počítačích by to bylo jednoduché

Možná jen pro úplnost
  * Fermatova čísla <math>F_i = 2^{2^i}</math>. Fermat předpokládal, že taková F_i jsou prvočísla. Euler rozložil F_5
  * Ne všechna čísla dané délky jsou stejně obtížně faktorizovatelná, Semi-primes násobky dvou podobně dlouhých prvočísel je nejobtížnější rozložit.

====== Materiály ======
is.muni.cz/th/73040/fi_m/diplomka.pdf

~~DISCUSSION~~