A deep dive into Computer Cryptography

Cryptography

The science of Secret writing with the goal of hiding the message.

Crypto-analysis

The art of breaking crypto systems.

Branches of Cryptography

Symmetric Algorithms

All parties have a encryption or decryption method for which they share a secret key.Used for data encryption and integrity check messages.

Problem with symmetric key cryptography is that both parties need to share the key with each other before they begin the communication which ultimately poses the threat of leakage of key to some other party.

• Encryption equation y = eK(x)
• Decryption equation x = dK(y)

Asymmetric (or Public key) Algorithms

A user posses a secret key (same a symmetric) but the difference is that there is a public key as well.Used in Digital signatures and key establishment and also for classical data encryption. Asymmetric cryptography contains a pair of key (public key and private key).Each user has its own public(shared with others) and private keys.Public key is shared with everyone while the private key is kept secret.A message encrypted by other persons public key can only be decrypted by their private key.So whenever we want to send a message first we encrypt it with other persons public key and then sign it with our own private key; This way the person will be able to decrypt the message with his private key and will also be able to know that the message was infact sent by me as it is also signed by my private key.

All encryption schemes before 1976 are symmetric ones.Majority of today protocols are hybrid using symmetric ciphers for encryption and message authentication and asymmetric ciphers for key exchange and digital signature

Cryptanalysis : Attacking Cryptosystems

title:Kerckhoff's Principle
A Cryptosystem should be secure even if the attacker knows all the details of the system with the exception of key.

Kerckhoffs’ Principle is counterintuitive! It is extremely tempt- ing to design a system which appears to be more secure because we keep the details hidden. This is called security by obscurity.

Classical Attacks

Mathematical Attacks

Brute-Force Attacks

• Requires at least 1 plaintext-ciphertext pair.
• Checks all possible combinations until the key is found.Substitution Attack
• Historical Cipher
• Encrypts letters rather than numbers
• Plain text is replaced by cipher letters.

Plain text to Cipher text

A->k
B->d
C->w

so ABBA -> kddk

Possible Attacks Against Substitution Cipher :

• Exhaustive key search : Try every possible substitution until a intelligent text appears.
• Frequency Analysis Attack : Checking frequency of different letters in the cipher and deducing the key.

Modular Arithmetic

Most of the cryptosystems are based on sets of a number that are

• Discrete (sets with integers are particularly useful)
• finite

Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (i.e., if there is an integer k such that a − b = kn).

Properties of congruence

1. a≡b(mod m) iff m/a-b

Where a and b are integers.

1. a=q.m+r
2. a≡b(mod m) implies b≡a(mod m)
3. if a≡b(mod m) and b≡c(mod m) then a≡c(mod m)

To find the mode of a negative number -x mod y = y -(x mod y) : but this formula can only be used if |x| mod y != 0

Stream Ciphers

There are two types of symmetric ciphers — Stream Cipher : Encrypts bits individually — Block Cipher : Encrypts a block of bits

Examples

• AES is an example of Block Cipher which is being used to encrypt internet communication.
• Stream Cipher is being used in mobile GSM voice communication encryption.
• AES and DES are highly optimized to work efficiently with modern apps.

Stream cipher

Encryption

Encryption in Stream Cipher is done by adding each bit with text+key (mod 2). it is worth having a closer look at addition modulo 2. If we do arithmetic modulo 2, the only possible values are 0 and 1 (because if you divide by 2, the only possible remainders are 0 and 1). Thus, we can treat arithmetic modulo 2 as Boolean functions such as AND gates, OR gates, NAND gates, etc.

Mod 2 is equivalent of XOR operation

So far, stream ciphers look unbelievably easy: One simply takes the plaintext, performs an XOR operation with the key and obtains the ciphertext.

Random Number Generators

RNGs play an important role in stream ciphers. There are three types of random number generator

True Random Number generator(TRNG)

• The our of TRNGs cannot be reproduced.For example if we flip a coin hundred times and then try to again output the same result.Other example include rolling of dice,radio active decay etc.
• TRNGs are used for generating session keys.

(General) Pseudorandom Number Generator (PRNG)

• PRNG has a starting state called seed state
• Many numbers are generated which can be reproduced if the starting point is known
• The numbers are predictable but efficient
• They make the use of already developed algorithm to produce random numbers.

s0 = 12345  # this is the initial seed state
si+1 = 012023492si+12345 mod 2E31
So,
s0 = seed
si+1 = ASi+B mod m

We generate the next random integer using the previous random integer, the integer constants, and the integer modulus. To get started, the algorithm requires an initial Seed, which must be provided by some means. The appearance of randomness is provided by performing modulo arithmetic.. PRNGs are suitable for applications where many random numbers are required and where it is useful that the same sequence can be replayed easily.

Cryptographically Secure Pseudorandom Number Generator (CSPRNG)

• They are a special type of PRNGs
• They posses unpredictability unlike PRNGs.

The One Time Pad

title: Unconditional Security
A cryptosystem is unconditionally or information-theoretically se-
cure if it cannot be broken even with infinite computational re-
sources.

Unconditional security simply assumes that the attacker has unlimited power and resources to break the cipher but despite that if cipher does not get broken then it has achieved unconditional security.

In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is no smaller than the message being sent. In this technique, a plaintext is paired with a random secret key (also referred to as a one-time pad). Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition.

The resulting ciphertext will be impossible to decrypt or break if the following four conditions are met:

• The key must be random (uniformly distributed and independent of the plaintext).
• The key must be at least as long as the plaintext.
• The key must never be reused in whole or in part.
• The key must be kept completely secret by the communicating parties.
• This implies that we need one key bit for every bit of plaintext.

Linear Feedback Shift Registers

• LFSR contain clock storage element called flip flops and a feedback path.
• The number of flip flops gives us the degree of LFSR which means that m flip flops mean the degree of LFSR is m.

In XOR operation if the bits are same the result is 0 otherwise its 1.

Data Encryption Standard

Data Encryption Standard is a Block Cipher. DES is no longer considered secure as it has a very small key space.In order to have a strong encryption algorithm it must have the following properties

• Confusion : is an encryption operation where the relationship between the key and the cipher text is obscured.
• Diffusion : means an operation where influence of one plain text symbol is spread over many cipher text symbols with the goal of hiding statistical properties of of a plain text.

If we change one bit of plain text half of the cipher text will change in most modern encryption algorithms confirming the diffusion property.if we apply confusion and diffusion many times over and over again we get a product cipher.

Plain DES is no longer being used but 3DES (pronounced as triple DES) is being used where we apply encryption 3 times DES. DES was broken by exhaustive search attack. DES had banking applications. 3DES actually got retired recently in 2018.

Overview of DES algorithm

DES uses a 56 bit key to encrypt a block of 64 bit or 8 bytes at a time. DES is built around a core idea called Feistel Network. n fact many of today cipher are based on a feistel network.

DES is based on 16 round feistel network

Working of Feistel Network

• After the initial permutation the 64 bit input is divided in 32 bit L0 and R0 separate input.
• The R0 or right hand side goes to the L1 as it is without any change.
• R0 is also used in the function (f) whose output is XOR with the input of L0.
• The result becomes R1.
• So only one 32 bit gets encrypted i.e. the L0.
• Note that values are being swapped for the next round.

Function involved in DES

• first a 32 bit plain text p1 is taken as input.
• Then an expansion is performed and it is turned into 48 bit.
• Now those 48 bits get XOR with a 48 bit key.
• The result is converted into 8 groups of 6 bits.
• These groups go into s-boxes which map these 6 bits to 4 bits using a lookup table giving us a total result of 32 bits.
• At last permutation is performed and final 32 bit output is given