**USING ENCRYPTION for AUTHENTICATION in LARGE NETWORKS of COMPUTERS**
======================================================================

This paper deals with *decentralized authentication*
Authentication = identifying/verifying the identity of communication *principal*

Risk: intruder can
- alter / copy parts of the message
- replay message
- create false message

In some sense, it also establish a secure channel between the two parties...
(by authenticating first, and send encrypted message followed)


What is authenticated?
- parties involved 
- authenticated communication channels

# 0. Take away:
- how to establish authenticate interactive communication between 2 principals
- How to authenticate one-way communication (like in mail server)
- digital signature

# 1. Establishing Interactive Connection
Say A wants to establish a secure connection with B.


*Secret key*
------------
Some notation:
- A, B: principals
- AS: authentication server (a trusted component)
- I: nonce number, used to identify session
- CK: common key, use in a communication session
- KA: A's secret key
- KB: B's secret key

1. A  -> AS : A, B, IA1

2. AS -> A  : {IA1, B, CK, {CK, A}(KB)} (KA)

AS says to A: ok, here is the CK (session key), to communicate with B
(and some details, to allow ...)
+ Only A can decrypt this message and learn about CK. 
+ B is included in (2) to avoid the case that intruder X intercepts
 message 1 before it comes to AS
+ IA1 is included because otherwise, X can replace 2 with old one, forcing A
to reuse old conversation key (i.e, to *avoid message replaying*)

3. A  -> B  : {CK, A}(KB)

Only B can decrypt this message, and find out CK. B also knows the ID of
intending correspondent (authenticated by AS)

Now, A knows that CK is new (because it just receive it from AS), 
but B does not unless its remember all keys used by A before. 
Hence *to avoid relaying* (i.e X can send to B the old message 3,
forcing B to use the old key), message (4) and (5)

4. B -> A :  {IB} (CK)

5. A -> B:   {IB - 1} (CK)

How to defeat replaying? At that point, if a message is replayed, i.e, the CK
 that B received is old, then A wont be able to produce {IB-1}.

If A cache the contents B: CK, {CK, A}(KB), then there is no need to contact AS
every time. Hence, a *shorter* protocol

1. A -> B:  {CK, A}(KB), {IA}(CK)
2. B -> A:  {IA - 1, IB}(CK)
3. A -> B:  {IB - 1} (CK)

The purpose of IA and IB is to avoid message replay risk.

*Public key*
------------
Some notation:
- PKA, PKB: public key of A, B
- SKAS: secret key of Authentication Sever

1. A  -> AS:  	A, B

2. AS -> A : 	{PKB, B}(SKAS)

A now learns about B public key (because A knows PKAS).
Because *every principals* know PKAS, then why need to encrypt M (2)?
Answer:to ensure *integrity*, not *privacy*.

Think about it, if it is not encrypted, then X can intercept and alter 
the message as {PKX, B}, force A to communicate with B using PKX,
hence, the risk of altering the message in between communication path of A & B.
With encryption, X may still know the content of the message, but it cannot
alter the message because it does not know the SKAS

Why B is in (2)? 

3. A -> B :   {IA, A} (PKB)

Only B can decrypt this message, it now contact AS to get PKA

4. B -> AS:   B, A
5. AS-> B :   {PKA, A} (SKAS)

And finally, handshaking:

6. B -> A:  {IA, IB} (PKA)
7. A -> B:  {IB}(PKB)

If A and B use caching, i.e they do not need contact to AS to learn about each
other public key, then we have a "shorten protocol"

1. A -> B:  {IA, A}(PKB)     // we need A here because B will use it to find PKA
2. B -> A:  {IA, IB}(PKA)
3. A -> B:   {IB}(PKB)

OK, now, after handshaking, if A want to send something to B, it need to
do *double encryption*, i.e
A -> B:   { {data}(SKA) } (PKB)
B knows PKA and SKB, hence can understand the message.

Why double encryption? Because if not, then X can interfere the stream,
because X knows PKB. Hence, it can simply send: X -> B: { data } PKB,
and B can still thing this message is from A
==> hence, again, the reason is for integrity and privacy

*Multiple AS*
-------------
In case of conventional encryption
1.  A    ->  ASA :   A, B
1.1 ASA  ->  ASB :   CK, B, A, IA1            (this channel should be secure)
1.2 ASB  ->  ASA :   {CK, A}(KB), IA1, A
2.  ASA  ->  A	:   {IA1, B, CK, {CK, A}(KB)} (KA)
3.  A    ->  B  :   {CK, A}(KB)
4.  B    ->  A  :   {IB}(CK)
5.  A    ->  B  :   {IB -1 }(CK)

In case of public key encryption:
- A can contact ASB directly to learn about B public key, and vice verse

*Implementing AS*
-----------------
(do i need to read more)
- with conventional encryption, entry A: SKA needs to be kept secret, and 
there is need for secure transaction
- with public key, entry does not need to be secret, and no need for
secure transaction

# 2. One-way communication
Say A want to send and email to B (without interaction)

*Conventional way*
------------------
A can simply {CK, A}(KB) as a header of email, and the following data is
encrypted with CK.

A -> B:   {CK, A}(KB), {data}(CK)

Question: how to obtain time integrity, i.e mail has not been recorded by
an intruder and repeated?
- Solution: 
	+ add a time of sending in each message
	+ this time is check at recipient side, if it predates the current time
	at B (by some threshold), then it is rejected

*Public key*
------------
Header is:
A -> B:  {A, I, {B}(SKA)} (PKB)   {I, {data}(SKA)}(PKB)

Why A and {B} (SKA)? 
Answer: To authenticate the sender.
Say B receives this header, it decrypt and learn about A.
Then it contacts AS to get PKA. 
It use PKA to decrypt {B}(SKA), and verification can be made.

Why nonce I?
to connect header with ensuing message text.
(in secret key case: the connection is done with CK)

# 3. Digital signature
Goals: provide evidence to third party that a particular communication
is exactly as received from a particular sender.
1) recipient could not alter a signed text undetected
   (B receives data from A, then change it to data', later on B claims:
   	hey A, you send me this crap)
2) sender cannot credibly disclaim it
	(A sent B data, later on A claim that A did not send it)

A compute hash of the content: CS
Then it sends to AS to request a signature block
A -> AS: A, {CS}(KA)

AS decrypts the message, and reply to A *the signature block*
AS -> A:  {A, CS}(KAS)

Now, A send content to B with the signature block
A  -> B:   {content}(CK), {A, CS}(KAS)

(A cannot say that A sends a different data (because the different data 
will have different CS))

B decrypts the content, and compute its hash, CSC.
B then send the signature block {A, CS}(KAS) to AS and ask for decryption
(because B does not know KAS)
B -> AS:  {A, CS}(KAS)
AS -> B: {A, CS}(KB)

B compare CS and CSC


Note that with public key, thing is easier:
1. A find out PKB as before
2. A -> B:  {{text-block}(SKA)}(PKB)

This is double encryptions.
B carries out the first decryption because B know SKB.
Then B learn about PKA using the protocol or from the cache.
(B should learn about A identity in some header)

When challenged, B simply performs outer decryption on the whole text 
and pass the result to the arbiter who can use PKA to finish the job.
(assuming that A does not changes his key pair)
- A cannot disclaim the message, because A is the only one who knows SKA
- B cannot alter the content, because B does not know SKA