# Tag Info

19

Bitslicing is a technique where computation is: Reduced to elementary operations (called gates) with two bit inputs (typically NOR, XOR, and similar like OR AND NAND NXOR), rather than operations on words or integers spanning several bits. Executed in parallel, with as many simultaneous instances (on a single CPU) as there are bits in some register kind, ...

16

The basic idea of bitslicing, or SIMD within a register, involves two parts: expressing the cipher in terms of single-bit logical operations (AND, OR, XOR, NOT, etc.), as if you were implementing it in hardware, and carrying out those operations for multiple instances of the cipher in parallel, using bitwise operations on a CPU. That is, in a bitsliced ...

9

Bitslicing is a technique that allows multiple instructions/Data points to be encoded into a single register. The idea is that you encode several bitwise operations within a single register. So, instead of 32 bitwise OR operations in sequence, you could reduce the total number of operations by cramming the data into SIMD registers and executing in ...

7

The reason it is taking 4 32-bit integers into the round function is because it IS a bitsliced implementation. It bitsclices 32 4-bit sboxes into 4 32-bit inputs and uses standard logical operations on the words to get the job done. The sbox you posted was not generated by Osvik, but he generated a set of optimized blitsliced sboxes for 32-bit ...

6

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 ...

5

Slide #8 in the presentation you linked to describes the way Käsper and Schwabe pack the bits of the AES data blocks into CPU registers. According to the slide, what they're doing is processing eight 128-bit AES blocks in parallel, using eight 128-bit XMM registers to store them. They're not doing basic "naïve bitslicing", which would involve using 128 $n$-...

5

You can (and should) do the reduction in constant time using masking. That is, instead of using the following (non-bitsliced) pseudo-C code to do the reduction: if ((result >> 8) & 1) { /* bit 8 is set: clear it and flip bits 0, 1, 3 and 4 */ result ^= 0x11b; } you can simply do: result ^= 0x11b * ((result >> 8) & 1); (where ...

3

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

Only top voted, non community-wiki answers of a minimum length are eligible