2 Dec — Security basics & cryptography

Category of OS security threats

Breach of confidentiality
retrieving secret data
Breach of integrity
changing data illicitly
Breach of availability
deleting data illicitly - may be easier than changing data
Theft of service
using resources illicitly (e.g., botnets)
Denial of service
preventing system from legitimate use - for example, flood system with invalid requests so that legitimate requests rarely succeed

Symmetic key encryption

  1. In secure location, A & B agree on a secret S.
  2. When insecure, A sends message encrypted with S.
  3. B decrypts message using S.

Simple example: One-time pad, where S is a random sequence of bits. Given message M, A encrypts by computing bitwise exclusive-or M ^ S. B decrypts by repeating bitwise exclusive-or (M ^ S) ^ S, which matches M since (M ^ S) ^ S = M ^ (S ^ S) = M ^ 0 = M. By the way, one-time pad is perfectly secure; but it is only secure as long as secret is used only once (hence the name one-time pad). In practice, this isn't very practical.

Other examples:

Public key cryptography

  1. B generates pair of keys: private key S and public key K.
  2. B announces K to world.
  3. A encrypts message using K.
  4. B decrypts message using S.

Example: RSA (for Rivest-Shamir-Adleman). B starts by generating two large prime numbers p and q, computing their product N = p ⋅ q. B then selects a number s that is relatively prime to (p − 1) ⋅ (q − 1). Then B computes k so that (k ⋅ s) mod ((p − 1) ⋅ (q − 1)) = 1. Public key is the pair (kN), private key is s.

When A wants to send a message M, A encrypts by computing Mk mod N. B can decrypt ciphertext C by computing Cs mod N. This depends on the fact from number theory that if (k ⋅ s) mod ((p − 1) ⋅ (q − 1)) = 1, then xk ⋅ s mod (p ⋅ q) = x for any x.

Example: B chooses p = 11, q = 13, two prime numbers. It finds that (p − 1) ⋅ (q − 1) is 120, so it chooses 77 as a number that's relatively prime to that; this is our s. As it happens, 53 is the correct number to choose for k, since (77 ⋅ 53) mod 120 = 1. B announces 53 and 143 (since 11 ⋅ 13 = 143) as his public key. Now suppose that A wants to send 89 as her message; she computes 8953 mod 143, which is 111, so she sends 111 to B. B decodes this by computing 11177 mod 143, which indeed does translate back to 89.

RSA was the first example of a decent public key cryptosystem, and it is still dominant today. However, elliptic curve crytography is an alternative.

Cryptographic hash functions

A cryptographic hash function takes a plaintext X of any length and generates a fixed-length result H(X) that should be one-way: Given H(X) but not X, it should be impossible to determine X aside from simply trying many values until we find a Y for which H(Y) = H(X). Also, a cryptographic hash function should avoid collisions: Given two values X and Y, H(X) and H(Y) should be completely different values if X and Y are similar, and they should be equal with as small a probability as possible.

Several cryptographic hash functions have been proposed over the years. Two older hash functions still being used are MD5 and SHA-1. However, MD5 has been shown to be prone to collisions, and people have found weaknesses in SHA-1 leading to concern about whether it is prone to collisions; so neither is recommended. Recommended hash functions include SHA-256 and SHA-512.

An aside on passwords

Hash functions are particularly important for storing passwords.

Tips for storing passwords:

Tips for using passwords:


  1. B generates pair of keys: private key S and public key K.
  2. B announces K to world.
  3. B sends message M followed by a certificate computed using S.
  4. A checks that the received message M actually came from B by verifying the certificate using K.

One can again use RSA to do this: B generates the key exactly as before. B computes the certificate by first hashing the message to get H(M) and then computing (H(M))s mod N. A verifies the certificate by computing Ck mod N and confirming that the result matches H(M) for the message A receives.

Signatures application: TLS/HTTPS

Applying certificates requires avoiding the man-in-the-middle attack: Person E may intercept all communication between A and B, using information to decode. For example, when A sends its public key to B, E may intercept that and instead send its own public key to B. Consequently, when E sends messages to B, B thinks they come from A.

The Web uses TLS (on which HTTPS is based); to get around the man-in-the-middle attack, it depends on &lqduo;certificate authorities” (CAs), trusted providers of authenticity.

  1. Site generates public and private key, pays CA to create a certificate for the site's public key using the CA's private key.
  2. All users' browsers are distributed including the public keys for several well-known CAs.
  3. When browser sends request to the server, the server sends the site's public key to the browser along with the CA-generated certificate.
  4. Browser verifies the certificate using its built-in public key for that CA.
  5. Browser generates a symmetric key, sending it to the server encrypted by the site's public key.
  6. Server decrypts the symmetric key using the site's private key.
  7. All subsequent communication between browser and server use the symmetric key.

(Note that the CA is only involved in the setup, not in each individual browser request.)

Other forms of cryptography

There are other niches for specialized cryptographic systems: steganography (hiding a message in some other information, like a picture) and secure voting.