1
$\begingroup$

I heard that the permutation in PRESENT affects all bits after only a few rounds. However, when I looked at it the bits return to their original position after only three rounds. For example, in round-1 bit b1 ---> b16, in round-2 b16 ---> b4, and in round-3 b4 ---> b1; thereafter the cycle repeats. This is the same for all bits, except b0, b21, b42 and b63 which do not move at all.

So my question is: this being the case, how does the permutation cause each bit to affect every other bit?

I am sure I have missed the point, so a simple 'numerical' example would be much appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Yes, you might think that the bits return to their original positions. But they don't because those aren't the bits you're looking for. They've changed. Specifically, you need to consider the effect of the s-boxes. If a single bit goes into a s-box, it's very nature means that on average, two bits come out. Similarly, if three bits go in, two bits still emerge on average. This is the substitution component of PRESENT. What you've focused solely on is the permutation component. To achieve full and proper diffusion of bits throughout a substitution /permutation network (SPN), you need both components to work together.

This repetitive substitution and permutation (what Shannon termed confusion and diffusion) creates an avalanche effect through the internal state. If such a network happened to have the same number of s-boxes as their width (ie. 8 boxes of 8 bits), you would achieve full avalanche effect in two rounds. If the ratio is different like PRESENT's 4/16 construction, full avalanche won't occur till more rounds happen. It's a function of the ratio. I don't know how many rounds PRESENT needs, but it clearly happens way before the total 31. These networks tend to have a very generous and conservative round count to help security.

So it's the effect of the s-boxes in conjunction with the permutation that ensures all bits affect all other bits. The diagram below is for a generic SPN but illustrates a bit's travel through it:-

SPN

One bit went in and as expected on average 8 bits come out. It simply doesn't work if you just consider the permutations on their own.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, but I am still unsure about: when one bit enters an S-box, on average two bits come out. In PRESENT all inputs to s-boxes are 4-bit. Or are you talking specifically about the digit 1 entering an s-box, and not the digit 0? I thought one bit could be either 0 or 1. Sorry for my confusion, this is still quite new to me. $\endgroup$
    – Red Book 1
    Jul 29, 2017 at 5:37
  • $\begingroup$ @RedBook1 The way an s-box operates is that on average it always outputs half of it's width, no matter the input. It's almost like a random relationship between input and output but a lot cleverer. So for PRESENT, a set bit on any of the 4 lines going in to the s-box outputs 2 bits (on average). Re. diagram: a bit enters the 2nd s-box down on the left and 2 emerge. This then propagates further between other s-boxes due to the permutations. Have a look at the s-box tag crypto.stackexchange.com/questions/tagged/s-boxes... $\endgroup$
    – Paul Uszak
    Jul 29, 2017 at 9:40
  • $\begingroup$ Can you give an example using PRESENT? Just a couple 'numerical' examples of a few rounds tracing the route of one bit entering an s-box and how it comes out as two or more bits. Moreover, I am not sure what the 'width' of an S-box means. Considering PRESENT, if bits b3,b2,b1,b0 = 1 1 1 1 then S[1111] = 0010, so now b3=0, b2=0, b1=1, b0=0. After that, the permutation moves each bit to a new location; b3 to position 48, b2 to 32, b1 to 16 and b0 unchanged. I still see four bits going in, and four bits coming out even though the bits have moved position. $\endgroup$
    – Red Book 1
    Aug 2, 2017 at 6:02

Your Answer

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

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