CS395T - Design and Analysis of Security Protocols

0 comments

file time: 2008-02-16

filetype:ppt

Click Here To Download...

>  
 
 
 
 

CS 395T 

Contract Signing Protocols

 
 
 
 
 

Real-World Fair Exchange 

Both parties want to sign the deal Neither wants to commit first   
 

Immunity

deal

 
 
 
 
 

General Setting 

Two parties agree on the items to exchange, each will release his item if the other releases his Physical solution is easy Sit at a table and exchange items simultaneously General problem:

   how to exchange information fairly on an

    asynchronous network?

Both parties succeed or both fail

  

 
 
 
 
 

Why is Fair Exchange Difficult? 

Cannot trust communication channels Messages may be lost Attacker may insert additional messages Cannot trust other party in protocol www.Fly-By-Night.com Public-key certificate does not certify honesty There may exist a trustworthy judge or trusted third party Use sparingly, only if something goes wrong, otherwise becomes a communication bottleneck  
 
 
 
 

Focus on Contract Signing Protocols 

Fair exchange of digital signatures Two parties want to sign a contract. 

   Contract is known in advance to both parties.

We00l look at protocols for exchanging signatures, not for contract negotiation (e.g., auctions) Multi-party signing is more complicated The attacker could be another party on the network or the person you think you want to sign a contract with In key establishment protocols, usually assume that both parties are honest  
 
 
 
 

Example: Stock Trading 

Willing to sell stock at price X 

Ok, willing to buy at price X 

stock broker 

customer 

Signed contracts are essential as proofs of agreement in case market price changes

 
 
 
 
 

Many Types of Protocols 

Probabilistic protocols We looked at Rabin00 and BGMR protocols Gradual-release protocols Exchange signatures a few bits at a time Work required to guess remaining bits decreases Main issue: it should be possible to verify that the bits received so far are part of a valid signature Fixed-round protocols with trusted third party Impossibility result: no two-party protocol can be fair Reason: fair two-party exchange can be used to solve the distributed consensus problem Need TTP in case one of the parties misbehaves  
 
 
 
 

Contract Signing with Online TTP 

A 

B 

TTP 

signature 

signature 

contract 

contract 

Problem: TTP is the communication bottleneck

Can it be removed?

 
 
 
 
 

Fundamental Limitation 

(Very weak) consensus is not solvable if one or more processes can be faulty Fisher, Lynch, Paterson. 00mpossibility of Distributed Consensus with One Faulty Process00 J ACM (1985). Consensus problem in asynchronous setting Several processes want to agree on value of some bit Each process has initial 0 or 1, eventually 00ecides00i> on 0 or 1 Weak termination: some correct process decides Agreement: no two processes decide on different values Very weak validity: there is a run in which the decision is 0 and a run in which the decision is 1  
 
 
 
 

Partial Intuition for FLP Result 

Quote from paper:

   The asynchronous commit protocols in current use all seem to have a 00indow of vulnerability00 an interval of time during the execution of the algorithm in which the delay or inaccessibility of a single process can cause the entire algorithm to wait indefinitely. It follows from our impossibility result that every commit protocol has such a 00indow,00confirming a widely believed tenet in the folklore.

 
 
 
 
 

Optimistic Contract Signing 

Involve trusted third party only if something goes wrong Declares contract binding if presented with first two messages  

A 

B 

I am going to sign the contract 

I am going to sign the contract 

Here is my signature 

Here is my signature

 
 
 
 
 

Crypto Magic: Signature Escrows 

Ordinary escrow: OrdEsc(sigA(m),T) Similar to {sigA(m)}pk(T) T can extract sigA(m)  if formed correctly B can00 extract sigA(m) and can00 verify what00 inside Verifiable escrow: VerEsc(sigA(m),T) T can extract sigA(m) if formed correctly B can00 extract sigA(m) but can verify that A00 signature is inside and that T will be able to extract it  
 
 
 
 
Private contract signature PCSX(m,Y,T)

   is an implementation of verifiable signature escrow

Non-interactive zero-knowledge designated-verifier proof of convertible commitment to a signature with a designated converter Can be created only by X, but Y can simulate it Therefore, Y cannot use it as proof of X00 participation T can convert PCS into a universally

   verifiable signature sigX(m)

Y can verify that PCS sent by X can indeed be converted by T into X00 signature  

Outsider can00 distinguish

X00 private contract signature

from Y00 simulation  

Private Contract Signatures 

[Garay et al.]

 
 
 
 
 

A 

B 

                   PCSA(text,B,T) 

       PCSB(text,A,T) 

  sigA(text) 

  sigB(text) 
 

[Garay, Jakobsson, MacKenzie] 

Abuse-Free Contract Signing

 
 
 
 
 

Role of Trusted Third Party 

T can convert PCS to regular signature (00esolve00 If one of the parties stops communicating, the other party can ask T to convert PCS into signature T can issue an abort token (00bort00 Promise not to resolve protocol in future T acts only when requested by A or B Decides whether to abort or resolve on a first-come-first-served basis  
 
 
 
 

B 

A 

T 

r1 = PCSA(text,B,T), sigB(text)  

aborted?

    Yes:  r2 = sigT(a1)

     No:   resolved := true

              r2 = sigA(text)

              store sigB(text) 

r2 

          PCSA(text,B,T) 

??? 

         PCSB(text,A,T) 

sigT(a1) 

sigA(text) 

or 

Resolve Subprotocol 

If A stops communicating,

B asks T to convert A00 PCS,

but must reveal his own sig

 
 
 
 
 

A 

          ??? 

B 

T 

a1=sigA(m1,abort) 

a2 

resolved?

    Yes:  a2 = sigB(text)

     No:   aborted := true

              a2 = sigT(a1) 

   m1 = PCSA(text,B,T) 

sigB(text) 

sigT(a1) 

OR 

Abort Subprotocol 

A (but not B!) can ask T to abort

the protocol (i.e., to promise that

T won00 convert A00 PCS in future)  

This is not a guarantee that A won00 be able to obtain B00 signature by

executing the protocol

 
 
 
 
 

Desirable Properties 

Fairness Either both A & B get each other00 signature, or none do Timeliness Any party can terminate protocol by contacting TTP No advantage No party can unilaterally determine the outcome No provable advantage No party can prove that it has advantage Accountability If a party or TTP cheats, message trace provides evidence of cheating  
 
 
 
 

Fairness and Timeliness 

If A cannot obtain B00 signature, then

B should not be able to obtain A00 signature 

and vice versa 

Fairness 

One player cannot force the other to wait --

a fair and timely termination can always be

forced by contacting TTP 

Timeliness

 
 
 
 
 

No Advantage (Balance) 

No party should be able to unilaterally

determine the outcome of the protocol 

Stock sale example: there is a point in the protocol where

                             the broker can unilaterally choose

                             whether the sale happens or not 

This property can fail even if basic fairness is satisfied! 

Can a timely, optimistic protocol be fair AND balanced?

 
 
 
 
 

Example of Advantage 

Willing to sell stock at price X 

Ok, willing to buy at price X 

stock broker 

customer 

Must be able to ask TTP to 00bort00 this

instance of protocol, or will be stuck

indefinitely if customer does not respond 

Can go ahead and complete the sale, OR

can still ask TTP to 00bort00/font>

       (TTP doesn00 know customer has responded) 

Optimistically waits for broker to respond00/font> 

Chooses whether deal will happen:

   does not have to commit stock for sale,

   can cancel if sale looks unprofitable 

Cannot back out of the deal:

   must commit money for stock  

FLP 00indow of vulnerability00again!

 
 
 
 
 

Game-Theoretic Model 

Each protocol message is a game move Different sets of moves for different participants Four possible outcomes (for signature exchange) A has B00 signature, B has A00 signature A has B00 signature, B doesn00 have A00 signature, etc. Honest players follow the protocol Dishonest players can make any move permitted by the formal model Send any message they can compute Wait instead of responding Reason about players00game strategies  
 
 
 
 

Protocol as a Game Tree 

... 

... 

... 

... 

(Y,N) 

(Y,Y) 

(Y,Y) 

(N,Y) 

(N,Y) 

(N,N) 

Every possible execution of the protocol is a path in the tree Players alternate their moves First A sends a message, then B, then A 00/font> Adversary 00olded00into dishonest player Every leaf labeled by an outcome (Y,Y) if A has B00 signature and B has A00 (Y,N) if only A has B00 signature, etc. Natural concept of strategy Informally, strategy is a rule for responding to any move of the opponent A has a strategy for getting B00 signature if, for any move B can make, A has a response move such that the game always terminates in some leaf state labeled (Y,00  
 
 
 
 

Define Properties on Game Trees 

No leaf node is labeled (Y,N) or (N,Y) 

Fairness 

B never has a strategy to reach (Y,Y)

AND a strategy to reach (N,N) 

No advantage (for B) 

B cannot PROVE that

it has advantage 

No provable advantage (for B) 

Not trace-based properties (unlike secrecy and authentication) Very difficult to verify with symbolic analysis or process algebras  

... 

... 

... 

... 

(Y,N) 

(Y,Y) 

(Y,Y) 

(N,Y) 

(N,Y) 

(N,N)

 
 
 
 
 

Key Idea   (omitting many subtleties) 

Define 00ower00 of a signer (A or B) in state s

                      
 
 

if A can get contract by reading a message already in network or doing internal computation

if A can get contract by communicating with TTP, assuming B does nothing

otherwise 

PowerA(s) = 

2 

1 

0 

Look at optimistic transition s 00/sub> s00where PowerB(s00 =1 > PowerB(s) = 0       
 
 
 
 

Advantage is Unavoidable (Intuition) 

If PowerB(s) = 0 00/sub> PowerB(s00 =1 then00/sub> The move must have been performed by A A must have given B additional information that increased B00 power The move by A is not a message to TTP This is an optimistic protocol B could abort in state s Follows from timeliness, since B can00 get contract in s B can still abort in s00 so B has advantage! Intuition: T doesn00 know that B has received additional information from A, so B can lie to T  
 
 
 
 

Impossibility Result 

Dishonest party has advantage in any fixed-round, timely, optimistic fair exchange protocol Dishonest party always has a strategy for reaching a state where it can unilaterally choose the outcome Similar to FLP impossibility result for consensus Cryptography cannot help Bad news for e-commerce Honest party must commit merchandise or money, while dishonest party can still decide whether to go ahead with the deal Need a trusted party in every transaction  
 
 
 
 

00buse-Free00 As Good as It Gets 

No party should be able to unilaterally

determine the outcome of the protocol 

No advantage 

No party should be able to prove that

it can unilaterally determine

the outcome of the protocol 

Abuse-Free (No Provable Advantage) 

impossible 00/font> 

Achieved by Garay-Jakobsson-MacKenzie protocol

 
 
 
 
 

A 

B 

                   PCSA(text,B,T) 

       PCSB(text,A,T) 

  sigA(text) 

  sigB(text) 
 

[Garay, Jakobsson, MacKenzie] 

Abuse-Free Contract Signing 

A has advantage here, but he can00 use B00 PCS to prove that B is participating

(e.g., to solicit another bid)

 
 
 
 
 

B 

A 

T 

r1 = PCSA(text,B,T), sigB(text)  

aborted?

    Yes:  r2 = sigT(a1)

     No:   resolved := true

              r2 = sigA(text)

              store sigB(text) 

r2 

          PCSA(text,B,T) 

??? 

         PCSB(text,A,T) 

sigT(a1) 

sigA(text) 

or 

Resolve Subprotocol 

If A stops communicating,

B asks T to convert A00 PCS,

but must reveal his own sig

 
 
 
 
 

A 

          ??? 

B 

T 

a1=sigA(m1,abort) 

a2 

resolved?

    Yes:  a2 = sigB(text)

     No:   aborted := true

              a2 = sigT(a1) 

   m1 = PCSA(text,B,T) 

sigB(text) 

sigT(a1) 

OR 

Abort Subprotocol 

A (but not B!) can ask T to abort

the protocol (i.e., promise that he

won00 convert A00 PCS in future)

 
 
 
 
 

B 

PCSA(text,B,T),

sigB(text)  

sigT(abort) 

                 PCSA(text,B,T) 

               PCSB(text,A,T) 

T 

sigA(abort) 

sigT(abort) 

Leaked by T 

sigT(abort) AND sigB(text) 

only sigT(abort) 

Attack on Accountability

 
 
 
 
 

B 

PCSA(text,B,T),

PCSB(text,A,T) 

                 PCSA(text,B,T) 

               PCSB(text,A,T) 

T 

If T converts PCS into a

conventional signature,

T can be held accountable 

Repairing the Protocol

   download CS395T - Design and Analysis of Security Protocols