Publication

Applied stream ciphers in mobile communications

Yi Lu
2006
Theses

Abstract

This dissertation is concerned with cryptanalysis of E0, the stream cipher used in the short-range wireless radio standard Bluetooth, and of its generalization by means of correlation attacks. It consists of three parts. In the first part, we propose an E0-like combiner with memory as the core stream cipher. First, we formulate a systematic and simple method to compute the correlations. An upper bound of the correlations is given. Second, we show how to build either a uni-bias-based or multi-bias-based distinguisher to distinguish the keystream produced by the combiner from a truly random sequence, once correlations are found. The data complexity of either distinguisher is analyzed for performance comparison. The keystream distinguisher is then upgraded for use in the key-recovery attack. The latter reduces to the well-known maximum likelihood decoding problem given the keystream long enough. In the second part, the core stream cipher is transformed into the dedicated stream cipher by attaching the one-level or two-level initialization scheme. We show that the correlation attack on the core stream cipher leads to the correlation attack on the dedicated stream cipher with the one-level initialization scheme (with equal bias), but not necessarily so with the two-level initialization scheme. In the last part, we generalize the existing concept of conditional correlations and study conditional correlation attacks against stream ciphers and other cryptosystems. A general framework is developed for smart distinguishers, which exploit those generalized conditional correlations. Based on the theory of the traditional distinguisher, we derive the number of samples necessary for a smart distinguisher to succeed. It allows to prove that the smart distinguisher improves on the traditional basic distinguisher. As an application of all our analysis, it leads to the fastest (and only) practical known-plaintext attack on Bluetooth encryption so far. Our attack recovers the encryption key using the first 24 bits of 223.8 frames and with 238 computations.

Official source

https://infoscience.epfl.ch/entities/publication/54a79c7f-0591-4484-bb07-165b6cb0f5fc

Yi Lu
2006
Theses

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/54a79c7f-0591-4484-bb07-165b6cb0f5fc

Ontological neighbourhood

Computer engineering

Computer security: Public-key cryptography

Related concepts (32)

Stream cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

Timing attack

In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker can work backwards to the input. Finding secrets through timing information may be significantly easier than using cryptanalysis of known plaintext, ciphertext pairs.

Stream cipher attacks

Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be very secure if used properly. However, they are vulnerable to attacks if certain precautions are not followed: keys must never be used twice valid decryption should never be relied on to indicate authenticity Stream ciphers are vulnerable to attack if the same key is used twice (depth of two) or more. Say we send messages A and B of the same length, both encrypted using same key, K.

Related publications (31)

Secure and Efficient Cryptographic Algorithms in a Quantum World

Loïs Evan Huguenin-Dumittan

Since the advent of internet and mass communication, two public-key cryptographic algorithms have shared the monopoly of data encryption and authentication: Diffie-Hellman and RSA. However, in the last few years, progress made in quantum physics -- and mo ...

EPFL2024

Side-channel analysis of isogeny-based key encapsulation mechanisms and hash-based digital signatures

Aymeric Genet

Current cryptographic solutions will become obsolete with the arrival of large-scale universal quantum computers. As a result, the National Institute of Standards and Technology supervises a post-quantum standardization process which involves evaluating ca ...

EPFL2024

An Ultra-High Throughput AES-Based Authenticated Encryption Scheme for 6G: Design and Implementation

Andrea Felice Caforio, Subhadeep Banik

In this paper, we propose Rocca-S, an authenticated encryption scheme with a 256-bit key and a 256-bit tag targeting 6G applications bootstrapped from AES. Rocca-S achieves an encryption/decryption speed of more than 200 Gbps in the latest software environ ...

Springer International Publishing Ag2024