4. Cryptography Primer

Cryptography

Cryptography is the study of techniques for secure communication.

‘Secure’ -> ‘in the presence of adversaries’

Link to original

If your communication is physically secure (only intended parties can participate), then there is no need for cryptography. At different layers of a system:

• The OS typically contains a lot of communication but little cryptography because they often contain the communication and have exclusive control of many data paths in the hardware, can isolate processes, etc.
• Cryptography is very common on the next layers up, such as within web browsers or more generally networked applications. Data paths out of the machine are not so controlled and contained isn’t an absolute.

Uses of Cryptography

Some uses of cryptography include:

• Confidentiality: communication whose content is secret
• Integrity: communication whose content is tamper-proof or tamper-evident
• Authenticity: communication where parties are known to be who they claim

Properties of Cryptography

Some other more subtle properties are:

• Non-repudiation

  Non-repudiation: parties cannot falsely deny their prior messages (‘only $X$ could have generated message $Y$’)

  Link to original

• Plausible Deniability

  Plausible deniability: parties can retain deniability of communication (‘no way to pin message $X$ on person $Y$’)

  Link to original

Ciphers

Cipher

Cryptography works by the use of ciphers, which is a pair of functions $E$ to encrypt and $D$ to decrypt. Unencrypted messages are called plaintexts, $P$. Encrypted messages are called ciphertexts, $C$.

$$\begin{array}{rl}C& =E(P)\\ P& =D(C)\end{array}$$

However, ciphers are well-known bits of mathematics, we need to instead parameterise the cipher by a secret key $K$. And design it to twiddle bits in ways that depend on $K$.

$$\begin{array}{rl}C& =E(P,K)\\ P& =D(C,K)\end{array}$$

This only works if $K$ is kept secret.

Link to original

Cryptography in practice

Applying to earlier concepts:

• Confidentiality: content is secret To send $P$, transmit $C=E(P,K)$; recipient recovers $P=D(C,K)$.
• Integrity: content is tamper-proof To send $P$, transmit $C=E(P\text{ ++ hash}(P),K)$. Recipient uses $K$ to decrypt as $M=(Q\text{ ++ }H)$ and checks $H=\text{hash}(Q)$. It is near impossible for an attacker to twiddle bits such that the check still passes after transit and decryption.
• Authenticity: parties known to be who they claim Use a challenge-response protocol. To challenge: send a random number (‘nonce’) $X$ Response of $E(X,K)$ proves responder knows key $K$

Simple Ciphers

• Caeser Cipher

  Caesar cipher: each plaintext character is replaced by character $3$ to the right modulo $26$ Equivalent to ROT13 with key of $3$.

  Brute-force cryptanalysis is possible as:

  1. the encryption and decryption algorithms are known
  2. only 25 keys to try
  3. language of plaintext is known and easily recognisable

  Link to original

• One-time Pad

  One-time pad: given any plaintext, the key is a string of equal length to the message. We use a self-inverting function such as XOR, $C$ transforms each $s_i$ into $s_i\oplus k_i$. Capable of perfect secrecy but requires a large amount of key material and key distribution is a big problem.

  One-time pad is an improvement to the Vernam cipher except:

  • we use a truly random key that is as long as the message, so the key need not be repeated
  • we use the key to encrypt and decrypt a single message, then we discard it

  Each new message $P$ requires a new key of the same length as $P$. Produces random output with no statistical relation to plaintext.

  It is unbreakable: $C$ contains no information whatsoever about $P$. This is the only cryptosystem that exhibits perfect secrecy.

  

  Link to original

Practical Ciphers

• Symmetric Cipher

  Symmetric cipher: same key works for encrypting and decrypting. The goal of a practical cipher is to be computationally infeasible to ‘crack’, i.e. decrypt without the key while being affordable to encode or decode with a reasonably sized key.

  Link to original

• We commonly exploit exponentials: the size of the key space grows exponentially with length. If there is no asymptotically faster cracking method than ‘brute force’, then we choose $\text{length}(K)$ such that cracking would take longer than the life of the universe. Many ciphers with 128-bit keys continue to be regarded as secure.

• Advanced Encryption Standard (AES)

  A symmetric block cipher intended to replace DES for commercial applications.

  • Uses $128$-bit block size and a key size of $128$, $192$, or $256$ bits.
  • Does not use Feistel structure.
  • Each full round consists of $4$ separate functions:
    • byte substitution
    • permutation
    • arithmetic operations over a finite field
    • XOR with a key

  

  Link to original

Asymmetric key cryptography

Asymmetric key cryptography

Key distribution is a big problem, to defeat cryptography we can usually discover the key instead of cracking the cipher.

Ideally we can send encrypted messages around without having pre-shared a secret key, we can do this with asymmetric encryption. Keys now come in two parts: public and private.

To send a confidential message:

• Alice sends Bob $C=E(P,K_{\text{public}})$
• Bob decrypts $C=D(C,K_{\text{private}})$

Where $(K_{\text{public}},K_{\text{private}})$ is Bob’s key pair.

Link to original

However this does not cover authenticity yet.

Rivest-Shamir-Adleman (RSA) cryptosystem

Rivest-Shamir-Adleman (RSA) cryptosystem

Relies on that factoring of very large ‘nearly-prime’ numbers is computationally hard. A public key is a product of two primes (‘nearly prime’) concatenated with an auxiliary value $m$. Encryption and decryption use exponentiation by one or other of these primes (individually private) modulo $m$.

Problem: exponentials are slow to compute Solution: generally use RSA to exchange a freshly generated symmetric key. Then use that for subsequent communication. (this is how SSH works)

Link to original

Authenticity problem with public keys

Suppose you receive a message using public-key crypto. If I can decrypt it using X’s public key, I know it was encrypted using X’s private key. So only X could have encoded it.

However this is not the whole story, you need to consider if person X is really who they say they are, and consider how you got the pubkey and come to trust it. There are two solutions to this: public key infrastructure (certificates) and web of trust (PGP-signed emails, ‘key-signing parties’)

Cryptographic Hashing

Cryptographic Hashing

Another kind of useful function is the cryptographic hash function:

• like any hash function $h(m)$, these map arbitrary-size data to fixed-width integers, in uniformly distributed fashion
• A hash function $h$ is cryptographic if given an output $h(m)$ it is computationally infeasible to discover $m$ or any $m^{\prime }$ where $h(m^{\prime })=h(m)$.
• Example algorithms are MD5 (broken), SHA-1 (broken), SHA-2 (still secure)
• Useful for authentication of software (file hashes) and implementing passwords.

Link to original