Finished Master Projects

From CryptoLUX
Revision as of 10:01, 16 September 2015 by Alex.biryukov (talk | contribs)
Jump to: navigation, search
  • Bromine - Proof Of Space On Disk

Proofs of work are puzzles which take a random, but statistically distributed amount of computer processor time to solve. However, the answers to these puzzles are not of interest; , what is desired is their side effect of increasing the cost of an operation. They are used in some email systems, and the Bitcoin mining implementation, but are taking more and more electrical energy. Algorithms in a class called memory-hard have been proposed as less resource intensive replacements for proofs of work. Their nature and development is recounted here in detail. Some memory-hard algorithms use certain directed acyclic graphs known as superconcentrators. They are described and discussed. A novel memory-hard scheme called Bromine is described. Its memory structure can be generated in linear time and it is optimised for creation and storage on hard disk. Its use as a memory-hard proof of space is analysed. The implementation of Bromine in the C programming language is detailed, along with problems encountered, and finally its performance measured and explained for structures of different sizes up to one terabyte (1TB).

This project was done by Brian Shaft, supervised by Alex Biryukov, advised by Dmitry Khovratovich.

Thesis (PDF).

  • Hidden Service Tracking Detection and Bandwidth Cheating in Tor Anonymity Network

Instantaneous online communications through the Internet have become an integral part of our world, both for business as well as for individuals. However, some entities restrict access to parts of the Internet, in an effort to establish censorship, while others monitor online communications. To circumvent censorship, restore privacy and anonymity, some tools such as Tor, a low latency anonymity network, have been created.

This work focuses on Tor and has two contributions:

1. A method of detecting tracking attacks on hidden services as well as an implementation. By analyzing 39841 hidden services addresses for the year 2013 we found that at least 50 tor relays were conducting tracking attacks on a total of 45 hidden services. 2. An attack on the Tor bandwidth measurements protocol in order to obtain higher chances of being chosen for a client path, the implementation reaching a 1% probability to be chosen as an Exit node on the Tor network and the 21st highest relay, in terms of bandwidth weight, out of 5.834 active relays, while using a bandwidth only 50 KB/s.

This project was done by Fabrice Thill, supervised by Alex Biryukov, advised by Ivan Pustogarov.

Thesis (PDF).

  • The Swiss cipher machine NeMa

This is a functional description and cryptanalysis of the Swiss cipher machine NeMa. The machine is first compared with its predecessor, the German Enigma which suggests taking a deeper look into NeMa’s wheel stepping mechanism. NeMa’s stepping mechanism was designed to avoid the attacks discovered on Enigma’s fast wheels. It turns out that NeMa’s mechanism produces identifiable patterns that can be related to the machine’s settings. Three attacks are proposed: The stepping catalog attack which reduces the complexity of brute force attacks by discarding settings that do not match the produced stepping pattern. The spy operator attack which aids in recovering the machine’s inner settings when having partial access to the machine. The known plaintext attack which is able to test some part of the machine’s settings while discovering at the same time the rest of it. The last attack has complexity of 2^41 which is a significant improvement over a simple brute force attack which has complexity of 2^73.

This project was done by Ana Gaggero, supervised by Alex Biryukov, advised by Ralf-Philipp Weinmann.

Thesis (PDF).

  • Efficient Code Obfuscation for Android

Recent years have witnessed a steady shift in technology from desktop computers to mobile devices. In the global picture of available platforms, Android stands out as a dominant participant on the market and its popularity continues rising. While beneficial for its users, this growth simultaneously creates a prolific environment for exploitation by vile developers which write malware or reuse software illegally obtained by reverse engineering. A class of programming techniques known as code obfuscation targets prevention of intellectual property theft by parsing an input application through a set of algorithms aiming to make its source code computationally harder and time consuming to recover. This work focuses on the development and application of such algorithms on the bytecode of Android, Dalvik. The main contributions are: (1) a study on samples obtained from the official Android market which shows how feasible it is to reverse a targeted application; (2) a proposed obfuscator implementation whose transformations defeat current popular static analysis tools while maintaining a low level of added time and memory overhead; (3) an attempt to initiate a discussion on what techniques known from the x86 architecture can(not) be applied on Dalvik bytecode and why.

This project was done by Aleksandrina Kovacheva, supervised by Alex Biryukov, advised by Ralf-Philipp Weinmann.

Thesis (PDF) slides source code.

  • Cryptanalysis of Lightweight Block Ciphers

This thesis work summarizes the design criteria of lightweight block ciphers. It also presents a detailed design analysis of some of the recently designed block ciphers KLEIN, LED, and LBlock.

This project was done by Vikash Jha from Aalto Univerisity, supervised by Tuomas Aura, advised by Alex Biryukov.

Thesis (PDF)

  • Design and Realisation of a Program for Playing Tantrix

In this thesis a design and implementation was made of a new robot for playing Tantrix. Tantrix is a strategic board game invented by Mike McManaway. It consists of fifty-six hexagonal tiles with three coloured lines on them which have to be linked to make the longest line or loop. Minimax-based search techniques were used combined with heuristics to measure real, virtual and fair share line length to make a robot which is able to play Tantrix at an advanced level. This robot currently plays on and is called Oliver.

This project was done by Pieter Bolle from K.U.Leuven Univeristy, supervised by Danny De Schreye advised by Alex Biryukov.

Thesis (PDF).