Improved Top-Down Techniques in Differential Cryptanalysis, by Itai Dinur and Orr Dunkelman and Masha Gutman and Adi Shamir
The fundamental problem of differential cryptanalysis is to find the highest entries in the Difference Distribution Table (DDT) of a given mapping F over n-bit values, and in particular to find the highest diagonal entries which correspond to the best iterative characteristics of $F$. The standard bottom-up approach to this problem is to consider all the internal components of the mapping along some differential characteristic, and to multiply their transition probabilities. However, this can provide seriously distorted estimates since the various events can be dependent, and there can be a huge number of low probability characteristics contributing to the same high probability entry.
In this paper we use a top-down approach which considers the given mapping as a black box, and uses only its input/output relations in order to obtain direct experimental estimates for its DDT entries which are likely to be much more accurate. In particular, we describe three new techniques which reduce the time complexity of three crucial aspects of this problem: Finding the exact values of all the diagonal entries in the DDT for small values of n, approximating all the diagonal entries which correspond to low Hamming weight differences for large values of $n$, and finding an accurate approximation for any $DDT$ entry whose large value is obtained from many small contributions. To demonstrate the potential contribution of our new techniques, we apply them to the SIMON family of block ciphers, show experimentally that most of the previously published bottom-up estimates of the probabilities of various differentials are off by a significant factor, and describe new differential properties which can cover more rounds with roughly the same probability for several of its members. In addition, we show how to use our new techniques to attack a 1-key version of the iterated Even-Mansour scheme in the related key setting, obtaining the first generic attack on 4 rounds of this well-studied construction.
Computational Aspects of Correlation Power Analysis, by Paul Bottinelli and Joppe W. Bos
Since the discovery of simple power attacks, the cryptographic research community has developed significantly more advanced attack methods. The idea behind most algorithms remains to perform a statistical analysis by correlating the power trace obtained when executing a cryptographic primitive to a key-dependent guess. With the advancements of cryptographic countermeasures, it is not uncommon that sophisticated (higher-order) power attacks require computation on many millions of power traces in order to find the desired correlation.
In this paper, we study the computational aspects of calculating the most widely used correlation coefficient: the Pearson product-moment correlation coefficient. We study various time-memory trade-off techniques which apply specifically to the cryptologic setting and present methods to extend already completed computations using incremental versions. Moreover, we show how this technique can be applied to second-order attacks, reducing the attack cost significantly when adding new traces to a dataset. We also present methods which allow one to split the potentially huge trace set into smaller, more manageable chunks in order to reduce the memory requirements. Our concurrent implementation of these techniques highlights the benefits of this approach as it allows efficient computations on power measurements consisting of hundreds of gigabytes on a single modern workstation.
Research Perspectives and Challenges for Bitcoin and Cryptocurrencies, by Joseph Bonneau, Andrew Miler, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, Edward W. Felten
Bitcoin has emerged as the most successful cryptographic currency in history. Within two years of its quiet launch in 2009, Bitcoin grew to comprise billions of dollars of economic value, even while the body of published research and security analysis justifying the system\'s design was negligible. In the ensuing years, a growing literature has identified hidden-but-important properties of the system, discovered attacks, proposed promising alternatives, and singled out difficult future challenges. This interest has been complemented by a large and vibrant community of open-source developers who steward the system, while proposing and deploying numerous modifications and extensions.
We provide the first systematic exposition of the second generation of cryptocurrencies, including Bitcoin and the many alternatives that have been implemented as alternate protocols or ``altcoins.\'\' Drawing from a scattered body of knowledge, we put forward three key components of Bitcoin\'s design that can be decoupled, enabling a more insightful analysis of Bitcoin\'s properties and its proposed modifications and extensions. We contextualize the literature into five central properties capturing blockchain stability. We map the design space for numerous proposed modification, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools. We focus on anonymity issues in Bitcoin and provide an evaluation framework for analyzing a variety of proposals for enhancing unlinkability. Finally we provide new insights on a what we term disintermediation protocols, which absolve the need for trusted intermediaries in an interesting set of applications. We identify three general disintermediation strategies and provide a detailed comparative cost analysis.
A look at the PGP ecosystem through the key server data, by Hanno Böck
PGP-based encryption systems use a network of key servers to share public keys. These key server operate on an add only basis, thus the data gives us access to PGP public keys from over 20 years of PGP usage. Analyzing this data allows searching for cryptographic weaknesses in large scale.
I created a parser script that puts the raw cryptographic data of the PGP keys into a database. Doing this allows large scale searches for well-known vulnerabilities. DSA signatures with a duplicate $k$ value due to bad random numbers allow the calculation of the private key. Similarly analyzing RSA keys for shared prime factors allows factoring the modulus and thus also regenerating the private key.
A small number of breakable keys due to these weaknesses were found.