V. Amin Ghafari; A. Vardasbi; J. Mohajeri
Abstract
The A5/1 algorithm is one of the most famous stream cipher algorithms used for over-the-air communication privacy in GSM. The purpose of this paper is to analyze several weaknesses of A5/1, including an improvement to an attack and investigation of the A5/1 state transition. Biham and Dunkelman proposed ...
Read More
The A5/1 algorithm is one of the most famous stream cipher algorithms used for over-the-air communication privacy in GSM. The purpose of this paper is to analyze several weaknesses of A5/1, including an improvement to an attack and investigation of the A5/1 state transition. Biham and Dunkelman proposed an attack on A5/1 with a time and data complexity of 239.91and 221.1, respectively. In this paper, we propose a method for identification and elimination of useless states from the pre-computed tables and a new approach to access the table in the online phase of the attack which reduces the time complexity to 237.89 and the required memory in half. Furthermore, we discuss another weakness of A5/1 by investigating its internal state transition and its key stream sequence period. Consequently, the internal states are divided into two classes, initially periodic and ultimately periodic. The presented model is verified using a variety of simulations which are consistent with the theoretical results.
A. Vardasbi; M. Salmasizadeh; J. Mohajeri
Abstract
Chi-square tests are generally used for distinguishing purposes; however when they are combined to simultaneously test several independent variables, extra notation is required. In this study, the chi-square statistics in some previous works is revealed to be computed half of its real value. Therefore, ...
Read More
Chi-square tests are generally used for distinguishing purposes; however when they are combined to simultaneously test several independent variables, extra notation is required. In this study, the chi-square statistics in some previous works is revealed to be computed half of its real value. Therefore, the notion of Multi _ Chi-square tests is formulated to avoid possible future confusions. In order to show the application of Multi _ Chi square tests, two new tests are introduced and applied to reduce round Trivium as a special case. These tests are modifications of the ANF monomial test, and when applied to Trivium with the same number of rounds, the data complexity of them is roughly 24 times smaller than that of former ANF monomial test. In a Multi _ Chi-square test the critical degrees of freedom is defined to be the minimum value of the degrees of freedom for which the test is successful at distinguishing the samples set from random. This study investigates the relation between this critical value and the chi-square statistic of a Multi _ Chi-square test. In the sequel, by exploiting this relation, a method to approximate the data complexity of a distinguishing Multi _ Chi-square test is introduced and shown to perform properly in the special case of reduced round Trivium.