Analysis and Correction of Courtois Attack to KeeLoq Cipher

KeeLoq is a block cipher designed by Willem Smit which is used in wireless devices that unlock doors in cars. Four slide-algebraic attacks that can break KeeLoq in practice are presented by Courtois et al. in 2007. The computing complexity of the fourth slide-algebraic attack is the smallest. However, the principle of Courtois fourth slide-algebraic attack is proved to be wrong in this thesis, so it can not break KeeLoq. The correction is made on Courtois fourth slide-algebraic attack and the improving attack is proposed. With 232 known plaintexts, the computing complexity of the improving attack is about O(248) KeeLoq encryptions for obtaining key and the success rate is 1. For 26％ of keys in KeeLoq, the first 64 rounds of KeeLoq have 2 or more fixed points, then the computing complexity of the improving attack which uses algebraic attack could decrease to O(248) KeeLoq encryptions.