Uvod

Ova skripta je namenjena kao prateći materijal za vežbe u okviru kursa Kriptografija na master studijama. Cilj skripte je da prikaže osnovne probleme kojima se kriptografija bavi, kao i tehnike za njihovo rešavanje.

Skripta je podeljena u tri oblasti. Prva oblast pokriva osnovne kriptografske primitive, kao što su klasične i protočne šifre, blok šifre i heš funkcije. Druga oblast se bavi kriptografijom javnog ključa. Treća oblast pokriva modernije teme u kriptografiji i neke njihove primene.

Svako poglavlje sadrži kratak teorijski uvod, praćen detaljnim objašnjenjima protokola i algoritama zajedno sa njihovom implementacijom. Na kraju svakog poglavlja nalaze se i rešeni zadaci za vežbanje.

Osnovne kriptografske primitive

U ovom poglavlju predstavljamo osnovne kriptografske primitive koje se koriste u savremenoj kriptografiji. Ove primitive su temelj za izgradnju složenijih kriptografskih sistema i protokola.

Klasične i protočne šifre

Definicija problema

Ana i Boban žele da komuniciraju poverljivo putem javnog kanala (npr. pomoću interneta). Eva, koja prisluškuje komunikaciju, ne sme da sazna sadržaj poruka koje Ana i Boban razmenjuju. Na koji način Ana i Boban mogu da ostvare poverljivu komunikaciju?

Rešenje ovog problema svodi se na korišćenje šifri. Ana i Boban se mogu unapred dogovoriti o šifri i ključu koji će koristiti. Pod ključem podrazumevamo neki tajni podatak koji je poznat samo Ani i Bobanu, a pod šifrom podrazumevamo algoritam koji proizvoljnu poruku uz dati ključ transformiše u nisku koju nije moguće protumačiti i razlikovati od slučajne niske. Takvu nisku nazivamo šifrovana poruka ili šifrat.

Formalnije, šifra je par algoritama \((E, D)\), gde je \(E\) algoritam šifrovanja odnosno enkripcije, a \(D\) algoritam dešifrovanja odnosno dekripcije. Algoritam \(E\) kao argumente prima poruku \(m\) i ključ \(k\) i vraća šifrat \(c = E(k, m)\). Algoritam \(D\) kao argumente prima šifrat \(c\) i ključ \(k\) i vraća poruku \(m = D(k, c)\). Šifra je takva da za svaku poruku \(m\) i ključ \(k\) važi \(D(k, E(k, m)) = m\).

Klasične šifre

Sada ćemo predstaviti nekoliko klasičnih šifri koje su se istoriјski koristile za ostvarivanje poverljive komunikaciјe.

Cezarova šifra

Cezarova šifra je jedna od najjednostavnijih šifri. Enkripcija se vrši pomeranjem celog alfabeta za fiksan broj mesta \(k\). Na primer, za \(k = 3\), alfabet izgleda ovako:

A	B	C	D	E	F	G	H	I	J	K	L	M
D	E	F	G	H	I	J	K	L	M	N	O	P

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Q	R	S	T	U	V	W	X	Y	Z	A	B	C

Poruka \(m\) se onda šifruje tako što se svako slovo u poruci menja odgovarajućim slovom iz pomerenog alfabeta. Na primer, poruka HELLO se šifruje kao KHOOR. Dešifrovanje se, jasno, vrši inverznim mapiranjem karaktera.

Cezarova šifra je jednostavna, ali je veoma nebezbedna. Postoji samo 25 mogućih ključeva (pomeraja), pa je moguće probati sve mogućnosti i pronaći pravi ključ. Na primer, ako je data šifrovana poruka ZRUOG, možemo probati sve pomeraje \(k\) redom i dešifrovati šifrovanu poruku dok ne dobijemo smislen rezultat:

k=1  YQTNF
k=2  XPSME
k=3  WORLD

Ovaj postupak je moguće automatizovati statističkom analizom dobijenog teksta u slučaju dužih poruka. Preciznije, možemo izračunati učestalost pojavljivanja svakog slova u dobijenom tekstu. Svaki jezik ima karakterističnu raspodelu učestalosti slova, pa možemo uporediti dobijenu raspodelu sa poznatom raspodelom za ciljani jezik i izabrati onaj pomeraj koji daje najpribližniju raspodelu. Na slici je prikazana učestalost pojavljivanja slova u engleskom jeziku.

Učestalost slova u engleskom jeziku

Naredna funkcija implementira jedan od načina za izračunavanje udaljenosti raspodele učestalosti u poruci u odnosu na poznatu raspodelu za engleski jezik.

def analyze(message, freq_eng):
  frequencies = {letter: 0.0 for letter in ascii_lowercase}
  for letter in message:
    if letter.islower():
      frequencies[letter] += 1 / len(message)

  score = 0
  for letter in ascii_lowercase:
    score += abs(frequencies[letter] - freq_eng[letter]) / 26
  return score

Nju možemo iskoristiti da pronađemo pravi pomeraj u Cezarovoj šifri, pokušavajući svaki mogući pomeraj:

for key in ascii_lowercase:
  message = "".join(dec(c, key) for c in ciphertext)
  score = analyze(message, freq_eng)
  if score < 0.01:
    print(f"Possible decryption for key {key} with score {score}")
    print(f"{message}")

Vižnerova šifra

Vižnerova šifra je unapređenje nad Cezarovom šifrom koje koristi ključ u vidu reči umesto fiksnog pomeraja. Svako slovo ključa određuje jednu vrednost pomeraja Cezarove šifre (na osnovu svoje pozicije u alfabetu), a svako slovo poruke se šifruje Cezarovom šifrom na odgovarajućoj poziciji. Na primer, ako je ključ SECRET, odgovarajući pomeraji su dati u sledećoj tabeli:

S	E	C	R	E	T
17	4	2	16	4	18

Onda se poruka HELLO šifruje tako što se H šifruje Cezarovom šifrom sa pomerajem 17, E šifruje Cezarovom šifrom sa pomerajem 4, itd. Rezultat šifrovanja je ZINCS. U slučaju da je poruka duža od ključa, možemo zamisliti da se ključ ponavlja dovoljan broj puta da pokrije celu poruku.

Vižnerova šifra je znatno bezbednija od Cezarove šifre, ali i dalje postoje efikasni napadi na nju. Na primer, možemo pokušati takozvani napad rečnikom. Ako je ključ kratak i poznatog je oblika (npr. jedna reč engleskog jezika, ili neka reč sa spiska korišćenih i otkrivenić ključeva), možemo pokušati da dešifrujemo poruku svim rečima iz rečnika. Zbog ovoga je najbolje koristiti nasumične, dugačke ključeve i ne upotrebljavati isti ključ više puta.

with open("dictionary.txt", "r") as file:
  for word in file:
    key = word.strip()
    message = "".join(dec(c, key[i % len(key)]) for i, c in enumerate(ciphertext))
    score = analyze(message, freq_eng)
    if score < 0.01:
      print(f"Possible decryption for key {key} with score {score}")
      print(f"{message}")

Postoje i sofisticiraniji napadi na Vižnerovu šifru. Na primer, ako je dužina ključa \(n\) poznata, možemo podeliti šifrovanu poruku u \(n\) grupa, gde svaka grupa sadrži karaktere koji su šifrovani pomoću istog pomeraja. Na primer, ako pretpostavljamo da je dužina ključa 3, onda delimo poruku HELLOWORLD u grupe H..L..O..D, .E..O..R.. i ..L..W..L.. Za svaku grupu onda možemo primeniti analizu učestalosti slova kao u Cezarovoj šifri da bismo otkrili odgovarajući pomeraj.

subtexts = [ciphertext[i::length] for i in range(length)]
key_candidates = [get_caesar_keys(subtext, freq_eng) for subtext in subtexts]

for key in ["".join(prod) for prod in product(*key_candidates)]:
  message = "".join(dec(c, key[i % len(key)]) for i, c in enumerate(ciphertext))
  score = analyze(message, freq_eng)
  if score < 0.01:
    print(f"Possible decryption for key {key} with score {score}")
    print(f"{message}")

Možemo pokušati sve moguće dužine ključeva redom dok ne pronađemo smislen rezultat. Ipak, dužinu ključa možemo pokušati i da procenimo pametnije. Primetimo da ako u šifrovanoj poruci postoji segment koji se ponavlja, moguće je da je u pitanju ista reč teksta koja je šifrovana istim delom ključa. Ako je tako, to znači da je razmak između ta dva ponavljanja deljiv sa dužinom ključa. Naravno, ne mora svako ponavljanje značiti da se ovaj scenario desio (ovo postaje očigledno ako gledamo segmente dužine jedan karakter), ali što je duži taj ponovljeni segment, to je verovatnije da se radi o takvom poklapanju. Možemo odabrati dužinu \(L\) i pronaći sve ponovljene segmente dužine \(L\) u šifrovanoj poruci. \(L\) biramo tako da bude dovoljno veliko da izbegnemo previše slučajnih ponavljanja, ali i dovoljno malo kako bismo uhvatili dovoljan broj ponavljanja. Dužina ključa je onda verovatno delilac nekog od razmaka između pronađenih ponavljanja. Radi ubrzanja postupka možemo preskočiti sve delioce koji se ne pojavljuju više od jednom. Ovaj postupak je poznat kao napad Kasiskog. U nastavku je njegova implementacija.

L = 5
gaps = []
for i in range(len(ciphertext) - L + 1):
  substring = ciphertext[i : i + L]
  gaps.extend(
    match.start() - i for match in re.finditer(substring, ciphertext[i + 1 :])
  )

divisors = {}
for gap in gaps:
  for d in get_divisors(gap):
    if d in divisors:
      divisors[d] += 1
    else:
      divisors[d] = 1

candidates = set()
for d in divisors:
  if divisors[d] > 1:
    candidates.add(d)

Nakon određivanja mogućih dužina ključeva, možemo pokušati da otkrijemo poruku svakom od njih, prethodno opisanim postupkom.

Jednokratna šifra (One-time pad)

Jednokratna šifra je šifra koja je teoretski neprobojna ako se koristi na pravilan način. Ključ je slučajan niz bitova koji je jednako dug kao i poruka. Enkripcija se vrši tako što se poruka kombinuje sa ključem pomoću operacije XOR, odnosno \(E(k,m) = k \oplus m\). Jasno, dekripcija se vrši na isti način, tj. \(D(k, c) = k \oplus c\).

Kako bi šifra zaista bila neprobojna, ključ mora biti slučajno generisan, iste dužine kao i poruka, korišćen samo jednom i čuvan u tajnosti. Ako bar jedan od ovih uslova nije ispunjen, šifra postaje podložna napadima.

Primera radi, recimo da smo poslali dve poruke \(m_{1}\) i \(m_{2}\) enkriptovane istim ključem \(k\). Neka su šifrati \(c_{1} = E(k, m_{1})\) i \(c_{2} = E(k, m_{2})\). Tada je \(c_{1} \oplus c_{2} = (k \oplus m_{1}) \oplus (k \oplus m_{2}) = m_{1} \oplus m_{2}\). Kako bismo najbolje prikazali koliko je ovo katastrofalno, posmatrajmo šta se dobije ako su \(m_{1}\) i \(m_{2}\) dve slike iste veličine:

OTP

Iako su slike pomešane XOR operacijom, moguće je tačno razaznati šta se nalazi na kojoj slici (lav na jednoj, put u pustinji na drugoj).

Jasno je da ove uslove nije lako ispuniti u praksi. Jedan od pokušaja da se napravi praktična jednokratna šifra je korišćenje generatora slučajnih bitova. Ukoliko je generator dovoljno dobar, moguće je generisati dugačke nizove bitova koji izgledaju nasumično i koristiti ih kao ključeve za OTP.

Protočne šifre

Protočne šifre zasnivaju se na generisanju pseudoslučajnog niza bitova na osnovu datog ključa, koji se na neki način kombinuje sa porukom, uglavnom XOR operacijom. Preciznije, neka je \(G\) pseudoslučajni generator (eng. pseudorandom generator, PRG) koji na osnovu ključa \(k\) generiše niz bitova \(b_{1}, b_{2}, \dots\). Tada možemo definisati protočnu šifru kao par algoritama \((E, D)\) gde je \(E(k, m) = G(k) \oplus m\) i \(D(k, c) = G(k) \oplus c\). Primetimo da je ovo suštinski jednokratna šifra, pri čemu sada ključ može biti kraći od poruke. Naglasimo da ovim još uvek nismo rešili problem ponovnog korišćenja ključa.

Obradićemo konstrukciju protočne šifre zasnovane na linearnim povratnim šift registrima. Ovakve protočne šifre su istoriјski bile veoma značajne, ali se danas ne koriste u kriptografske svrhe zbog svojih slabosti.

LFSR

Linearni povratni šift registar (eng. linear feedback shift register) drži stanje od \(n\) bitova \(s_{1}, \dots, s_{n}\). Svaki naredni bit pseudoslučajnog stanja računa se po formuli \(s_{i} = c_{n} s_{i - n} \oplus \dots \oplus c_{1} s_{i-1}\) gde su \(c_{1}, \dots, c_{n}\) bitovi koji definišu registar i služe da odaberu bitove trenutnog stanja na osnovu kojih se računa naredni bit stanja. Za LFSR je usko vezan polinom \(C(x) = c_{n} x^n + \dots + c_{1} x + 1\) sa koeficijentima u \(\mathbb{F}_{2}\).

Na primer, neka je LFSR dužine \(n=4\) definisan polinomom \(x^4+x^3+x+1\). To znači da se naredni bit stanja računa po formuli \(s_i = s_{i-4} \oplus s_{i-3} \oplus s_{i-1}\).

 ┌──>s[i-1] s[i-2] s[i-3] s[i-4]───> output
 │     │             │      │
 └───[          XOR          ]

Ako je početno stanje \(s_{i-1}, s_{i-2}, s_{i-3}, s_{i-4} = 1, 0, 0, 0\), prvih nekoliko koraka pomeranja registra izgleda ovako:

 1 0 0 0       1 1 0 0       1 1 1 0       0 1 1 1       0 0 1 1    
 |   | |       |   | |       |   | |       |   | |       |   | |    
 +---+-+-> 1   +---+-+-> 1   +---+-+-> 0   +---+-+-> 0   +---+-+-> 0

Naredna funkcija implementira LFSR generator sa početnim stanjem state. Generiše se b bitova pseudoslučajnog niza.

def lfsr(state: list[int], b: int) -> list[int]:
  stream = state + [0] * b
  for i in range(len(state), len(stream)):
    stream[i] = stream[i - 1] ^ stream[i - 3] ^ stream[i - 4]
  return stream[len(state):]

Implementaciju možemo uopštiti i da prihvata proizvoljni LFSR polinom u vidu liste pozicija koeficijenata čija je vrednost 1.

def lfsr(state: list[int], taps: list[int], b: int) -> list[int]:
  stream = state + [0] * b
  for i in range(len(state), len(stream)):
    for t in taps:
      stream[i] ^= stream[i - t]
  return stream[len(state):]

Od LFSR generatora možemo napraviti protočnu šifru tako što ključ koristimo kao početno stanje registra, a zatim generišemo niz bitova koji se kombinuju sa porukom pomoću XOR operacije. Veličina ključa mora da odgovara veličini registra.

def encrypt(key: bytes, message: bytes) -> bytes:
  keystream = lfsr(bytes_to_bits(key), 8 * len(message))
  return xor(bits_to_bytes(keystream), message)

def decrypt(key: bytes, ciphertext: bytes) -> bytes:
  keystream = lfsr(bytes_to_bits(key), 8 * len(ciphertext))
  return xor(bits_to_bytes(keystream), ciphertext)

Kako bismo rešili problem ponovnog korišćenja ključa, moramo osigurati da LFSR ne koristi isto početno stanje za različite poruke. Jedan od načina da se to izbegne je korišćenjem inicijalizacionog vektora (IV). Inicializacioni vektor je slučajni niz bitova koji se koristi zajedno sa ključem da bi se generisalo početno stanje LFSR. Na primer, početno stanje registra se može inicijalizovati kao konkatenacija ključa i inicijalizacionog vektora. Inicializacioni vektor se šalje zajedno sa šifratom kao javno dostupan podatak, kako bi primalac mogao da rekonstruiše početno stanje LFSR i dešifruje poruku. Ovo ne umanjuje bezbednost šifre, već samo osigurava da se za različite poruke koristi različito početno stanje LFSR.

Naredne funkcije implementiraju enkripciju i dekripciju pomoću LFSR sa inicializacionim vektorom. Veličina registra treba da bude jednaka zbiru veličine ključa i veličine inicijalizacionog vektora.

def encrypt(key: bytes, message: bytes, iv: bytes) -> bytes:
  keystream = lfsr(bytes_to_bits(key+iv), 8 * len(message))
  return xor(bits_to_bytes(keystream), message)

def decrypt(key: bytes, ciphertext: bytes, iv: bytes) -> bytes:
  keystream = lfsr(bytes_to_bits(key+iv), 8 * len(ciphertext))
  return xor(bits_to_bytes(keystream), ciphertext)

Primetimo da ukoliko znamo \(n\) uzastopnih bitova generisanih LFSR generatorom dužine \(n\), možemo lako odrediti sve bitove generatora (pošto su pozicije registra fiksirani, javni podaci). Sve naredne bitove možemo izračunati direktno primenom generatora. Prethodne bitove možemo izračunati obrtanjem relacije. Na primer, ako se naredni bit računa kao \(s_i = s_{i-1} \oplus s_{i-3} \oplus s_{i-4}\), onda važi \(s_{i-4} = s_i \oplus s_{i-1} \oplus s_{i-3}\), odnosno \(s_{j} = s_{j+4} \oplus s_{j+3} \oplus s_{j+1}\) uvođenjem smene \(j=i-4\). Naredna funkcija implementira određivanje prethodnih \(b\) bitova LFSR generatora na osnovu datih \(n\) bitova stanja.

def lfsr_reverse(state: list[int], b: int) -> list[int]:
  stream = [0] * b + state
  for j in range(b - 1, -1, -1):
    stream[j] = stream[j + 4] ^ stream[j + 3] ^ stream[j + 1]
  return stream[:b]

NLFSR

Jedan od načina da ojačamo LFSR generator je nelinearnim kombinovanjem više LFSR generatora u takozvani NLFSR (nelinearni povratni šift registar) generator. Prikazaćemo par primera NLFSR generatora.

Umanjujući generator

Umanjujući generator koristi dva LFSR. U svakom koraku pomeramo oba generatora za jedan korak. Ukoliko prvi generator vrati 1, na izlaz NLFSR generatora ispisujemo bit drugog generatora. Ako prvi generator vrati 0, bit drugog generatora se preskače.

 [LFSR A]───────┐
 [LFSR B]──[if A = 1]──> output

Primer:
 A: 0110101110
 B: 1010011100
 O:  01 0 110

Naizmenični generator

Naizmenični generator je NLFSR koji koristi tri LFSR generatora. Kontrolni generator se pomera u svakom koraku. U zavisnosti od toga da li je generisao 0 ili 1 bira se koji od druga dva LFSR generatora se pomera. Na izlaz NLFSR se ispisuje XOR izlaznih bitova drugog i trećeg LFSR (u XOR se koristi poslednji generisan bit generatora koji nije pomeren).

 [LFSR C]─┬─[LFSR A, clock if C = 0]─[XOR]─> output
          └─[LFSR B, clock if C = 1]───┘

Primer:
 C:  01100011
 A: 01..011..
 B: 1.01...01
 O:  01010010

Zadaci

Zadatak 1

Data je implementacija protočne šifre zasnovane na pseudoslučajnom generatoru \(G\). Objasniti slabost ove implementacije i ispraviti je.

def encrypt(key: bytes, message: bytes) -> bytes:
  generator = G(key)
  keystream = generator.generate(len(message))
  return xor(keystream, message)

def decrypt(key: bytes, ciphertext: bytes) -> bytes:
  generator = G(key)
  keystream = generator.generate(len(ciphertext))
  return xor(keystream, ciphertext)

Zadatak 2

Klijent i server komuniciraju koristeći ključ \(k\) i šifru iz Zadatka 1. Poruke koje razmenjuju definisane su nekim protokolom. Svaka poruka se dopunjava slučajnim bajtovima do 16 bajtova pre šifrovanja. Spisak validnih poruka je sledeći:

LOGIN|<id>
LOGOUT
PING
SYNC
GET_STATUS
GET_TIMESTAMP

Poznate su šifrovane poruke:

b83f0d799979e6a47f4681d646e7143f
a7290475db7e3e56edd221347d73acbf
b83f0d7f825185169f6daa2bd7c9b9a8
b3351e699864a920a85fda54f346db8d
b83f0d7f825185019662f52865572129

Odrediti ID svih korisnika iz LOGIN poruka, ako je poznato da je dužina ID-a 6 bajta.

Zadatak 3

Dat je šifrat 7dda6f65ea2aebf23a88925f66 dobijen šifrovanjem poruke pomoću LFSR kom odgovara polinom \(x^{16}+x^{15}+x^{13}+x^4+1\). Poznat je deo poruke .........f2c2.............. Odrediti celu poruku.

Zadatak 4

Dat je šifrat 296a9e72bc5a98f910274dafeff61c5bd3 dobijen šifrovanjem poruke pomoću LFSR kom odgovara polinom \(x^{16}+x^{15}+x^{13}+x^4+1\). Poznat je deo poruke ......6.75........................ Odrediti celu poruku.

Zadatak 5

Dat je šifrat dfa9dfc3a06c9506b6fcc1ad0d290af6fb92047d dobijen šifrovanjem poruke pomoću LFSR kom odgovara polinom \(x^{16}+x^{15}+x^{13}+x^4+1\), sa četvorobitnim inicijalnim vektorom 7. Poznat je deo poruke .........d617............................ Odrediti dvanaestobitni ključ i dešifrovati 2c3641c356038d362309704493c938221789db47 sa inicializacionim vektorom 9.

Zadatak 6

Poruka se šifruje pomoću protočne šifre zasnovane na LFSR kom odgovara polinom \(x^{32}+1\). Odrediti celu poruku. Pretpostaviti da je poruka tekst na engleskom jeziku.

190f53071804531b15000107500e155304091653121400071c081d145002
1a07094d53041804011650151b1650131b0a04091e531f07531f19071653
12041207034101161c041d071c0400001c185f53040916011541160b1912
07005000530205001a1d04411f1a04151f1650031c1c1b12071c0204531d
110c16175043041b190c001a13001f5300001416034f51531e0400071c04
17531204070415041d53040e041602081d145012180a0302011200040100
5c41071b191253101800011e190f1453180005161e410701110f00031f13
07005008070050171a0019151c010341071c500053041f131f17500e1553
1c0807160200010a50041d1018001d071d041d075e41071b1541001b150d
0516034d531f190f161750161a071841111c1f0a00531f0753121c0d5300
180003160341121d1441001a0a04005f50161b1a031116015015121f1512
531c1641121706041d070513165f50131c1e110f10165c41121d14411e0a
03151601094f530718045312020e1e12500e155311061617501112031513
53121e055307180453001f070753131316121b081d14500e1553070e1c17
150f53151c0e1c01120e12011412531002041207154112531e0e0007110d
141a1341121e1208121d1304530718000753150c11011102160050040516
0218530519121a071f135d530409165300131c03020816071f135f53110f
53161302161d04131a1050031a111c081c0318081f1650161a0718411253
00041d1018001d0750071c015012071c021807161c0d1a1d174d53140204
16070341100603151c1e151300530708071b5000530411131e53030c1a1f
1541121d1441125317041d06190f165300000000190e1d53160e01530409
165307131a0704041d53070e01175e41120050111207020e1d00500c1612
1e05160150151b011f14141b50151b1650001a001c04005f50151b160941
1e1209410007050c111f154106031f0f531b190517161e41121f130e0516
034112171f131d161441041a04095305190f07121704531f1500071b1513
5e111f141d1750021f1203121a1003411c0150021c090941011611051a1d
17411d1c1f0a0053070916011541071a1d04530015041e0050151c530315
121d14410007190d1f5d50081d5304091a00500c12141902121f50120312
13045f5304091653120e061d1400011a1512531115150416150f53011500
1f1a041853121e0553151902071a1f0f53111c14015f50001d1750040516
021853111f0e18531204101c1d0400531141031c0215121f50151c531141
171a16071601150f07530204121f1d4d531a1e171a07190f145302041217
15130053040e53161d0312011b411c1d500d1a07151312010941191c0513
1d1609125307180007530413121d0302161d1441071b1541101c1e071a1d
1512531c1641071b1541160515130a1711185d5307091a1e030810121c41
0312170400530315121d141253120341125304040007110c161d0441071c
50151b1650041d1705131a1d1741031c070401531f07531f191516011115
06011541071c501501121e12031c02155f53190f00031913165f50001d17
50021c1d1e04100750140053040e53071804530511120753040003160315
010a500e155318141e121e411a1e11061a1d11151a1c1e4f

Zadatak 7

Slika se šifruje pomoću protočne šifre zasnovane na LFSR kom odgovara polinom \(x^{16}+x^{15}+x^{13}+x^4+1\). Odrediti sadržaj slike.

01b09d5188d8926f83b90997b0aeebb28750b8dbb589ec341dc699d8ea7d
fc7d32534cadda6a307cb7e83a1495dd7d2079f8a5a4db0a631b5c65f50a
d6c8ab1aa92061c59a16ae74983d2abe643555c04566db6f1d512e2a7df5
874a8af5e45a41617ef0f62471223a335caff1adfdcf4adde17535a3474d
a88159916bcafe4b76f790635b735bf189b3acdc34c2aefe30e1794c6916
494bd0765ba614be5c203ccfe8e7ff83d3d5ace765777d9f7eb0308a83ab
1c0efc58fb444409e6fca092dd131b3f09c509912fc53f2d1bb77e74cafb
e3259ae68ee566190ea1f725aacabda90862be6b987b94188d5e6cb9b594
b992d83534699e573209a020dd4f8e9ce85d8afa706a1258db5203538abc
72f138ffb0c0a231657fb2d9903d783dc36c5dd84e2a4efe1525774b3f60
73cf66f129327140713177f9c3c78e7892f15223f3b70ad02833cfbe241f
872bbb3b318b6adff1fd3a890ff404286c4e0b2066a29f951d0a5d525f63
9aa76dae5815cdace0be2618ec1145a3b53bb36576ed0d8692c5ad5e3d51
85a9d8b36439992d3d6933401b46898a0fa339f94704530b33bd88bf157e
727f82612aa10aa6dcf5a7f1a9167582fec611e28468726c5edbfd266247
dc2518bc4c8e355c003916f6b1686e399cef14f0776393ddabbabc3310fe
8cf658e8890c8ff5d1535f57a501f3769b885d97c20c9b2ffe5a640828d8
39765081a2e23ff62a4ef101a2ec6a1500ad0fe614326a36666e68cad316
779bf5baf18c0bfc74ef7bf52e9d2b60b4852f3f1332bf38276e8c357a38
ee6dda701f4ffe0afb940aaf6b1cbe20abfc0708a064c853fa0938303f16
6961f3fab88ab835b4c367b12a10d4dce31f74e895bd52a2c9f8f294d40f
7dc4789b8b4da5ecaedcc85c3817696270df41810126829d3ad46f2379bb
a441b1b68fe65282fbdc2d190a26ff80bdccbf68d0c42a54fda13e569f06
2b2fda374e4a6e84007916574e75a35a6b63aa440b2b70f60c7798b338dc
91aa5e7296a216ba255ca893ffaf8aa7fcc41452d6756a13938881e68e5a
cc2875ea476e54cdd499bc21e36a058dce7505bf55a91009d1d09cdd69ae
c086214745437c781cfc7853c4cc93d2ff62121d7a6a3627cc9b16f22966
46f2254290a9e98587acde606d9720b85b326fe2c4c3719e873735a97051
153a9148dc59384a56819ff08c10756761ed9b1ee3a2e26dcfddce9b1697
2716571960a665e7603d747ed0fb7edca865122b5b4f042971eef5355801
14696197cafb3c691a29b5dabc94fefbc76300aff88b27c2543a94dccb47
aaf1eb88b7407c985088ec2c6349887ea707ffea1afcf33e8cfa80a84ca3
998f101fcab6c54dc31d3ff170eb9b1bb24436e50c190698abd0bab17be1
3a0f90007efce93b7cad3e2da43af4ec091ba5358d83ffb3f21f42949b7a
8d01b9442db6399e1c15f9af72faa21c00f57885d12eb6e2d3ebd3dece84
2887a3ce73cf8508b999e826ffd5add2b34ea4ccbd54ecca83a4aa5102b1
83ed5e1bfcd88762ca302eec822d7493fae27bb7c09328e420265dd8f887
fbe2bc35c2e0885c8ff1c1e35435162875ccbe54c8426dba87fd08721eab
1615806f8a27fecc6cc3518ef03771bb08054b8a81a3cc7b261370efc0c7
84400d558a0d012b2d37170c0fd42e8b920e6b1a7d34f47c8db697dce392
45277af8dbc23de7461f785846e9790d011fd0fd6df708e3de030b5e8298
cb4e4d2d6ae98e67384408c78a15128392744caf61286a05e2e64a169618
7a171de3e09f2bd66090ae26f38d798b4ea490ed35d56e9dd0b0ae1b7e6c
ea672d30889eff5f1c28e3a6abb803b892e79db0ffe7b347a681c7eaaae2
0caeb7f371a61dfea0ae3380a1b18d08a81acb77a69a3c44a46dbfa0d103
ec490d57ff7fcb4cb2fb22edf04a921eb0c41b996f018c4c6ca1f325774b
7c869ca7f0620c190870ead47c49e4ecfd7380db0803ea01c3b94e57c217
cc4b5476c210b6c19473bd534ee2d03b8cc3d3a7c0af166f5842c38b87ea
d8020262194b01c827583aab043e97c73d1b894bc6c943dbc320b0f32afa
7bbf7c7b13ce38204bf6f3eadd12a18db7b19890db7527c31006b8c551df
8c495a8ac948b1d79dbbeae09e69edf1607e3af100b3a27eb280bef9de3c
52b23703953b4a01b552d7e5f7dbc51bbfca901d2608ceaa859842b1b702
c75cf697040961f1638693f4297db6a9a74c8dd337ee62dfb63f820ec260
7a93a147fc087e7d429153ae2c3f1592a4d87cf05cc7a563b69cd987c044
3e0f138836f2c6468b8a94a429c2c5d1abc4ddc97d6a691feb06edd38788
51419c7921d514949cc425ac2677ced325dd82b5fb64ab7f3d1b25ffa72f
9297949e923ceab007a4214d2a41ed8c44e5778b3b94d5ff6b7ea918398c
087dcdbc2256cd1849e80bb2fb8516fd04df17faa4ad1d42ffb30b0a9e11
48a90ceb586fa39aea408f81a44ab656eebe179ab4a260376c149656c79a
5720ba5a16c3f4237faa0c3c43db46d75cbc29b4cc927df3a4ae864477c7
a0bbf40803e7866b96c605dc281a3191c9546e5cd15da68f1595e9a1defe
c28590076385e513b4b44c8648e2e7213e21be1bb45e480c5a9649463224
341a9d360d744461247552dfd7bccb1c97995d84e4334c19baae63f28a73
9431907950709301aa6b0a4ea3613eb5c295e4be80522d1394ded1e2c625
2fa997208f955b56565ef4a153ef23bf01b7ae5fcfe2aa23232b7f29499f
5e7cb2634586fd780c87e22ac89fb62b86d44ebecc9aba1d3382fda998eb
1b454b4b4d8fcf412678a136eb8fc80076d494cdc120338682c4c6050331
721904a6600490db5500c4b37b51e944946c0e203134124df713cc7d8b31
c5913a982039f089e26e15cd7fd5091b6bef54cb33b4c6fe563e3b9c4ec5
e8563827b8103f02a6505e7d02b99aae7881bbbd861d28bc5f0cddf56234
fe194f85d538034a2f3d5f88f5c03b49ccda1c4a4ba22419407b79bd3d0f
b0ccc8cc22ff3b3a6019130d67a2d6aa193d31fcc24cdc34830f31

Blok šifre, operacioni modovi i autentifikacija

Definicija problema

Ana i Boban žele da komuniciraju poverljivo putem nebezbednog javnog kanala (npr. pomoću javne WiFi mreže). Eva, koja kontroliše kanal, može da prisluškuje komunikaciju, ali i da menja sadržaj svake poruke. Na koji način Ana i Boban mogu da ostvare poverljivu komunikaciju, a da pritom otkriju ukoliko je bilo koja poruka izmenjena?

Blok šifre su osnovne kriptografske primitive nad kojima je izgrađena većina modernih šifarskih sistema. Osim što nude rešenje za problem poverljive komunikacije, takođe omogućavaju konstrukciju takozvane autentifikovane enkripcije.

Formalno, blok šifra je šifra \((E, D)\) pri čemu je veličina poruke, odnosno šifrata, fiksirana na \(n\) bitova. Kažemo da je \(n\) veličina bloka. Naglasimo da se, zbog tog uslova, blok šifrom ne mogu direktno šifrovati proizvoljne poruke. Za fiksirani ključ \(k\), funkcija \(E_k(m) = E(k, m)\) je permutacija skupa svih bitovskih niski dužine \(n\). Cilj prilikom dizajniranja blok šifre je da se funkcija \(E_k\) ponaša kao pseudoslučajna permutacija (eng. pseudorandom permutation, PRP) za svaki ključ \(k\).

Konstrukcije blok šifre

Uopšteno, blok šifre se konstruišu iterativnom primenom neke jednostavne invertibilne transformacije koja zavisi od ključa, pri čemu jednu iteraciju nazivamo rundom, a tu transformaciju funkcijom runde. Ključ \(k\) se proširuje u niz podključeva \(k_1, \dots, k_r\) (po jedan za svaku rundu) jednostavnim pseudoslučajnim generatorom.

def encrypt_block(key: bytes, block: bytes) -> bytes:
  keys = key_expansion(key, rounds)
  for k in keys:
    block = round_function(k, block)
  return block

def decrypt_block(key: bytes, block: bytes) -> bytes:
  keys = key_expansion(key, rounds)
  for k in reversed(keys):
    block = round_inverse(k, block)
  return block

Osnovne komponente

Dve osnovne komponente koje se koriste u konstrukciji blok šifri su P-tabela (P-box) i S-tabela (S-box).

P-tabela, uslovno rečeno, vrši permutaciju pozicija bitova. Preciznije, preslikava \(m\) ulaznih bitova u \(n\) izlaznih bitova promenom njihovog redosleda. P-tabela može da permutuje bitove u slučaju da je \(m=n\), ali i da proširi ako je \(n>m\), odnosno kompresuje ako je \(m>n\).

0 1 1 1 0 1 0 1         0   0   1   0         1 1 1 0 0 1 1 0
│ │ │ │ │ │ │ │         │   │   │   │         │ │ │ │ │ │ │ │
0 1 2 3 4 5 6 7         0   1   2   3         0 1 2 3 4 5 6 7
[    P-box    ]        [    P-box    ]        [    P-box    ]
3 2 7 6 1 0 5 4        0 1 2 3 3 2 1 0         0   2   4   6 
│ │ │ │ │ │ │ │        │ │ │ │ │ │ │ │         │   │   │   │ 
1 1 1 0 1 0 1 0        0 0 1 0 0 1 0 0         1   1   0   1

S-tabela je komponenta koja vrši supstituciju, odnosno preslikava \(m\) ulaznih bitova u \(n\) izlaznih bitova, najčešće definisana pomoću lookup tabele. Dobro odabrana S-box funkcija uvodi nelinearnost u šifru, otežavajući kriptoanalizu i pokušaje napada. Nelinearnost podrazumeva da se izlazni bitovi ne mogu izraziti kao linearne funkcije ulaznih bitova. Za razliku od S-tabele, P-tabela je linearna transformacija, jer se svaki izlazni bit \(y_j\) predstavlja trivijalnom formulom \(y_j = x_i\) gde je \(x_i\) neki ulazni bit. U nastavku je primer S tabele koja preslikava 4 bita u 3 bita:

4 bita -> 3 bita (prvi bit određuje red, preostala tri kolonu)

  │ 0 1 2 3 4 5 6 7
──┼────────────────
0 │ 6 0 1 7 2 4 5 3
1 │ 7 6 5 3 0 1 4 2

S(3)  = 7 jer je 3  = 0.011 odnosno (0, 3)
S(13) = 1 jer je 13 = 1.101 odnosno (1, 5)

Fajstelova mreža

Fajstelova mreža je konstrukcija koja omogućava da od proizvoljne funkcije \(f(k, b)\) formiramo blok šifru. Blok se deli na dva dela, \(b=l \parallel r\). U jednoj rundi Fajstelove mreže se blok transformiše po formuli \(l \parallel r \to r \parallel l \oplus f(k, r)\). Primetimo da je ova transformacija invertibilna, bez obzira na to da li je funkcija \(f\) invertibilna.

Fajstelova mreža

def round_function(key: bytes, block: bytes) -> bytes:
  n = len(block) // 2
  left, right = block[:n], block[n:]
  return right + xor(left, f(key, right))

def round_inverse(key: bytes, block: bytes) -> bytes:
  n = len(block) // 2
  left, right = block[:n], block[n:]
  return xor(right, f(key, left)) + left

DES je primer šifre zasnovane na Fajstelovoj konstrukciji. Radi nad blokovima veličine 64 bita, sa ključem veličine 56 bitova i izvršava se u 16 rundi. Funkcija \(f\) je definisana kombinovanjem nekoliko pažljivo odabranih S-tabela sa jednom P-tabelom.

SP mreža

SP mreža (eng. Substitution-Permutation network, SPN) je konstrukcija koja se zasniva na naizmeničnoj primeni S-tabela i P-tabele. Sve operacije moraju biti invertibilne kako bi dešifrovanje bilo moguće. Preciznije, u svakoj rundi se ključ runde kombinuje sa blokom pomoću xor operacije, zatim se na segmente bloka primenjuju S-tabele, nakon čega se primenjuje P-tabela. Naredne funkcije implementiraju rundu SP mreže i njenu inverznu funkciju. Ukoliko je veličina S-tabele \(s\) bita, funkcija sbox deli blok na segmente veličine \(s\) bita i na svaki segment primenjuje S-tabelu.

def round_function(key: bytes, block: bytes) -> bytes:
  block = xor(block, key)
  block = sbox(block)
  block = pbox(block)
  return block

def round_inverse(key: bytes, block: bytes) -> bytes:
  block = pbox_inverse(block)
  block = sbox_inverse(block)
  block = xor(block, key)
  return block

Kako je poslednja primena S-tabele i P-tabele invertibilna, potrebno je primeniti još jedan xor sa ključem na kraju šifrovanja. To znači da proširivanje ključa mora da generiše \(r+1\) podključeva.

def encrypt_block(key: bytes, block: bytes) -> bytes:
  keys = key_expansion(key, rounds)
  for k in keys[0:-1]:
    block = round_function(k, block)
  block = xor(block, keys[-1])
  return block

def decrypt_block(key: bytes, block: bytes) -> bytes:
  keys = key_expansion(key, rounds)
  block = xor(block, keys[-1])
  for k in reversed(keys[0:-1]):
    block = round_inverse(k, block)
  return block

AES je primer blok šifre zasnovane na SPN konstrukciji. Radi nad blokovima veličine 128 bita, sa ključevima veličine 128, 192 ili 256 bita i izvršava se u 10, 12 ili 14 rundi, zavisno od veličine ključa. Supstitucija (SubBytes korak) u AES se radi nad bajtovima. Konstruisana je kao kombinacija multiplikativnog inverza u \(F_{2^8}\) i afine transformacije. Permutacija u AES se vrši u dva koraka. Blok se posmatra kao matrica dimenzije 4x4 bajta. Prvo se vrši ciklično pomeranje redova matrice (ShiftRows korak), nakon čega se svaka kolona transformiše množenjem sa fiksnom invertibilnom matricom nad \(F_{2^8}\) (MixColumns korak). Iako MixColumns korak nije striktno P-tabela, on ispunjava ulogu mešanja bitova u bloku linearnom transformacijom i na taj način se može posmatrati kao uopštenje P-tabele.

Operacioni modovi

Kako bismo šifrovali poruke proizvoljne dužine koristeći blok šifre, potrebno je da definišemo operacioni mod šifrovanja.

ECB

ECB (eng. Electronic Codebook) je najjednostavniji operacioni mod. Poruka se deli na blokove i svaki blok se šifruje zasebno.

def encrypt(key: bytes, message: bytes) -> bytes:
  blocks = bytes_to_blocks(message)
  ciphertext = bytes()
  for block in blocks:
    ciphertext += encrypt_block(key, block)
  return ciphertext

def decrypt(key: bytes, ciphertext: bytes) -> bytes:
  blocks = bytes_to_blocks(ciphertext)
  message = bytes()
  for block in blocks:
    message += decrypt_block(key, block)
  return message

Primetimo da ukoliko veličina poruke nije deljiva veličinom bloka, ne možemo direktno primeniti ovaj pristup. Zato se svaka poruka dopunjava (eng. padding) do veličine deljive veličinom bloka. Ovaj postupak mora biti invertibilan kako bismo mogli da uklonimo dopunu prilikom dešifrovanja. Jedan od najčešće korišćenih načina za dopunu poruke je PKCS#7 standard, gde ukoliko je potrebno dodati \(p\) bajtova dopune, dodajemo tih \(p\) bajtova na kraj poruke, a svaki od tih bajtova ima vrednost \(p\). Na primer, ako je veličina bloka 8 bajtova, poruka 48 45 4C 4C 4F se dopunjuje sa tri bajta 03 03 03. Kako bi dopuna bila invertibilna, u slučaju da je poruka već deljiva veličinom bloka, dodaje se ceo novi blok. Recimo da treba šifrovati poruku 57 4F 52 4C 44 03 03 03. Ako je ne bismo dopunili, ne bismo mogli da razlikujemo između originalne poruke i poruke 57 4F 52 4C 44 koja je dopunjena sa tri bajta 03 03 03. Stoga, poruka se dopunjuje blokom 08 08 08 08 08 08 08 08.

def bytes_to_blocks(message: bytes) -> list[bytes]:
  padding = block_size - (len(message) % block_size)
  message += bytes([padding] * padding)
  return [message[i:i+block_size] for i in range(0, len(message), block_size)]

def check_and_remove_padding(message: bytes) -> bytes:
  padding = message[-1]
  if padding < 1 or padding > block_size:
    raise ValueError("Invalid padding")
  for i in range(1, padding + 1):
    if message[-i] != padding:
      raise ValueError("Invalid padding")
  return message[:-padding]

Naglasimo da ECB mod nije bezbedan za upotrebu u praksi, zbog toga što se isti blokovi poruke šifruju u isti blok šifrata. Sledeća slika najbolje illustruje ovaj problem.

ECB mod

CBC

Jedan od načina da se prevaziđu nedostaci ECB moda je korišćenjem CBC (eng. Cipher Block Chaining) moda. Blok poruke se pre šifrovanja kombinuje sa prethodnim blokom šifrata pomoću xor operacije. Za prvi blok se koristi nasumični inicijalizacioni vektor (IV). Slično kao i kod ECB moda, poruka se dopunjava do veličine deljive veličinom bloka.

def encrypt(key: bytes, message: bytes, iv: bytes) -> bytes:
  blocks = bytes_to_blocks(message)
  cipher = [iv]
  for block in blocks:
    cipher.append(encrypt_block(key, xor(block, cipher[-1])))
  return blocks_to_bytes(cipher)

def decrypt(key: bytes, ciphertext: bytes) -> bytes:
  blocks = bytes_to_blocks(ciphertext)
  message = bytes()
  for i in range(1, len(blocks)):
    message += xor(decrypt_block(key, blocks[i]), blocks[i-1])
  return message

CTR

Moderaniji pristup šifrovanju blok šifrom je CTR (eng. Counter) mod. Ovo je način da se od blok šifre konstruiše protočna šifra. Počevši od nekog slučajno odabranog brojača, odnosno inicijalizacionog vektora \(n\) (eng. nonce), generiše se niz blokova \(E(k, n), E(k, n+1), E(k, n+2), \dots\). Poruka se kombinuje sa ovim blokovima pomoću xor operacije. Za razliku od prethodna dva moda, ovde nije potrebna dopuna poruke. Još jedna prednost CTR moda je što se blokovi mogu šifrovati paralelno, što nije slučaj kod CBC moda. Takođe, dešifrovanje se ne oslanja na algoritam dešifrovanja blok šifre, što može pojednostaviti implementaciju.

def encrypt(key: bytes, message: bytes, n: int) -> bytes:
  keystream = bytes()
  for i in range(0, 1 + len(message) // block_size):
    keystream += encrypt_block(key, int.to_bytes(n + i, block_size))
  return xor(message, keystream)

def decrypt(key: bytes, ciphertext: bytes, n: int) -> bytes:
  keystream = bytes()
  for i in range(0, 1 + len(ciphertext) // block_size):
    keystream += encrypt_block(key, int.to_bytes(n + i, block_size))
  return xor(ciphertext, keystream)

Kodovi za autentifikaciju

Blok šifre možemo koristiti kao osnovu za konstrukciju kodova za autentifikaciju poruka (eng. message authentication code, MAC). Ukratko, uz svaku poruku \(m\) pomoću tajnog ključa \(k\) računamo kratak podatak, tzv. tag \(t = \text{MAC}(k, m)\), koji šaljemo uz poruku. Primalac, koji takođe poseduje ključ \(k\), može da proveri da li je poruka autentična tako što nezavisno izračuna tag primljene poruke i uporedi ga sa primljenim tagom. Ukoliko se tagovi ne poklapaju, znamo da je poruka izmenjena ili da ne potiče od pošiljaoca koji poseduje ključ.

CBC-MAC

Jedan od najjednostavnijih načina da se konstruše MAC je korišćenjem CBC operacionog moda. CBC-MAC se računa tako što se poruka transformiše u CBC modu sa inicijalizacionim vektorom postavljenim na nulu, a kao tag se uzima poslednji izračunat blok. Naglasimo da se ovde CBC mod ne koristi za šifrovanje poruke, kao i da sama poruka ne mora uopšte biti tajna ako to nije neophodno.

def mac(key: bytes, message: bytes) -> bytes:
  blocks = bytes_to_blocks(message)
  cipher = [int.to_bytes(0, block_size)] # Prvi blok je IV = 0
  for block in blocks:
    cipher.append(encrypt_block(key, xor(block, cipher[-1])))
  return cipher[-1]

def verify(key: bytes, message: bytes, tag: bytes) -> bool:
  return mac(key, message) == tag

Napomenimo da je CBC-MAC u ovom obliku bezbedan samo za poruke fiksne dužine. U suprotnom, moguće je izvesti napade na autentičnost poruka. Neka su poznate dve poruke \(m_{1}\) i \(m_{2}\) sa odgovarajućim tagovima \(t_{1}\) i \(t_{2}\). Napadač može da konstruše novu poruku \(m_{3} = m_{1} \parallel m_{2}^{\prime}\) gde se \(m_{2}^{\prime}\) dobija od \(m_{2}\) tako što se prvi blok xor-uje sa \(t_{1}\). Odgovarajući tag \(t_{3}\) za ovu poruku biće jednak \(t_{2}\) zato što prilikom računanja CBC za prvi blok \(b^{\prime}\) poruke \(m_{2}^{\prime}\) važi \(E(k, b^{\prime} \oplus t_{1}) = E(k, b \oplus t_{1} \oplus t_{1}) = E(k, b)\) gde je \(b\) prvi blok poruke \(m_{2}\). To znači da napadač može da konstruiše poruku sa validnim tagom bez poznavanja ključa.

Jedan od načina da se ovaj problem izbegne je da se na početak svake poruke doda jedan blok koji sadrži dužinu poruke. Na taj način, prethodni napad nije moguć jer dužina poruke \(m_{3}\) ne bi odgovarala dužini poruke \(m_{2}\), što znači da tag \(t_{2}\) ne bi bio validan za poruku \(m_{3}\).

def mac(key: bytes, message: bytes) -> bytes:
  length = int.to_bytes(len(message), block_size)
  blocks = [length] + bytes_to_blocks(message)
  cipher = [int.to_bytes(0, block_size)]
  for block in blocks:
    cipher.append(encrypt_block(key, xor(block, cipher[-1])))
  return cipher[-1]

def verify(key: bytes, message: bytes, tag: bytes) -> bool:
  return mac(key, message) == tag

Enkripcija i autentifikacija

Ukoliko želimo da ostvarimo i poverljivost i autentičnost poruka, možemo kombinovati šifrovanje i MAC. Koristimo dva različita ključa za ove dve operacije. Postoje tri osnovna pristupa:

Encrypt-then-MAC: Prvo se poruka šifruje, a zatim se nad šifratom računa MAC.
Encrypt-and-MAC: Poruka se šifruje i nad njom se računa MAC.
MAC-then-encrypt: Prvo se računa MAC nad porukom, zatim se poruka i tag kombinuju i šifruju zajedno.

Od ova tri pristupa, Encrypt-then-MAC je najotporniji na napade. Bez ulaženja u detalje, na intuitivnom nivou možemo razumeti princip da ne želimo uopšte da pokušamo da dešifrujemo poruku ukoliko nismo sigurni da je autentična.

Zadaci

Zadatak 1

Definisana je blok šifra na sledeći način:

# P-box permutuje bajtove
pbox_table = [3, 0, 1, 2, 7, 4, 5, 6]

def pbox(block: bytes) -> bytes:
  return bytes(block[i] for i in pbox_table)

def encrypt_block(key: bytes, block: bytes) -> bytes:
  assert len(block) == 8
  assert len(key) == 16
  keys = [key[i:i+8] for i in range(0, 16, 8)]
  for k in keys[0:-1]:
    block = xor(block, k)
    block = pbox(block)
  block = xor(block, keys[-1])
  return block

Neka je poznato da se šifrovanjem bloka 62 6c 6f 6b 73 69 66 72 dobija blok 6d 64 64 3b 7d 7f 63 61. Odrediti blok koji se šifruje u 72 76 7a 3b 6e 63 69 69.

Zadatak 2

Definisana je blok šifra na sledeći način:

# P-box permutuje bajtove
pbox_table = [3, 0, 1, 2, 7, 4, 5, 6]

def pbox(block: bytes) -> bytes:
  return bytes(block[i] for i in pbox_table)

def encrypt_block(key: bytes, block: bytes) -> bytes:
  assert len(block) == 8
  assert len(key) == 24
  keys = [key[i:i+8] for i in range(0, 24, 8)]
  for k in keys[0:-1]:
    block = xor(block, k)
    block = pbox(block)
  block = xor(block, keys[-1])
  return block

Neka je poznato da se šifrovanjem bloka 6a 61 3c 33 6d 61 74 66 dobija blok 1f 4c 06 10 1c 14 5a 05. Odrediti blok koji se šifruje u 59 1b 1c 1e 1e 53 45 05.

Zadatak 3

Definisana je blok šifra na sledeći način:

import aes

def sbox(block: bytes) -> bytes:
  return bytes(aes.sbox[b] for b in block)

def encrypt_block(key: bytes, block: bytes) -> bytes:
  assert len(block) == 16
  assert len(key) == 16
  keys = [key] * 4
  for k in keys[0:-1]:
    block = xor(block, k)
    block = sbox(block)
  block = xor(block, keys[-1])
  return block

Neka je poznato da se šifrovanjem bloka 43 6f 6d 70 75 74 65 72 20 73 63 69 65 6e 63 65 dobija blok a1 38 56 72 9f 84 99 a5 54 c5 84 1f 1b b5 28 99, kao i da se šifrovanjem bloka 52 61 63 75 6e 61 72 73 6b 65 20 6e 61 75 6b 65 dobija blok d7 26 85 bb 4b 80 cf 49 ed a0 55 cc 26 ee 31 99. Odrediti ključ korišćen prilikom šifrovanja.

Zadatak 4

Definisana je blok šifra na sledeći način:

import aes

def sbox(block: bytes) -> bytes:
  return bytes(aes.sbox[b] for b in block)

# P-box permutuje bajtove
pbox_table = [3, 0, 1, 2, 7, 4, 5, 6]

# P tabela prvo rasporedjuje bitove tako da j-ti bit i-tog bajta
# postane i-ti bit j-tog bajta
# Zatim se vrsi permutacija bajtova
def pbox(block: bytes) -> bytes:
  bits = bytes_to_bits(block)
  shuffled = [0] * len(bits)
  for i in range(8):
    for j in range(8):
      shuffled[i * 8 + j] = bits[j * 8 + i]
  shuffled_bytes = bits_to_bytes(shuffled)
  return bytes(shuffled_bytes[i] for i in pbox_table)

def encrypt_block(key: bytes, block: bytes) -> bytes:
  assert len(block) == 8
  assert len(key) == 8
  block = xor(block, key)
  block = sbox(block)
  block = pbox(block)
  block = xor(block, key)
  return block

Neka je poznato da se šifrovanjem bloka 726163756e617269 dobija blok 49c69a043f667533, šifrovanjem bloka 73706d72657a613b dobija se blok c11cdfed6a6a42a0 i šifrovanjem bloka 6173646667686b6c dobija se blok fd809dee3393e9c5. Odrediti ključ korišćen prilikom šifrovanja.

Zadatak 5 (u izradi)

SPN sa linearnim S

Zadatak 6

Data je blok šifra konstruisana Fajstelovom konstrukcijom u dve runde, sa funkcijom runde \(f(k, r) = r \oplus k\), nad blokom veličine 8 bajtova. Ključ ima 8 bajtova, od toga se prva 4 koriste u prvoj rundi, a poslednja 4 u drugoj rundi. Ako je poznato da se šifrovanjem bloka 3c 6b 72 69 70 74 6f 3e dobija blok 21 7e 69 31 60 38 35 3b, odrediti ključ korišćen za šifrovanje.

Zadatak 7

Disk je enkriptovan pomoću AES blok šifre u ECB modu. Odrediti:

Koliko ima fajlova na disku
Koliko ima različitih tipova fajlova
Koje su veličine fajlova

Pretpostaviti da se neiskorišćeni bajtovi na disku pojavljuju kao 0x00 i 0xff. Sadržaj diska je moguće učitati na sledeći način:

from kurs import enkriptovan_disk

Zadatak 8 (u izradi)

Baza podataka sa transakcijama jednog podzemnog marketa je enkriptovana AES šifrom u ECB modu. Shema baze nije enkriptovana i data je sledećim: kupac string(16) | prodavac string(16) | vreme | jos neki podaci

Odrediti koliko postoji velikih prodavaca.
Odrediti da li postoji velika grupa umreženih korisnika (prodavaca ili kupaca).

Zadatak 9

CBC-MAC je implementiran na sledeći način:

from Crypto.Cipher import AES

def mac(key: bytes, message: bytes) -> bytes:
  aes = AES.new(key, AES.MODE_CBC, iv=int.to_bytes(0, 16))
  return aes.encrypt(message)[-16:]

Poznate su poruke CBC-MAC je nebezbedno koristiti sa porukama razlicitih duzina... sa CBC-MAC tagom 05 ae 56 04 bb 4a cb 84 c1 df e1 58 1b 44 30 7c i osim, naravno, ako zelimo da demonstriramo napad sa tagom bc 20 e1 ed 5c 02 74 98 f9 d8 ec bb 71 cb 74 d7. Konstruisati novu poruku sa validnim tagom.

Zadatak 10 (u izradi)

Dat je server koji prihvata poruke u encrypt-and-mac modu. Server prvo proverava padding, a zatim MAC i vraća odgovarajuću grešku ukoliko je do nje došlo.

Neka je data šifrovana poruka todo. Odrediti sadržaj poruke.

Heš funkcije i obavezivanja

Definicija problema

Ana ima neki podatak \(m\) koji želi kasnije da pošalje Bobanu, ali možda ne želi odmah da ga otkrije. Boban želi da dobije garanciju od Ane da, kada mu Ana konačno pošalje neki podatak (možda i pomoću nekog posrednika, Eve), on može nezavisno da se uveri da je zaista dobio podatak \(m\).

Kriptografska heš funkcija je kriptografska primitiva koja nam omogućava da proizvoljnom podatku pridružimo kratak “otisak prsta”. Formalnije, kriptografksa heš funkcija preslikava proizvoljnu poruku \(m\) u niz bitova \(h(m)\) fiksne dužine \(n\) (npr. 256), pri čemu mora da poseduje sledeća svojstva:

Otpornost na inverznu sliku: Za dato \(d\) nije moguće pronaći poruku \(m\) tako da je \(h(m) = d\).
Otpornost na drugu inverznu sliku: Za dato \(m\) nije moguće pronaći poruku \(m’\) različitu od \(m\) tako da je \(h(m) = h(m’)\).
Otpornost na kolizije: Nije moguće pronaći par različitih poruka \(m\) i \(m’\) tako da je \(h(m) = h(m’)\).

U ovom kontekstu, izraz “nije moguće” znači da ne postoji algoritam koji može da izračuna traženi rezultat u nekom razumnom vremenu.

Konstrukcija heš funkcije

Konstrukcije kriptografskih heš funkcija se uglavnom zasnivaju na iterativnoj primeni neke funkcije \(f\). Svojstva funkcije \(f\) se mogu razlikovati u zavisnosti od konstrukcije.

Merkle-Damgard konstrukcija

Merkle-Damgard konstrukcija koristi funkciju \(f\) koja preslikava par blokova veličine \(n\) u blok veličine \(n\). Poruka \(m\) se deli na blokove veličine \(n\) i računa se niz stanja \(s_{i} = f(s_{i-1}, m_{i})\) pri čemu se za \(s_0\) uzima algoritmom definisan inicializacioni vektor. Za vrednost funkcije \(h(m)\) se uzima poslednje stanje \(s_k\). Kako bi funkcija \(h\) ispunjavala željena svojstva, dovoljno je da ih zadovoljava i funkcija \(f\).

def md_hash(message: bytes) -> bytes:
  state = iv
  for block in bytes_to_blocks(message):
    state = f(state, block)
  return state

Primetimo da dužina poruke \(m\) ne mora biti deljiva sa \(n\). U tom slučaju je potrebno dopuniti poruku, npr. dodavanjem niza bitova oblika 100...0.

def pad(message: bytes) -> bytes:
  padded = message + b"\x80"
  pad_len = (-len(padded)) % block_size
  return padded + (b"\x00" * pad_len)

Neke od najpoznatijih heš funkcija, kao što su MD5 i SHA-1, su konstruisane Merkle-Damgard konstrukcijom. Zbog određenih slabosti njihovih funkcija \(f\) koje su otkrivene tokom godina, više se ne smatraju bezbednim. SHA-2 je primer heš funkcije konstruisane Merkle-Damgard konstrukcijom koja se još uvek smatra bezbednom i koja je još uvek u upotrebi.

Sunđer konstrukcija

Sunđer konstrukcija se oslanja na funkciju \(f\) koja je bijekcija i koja ima svojstva pseudoslučajne permutacije. Tokom konstrukcije održava se stanje \(s = [ r, c ]\), gde \(r\) predstavlja deo stanja koji se direktno kombinuje sa ulaznom porukom operacijom xor, dok \(c\) predstavlja unutrašnje stanje heša.

Sunđer konstrukcija

Heš funkcija se dobija tako što se prvo “upija” poruka, odnosno tako što se svaki blok poruke XOR-uje sa trenutnim \(r\). Između svaka dva bloka se stanje \([ r, c ]\) transformiše funkcijom \(f\), odnosno \(s_i = [r_i, c_i] = f([r_{i-1} \oplus m_i, c_{i-1}])\). Nakon upijanja svih blokova, vrednost heš funkcije se “istiskuje”, odnosno čitaju se blokovi iz \(r\) do željene dužine heš vrednosti.

Najpoznatiji primer heš funkcije konstruisane sunđer konstrukcijom je SHA-3, koja se takođe smatra bezbednom i koja je u širokoj upotrebi.

def absorb(state, block):
  absorbed = xor(state[:r], block) + state[r:]
  return f(absorbed)

def squeeze(state):
  return state[:r], f(state)

def sponge(data, output_blocks):
  state = [0] * (r + c)
  for block in bytes_to_blocks(pad(data), r):
    state = absorb(state, block)
  hash = []
  for _ in range(output_blocks):
    output, state = squeeze(state)
    hash.append(output)
  return bytes_from_blocks(hash)

HMAC

Jedan pokušaj da se konstruiše MAC na osnovu heš funkcije \(h\) za poruku \(m\) i ključ \(k\) bi bio da se tag izračuna kao heš konkatenacije ključa i poruke, tj. \(h(k \mid m)\). Ispostavlja se da za heš funkcije konstruisane Merkle-Damgard konstrukcijom ovaj pristup nije bezbedan.

Pretpostavimo da je poruka \(m\) autentifikovana ključem \(k\) i da je tag \(t = h(k \mid m)\). Jednostavnosti radi, pretpostavimo da se \(k \mid m\) može tačno podeliti na blokove. Vrednost \(t\) je zapravo poslednje stanje u Merkle-Damgard konstrukciji, tj. \(t = s_k\). Napadač može izračunati tag za bilo koju poruku \(m’ = m \mid e\) izračunavajući naredne blokove stanja počevši od stanja \(t\) za produžetak \(e\) poruke. Poslednje stanje \(t’\) je validan tag za poruku \(m’\) i ključ \(k\), iako napadač ne zna vrednost ključa.

Jedan način da se reši ovaj problem je korišćenjem HMAC konstrukcije. HMAC se računa kao \(h((k \oplus opad) \mid h((k \oplus ipad) \mid m))\), gde su \(opad\) i \(ipad\) predefinisane konstante. Ova konstrukcija je bezbedna čak i kada se koristi sa heš funkcijama konstruisanim Merkle-Damgard konstrukcijom.

Identifikacija i integritet podataka

Heš funkcije imaju široku primenu u kriptografiji. Jedna od tipičnih primena je identifikacija velikih podataka. Na primer, česta je pojava da se različiti softverski paketi (npr. distribucije Linuxa) mogu preuzeti pomoću BitTorrent protokla. Proizvođači softvera u tom slučaju objavljuju heš vrednost instalacionog fajla, a korisnici fajl mogu preuzeti od bilo kojih učesnika u mreži. U integritet preuzetih podataka moguće je uveriti se izračunavanjem heš vrednost preuzetog fajla i upoređivanjem sa objavljenom hešom. Na ovaj način korisnik ne mora verovati drugim učesnicima u mreži, kao ni konkretnoj implementaciji BitTorrent klijenta, da bi se uverio da je preuzeo željeni fajl u potpunosti.

Još jedna tipična primena heš funkcija je prilikom prijavljivanja na sajt pomoću lozinke. Najjednostavniji način da se omogući prijavljivanje pomoću lozinke je da se u bazi podataka uz nalog čuva i sama lozinka. Ovo naravno nije bezbedno, jer bilo koji napadač koji dobije pristup bazi podataka automatski dobija pristup lozinkama svih korisnika. Bolji pristup je čuvanje heš vrednosti loozinke. Prilikom prijavljivanja, korisnik unosi lozinku, a server računa heš vrednost unete lozinke i omogućava pristup korisniku ukoliko se dobijena vrednost poklapa sa vrednošću iz baze.

Kriptografsko obavezivanje

Kriptografska šema za obavezivanje (eng. commitment scheme) je postupak koji omogućava korisniku da se obaveže na neki podatak, bez da mora taj podatak odmah da otkrije. Sastoji se iz dve faze:

Vezivanje: Korisnik objavljuje vrednost \(c\) koja je na neki način izvedena iz podatka \(m\) na koji se obavezuje, bez otkrivanja podatka \(m\).
Otkrivanje: Korisnik otkriva podatak \(m\) i dokazuje da je \(c\) izveden iz \(m\).

Vrednost \(c\) je potrebno odabrati tako da je sakriva podatak \(m\), odnosno da se na osnovu \(c\) ne može izračunati \(m\) (svojstvo sakrivanja), ali i da nije moguće lažirati vezivanje, odnosno da nije moguće pronaći podatak \(m’\) iz kojeg se takođe izvodi obavezujuća vrednost \(c\) (svojstvo vezivanja).

Heš funkcije se prirodno nameću kao primitiva u izgradnji ovakve šeme. Korisnik može da se obaveže na podatak \(m\) objavljivanjem heš vrednosti \(c = h(m)\).

def commit(message: bytes) -> bytes:
  return h(message)

def verify(commitment: bytes, message: bytes) -> bool:
  return h(message) == commitment

Međutim, ovaj pristup nije u potpunosti bezbedan. Recimo da korisnik želi da se obaveže na podatak \(m\) iz nekog malog skupa, npr. \({1, 2, 3, 4}\). Napadač može lako da izračuna heš vrednosti \(h(1), h(2), h(3), h(4)\) i da proveri sa kojom od ovih vrednosti se poklapa objavljena vrednost \(c\), narušavajući svojstvo skrivanja. Sa druge strane, čak i ako je skup vrednosti dovoljno velik, ako se korisnik više puta obaveže na istu vrednost, napadač će to moći da prepozna bez ikakvog napora. Rešenje prethodno navedenih problema je dodavanje pseudoslučajnog podatka \(r\) prilikom vezivanja. Obavezujuća vrednost se računa kao \(c = h(m \mid r)\).

def commit(message: bytes) -> tuple[bytes, bytes]:
  r = secrets.token_bytes(16)
  c = h(message + r)
  return c, r # Objavljujemo samo c

def verify(commitment: bytes, message: bytes, r: bytes) -> bool:
  return h(message + r) == commitment

Zadaci

Zadatak 1

Odrediti dve različite poruke \(m_1\) i \(m_2\) koje imaju istu vrednost heš funkcije definisane na sledeći način:

import kurs

def h(message: bytes) -> bytes:
  state = kurs.md_iv
  for block in bytes_to_blocks(message):
    state = kurs.md_f(state, block)
  return state

Zadatak 2

Neka je data poruka TODO i njen tag TODO izračunat pomoću HMAC-a definisanog u nastavku. Bez poznavanja ključa, odrediti novu poruku čiji je tag validan za taj ključ.

def mac(key: bytes, message: bytes) -> bytes:
  return md_hash(key + message)

def verify(key: bytes, message: bytes, tag: bytes) -> bool:
  return mac(key, message) == tag

Zadatak 3

Neka je data poruka TODO i njen tag TODO izračunat pomoću HMAC-a iz prethodnog zadatka. Bez poznavanja ključa, odrediti novu poruku čiji je tag validan za taj ključ.

block_size = 16

def mac(key: bytes, message: bytes) -> bytes:
  return md_hash(pad10(key + message, block_size))

def verify(key: bytes, message: bytes, tag: bytes) -> bool:
  return mac(key, message) == tag

Zadatak 4

Definisana je šema za obavezivanje na sledeći način:

Korisnik objavljuje par vrednost \((c, r)\) gde je \(c = h(m \mid r)\), a \(r\) je pseudoslučajna vrednost.
Korisnik otkvira vrednost \(m\) i proverava se da li je \(c = h(m \mid r)\).

Da li je ova šema bezbedna? Ako jeste, obrazložiti. Ako nije, navesti napad i predložiti ispravku.

Zadatak 5

Korisnik se prilikom glasanja obavezuje za svoj glas iz skupa niski DA, NE, SUZDRZAN objavljivanjem vrednosti \(c = h(m)\), gde je \(h\) definisano kao u nastavku. Odrediti glas korisnika pre završetka glasanja ukoliko je objavljena vrednost \(c\) jednaka d539cd97ca1a108f9f5e3f611d7606d84c0aa35ea1973304e479b99025124e16.

import hashlib

def h(message: string) -> bytes:
  return hashlib.sha256(message.encode()).digest()

Zadatak 6

U okviru peer-to-peer mreže potrebno je implementirati mehanizam za održavanje aukcije sa skrivenim ponudama. Svaki učesnik u mreži može da ponudi neki iznos za predmet aukcije, ali ponudu ne otkvira do kraja aukcije. Nakon završetka aukcije, sve ponude se otkrivaju i pobednik je onaj učesnik sa najvećom ponudom. Implementirati funkcije bid i reveal koje omogućavaju ovu funkcionalnost.

TODO!

Zadatak 7

Implementirati igru Papir, kamen, makaze preko peer-to-peer konekcije. Obezbediti da igrači ne mogu da varaju.

TODO!

Zadatak 8

U američkoj emisiji “The Price is Right”, učesnici se takmiče u pogađanju cene proizvoda. Prikazuje se jedan proizvod, a učesnici redom pogađaju cenu. Učesniku nije dozvoljeno da predloži cenu koja je prethodno već predložena, a pobednik je onaj koji je najbliži stvarnoj ceni proizvoda bez da je premaši. Implementirati varijantu ove igre u okviru peer-to-peer mreže.

TODO!

Keyboard shortcuts

Kriptografija