Skip to content

Hes funkcije

Hes funkcije ulaz promenljive duzine transformisu u izlaz fiksne duzine i imaju sledece osobine:

  • deterministicnost $H(x) = y$ kad god da izracunam $H(x)$
  • nebitno koliko veliki podatak hes tog podatka je uvek fiknse duzine (obicno od 128b-512b)
  • brzo se racuna
  • jednosmerna funkcija, ako imamo y = H(x) skoro nemoguce iz y naci x
  • otpornost na kolizije slaba je za dato x nemoguce naci x' tako da je H(x) = H(x'), jaka je da je nemoguce naci bilo koje x i x' tako da je H(x) = H(x')

Primeri hes funkcija (informativno):

  • MD5 -> 128b hes
  • SHA-0 i 1 -> 160b hes
  • SHA-2 razne varijante (224-512b)
  • SHA-3 razne varijante (224-512b)
  • RIPEMD
  • Whirlpool

rodjendanski paradoks (zasto nam treba hes od bar 160b)

Gde se koristi:

  • Digitalni potpisi
  • comitment sema
  • HMAC
  • Decentralizovane hes mape
  • Blockchain
  • Merkle tree
  • Verifikacija fajlova
  • ...

Digitalni potpisi

Racuna se hes poruke, sifruje privatnim kljucem tako se dobije potpis, salje se poruka i potpis. Da proverimo potpis hesiramo poruku i proverimo da li su hes, potpis i javni kljuc povezani na odgovarajuci nacin.

Commitment Shema

Definicija

Commitment shema je kriptografski mehanizam koji omogućava osobi A da se "obaveže" na određenu vrednost iz nekog skupa — na način da:

  • Osoba B ne može saznati koja vrednost je izabrana, sve dok osoba A sama ne otkrije izbor (svojstvo skrivanja — hiding)
  • Osoba A ne može promeniti svoj izbor nakon što se obavezala (svojstvo vezivanja — binding)

Ova dva svojstva zajedno garantuju fer i poverljiv razmenu informacija između dve strane.

Motivacioni primer: Bacanje novčića preko telefona

Zamislimo sledeći scenario: osobe A i B žele da bace novčić kako bi odredile ko je za nešto zadužen. Problem nastaje kada se bacanje odvija na daljinu (npr. telefonom) — onaj ko baca novčić može jednostavno lagati o ishodu.

Problem

Osoba A baca novčić i saopštava ishod osobi B. Posto da B nije prisutna, A može reći bilo šta — sistem nije fer.

Rešenje pomoću commitment sheme

Protokol se odvija u dva koraka:

1. Faza obavezivanja (Commit) Osoba A baca novčić i generiše commitment — maskiranu verziju ishoda — koju šalje osobi B. B ne može iz toga zaključiti pravi ishod.

2. Faza otkrivanja (Reveal) Osoba B određuje šta se dešava u kom slučaju (npr. "glava — ti si zadužen, pismo — ja sam zadužena"). Nakon toga, osoba A otkriva pravi ishod zajedno sa dokazom da nije lažirala.

Na ovaj način, ni jedna strana ne može varati: A se obavezala pre nego što je B odredila pravila, a B ne može uticati na ishod bacanja.

Tehnička realizacija

Obavezivanje (Commit faza)

Commitment se generiše kriptografskom heš funkcijom uz dodatak nasumičnog salta:

commitment = H(salt || izbor)
  • H — kriptografska heš funkcija (npr. SHA-256)
  • salt — nasumično generisana vrednost koja sprečava napade rečnikom (bez salta, B bi mogla da heširanjem proveri sve moguće vrednosti)
  • izbor — vrednost na koju se A obavezuje

Osoba A šalje commitment osobi B. B vidi samo heš vrednost — iz nje ne može rekonstruisati originalni izbor.

Otkrivanje (Reveal faza)

Kada dođe vreme za otkrivanje, osoba A šalje osobi B:

(salt, izbor)

Osoba B samostalno izračunava:

H(salt || izbor)

i poredi rezultat sa primljenim commitment-om. Ako se vrednosti poklapaju, izbor je autentičan i nepromenjen.

HMAC — Hash-based Message Authentication Code

Definicija

HMAC je kriptografski mehanizam za proveru autentičnosti i integriteta poruke pomoću deljenog tajnog ključa. Svako ko poseduje ključ može:

  • Proveriti integritet — utvrditi da poruka nije izmenjena u prenosu
  • Proveriti autentičnost — utvrditi da je poruku kreirao neko ko poseduje isti tajni ključ

HMAC je primer simetričnog mehanizma autentičnosti — obe strane dele isti tajni ključ.

HMAC vs. Digitalni potpis

HMAC Digitalni potpis
Tip kriptografije Simetrična (deljeni ključ) Asimetrična (par javni/privatni ključ)
Ko može verifikovati? Samo onaj ko ima tajni ključ Bilo ko ko ima javni ključ
Neporecivost ❌ Ne pruža ✅ Pruža
Brzina Brži Sporiji
Tipična upotreba API autentikacija, TLS, JWT Sertifikati, potpisivanje dokumenata

Ključna razlika je u neporecivosti (non-repudiation): kod HMAC-a, pošto obe strane dele isti ključ, nije moguće dokazati trećoj strani ko je tačno potpisao poruku. Digitalni potpis to garantuje jer samo vlasnik privatnog ključa može potpisati.

Zašto ne koristiti naivno rešenje H(K || M)?

Prva intuitivna ideja bila bi jednostavno nadovezati ključ K na poruku M i heširati:

HMAC_naivno = H(K || M)

Problem: Length Extension napad

Većina heš funkcija koje se danas koriste (SHA-1, SHA-256, MD5...) zasnovane su na Merkle-Damgård konstrukciji. Kod ove konstrukcije, stanje heš funkcije na kraju procesiranja poruke direktno odgovara izlaznom hešu.

To znači da napadač koji zna H(K || M) može — bez poznavanja ključa K — izračunati:

H(K || M || padding || M')

za proizvoljni dodatak M', zajedno sa validnim HMAC-om za tu proširenu poruku. Ovo je tzv. length extension napad i čini naivno rešenje nesigurnim.

Ispravna HMAC konstrukcija

Standardni HMAC (definisan u RFC 2104) koristi dvostruko heširanje sa dve različite konstante:

$$\text{HMAC}(K, M) = H\big((K \oplus opad) \,||\, H((K \oplus ipad) \,||\, M)\big)$$

Parametri

Oznaka Opis
K Tajni ključ (proširuje se nulama do dužine bloka ako je kraći)
M Poruka čiji se integritet proverava
ipad Unutrašnja konstanta: 0x36 ponovljena do dužine bloka
opad Spoljašnja konstanta: 0x5C ponovljena do dužine bloka
⊕ Operacija XOR (ekskluzivno ILI)
\|\| Nadovezivanje (konkatenacija)

Tipične primene HMAC-a

  • TLS/HTTPS — verifikacija integriteta poruka u bezbednoj komunikaciji
  • JWT (JSON Web Token) — potpisivanje tokena za autentikaciju korisnika
  • API autentikacija — verifikacija da zahtev dolazi od legitimnog klijenta
  • IPsec — zaštita mrežnih paketa

AEAD — Authenticated Encryption with Associated Data - informativno

Motivacija

HMAC pruža autentičnost, ali ne i poverljivost — poruka ostaje čitljiva. Ukoliko je potrebno i šifrovati poruku i proveriti njen integritet, tradicionalni pristup je bio kombinovati šifarski algoritam i MAC zasebno. Ovo je podložno greškama u implementaciji (pogrešan redosled operacija može uvesti ranjivosti).

AEAD rešava ovo elegantno — šifrovanje i autentikacija su integrisani u jedan mehanizam.

Šta AEAD pruža?

Svojstvo Opis
Poverljivost Sadržaj poruke je šifrovan i nečitljiv bez ključa
Integritet Svaka izmena šifrovane poruke se detektuje
Autentičnost Potvrđuje da poruku nije izmenim neovlašćeni entitet
Associated Data Deo poruke može biti nešifrovan, ali i dalje autentifikovan

Šta su "Associated Data"?

Ovo je ključna osobina AEAD-a. Neke informacije moraju biti vidljive (nešifrovane) kako bi sistem funkcionisao, ali ipak moraju biti zaštićene od izmene.

Analogija sa pismom:

┌─────────────────────────────────────┐
│  Prima: Marko Marković              │  ← Vidljivo (nešifrovano)
│  Ul. Knez Mihailova 10, Beograd     │  ← ali autentifikovano
├─────────────────────────────────────┤
│                                     │
│  [Sadržaj pisma — šifrovan]         │  ← Šifrovano + autentifikovano
│                                     │
└─────────────────────────────────────┘

Popularni AEAD algoritmi

Algoritam Opis
AES-GCM Najrašireniji; koristi se u TLS 1.3, HTTPS
ChaCha20-Poly1305 Brži na uređajima bez hardverske AES podrške; koristi se u modernim VPN protokolima
AES-CCM Varijanta pogodna za uređaje sa ograničenim resursima (IoT)

HMAC vs. AEAD

HMAC AEAD
Šifrovanje ❌ Ne ✅ Da
Autentikacija ✅ Da ✅ Da
Associated data ❌ Ne ✅ Da
Složenost Niska Srednja
Trend Stariji standard Moderna preporuka

U savremenim implementacijama sigurnosnih protokola sve se više prelazi na AEAD upravo zbog toga što u jednom koraku pruža i poverljivost i autentičnost, smanjujući prostor za greške u implementaciji.

Decentralizovane hes mape (DHT) - informativno

Kljuc se hesira -> id

id -> odredjuje cvor/grupu cvorova koji su zaduzeni za podatak

tom cvoru trazimo podatak ili izmenu podatka

Najbitnije osobine: nema centralni server, dobro skalira

Primer: bittorent, distribuirane baze podataka...

bittorent uprosceno: pitam DHT mrezu ko ima ima podatak o peer-ovima za neki fajl, njega pitam za ip adrese, i krecem skidanje fajla

Blockchain

Ostavlja se za treci deo kursa

Merkle tree

Sta je merkle tree? 

                         ┌─────────────────────────┐
                         │      Merkle Root        │
                         │   H(H12 || H34) = R     │
                         └───────────┬─────────────┘
                                     │
                ┌────────────────────┴────────────────────┐
                │                                         │
        ┌───────┴────────┐                       ┌────────┴────────┐
        │      H12       │                       │       H34       │
        │  H(H1 || H2)   │                       │   H(H3 || H4)   │
        └───────┬────────┘                       └────────┬────────┘
                │                                         │
        ┌───────┴───────┐                         ┌───────┴───────┐
        │       H1      │                         │       H3      │
        │   hash(Tx1)   │                         │   hash(Tx3)   │
        └───────────────┘                         └───────────────┘
        ┌───────────────┐                         ┌───────────────┐
        │       H2      │                         │       H4      │
        │   hash(Tx2)   │                         │   hash(Tx4)   │
        └───────────────┘                         └───────────────┘
Merkle stablo je hijerarhijska struktura zasnovana na heš funkcijama koja omogućava efikasnu i sigurnu proveru integriteta velikih skupova podataka.

Listovi su hesevi podataka, svaki unutrasnji cvor sadrzi hes svoje 'dece', koren sadrzi hes kombinaciju svih podataka u strukturi, samim tim predstavlja sve podatke u strukturi. Promena bilo kog podatka menja koren stabla.

Gde mogu da iskoristim Merkle stabla: da uporedim sta se promenilo u nekom skupu fajlova, da pokazem da je neki podatak u skupu ...

primer sa gitom: unutar gita se cuva neka slicna stuktura Merkle stablu, sadrzaj fajla je list, sadrzaj foldera je spisak (imena fajla, prava i sadrzaj fajla,...) pravi se hijerarhija, commit je koreni hes svih podataka.

Verifikacija fajlova

Vlasnik fajla prilikom postavljanja fajla na internet postavi checksum, kada skinemo fajl izracunamo checksum rucno i proverimo da li se dobije isti rezultat

KDF (Key Derivation Function)

Koristi se da se od slabih lozinki napravi kriptografski kljuc (intuitivno: lozinka koja je "jaka" i precizno definisana (nepredvidiv, dovoljno dug, uniforman))

Razmena kljuca DH-protokolom -> $g^{a \cdot b}$ je zajednicka tajna, ovo nije dovoljno nasumicno da bude jak kriptografski kljuc - neki bitovi su verovatniji od drugih -> koristi se KDF da se od tajne napravi kljuc/kljucevi za simetricni sifarski sistem.

KDF rade na razlicite nacine, recimo jedan prost je lozinka+salt se hesira n puta (u ovom slucaju u bazi se cuva podatak salt, n i koji algoritam za hesiranje se koristi)

Sta se dobija koriscenjem KDF:

  • sporost - da bi probali jednu lozinku treba nam vise vremena nego bez KDF
  • jedinstvenost - salt nam daje jedinstvenost, ista sifra sa razlicitim saltom je skroz drugacija
  • neke KDF su memorijski zahtevne pa paralelizacija ne ide tako lako
  • login je dovoljno brz, ali su masovni pokusaji razlicitih lozinki preskupi