• Alice and bob want to have a conversation
• Eve can listen in, she can't alter messages
• Mallory can modify messages, sub in his own messages replay messages etc.
• E and M are computationally limited.

Confidentiality/Privacy

• Make sure E and M don't understand whats appearing on the channel.
• only those authorized to read, can read
• done by physical security and algorithms which make data unintelligible

Data Integrity

• Messages sent between A&B appear in tact (vs M). A and B should know that a message has been modified.
• Written data should not be altered. If it is, we should know about it.

Authentication

• Ensure that A knows that she is talking to B and vice versa
• Difficult to define well
  • Data: verification of the origin of the data
  • Entity: verification of the identity of the entity

Non-Repudiation

• Ensure that, if A says that she will meet B at 8:30 in Tim Hortons, she can't later say 'I did not say that'.
• prevents an entity from denying previous commitments/actions

Things that fall outside

• Software registration
• Digital rights managment

These are usually impossible to implement, mostly rely on security by obscurity (using secrecy of design/implementation to ensure security).

Questions

1. Which is more important for a bank account, secrecy or authentication

Other things we would like to do

• Flip a coin in a distributed way or play black jack when A and B do not trust eachother.
• Exchange information over an insecure, faulty channel in a secure way. (ie) At the end of the protocol A and B agree on X, but E and M don't know X.
• Digital watermarking
• Online auctions and Voting

Requirements for Cryptosystems

A cryptosystem should be secure even if everything about the system, except the key, is public knowledge. This is one of...

Parts of a Cryptosystem

• Sigma: The alphabet (ie Sigma={a,b,c,...x,y,z, ,0,...,9} or Sigma={0,1}
• M <= Sigma^*, the message space
• C <= Sigma^*, the cyphertext space
• K the keyspace
• for each e in K, E_e(x):M->C, E_e(x) is a bijection (1-1, onto)
• for each d in K, D_d(x):C->M, D_d(x) is a bijection (1-1, onto)
• forall e in K, exists d in K such that D_d=E_e^-1, that is,
  forall m in M D_d(E_e(m))=m

Question:Why use keys? Why not just a single pair of functions E and D such that forall m in M, D_d(E_e(m))=m?
Answer: In practise E and D get discovered. For example, when a person leaves the secure group.

Substitution Cypher

Define a map between letters 1 A -&gt; Z 26 2 B -&gt; X 25 3 C -&gt; W 23 . . . 26 Z -&gt; E 5 call this map k (the key). This map (essentially, the right side) is the key (K, the keyspace, is the set of all permutations of {1,...,26}). |K|=26!. We can write the above key as (ZXW...E) where we understand that A->Z, B->X, ... We naturally extend E_k to strings m in M by applying E_k to each letter of m. What is D? Actually it is the same function. For a given e in K, what is the inverse key d?

Caesar Cipher

• This is a special case of the Substitution cypher.
• Let D_k(x)=E_k(x)=[(x-'A')+k mod 26]+'A'.
• Here we consider the keyspace K={0,...,25}.

Problem with this cypher: Eve simply trys all keys (just 26 of them) and looks for english. Eve discovers the key and the message.
Solution: Use a true substitution cypher. |K|=26! around 2⁸⁸ keys, not as easy to check all possible keys.

Problem with Substitution Cypher

It is vulnerable to frequency analysis.

One Time Pad: Provably perfect secrecy

First a few preliminaries: the XOR operation is defined by the following truth table... Imagine Alice and Bob both have the same secret random sequence of bits r₀, r₁, ..., r_n-1 (the One Time Pad). Alice has a binary message m₀, m₁, ..., m_n-1 which she wants to securely (against Eve) send to Bob. Alice does the following: This is called a one time pad since perfect security can only be guaranteed for a single message sent with the key. Repeatedly using the same one time pad can allow Eve to decrypt the s[i] she sees flying across the channel.

One Time Pad is Secure

First we have to discuss what we mean by secure. We will say that a scheme is secure against Eve, if, when Bob and Alice are using this scheme, the sequence of bits Eve sees flying across the channel is indistinguishable from a random sequence of bits.

We argue below that, using the One Time Pad scheme, the sequence of bits flying across the channel is a random sequence of bits.

r[i] | 0 | 1 --+--------+-------- 0 | s[i]=0 | s[i]=1 m[i] --+--------+-------- 1 | s[i]=1 | s[i]=0 | | The events (s[i]=0 intersect m[i]=0) and (r[i]=0 intersect m[i]=0) are the same so Pr(s[i]=0|m[i]=0)=Pr(r[i]=0|m[i]=0). Now events r[i]=0 and m[i]=0 are independent, so Pr(r[i]=0|m[i]=0)=Pr(r[i]=0)=1/2. Putting these together we have Pr(s[i]=0|m[i]=0)=1/2 Similarly Pr(s[i]=1|m[i]=0)=1/2. So Pr(s[i]=0 intersect m[i]=0)=Pr(s[i]=1 intersect m[i]=0) (by definition of conditional probability). We will call this number x.

A similar argument establishes that Pr(s[i]=0 intersect m[i]=1)=Pr(s[i]=1 intersect m[i]=1). We call this number y.

Now Pr(s[i]=0)=Pr(s[i]=0 intersect m[i]=0)+Pr(s[i]=0 intersect m[i]=1) since these are mutually exclusive events. So Pr(s[i]=0)=x+y. Similarly Pr(s[i]=1)=x+y. So Pr(s[i]=0)=Pr(s[i]=1)=1/2. That is, the s[i] is a random stream of bits and the one time pad scheme is secure.

Using a Pseudo Random Number Generator

The obvious problem with a One Time Pad is communicating the key (the one time pad). Unfortunately, the key is as long as the message it is used to encrypt and it can only be used one time. One way to work around this is to use a pseudo random number generator. To use the pseudo random number generator, set its initial state by executing seed(r), for some number r called the random seed. Subsequent calls to nextRandomBit() results in a sequence of bits that 'appears' random. If we had such a function, then to generate the one time pad for use in the above scheme, Alice and Bob would only need to share the initial secret seed. Note: The sequence of bits nextRandomBit(), nextRandomBit(), ... is determined by the initial call to seed(r).

Imagine Alice and Bob both have the same secret number r (this is the key or the random seed). Alice has a binary message m₀, m₁, ..., m_n-1 which she wants to securely (against Eve) send to Bob. Alice does the following:

Alice executes seed(r) to initialize the random number generator. Alice computes s[i]=m[i] XOR nextRandomBit() and then sends the s[i] across the channel in order. =s[2]-&gt; =s[1]-&gt; =s[0] -&gt; Alice --------+------------------------- Bob | | | | Eve (eavesdropper) To start Bobs side of the protocol, Bob executes seed(r) to initialize the pseudo random number generator on his side. Bob will now be generating the same sequence of pseudo random bits that Alice did. When Bob receives s[i], he decripts by XORing s[i] with nextRandomBit(). Remember that Bob and Alice have the same secret key (r). That is, Bob computes s[i] XOR nextRandomBit()= m[i].

Data Encryption Standard (DES)

• Also known as DES, DEA (A=Algorithm).
• Symmetric key ('essentially' same key used to encrypt/decrypt)
• Block Cypher
• Uses 64 bit "key" = 56 bit key + 8 bits for error checking
• DES(k,b)=b' where b and b' are 64 bits
• The computation of DES(k,b) is complex, but each step is reversible so DES(K,x) is 1-1, onto function from {0,1}⁶⁴ to {0,1}⁶⁴.
• DES can be used in many different ways... ECB (Electronic Code Book), CBC (Cypher Block Chaining)
  ECB (Electronic Code Book)

  Message M broken into 64 bit chunks m1 m2 m3 m4 m5 ... DES(k, ) applied to each block independently Vulnerable to frequency analysis for known language.
  
  
  
  
  CBC (Cipher Block Chaining)

  Message M broken into 64 bit chunks m1 m2 m3 m4 m5 ... DES(k, ) applied to each block XORed with the previous ciphertext.
  
  
  
  
• RSA has a DES challenge, DES broken by parallel computation (trying all possible keys).
• DES no longer considered secure enough, instead 3DES (Triple-DES) is used when it matters.
  3DES Key=(k₁, k₂, k₃) (3 DES keys).
  3DES(k,b)=DES(k₃,DES^-1(k₂,DES(k₁, b)))
  3DES is again a 64bit block cipher.

The above scheme (using a pseudo random number generator to generate a onetime pad) relies on a shared secret random seed (called r above). You might wonder how Alice and Bob can exchange such a secret in the presence of Eve. Of course, Alice could physically visit Bob to exchange the secret. It turns out that Alice and Bob can agree on a secret number using the insecure channel and that, under some cryptographic assumnptions, Eve will not know the secret. This is the Diffie Hellman Key Exchange. See the RSA Labs article. or this great video.

Preliminaries

The Diffie Hellman Key Exchange relies, in some sense, on the difficulty of the Discrete Log problem. Assume you know number g and large prime p. I have x in {1,...,p-1} If I give you g^x mod p can you find x? This problem (under certain assumptions about g,x and p) is believed to be computationally difficult to solve.

The protocol

Alice Bob choose g,p and send to Bob --------------------&gt;g,p choose secret a send g^a mod p to Bob -------------------------&gt;g^a mod p choose secret b g^b mod p&lt;------------------------------------- send g^b mod p to Alice compute (g^b mod p)^a mod p =g^{ab} mod p compute (g^a mod p)^b mod p =g^{ab} mod p Both Alice and Bob have a shared secret. That is g^{ab} mod p. At the completion of the Diffie Hellman Key Exchange, Eve knows, g,p,g^a mod p, g^b mod p. It is believed to be computationally difficult to compute g^{ab} mod p from this information. Of course, if Eve could solve the Discrete Log problem, then Eve could compute g^{ab} mod p.

Diffie Hellman Vulnerability

The Diffie Hellman Key Exchange is vulnerable to Mallory. That is, Mallory can run a Man in the Middle Attack. Mallory hijacks the channel, placing himself between Alice and Bob. A ----------------- M ---------------- B Mallory executes two Diffie Hellman Key Exchanges, one between Mallory and Alice and another between Mallory and Bob. At the end of this, Mallory and Alice share a secret key, Mallory and Bob share another secret key. Alice and Bob are none the wiser.

Confidentiality

Send encrypted messages across the wire. just decrypt m' and read. m-&gt;E (m)----------------------&gt;m' D (m') e d Alice --------+-----+---------- Bob | | | | | Mallory (malicious attacker) | Eve (eavesdropper) Note: Keys must be secret! This is private key cryptography.

Data Integrity

Remember, we want to ensure that data has not changed since I stored it on disk. In terms of the Alica/Bob model, we want to defend against Mallory. The best we can do is to 'ensure' that, if Bob recieves a message, then Bob can determine that it was created with Alices encryption key and not subsequently altered.

Alice sends m as well as E_e(m) to Bob. Bob verifies that the message m1 recieved and the encrypted version m2 satisfy D_d(m2)=m1. If these match then Bob has confidence that the message recieved was encrypted using Alices private key e. Note: It is still possible for Mallory to resend a pair previously seen. This technique protects against Mallory manipulating the message m parts of a message.

m-----------------------&gt;m1 Check that m-&gt;E (m)----------------------&gt;m2 D (m2)=m1 e d Alice --------+-----+---------- Bob | | | | | Mallory (malicious attacker) | Eve (eavesdropper) In what follows, we will see that instead of sending both m and E_e(m) we will send m and hash(m). Note: We will use a keyed hash function.

Hash Functions and their properties

You might ask, why does Alice need to send m as well as E_e(m)? That was just the setup for hash functions. A hash function is a one way function from larger finite strings to typically smaller, fixed length strings. To be a cryptographic hash function, there are a few properties we would like to have.

For an unkeyed hash function h, we would like to have

1. preimage resistance: given y, it is computationally difficult to find x such that h(x)=y.
2. 2nd-preimage resistance: given x, it is computationally difficult to find x1 such that h(x)=h(x1).
3. collision resistence: it is computationally difficult to find x0 and x1 such that h(x0)=h(x1).

We have left out the issue of whether there actually is a cryptographically secure hash function. None has yet been proven secure (whatever that means).

Application of Hash functions to Data Integrity

Say I want to distribute software. I want to have a main distribution site as well as mirrors. I want to ensure to be able to ensure that downloaders of my software from mirrors will be confident that they have good, unmolested copies of my software. What do I do? I keep a MD5 hash of my file a the main distribution site. Those interested in the software can download it from any of the mirrors and verify their download by computing the MD5 hash of the download and comparing it with the MD5 fingerprint downloaded from the main site. file.zip file.zip.md5=MD5(file.zip) -----+ MAIN | | +----&gt; file.zip.md5 check whether file.zip.md5=MD5(file.zip (from MIRROR4)) file.zip MIRROR1 +----------&gt; file.zip (from MIRROR4) | | file.zip | MIRROR2 | | | file.zip | MIRROR3 | | | file.zip -----------------+ MIRROR4 Note: For this to work, we need 2nd preimage resistence. Why?

Data Integrity (continued)

We left off with the question of how Alice convinces Bob that the data has arrived in tact. Alice and Bob have a secret key k (salt possibly). Instead of using a simple hash function, they used a keyed hash function (for example MD5(salt+message)). To ensure data integrity, Alice sends Bob the pair (m,h(k,m)). Bob receives (m',h') and checks whether h(k,m')=h'. Note:This does not prevent Mallory from replaying a past message. It prevents Mallory from manipulating the message. m-----------------------&gt;m' h(k,m)----------------------&gt;h' Bob now verifies h'=h(k,m') Alice --------+-----+---------- Bob has secret | | has secret key k key k | | | Mallory (malicious attacker) | Eve (eavesdropper)

In terms of MD5, Alice and Bob would have the same secret string (called salt). Alice would send m as well as MD5(salt+m) (+ is string concatenation). Bob receives m' and h' and checks whether MD5(salt+m')=h'.

Authentication

Alice wants to convince Bob that Alice is on the other end of the line. Alternatively, you want to login to your computer. First attempt: E ('Im Alice'))------------&gt;m' Bob checks D (m')='Im Alice' e d Alice --------+-----+---------- Bob | | | | | Mallory (malicious attacker) | Eve (eavesdropper) While Bob is fairly certain that no one else could have encrypted the message 'Im Alice', Mallory could replay the authentication. An alternative...challenge/responce. Bob chooses a random number, sends it to Alice, Alice encrypts the random number and returns it. Each round gives Bob more confidence that the individual on the other end of the line is capable of encrypting using key e. Remember, Bob has key d and Alice has key e. choose a random number x1 send it to Alice &lt;-------------------x1 encrypt and return E (x1) --------------------&gt;m' Bob checksD (m')=x1 e d choose a random number x2 send it to Alice &lt;-------------------x1 encrypt and return E (x2) --------------------&gt;m'' Bob checksD (m'')=x2 e d . . . Alice --------+-----+---------- Bob | | | | | Mallory (malicious attacker) | Eve (eavesdropper)

A special case of assymmetric key cryptography where knowing an encryption key does not allow one to derive the decryption key and vice versa. The security of RSA relies on the infeasibility of factoring large numbers.

Alice gets a public, private key pair (k_e, k_d). Knowing one does not easily lead to knowing the other. Alice publishes her public key k_e and keeps the private key securely hidden. k_e and k_d are inverses with respect to RSA, that is

RSA(k_d, RSA(k_e, m))= RSA(k_e, RSA(k_d, m))=m

RSA is not known to be more secure than block ciphers. The difference here is that RSA is not symmetric AND it is difficult to find the private key given the public key and vice versa.

RSA calculations are time consuming. Typically RSA is used to exchange a session key (ie for 3DES).

• An Introduction from Verisign

An X.509 digital certificate is a way for Alice to publish her public key, such that everyone that reads the certificate 'knows' that it really is Alices public key. In order to make this happen, we need a trusted third party. Companies like entrust, verisign and thwate (see compare certificates) play this role. They have well known public keys and will verify your public key (that the public key is under your control). You can make up a public/ private key pair, then submit a Certificate Signing Request (CSR). They (the Certificate Authority (CA) then creates an x.509 digital certificate signed with the CAs private key.

• Block Cipher Modes of operation
• Browser Security Handbook
• OpenSSL
  • open ssl tricks
  • Creating a digital certificate with OpenSSL
  • Real World Uses For OpenSSL
  • OpenSSL docs
• GnuPG
  • The GNU Privacy Handbook,
  • Gnu Privacy Guard (GnuPG) Mini Howto (English)
• OpenVPN
  • OpenVPN How-To,
  • Openvpn CSR,
  • OpenVPN RSA Key Management