‹

COM-401: Cryptography and Security

Tags:

"A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine." - Alan Turing

This compendium is made for the course COM-401 Cryptography and Security at École Polyteqnique Fédérale de Lausanne (EPFL) and is a summary of the lectures and lecture notes. Is is not the complete curriculum, but rather a list of reading material.

Ancient Cryptography

Terminology

Confidentiality	Only receiver shall receive message
Authentication	Only sender can send the message
Integrity	Message shall not change

Cryptography Prehistory

Transposition

Transposition moves the characters around, but all the characters are still in place.

Scylates is a cylider with a belt wrapped around. Only cylinder of same circumference can decrypt message.

Simple substitution

Substitute each letter in the alphabet by another letter. $ 26! \approx 2^{88} $ different permutations, i.e. a 88 bit key. Example of this is the Ceasar cipher that is a shift in the alphabet by two positions.

Simple substitution can easily be broken by statistical analysis, i.e. frequency analysis, digrams, trigrams, etc..

Vignère cipher

Is configured by a key. Algorithm can be known. Add more info

Can be broken by guessing key lenght and doing statistical analysis on each column.

Kasinsky: Frequent patterns is not random. Can guess key lenght out of this.

Index of coincidence: Can guess key lenght and test with index of coincidence. This will reveal key length since natural languace does not have the same IoC as random text.

Pre-Modern Industrial Cryptography

Enigma

Kerckhoffs principle

Do not make security dependent on the secrecy of its design. Instead, use an easy to select secret key.

Cryptography and Information Theory

Vernam cipher:

$ (x_1, ... , x_n) \oplus (y_1, ... , y_n) = (x_1 \oplus y_1, ... , x_n \oplus y_n) $
$ a \oplus b = (a + b)\bmod 2 $ for $a, b \in {0, 1} $

Do not encrypt two times with same key!

Diffie-Hellman Cryptography

Artihmetics and Zn

For all $a \in \mathbb{Z}$ and $n \gt 0$, there exists a unique way to write $ a = qn + r$ with $q;r \in \mathbb{Z}$ and $ 0 \leq r \le n$.
$ a \boxplus b = (a + b) mod n$ and $ a \boxtimes b = (a \cdot b) mod n$

Groups: Theory, Algorithms and Diffie-Hellman Key Exchange

Group definition

A group is a set with a dyadic operation + such that:

The set is closed under the operation: for all $a$ and $b$ in $G$, we have $a + b \in G$
The operation is assiciative: for all $a;b;c \in G$, we have $(a + b) + c = a + (b + c)$
There exists a neutral element 0: for all $a \in G$, we have $a + 0 = 0 + a = a$
Every set element has an inverse: for all $a \in G$, there exits an eleent in $G$ denoted by $-a$ such that $ a + (-a) = (-a) + a = 0$

The group is said Abelian if the operation is further commutative: for all $a, b \in G$, we have $a + b = b + a$.

We have both addition groups and multiplication groups. An element added (multpilied with itsef is denoted $n.x$ and $x^n$ respectively.

A mapping from one group to another is called homomorphisms, and isomorphisms if they are further bijective.

The Diffie-Hellman Key Exchange

The existense of subgroups, in general, create security problems and should be avoided, by taking groups of prime order.
The existence of the trivial subgroup $\{1\}$ cannot be avoided and a specific countermeasure must be taken in te protocol.
The value $\mathbb{K} = g^{xy}$ may have some bad distribution and it canoot be used directly as a symmetric key.

We use a goup whose order $q$ is a prime number. $x$ and $y$ shall be selected in $\mathbb{Z}^*_q$

The key exchange follows:

Alice: pick $x \in \mathbb{Z}^*_q, X \gets g^x$
Bob: if $X \notin \langle g \rangle - \{1\}$, abort
Bob: pick $y \in \mathbb{Z}^*_q, Y \gets g^y$
Alice: if $Y \notin \langle g \rangle - \{1\}$, abort
Both: $K \gets KDF(Y^X)$

There is still a problem with the active man-in-the-middle attack. The adversary Eve can pretend to be the other part in this key exchange and can therefor perform an active attack.

The hardness of the computatilnal Diffie-Hellman problem implies the hardness of the discrete logarithm problem in the same group.

The ElGamal Public-Key Cryptosystem

Three algorithms

A key generation algorithm, produsing a key pair $(K_p; K_s)$.
An encryption algorithm, using the public key
A decryption algorithm, using the secret key.

We could use Bob's key $y$ as a long term private key and $Y = g^y$ as his public key.

RSA Cryptography

Euler and other Chinese

Orders in a group

Primality testing

RSA Basics

Public key consist of modulus $n = pq$ and some exponent $e$ such that $gcd(e, \varphi (n)) = 1$. Note that $\varphi (n) = (q - 1)(p - 1)$
Secret key is the inverse $d$ of $e$ modulo $\varphi (n)$. $ d = e^{-1} \mod \varphi(n) $
Encrypt: $y = x^e \mod n$
Decrypt: $x = y^d \mod n$

Quadratic Residuosity

In a field, the equation $x^2 = 1$ leads to two solutions, $x = +1$ and $x = -1$.

For $p$ prime and odd, elements of $\mathbb{Z}^*_p$ have either $0$ or $2$ square roots. The elements with square roots are called quadratic residues and form a subgroup of $\mathbb{Z}^*_p$.

Given a prime $p$ , and element $x \in \mathbb{Z}^*_p$ is a quadratic residue iff $x^{\frac{p - 1}{2}} \mod p = 1$.

Elliptic Curve Cryptography

Galois fields

All finite fields have cardinality $p^k$ where $p$ is a prime number. The prime number $p$ is called the caracteristics of the field. We can therefore construct a finite field $GF(p^k)$ for any prime number $p$ and integer $k$.

In cryptography we are interested in prime fields with cardinality of a large prime number $p$ as well as binary fields of cardinality $2^k$. Operations are taken modulo a fixed polynomial $P(x)$ and coeficcients are reduced by modulo 2.

Characteristics of a binary field:

$-a = a$
$(a + b)^2 = a^2 + b^2$
$\sqrt{a} = a^{2^{k - 1}}$
$Tr(a) = a + a^2 + ... + a^{2^{k - 1}}$
$Tr(a^2) = Tr(a)$

In $GF(2^k)$, the equation $a = x^2 + x$ in $x$ has solutions if and only if $Tr(a) = 0$.

Elliptic curves

Over a field R an elliptic curve with parameters $a$ and $b$ consists of a point of infinity $O$ and points $(x, y)$ of the equation $y^2 = x^3 + ax + b$.

Slope between two points $Q$ and $P$ is $\lambda = \frac{y_Q - y_P}{x_Q - x_P}$

Elliptic curves over a prime field

$$ E_{a, b}(K) = \{O\} \cup \{(a, b) \in K^2; y^2 = x^3 + ax + b\} $$

Characteristics:

for $P = (x_P, y_P)$, we let $−P = (x_P,−y_P)$ and $−O = O$
for $P = (x_P, y_P)$ and $Q = (x_Q, y_Q)$, if $Q = −P$ we let $P+Q = O$
...

Symmetric encryption

Symmetric encryption uses the same key for encryption and decryption. Main focus on two types, block ciphers and stream ciphers.

Block ciphers

DES

Encrypts blocks of 64 bits with a key of 56 effective bits (last 8 are checksum).
The 56-bit key is expanded into 16 48-bit subkeys.
The encryption goes through 16 rounds, each uses a subkey as the round key.
Follows the Feistel scheme

Can do double or triple encryption. Triple is defined as $3DES = DES_{K_3} ( DES^{-1}_{K_2} (DES_{K_1}(X))$. Double encryption only uses $K_1 = K_3$.

AES

Encrypts blocks of 128 bits using keys of 128, 192 or 256 bits with 10, 12 or 14 rounds respectively. Each 16 bytes (128 bits) represent an element in $GF(2^8)$. Four operations are used:

AddRoundKey
SubBytes
ShiftRows
MixColumns

See more on AES here

Modes of operation

ECB: Electronic Codebook
CBC: Cipher Block Chaining
OFB: Ouput Feedback
CFB: Cipher Feedback
CTR: Counter
TCB: Tweaked-codebook
XTS: For harddisks etc.

Stream ciphers

Encrypt streams of data on-the-fly.

RC4

RC4 geneates a key-stream of bytes from a secret key (a nonce) which is a sequence of bytes of total lenght between 40 and 256 bits. It is based on operations in the $\mathbb{Z}_{256}$ group.

Known weaknesses slike correlation between some key byte and some output bytes. Passive key recovery attacks in WEP. Cipher text only attacks in TLS when same plaintext is encrypted many times.

A5/1

Used in GSM communication. 64-bit secret key and 22-bit nonce. Key-recovery know plaintext attacks and active attacks on GSM.

Bruteforce Inversion Algorithms

Random guessing game etc.

Written by

iverjo Assios Martin Hallén

Last updated: Sat, 16 Jan 2016 13:46:39 +0100 .