5
$\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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
$\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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ and in the paper there is even a link to github repo... $\endgroup$
    – Kris
    Commented May 3, 2016 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
    Commented May 7, 2016 at 15:26
  • $\begingroup$ Another FSE paper you may want to check eprint.iacr.org/2017/101 $\endgroup$
    – hola
    Commented Sep 30, 2018 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

Improve this answer
$\endgroup$
1
  • $\begingroup$ This page does not exist $\endgroup$
    – hola
    Commented Sep 30, 2018 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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