I have an assignment where I have to understand a protocol proposed in a research paper. The first step involves computing Per-XOR, but I can't seem to understand the explanation given. Below is the explanation given, along with solved question:

"Permute (transposition) the string β€˜π‘šβ€™ according to the string β€˜π‘›β€™, by checking each π‘–π‘‘β„Ž bit of the string β€˜π‘›β€™ (starting from LSB). If 𝑛𝑖= 0 then the bit stored at π‘šπ‘– will be placed at π‘šπ‘™ location (LSB); otherwise, it will be placed at the same position. In the next clock cycle, if 𝑛𝑖+1= 0 then the bit stored at π‘šπ‘–+1 will be placed at π‘šπ‘™βˆ’1 location; otherwise, it will shifted-left (LSB side). This process will continue till we reach to MSB of string β€˜π‘›β€™(𝑛𝑙). After completion, we will have a new string β€˜mβˆ—β€™ which is the permuted version of string β€˜π‘šβ€™."

enter image description here

Now what I'm understanding from the above explanation is that with n we have to start from the LSB side and permutate bits in m accordingly. But in the fig we are starting from the MSB side, because n = 1 and therefore the bit in m1 position will not be shifted, if it started from the LSB side the n = 0 and m would be placed at ml.

I'm really confused as to what's happening, If anyone can provide an explanation with the above given example, I would be grateful.


1 Answer 1


Here is another way to understand the transform (and it may be an easier way):

  • For all the locations where N has a 1 bit, take the corresponding bit in M, and place them together to form A (so that if N has 5 1 bits, the result A has 5 bits). In the example, A would be 0101.

  • For all the locations where N has a 0 bit, take the corresponding bit in M, and place them together to form B (so that if N has 3 0 bits, the result B has 3 bits). In the example, B would be 0111.

  • Reverse the bit order of B (so if it was 011, it becomes 110). In the example, B would now be 1110.

  • Concatinate A and B together (with A being the most significant bit), forming M*. In the example, M* would be 01011110

  • Last step: xor M* and N to get the result.

Now, looking at it from a cryptanalyst standpoint, this primitive does not look promising. Flipping one bit of the input N will always flip exactly one bit of the output. Flipping the lsbit of M will always flip the lsbit of the output (with no other changes). It has high probability linear and differential characteristics. In addition, it is unclear how it could be implemented efficiently (and in constant time/memory accesses). However, whether these are fatal would depend on the latter steps of the entire protocol.

One task you might try to help you understand the protocol: try to figure out how these weaknesses could be used to undermine the overall protocol.

  • $\begingroup$ Thank you so much. $\endgroup$
    – Fakhr Ali
    Commented Dec 23, 2023 at 18:29

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.