NS ASSIGNMENT 1

Submitted by: Bhoomika Jethwani, 16070122009

Q1. Explain AES algorithm in detail.

AES is an iterative rather than Feistel cipher. It is based on ‘substitution–
permutation network’. It comprises of a series of linked operations, some of
which involve replacing inputs by specific outputs (substitutions) and others
involve shuffling bits around (permutations).
Interestingly, AES performs all its computations on bytes rather than bits.
Hence, AES treats the 128 bits of a plaintext block as 16 bytes. These 16 bytes
are arranged in four columns and four rows for processing as a matrix −
Unlike DES, the number of rounds in AES is variable and depends on the length
of the key. AES uses 10 rounds for 128-bit keys, 12 rounds for 192-bit keys and
14 rounds for 256-bit keys. Each of these rounds uses a different 128-bit round
key, which is calculated from the original AES key.
The schematic of AES structure is given in the following illustration −
Encryption Process
Here, we restrict to description of a typical round of AES encryption. Each
round comprise of four sub-processes. The first round process is depicted below
−

Byte Substitution (SubBytes)

The 16 input bytes are substituted by looking up a fixed table (S-box) given in
design. The result is in a matrix of four rows and four columns.

Shiftrows
Each of the four rows of the matrix is shifted to the left. Any entries that ‘fall
off’ are re-inserted on the right side of row. Shift is carried out as follows −
• First row is not shifted.
• Second row is shifted one (byte) position to the left.
• Third row is shifted two positions to the left.
• Fourth row is shifted three positions to the left.
• The result is a new matrix consisting of the same 16 bytes but shifted with
respect to each other.

MixColumns
Each column of four bytes is now transformed using a special mathematical
function. This function takes as input the four bytes of one column and outputs
four completely new bytes, which replace the original column. The result is
another new matrix consisting of 16 new bytes. It should be noted that this step
is not performed in the last round.

Addroundkey
The 16 bytes of the matrix are now considered as 128 bits and are XORed to the
128 bits of the round key. If this is the last round then the output is the cipher
text. Otherwise, the resulting 128 bits are interpreted as 16 bytes and we begin
another similar round.
Decryption Process
The process of decryption of an AES ciphertext is similar to the encryption
process in the reverse order. Each round consists of the four processes
conducted in the reverse order −
• Add round key
• Mix columns
• Shift rows
• Byte substitution
Since sub-processes in each round are in reverse manner, unlike for a Feistel
Cipher, the encryption and decryption algorithms needs to be separately
implemented, although they are very closely related.

THE ENCRYPTION KEY AND ITS EXPANSION

• Assuming a 128-bit key, the key is also arranged in the form of an array of 4 ×
4 bytes. As with the input block, the first word from the key fills the first
column of the array, and so on.

• The four column words of the key array are expanded into a schedule of 44
words. (As to how exactly this is done, we will explain that later in Section 8.8.)
Each round consumes four words from the key schedule.

• The following figure depicts the arrangement of the encryption key in the form
of 4-byte words and the expansion of the key into a key schedule consisting of
44 4-byte words. Of these, the first four words are used for adding to the input
state array before any round-based processing can begin, and the remaining 40
words used for the ten rounds of processing that are required for the case a 128-
bit encryption key.

k 0 k 4 k 8 k 12
k 1 k 5 k 9 k 13
k 2 k 6 k 10 k 14
k 3 k 7 k 11 k 15
w 0 w 1 w 2 w 3 w 4 w 5 w 42 w 43

This figure shows the four words of the original 128-bit key being expanded
into a key schedule consisting of 44 words. Section 8.8 explains the procedure
used for this key expansion.
Overall AES Structure
THE FOUR STEPS IN EACH ROUND OF PROCESSING

STEP 1: (called SubBytes for byte-by-byte substitution during the forward

process) (The corresponding substitution step used during decryption is called
InvSubBytes.)

 This step consists of using a 16 × 16 lookup table to find a replacement

byte for a given byte in the input state array.

 The entries in the lookup table are created by using the notions of
multiplicative inverses in GF (2^8) and bit scrambling to destroy the bit-
level correlations inside each byte.

STEP 2: (called ShiftRows for shifting the rows of the state array during the
forward process) (The corresponding transformation

One round of encryption is shown at left and one round of decryption at

right

during decryption is denoted InvShiftRows for Inverse Shift- Row

Transformation.)

• The goal of this transformation is to scramble the byte order inside each
128-bit block.

This step is explained in greater detail in Section 8.6.

STEP 3: (called MixColumns for mixing up of the bytes in each column
separately during the forward process) (The correspond- ing transformation
during decryption is denoted InvMixColumns and stands for inverse mix
column transformation.) The goal is here is to further scramble up the 128-bit
input block.

 The shift-rows step along with the mix-column step causes each bit
of the ciphertext to depend on every bit of the plain- text after 10
rounds of processing.
 Recall the avalanche effect from our discussion on DES in Lecture
3. In DES, one bit of plaintext affected roughly 31 bits of
ciphertext. But now we want each bit of the plaintext to affect
every bit position of the ciphertext block of 128 bits.

STEP 4: (called AddRoundKey for adding the round key to the output of the
previous step during the forward process) (The cor- responding step during
decryption is denoted InvAddRound- Key for inverse add round key
transformation.)

AES Analysis

In present day cryptography, AES is widely adopted and supported in both

hardware and software. Till date, no practical cryptanalytic attacks against AES
has been discovered. Additionally, AES has built-in flexibility of key length,
which allows a degree of ‘future-proofing’ against progress in the ability to
perform exhaustive key searches.
However, just as for DES, the AES security is assured only if it is correctly
implemented and good key management is employed.
Q2. Explain Birthday Paradox Problem.
The birthday attack is a statistical phenomenon relevant to information security
that makes the brute forcing of one-way hashes easier. It’s based off of the
birthday paradox, which states that in order for there to be a 50% chance that
someone in a given room shares your birthday, you need 253 people in the
room.
If, however, you are looking for a greater than 50% chance that any two people
in the room have the same birthday, you only need 23 people.
This works because the matches are based on pairs. If I choose myself as one
side of the pair, then I need a full 253 people to get to the magic number of 253
pairs. In other words, it’s me combined with 253 other people to make up all
253 sets.
But if I am only concerned with matches and not necessarily someone matching
me, then we only need 23 people in the room. Why? Because it only takes 23
people to form 253 pairs when cross-matched with each other.
So the number 253 doesn’t change. That’s still the number of pairs required to
reach a 50% chance of a birthday match within the room. The only question is
whether each person is able to link with every other person. If so you only need
23 people; if not, and you’re comparing only to a single birthday, you need 253
people.
This applies to finding collisions in hashing algorithms because it’s much
harder to find something that collides with a given hash than it is to find any
two inputs that hash to the same value.
Birthday paradox problem –
Let us consider the example of a classroom of 30 students and a teacher. The
teacher wishes to find pairs of students that have the same birthday. Hence the
teacher asks for everyone’s birthday to find such pairs. Intuitively this value
may seem small. For example, if the teacher fixes a particular date say October
10, then the probability that at least one student is born on that day is 1 –
(364/365)30 which is about 7.9%. However, the probability that at least one
student have same birthday as any other student is around 70% using the
following formula:
1 - 365!/((365 - n!) * (365n)) (substituting n = 70 here)

Derivation of the above term:

Assumptions –
1. Assuming a non leap year(hence 365 days).
2. Assuming that a person has equally likely chance of being born on any day of
the year.
Let us consider n = 2.
P(Two people have the same birthday) = 1 – P(Two people having different
birthday)
= 1 – (365*365)*(364*365)
= 1 – 1*(364/365)
= 1 – 364/365
= 1/365.
So for n people the probability that all of them have different birthday is:
P(N people having different birthdays) = (365/365)*(365-1/365)*(365-
2/365)*….(365-n+1)/365.
= 365!/((365-n)! * 365n)
Hash function –
A hash function H is a transformation that takes a variable sized input m and
returns a fixed size string called as hash value(h = H(m)). Hash functions
chosen in cryptography must satisfy the following requirements:
 The input is of variable length,
 The output has a fixed length,
 H(x) is relatively easy to compute for any given x,
 H(x) is one-way,
 H(x) is collision-free.
A hash function H is said to be one-way if it is hard to invert, where “hard to
invert” means that given a hash value h, it is computationally infeasible to find
some input x such that H(x) = h.
If, given a message x, it is computationally infeasible to find a message y not
equal to x such that H(x) = H(y) then H is said to be a weakly collision-free
hash function.
A strongly collision-free hash function H is one for which it is computationally
infeasible to find any two messages x and y such that H(x) = H(y).
Let H: M => {0, 1}n be a hash function (|M| >> 2n )
Following is a generic algorithm to find a collision in time O(2n/2) hashes.
Algorithm:
1. Choose 2n/2 random messages in M: m1, m2, …., mn/2
2. For i = 1, 2, …, 2n/2 compute ti = H(mi) => {0, 1} n
3. Look for a collision (ti = tj). If not found, go back to step 1
We consider the following experiment. From a set of H values, we choose n
values uniformly at random thereby allowing repetitions. Let p(n; H) be the
probability that during this experiment at least one value is chosen more than
once. This probability can be approximated as:
P (n; H) = 1 - ( (365-1)/365) * (365-2)/365) * ...(365-n+1/365))
P (n; H) = e-n(n-1)/(2H) = e-n2/(2H)

Digital signature susceptibility –

Digital signatures can be susceptible to birthday attack. A message m is
typically signed by first computing H(m), where H is cryptographic hash
function, and then using some secret key to sign H(m). Suppose Alice want to
trick Bob into signing a fraudulent contract. Alice prepare a fair contract m and
fraudulent one m’. She then finds a number of positions where m can be
changed without changing the meaning, such as inserting commas, empty lines,
one versus two spaces after a sentence, replacing synonyms etc. By combining
these changes she can create a huge number of variations on m which are all fair
contracts.
Similarly, Alice can also make some of these changes on m’ to take it even
more closer towards m, that is H(m) = H(m’). Hence, Alice can now present the
fair version m to Bob for signing. After Bob has signed, Alice takes the
signature and attaches to it the fraudulent contract. This signature proves that
Bob has signed the fraudulent contract.
To avoid such an attack the output of hash function should be a very long
sequence of bits such that birthday attack now becomes computationally
infeasible.