1. cvičení řešení úkolů - vse.cz · Řešení úkolů na 1. cvičení ze 4SA313 verze 30. 9....

Řešení úkolů na 1. cvičení ze 4SA313 verze 30. 9. 2017

1. cvičení – řešení úkolů a) Jak silné heslo potřebujete? Následující tabulka udává požadovanou entropii vytvořeného hesla

v závislosti na počtu iterací při jeho hašování a v závislosti na předpokládaném útočníkovi.

Schopnosti útočníka (počet hašovacích operací)

Uložení hesla

5000 iterací 1000 iterací 1 iterace 5 mil. iterací

2^70 (NSA za rok) 58,5 61 71 49 2^58 (firma za půl roku) 46,5 49 59 37 2^52 (jednotlivec s GPU za měsíc) 41,5 43 53 31 2^42 (jednotlivec s CPU za týden) 31,5 33 43 21

Jak jsem došel k této tabulce? První sloupec udává typ útočníka a odhad počtu operací

kryptografického hašovacího algoritmu1, které je schopen provést za uvedenou dobu.

Ve studii „Towards Reliable Storage of 56-bit Secrets in Human Memory“2 autoři odhadují, že NSA je

schopna za 1 milion USD sestavit zařízení, které spočítá 270 hašů za rok (předpokládají se operace

SHA, SHA-2 či SHA-3). Při vynaložení miliardy USD se výkon zvýší na 280 hašů za rok.

Ne každý je ale cílem NSA. Firma3 či zločinecká skupina je schopna si sestavit či zakoupit speciální

server pro lámání. Firma Sagita HPC prodává za necelých 20 tis USD server Brutallis, který je schopen

za vteřinu spočítat 11 231 miliónů hašů algoritmu SHA-256. Za půl roku je to 2^58 hašů.

Pokud by Vaše heslo lámal jednotlivec pomocí grafické karty „AMD Radeon R9 290 Series“, tak je

schopen za měsíc spočítat 252 hašů SHA-256.

Na procesoru Core i7-2600K za týden spočítá 242 hašů SHA-256.

Počet vyzkoušených kombinací závisí i na způsobu uložení hesla – na počtu iterací hašovací funkce.

Např. 1000 iterací snižuje požadovanou entropii o 10, 5000 iterací o 11,5. Aby pravděpodobnost

uhodnutí byla menší než 50% za uvedenou dobu, tak přičteme k entropii hodnotu 1.

Svoje hesla ukládám do správce hesel Keepass, u kterého lze nastavit počet iterací při odvozování

klíče pro symetrickou šifru, pomocí které se šifruje soubor s databází hesel. Mám nastaveno

5 000 000 iterací, log2 tohoto čísla je přibližně 22. Vzhledem k citlivosti uložených údajů je ale vhodné

počítat s tím, že útočník se bude více a delší dobu snažit o prolomení.

1 Obecné kryptografické hašovací funkce jako MD5, SHA1, SHA-2, SHA-3 mají podobnou rychlost. Rychlost specializovaných algoritmů pro ukládání hesel (bcrypt, scrypt, argon2, …) se výrazně liší, ale tyto algoritmy nejsou národními standardy, takže mohou bránit certifikaci aplikace. 2 BONNEAU, Joseph; SCHECHTER, Stuart. Towards reliable storage of 56-bit secrets in human memory. In: 23rd USENIX Security Symposium (USENIX Security 14). 2014. p. 607-623. 3 Některé firmy preventivně lámají hesla svých zaměstnanců. Pokud se to podaří, tak si zaměstnanec musí změnit heslo.


Úkol: dopočítejte minimální délky hesla pro jednotlivé entropie:

požadovaná entropie H v

bitech

číslice 0-9 písmena [a-z] bez rozlišení

velikosti

číslice, malá a velká písmena, [a-z, A-Z, 0-9]

tisknutelné znaky ASCII

tabulky diceware

10 26 62 95 7776

43

53

59

71

Entropie se používá pro vyjádření variability. V informatice se obvykle vyjadřuje pomocí logaritmu

o základu 2 (log2). Používá se též pro vyjádření síly (obtížnosti prolamování) hesel. PIN o čtyřech

číslicích lze sestavit 10 000 způsoby – na každém místě je 10 možností, vzájemně jsou nezávislé,

takže možnosti vynásobíme mezi sebou: 10 * 10 * 10 * 10. tj. 104. Entropie se vypočítá jako log2

počtu možností, tj.

log2 104 = 13.28771

V Excelu vzorec vypadá takto:

=LOGZ(10^4;2)

Pokud je náhodný výběr a jednotlivé znaky v hesle jsou rozmístěny rovnoměrně (to odpovídá výše

uvedené tabulce, porušením jsou pravidla typu minimálně jedno písmeno a minimálně jedna

číslice), tak entropie (e) závisí na počtu prvků v množině (N) a na počtu prvků, které je mají vybrat

(L):

S = log2 NL = L log2 N

Z toho se již snadno odvodí vzorec na požadovaný počet znaků v hesle:

L = S

log2 N

V Excelu je to včetně zaokrouhlení nahoru (buňky v závislosti na umístění tabulky):

=ZAOKR.NAHORU($A3/LOGZ(G$2;2);1)

požadovaná entropie H v

bitech

číslice 0-9 písmena [a-z] bez rozlišení

velikosti

číslice, malá a velká písmena, [a-z, A-Z, 0-9]

tisknutelné znaky ASCII

tabulky diceware

10 26 62 95 7776

43 13 10 8 7 4

53 16 12 9 9 5

59 18 13 10 9 5

71 22 16 12 11 6


b) InSIS generuje počáteční hesla dle schématu nnxxxnxxX (dvě číslice, tři malá písmena, jedna číslice,

dvě malá písmena, velké písmeno). Jaká je entropie těchto hesel? Kolikrát se zkrátí čas prolamování

pro 9 znaková hesla proti variantě testování všech variant z 62 znaků ([a-zA-Z0-9])?

schéma nnxxxnxxX – na prvním místě může být jedna z 10 číslice, na druhém opět jedna z deseti

číslic, na třetím místě jedno z 26 malých písmen, atd. Počet kombinací je následující:

10 * 10 * 26 * 26 * 26 * 10 * 26 * 26 * 26 = 103 * 266

Hesla se generují náhodně, tj. všechny varianty jsou stejně pravděpodobné, proto lze pro výpočet

entropie použít opět dvojkový logaritmus:

e = log2(103 ∗ 266) ≈ 38.2

Entropie náhodně generovaného 9 znakového hesla z 62 znaků je:

e = log2 629 ≈ 53.6

Rozdíl je 15 bitů, tj. čas se zkrátí přibližně 215 ≈ 32 000. Tj. pokud útočník otestuje všechny varianty

hesla dle uvedeného schématu za jednu hodinu, tak náhodná 9 znaková hesla otestuje přibližně za

4 roky.

c) Máte 8znaková hesla složená z malých/velkých písmen a číslic (minimálně jedno malé písmeno, jedno

velké písmeno a jedna číslice). Chcete zvětšit odolnost vůči prolamování hrubou silou. Více variant

(větší entropii) bude mít zvětšení minimálního počtu znaků na 9 či rozšíření abecedy o tisknutelné

znaky ASCII tabulky (tj. na 95 znaků)?

Hrubý výsledek se získá z porovnání hodnot 62^9 (rozšíření na 9 znaků hesla) a 95^8 (všechny

tisknutelné znaky).

Přesnější je ale počítat v první variantě, že musí být aspoň jedna číslice, aspoň jedno malé písmeno

a aspoň jedno velké písmeno. O zbývajících 6 znacích nic nevíme, tj. může tam být libovolný z 62

znaků z množiny.

𝟏𝟎 ∗ 𝟐𝟔 ∗ 𝟐𝟔 ∗ 𝟔𝟐𝟓

Podobně je potřeba upřesnit výpočet pro druhou variantu:

𝟏𝟎 ∗ 𝟐𝟔 ∗ 𝟐𝟔 ∗ 𝟗𝟓𝟒

Pokud si ale heslo vybírá sám uživatel, tak se obvykle množina 33 nepísmenných a nečíselných

znaků zmenší na 6 až 10 speciálních znaků (znaky tečka, plus, mínus, …). Zvlášť v českém prostředí,

kdy uživatelé musí přepínat mezi klávesnicemi či si pamatovat Alt a číselnou kombinaci (např. pro

znak @).

d) V následující tabulce je rychlost prolamování některých typů hesel pomocí CPU i pomocí GPU:


John the Ripper, Intel i7 2600 oclhashcat, AMD Radeon HD 7970

DEScrypt 18 284K/s 65 594K/s MD5 crypt 66,9K/s 3 592K/s Bcrypt, 4,8K/s 4,1K/s LM hash 88 834K/s 2 384M/s

Za jak dlouho by program oclhashcat otestoval všechny možné varianty počátečních hesel ze zadání

b) na grafické kartě AMD Radeon HD 7970, pokud jsou hesla uložena pomocí LM hash?

Toto vede k velmi jednoduchému výpočtu – počet variant se vydělí rychlostí, tj.

(103 ∗ 266)

2384000000

Výsledek je přibližně 130 sekund. U algoritmu LM hash by bylo prolamování bylo ještě rychlejší – v algoritmu LM hash je maximální délka hesla 14 znaků, pokud je kratší, tak se doplní binárními nulami. Dále se všechna písmena hesla převedou na velká – to nám v našem příkladu nepomůže, neboť víme dopředu velikost písmen. Následně se heslo rozdělí na dvě poloviny po 7 znacích. Každá polovina má délku 56 bitů, která se použije jako klíč pro šifrovací algoritmus DES pro zašifrování řetězce „KGS!@#$%”. Výsledky se spojí do jednoho výsledného řetězce. Prolamování se tudíž rozpadne na dvě části:

a) louskání řetězců nnXXXnX, tj.

(103 ∗ 264)

2384000000

b) louskání řetězců XX

(262)

2384000000

Výsledek je přibližně 0,2 sekundy. LM hash je z dnešního pohledu velmi špatně navržený algoritmus pro ukládání hesel.

e) Spočtěte průměrnou dobu pro prolomení jednoho náhodně vygenerovaného hesla uloženého

pomocí MD5, pokud útoční použije program oclhashcat a AMD Radeon HD 7970:

entropie hesla doba louskání ve vteřinách doba louskání ve dnech

16

32

40

48 Budou se lišit výsledky v případě, že heslo je uloženo se solí o délce 48 bitů?

To jsou opět jednoduché výpočty. Entropie je mocnina o základu 2, takže např. všechny varianty

hesel s entropii 16 se otestují za

(216)

3 592 000

tj. asi 0,018 vteřiny. V zadání se ale mluví o průměrné době pro prolomení – výsledek je potřeba

vydělit dvěma. Některé heslo se najde hned a některé až téměř po prozkoumání téměř všech

kombinací.


Sůl na tyto výpočty nemá vliv – v zadání se mluví o prolomení jednoho náhodně vygenerovaného

hesla.

Situace se změní, pokud by se mělo prolamovat např. 100 hesel. Pokud se nepoužije sůl, tak

všechna hesla se najdou za 0,018 sekundy. Pokud by pro každé heslo byla jiná sůl, tak na prolomení

každého hesla potřebujete v průměru 0,009 sekundy a všechny budete mít za 0,9 sekundy.

f) Entropie hesel vytvářených uživateli se měří poměrně špatně. Knihovna zxcvbn odhaduje entropii na

základě existence částí hesla ve slovnících nejčastějších hesel plus zohledňuje „běžné“ operace

obsažené v nástrojích pro lámání hesel. Přidává entropii za použití velkých písmen či substituci znaků

(např. o se nahradí číslicí 0). Odebírá za posloupnosti či za opakování stejných znaků či skupin znaků.

Heslu poté přiřadí skóre dle následující tabulky:

Skóre Skóre text Entropie od Entropie do

0 velmi slabé 0 < 10

1 slabé 10 < 20

2 průměrné 20 < 27

3 silné 27 < 33

4 velmi silné 33

Ve vytvářené aplikaci hesla před uložením do databáze hašujete pomocí PBKDF2 s funkcí HMAC-SHA-

256 (v každé iteraci se provádějí dvě operace SHA-256). V pravidlech pro hesla požadujete minimální

skóre 3. Předpokládáte, že v systému bude uloženo přibližně 20 000 účtů. Vašim úkolem je spočítat

počet iterací pro PBKDF2 tak, aby se výrazně snížilo nebezpečí odhalení hesel při ukradení celé

databáze. Předpokládáte, že útočník pro prolamování použije počítač s grafickou kartou AMD HD

7970, na které je schopen spočítat 1 032 milionů SHA-256 haší za sekundu (1 032 MH/s). Za jeden

den by měl útočník získat v průměru jedno heslo, útočník používá útok hrubou silou.

Útočník za den provede

(1032000000

2) ∗ (60 ∗ 60 ∗ 24) ≈ 4,4 ∗ 1013

operací HMAC-SHA-256. Zadávaná hesla mají minimální entropii 27, tj. jako by uživatelé vybírali

heslo z množiny 227 variant. Potřebný počet iterací se spočte již jednoduše (násobení dvěma je za

50% pravděpodobnost):

4,4∗ 1013

227 ∗ 2 ≈ 664330

Tj. nastavit 664330 iterací. Předpokládáme, že každé heslo má svoji vlastní dostatečně dlouhou sůl.

Všechna hesla nebudou mít entropii 27, průměr odhaduji okolo 33. Bylo by možné použít toto číslo

ve výpočtu (potřebný počet iterací se sníží na přibližně 10 tisíc), ale dostávali bychom „falešné“

výsledky. Stále by se našlo v souboru dostatek hesel s entropii 27 a tudíž první dny/týdny by útočník

získal velké množství hesel. Pokud by v souboru byly 5% hesel s entropii 27 a útočník se rozhodne

hádat heslo někoho z těchto uživatelů, tak ho získá v průměru za 23 minut.


Existuje ještě jedna úvaha – útočník bude zkoušet získat heslo libovolného uživatele. A bude

postupovat tak, že vygeneruje možné heslo a poté postupně zkouší hádat jednotlivé uživatele. Tj. u

každého uživatele vezme sůl, přidá ji k heslu a poté udělá potřebný počet iterací. Zde by při 10000

iteracích získal všechna hesla s entropii 27 za 602 dní, v průměru 1,5 hesla za den. Za den by

otestoval 223 tisíc různých hesel pro všech 20000 solí

´ 4,4∗1013

10000∗20000 ≈ 223 000

Všechny varianty hesel s entropii 27 otestuje za

227

223000 ≈ 602 dní

Na první pohled by pro zadání mohlo stačit přibližně 15 tis. iterací. Ale pořád je to za předpokladu,

že útočník si náhodou nevybere uživatele či skupinu uživatelů s nízkou entropií jejich hesla.

g) Pokračování předchozího zadání. Kolik uživatelů se bude moci za sekundu přihlásit na Vašem serveru

se čtyřmi jádry Intel Xeon E3-1230? Tento procesor zvládá 36 miliónů SHA256 operací za vteřinu na

jednom jádru.

Pokud v PBKDF2 nastavíte 664 330 iterací, tak jedno jádro za sekundu ověří heslo pouze 54

uživatelům.

36000000

664300 ≈ 54

Výsledek nelze automaticky rozšířit na 4 jádra – procesory musí zajistit i další operace, nějaký čas

zabere režie. Odhaduji, že server by byl schopen ověřit 100 hesel za vteřinu.

h) varianta zadání f). Při těžbě Bitcoinů se počítají haše SHA-256, na stránce

https://en.bitcoin.it/wiki/Mining_hardware_comparison je přehled dostupného hardware pro těžbu

bitcoinů včetně rychlosti operací SHA-256.

Při výpočtu počtu iterací pro PBKDF2 dle zadání f) předpokládejte, že útočník má přístup ke

specializovanému hardware pro prolamování hesel, který má stejnou rychlost operací SHA-256 jako

nejrychlejší zařízení na těžbu bitcoinů s cenou do 3 000 USD. Spočtěte potřebný počet iterací, pokud

budete vyžadovat velmi silné heslo dle knihovny zxcvbn.

Obdoba předchozích výpočtů. Smyslem zadání je, abyste se zamysleli nad možnostmi

specializovaného hardware pro prolamování hesel.

Stav k 20. únoru 2016 – za 2 307 USD se prodává AntMiner S5+, které spočítá 7 722 000 MHash za

sekundu. Pokud by ve variantě h správce nastavil v PBKDF2 1 milión iterací, tak útočník se

specializovaným hardwarem stejné výkonnosti za vteřinu otestuje téměř 4 miliony hesel.

Pokud chci jedno heslo za den, tak by se muselo nastavit přibližně 77 mil. operací za vteřinu.


Je z toho vidět obrovská nevýhoda PBKDF2 v kombinaci s klasickými hašovacími funkcemi jako je

SHA-256 – útočník louskající hesla má obrovskou převahu. Pro ukládání hesel by se měly používat

algoritmy, které nelze levně implementovat do specializovaného hardware. Další variantou je

zavést vícefaktorovou autentizaci či přihlašování pomocí klíčů uložených na USB tokenech/čipových

kartách.

Specializované ASICy pro těžbu Bitcoinů naštěstí nelze přímo použít pro prolamování hesel. Pro

jejich výrobce je ale poměrně jednoduché upravit návrh obvodu tak, aby se pro prolamování mohl

použít. Kolik se najde platících zájemců o tyto upravené obvody?

Zadání na entropii

i) Při vytváření virtuálních serverů ve VMware se náhodně generuje ethernetová adresa (6B). První tři

bajty jsou dány (00:50:56), další tři se náhodně generují. Jaká je pravděpodobnost kolize MAC adres v

podsíti s maskou /22 (1022 počítačů).

Následující popis převzat z české Wikipedie:

V teorii pravděpodobnosti je narozeninovým problémem (či narozeninovým paradoxem) myšlena

pravděpodobnost, že pro skupinu náhodně vybraných 23 (či více) lidí, je více než 50%

pravděpodobnost, že nějací dva lidé budou mít narozeniny ve stejný den. Pro 57 a více lidí je ona

pravděpodobnost více než 99%, postupně rostoucí až ke 100 % pro 366 lidí (za předpokladu že

pracujeme s rokem o 365 dnech).

Výpočet. Je jednodušší nejprve spočítat pravděpodobnost, že všech „n“ narozenin je rozdílných. Pro

„n“ > 365 je tato pravděpodobnost rovna nule. Pro „n“ ≤ 365 je dána následujícím vzorcem, protože

druhá osoba nemůže mít stejné narozeniny jako první (364/365), třetí nemůže mít stejné

narozeniny jako první dvě (363/365), atd.:

p̅ = 1 ∗ (1 − 1

365) ∗ (1 −

2

365) ∗ … .∗ (1 −

n − 1

365)

Skutečnost, že nejméně dva z „n“ lidí mají stejné narozeniny je komplementární jevu, že všechny

data narozenin jsou různé. Proto pravděpodobnost p je

p = 1 − p̅

Tato pravděpodobnost překračuje 50% pro „n“ = 23 (pravděpodobnost kolize je ≈50,7 %).

Pokud ze sady o velikost H vybereme n prvků, tak pravděpodobnost kolize lze spočítat dle

následujícího přibližného vzorce:

p ≈ 1 − e−n2/2H

V našem příkladu za H doplníme 224 (poslední tři byty MAC adresy mají 24 bitů), za n doplníme

1022. Pravděpodobnost kolize je 3,06 %.


Nejmenší množství n vybraných prvků k dosažení p pravděpodobnosti kolize spočítáme dle

následujícího přibližného vzorce:

n ≈ √2H ∗ ln1

1 − p

j 2015) Předpokládejte, že všech 20 000 uživatelů na škole si vygeneruje PGP klíč. Běžně se tyto klíče

identifikují pomocí ID o délce 32 bitů (např. 0xB9F8D6D9), které má náhodné rozdělení. Jaká je

pravděpodobnost, že dva uživatelé na škole budou mít u svého klíče stejné ID?

Do přibližného vzorce z předchozího příkladu za H doplníme 232, za n doplníme 20 000. Výsledek je

4,55%.

j 2016) Budete ukládat 20 000 hesel, pro každé uložené heslo vygenerujete náhodnou sůl. Kolik bitů má mít

sůl, aby pravděpodobnost stejné soli (tj. kolize) byla menší než 1%?

Sůl musí být dlouhá minimálně 15 bitů – 215 je 32768 a to je první číslo větší než počet uložených

hesel. Při této velikosti soli je pravděpodobnost existence kolize (tj. že minimálně dva uživatelé

budou míst stejnou sůl) rovná 100%.

Pro řešení úlohy jsem si v excelu vytvořil následující tabulku, ve kterém používám přibližný vzorec

pro výpočet pravděpodobnosti kolize: =1-EXP(-(20000^2)/(2*počet_variant))

bitů variant pravděpodobnost kolize 2 prvků

15 32768 100,00000%

16 65536 100,00000%

17 131072 100,00000%

18 262144 100,00000%

19 524288 100,00000%

20 1048576 100,00000%

21 2097152 100,00000%

22 4194304 100,00000%

23 8388608 100,00000%

24 16777216 99,99934%

25 33554432 99,74213%

26 67108864 94,92190%

27 134217728 77,46535%

28 268435456 52,52933%

29 536870912 31,10103%

30 1073741824 16,99460%

31 2147483648 8,89270%

32 4294967296 4,54986%

33 8589934592 2,30141%

34 17179869184 1,15740%


35 34359738368 0,58039%

36 68719476736 0,29062%

37 1,37439E+11 0,14541%

38 2,74878E+11 0,07273%

39 5,49756E+11 0,03637%

40 1,09951E+12 0,01819%

41 2,19902E+12 0,00909%

42 4,39805E+12 0,00455%

43 8,79609E+12 0,00227%

44 1,75922E+13 0,00114%

45 3,51844E+13 0,00057%

46 7,03687E+13 0,00028%

47 1,40737E+14 0,00014%

48 2,81475E+14 0,00007%

Tj. u soli s minimálně 35 bity je pravděpodobnosti existence kolize menší než 1%. V praxi se

doporučuje sůl o minimální délce 64 bitů. Algoritmus bcrypt používá sůl o délce 128 bitů.

Stará zadání a jejich řešení

d 2015) Spočítejte entropii hesel vytvářených uživateli v InSISu dle pravidel ze standardu NIST SP 800-63.

(verze úkolu z roku 2015)

V předchozích příkladech se předpokládalo, že všechny kombinace jsou stejně pravděpodobné.

Tento předpoklad v případě uživatelsky definovaných hesel neplatí. Příklad: máme dvě sady většího

množství kartiček, na každé kartičce je napsáno jedno z písmen „a“, „b“, „c“ a „d“. V první sadě

jsou písmena rozdělena náhodně a rovnoměrně, ve druhé sadě jsou písmena zastoupeny

s rozdílnou pravděpodobností, viz následující tabulka.

písmeno sada 1 sada 2

a 25% 60% b 25% 25% c 25% 10% d 25% 5%

Bude se postupně losovat 100 kartiček a máme uhodnout, jaké písmeno je na kartičce – u každé

kartičky zkoušíme, dokud písmeno neuhodneme. Kolik pokusů bude potřeba u jednotlivých sad?

U první sady je jedno, v jakém pořadí budeme hádat jednotlivá písmena. U druhé sady je výhodné

hádat písmena v závislosti na jejich četnosti v sadě, nejčastější jako první.

pořadí pokusu o uhodnutí

sada 1 sada 2

uhodnutých na pokus

celkem pokusů

uhodnutých na pokus

celkem pokusů

1. pokus 25 25 60 60

2. pokus 25 50 25 50


3. pokus 25 75 10 30

4. pokus 25 100 5 20

celkem x 250 160 Rozdílnou pravděpodobnost jednotlivých prvků v množině postihuje i entropie. Vzorec na výpočet

entropie se započtením pravděpodobností jednotlivých prvků Pi vypadá následovně:

S = ∑ − (Pi ∗ log2 Pi)

písmeno sada 1 sada 2

podíl −(𝑷𝑷 ∗ 𝐥𝐥𝐥𝑷𝑷𝑷) podíl −(𝑷𝑷 ∗ 𝐥𝐥𝐥𝑷𝑷𝑷)

a 25% 0,5 60% 0,44

b 25% 0,5 25% 0,50

c 25% 0,5 10% 0,33

d 25% 0,5 5% 0,22

entropie x 2,0 1,49

Většina uživatelů při vytváření hesla vychází ze slov nějakého jazyka. Jednotlivá písmena jsou na

sobě závislá – pokud je první písmeno „a“, tak v češtině bude na druhém místě nejčastěji „n“

(22,4%), poté „r“ (10,5%) či „l“ (10,2%)4. Písmeno „e“ bude na druhém místě jen

s pravděpodobností 0,6% – písmeno „e“ je přitom v češtině nejčastější. I tyto závislosti výrazně

snižují entropii hesel a usnadňují útočníkům jejich odhalování.

Počítat entropii pro závislé jevy je poměrně složité. Americký standardizační úřad vydal normu NIST

SP 800-63, která na základě entropie anglických slov stanoví následující zjednodušená pravidla pro

výpočet entropie uživateli vytvářených hesel:

za 1. znak se počítají 4 bity,

za 2. – 8. znak se počítají 2 bity (za každý),

za 9. – 20. znak se počítá 1,5 bitu,

za 21. – ... znak se počítá jeden bit,

bonus 6 bitů, pokud musí být minimálně 1 malé písmeno, minimálně 1 velké písmeno a minimálně 1 nepísmenný znak,

bonus 6 bitů, pokud má heslo méně než 20 znaků a provádí se kontrola navržených hesel

vůči slovníku.

V InSISu jsou následující pravidla pro heslo (viz příslušná stránka pro změnu hesla):

Minimální délka hesla je 9 znaků.

Heslo musí obsahovat alespoň jedno malé písmeno.

Heslo musí obsahovat alespoň jedno velké písmeno.

Heslo musí obsahovat alespoň jednu číslici.

Entropie je 4 + 7*2 + 1,5 + 6 = 25,5.

4 Vzal jsem český slovník pro aspell/ispell (ke stažení např. na https://packages.debian.org/cs/wheezy/aspell-dictionary), odstranil diakritiku, převedl na malá písmena a poté spočítal pravděpodobnosti výskytu. Ve slovníku je poměrně hodně slov z okolních států.


f 2015) Spočítejte entropii hesel vytvářených uživateli v InSISu a to dle pravidel ze standardu NIST SP 800-63.

V InSISu jsou v současné době následující požadavky na heslo:

Požadavky na heslo

Minimální délka hesla je 9 znaků. Heslo musí obsahovat alespoň jedno malé písmeno. Heslo musí obsahovat alespoň jedno velké písmeno. Heslo musí obsahovat alespoň jednu číslici.

Výpočet dle NIST je jednoduchý:

4 body za první písmeno

po dvou bodech za 2 až 8 písmeno, tj. 14 bodů

1,5 bodu za 9 písmeno

prémie 6 bodů za požadavek na malé písmeno, velké písmeno a nepísmenný znak (číslici)

Tj. celkem 25,5 bodu entropie. Odpovídá náhodně vygenerovanému heslu s entropii 25,5. Pro

některé výpočty se počítá, jako by bylo 225,5 kombinací hesel.

g 2015) Ve vytvářené aplikaci hesla před uložením do databáze hašujete pomocí PBKDF2 s funkcí HMAC-SHA-

256 (v každé iteraci se provádějí dvě operace SHA-256). V pravidlech pro hesla požadujete minimální

délku 9 znaků, z toho minimálně jedno malé písmeno, jedno velké písmeno a jeden nepísmenný

znak. Předpokládáte, že v systému bude uloženo přibližně 20 000 účtů. Vašim úkolem je spočítat

počet iterací pro PBKDF2 tak, aby se výrazně snížilo nebezpečí odhalení hesel při ukradení celé

databáze. Předpokládáte, že útočník pro prolamování použije počítač s grafickou kartou AMD HD

7970, na které je schopen spočítat 1 032 milionů SHA-256 haší za sekundu (1 032 MH/s). Za jeden

den by měl útočník získat v průměru jedno heslo, útočník používá útok hrubou silou. Předpokládejte

náhodně generovaná hesla o 9 znacích splňující pravidla.

O kolik bude potřeba zvýšit počet iterací, pokud budeme předpokládat uživateli vytvářená hesla, tj.

při výpočtu budete vycházet z entropie dle NIST 800-63.

Při náhodném generování dle uvedených pravidel vznikne 26 * 26 * 43 * 956 hesel o devíti znacích

(nepísmenných znaků je 95 – 26 – 26). To je přibližně 2,1E+16 variant. Útočník za den otestuje

4,4E+13 operací HMAC-SHA-256. Pokud by každý uživatel měl odlišnou sůl, tak odhalí jedno heslo

za přibližně 16 měsíců při jedné iteraci. Pokud by všichni uživatelé měli stejnou sůl, tak útočník

odhalí přibližně 42 hesel za den. Pro výše uvedený cíl - 1 heslo za den - by postačovalo 42 iterací.

Jiná situace je v případě, že heslo si volí uživatel a počítáte entropii dle NIST 800-63. Výsledná

entropie je 25,5 (viz úkol c), tj. odpovídají 225,5 ≈ 4,75E+07. Pokud u každého hesla bude odlišná sůl,

tak za den by útočník odhalil 931 310 hesel – je potřeba mít tento počet iterací v PBKDF2, vhodné

zaokrouhlit na 1 milión. Pokud by u všech hesel byla stejná sůl, tak je potřeba počet iterací

vynásobit ještě 20 000.

Uvedený výpočet ukazuje nevýhody počítání entropie dle NIST 800-63. Můj odhad je, že entropie

souboru hesel by se pohybovala mezi 30 až 35. Ovlivňují to dva faktory:


většina uživatelů v současné době vytváří složitější hesla, než ze slova (slovního spojení)

doplněného o číslici,

významná část uživatelů má heslo delší než 9 znaků.

Druhým problémem je, že uvedený výpočet nezohledňuje průběh prolamování uživatelsky

definovaných hesel. Efektivita se průběhem času snižuje. Odhaduji, že za první hodinu útočník získal

přibližně polovinu hesel (hašování s jednou iterací), za celý den by získal okolo 90% hesel. Pro získání

všech 20000 hesel by potřeboval mnoho let.

Pro zvýšení odolnosti vůči prolamování by bylo vhodné kontrolovat vytvářená hesla vůči slovníku,

popř. zavést vícefaktorovou autentizaci.

h 2015) Pokračování předchozího zadání. Kolik uživatelů se bude moci za sekundu přihlásit na Vašem serveru

se čtyřmi jádry Intel Xeon E3-1230? Tento procesor zvládá 36 miliónů SHA256 operací za vteřinu.

Pokud v PBKDF2 nastavíte 1 milión iterací, tak se za sekundu ověří heslo pouze 18 uživatelům.

Pokud by byla stejná sůl (z kryptografického hlediska je to nesmysl), tak se počet iterací vynásobí

20 000 a úměrně se zvýší nároky na kontrolu správnosti hesla – systém by byl nepoužitelný.

Date post:	23-Mar-2020
Category:	Documents
Upload:	others
View:	2 times
Download:	0 times

1. cvičení řešení úkolů - vse.cz · Řešení úkolů na 1. cvičení ze 4SA313 verze 30. 9....

Documents