Belief Propagation on Lightweight Cipher KLEIN

The KLEIN block cipher is a lightweight crpytographic algorithm designed for use inconstrained environments

such as smart cards and RFID tags, where low computational complexity and memory requirements are critical. [1]

In this thesis, we investigate the security of KLEIN against side-channel attacks that exploit leakage information from

the algorithm. Specifically, we propose a method for extracting the master key of KLEIN using Belief Propagation (BP)

and the Hamming Weight (HW) leakage of the key schedule. Our approach is based on modeling the key schedule as a

graphical model and using BP to infer the most likely value of the sub-round keys given the observed leakage. With the

most likely values of the sub-round keys, we can get the most likely values of the master key. After an introduction to BP

and building the graph and specifics of BP to model the KLEIN key schedule algorithm, we compare predicted results to a

correct implementation of KLEIN. Building upon the first design, we model multiple graphs with the combinations of different

nodes and operations in order to allow inference on many different leakage models created by a Side Channel Attack (SCA).

We then test BP applied on the graphs by comparing the predicted values with the real keys in our simulation. We compare

the accuracy of prediction with different noise levels and graph variations such as size and modifications.