4
$\begingroup$

I'm currently trying to convert a 5-bit sbox (the one from this cipher: http://primates.ae/wp-content/uploads/primatesv1.02.pdf) to its bit-sliced format (i.e. to a boolean network).

Most papers only address techniques for converting up to 4-bit s-boxes into their bitsliced format.

I have done some work trying to brute-force my way to the results, as a 5-bit s-box does not seem as much, this however still proved tricky, as their is in the end an infinite possibility og AND, NOT, OR and XOR that you can do on the 5 input bits... Is there any accepted/known way of doing this, or does it come down to trying to bruteforce different combinations till a matching one is found? (I hope not, as I have no guarantee on it being the optimal then).

I have considered trying to make truth tables and synthesize the logic network from them. I'm not sure this is the way to go though.

$\endgroup$
6
$\begingroup$

A recent paper presented at FSE'2016 [1] addresses this exact question. In fact, it even provides a bitsliced implementation for the S-Box you are interested in Section 4.

In summary: you first encode the existence of a bitsliced implementation as a SAT problem, use an off-th-shelf SAT-solver to solve it and finally retrieve the bitsliced encoding from the output of the SAT-solver.

[1]: http://eprint.iacr.org/2016/198.pdf "Optimizing S-box Implementations for Several Criteria using SAT Solvers", Ko Stoffelen, Proceedings of Fast Software Encryption 2016

$\endgroup$
  • 1
    $\begingroup$ and in the paper there is even a link to github repo... $\endgroup$ – Krystian May 3 '16 at 20:16
  • $\begingroup$ I cannot thank you enough for that answer. It has really helped me out. It describes well how to also optimize the s-box afterwards, so I can do some testing in terms of efficiency with the different variations of the s-box. Thanks! $\endgroup$ – oPolo May 7 '16 at 15:26
  • $\begingroup$ Another FSE paper you may want to check eprint.iacr.org/2017/101 $\endgroup$ – pushpen.paul Sep 30 '18 at 17:56
3
$\begingroup$

Try to generate the Algebraic Normal Form (ANF) from the sbox step by step (i.e., with 2 bits and so on) or use something like http://cis.sjtu.edu.cn/index.php/A_Simple_Python_Script_for_Translating_Sbox_to_ANF_Boolean_Functions

$\endgroup$
  • $\begingroup$ This page does not exist $\endgroup$ – pushpen.paul Sep 30 '18 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.