**Lecture Notes - Week 6
**

These are protocols that allow two persons to exchange cryptographic keys in order to conduct a private communication.

A key k for symmetric encryption can be exchanged over a secure channel, eg a trusted messenger.

To avoid encrypting a large number of messages with the
same key, k can be used as a "master key" which is used once for each
session to exchange a new key k_{s} as a session key, eg by establishing
a new key k_{s} and sending it to the other party, encrypted as E(k_{s},
k).

Two users may utilise a central key distribution agency to establish a new
symmetric key for their communication.

Assume that Pablo wishes to communicate with Renee. P
shares a symmetric key K_{P} with the agency and R shares a key K_{R}
with the agency. See Figure 1.

1.
P sends (P, R, I_{P}) to the agency where P and R are the names
and I_{P} is P's reference number.

2.
The agency sends E((I_{P}, R, K_{PR}, E((K_{PR},
P), K_{R})), K_{P}) back to P. P checks whether I_{P}
and R are corrected. P now has a key K_{PR} to communicate with R and a
cryptogram that he can't read.

3.
P sends E((K_{PR}, P), K_{R}) to R. R knows that P wants
to communicate with her and that K_{PR} is a key that was issued by the
agency.

4.
P and R now have a shared key K_{PR} to communicate with each
other.

Exercise: What possible attacks could be mounted by eavesdropper Octavia? Is the protocol susceptible to any of these attacks?

Given that P has public and private keys E_{P} and
D_{P} and that R has public and private keys E_{R} and D_{R},
P could send messages directly R using E_{R}. However, since symmetric
encryption is much faster than public-key encryption, P would normally select a
symmetric key K_{PR} to communicate with R and will send that key to R
as E_{R}(K_{PR}). This message could, however, be forged by O.
Therefore P seals the message with his signature and both parties confirm that
they a have a "live" key, ie not a key replayed from a previous
communication. See Figure 2.

1.
P sends E_{R}(D_{P}(K_{PR})) to R. R can obtains
K_{PR} = D_{R}(E_{P}(E_{R}(D_{P}(K_{PR}))))
and is convinced that the message is authentic.

2.
R sends E(n, K_{PR}) with a random number n to P.

3.
P sends E(f(n), K_{PR}) back to R where f(n) is an agreed
function, eg f(n)=n+1.

This protocol works as long as P and R can be sure that they have each other's genuine public keys.

For the secure distribution of public keys an agency can be used. See Figure 3.

1. P sends a message (P, R) to the agency D.

2.
D responds with D_{D}((E_{R}, R)) sealing the message
with its private key.

3. P decrypts the message with the agency's public key and is sure to have R's public key.

4.
P sends a message E_{R}((P, I_{P})) to R where I_{P}
is P's message reference number

5. R sends a message (R, P) to the agency D.

6.
D responds with D_{D}((E_{P}, P)) sealing the message
with its private key.

7. R decrypts the message with the agency's public key and is sure to have P's public key.

This protocol is secure as long as the agency has indeed the genuine public keys of both parties.

A certificate comprises a person's (or machine's) identity and his/her/its public key, authenticated by the issuer of the certificate, similarly to, for example, a driver's licence linking a person's photograph to his/her name as authenticated by the issuing authority's stamp and signature.

In a hierarchical structure, it is assumed that each
immediate superior knows her immediate subordinates. For example in the company
structure in Figure 4, Diana obtains a certificate as follows:

1. Diana creates (Name=Diana, Pos=DivManager, PubKey=17EF83)

2.
Edward adds hash and signs: D_{Ed}((Name=Diana, Pos=DivManager,
PubKey=17EF83CA, Hash= 128C4)) which is Diana's certificate.

Similarly, Delwyn obtains a cerficate as follows:

1. Delwyn creates (Name=Delwyn, Pos=DeptManager, PubKey=3AB3882C)

2.
Diana adds hash and signs: D_{Di}((Name= Delwyn, Pos=DeptManager,
PubKey=3AB3882C, Hash= 48CFA)), then appends her certificate D_{Ed}((Name=Diana,
Pos=DivManager, PubKey=17EF83CA, Hash= 128C4)). This is Delwyn 's certificate.

This self-enforcing protocol allows two players to play poker by email. To simplify things, assume that there are 10 cards of which A obtains 5 at random and B obtains 5 at random. Assuming commutative encryption, this is achieved by the following protocol:

1.
A encrypts the 10 cards c_{1} â€¦ c_{10} with her key and
sends E(c_{1}, K_{A}) â€¦ E(c_{10}, K_{A}) to B.

2.
B chooses 5 cards, say c_{1} â€¦ c_{5}, and sends E(c_{1},
K_{A}) â€¦ E(c_{5}, K_{A}) back to A.

3.
B encrypts the other 5 cards c_{6} â€¦ c_{10} with his
key and sends E(E(c_{6}, K_{A}), K_{B}) â€¦ E(E(c_{10},
K_{A}), K_{B}) back to A.

4.
A decrypts all 10 cards and has c_{1} â€¦ c_{5}, and E(c_{6},
K_{B}) â€¦ E(c_{10}, K_{B}), [assuming that the 2
encryptions are commutative].

5.
A sends E(c_{6}, K_{B}) â€¦ E(c_{10}, K_{B})
back to B.

6.
B decrypts the 5 cards and has c_{6} â€¦ c_{10}.

Exercise: Modify the protocol for a game with 32 cards of which 5 are dealt to each of 2 players.

Normally, users cannot or don't want to generate their own keys and there is legitimate concern that the key distribution agency should not know which key pair it has given to which user. Of course the agency cannot simply let users choose a key pair from a published list because anyone else would have a convenient mapping between public and private keys. A possible solution is derived from the remote poker game:

1.
A send out a constant stream of key pairs E((E_{i}, D_{i}),
K_{A}) encrypted with her key K_{A}.

2.
B picks one key pair at random, encrypts it with his key K_{B}
and sends E(E((E_{j}, D_{j}), K_{A}), K_{B})
back to A.

3.
A decrypts it with her key K_{A} and sends E((E_{j}, D_{j}),
K_{B}) back to A.

4.
B decrypts it with his key K_{B} and has his key pair (E_{j},
D_{j}).

A remote voting protocol needs to fulfil the following criteria:

Â· Only authorised users can transmit messages.

Â· Each user can only transmit 1 message.

Â· It is impossible to determine who sent a particular message.

Assume 3 voters J, K and L, each of whom has a vote v (v=0 or v=1). Each voter has public-key encryption/decryption functions E and D. Each voter also has another public encryption function R which embeds v in a random string and the corresponding decryption function Q. The voting is conducted as follows:

1.
Each voter encrypts R_{J}(R_{K}(R_{L}(E_{J}(E_{K}(E_{L}(v_{j}))))))
and send it to J. Records are kept of the intermediate encryption results.

2. J verifies that her vote is in the set.

3.
J decrypts with Q_{J}, scrambles the order and sends the set of R_{K}(R_{L}(E_{J}(E_{K}(E_{L}(v_{i})))))
to K.

4. K verifies that his vote is in the set, using his record of the intermediate encryption results.

5.
K decrypts with Q_{K}, scrambles the order and sends the set of R_{L}(E_{J}(E_{K}(E_{L}(v_{i}))))
to L.

6. L verifies that her vote is in the set, using her record of the intermediate encryption results.

7.
L decrypts with Q_{L}, scrambles the order and sends the set of E_{J}(E_{K}(E_{L}(v_{i})))
to J.

8. L also signs the set and sends the signature to J and K.

9.
J decrypts with D_{J} and sends the set of E_{K}(E_{L}(v_{i}))
to K.

10. J also signs the set and sends the signature to K and L.

11.
K decrypts with D_{K} and sends the set of E_{L}(v_{i})
to L.

12. K also signs the set and sends the signature to J and L.

13.
L decrypts with D_{L} and publishes the resulting v_{i}.

This protocol works because in steps 1-7, the individual votes are not revealed, but each voter can verify that his/her vote is still in the set. This is due to the embedding in random bit strings. Forgery in steps 8-13 is transparent because everyone can reverse the steps 13, 11 and 9 and thereby confirm that no tampering has taken place. Moreover, if anyone had modified the votes in steps 8-13, the digital signatures in steps 8, 10 and 12 would reveal who had done the tampering.

The problem of sending one of two possible messages such that neither sender nor receiver knows until later which of the two is sent. Example: P and N decide to flip a coin. Heads wins. The following protocol achieves this in a fair manner:

1.
P chooses to public-key pairs E_{i}, D_{i} and E_{j},
D_{j}.

2.
N chooses a symmetric key K_{N} to a symmetric encryption
function S(.).

3.
P send E_{i} and E_{j} to N.

4.
N chooses either i or j, call it h, and sends E_{h}(K_{N})
to P.

5.
P chooses either i or j, suppose it is j, and computes K_{?}=D_{j}(E_{h}(K_{N})).
If h=j, then K_{?}=K_{N}, other K_{?} is meaningless.

6.
P send S("heads", K_{?}) to N.

7.
N decrypts S(S("heads", K_{?}), K_{N}) and
either obtains "heads" or a meaningless string.

8.
For control, P gives D_{i} and D_{j} to N who can then
verify that h=i or h=j.

The problem of two parties simultaneously signing a contract without a truusted third party requires

Â· Simultaneous commitment

Â· Unforgeability

This can be achieved by splitting one's signature into parts (say 4 quarters) and transmitting the parts by oblivious transfer, such that neither party can be aware exactly at which point the signatures have been transmitted in full.

Assume that A and B want to simultaneously sign a contract:

1. Both A and B randomly select 2n symmetric keys (eg DES) and group them in pairs.

2.
Both A and B generate n pairs of messages L_{i} and R_{i},
eg "This is the left half of my signature" and
"This is the right half of my signature". The contract is
considered signed if either party can produce both halves, L_{i} and R_{i},
for any i.

3. Both A and B encrypt each message pair with each DES key pair, left half with left key, right half with right key.

4.
They send each other the 2n encrypted messages, labelling the messages as
c(L_{i}) or c(R_{i}).

5. A and B send each key pair by oblivious transfer to each other, ie neither knows which of the two keys of a pair has been transmitted.

6. Both A and B decrypt all the messages they can and verify that they are valid.

7.
For b = 1 â€¦ keylength

A and B send each other the
bit b of each of the 2n keys

8. A and B decrypt the remaining halves of the messages and the contract is signed.

What if A sent nonsense in steps 4 or 5? B would notice in step 6.

What if A sent only one half of each pair correctly in step 4? She has a 50% chance of getting away with it for each pair. Therefore n should be large, eg for n=10, A's chance of cheating is 1/1024.

What if A stops sending bits in the loop in step 7 and determines the rest of the key by brute force? At that point B has the same chance of determine the rest of the key by brute force (given the same computing power).

What if A sends identical messages in step 5? B will notice this from the record of the protocol.

Similar protocols allow the sending of certified mail, message against receipt, and the simultaneous exchange of secrets. See B. Schneier, Applied Cryptography, ss 5.8 and 5.9).

Note that a lost keys presents a problem in authentication protocols: a user who wants to repudiate a digital signature, for example, may state that the private key was revealed before the transaction took place.

Block ciphers, eg the 64-bit DES scheme, will encrypt identical 8-byte blocks identically. For example, a bank transfer may be transmitted in a 40-byte message as follows:

Account Name (24 bytes) |
Acct No (8) |
Xfer Amt (8) |

Since this message makes up 5 DES data blocks, single
blocks can be intercepted and replayed in the context of other messages, eg
changing the transfer amount in another message. This can be avoided using Block
Chaining where a sequence of blocks B_{1}, B_{2}, B_{3}
etc is transmitted as C_{1}, C_{2}, C_{3} etc with C_{1}=B_{1},
C_{2}=C_{1}+B_{2}, C_{3}=C_{2}+B_{3}
where the + is an exclusive-or operation.