Kryptografické protokoly, způsoby ustavení kryptografických klíčů, protokoly s nulovým rozšířením znalostí. Kvantová kryptografie.

• A protocol is an algorithm two (or more) parties have to follow to perform a communication/cooperation. (Algoritmus, definovaný posloupností kroků akcí dvou/více stran k dosažení cíle)
• A cryptographical protocol is a protocol to achieve secure communication during some goal oriented cooperation.
• Motivace
  • Zašifrovat nebo hashovat tajnou informaci (heslo) může být nebezpečné. Replay attack
  • Použití složitější komunikace - autentizačního protokolu
  • Dobré např k demonstraci znalosti tajné informace bez jejího přenosu
  • Založeno na kryptografických systémech (sym. i asym.), hashe. Často na principu challange-response
• Cíle krypto protokolů:
  • Důvěrnost, autentizace (stran i zprávy), integrita, ustavení klíče, nepopiratelnost atd…

• Protokoly založené na sdíleném tajemství (klíči)
  • důvěra mezi stranami, které tajemství sdílí
  • autentizace odpovídá schopnosti (de)šifrovat, případně vytvářet MAC
  • mohou využívat důvěryhodnou třetí stranu (např. Kerberos)
• Protokoly s veřejnými klíči
  • důvěra v držitele soukromého klíče
  • důvěra ve spojitost mezi veřejným klíčem a dalšími daty (certifikáty)
  • autentizace odpovídá schopnosti dešifrovat nebo podepisovat zprávy
  • SSL, SSH …

Dalsi protokoly (asi jen pro uplnost, z IV054)

• Coin flipping protokoly - A a B si pošlou „minci“ na dálku, nikdo z nich nedokáže určit outcome. Dokážou se na něm ale dohodnout, i když si nevěří. CF pomocí jednocestné fce.
• bit commitment protocols - A vezme bit x a událá commit(x). Nelze to změnit a B neví, jaký commit udělala. B si může tipnout, A dokáže udělat open(x) a dokazat jaky byl commit (0 nebo 1). commit muze byt napr HASH.
• Oblivious transfer protocol - A posle tajemstvi B. A nevi, jestli B ho dostane. B ho dostane s pravedpodobnosti 1/2 (1/2 odpad).

• Přesvědčit druhou stranu, že identita patří mně.
• Jedné/obou stran
• Na Pubkey Crypto (šifrovat nonce, na druhou stranu poslat nonce + 1 zašifrované…)
• Pomocí MAC (nonce + MAC(nonce)) - HMAC, CBC-MAC
• Challange-response (commitment to a secret, challange, response, verification), příklad simplified Fiat-Shamir
• Trojcestná auth. - podpisem A dokáže, že je A. B vytvoří session key K, zašifruje a podepíše → A. A a B si ve zprávách ještě posílají nonce (2 různé)
• Zero-knowlegde protokoly: Důkaz, že znám tejemství nebo informaci (např dokážu spočítat rovnici, odpovědět na otázku) s dostatečně malou pravděpodobností podvodu (tipování) aniž bych zveřejnil cokoli o tom, jak jsem to dokázal.
  • Příklad: Chodba s jedním vchodem. Chodba je do kruhu. V jedné části kruhu jsou zavřené dveře rozdělující chodbu na 2 části, není na ně od vchodu do chodby vidět. Jak Alice dokáže, že má klíče od dveří, aniž by ukázala klíče Bobovi, nebo mu ukázala, že jimi prochází? Bob si stoupne ke vchodu, Alice vyjde jedním směrem a vrátí se z druhé strany. Jinak než přes zamčené dveře jít nemohla. Bob má důkaz.
  • Podobné challange - response (taky si povídají a odpovídají na výzvu)
  • Completeness - hodní dokáží odpovědět
  • Soundness - zlí nedokáží přesvědčit ověřovatele aniž by odhalili tajemství.
  • Příklad: Fiat-Shamir algoritmus, (nebo z-k proof for quadratic residua)
• Nonces (unikátní číslo pro danou komunikaci):
  • náhodná čísla - nutná čerstvost a dostatečná kvalita, challenge-response protokoly
  • sekvenční čísla - nárůst o 1 nebo jen kontrola, že neklesají
  • časová razítka - „acceptance window“, je třeba zajistit zabezpečenou a dobře fungující synchronizaci hodin (NTP)

• Bezpečné předání klíče nebo dohoda na klíči (vzájemné vytvoření)
• Požadované vlatnosti:
  • implicitní autentizace klíče - ujištění, že pouze konkrétní protistrana získala přístup ke stejnému sdílenému klíči
  • potvrzení klíče - ujištění, že protistrana opravdu má přístup ke klíči
  • explicitní autentizace klíče - předchozí dva
  • autentizace stran
• Klíče relací (session keys - krátkodobé klíče)
  • Méně šifr. textu k dešifrování pod stejným klíčem
  • Při vyzrazení méně škod
  • Určitá nezávislost aplikací používajících stejný dlouhodobý klíč
  • Příklad: Merkle alg. - A použije nový klíčový pár (asym krypto), pošle public B, B generuje nový symetrický klíč a šifruje pomocí asym. veřejného klíče A …
  • Distribude pomocí Key transport centre (viz KDC u kerbera)
  • Shamir proto. - komunikace bez sdílených klíčů. A zašifruje X pomocí k1 → B zašifruje E_k1(X) pomocí k2 → A dešifruje a pošle E_k2(X) → B
• Diffie-Hellman (viz vypracováno v jiné otázce)
• Další příklady: Needham-Schroeder (public key) - prostě pomocí existujících asym. klíčů dohodnu sym. klíč, COMSET (a variace: R-COMSET, RRC) Helsinki (modifikace Needham-Schroeder)
• Escalatory protocols (EKE, Diffie-Hellman EKE …)
• Použití biometrik
  • V biometrické charakteristice najdi jedinečnou neměnnout část. Zkombinuj s tajnou informací a zpracuj dohromady (např HASH). Biometrika sama o sobě není tajné info, problém bývá s přidáním tajné informace.
  • Nebo pomocí biometrik zamkni klíč

• X509 certifikáty, CA, revokace (CRL, OCSP) a PGP, Publicly available directory - vše zpracováno v ostatních otázkách k BIT.

PV079 Applied ryptography
Summarizing information from Handbook of Applied cryptography (challenge-response protocols, zero-knowledge, auth protocols)
https://is.muni.cz/auth/el/1433/podzim2012/PV079/um/PV079_2012_L06.pdf https://is.muni.cz/auth/el/1433/podzim2012/PV079/um/PV079_2012_L07.pdf

IV054 Codes, Cryptography and Cryptographical Protocols
http://www.fi.muni.cz/usr/gruska/crypto12/crypto_09.pdf

Zero-knowledge proofs protocols:
http://www.cs.cmu.edu/~ryanw/crypto/lec6.pdf http://www.fi.muni.cz/usr/gruska/crypto12/crypto_10.pdf

CS276 Lecture 24: Zero Knowledge Protocols
http://lucatrevisan.wordpress.com/2009/05/11/cs276-lecture-24/

CS276 Lecture 25: Quadratic Residuosity and Zero Knowledge
http://lucatrevisan.wordpress.com/2009/05/04/cs276-lecture-25/

CS276 Lecture 26: Quadratic Residuosity and Proofs of Knowledge
http://lucatrevisan.wordpress.com/2009/05/04/cs276-lecture-26/

CS276 Lecture 27: Computational Zero Knowledge
http://lucatrevisan.wordpress.com/2009/05/16/cs276-lecture-27/

CS276 Lecture 28: the CZK 3-Coloring Protocol
http://lucatrevisan.wordpress.com/2009/05/06/cs276-lecture-28/

All nicely summarized in following book:
Luca Trevisan, Cryptography, Lecture Notes from CS276, Spring 2009, Stanford University
http://theory.stanford.edu/~trevisan/books/crypto.pdf

• Slajdy IA066 Úvod do kvantových algoritmov a počítačov
  • Quantum cryptography http://www.fi.muni.cz/usr/gruska/quantum11f/qc1109.ps
  • Basic concepts and outcomes http://www.fi.muni.cz/usr/gruska/quantum11f/qc1102.ps

• Založeno na fyzikálních zákonech. Používá částice (proton, elektron, neutron, fotony a další elementární č.)
• Quantum information vs classical: Těžko se ukládá a zpracovává, neznámá se nedá okopírovat a měření ničí informaci (viz. dole)
• Informace reprezentována pomocí qubits (kvanta bitů) nabívají nespočetně mnoho hodnot α|0> + β|1>, kde α,β jsou komplexní čísla t.ž.
• Př. elektron v atomu vodíku - Báze - 2 pozice. Obecný stav určen amplitudou α,β vzhledem k bázi
• Kvantový stav může obsahovat neomezeně informace. Měřením klasické informace dostaneme 0 s pravděpodobností , podobně pro 1.
• Složený kvantový systém nelze zkonstruovat ze znalostí podsystémů (v klasických systémech ano)
• Příklad použití: Quantum one-time pad, Qantum registers, a hlavně Quantum key distribution (generation)
• Síla kvantového počítání je v možnosti dělat věci běžně nemožné (teleportace, vytvoření zcela tajného sdíleného klíče, vytváření efektivních kvantových algoritmů a protokolů)
• Polarizace fotonů ke generování klíče (viz BB)

• Meranie kvantového stavu pôvodný stav zničí/zmení - odpočúvanie je možné detekovať
• No-cloning theorem: Neznámy kvantový stav nemôže byť skopírovaný - tj. nie je možné kvantový stav pri odpočúvaní odchytiť, naklonovať si pomocný, pôvodný poslať ďalej a merať len naklonovaný
• Heisenbergov princíp neurčitosti: ak je výsledok merania kvantového stavu v istej báze istý, výsledok merania v duálnej báze je náhodný. Viď BB-84
• Shanonova veta(kvantová verzia): Na bezpečné zakódovanie n qubitov je potrebných 2n klasických bitov
• Meranie kvantového stavu: meranie prebieha vždy vzhľadom k zvolenej báze, ktorá určuje, aké možné výsledky môžme dostať. Pravdepodobnosti, s akými dostaneme výsledky sú určené kvantovým stavom.
  • Príklad: Meriame v štandardnej báze |0>,|1> takže kvantový stav skolabuje do stavu |0> s pravdepodobnosťou P alebo do stavu |1> s pravdepodobnosťou 1-P. Pri následnom meraní v duálnej báze |0'>,|1'> (tj. meranie stavu |0> alebo|1>) dostaneme výsledok |0'> s pravdepodobnosťou 1/2 a výsledok |1'> s pravdepodobnosťou 1/2.
  • Príklad 2: Meriame polarizáciu fotónu v báze 0°,90°. Následné meranie v duálnej báze 45°,135° bude náhodné.

• Bennet-Brassard 1984
• Protokol na bezpečné ustanovene zdieľaného kľúča, dokázateľne bezpečný
• 1. fáza: Alica vygeneruje náhodnú postupnosť bitov
• 2. fáza:
  • Alica posiela Bobovi fotóny polarizované buď v báze 0°,90° (označme |0>,|1>) alebo v báze 45°,135° (označme |0'>,|1'>). Pri každom fotóne zvolí bázu náhodne. Fotóny kódujú binárnu postupnosť - 0 je kódovaná pomocou stavov |0> a |0'>, 1 je kódovaná pomocou stavov |1> a |1'>
  • Bob nevie, v akej báze sú fotóny polarizované, tak ich meria náhodne v jednej z nich
• 3. fáza:
  • Bob zverejní, aké bázy pri meraní použil. Alica mu klasickým kanálom odpovie, pri ktorých fotónoch použili rovnakú bázu (v týchto prípadoch bude výsledok so 100% pravdepodobnosťou správny). Bity, ktoré Bob získal meraním v rovnakej báze ako Alica posielala, boli bezpečne prenesené a sú známe obom.
• 4. fáza:
  • Alica a Bob sa dohodnú na niekoľkých bitoch, ktoré zdieľajú, a klasickým spôsobom si ich oznámia (ďalej ich už nepoužijú). V tejto fáze ide o odhalenie odpočúvania: ak aspoň 1 bit nesedí, určite došlo k odpočúvaniu.
• 5. fáza (Privacy amplification, nie som si istý, či je nutná ku štátniciam, uvádzam pre úplnosť):
  • Alica a Bob ešte zdieľajú n bitov. Stále existuje riziko, že Eva mala šťastie a uhádla niekoľko meraní správne, teda vie časť z bitov, ktoré Alica a Bob zdieľajú. Alica a Bob sa preto dohodnú na podmnožinách S₁..S_k bitov, ktoré zdieľajú. i-ty bit finálneho zdieľaného kľúča je parita množiny S_i (tj. XOR z bitov kľúča určených množinou S_i). Aby Eva vedela určiť i-ty bit, musí vedieť všetky bity určené podmnožinou S_i, preto ak aj Eva vedela na začiatku pár zdieľaných bitov, po tejto fáze už nebude poznať takmer žiaden.

• B92
  • Bennet 1992, minimálny QKG (quantum key generation) protokol
  • Rovnaký ako BB-84, ale miesto 4 stavov |0>,|1>,|0'>,|1'> (0°,90°,45°,135°) používa na kódovanie iba 2 stavy |0> a |1'> (tj. napríklad 90° a 45°)
• Ekert QKG
  • Na detekciu odpočúvania využité Bellove nerovnosti

Kvantove protokoly:

In coin-flipping protocols, Alice and Bob can flip a coin over a distance in such a way that neither of them can determine the outcome of the flip but both can agree on the outcome in spite of the fact that they do not trust each other.

In bit commitment protocols Alice can choose a bit and get committed to it in the following sense: Bob has no way of learing Alice's commitment and Alice has no way of changing her commitment.

In 1-out-2 oblivious transfer protocols Alice trasmits two messages m_1 and m_2 to Bob who can chose whether to receive m_1 or m_2, but cannot learn both, and Alice has no idea which of them Bob has received.

In standard oblivious transfer protocols Alice can send a message to Bob in such a way that Bob receives the message with probability 1/2 and a garbage with probability 1/2. Moreover, at the end Bob knows whether he got a message or a garbage, but Alice has no idea which of them Bob has received.