Transcript Trust calculus for PKI

Trust calculus for PKI
Roman Novotný, Milan Vereščák
Outline





PKI
Maurer deterministic model
Maurer probabilistic model
Maurer PKI on P2P
Roman continues with modeling in real world
Public key infrastructure (PKI)






PKI – complex distributed systems of the
end entities, CA, certificates, RA
Public key cryptography
Certificate issuance
Certificate validation
Certificate revocation
CA – trusted third party
Public key certification


Alice knows the public key of X (for verifying
the certificate) and is convinced of its
authenticity.
Alice trusts X to be honest and to correctly
authenticate the owner of a public key before
signing it.
X (CA)
Alice
Bob
Simple example

If Alice does not know an authentic copy of X's
public key, the first condition can be satisfied by
using a certificate for X's public key issued by
another entity Y.
Y (CA)
Alice
X (CA)
Bob
Maurer PKI deterministic
model
Requirements:
 Generality and expressive power.
 Precise Semantics.
 Evaluation order independence.
 Efficient implementation.
 Scalability.
 Easy usability.
Maurer model



Special type of logic
syntax: 4 formulas (statements)
Semantics: 2 inference rules
Example 1
Example 2
Probablistic Maurer model



True/false (trust/distrust)
This model measures validity on continuos
scale from 0 to 1
Every statement has assigned confidence
parameter
Example
PKI based on P2P network






Based on Chord: scalable p2p lookup
protocol
Chord p2p network consists of nodes
maps given key onto a node
Node identifier (e.g. IP address of node)
Key (e.g. filename)
Hash function maps both the key and the
node identifier into m-bit identifier
Algorithm for lookup


The mapping principle: each key is assigned to the
first existing node whose identifier is greater than or
equal to the identifier of the key.
Each node has finger table with m entries pointing to
m nodes
Finger table of node 8
Finger table of node 42
i
start-id
N8.finger[i]
i
start-id
N8.finger[i]
1
8+1=9
N14
1
42+1=43
N48
2
8+2=10
N14
2
42+2=43
N48
3
8+4=12
N14
3
42+4=46
N48
4
8+8=16
N21
4
42+8=50
N51
5
8+16=24
N32
5
42+16=58
N1
6
8+32=40
N42
6
42+32=10
N14
Searching

Requires maximum LogN steps, where N is a
number of nodes
Views




Nodes are used for storing statements
privateView: a set of private statements that
are not accessible from other nodes, only
local node can access them.
publicView: a set of message tokens that are
accessible to other nodes.
Message tokens consist of encrypted
message and index key associated to that
particular message.
Public messages

Public messages



Private messages



Certificate messages Cert(X, PX, Y, PY)
Recommendation messages Rec(X, PX, Y, i)
Authenticity statements Aut(X, PX)
Trust statements Trust(X, i)
Distributing is done according to p2p lookup
protocol and retrieving also using a Maurer
inference rules
Advantages of P2P model



load distribution: Hash function distributes
message tokens (public messages) uniformly
among the nodes.
scalability: We need Log(N) steps to retrieve
or publicate a message token of the total
number of N nodes.
fault resistance: This is because of
decentralized character of this model.
Improvement of model



Binding between public keys and certification
informations
Time – aware model
Validity template
Statements






Authenticity of binding - Aut(A,X,P,I)
Trust – Trust(A,X,D,I)
Certificates – Cert(X,Y,P,I)
Trust Transfers – Tran(X,Y,P,I)
Certification Validity Templates – Val(A,C,t)
Transfer Validity Templates – Val(A,T,t)
Derivation of new statements
X.509 and model



Set of property – subject’s name, issuer,
signature algorithm
Time interval – validity – not before, not after
Certification revocation list – Cert(X,0,L,I),
where 0 – empty set
Thanks for your
attention