Good Mood

Toto je první příspěvek v 3. dílu série, na základy kryptografie. Série je popsán takto:

1. Symetrické Šifrování
2. Integrita Dat & Ověřený Šifrování
3. Asymetrické Šifrování pomocí Veřejného/Soukromého Klíče Párů

Potápění do světa počítačové vědy může být skličující úkol. Zvlášť sám!, V této sérii blogů bych chtěl nabídnout přehled na vysoké úrovni o základech kryptografie pro ty, kteří se chtějí ponořit dále do tématu, kteří nemusí nutně vědět, kde začít. Tento přehled je založen konkrétně na mých hlavních takeaways ze Stanfordovy kryptografie i samozřejmě, jak učil Dan Boneh, k dispozici na Coursera.

rozhodl jsem se absolvovat tento kurz, protože jsem vývojář blockchainu, který nepocházel z tradičního comp-sci pozadí. Studoval jsem ekonomii na vysoké škole, ale při zahájení své kariéry jsem se více zaměřil na počítačové programování., Od té doby, co jsem začal kódování, byl jsem na misi dostat „blíže k počítači“ — loupat zpět vrstvy abstrakce jsem si užil jako web developer a pochopit, co se děje pod kapotou. Přechod do kryptoměna a distribuované systémy z webu vývoj byl divoký a nádherný krok v tomto směru v mnoha ohledech, ne nejméně který byl stále více obeznámeni s pojmy z kryptografie. Chtěl jsem však pevnější základ., Jelikož je to poměrně rozsáhlé oblasti, myslel jsem, že to stálo za to, aby drop $70 konzumovat tyto informace ve fóru speciálně sestaveného ze Stanford University. Můžete také provést audit tohoto kurzu bez předání úkolů zdarma. Zázraky internetu!

začněme.

kryptografie je v podstatě praxí bezpečné komunikace za přítomnosti potenciálních protivníků třetích stran. Koncept bezpečné komunikace se skládá ze 2 hlavních bodů:

1. Zabezpečení proti odposlechu: to zaručuje důvěrnost údajů.,
2. Zabezpečení proti manipulaci s daty: to zajišťuje integritu dat, což znamená, nikdo nemůže manipulovat s údaje, které jste poslal a oklamat příjemce do přijetí manipulovat data jako platné.

důvěrnost dat je dosažena šifrováním, které může mít dvě formy: symetrické a asymetrické.

• symetrické šifrování používá jeden jediný klíč, který je třeba sdílet mezi všemi účastníky, kteří komunikují.
• asymetrické šifrování používá osobní klíče., Každý účastník má svůj vlastní veřejný klíč a pár soukromých klíčů pro šifrování a dešifrování zpráv při komunikaci.

(Poznámka: Tento blogpost bude hovořit o kryptografii v souvislosti se symetrickým šifrováním. V následném příspěvku se ponoříme do asymetrického šifrování.)

Šifrování Dat: Dva typy Šifer

Šifrování zajišťuje důvěrnost dat a zahrnuje dvě důležité složky:

1. tajný klíč: V rámci symetrické šifrování, můžeme předpokládat, že naši účastníci, Alice a Bob, mají společný tajný klíč.,
2. šifra: sada algoritmů, jeden pro šifrování a jeden pro dešifrování.

je důležité si uvědomit, že šifrovací a dešifrovací algoritmy jsou veřejně známé. Jediné, co je v tajnosti, je klíč.

dva typy šifer jsou proudové šifry a blokové šifry. Potenciální předpokladem pro odpovídající pochopení obou těchto šifer je znalost bitové operace (operace prováděné na kousky). Přesněji řečeno, koncept exkluzivní-nebo (XOR). Zjistil jsem, že tento blogpost poskytuje velmi jasné vysvětlení bitových operací., Nebo se můžete pokusit pochopit koncept XOR pomocí obrázku níže. V podstatě dva bity jsou kombinovány, a pokud jsou různé (jeden 0 a jeden 1) mají za následek 1, a pokud jsou stejné, (oba 0 nebo oba 1) mají za následek 0. Od teď, budu předpokládat, že čtenář chápe pojem XOR a že univerzální notace pro XOR je: ⊕

Šifra datového Proudu

stream šifra je symetrický klíč šifrovací, kde holý text (v bajtech formě) je XOR, že kousek po kousku s klíčem (také v bajtech formě) na výrobu šifrované ciphertext., Stejný proces se používá k dešifrování šifrytextu. Vzhledem k povaze XOR operace, pokud jsme ciphertext XOR s klíčem, tyto výsledky s původní otevřený text.

Bystrý čtenář možná uvědomíte, že z tohoto popisu, že klíč (označen ve výše uvedené ilustraci, jak „Cipher stream“) a otevřený text musí mít společného něco velmi důležitého. Přesně tak! Klíč a prostý text musí mít stejnou délku., To samozřejmě není příliš praktické.

aby byla proudová šifra praktičtější, je zavedena myšlenka generátoru pseudorandomu. A pseudonáhodných generátor je deterministický postup, který má vstupy a výstupy i delší pseudonáhodných výsledek. Být deterministický postup znamená, že se vždy vrací stejný výstup, pokud dostane stejný vstup (tj. „abc123“ výsledky v „8474f24e0d72e1b949ffd2…“ pokaždé)., Slovo pseudorandom znamená, že zatímco výstup není ve skutečnosti náhodný (protože je určen na základě konkrétního vstupu), je ve skutečnosti nerozeznatelný od skutečně náhodného řetězce. Jinými slovy, vzhledem k vzorku vstupů a výstupů neexistují žádné stopy o tom, který výstup odpovídá určitému vstupu a naopak, proto je pseudorandom. Je možné použít sdílený tajný klíč jako vstup k výrobě ještě delší pseudonáhodných klíč jednat jako dlouhý klíč XOR bych se stejně dlouho plaintext.,

tato specifická implementace streamové šifry, kterou jsme dosud ilustrovali, se nazývá „jednorázová podložka“. Mimořádně důležitou vlastností jednorázové podložky je, že jednorázový klíč lze použít pouze jednou. Jakmile je použit podruhé, bezpečnost těchto zpráv je ohrožena.

Na obrázku níže je snímek z kurzu. PRG (k) označuje pseudorandomovou sekvenci generovanou z našeho sdíleného klíče k.symbol ⊕ označuje XOR. c označuje šifertext. m označuje zprávu (nebo prostý text).,

v Podstatě, tento snímek říká, že jakmile je klíč je použit dvakrát, můžeme XOR na ciphertexts spolu, a to je přesně rovna XOR ‚ ing dva plaintexts spolu. Vzhledem k tomu, že v angličtině je dostatek redundance, důvtipný útočník může tyto informace použít k úplnému obnovení zpráv.

Chcete-li zachovat jeden sdílený tajný klíč, lze koncept nonce použít k zajištění toho, abychom nikdy neopakovali jednorázový klíč., Nonce je libovolné číslo, které lze použít pouze jednou v kryptografické komunikaci. Při odesílání ciphertext, odesílatel může také poslat nonce, aby byly v kombinaci s tajným klíčem, aby se pak použít jako vstup k výrobě výraznou pseudonáhodných klíč pro každé šifrování.

(možná jste si všimli, že výše uvedený snímek říká útok 1., Jako stranou, pro ty, přemýšlel, co Útok 2 je, že Útok 2 je skutečnost, že zatímco stream cipher nabízí důvěrnost dat, nezajišťuje integritu dat, jak je definováno v první části)

Bloková Šifra

druhý typ šifra je Bloková Šifra. Bloková šifra bere v pevné-délka vstupní a opakované šifruje prostý text znovu a znovu pomocí jiného klíče („kulatý klíč“) pro každé kolo a nakonec výstupy ciphertext stejné délky. 3DES a AES jsou dva příklady blokových šifer, které mají vstup 48 bitů a 128 bitů.,

Snímek výše ukazuje základní architekturu pro bloková šifra. Můžete vidět, že klíčový rozšiřující mechanismus slouží k tomu, aby měl nový klíč pro každé kolo. Prostý text, označený (m) pro zprávu, se znovu a znovu zašifruje, dokud se nakonec nevrátí odpovídající šifra (c) stejné délky.

kvůli stručnosti budu v tomto blogu pokrývat AES., Ačkoli DES / 3DES je historicky významný, dnes AES je více široce používán a přijímán.

AES je postaven jako Substituce, Permutace Sítě. AES pracuje na 128 bitovém bloku, který se rovná 16 bajtů. Jak je znázorněno nahoře vlevo nahoře, zapíšeme 16 bajtů jako matici 4 x 4. Tato matice slouží jako datová struktura dobrá pro míchání dat kolem., V každém kole, postup je následující:

1. XOR kolo, klíč, první (k0), s aktuální zprávy
2. Pak jsme se projít substituční proces, kde bloky dat jsou nahrazeny jinými bloky na základě dané substituční tabulky (na obrázku výše (1) ByteSub).
3. procházíme permutační vrstvou, kde jsou bity permutovány a zamíchány (na obrázku nahoře (2) ShiftRow & (3) MixColumn).
4. pak tento proces opakujeme po dobu 10 kol.,

na Obrázku výše, zjistíte, že poslední kolo přeskočí Mix Sloupci krok, XOR je výsledek s naším posledním kole klíč a výstupy náš výsledný šifrový. Abychom mohli dešifrovat, jednoduše zvrátíme proces. Kurz nabízí přehled o tomto šifrovacím procesu na vysoké úrovni a povzbuzuje studenty, aby se do něj podívali hlouběji, pokud vás to zajímá. Proto nechám vnitřní fungování AES v tomto. Doporučuji lidem podívat do Fiestel Sítě postup 3DES pro zábavu porovnat a kontrast různé šifry.,

z hlediska hardwaru, od uvedení Intel Westmere, Intel navrhl své procesory se speciálními pokyny pro optimalizaci AES zabudované přímo do jejich hardwaru a AMD následoval krátce poté.

blokové Šifrové režimy provozu

Na rozdíl od proudové šifry má bloková šifra pouze vstup s pevnou délkou. Samozřejmě chceme zpracovávat data, která jsou větší než 16 bajtů najednou. Takže dále je důležité pochopit provozní režimy,za kterých můžeme použít blokové šifry k šifrování velkých sad dat., Chcete-li použít tuto blokovou šifru na velký datový soubor, první způsob provozu, který může přijít na mysl, se nazývá „elektronická kódová kniha“ (ECB). ECB jednoduše rozděluje data na 16 bajtových bloků a provádí jednotné šifrování AES. Mohlo by to být dokonce provedeno paralelně. Velmi rychle! Ale ve skutečnosti to není příliš bezpečné.

Je to nejistá, protože pokud 16 byte zprávy se opakuje, šifrový text bude mít také opakované údaje., To prozrazuje informace o našich datech potenciálnímu útočníkovi. Tuto chybu zabezpečení můžeme použít v případě, kdy zašifrujeme obrázek s ECB. Jak vidíte níže, je jasné, že náš obraz je headshot. V silně černé oblasti vidíme siluetu přes tmavé vlasy a košili.

Je důležité, že naše šifrovací systémy jsou sémanticky bezpečné., Sémantické Bezpečnosti je koncept, že pokud máme kód, který odpovídá jednomu ze dvou různých plaintexts, protivník nemůže hádat s lepší pravděpodobností, než 1/2, které otevřený text šifrový text odpovídá. Je zřejmé, že ECB není sémanticky bezpečná. Náš zašifrovaný obrázek nám dává spoustu informací, abychom mohli odhadnout jeho odpovídající prostý obrázek.

ECB je příkladem jednorázového režimu provozu (což znamená, že stejně jako jednorázový pad lze klíč použít pouze jednou). Dalším bezpečnějším jednorázovým režimem provozu je deterministický režim čítače. Můžete se na to podívat sami., Přesunu se na zabezpečené provozní režimy, které umožňují mnohonásobné klíče!

Cipher Block Chaining (CBC) je způsob provozu, že se řetězy každý 16bitový blok textu spolu přes XOR ‚ ing ciphertext z předchozího textu do běžného textu před provedením bloková šifra šifrování (tj. šifrování AES). Níže obrázek objasňuje tento pojem:

Jsme první start s náhodným IV., IV znamená inicializační vektor, který může být definován jako: počáteční hodnota použitá k zahájení nějakého iteračního procesu. V případě CBC musí být IV náhodný (tedy nepředvídatelný), proto musí být jedinečný pro každou transakci. První blok ciphertext je prostě nezašifrované náhodný IV. K výrobě zbytek ciphertext, první, náhodný IV je XOR, že s první blok prostého textu (m). Výsledek se pak zašifruje pomocí kulatého klíče k a vrátí se první blok šifrované šifry (c)., Že šifrový pak dostane XOR, že s další blok textu (m), výsledek je šifrována s kulatým klíčem k a vrací druhý blok šifrovaných ciphertext (c). Proces pokračuje, dokud nebudou všechny bloky šifrovány.

K dešifrování, jsme jen zvrátit proces.

důležitou součástí šifrování CBC je, že náhodný IV je nepředvídatelný., Pokud se IV stane předvídatelným, pak se naše šifrovací schéma stane zranitelným vůči vybraným útokům v prostém textu. Zvolený Plaintext Attack (CPA) je útočný model, který předpokládá, že útočník může získat šifertexty pro libovolné plaintexty a použít je k odhalení informací o šifrovaných zprávách. K zajištění bezpečnosti CPA je proto zapotřebí nepředvídatelné IV.

Medvěd se mnou jak se snažím vysvětlit, jak tento útok by práce: je možné provádět vybrané plaintext attack v přítomnosti předvídatelné IV je vzhledem k povaze XOR., Pokud XOR stejnou hodnotu společně (0101 ⊕ 0101) bude vždy rovno 0, proto se zruší. Takže pokud máte podezření, že pozorované ciphertext c odpovídá určitý otevřený text m si můžete vyzkoušet své hypotézy s předvídatelným IV. Pokud otevřený text byl zašifrován s IV1 takové, že c = E(k, m ⊕ IV1) si může předložení nového textu, který chcete zašifrovat, a uvidíme, jestli můžete získat odpovídající výsledek: c. Vzhledem k tomu, můžete předvídat IV bude IV2, odešlete m ⊕ IV1 ⊕ IV2., CBC proces bude XOR tento vstup s dalším IV, IV2 takové, že platí: c = E(k, m ⊕ IV1 ⊕ IV2 ⊕ IV2) proto IV2 ruší, a opět jsme šifrování E(k, IV1 ⊕ m), které by opět s c a pokud se to stane, jsme byli schopni odhadnout, co bylo dříve zašifrované IV1.

opravdu úžasná práce pokud jste to prošli – ^

s tím bych rád přezkoumal ještě jeden blokový šifrovací režim provozu,který uzavře první blogpost v této sérii 3 dílů. Pokud to bylo velké úsilí, aby to tak daleko, nyní může být vhodná doba pro rychlou přestávku před pokračováním!,

Ok, takže jsme zkontrolovali ECB, CBC a jejich zranitelnosti, ale nakonec a pravděpodobně nejdůležitější představím randomizovaný režim čítače (CTR). Jedná se o nejnovější, nejbezpečnější způsob provozu a je také účinnější než CBC.

Náhodně Counter Mode také se náhodný IV. IV slouží k jinému účelu, i když zde. Náš klíč se spojí (např., přes AES) s iterovanou verzí naše IV: nahoře přidáváme 1 do našeho IV pro každou iteraci, jinak bychom získali opakovaný výsledek. Děláme to, dokud nebudeme mít podložku tak dlouho, jak naše prostý text zprávy. Stejně jako one-time-pad stream cipher, jsme nyní XOR náš otevřený text zprávy s naší pseudonáhodných pad výsledek v ciphertext. Pokud má váš hardware více motorů AES, je to velmi efektivní, protože je rovnoběžné. V CBC závisel každý šifrový text na předchozím bloku šifry, takže nebylo možné paralelizovat.,

ani nutně nepotřebujeme blokovou šifru, abychom spojili náš IV a klíč do pseudorandomové podložky. Blokové šifry musí být reverzibilní. Pokud se podíváte pozorně na mechaniku randomizované counter mode, zjistíte, že dešifrování nevyžaduje, abychom reverzní F(k, IV) . Vzhledem k povaze XOR, vše, co musíme udělat, je obnovit stejnou pseudonáhodných pad a XOR s naší ciphertext. Proto, abychom mohli dešifrovat, musíme operaci opakovat, nikoli ji zvrátit.,

Abstraktně řečeno (tak daleko jsem se vyhnout abstraktní pojmy), to znamená, že postup používáme, abychom dohromady naše tajný klíč a IV F(k, IV) musí být Pseudonáhodná Funkce (PRF) na rozdíl od Pseudonáhodných Permutace (PRP). Ve skutečnosti jsme tyto koncepty uplatňovali v celém tomto blogpostu. Jak PRPs, tak PRFs jsou deterministickými postupy, které vzhledem k určitému vstupu vedou k pseudorandomovému výstupu. (tj. AES, XOR). PRP je však přísnější v tom smyslu, že musí být reverzibilní., Ve skutečnosti se pojmy PRP a bloková šifra (například AES) často používají synonymně. PRF však nemusí být reverzibilní. Pokud se vrátíte zpět na předchozí snímky zobrazené v tomto příspěvku, nyní pochopíte notaci PRF a PRP.

to uzavírá můj přehled symetrického šifrování! Pokrývali jsme proudové šifry a blokovali šifry. Poté, protože blokové šifry lze provádět pouze na přibližně 16 bajtech najednou, pokryli jsme provozní režimy používané k provádění blokových šifer na velkých plaintextech. Také jsme objasnili pojmy PRPs vs PRFs.