,Название: Parallel Cryptanalysis
Автор: Ruben Niederhagen
Издательство: Autoedici?n
Год: 2012
Формат: pdf
Страниц: 125
Размер: 0,8 mb.
Язык: English
Most of today’s cryptographic primitives are based on computations that are hard to perform for a potential attacker but easy to perform for somebody who is in possession of some secret information, the key, that opens a back door in these hard computations and allows them to be solved in a small amount of time. Each cryptographic primitive should be designed such that the cost of an attack grows exponentially with the problem size, while the computations using the secret key only grow polynomially. To estimate the strength of a cryptographic primitive it is important to know how hard it is to perform the computation without knowledge of the secret back door and to get an understanding of how much money or time the attacker has to spend. Usually a cryptographic primitive allows the cryptographer to choose parameters that make an attack harder at the cost of making the computations using the secret key harder as well. Therefore designing a cryptographic primitive imposes the dilemma of choosing the parameters strong enough to resist an attack up to a certain cost while choosing them small enough to allow usage of the primitive in the real world, e.g. on small computing devices like smart phones.
Typically a cryptographic attack requires a tremendous amount of computation—otherwise the cryptographic primitive under attack can be considered broken. Given this tremendous amount of computation, it is likely that there are computations that can be performed in parallel. Therefore, parallel computing systems are a powerful tool for the attacker of a cryptographic system. In contrast to a legitimate user who typically exploits only a small or moderate amount of parallelism, an attacker is often able to launch an attack on a massively parallel system. In practice the amount of parallel computation power available to an attacker is limited only by the amount of money he is able to spend; however the amount of parallelism he can exploit depends on the particular attack which he is going to mount against a particular cryptographic primitive. The main challenge of implementing a cryptographic attack for a parallel computing system is to explore which parts of the computation can be computed in parallel and how this parallelism can be exploited most efficiently.
This thesis investigates three different attacks on particular cryptographic systems: Wagner’s generalized birthday attack is applied to the compression function of the hash function FSB. Pollard’s rho algorithm is used for attacking Certicom’s ECC Challenge ECC2K-130. The implementation of the XL algorithm has not been specialized for an attack on a specific cryptographic primitive but can be used for attacking certain cryptographic primitives by solving multivariate quadratic systems. All three attacks are general attacks, i.e. they apply to various cryptographic systems; therefore the implementations of Wagner’s generalized birthday attack and Pollard’s rho algorithm can be adapted for attacking other primitives than those given in this thesis. The three attacks have been implemented on parallel architectures, each attack on a different architecture. The results give an estimate of the scalability and cost of these attacks on parallel systems.