Modeling Linear and Non-linear Layers: An MILP Approach Towards Finding Differential and Impossible Differential Propagations

• URL: http://arxiv.org/abs/2405.00441v1
• Date: Wed, 1 May 2024 10:48:23 GMT
• Title: Modeling Linear and Non-linear Layers: An MILP Approach Towards Finding Differential and Impossible Differential Propagations
• Authors: Debranjan Pal, Vishal Pankaj Chandratreya, Abhijit Das, Dipanwita Roy Chowdhury,
• Abstract summary: We introduce an automatic tool for exploring differential and impossible propagations within a cipher. The tool is successfully applied to five lightweight block ciphers: Lilliput, GIFT64, SKINNY64, Klein, and M.IBS.
• Score: 1.5327660568487471
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Symmetric key cryptography stands as a fundamental cornerstone in ensuring security within contemporary electronic communication frameworks. The cryptanalysis of classical symmetric key ciphers involves traditional methods and techniques aimed at breaking or analyzing these cryptographic systems. In the evaluation of new ciphers, the resistance against linear and differential cryptanalysis is commonly a key design criterion. The wide trail design technique for block ciphers facilitates the demonstration of security against linear and differential cryptanalysis. Assessing the scheme's security against differential attacks often involves determining the minimum number of active SBoxes for all rounds of a cipher. The propagation characteristics of a cryptographic component, such as an SBox, can be expressed using Boolean functions. Mixed Integer Linear Programming (MILP) proves to be a valuable technique for solving Boolean functions. We formulate a set of inequalities to model a Boolean function, which is subsequently solved by an MILP solver. To efficiently model a Boolean function and select a minimal set of inequalities, two key challenges must be addressed. We propose algorithms to address the second challenge, aiming to find more optimized linear and non-linear components. Our approaches are applied to modeling SBoxes (up to six bits) and EXOR operations with any number of inputs. Additionally, we introduce an MILP-based automatic tool for exploring differential and impossible differential propagations within a cipher. The tool is successfully applied to five lightweight block ciphers: Lilliput, GIFT64, SKINNY64, Klein, and MIBS.

Related papers

• Anomaly Detection with LWE Encrypted Control [5.263161322684099]
  We present a novel mechanism for anomaly detection over Learning with Errors encrypted signals. The detector exploits the homomorphic property of LWE encryption to perform hypothesis tests on transformations of the encrypted samples.
  arXiv  Detail & Related papers  (2025-02-14T16:38:51Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem. These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem. We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Leveraging a Randomized Key Matrix to Enhance the Security of Symmetric Substitution Ciphers [0.0]
  An innovative strategy to enhance the security of symmetric substitution ciphers is presented. It is implemented through the implementation of a randomized key matrix suitable for various file formats.
  arXiv  Detail & Related papers  (2023-11-29T21:13:38Z)
• Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems [0.05120567378386613]
  We introduce a novel perspective on cryptosystems by viewing the Diffie-Hellman key exchange and the Rivest-Shamir-Adleman cryptosystem as nonlinear dynamical systems. By applying Koopman theory, we transform these dynamical systems into higher-dimensional spaces and analytically derive equivalent purely linear systems.
  arXiv  Detail & Related papers  (2023-11-21T16:38:48Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Recovering AES Keys with a Deep Cold Boot Attack [91.22679787578438]
  Cold boot attacks inspect the corrupted random access memory soon after the power has been shut down. In this work, we combine a novel cryptographic variant of a deep error correcting code technique with a modified SAT solver scheme to apply the attack on AES keys. Our results show that our methods outperform the state of the art attack methods by a very large margin.
  arXiv  Detail & Related papers  (2021-06-09T07:57:01Z)
• Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers [0.0]
  We cast encryption via classical block ciphers in terms of operator spreading in a dual space of Pauli strings. We quantify the quality of ciphers using measures of delocalization in string space.
  arXiv  Detail & Related papers  (2020-11-12T18:06:27Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Suppress and Balance: A Simple Gated Network for Salient Object Detection [89.88222217065858]
  We propose a simple gated network (GateNet) to solve both issues at once. With the help of multilevel gate units, the valuable context information from the encoder can be optimally transmitted to the decoder. In addition, we adopt the atrous spatial pyramid pooling based on the proposed "Fold" operation (Fold-ASPP) to accurately localize salient objects of various scales.
  arXiv  Detail & Related papers  (2020-07-16T02:00:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.