TY - GEN
T1 - Extending the applicability of the mixed-integer programming technique in automatic differential cryptanalysis
AU - Sun, Siwei
AU - Hu, Lei
AU - Wang, Meiqin
AU - Yang, Qianqian
AU - Qiao, Kexin
AU - Ma, Xiaoshuang
AU - Song, Ling
AU - Shan, Jinyong
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - We focus on extending the applicability of the mixed-integer programming (MIP) based method in differential cryptanalysis such that more work can be done automatically. Firstly, we show how to use the MIP-based technique to obtain almost all high probability 2-round iterative related-key differential characteristics of PRIDE (a block cipher proposed in CRYPTO 2014) automatically by treating the (formula presented) function with a special kind of modulo addition operations in the key schedule algorithm of PRIDE as an 8 × 8 S-box and partially modelling its differential behavior with linear inequalities. Note that some of the characteristics presented in this paper has not been found before, and all the characteristics we found can be used to attack the full-round PRIDE in the related-key model. Secondly, we show how to construct MIP models whose feasible regions are exactly the sets of all possible differential characteristics of SIMON (a family of lightweight block ciphers designed by the U.S. National Security Agency). With this method, there is no need to filter out invalid characteristics due to the dependent inputs of the AND operations. Finally, we present an MIP-based method which can be used to automatically analyze how the differences at the beginning and end of a differential distinguisher propagate upwards and downward. Note that how the differences at the ends of a differential distinguisher propagate, together with the probability of the differential distinguisher, determine how many outer rounds can be added to the distinguisher, which key bits can be recovered without exhaustive search, and how to identify wrong pairs in the filtering process. We think this work serves to further strengthens the position of the MIP as a promising tool in automatic differential cryptanalysis.
AB - We focus on extending the applicability of the mixed-integer programming (MIP) based method in differential cryptanalysis such that more work can be done automatically. Firstly, we show how to use the MIP-based technique to obtain almost all high probability 2-round iterative related-key differential characteristics of PRIDE (a block cipher proposed in CRYPTO 2014) automatically by treating the (formula presented) function with a special kind of modulo addition operations in the key schedule algorithm of PRIDE as an 8 × 8 S-box and partially modelling its differential behavior with linear inequalities. Note that some of the characteristics presented in this paper has not been found before, and all the characteristics we found can be used to attack the full-round PRIDE in the related-key model. Secondly, we show how to construct MIP models whose feasible regions are exactly the sets of all possible differential characteristics of SIMON (a family of lightweight block ciphers designed by the U.S. National Security Agency). With this method, there is no need to filter out invalid characteristics due to the dependent inputs of the AND operations. Finally, we present an MIP-based method which can be used to automatically analyze how the differences at the beginning and end of a differential distinguisher propagate upwards and downward. Note that how the differences at the ends of a differential distinguisher propagate, together with the probability of the differential distinguisher, determine how many outer rounds can be added to the distinguisher, which key bits can be recovered without exhaustive search, and how to identify wrong pairs in the filtering process. We think this work serves to further strengthens the position of the MIP as a promising tool in automatic differential cryptanalysis.
KW - Automatic cryptanalysis
KW - Mixed-integer programming
KW - PRIDE
KW - Related-key differential attack
UR - http://www.scopus.com/inward/record.url?scp=84945897667&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-23318-5_8
DO - 10.1007/978-3-319-23318-5_8
M3 - Conference contribution
AN - SCOPUS:84945897667
SN - 9783319233178
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 141
EP - 157
BT - Information Security - 18th International Conference, ISC 2015, Proceedings
A2 - Lopez, Javier
A2 - Mitchell, Chris J.
PB - Springer Verlag
T2 - 18th International Conference on Information Security, ISC 2015
Y2 - 9 September 2015 through 11 September 2015
ER -