Differences

This shows you the differences between two versions of the page.

--- public:thesis:kubicek2017 [2017-05-22 08:59] – [Optimisation heuristics in randomness testing] xkubice8
+++ public:thesis:kubicek2017 [2017-06-21 15:48] (current) – [Optimisation heuristics in randomness testing] xkubice8
@@ Line 1: / Line 1: @@
 ====== Optimisation heuristics in randomness testing ======
-**Karel Kubíček, master thesis, spring 2017**
+**Karel Kubíček [[karel.kubicek@mail.muni.cz]], master thesis, spring 2017**
 **Keywords:** //randomness testing, cryptanalysis, block functions, stream functions, hash functions, problem optimization, metaheuristics//
@@ Line 12: / Line 12: @@
 //This thesis has three main contributions. The first is a development of a testbed of 16 well-known cryptographic functions used for randomness testing comparison. The second is an extension of EACirc by three new metaheuristics. One of them, called guided local search, outperforms all the others in terms of its success rate. The third contribution is an analysis of randomness tests produced by EACirc computation. Successful tests contain evidence of the bias in the tested data. The influence of tested metaheuristics on the complexity of these tests is analysed. It is shown that the guided local search produces the least complex tests, such that allow easier cryptanalysis.//
-  * Download thesis {{ :public:thesis:thesis-pc.pdf |pdf}}, presentation will be added after thesis defence
+  * Download thesis {{ :public:thesis:thesis-pc.pdf |pdf}}, presentation {{ :public:thesis:pres.pdf |pdf}}
   * Download [[https://drive.google.com/drive/folders/0B5Z1zst5NzwXQmFKaXgxREJWNk0?usp=sharing|dataset]]
   * List of tools:
@@ Line 22: / Line 22: @@
 ===== Bibtex =====
+<code>
+@thesis{kubicekMasterThesis,
+    author = {Karel Kubíček},
+    supervisor = {Petr Švenda},
+    title = {{Optimisation heuristics in randomness testing}},
+    type = {Master thesis},
+    institution = {Faculty of Informatics Masaryk University},
+    year = {2017},
+    url = {http://is.muni.cz/th/408351/fi_m/},
+}
+</code>
 ===== Results =====
+We analysed application of three single-solution metaheuristics in randomness testing tool EACirc. They all performed similarly, over the testbed of 16 functions, only five of them showed some differences. The differences are showed in following figure. The numbers are rejection rate of EACirc - how often the metaheuristic produces a randomness test capable of distinguishing selected data.
+{{:public:thesis:comparison.png?800|}}
+More important is the impact of the metaheuristics on cryptanalysis. The produced distinguisher is in form of simulated electronic circuit. This circuit can be analysed to find the source of non-randomness of the tested data. Formerly, the circuits were dense, hard to analyse. Guided local search metaheuristic forces the circuits to be sparser.
+{{:public:thesis:circuit.dot.png?400|}} {{:public:thesis:circuit.gls.png?400|}}
+//The left circuit was produced by former metaheuristic in EACirc (iterated local search), the right was produced by guided local search.//
+We can automatically remove unnecessary connectors from the circuits by pruning. This leads to the following circuits:
+{{:public:thesis:pruned.ils.png?400|}} {{:public:thesis:pruned.gls.png?400|}}
+//The left circuit is pruned circuit produced by former metaheuristic in EACirc (iterated local search), the right was produced by guided local search.//
+The pruned circuit from guided local search is much easier to analyse, which reduce the needed time for manual cryptanalysis of the cryptoprimitives.