Introduction

Not sure if the title is an accurate description, but when you apply a self-inverse permutation or involution twice, you get back the original data and that’s pretty much what the code shown in this post does. There’s a number of block and stream ciphers that use involutions to make implementation of a cipher much easier in resource-constrained environments. And it also makes the job of cryptanalysis simpler because there’s less code to analyse. Some notable ciphers that use them include:

• KHAZAD
• Anubis
• NOEKEON

There’s also modular arithmetic (add/sub/mul/pow) can be used with the right modulus.

Of course, an XOR is also an involution and the most popular used for masking strings and code. But as you’ll see in the following code, it’s just as easy to use an involutory S-Box.

Example

Although RC4 isn’t an involution itself, it’s possible to modify the Key-scheduling algorithm (KSA) to create one. After the initialisation of S-Box and shuffling, some additional code can create an involutory S-Box. In the previous post, there were two S-Boxes created for masking and unmasking. The second was simply an inverse of the first. In the following, only one S-Box is created for both.

typedef unsigned int W;
typedef unsigned char B;

// Pseudo-Random Involution: S(S(x)) == x
void
make_sbox(B s[256], B k[16]) {
    // initialise
    for (W i=0; i<256; i++) {
        s[i] = (B)i;
    }
    // shuffle
    for (W i=0, j=0; i<256; i++) {
        j = (j + (s[i] + k[i % 16])) % 256;
        B t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
    // make involution
    for (W i=0; i<256; i++) {
        if (s[s[i]] == i) continue;
        for (W j=i+1; j<256; j++) {
            if (s[s[j]] != i) continue;
            B t = s[i];
            s[i] = s[j];
            s[j] = t;
            break;
        }
    }
}

A test program generates something similar to the following:

 Pseudo-Random Involution : Sk(Sk(x)) == x

key:
 22 5F 4D 02 12 48 A5 04 34 AD 55 96 D9 EB 56 9D

sbox:
 F1 12 C5 F4 91 A3 9E EA 38 70 F7 B8 D1 57 5F 3C
 99 46 01 89 51 4A D4 AD 25 F5 8E 2E 47 65 80 8B
 E5 DE FA 90 64 18 FF AB DC 9C 76 B9 55 7B 1B FB
 E6 B3 53 7D DD 4C 41 F6 08 E7 95 BB 0F EC 8D 8F
 B0 36 AC 86 4F B2 11 1C A4 5D 15 6E 35 A0 8C 44
 F9 14 E8 32 C3 2C D5 0D 9D C9 A7 E0 9A 49 A2 0E
 EE E2 BC B7 24 1D 6A C1 F3 79 66 77 C7 BE 4B 7E
 09 EF E4 C0 D7 9F 2A 6B FC 69 D2 2D CA 33 6F AE
 1E B4 A6 E9 F8 CE 43 F2 C6 13 8A 1F 4E 3E 1A 3F
 23 04 BD D9 A1 3A E3 D0 DA 10 5C C8 29 58 06 75
 4D 94 5E 05 48 FD 82 5A A8 C2 CC 27 42 17 7F DF
 40 D8 45 31 81 CD E1 63 0B 2B C4 3B 62 92 6D F0
 73 67 A9 54 BA 02 88 6C 9B 59 7C CF AA B5 85 CB
 97 0C 7A D3 16 56 ED 74 B1 93 98 FE 28 34 21 AF
 5B B6 61 96 72 20 30 39 52 83 07 EB 3D D6 60 71
 BF 00 87 68 03 19 37 0A 84 50 22 2F 78 A5 DB 26


 Involution : Yes

raw:
 E7 9D EB 21 D1 BD 32 98 C6 0C F9 67 29 B3 D4 A6
 42 2A 6C 23 33 59 1A AA 2D FD B5 84 E3 4E A8 3E

encoded:
 39 58 EB DE 0C 92 53 DA 88 D1 50 C1 9C 31 16 82
 AC 76 C7 90 7D C9 8E CC 7B A5 CD F8 96 8C A8 8D

decoded:
 E7 9D EB 21 D1 BD 32 98 C6 0C F9 67 29 B3 D4 A6
 42 2A 6C 23 33 59 1A AA 2D FD B5 84 E3 4E A8 3E

This isn’t encryption of course and shouldn’t be used for protecting data. It’s just another involution and nothing more. And because the function accepts a key, it appears random enough to be sufficient for simple masking.