| 1. |
- Ekdahl, Patrik, et al.
(författare)
-
Another attack on A5/1
- 2003
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 49:1, s. 284-289
-
Tidskriftsartikel (refereegranskat)abstract
- A5/1 is a stream cipher used in the Global System for Mobile Communications (GSM) standard. Several time-memory tradeoff attacks against A5/1 have been proposed, most notably the recent attack by Biryukov, Shamir, and Wagner, which can break A5/1 in seconds using huge precomputation time and memory. This correspondence presents a completely different attack on A5/1, based on ideas from correlation attacks. Whereas time-memory tradeoff attacks have a complexity which is exponential with the shift-register length, the complexity of the proposed attack is almost independent of the shift-register length. Our implementation of the suggested attack breaks A5/1 in a few minutes using 2-5 min of conversation plaintext.
|
|
| 2. |
- Guo, Qian, et al.
(författare)
-
A Key Recovery Reaction Attack on QC-MDPC
- 2019
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 65:3, s. 1845-1861
-
Tidskriftsartikel (refereegranskat)abstract
- Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this work we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80-bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides INDCCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility. Last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the naïve algorithm for key reconstruction by a factor of about 30,000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery.
|
|
| 3. |
- Guo, Qian, et al.
(författare)
-
A New Algorithm for Solving Ring-LPN With a Reducible Polynomial
- 2015
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 61:11, s. 6204-6212
-
Tidskriftsartikel (refereegranskat)abstract
- The learning parity with noise (LPN) problem has recently proved to be of great importance in cryptology. A special and very useful case is the Ring-LPN problem, which typically provides improved efficiency in the constructed cryptographic primitive. We present a new algorithm for solving the Ring-LPN problem in the case when the polynomial used is reducible. It greatly outperforms the previous algorithms for solving this problem. Using the algorithm, we can break the Lapin authentication protocol for the proposed instance using a reducible polynomial, in ~271 bit operations.
|
|
| 4. |
- Guo, Qian, et al.
(författare)
-
On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving
- 2019
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 65:8, s. 5243-5259
-
Tidskriftsartikel (refereegranskat)abstract
- The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the Blum-Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the Regev parameters $q=n^2$ and noise level $\sigma = n^{1.5}/(\sqrt{2\pi}\log_{2}^{2}n)$, the asymptotic complexity is $2^{0.893n}$ in the standard setting, improving on the previously best known complexity of roughly $2^{0.930n}$. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.
|
|
| 5. |
- Hell, Martin, et al.
(författare)
-
Improved Distinguishers on Stream Ciphers with Certain Weak Feedback Polynomials
- 2012
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 58:9, s. 6183-6193
-
Tidskriftsartikel (refereegranskat)abstract
- It is well known that fast correlation attacks can be very efficient if the feedback polynomial is of low weight. These feedback polynomials can be considered weak in the context of stream ciphers. This paper generalizes the class of weak feedback polynomials into polynomials were taps are located in several groups, possibly far apart. Low weight feedback polynomials are thus a special case of this class. For the general class it is shown that attacks can sometimes be very efficient even though the polynomials are of large weight. The main idea is to consider vectors of noise variables. It is shown how the complexity of a distinguishing attack can be efficiently computed and that the complexity is closely related to the minimum row distance of a generator matrix for a convolutional code. Moreover, theoretical results on the size of the vectors are given.
|
|
| 6. |
- Hell, Martin, et al.
(författare)
-
Two new attacks on the self-shrinking generator
- 2006
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 52:8, s. 3837-3843
-
Tidskriftsartikel (refereegranskat)abstract
- The self-shrinking generator was introduced in 1994. It is based on the idea behind the shrinking generator and despite its simplicity it has remained remarkably resistant to efficient attacks. Several known plaintext attacks have been proposed on the generator, some operating on a short keystream and others requiting a longer sequence to succeed. In this paper, two new attacks on the self-shrinking generator are proposed. The first attack, using a short known keystream, has the same complexity as the BDD-based attack, which is the best previously known attack. However, while the BDD-based attack requires a huge amount of memory, the proposed algorithm uses almost no memory, leaving it as the preferred alternative. The second attack operates on a longer known keystream, exponential in the length of the LFSR. The attack considers one or several segments of keystream bits and guesses that these bits stem from LFSR segments of some size. It is shown that this attack achieves better complexity than any previously known attack.
|
|
| 7. |
- Johansson, Thomas, et al.
(författare)
-
A construction of resilient functions with high nonlinearity
- 2003
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 49:2, s. 494-501
-
Tidskriftsartikel (refereegranskat)abstract
- We provide a construction technique for multiple-output resilient functions F: F-2(n) --> F-2(m) with high nonlinearity. The construction leads to the problem of finding a set of linear codes with a fixed minimum distance, having the property that the intersection between any two codes is the all-zero codeword only. This problem is considered, and existence results are provided. Moreover, the constructed functions obtain a nonlinearity superior to previous construction methods.
|
|
| 8. |
- Johansson, Thomas, et al.
(författare)
-
A linear distinguishing attack on SCREAM
- 2007
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 53:9, s. 3127-3144
-
Tidskriftsartikel (refereegranskat)abstract
- A linear distinguishing attack on the stream cipher Scream is proposed. When the keystream is of length 2(98) words, the distinguisher has a detectable advantage. When the keystream length is around 2(120) the advantage is very close to 1. This shows certain weaknesses of Scream. In the process, the paper introduces new general ideas on how to improve the performance of linear distinguishing attacks on stream ciphers.
|
|
| 9. |
- Johansson, Thomas, et al.
(författare)
-
A simple one sweep algorithm for optimal APP symbol decoding of linear block codes
- 1998
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448. ; 44:7, s. 3124-3129
-
Tidskriftsartikel (refereegranskat)abstract
- Soft-input/soft-output symbol decoding plays a significant role in iterative decoding. We propose a simple optimal soft-input/soft-output symbol decoding algorithm for linear block codes which requires one forward recursion using a trellis. For many codes the decoding complexity is lower than previous methods, such as the algorithm by Bahl et al. (1974), and the decrease is shown at its most when decoding Hamming codes.
|
|
| 10. |
- Johansson, Thomas
(författare)
-
Lower bounds on the probability of deception in authentication with arbitration
- 1994
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448. ; 40:5, s. 1573-1585
-
Tidskriftsartikel (refereegranskat)abstract
- The paper investigates a model for authentication in which not only an outsider, but also the transmitter or the receiver, may cheat. Lower bounds on the probability of success for different types of deception as well as on the parameters of secure authentication codes are derived. The latter bounds are shown to be tight by demonstrating codes in projective space that meet the bounds with equality.
|
|
