General model for (network) security

General model for (network) security

A message is to be transferred from one principal (sender) to another (recipient) across some internet service. The two must cooperate for the exchange to happen. A logical information channel is established by defining a route through the internet from the source to the destination by the principals’ cooperative user of communication protocols (e.g. TCP/IP).

All the techniques for providing security have two components:

• A security-related transformation on information to be sent:
  • encryption of the message to make it unreadable by opponent, and/or
  • addition of a code that can be used to verify identity of sender
• Some secret information shared by the two principals (which is hoped to be) unknown to the opponent: such as an encryption key.

Trusted Third Party (security)

A trusted third party may be needed to achieve secure transmission:

• they are responsible for distributing secret information to the two principals while keeping it from any opponent
• needed to arbitrate disputes between the two principals concerning authenticity of a message transmission

Link to original

This model shows 4 basic tasks:

• design an algorithm for performing security-based transformation
• generate secret information to be used w/ algorithm
• develop methods for distribution of secrets
• specify a protocol to be used by the two principals that uses the security algorithm

Link to original

General cryptographic schema

General cryptographic schema

Where $E({\text{Key}}_1,P)=C$ and $D({\text{Key}}_2,C)=P$.

Link to original

• Plaintext

  Plaintext is text that can be read and understood by anyone.

  Link to original

• Encryption

  Encryption is a transformation $E$ that takes an input of plaintext and a key, and generates ciphertext.

  Link to original

• Ciphertext

  Ciphertext is transformed text that needs to be “processed” to be understood.

  Link to original

• Decryption

  Decryption is a transformation $D$ that takes an input of ciphertext and a key, and generates plaintext.

  Link to original

• Symmetric algorithms

  Symmetric algorithms are where ${\text{Key}}_1={\text{Key}}_2$, or otherwise are easily derived from one another.

  Link to original

• Asymmetric algorithms

  Asymmetric (or public key) algorithms are where we use different keys for encryption and decryption, the public key can be published without compromising the private key.

  Link to original

Cipher (short definition)

A cipher is a function (or algorithm) for performing encryption / decryption.

Link to original

Security depends only on the secrecy of the key and not on the algorithm.

Six fundamental principles for military ciphers

Six fundamental principles for military ciphers

1. The system must be substantially, if not mathematically, undecipherable.
2. The system must not be required to be secret and can be stolen by the enemy without causing trouble.
3. It must be easy to communicate and retain the key without the aid of written notes, it must also be easy to change or modify the key at the discretion of the correspondents.
4. The system ought to be compatible with telegraph communication.
5. It must be portable, and its use must not require more than one person.
6. Finally, given the circumstances in which such system is applied, it must be easy to use and must neither stress the mind or require the knowledge of a long series of rules.

J.-G.-H.-V.-F.-A.-A. Kerckhoffs von Nieuwenhof, “La Cryptographie Militaire” in Journal des sciences militaires, vol. IX, 1883

Link to original

Mathematical formalisation of encryption / decryption

Mathematical formalisation of encryption & decryption

• $\mathcal{A}$, the alphabet, is a finite set.
• $\mathcal{M}\subseteq {\mathcal{A}}^{\ast }$ is the message space. $M\in \mathcal{M}$ is a plaintext (message).
• $\mathcal{C}$ is the ciphertext space, whose alphabet may differ from $\mathcal{M}$.
• $\mathcal{K}$ denotes the key space of keys.
• Each $e\in \mathcal{K}$ determines a bijective function from $\mathcal{M}$ to $\mathcal{C}$, denoted by $E_e$. $E_e$ is the encryption function (or transformation). Note: we write $E_e(P)=C$ or equivalently $E(e,P)=C$.
• For each $d\in \mathcal{K}$, $D_d$ denotes a bijection from $\mathcal{C}$ to $\mathcal{M}$. $D_d$ is the decryption function.
• Applying $E_e$ is called encryption, applying $D_d$ is called decryption.

Link to original

Encryption scheme

An encryption scheme (or cipher) consists of a set $\{E_e|e\in \mathcal{K}\}$ and a corresponding set $\{D_d|d\in \mathcal{K}\}$ with the property that for each $e\in \mathcal{K}$ there is a unique $d\in \mathcal{K}$ such that $D_d=E_e^{-1}$.

i.e. $D_d(E_e(m))=m\text{ for all }m\in \mathcal{M}$

The keys $e$ and $d$ above form a key pair, sometimes denoted by $(e,d)$. (they can be identical in the case of a symmetric key)

Link to original

To construct an encryption scheme requires fixing a message space $\mathcal{M}$, a ciphertext space $\mathcal{C}$, and a key space $\mathcal{K}$, as well as encryption transformations $\{E_e|e\in \mathcal{K}\}$ and corresponding decryption transformations $\{D_d|d\in \mathcal{K}\}$.

Example

Let $\mathcal{M}=\{m_1,m_2,m_3\}$ and $C=\{c_1,c_2,c_3\}$. There are $3!=6$ bijections from $\mathcal{M}$ to $\mathcal{C}$. They key space $\mathcal{K}=\{1,2,3,4,5,6\}$ specifies these transformations.

Suppose Alice and Bob agree on transformation $E_1$. To encrypt $m_1$, Alice computes $E_1(m_1)=c_3$. Bob decrypts $c_3$ by reversing the arrows on the diagram for $E_1$ and observing that $c_3$ points to $m_1$.

Three characteristics of cryptographic systems

1. Type of operations used to transform plaintext into ciphertext All encryption algorithms are based on two general principles:

   • Substitution (Cipher)

     Substitution: each element in plaintext is mapped into another

     Link to original

   • Transposition (Cipher)

     Transposition: elements in plaintext are rearranged (some permutation is performed)

     Link to original

   All operations must be reversible. Most systems are product systems which involve multiple stages of substitutions and transpositions.

2. Number of keys used

   • Symmetric, single-key, secret-key, or conventional encryption: both sender and receiver use the same key
   • Asymmetric, two-key, or public-key encryption: sender and receiver use different keys

3. Way in which plaintext is processed

   • Block cipher: input is processed one block of elements at a time, producing an output block for each input block
   • Stream cipher: elements are processed continuously, producing output elements as they come in.

Types of ciphers

Block Cipher

A block cipher is an encryption scheme that breaks up the plaintext message into strings (blocks) of a fixed length $n$ and encrypts one block at a time.

• Encryption: takes in input one block of $n$ bits of plaintext and key of $k$ bits, producing an output of one block of ciphertext of $n$ bits.
• Decryption: takes in input one block of $n$ bits of ciphertext and a key of $k$ bits, producing an output of one block of plaintext of $n$ bits.

Link to original

Stream Cipher

A stream cipher is a XOR operation that encrypts and decrypts one bit or one byte at a time.

Link to original

Codes

Codes work on words of varying length, translation is given by a code-book.

This poses some problems such as:

• If there is no entry for a word, you can’t say it.
• The code-book needs to be protected and distributed.

Link to original

Symmetric-key encryption

Symmetric-key cryptography

An encryption scheme $\{E_e|e\in \mathcal{K}\}$ and $\{D_d|d\in \mathcal{K}\}$ is symmetric-key if for each associated pair $(e,d)$ it is computationally easy to determine $d$ knowing only $e$ and to determine $e$ from $d$. In practice, $e=d$. Sender and recipient share a common key.

There are two requirements for secure use of symmetric encryption:

1. Strong encryption algorithm: at minimum, an attacker who has access to algorithm and one or more ciphertexts should be unable to decipher ciphertext. An even stronger algorithm would prevent an attacker from decrypting ciphertext or discovering the key even if they have access to the ciphertexts with the original plaintext.
2. Sender and receiver must obtain copies of secret key in secure fashion (and keep key secure): nobody must be able to discover the key.

As such, we only need to keep the key secret.

Link to original

Symmetric Cryptosystem Model

Symmetric Cryptosystem Model

• A source produces a message in plaintext: $X=[X_1,X_2,\dots ,X_i]$.
• An encryption key of the form $K=[K_1,K_2,\dots ,K_j]$ is generated.
• Encryption algorithm forms ciphertext $Y=E(K,X)=[Y_1,Y_2,\dots ,Y_n]$.
• Intended receiver, who is in possession of key $K$, is able to invert transformation $X=D(K,Y)$.

The attacker knows the encryption ($E$) and decryption ($D$) algorithms. Observing $Y$ but not having access to $K$ or $X$, may attempt to recover $X$ or $K$ or both by generating $\hat{X}$ or $\hat{K}$.

Link to original

Cryptanalysis and brute-force attacks

The typical objective of attacking an encryption system is to compromise the key in use so that all future and past messages encrypted with that key are compromised.

Cryptanalysis

Cryptanalysis: (science of) recovering the plaintext from ciphertext without the key Cryptanalysis attacks rely on the nature of the algorithm and in some cases knowledge of the general characteristics of the plaintext or even some sample plaintext-ciphertext pairs. We exploit characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used.

Link to original

Brute-force attacks

Brute-force attacks are where the attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained.

Link to original

Average time required for exhaustive key search:

Modelling attacks

Modelling attacks

We can think of the adversary as playing a game:

• Input: whatever adversary necessarily knows from the beginning, e.g. public key, distribution of plaintexts, etc
• Oracle: models information adversary can obtain during an attack. different kinds of information characterise different types of attacks
• Output: whatever the adversary wants to compute, e.g. secret key, partial information on plaintext, etc. They win if they succeed.

Link to original

Possible Attacks

Building a definition of security

Building a definition of security

1. Specify an oracle (type of attack)
2. Define what the adversary needs to do to win the game.
3. The system is secure under the definition, if any efficient adversary wins the game with only negligible probability.

Link to original

Standard definition of conventional encryption

The standard definition of conventional encryption works as follows:

• There is no input data for the adversary.
• We choose a plaintext attack of one of two kinds:
  1. When asked to encrypt message $m$, the oracle returns encryption of $m$ under a fixed key that is chosen randomly initially.
  2. Oracle returns encryption of a randomly chosen message, totally independent of $m$.

The idea is that in the second case, the adversary gets completely useless data, and if they cannot tell this apart from the correct encryptions, then they cannot do any damage in the real world either.

Link to original

Classification of security

Unconditional Security

Unconditional Security

In unconditional security, the system (algorithm) is secure even if attacker has unbounded computing power since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext.

• Security measured using information theory.
• With exception of one-time pad, there’s no unconditionally secure encryption algorithm.
• Hence, strive for algorithm that meets one or both of:
  • Cost of breaking cipher exceeds value of encrypted information.
  • Time required to break cipher exceeds useful lifetime of information. Algorithm is computationally secure if either of these two criteria met.

Link to original

Conditional Security

Conditional security

System can be broken in principle, but this requires more computing power than a realistic attacker would have.

• Security measured using complexity theory.

Link to original