Linear Cryptanalysis of Bluetooth Stream Cipher

摘要

A general linear iterative cryptanalysis method for solving binary systems of approximate linear equations which is also applicable to keystream generators producing short keystream sequences is proposed. A linear cryptanalysis method for reconstructing the secret key in a general type of initialization schemes is also developed. A large class of linear correlations in the Bluetooth combiner, unconditioned or conditioned on the output or on both the output and one input, are found and characterized. As a result, an attack on the Bluetooth stream cipher that can reconstruct the 128-bit secret key with complexity about 2~(70) from about 45 initializations is proposed. In the precomputation stage, a database of about 2~(80) 103-bit words has to be sorted out.