Linear Cryptanalysis of Bluetooth Stream Cipher

A general linear iterative cryptanalysis methodfor 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 conditionedon the output or on both the output andone input, are found andcharacterized. As a result, an attack on the Bluetooth stream cipher that can reconstruct the 128-bit secret key with complexity about 270 from about 45 initializations is proposed. In the precomputation stage, a database of about 280 103-bit words has to be sorted out.