Útoky na kryptografické systémy a protokoly. Faktorizace a rozpoznání prvočísel.

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

• 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

• Hrubou silou - závisí hlavně na délce výstupu. Pro 128b výstup musím vypočítat max výstupů, abych našel kolizi 2. řádu (ne vstup, pokud neznám množinu vstupů).
• Díky Birthday paradoxu mi ale stačí . Ú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.

• 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)

• 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)

• ú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.
  • 
  • 
• 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

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

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 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
• 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 . 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.

is.muni.cz/th/73040/fi_m/diplomka.pdf