ChaCha20 i Poly1305 autentifikator zajedno predstavljaju AEAD - Authenticated Encryption with Additional Data cipher. Važna stvar kod AEAD-a je to da on podržava dvije različite operacije: seal i open. Drugi slični AEAD koji se upotrebljava za TLS veze je AES-GCM. AES (Advanced Encryption Standard) je postao temeljni standard vezan za enkripciju, a sve zahvaljujući njegovom učinkovitom dizajnu, implementaciji i hardverskoj podršci. Sve navedeno omogućilo je da ovaj kriptografski algoritam za zaštitu digitalnih podataka pruži visoke performanse u mnogim područjima. Osnovna zadaća AES algoritma je nasljeđivanje DES algoritma čije osnovne karakteristike danas više ne zadovoljavaju razvijene kriptografske sustave. Važno je napomenuti kako je AES od četiri do deset puta brži od DES algoritma (prethodnik AES-a) što ga ne čini jedinim najboljim rješenjem, ali ga svrstava u skupinu jedinog praktičnog rješenja. Može se reći kako je AES postao globalni standard za komercijalni i open source softver te za hardver. Koriste ga mnogobrojne institucije i pojedinci u cijelom svijetu.

ChaCha20 je algoritam velike brzine koji je oko tri puta brži od AES algoritma u softverskim implementacijama kojima nedostaje specijalizirani AES hardver. Također, prednost ovog algoritma je da nije osjetljiv na napade kod kojih napadači pokušavaju kompromitirati kripostustav na način da analiziraju vrijeme koje je potrebno za izvršavanje kriptografskog algoritma (Timing attack). Drugi algoritam koji se ovdje spominje je Poly1305 koji predstavlja algoritam velike brzine za autentifikaciju poruke. Ova dva algoritma zajedno tvore autentificiranu enkripciju s pridruženim podacima (ChaCha20 - Poly1305).

ChaCha20 je varijanta 'Salsa20' algoritma objavljena 2008. godine od strane Daniel Julius Bernstein-a, njemačko - američkog matematičara, kriptografa, programera i profesora. Nadalje, Google je odabrao ChaCha20 zajedno s Bernsteinovim kodom za autentifikaciju poruke - Poly1305 kao zamjenu za RC4 u TLS protokolu, koji se koristi za internetsku sigurnost. Google je takav način sigurnosti implementirao za kontrolu prometa između Chrome preglednika na Android mobilnim uređajima i Google web stranica. Također, nedugo nakon toga primjena ovih algoritama iskorištena je za novi kod u OpenSSH paketu sigurnosnih servisa na mreži.

The ChaCha Quarter Round

Osnovna operacija ChaCha algoritma je "Quarter Round". Navedena operacija se izvršava na 32 - bitnim integerima (a, b, c, d).

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

U prethodnom primjeru "^" označava ekskluzivni "ILI" (XOR), a "<<<=n" označava n - bitnu lijevu rotaciju.

Funkcija Quarter round implementirana je u konzolnoj aplikaciji - C#. U nastavku je prikazana glavna funkcija koja služi za izračun quarter round-a. Testni podaci su korišteni iz dokumenta - sekcija 2.1.1. Funkcija prima testni vektor, odnosno ulazni parametri funkcije su četiri integera tipa 'UInt32'. Nakon toga su provedene operacije zbrajanja, operacija ekskluzivni ILI te operacije pomicanja bitova u lijevo. Vidljivo je kako se podaci iz primjera i rezultat implementacije poklapaju što znači da je implementacija uspješno provedena.

ChaCha's Matrix

ChaCha kao i Salsa20 koristi 4 x 4 matricu. Dakle, ChaCha algoritam nema četiri broja (integer) već ima 16 brojeva (integera). No, "quarter round" funkcija radi na samo četiri od njih. U nastavku se nalazi primjer ChaCha matrice u kojoj se "quarter round funkcija poziva na elemente označene s "*", a ostale ne dira - QUARTERROUND(a, b, c, d).

   0 1 *a 3
   4 5 *b 7
   8 9 *c 11
 12 13 *d 15

ChaCha quarter round bolje kodira podatke od prethodnika - Salsa20 quarter round. Razlog je taj što se svaka riječ ažurira dva puta i svaka riječ ima priliku utjecati na još tri. Stoga, to čini ChaCha20 algoritam u praksi malo sigurnijim od Salsa20 algoritma. U nastavku je prikaz primjene Quarter round funkcije na ChaCha matricu. Implementacija je provedena na način da program generira matricu tipa 4x4. Odnosno generira se niz slučajnih brojeva koji se u konačnici pretvaraju u hex zapis i prikazuju na zaslonu. Nakon toga omogućeno je da korisnik unese četiri različite pozicije nad kojima želi izvršiti Quarter round funkciju. Slika u nastavku prikazuje izvršavanje Quarter round funkcije na odabranim pozicijama: '0', '2', '8', '10'.

ChaCha's Block Function

Blok funkcija ChaCha algoritma temelji se na izvršavanju "Quarter round" funkcije više puta. Ulazni parametri blok funkcije su 256-bitni ključ i IV vektor koji se tretiraju kao povezani 32-bitni integeri (misli se na pojedinačnu povezanost parametara). Treći ulazni parametar je 32-bitni brojač blokova. Obzirom na ulazne parametre početna ChaCha matrica (4x4) postavljena je tako da su prva četiri sloga konstante:

 0x61707865
 0x3320646e
 0x79622d32
 0x6b206574

Slijedećih osam slogova uzima se iz 256-bitnog ključa tako da se bajtovi čitaju u "little-endian" poretku. Dvanaesti slog je brojač blokova, a posljednja tri sloga predstavlja IV vektor. IV vektor se ne smije ponavljati za isti ključ. Trinaesti slog je prvih 32-bita ulaznog IV vektora uzete u "little-endian" poretku, a posljednji slog su zadnjih 32 bita IV vektora. U nastavku je prikaz početne ChaCha matrice obzirom na ulazne parametre.

 c - konstanta 
 k - ključ 
 b - brojač blokova 
 n - nonce (IV)

 cccccccc   cccccccc   cccccccc   cccccccc
 kkkkkkkk   kkkkkkkk   kkkkkkkk   kkkkkkkk
 kkkkkkkk   kkkkkkkk   kkkkkkkk   kkkkkkkk
 bbbbbbbb   nnnnnnnn   nnnnnnnn   nnnnnnnn

ChaCha blok funkcija izvršava Quarter - round dvadesetak puta. Deset ponavljanja izvršava na stupcima matrice, a preostalih deset odnosi se na dijagonale vrijednosti. Na kraju zadnje operacije dobivena matrica se zbraja s početnom matricom nad kojom je izvršen blok Quarter round operacija te se njihov rezultat sekvencijalno serijalizira u "little-endian" redoslijedu. U nastavku se nalazi pseudokod ChaCha20 block funkcije.

  quarter_funkcija(matrica):
     QUARTERROUND(matrica, 0, 4, 8, 12)
     QUARTERROUND(matrica, 1, 5, 9, 13)
     QUARTERROUND(matrica, 2, 6, 10, 14)
     QUARTERROUND(matrica, 3, 7, 11, 15)
     QUARTERROUND(matrica, 0, 5, 10, 15)
     QUARTERROUND(matrica, 1, 6, 11, 12)
     QUARTERROUND(matrica, 2, 7, 8, 13)
     QUARTERROUND(matrica, 3, 4, 9, 14)
  end

  ChaCha20_blok_funkcija(k, c, n):
     početna_matrica = konstante | ključ | blok_brojač | nonce(iv)
     radna_matrica = početna_matrica
     for i=1 do 10
        quarter_funkcija(radna_matrica)
        end
     početna_matrica += radna_matrica
     return serlialize(početna_matrica)
     end

ChaCha20 Encryption Algorithm

ChaCha20 poziva prethodno objašnjenu ChaCha20 blok funkciju koja ima isti ključ i nounce parametar, a uz navedeno uzastopno povećava parametar - brojač blokova. Nakon toga ChaCha20 provodi serijalizaciju početnih parametara tako da brojeve zapiše u "little-endian" redoslijedu što rezultira kreiranjem keystream bloka. Spajanjem uzastopnih blokova formira se keystream kojeg ChaCHa20 funkcija XOR-a zajedno s čistim tekstom. Ulazni parametri ChaCha20 su: 256 - bitni ključ, 32 - bitni brojač (obično je 0 ili 1), 96 - bitni nounce (inicijalizacijski vektor) i tekst proizvoljne duljine.

S druge strane, izlaz predstavlja kriptirana poruka ili "ciphertext" iste duljine. 'Dekriptiranje je slično kao i kriptiranje. ChaCha20 blok funkcija se koristi kako bi iz ključa dobila keystream blok koji je XOR-an sa kriptiranom porukom te se na kraju vraća prvobitna nešifrirana poruka.

U nastavku je prikazan jedan primjer rezultata ChaCha20 kriptiranja.

Prva matrica prikazuje početno stanje nakon što su dodane konstante, ključ, brojač i IV.

      61707865  3320646e  79622d32  6b206574
      03020100  07060504  0b0a0908  0f0e0d0c
      13121110  17161514  1b1a1918  1f1e1d1c
      00000001  00000000  4a000000  00000000

Nakon toga generiraju se nove matrice obzirom da se ChaCha20 funkcija u pseudokodu algoritma poziva dva puta. Nakon što se funkcija pozove drugi put matrica izgleda ovako:

      9f74a669  410f633f  28feca22  7ec44dec
      6d34d426  738cb970  3ac5e9f3  45590cc4
      da6e8b39  892c831a  cdea67c1  2b7e1d90
      037463f3  a11a2073  e8bcfb88  edc49139

Upravo ta matrica predstavlja finalni blok nakon kojeg se generira keystream. Krajnji rezultat je obavljanje XOR operacije keystream-a sa željenim tekstom. Šifrirana poruka prikazana je u nastavku.

 000  6e 2e 35 9a 25 68 f9 80 41 ba 07 28 dd 0d 69 81  n.5.%h..A..(..i.
 016  e9 7e 7a ec 1d 43 60 c2 0a 27 af cc fd 9f ae 0b  .~z..C`..'......
 032  f9 1b 65 c5 52 47 33 ab 8f 59 3d ab cd 62 b3 57  ..e.RG3..Y=..b.W
 048  16 39 d6 24 e6 51 52 ab 8f 53 0c 35 9f 08 61 d8  .9.$.QR..S.5..a.
 064  07 ca 0d bf 50 0d 6a 61 56 a3 8e 08 8a 22 b6 5e  ....P.jaV....".^
 080  52 bc 51 4d 16 cc f8 06 81 8c e9 1a b7 79 37 36  R.QM.........y76
 096  5a f9 0b bf 74 a3 5b e6 b4 0b 8e ed f2 78 5e 42  Z...t.[......x^B
 112  87 4d                                            .M

Poly1305

Poly1305 slovi brzim, sigurnim i jednostavnim autentifikatorom. Autor ovog algoritma je Daniel J. Bernstein koji je identificirao nekoliko bitnih značajka ovog algoritma:

  Garantira sigurnost ako je AES siguran
  Zamijenjivost šifre
  Izuzetno velika brzina
  Paralelizabilnost i inkrementalnost
  Nema zahtjeva za intelektualno vlasništvo

Ovaj autentifikator generira MAC (Message Authentication Code) koristeći pri tome poruku i jednokratni ključ. Ključ je podijeljen u dva dijela: "r" i "s". Par (r,s) mora biti jedinstveno i mora biti nepredvidiv za svaki poziv, dok "r" može biti konstanta, ali se prije uporabe mora mijenjati kako je prikazano u nastavku. Zahtijeva se da r[3], r[7], r[11], i r[15] imaju svoja gornja četiri bita manja od 16, dok r[4], r[8], i r[12] trebaju imati donja dva bita djeljiva s 4.

Dio ključa "s" treba biti nepredvidiv, ali je poželjno i prihvatljivo da se svaki put oba dijela "r" i "s" generiraju kao jedinstveni. Spomenuto je kako su ulazni parametri Poly1305 algoritma 256 - bitni ključ i poruka proizvoljne duljine. Obzirom na ulazne parametre izlaz je 128 - bitna oznaka.

Prvi korak kod Poly1305 algoritma je postavljanje dio vrijednosti ključa - "r". Nakon toga je potrebno postaviti konstantu "P" koja treba biti oblika 2^n-q pri čemu je q jako mali broj (manji od 10). Jedan od najboljih kandidata je 2¹³⁰ - 5: 3fffffffffffffffffffffffffffffffb. Ovaj broj odabran je jer je 5 mali broj koji omogućuje varanje modularne redukcije, a drugi razlog je što je 2¹³⁰ - 5 malo veći od 2^128, što dopušta jako lijepo kodiranje poruke. Također, varijablu "accumulator" je potrebno postaviti na 0. Slijedeći korak je podijeliti poruku u 16-bitne blokove, postoji mogućnost da je posljednji blok kraći od prethodnih. Posljednji korak je dodavanje tajnog dijela ključa "s" u varijablu "accumulator" i najmanjih 128 bitova je serijalizirano u "little-endian" redoslijedu kako bi se formirala oznaka.

ChaCha20 - Poly1305

Kod Poly1305 autentifikatora je prihvatljivo da se jednokratni ključ generira slučajno. Kombiniranje ChaCha20 i Poly1305 omogućava da se putem ChaCha20 funkcije generira par ključeva (r,s). Potrebno je pozvati blok funkciju sa slijedećim parametrima:

  Kao 256 - bitni ključ za integraciju sesije se koristi ChaCha20 ključ

  Brojač blokova je postavljen na 0

  Protokol specificira 96 - bitni ili 64 - bitni inicijalizacijski vektor (IV) koji mora biti jedinstven kod pozivanja vezanog za isti ključ. 
  Dobre metode koje se preporučaju za generiranje ovog vektora su brojač ili LFSR (Linear Feedback Shift Register) metoda.

Nakon izvršavanja blok funkcije rezultat je 512 - bitno stanje. Prvih 256 bitova ili serializacija stanja se koristi kao jednokratni Poly1305 ključ (prvih 128 bitova koristi se za "r", a ostalih 128 se koristi za "s"). Preostalih 256 bitova se odbacuje. Primjer se nalazi u nastavku.

Ključ:

 000  80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f  
 016  90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f 

IV vektor (nonce):

 000  00 00 00 00 00 01 02 03 04 05 06 07              

Početna ChaCha matrica nakon postavljanja ključa, IV i brojača:

        61707865  3320646e  79622d32  6b206574
        83828180  87868584  8b8a8988  8f8e8d8c
        93929190  97969594  9b9a9998  9f9e9d9c
        00000000  00000000  03020100  07060504

ChaCha matrica nakon izvršavanja ChaCha blok funkcije:

        8ba0d58a  cc815f90  27405081  7194b24a
        37b633a8  a50dfde3  e2b8db08  46a6d1fd
        7da03782  9183a233  148ad271  b46773d1
        3cc1875a  8607def1  ca5c3086  7085eb87

Izlaz:

 8a d5 a0 8b 90 5f 81 cc 81 50 40 27 4a b2 94 71
 a8 33 b6 37 e3 fd 0d a5 08 db b8 e2 fd d1 a6 46  

Ovaj izlaz je ujedno i 32-bitni jednokratni ključ korišten za Poly1305.

Konstrukcija AEAD-a

AEAD je autentificirana enkripcija s pridruženim podacima. Ulazni parametri ovog algoritma su:

  256 - bitni ključ
  96 - bitni inicijalizacijski vektor (IV)
  Poruka / tekst proizvoljne duljine
  Pridruženi podaci proizvoljne duljine (AAD)

Zanimljivo je kako neki protokoli nemaju IV duljine 96 - bitova. Jedan od takvih primjera je protokol IPsec (protokol za uspostavu sigurne komunikacije između računalnih sustava). Spomenuti protokol ima 64 - bitni IV. U takvim slučajevima se zahtijeva da taj protokol u svojoj dokumentaciji ima definirano kako će pretvoriti IV u 96 - bitni vektor. Jedna od mogućnosti je dodavanje konstantne vrijednosti.

Gledajući ChaCha20 i Poly1305 oni su ukomponirani u AEAD koji koristi 256 - bitni ključ i 96 - bitni IV vektor. Na samom početku, generiran je jednokratni 256 - bitni Poly1305 ključ i IV vektor korištenjem ChaCha20 algoritma. Nakon toga poziva se ChaCha20 funkcija koja kriptira poruku koristeći isti ključ i IV vektor koji je prethodno generiran. Uz to, vrijednost brojača postavlja se na 1.

Konačno, Poly1305 funkcija se poziva sa Poly1305 ključem i konstruiranom porukom koja sadrži:

  Pridružene podatke
  Padding1 - do 15 (zero) bajtova i donosi ukupnu dužinu sve do integralnog višekratnika 16
  Šifrirani tekst
  Padding2 - do 15 (zero) bajtova i donosi ukupnu dužinu sve do integralnog višekratnika 16
  Dužinu pridruženih podataka u oktetima (kao 64-bitni integeri u "little-endian" poretku)
  Dužinu šifriranog teksta u oktetima (kao 64-bitni integeri u "little-endian" poretku)

Izlaz AEAD-a:

  Šifrirani tekst iste duljine kao i početna poruka
  128 - bitna oznaka koja predstavlja izlaz Poly1305 funkcije

Dekpriptiranje je slično kao i kriptiranje samo što sadrži neke razlike.

  Prva je što je uloga šifriranog teksta i početne poruke obrnuta. Primjenjuje se ChaCha20 funkcija šifriranja na šifrirani tekst kako 
  bi se došlo do početne poruke. 
  
  Poly1305 funkcija se još primjenjuje na pridruženim podacima i šifriranom tekstu, ali se ne primjenjuje na početnoj poruci.
  
  Izračunata oznaka se uspoređuje s primljenom oznakom. Poruka je prikazana jedino ukoliko se te dvije oznake podudaraju. 
  U suprotnom se rezultat smatra nepouzdanim i nesigurnim.

Literatura

1. CloudFlare. (2016). It takes two to ChaCha (Poly) Dostupno 3.2.2018. godine na linku https://blog.cloudflare.com/it-takes-two-to-chacha-poly/
2. Cr.yp.to. (2008). The ChaCha family of stream ciphers. Dostupno 2.2.2018. godine na linku https://cr.yp.to/chacha.html
3. Cr.yp.to. (2008). The Poly1305-AES message-authentication code. Dostupno 5.2.2018. godine na linku http://cr.yp.to/mac/poly1305-20050329.pdf
4. Daniel J. Bernstein. (2008). ChaCha, a variant of Salsa20 Dostupno 2.2.2018. godine na linku https://cr.yp.to/chacha/chacha-20080128.pdf
5. Internet Research Task Force. (2015). ChaCha20 and Poly1305 for IETF Protocols. Dostupno 30.1.2018. godine na linku https://tools.ietf.org/html/rfc7539
6. Internet Engineering Task Force. (2015). ChaCha20, Poly1305, and Their Use in the Internet Key Exchange Protocol (IKE) and IPsec. Dostupno 30.1.2018. godine na linku https://tools.ietf.org/html/rfc7634
7. Loup. (2017). The Design of ChaCha20. Dostupno 1.2.2018. godine na linku http://loup-vaillant.fr/tutorials/chacha20-design