Paralllella board - primjena za kriptoanalizu
Uzeli: Goran Grgić i Goran Drmenčić. 11.10.2014., 11:38h
Sadržaj |
O Parallelli
Parallella platforma je "open-source", energetski učinkovita i visokih performansi. Temelji se na Epiphany višejezgrenim čipovima koje je razvila tvrtka Adapteva. Ova jednostavna platforma dizajnirana je za razvoj i provedbu visokih performansi, paralelnih procesnih aplikacija razvijenih da iskoriste puni potencijal on-board Epiphany čipa. Epiphany 16 ili 64 jezgreni čipovi sastoje se od skalabilnog polja jednostavnih RISC (engl. "Reduced Instruction Set Computer") procesora programabilnih u C/C++ jeziku, povezanih zajedno s brzim čipom u mrežu unutar zajedničke memorijske arhitekture. Veličine je kreditne kartice. [1]
Karakteristike pločice
1. Zynq-7000 Series Dual-core ARM A9 CPU (Z-7010 or Z-7020), 2. 16 ili 64-jezgreni Epiphany Multicore Accelerator, 3. 1 GB RAM-a, 4. MicroSD kartica, 5. 2x USB 2.0, 6. 4 priključka za proširenje, 7. 10/100/1000 Ethernet priključak, 8. HDMI port, 9. Sadrži Ubuntu OS, 10. Dimenzije oko 3.4" x 2.15" (8.6 x 5.5 cm).
[2] -- Goran Drmencic 10:55, 06.12.2014. (SUB)
Projekt Parallella
Projekt Parallella Board je nadahnut na temelju hardwera kao što su Raspberry Pi, BeagleBoard i Arduino. Glavni ciljevi projekta su da se svima omogući paralelno računalstvo pomoću open source alata, i razvijanje softvera koji može spregnuti snagu paralelnih sustava. Kako bi paralelno računalstvo postalo sveprisutno, developeri moraju imati pristup platformi koja je jeftina, open source i jednostavna za korištenje. Upravo na tim idejama počiva cijeli Parallella projekt. Platforma Parallella je dizajnirana na sljedećim principima:
- Open Access - sva arhitektura i SDK dokumentacija je publicirana na Internetu (nije potreban NDA ili neki specijalni pristup)
- Open Source - softverska platforma je bazirana na besplatnim i open source razvojnim alatima i bibliotekama
- Priuštivost - cijena hardwera i SDK je uvijek predstavljala problem za developere, no pošto je cijena Parallelle manja od $100, Parallella je svima priuštiva
Što se tiče primjene Parallelle, može se koristiti gotovo u svim područjima: u informatici aplikacija za prepoznavanje glasa ili lica, u medicini za ultrazvuk i CT, u industriji za autonomnu navigaciju robota, u vojsci za radare, dronove itd.
[3] --Ggrgic 17:02, 25. siječnja 2015. (CET)
Kriptografija i kriptoanaliza
Kriptografija je znanstvena disciplina koja se bavi proučavanjem metoda za slanje poruka koje su u takvom obliku da ih može pročitati samo onaj kome je poruka namijenjena. Riječ kriptografija je grčkog podrijetla te se doslovce prevodi kao "tajnopis". Glavni cilj kriptografije je omogućavanje dvjema osobama da komuniciraju putem nesigurnog komunikacijskog kanala tako da neka treća osoba ne može razumjeti njihove poruke. Poruka koju šalje pošiljatelj naziva se otvoreni tekst. Pošiljatelj otvoreni tekst preoblikuje putem unaprijed dogovorenog ključa te se ta procedura naziva šifriranje, a rezultat šifriranja zovemo šifrat. Zatim pošiljatelj može poslati šifrat primatelju koji pomoću unaprijed definirianog tajnog ključa može dešifrirati poruku. Ukoliko netko prisluškuje komunikacijski kanal, on može saznati sadržaj šifrata, ali pošto nema tajni ključ, ne može odrediti otvoreni tekst (osim ako razbije ključ). [4]
Kriptoanaliza je znanstvena disciplina koja određuje otvoreni tekst na temelju šifrata, ali bez ključa. Upotrebom kriptoanalize moguće je pronaći slabosti u kriptosustavu i pritom otkriti ključ. Glavna pretpostavka kriptoanalize koju je objavio Kerckhoff govori da tajnost mora biti zasnovana na ključu. Također, Kerckhoff pretpostavlja da kriptoanalitičar zna sve pojedinosti kriptografskog algoritma i njegove primjene. Možemo razlikovati četiri osnovna tipa kriptoanalitičkih napada:
- Napad "samo šifrat" - je vrsta napada kod kojeg kriptoanalitičar ima šifrate od nekoliko poruka koje su šifrirane istim algoritmom za šifriranje. Zadatak kriptoanalitičara je da rekonstruira otvoreni tekst od što više poruka ili da otkrije ključ za šifriranje.
- Napad "poznati otvoreni tekst" - kod kojeg kriptoanalitičar ima šifrate za neke poruke kao i otvorene tekstove za te poruke. Njegov zadatak je izračunati ključ ili algoritam za dešifriranje poruka šifriranih tim ključem.
- Napad "odabrani otvoreni tekst" - napad kod kojeg kriptoanalitičar ima šifrate za za neke poruke, otvoreni tekst, ali i mogućnost biranja otvorenog teksta koji će biti šifriran. Njegov zadatak je izračunati ključ ili algoritam za dešifriranje poruka šifriranih tim ključem. Ovaj napad je moćniji od prethodnog.
- Napad "odabrani šifrat - kriptoanalitičar ima šifrat za dešifriranje i pristup dešifriranom otvorenom tekstu. Ova vrsta napada se primjenuje na algoritme s javnim ključem te je zadatak takvog napada otkriti tajni ključ. [5]
--Ggrgic 16:08, 26. siječnja 2015. (CET)
Ukratko o S-DES algoritmu
S-DES (engl. Simplified DES) razvijen je od strane profesora Edwarda Schaefera na Santa Clara University-u. To je algoritam više primjeren edukacijskoj svrsi negoli zaštiti podataka svojim kriptiranjem. Ima sličnu strukturu i opcije kao DES sa manjim brojem parametara. Upravo zbog jednostavnosti smo uzeli S-DES algoritam i na njemu sproveli kriptoanalizu pomoću Parallelle. S-DES enkripcija uzima 8 bitni blok čistog teksta (npr. 10111101) i 10 bitni ključ kao ulaze i daje 8 bitni blok kriptiranog teksta kao izlaz. S-DES dekripcija opet, uzima 8 bitni block šifriranog teksta i pomoću istog 10 bitnog ključa korištenog za izradu šifriranog teksta na ulazu dobiva na izlazu čisti tekst, naravno 8 bitni. Enkripcijski algoritam uključuje pet funkcija: inicijalna permutacija IP, kompleksna funkcija f(k) koja uključuje i permutaciju i zamjenu mjesta te ovisi o ulaznom ključu, jednostavna permutacija koja zamjenjuje dvije polovice teksta, ponovno funkcija f(k) te nakraju permutacijske funkcije koja inverza inicijalnu permutaciju 1/IP. [6]
--Goran Drmencic 21:14, 26. siječnja 2015. (PON)
Diferencijalna kriptoanaliza S-DES-a
Diferencijalna kriptoanaliza je napad „odabranog otvorenog teksta“ koji je ispočetka bio razvijen za napade na algoritme nalik na DES. Napad „odabranog otvorenog teksta“ je onaj u kojemu napadač ima mogućnost unosa šifri i mogućnost ispitivanja izlaza. Budući da je jedan od prvih napada na DES, diferencijalna kriptoanaliza je opsežno proučavana. Mnogi od današnjih kriptoalata su dizajnirani sa otpornošću na diferencijalnu kriptoanalizu. Ipak, diferencijalna kriptoanaliza još uvijek pruža dobar uvid u moguće slabosti kriptiranja i tehnike kako ih razbiti.
Osnovna ideja diferencijalne kriptoanalize je u usporedbi XOR-a dvaju otvorenih tekstova sa XOR-om dvaju odgovarajućih šifrata. Najčešća razlika korištenja je fiksna XOR vrijednost šifrata. Istraživanjem tih razlika, nepotpun međuključ korišten u algoritmu se može pogoditi. Taj međuključ se pogađa statički koristeći postupak brojanja za svaki ključ u kojem ključ s najvišim zbrojem se uzima kao vjerojatni nepotpuni ključ.
Osnovni koncept
Uzmimo u obzir slijedeću osnovnu linearnu funkciju šifrata:
C = P ⊕ K
Uzimajući u obzir razliku parova šifranata, otkazali bi uključenost ključa, ostavljajući nas bez podataka o ključu:
C ⊕ C’ = P ⊕ K ⊕ P’ ⊕ K
C ⊕ C’ = P ⊕ P’
To je zbog linearnosti funkcije. Gornja jednadžba govori nam da razlika između čistih tekstova je ista kao i razlika između šifriranih tekstova. S-DES nije linearni šifrat. Zbog toga razlika između šifriranih tekstova nije ista kao razlika između čistih tekstova. U S-DES-u, razlika u šifriranom i čistom paru utjecana je sa ključem. Za S-kutije S0 i S1, označavat ćemo ulaz u S-kutiju sa X, a izlaz sa Y. Tada je razlika između parova S-kutija ΔX i ΔY, gdje je ΔX = X’ ⊕ X’’. Zgodnije je ako uzmemo u obzir svih 16 vrijednosti X’ sa ΔX kao ograničenjem na vrijednosti X’’, čime X’’ = X’ ⊕ ΔX. Preko X’’ i X’, vrijednosti od ΔY mogu se dobiti.
Diferencijalne karakteristike
Tablice razlike distribucije za S0 i S1 služe za:
1. Dobivanje mogućih ulaznih i izlaznih vrijednosti s obzirom na njihove razlike.
2. Dobivanje ključnih bitova uključenih u S-kutije koristeći poznate ulazne parove i izlazne razlike u S-kutijama.
Diferencijalna karakteristika za rundu 1 za S-DES. Sa ovom karakteristikom može se dobiti međuključ K2. Prvo kreiramo diferencijalnu karakteristiku koja uključuje S1 u obje runde S-DES-a koristeći slijedeći diferencijalni par od S0 i S1:
S0: ΔX0 = 2 -> ΔY0 = 2 sa vjerojatnošću 12/16
S1: ΔX1 = 4 -> ΔY1 = 2 sa vjerojatnošću 10/16
Uzimajući ΔX0, ΔX1 i ekspanzije E koju smo modificirali u npr. E = [0 2 1 3 0 1 2 3]; ulazna razlika u prvoj rundi je ΔU1 = [0 0 0 0 0 1 0 0]. Razlika je stvaranje derivacije ulaznih razlika jasnijom, ekspanzija ovdje nije glavna briga. Tada, uzimajući ΔY0 i ΔY1 i permutaciju P koja slijedi, dobivamo izlaznu razliku za rundu 1: ΔV1 = [ 0 1 0 0 0 1 0 1]. Prva runda posjeduje vjerojatnost od 12/16 x 10/16 = 15/32, što znači da za svaki 32- nasumični i ravnomjerno raspoređeni par odabranih čistih tekstova s razlikom ΔU1 očekivamo da pronađemo oko 1 par odgovarajućeg šifriranog teksta koji zadovoljava razliku ΔV1. Parove koji sa čistim tekstom stvaraju ΔU1 i odgovarajući šifrirani tekst koji proizvodi ΔV1 zovemo pravi parovi. Za N-runda šifrate moramo pronaći N-1 diferencijalne karakteristike da bi izvršili napad. Pošto je ovaj S-DES 2-rundni šifrat, jedna karakteristika je dovoljna. [7]
Izvođenje parcijalnog međuključa
Sa diferencijalnim karakteristikama možemo nastaviti izvoditi međuključeve K2 runde 2. Nazovimo toga međuključa našim ciljnim međuključem. Proces izvođenja međuključa opisan je u slijedećem algoritmu:
1. Dobi nasumičan čisti tekst P’ i izračunaj P’’ = P’⊕ ΔX.
2. Za P’ i P’’:
2.a. Kriptiraj oba P’ i P’’ sa oba K1 i K2 da dobiš C’ i C’’. Također, dobi CI’ i CI’’, kriptirani tekst nakon prve runde, koji je kriptiran samo ključem K1.
2.b. Ako je CI’ ⊕ CI’’ = ΔY, tada
2.b.i. Za sve moguće vrijednosti međuključeva, kriptiraj C’ ⊕ C’’ sa samo jednom rundom, koja je runda 2.
2.b.ii. Ako je rezultat enkripcije od 2.b.i. ekvivalentan sa rezultatom predloženim u C’ i C’’, tada povećaj zbroj za odgovarajuću vrijednost korištenog međuključa.
3. Ponavljaj 1. i 2. za drugi nasumični tekst P’. Ponavljaj dok god jedna od vrijednosti međuključa nije zbrojena mnogo više puta od drugih. Ovaj međuključ se tada smatra kao točan međuključ korišten u drugoj rundi. [7]
Kriptoanaliza uspjeva. Dobiveni rezultati su točni, napad 100% pogodi međuključ. Cijeli proces je automatiziran, od generiranja S-kutija tablica pa do brojanja. Eksperiment koristi 95 enkripcija.
Parametri:
Ako se kod pokretanja programa unese slovo 'y' (odabere se defaultni ulaz), dobijemo slijedeće parametre:
Runda 1 Ulazna diferencijalna karakteristika ∆U1=4
Runda 1 Izlazna diferencijalna karakteristika ∆V1=69
Modificirana ekspanzija E = [ 0 2 1 3 0 1 2 3]
Notacija: C - šifrirani tekst, P - čisti tekst, E - funkcija kriptiranja, D - funkcija dekriptiranja, K - ključ, (X',X) - ulazni parovi, ∆U - Ulazna razlika, ∆V - Izlazna razlika.
Zaključak
Kriptoanaliza je pronašla 8 bitova međuključa u zadnjoj rundi. Ti bitovi međuključa su zapravo 8 bita S-DESovog 10 bitnog ključa, 2 bita još nedostaju. Zbog toga možemo pokušati 2^2 mogućnosti za pogoditi ta dva bita. To nebi trebao biti problem.
[Diferencijalna kriptoanaliza SDES-a Source code] - kod preuzet s https://eprint.iacr.org/2002/045.pdf i modificiran tako da radi na Parallelli.
Slike diferencijalne kriptoanalize na Parallella-i
--Goran Drmencic 12:41, 27. siječnja 2015. (UTO)
Brute Force kriptoanaliza
Brute Force kriptoanaliza je najdirektnija vrsta napada. Iako je to jedna od najprimitvnijih metoda napada, dobiva veću primjenjivost povećanjem snage računala. Pošto je to jednostavan napad može se primjenjivati na kriptosustave s maksimalnom veličinom ključa do 56 bita. Za kriptosustave s ključom većim od 56 bita je potrebno duže vrijeme za krekiranje ili čak nije niti moguće. Npr. AES s 128-bitnim ključem je nemoguće razbiti s današnjom snagom računala. (Broj kombinacija za pokušaj razbijanja je veći od broja zrnca pijeska na Zemlji.) [7]
Automated Brute Force Attack of S - DES Source Code - kod preuzet s https://eprint.iacr.org/2002/045.pdf
--Ggrgic 21:54, 26. siječnja 2015. (CET)
Priprema Parallelle za rad
Kako bismo mogli početi raditi s Parallelom potrebno je napraviti sljedeće:
1. Osigurati potreban pribor: - 2000mA rated 5V DC power supply with 5.5mm OD / 2.1mm ID center positive polarity plug - micro HDMI na HDMI kabel - muški Micro-B na ženski Standard-A kabel - ethernet kabel - ventilator za hlađenje
2. Napraviti bootabilnu micro-SD karticu: - skinuti Ubuntu 14.04 for Parallella - ubaciti micro-SD karticu u PC - unzipati Ubuntu image - nasnimiti Ubuntu image na micro-SD karticu - kopirati Parallella Linux kernel i FPGA fileove - preimenovati FPGA “.bin” file kao “parallella.bit.bin
3. Spojiti periferiju i adapter za struju kao što je prikazano na sljedećoj slici:
4. Logirati se s korisničkim imenom: linaro i lozinkom: linaro
[8] --Ggrgic 20:08, 18. siječnja 2015. (CET)
mcrypt program
Pošto se na Parallelli vrti Linux, možemo za jednostavniji pristup kriptiranju koristiti manje programske alate za kriptiranje odnosno dekriptiranje. Jedan od takvih programa je mcrypt odnosno mdecrypt. Kao što i imena govore, služe za kriptiranje odnosno dekriptiranje datoteka.
Sintaksa upita/mogućih naredbi: mcrypt [ -dLFubhvrzp ] [-a algorithm] [-c config_file] [-m mode] [-s keysize] [-o keymode] [-k key1 key2 ...] [-f keyfile] [ filename ... ]
mdecrypt [ -LFusbhvzp ] [-a algorithm] [-c config_file] [-m mode] [-s keysize] [-o keymode] [-k key1 key2 ...] [-f keyfile] [ filename ... ]
mcrypt je zamjena za stariji crypt program. Kada se kriptira, kreira se nova datoteka sa ekstenzijom .nc i modom 0600. Novokreirana datoteka čuva vrijeme modifikacije originala. mcrypt koristi simetrične algoritme koji su sakupljeni u libmcrypt-u. mcrypt također pruža uslugu kompresije, tipa gzop i bzip2. Svi podržani blok algoritmi mogu koristiti ove modove enkripcije: ECB (The Electronic CodeBook mode), CBC (The Cipher Block Chaining mode), CFB (The Cipher-Feedback Mode, 8 bitni), OFB (The Output-Feedback Mode, 8 bitni), nOFB (The Output-Feedback Mode, n-bitni). Kriptirane datoteke mogu se povratiti na original koristeći naredbu mcrypt -d ili mdecrypt. [9]
PRIMJERI:
Da mcrypt bude kompatibilan sa solaris des algoritmom, koristimo slijedeće parametre: "mcrypt -a des --keymode pkdes --bare --noiv filename".
Da mcrypt bude kompatibilan sa unix crypt algoritmom, koristimo slijedeće parametre: "mcrypt -a enigma --keymode scrypt --bare filename".
PRIMJERI KORIŠTENJA:
Kriptirajući male datoteke, vrijeme izvršavanja je isto ko da je rađeno na običnom računalu. Povećanjem veličine datoteke, povećava se i razlika u vremenu izvršavanja Parallella pločice i računala. Za više informacija o mcrypt-u posjetite slijedeći link.
-- Goran Drmencic 21:25, 18.01.2015. (NED)
Literatura
[1] http://www.parallella.org/board/ [2] https://www.parallella.org/board/ [3] https://www.kickstarter.com/projects/adapteva/parallella-a-supercomputer-for-everyone [4] Dujella A., Maretić M.: Kriptografija (2007), Element, Zagreb [5] Schneier B.: Primjenjena kriptografija (2007), Mikroknjiga, Beograd [6] http://www2.kinneret.ac.il/mjmay/ise334/sdes.pdf [7] https://eprint.iacr.org/2002/045.pdf [8] https://www.parallella.org/get-started/ [9] http://linux.die.net/man/1/mcrypt
