🇬🇧

Secure Volunteer Computing for Distributed Cryptanalysis

Volunteer computing offers researchers and developers the possibility to distribute their huge computational jobs to the computers of volunteers. So, most of the overall cost for computational power and maintenance is spread across the volunteers. This makes it possible to gain computing resources that otherwise only expensive grids, clusters, or supercomputers offer. Most volunteer computing solutions are based on a client-server model. The server manages the distribution of subjobs to the computers of volunteers, the clients, which in turn compute the subjobs and return the results to the server. The Berkeley Open Infrastructure for Network Computing (BOINC) is the most used middleware for volunteer computing. A drawback of any client-server architecture is the server being the single point of control and failure. To get rid of the single point of failure, we developed different distribution algorithms (epoch distribution algorithm, sliding-window distribution algorithm, and extended epoch distribution algorithm) based on unstructured peer-to-peer networks. These algorithms enable the researchers and developers to create volunteer computing networks without any central server. The thesis is structured into two different parts. The first is the distribution part and discusses the aforementioned new distribution algorithms and their usage for distributed cryptanalysis. The second part is the cheating part which extends our system with solutions for cheat detection in unstructured peer-to-peer networks. In this thesis, we focus on volunteer computing for distributed cryptanalysis. Since the computational effort to break many classical as well as most modern ciphers is very huge, hundreds to thousands of computers are often needed for executing successful attacks. We show in this thesis that our solutions are well-suited for attacking classical as well as modern ciphers. Some of our algorithms have been implemented for distributed cryptanalysis, e.g. brute-force and heuristics, to solve real-world ciphers. Additionally, we evaluated all of our distribution solutions with selfwritten simulators and with real-world tests over the Internet in CrypTool 2. By combining 50 off-the-shelf computers, we achieved a search speed of about 615 millions AES keys per second. A single of these computers, an Intel i5-3570 with 3.4 GHz and 4 CPU cores, is able to search at a rate between 12 and 13 millions AES keys per second. The distribution is self-organized by our algorithms. Additionally, we achieved a speedup for the cryptanalysis of the classical M-94 cipher of about 6.82, with respect to using only a single computer, enabling us to break original M-94 messages within 2 hours and 56 minutes with 6 standard computers. Cheating is a well-known threat in any volunteer computing project. Cheaters aim at computing less work as demanded by the creator of the project but they try to gain the same reward, i.e. credit points, as non-cheaters deserve. Cheated results are mostly incomplete or wrong, disturbing or even destroying the final result of the volunteer computing project. This can make weeks, months, and years of computational work useless. To fight cheaters, detection and prevention mechanisms are needed. A BOINC server assigns the same subjob to different clients and uses majority voting to determine the correctness of results. Since we base our volunteer computing and our distribution algorithms on unstructured peerto-peer networks, where all peers are equal in role, majority voting is not possible. No central server is available to assign same subjobs to different peers. Thus, we developed new cheat detection mechanisms for decentralized peer-to-peer networks. We spread the detection of a cheated result over all peers of the network. Each peer has a small probability of detecting a cheated result but the network in sum reaches a high detection rate. In this thesis, we differentiate between two cheat detection approaches: static detection, with each peer performing the same amount of detection effort, and adaptive detection, with each peer dynamically adapting his additional cheat-detection effort to the growing and shrinking size of the peer-to-peer network. Both approaches work but the static does not scale while the adaptive scales well. We show that we can achieve detection rates above 99.8% with both, the static cheat detection approach as well as the adaptive cheat detection approach. With the adaptive cheat detection approach the needed detection effort is constant throughout the network when increasing the amount of connected nodes.

Imprint
@book{doi:10.19211/KUP9783737604277,
urn:nbn:de:0002-404276,
  author    ={Kopal, Nils},
  title    ={Secure Volunteer Computing for Distributed Cryptanalysis},
  keywords ={004 and Verteiltes System and Netzwerktopologie and Computersicherheit and Kryptoanalyse and Secret-Sharing and Private-Key-Kryptosystem and Public-Key-Kryptosystem and Peer-to-Peer-Netz and Cloud Computing},
  copyright  ={https://rightsstatements.org/page/InC/1.0/},
  language ={en},
  year   ={2018}
}