© Marius Iulian Mihailescu and Stefania Loredana Nita 2021
M. I. Mihailescu, S. L. NitaPro Cryptography and Cryptanalysis https://doi.org/10.1007/978-1-4842-6367-9_21

21. Integral Cryptanalysis

Marius Iulian Mihailescu1   and Stefania Loredana Nita1
(1)
Bucharest, Romania
 

Integral cryptanalysis represents a particular cryptanalytic attack that is applicable to the block ciphers that are built based substitution-permutation networks. The attack was designed by Lars Knudsen as a dedicated attack against Square [1], leading it to be known as the Square attack.

The substitution-permutation networks represent one of the most important vulnerable points of block ciphers. Once the networks can be found (let’s say intuitively) then the attack on the block cipher can devastatingly corrupt the entire cryptosystem. The next vulnerable points are the key and the table used to permutate the key. Once the key is close to the real one or identical, then we are close to cracking the cryptosystem. An example of such a key is
        private byte[]PermutationTableForKey = {
            06, 30, 13, 07, 05, 35, 15, 14,
            12, 18, 03, 38, 09, 10, 22, 25,
            16, 04, 21, 08, 39, 37, 36, 02,
            24, 11, 28, 27, 29, 23, 33, 01,
            32, 17, 31, 00, 26, 34, 20, 19
        };

In the following pages, we will go through the necessary elements required to implement a block cipher and identify the elements that are necessary to focus on in order to launch an integral cryptanalysis attack, such as building Feistel networks (see Listing 22-2) and generating a permutation table for a cryptographic key (Listing 22-4). Once there is a clear understanding of these two phases, it will become very clear how an integral cryptanalysis has to be conducted.

Basic Notions

In order to implement and design an integral cryptanalytic attack, it is very important to understand the fundamental notions first. So let’s consider the following notions as the main starting point. Based on that foundation we will design and implement such an attack for education purposes only.

Let’s consider (G, +) to be a finite abelian group or order k. The following product group, Gn = G × … × G, is the group with elements of the form v = (v1, …, vn), where vi ∈ G. The addition within Gn is defined as component-wise. So now we have u + v = w holds for u, v, w ∈ Gn when ui + vi = wi for all i.

We note with B the multiset of vectors. The integral that is defined over B represents the sum of all vectors, S. In other words, the integral is defined as $$ int S=sum limits_{vin B}v $$, the summation operation being defined in terms of the group operation for Gn.

When designing an integral cryptanalytic attack, it is very important to know and to figure out the number of words in the plaintext and ciphertext. For our example, this number will be denoted with n. Another number that is very important to be aware of is the number of plaintexts and ciphertexts, denoted with m. Usually, m = k (i.e. k = |G|), the vectors v ∈ B representing the plaintext and ciphertexts, and G = GF(2B) or G = Z/kZ.

Moving forward to the attack, one of the parties will try to predict the values situated in the integrals after a specific number of encryption rounds. Based on this purpose, it is beneficial to make the difference between three cases: (1) where all the words are equal (e.g. i), (2) all words are different, and (3) sum to a certain value that is predicted in advance.

Let’s consider B ⊆ Gn be declared as before and an fixed index i. The following three cases take place:
  1. (1)

    vi = c, for all v ∈ B

     
  2. (2)

    {vi : v ∈ B} = G

     
  3. (3)

    $$ sum limits_{vin B}{v}_i={c}^{prime } $$

     

where c, c′ ∈ G are some values known and fixed in advance.

The following example represents a typical case in which m = k, the number of vectors that are found within B equals the number of elements in the considered group. By using Lagrange’s theorem, we can see if all words, ith, are equal, and then it is quite clear that ith word from the integral will take the value of the neutral element from G.

The following two theorems are necessary and represent a must for any practical developer who wants to translate into practice an integral cryptanalysis.

Theorem 21-1 [1, Theorem 1, p. 114]. Let’s consider (G, +) a finite abelian additive group. The subgroup of elements of order 1 or 2 is denoted as L = {g ∈ G : g + g = 0}. We consider writing s(G) as being the sum $$ sum limits_{gin G}g $$ of all the elements found within G. Next, we consider s(G) = ∑h ∈ HH. More, it is very important to understand the following analogy: s(G) ∈ H, i.e. s(G) + s(G) = 0.

This being said, for G = GF(2B) we have s(G) = 0 and for Z/mZ we obtain s(Z/mZ) = m/2 when m is found in the case of being even or 0. We have also the multiplicative case for written groups (see Theorem 21-2).

Thereom 21-2 [1, Theorem 2, p. 114]. Let’s consider (G, ∗) a finite abelian multiplicative group. The subgroup of elements of order 1 or 2 is denoted as H = {g ∈ G : g ∗ g = 1}. We consider writing p(G) as being the product $$ prod limits_{gin G }g $$ of all the elements of G. Next, we consider $$ p(G)=prod limits_{hin H}h $$. More, it is very important to understand the following analogy: p(G) ∈ H, i.e. p(G) ∗ p(G) = 1.

As an example, if we have G = (Z/pZ)∗ where p is prime, p(G) is −1, p(G) =  − 1. This is proved using Wilson’s theorem.

Practical Approach

The section will show how an integral cryptanalysis attack can be put into practice using the .NET Framework and the C# programming language. The following approach represents a basic implementation of a Feistel network in C# with the possibility to override the current block size. We will use repeating sequences with the purpose of creating a weakness to show how it can be exploited and create the attack.

Listing 21-1 shows how the integral cryptanalytic attack can be built and designed. Listing 21-2 shows how the Feistel network is built. Once we have structure, to have success with the attack, it is important to “figure out” how the Feistel network is built and to create a replica of it or at least something that is similar to the original one. Listing 21-3 shows how to implement the block data and Listing 21-4 shows how to generate the keys.
using System;
using System.IO;
namespace BuildingIntegralCryptanalysis
{
    class Program
    {
        static void Main(string[] args)
        {
            string theKeyword = "", data_input = "",
                   data_output = "", data_file = "";
            FeistelNetwork feist_network;
            StreamReader file_stream_reader;
            StreamWriter file_stream_writer;
            //** create a help text for the user
            const string helperData =
            @"Building Integral Cryptanalysis Attack
              Usage:
               private [-option] keyword
                         input_file output_file
                          Options:
                             -enc Encrypt the file passed as
                                          input using the keyword
                             -dec Decrypt the file passed as
                                          input using the keyword";
            //** show in the console the helper
            //** if we have less than four arguments
            if(args.Length < 4)
            {
                Console.WriteLine(helperData);
                return;
            }
            else if(args[1].Length < 10 ||
                                              args[1].Length > 40)
            {
                 //** Output usage if the password
                 //** is too short/long
                 Console.Write("The length of the password is
                 invalid. The password should have between 10-40 characters. " + helperData);
                 return;
            }
            theKeyword = args[1];
            data_input   = args[2];
            data_output  = args[3];
            //** environment input/output configuration
            feist_network = new FeistelNetwork(theKeyword);
            file_stream_reader = new StreamReader(data_input);
            file_stream_writer = new
                                     StreamWriter(data_output);
            //** Read the data from the input file
            data_file = file_stream_reader.ReadToEnd();
            file_stream_reader.Close();
            if (args[0] == "-enc")
            {
                //** do the encryption based
                //** on the argument provided
                string ciphertext =
                                   feist_network.EncryptionOp(data_file);
                file_stream_writer.Write(ciphertext);
                Console.WriteLine("The file has been encrypted
                        with success. The file has been saved
                                               to: " + data_output);
            }
            else if(args[0] == "-dec")
            {
                //** do the decryption based on the argument
                string thePlaintext =
                                   feist_network.DecryptionOp(data_file);
                file_stream_writer.Write(thePlaintext);
                Console.WriteLine("The file has been decrypted
                             with success. The file has been saved
                             to: " + data_output);
            }
            else
            {
                //** invalid option selected
                Console.Write("The selected option is invalid.
                               Please, choose another option. "
                               + helperData);
            }
            file_stream_writer.Close();
            Console.ReadKey();
        }
    }
}
Listing 21-1

The Main Program

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace IntegralCryptanalysis
{
    public class FeistelNetwork
    {
        //** represents the size in bytes
        //** for each of the block
        public int BlockSize
        {
            get;
            private set;
        }
        //** the password code for
        //** encryption and decryption
        public string PasswordCode
        {
            get;
            set;
        }
        /// <summary>
        /// The basic constructor of Feistel Class.
        /// </summary>
        /// <param name="password_code">represents the
        /// password code</param>
        public FeistelNetwork(string password_code)
        {
            this.PasswordCode = password_code;
            this.BlockSize = 16;
        }
        /// <summary>
        /// Constructs a new instance of the Feist class, with a custom blocksize
        /// </summary>
        /// <param name="password_code">Passcode used in this instance</param>
        /// <param name="the_block_size">Size of the blocks to use in this instance</param>
        public FeistelNetwork(string password_code, int the_block_size) : this(password_code)
        {
            this.BlockSize = the_block_size;
        }
        /// <summary>
        /// Encryption operation of the clear text using the password code
        /// </summary>
        /// <param name="clearText">The string to encrypt</param>
        /// <returns>The encrypted text.</returns>
        public string EncryptionOp(string clearText)
        {
            return DoCiphering(clearText, true);
        }
        /// <summary>
        /// Decryption operation of the encrypted text using the password code
        /// </summary>
        /// <param name="clearText">The string to decrypt</param>
        /// <returns>The decrypted text.</returns>
        public string DecryptionOp(string clearText)
        {
            return DoCiphering(clearText, false);
        }
        /// <summary>
        /// Do a Feistel encryption on the text
        /// </summary>
        /// <param name="sourceText">The clear text or encrypted text to encrypt/decrypt</param>
        /// <param name="isClearText">Decide if the given text represents (true) or not (false) a plaintext string</param>
        /// <returns>A string of plain or ciphered
        /// text</returns>
        private string DoCiphering(string sourceText, bool isClearText)
        {
            int pointer_block = 0;
            string cipher_text_posting = "";
            List<ulong> the_round_keys = new Key(PasswordCode).ReturnRoundKeys();
            //** Do a padding operation to
            //** the string using ''.
            //** The output will
            //** be a multiple of <blocksize>
            while (sourceText.Length % BlockSize != 0)
                sourceText += new char();
            //** in case of decryption, reverse
            //** the encryption keys
            if (!isClearText)
                the_round_keys.Reverse();
            byte[] the_text_bytes = Encoding.UTF8.GetBytes(sourceText);
            //** do iteration through the text
            //** moving with <blocksize> bytes per iteration
            while (pointer_block < the_text_bytes.Length)
            {
                byte[] the_block_as_bytes = new byte[BlockSize];
                Array.Copy(the_text_bytes, pointer_block, the_block_as_bytes, 0, BlockSize);
                Block text_as_block = new Block(the_block_as_bytes);
                //** if we have a ciphertext,
                //** swap it in halves
                if (!isClearText)
                    text_as_block.SwapHalfes();
                //** each round keys will be
                //** applied to the text
                foreach (ulong the_round_key in the_round_keys)
                    text_as_block = RoundOnTheBlock(text_as_block, the_round_key);
                //** build the output by appending it
                if (!isClearText) text_as_block.SwapHalfes();
                cipher_text_posting += text_as_block.ToString();
                pointer_block += BlockSize;
            }
            return cipher_text_posting.Trim('');
        }
        /// <summary>
        /// Do a single round encryption on the block
        /// </summary>
        /// <param name="theBlock">The block that will be encrypted or decrypted</param>
        /// <param name="theRoundKey">The round key which will be applied as the round function</param>
        /// <returns>The next block in the round sequence</returns>
        private Block RoundOnTheBlock(Block block, ulong theRoundKey)
        {
            ulong theRoundFunction = 0;
            Block roundBlock = new Block(block.BlockSize);
            BitArray keyBits = new BitArray(BitConverter.GetBytes(theRoundKey)), funcBits = block.RightBitsOfBlock.Xor(keyBits);
            roundBlock.LeftHalf = block.RightHalf;
            //** do the proper casting AND round
            //** the function bits to an int
            //** set R(i+1) as L(i) XOR f
            theRoundFunction = ToInteger64(funcBits);
            roundBlock.RightHalf = BitConverter.GetBytes(ToInteger64(block.TheLeftBitsOfBlock) ^ theRoundFunction);
            return roundBlock;
        }
        /// <summary>
        /// Helper method used for conversion of BitArray to have an integer representation
        /// </summary>
        /// <param name="theArray">BitArray that will be converted</param>
        /// <returns>A value of 64-bit integer of the array</returns>
        private ulong ToInteger64(BitArray theArray)
        {
            byte[] array_as_byte = new byte[8];
            theArray.CopyTo(array_as_byte, 0);
            return BitConverter.ToUInt64(array_as_byte, 0);
        }
    }
}
Listing 21-2

Building the Feistel Network

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace IntegralCryptanalysis
{
    public class Block
    {
        /// <summary>
        /// Represents the data that are held by the block
        /// </summary>
        public byte[] DataStructure { get; set; }
        /// <summary>
        /// Represents the left half of the data block
        /// </summary>
        public byte[] LeftHalf
        {
            get
            {
                return DataStructure.Take(DataStructure.Length / 2).ToArray();
            }
            set
            {
                Array.Copy(value, DataStructure, DataStructure.Length / 2);
            }
        }
        /// <summary>
        /// Represents the right half of the data block
        /// </summary>
        public byte[] RightHalf
        {
            get
            {
                return DataStructure.Skip(DataStructure.Length / 2).ToArray();
            }
            set
            {
                Array.Copy(value, 0, DataStructure, DataStructure.Length / 2, DataStructure.Length / 2);
            }
        }
        /// <summary>
        /// Get and return as BitArray the left half of the block data
        /// </summary>
        public BitArray TheLeftBitsOfBlock
        {
            get
            {
                return new BitArray(LeftHalf);
            }
        }
        /// <summary>
        /// Get and return as BitArray the right half of the block data
        /// </summary>
        public BitArray RightBitsOfBlock
        {
            get
            {
                return new BitArray(RightHalf);
            }
        }
        /// <summary>
        /// Representation of the size in bytes of the Block
        /// </summary>
        public int BlockSize
        {
            get
            {
                return DataStructure.Length;
            }
        }
        /// <summary>
        /// The representation of a data block. Constructor
        /// </summary>
        /// <param name="size_of_the_block">The size value (in bytes) of the block</param>
        public Block(int size_of_the_block)
        {
            DataStructure = new byte[size_of_the_block];
        }
        /// <summary>
        /// The representation of a data block. Constructor
        /// </summary>
        /// <param name="the_data_block">the data content stored by the block</param>
        public Block(byte[] the_data_block)
        {
            DataStructure = the_data_block;
        }
        /// <summary>
        /// Swaps the halves (left and right) of the block
        /// </summary>
        public void SwapHalfes()
        {
            byte[] temporary = LeftHalf;
            LeftHalf = RightHalf;
            RightHalf = temporary;
        }
        /// <summary>
        /// Converts the Block to a UTF-8 string
        /// </summary>
        /// <returns>String representation of this block</returns>
        public override string ToString()
        {
            return System.Text.Encoding.UTF8.GetString(DataStructure);
        }
    }
}
Listing 21-3

Implementing the Block Data

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace IntegralCryptanalysis
{
    public class Key
    {
        //** permutation table (initial)
        //** used to permutate the key
        private byte[] initial_permutation_table_1 = {
            06, 30, 13, 07, 05, 35, 15, 14,
            12, 18, 03, 38, 09, 10, 22, 25,
            16, 04, 21, 08, 39, 37, 36, 02,
            24, 11, 28, 27, 29, 23, 33, 01,
            32, 17, 31, 00, 26, 34, 20, 19
        };
        /// <summary>
        /// The representation of the key as a byte array
        /// </summary>
        public byte[] KeyBytes
        {
            get; set;
        }
        /// <summary>
        /// Encryption and decryption key for a text
        /// </summary>
        /// <param name="keyAsAString">The key to use for this instance</param>
        public Key(string keyAsAString)
        {
            int k = 0, key_length = keyAsAString.Length;
            //** expansion of the key to a maximum of 40 bytes
            while (keyAsAString.Length < 40)
                keyAsAString += keyAsAString[k++];
            KeyBytes = System.Text.Encoding.UTF8.GetBytes(keyAsAString);
            //** permutation of the key bytes using
            //** initial_permutation_table_1
            for (k = 0; k < KeyBytes.Length; k++)
                KeyBytes[k] = KeyBytes[initial_permutation_table_1[k]];
            Debug.WriteLine("The post permutation key is: "+ System.Text.Encoding.UTF8.GetString(KeyBytes));
        }
        /// <summary>
        /// Generate the keys that are used within the round function
        /// </summary>
        /// <returns>A list with the keys that are of 64-bit. The format is ulong.</returns>
        public List<ulong> ReturnRoundKeys()
        {
            //** Rounds is defined as 64-bit
            //** keys found in the Key string
            int count_of_round = KeyBytes.Length / 8;
            List<ulong> round_keys = new List<ulong>();
            for (int k = 0; k < count_of_round; k++)
            {
                byte[] round_key_bytes = new byte[8];
                ulong round_key = 0;
                Array.Copy(KeyBytes, k * 8, round_key_bytes, 0, 8);
                Array.Reverse(round_key_bytes);
                round_key = BitConverter.ToUInt64(round_key_bytes, 0);
                round_keys.Add(round_key);
            }
            return round_keys;
        }
    }
}
Listing 21-4

The Key Class

Conclusion

In this chapter, we discussed integral cryptanalysis and how such attack can be designed and implemented. We presented a way of building a block cipher cryptosystem together with the vulnerable points in order to show how to apply an integral cryptanalysis attack.

At the end of this chapter, you can now

  • Design and implement a simple block cipher

  • Understand the two vulnerable points of such ciphers, such as Feistel networks and generating the permutation tables to permutate the key

  • Understand how a Feistel network is implemented

  • Use permutation tables and work with them over the keys

Bibliography

  1. [1]

    Joan Daemen, Lars Knudsen, and Vincent Rijmen, “The Block Cipher Square. Fast Software Encryption (FSE) 1997,” Volume 1267 of Lecture Notes in Computer Science (pp. 149–165). Haifa, Israel: Springer-Verlag. CiteSeerX 10.1.1.55.6109. 1997.

     
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.222.20.101