Transcript A Fine-Grained Access Control System for XML Documents

Daniel Moran & Marina Yatsina
Access control through encryption
Access control through encryption
 Publish data in such way that each client can only
see the appropriate parts.
Access control through encryption
example
<hospital>
<physician>
<administrative>
</administrative>
</physician>
<nurse>
<patientID>
</patientID>
<patientID>
</patientID>
</nurse>
</hospital>
Access control through encryption
example
<hospital>
<physician>
<administrative>
</administrative>
</physician>
<nurse>
<patientID>
</patientID>
<patientID>
</patientID>
</nurse>
</hospital>
<hospital>
<physician>
<administrative>
</administrative>
</physician>
safasfdsfdsgdsgdnml
gmpodsngnjyjnsbigfs
</hospital>
The physician
doesn’t see the
nurse’s information
Protections
example
The nurse doesn’t
see the physician’s
information
<hospital>
<physician>
<administrative>
</administrative>
</physician>
<nurse>
<patientID>
</patientID>
<patientID>
</patientID>
</nurse>
</hospital>
<hospital>
nvoidsnfnvodsnvonds
foinfbidpadmpnfosbgj
<nurse>
<patientID>
</patientID>
<patientID>
</patientID>
</nurse>
</hospital>
Access control through encryption
 Publish data in such way that each client can only
see the appropriate parts.
 Alternative to keeping data on servers and relying on
them for mediating between data and clients.
I’m a nurse
I’m a physician
<hospital>
<physician>
<administrative>
</administrative>
</physician>
<nurse>
<patientID>
</patientID>
<patientID>
</patientID>
</nurse>
</hospital>
Access control through encryption
 Publish data in such way that each client can only
see the appropriate parts.
 Alternative to keeping data on servers and relying on
them for mediating between data and clients.
 Avoids data duplication.
There is only one copy of the data, each
client sees the information in it based on
the set of keys he posses.
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations.
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
We need them to understand
the motivation
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations.
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
Protections
example
<hospital>
<physician>
<administrative>
</administrative>
</physician>
<nurse>
<patientID>
</patientID>
<patientID>
</patientID>
</nurse>
</hospital>
Protections
example cont.
<hospital>
<nurse>
<patientID>
<physician>
<patientID>
<administrative>
Protections
example cont.
K1
<hospital>
 K1  K3   K4
true
<nurse>
<physician>
K3
K4
<patientID>
<patientID>
K2
<administrative>
Protections
 XML tree in which nodes are guarded by positive
boolean formulas over a set of cryptographic keys.
K1
<hospital>
 K1  K3   K4
true
<nurse>
<physician>
K3
K4
<patientID>
<patientID>
K2
<administrative>
Protections cont.
 Accessing a node is conditioned by possessing a
combination of keys that satisfy the formula that
guards the node (and the formulas that guard its
If you don’t have K1
ancestors).
K
1
you can’t access any
of the nodes
<hospital>
 K1  K3   K4
true
<nurse>
<physician>
K3
<patientID>
K4
K2
<patientID> <administrative>
Protections cont.
 Formally: protection is a function that maps each
possible set of keys to the set of nodes that can be
accessed using those keys.
K1
K1 , K 2
<hospital>
 K1  K3   K4
true
<nurse>
<physician>
K3
hospital, physician,
administrative
<patientID>
K4
K2
<patientID> <administrative>
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
Security & data secrecy
 Adversary is given an arbitrary set of keys.
Security & data secrecy cont.
 The adversary select 2 documents which contain the
same information in the nodes he has access too
according to his keys .
<theSmurfs>
<gargamel />
<papaSmurf />
</theSmurfs>
<theSmurfs>
<gargamel />
<smurfette />
</theSmurfs>
Security & data secrecy cont.
 The adversary is given a partially encrypted
document that corresponds to one of its 2
documents.
<theSmurfs>
<gargamel />
dsdmhtkinhf
</theSmurfs>
Security & data secrecy cont.
 Security means that the adversary cannot decide
which of the 2 documents was used in creation of
the partially encrypted document (better than
picking randomly) .
?
<theSmurfs>
<theSmurfs>
<gargamel />
<gargamel />
<papaSmurf />
?
</theSmurfs>
<theSmurfs>
<gargamel />
<smurfette />
</theSmurfs>
dsdmhtkinhf
</theSmurfs>
Security & data secrecy cont.
 Security means that the adversary cannot decide
which of the 2 documents was used in creation of
the partially encrypted document (better than
picking randomly) .
 Meaning, partially encrypted document reveals no
information on the data in the nodes that should be
hidden from the adversary.
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations.
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
Motivation
 Bridge the gap between the abstract semantic of
protections and the use of actual keys and
(symmetric) encryption.
 Establish that if data is hidden according to
protection, then it is secret according to the
presented definition of secrecy.
<theSmurfs>
?
<gargamel />
dsdmhtkinhf
?
<theSmurfs>
<gargamel />
<papaSmurf />
</theSmurfs>
</theSmurfs>
<theSmurfs>
<gargamel />
<smurfette />
</theSmurfs>
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations.
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
XML
Protection
Normalized protection
Key shares
Basic notations - XML
example
<hospital>
<nurse>
<patientID>
<physician>
<patientID>
<administrative>
Basic notations - XML
 We describe XML tree as follows:
XML ::  Data   Data, XML, XML,..., XML 
 For example:
<hospital>
 hospital,  nurse,  patientID  ,  patientID  ,  physician,  administrative 
<nurse>
<patientID>
<patientID>
<physician>
<administrative>
Basic notations – Protection
 Lets recall:
K1
<hospital>
 K1  K3   K4
true
<nurse>
<physician>
K3
K4
<patientID>
<patientID>
K2
<administrative>
Basic notations – Protection cont.
 We describe protection tree as follows:
Prot ::  BData  , Cond   BData, Prot , Prot ,..., Prot  , Cond 
Cond :: true | false | Keys | Cond  Cond | Cond  Cond
BData :: Data  Keys  KeyShares  OR, AND
K1
<hospital>
Explanation in a
couple of K
slides
1  K3   K 4
true
<nurse>
<physician>
K3
K4
<patientID>
<patientID>
K2
<administrative>
Basic notations – Protection cont.
 For example:
HOSPITAL   hospital , NURSE _ PROT , PHYCISIAN _ PROT  , K1 


NURSE _ PROT   nurse,  patientID  , K3  ,  patientID  , K4  ,  K1  K3   K4 


PHYSICIAN _ PROT   physician,  administrative  , K2  , true




Basic notations – Normalized
protection
 In standard encryption schemes we can encrypt
under a single key but not under a boolean
combination of keys.
 Using simple transition we can rewrite any
protection into an equivalent normalized protection
where all formulas that guard a node are atomic.
Basic notations – Normallized
protection
 Lets recall:
K1
<hospital>
 K1  K3   K4
true
<nurse>
<physician>
K3
K4
<patientID>
<patientID>
K2
<administrative>
Basic notations – Normalized
protection cont.
K
1
<hospital>
true
true
OR
K1
K 51
true
K4
AND
K6
K3
K5
K 52
K6
<physician>
K6
K2
<nurse>
K3
<administrative>
K4
<patientID> <patientID>
Basic notations – Key shares
 We’ve split key K5 into 2 pieces K 51 , K 52 , each piece is
called key share.
 Key shares Ki1 , Ki2 ,..., Kin are pieces of information that
together allow the recovery of the key . K i
 No proper subset of key shares Ki1 , Ki2 ,..., Kin suffices
for computing K i .
 We define:


KeyShares  K ij Ki  Keys, j 1,..., n
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
Expression
Recoverable keys
Structure
Pattern
Pattern-protection semantics
Formal analysis - Expression
 Lets recall:
K1
<hospital>
true
true
OR
K1
K 51
true
K4
AND
K6
K3
K5
K 52
K6
<physician>
K6
K2
<nurse>
K3
<administrative>
K4
<patientID><patientID>
Formal analysis – Expression cont.
 We describe expressions as follows:
Exp :: BData |  Exp, Exp,..., Exp  | ExpKeys
 For example:
 nurse, paitentID
K3
,  paitentIDK
4

K6
K6
<nurse>
K3
K4
<patientID>
<patientID>
Formal analysis – Expression
cont.
 We use expressions for giving a precise definition of
how to map normalized protection to a partially
encrypted document.
K1
<hospital>
true
true
OR
K1
K51
<physician>
true
K4
AND
K6
<nurse>
<administrative>
K5
K3
K3
K 52
K6
K6
K2
K4
<patientID>
<patientID>
<hospital>
<physician>
<administrative>
</administrative>
</physician>
safasfdsfdsgdsgdnml
gmpodsngnjyjnsbigfs
</hospital>
Formal analysis – Expression
cont.
 We describe expressions as follows:
B  BData
P1 , P2 ,..., Pl
E   B  , true     B 



are
normalized protections

E  B, P1 , P2 ,..., Pl  , true  
K1
 B, E  P  , E  P  ,..., E  P  
E   B  , K     B 
1
2
l
<hospital>
K


 B, E  P  , E  P  ,..., E  P 
E  B, P1 , P2 ,..., Pl  , K  
1
2
l
 K1  K3   K4
true
<nurse>
<physician>
K K3
<patientID>
K4
K2
<patientID> <administrative>
Formal analysis – Expression
cont.
 For example:
HOSPITAL  hosp, OR _ EXP, PHYSICIAN _ EXPK

1
OR _ EXP  OR, AND _ EXP, K6 K , NURSE _ EXP

4
  , K  , K 
AND _ EXP  AND, K51
NURSE _ EXP 
K2
2
5 K
3
 nurse, paitentID
K3

6 K
5


,  paitentIDK
PHYSICIAN _ EXP  physician, administrativeK
2

4

K6
Formal analysis – Recoverable
keys
 A key is recoverable from expression E if it occurs in
clear (not encrypted) form, or if it’s encrypted under
 For example:

    , K 
E  AND, K51
K2
, K52
K3
Keys  E   K1 , K3 , K5 , K6 
recoverable  E   K1 , K3 
6 K
5
, K1 , K3 K
1

key symbols that occur in E or
their shares occur in E
Formal analysis – Structure
 We use structures to describe the structure of the
partially encrypted document.
K1
Data
<hospital>
true
true
true
OR
Data
KK1
KK511
true
true
K
K4
AND
Data
K66
KK3
KK5
KK521
KK6
<physician>
Data
K
K6
K2
<nurse>
Data
K
K3
<administrative>
Data
K4
<patientID>
Data <patientID>
Data
Formal analysis – Structure
 We describe structures as follows:
struct  Ki   K for all Ki  Keys
 
struct Ki j  K j for all Ki  Keys, j 1,..., n
struct  Di   D for all Di  Data
struct  OR   OR
struct  AND   AND
struct   E1 , E2 ,..., Em     struct  E1  , struct  E2  ,..., struct  Em  


struct EK  struct  E K for all K i  Keys
i
Formal analysis – Structure
cont.
 Lets recall:
K1
<hospital>
true
true
OR
K1
K 51
true
K4
AND
K6
K3
K5
K 52
K6
<physician>
K6
K2
<nurse>
K3
<administrative>
K4
<patientID><patientID>
Formal analysis – Structure
cont.
 Lets recall:
HOSPITAL
, OR
_ EXP
, PHYSICIAN
_ EXP
HOSPITAL hosp
D, OR
_ EXP
, PHYSICIAN
_ EXP
K K1

OR _ EXP   OR, AND _ EXP, K6KK, NURSE
, NURSE_ _EXP
EXP


4
 

AND _ EXP  AND, K51 , , KK252  , ,K
KK6 K
NURSE _ EXP 
   
K2
KK3
D, D, paitentID
, D  
 nurse
K

K

K
K3
5
,  paitentIDK
PHYSICIAN _ EXP  D
,  DK , administrativeK
physician
2

4

K6
Formal analysis – Pattern
 A pattern represents the information an expression
reveilles to the adversary.
K1
<hospital>
K1 , K 4
true
true
OR
K1
K 51
true
K4
AND
K6
K3
K5
K 522
K6
<physician>
K6
K2
<nurse>
K3
<administrative>
Data
K4
<patientID>
Data <patientID>
Formal analysis – Pattern
 We describe pattern that can be observed in Eusing
for decryption keys from T  Keys  E  as follows:
  B, T   B
   E1 , E2 ,..., Em  , T      E1 , T  ,   E2 , T  ,...,   Em , T  


 E , T     E , T 
 EK , T  struct  E K
i
Ki
Ki
i
if K i  T
if Ki  T
Formal analysis – Pattern cont.
 Lets recall:
K1
<hospital>
true
true
OR
K1
K 51
true
K4
AND
K6
K3
K5
K 51
K6
<physician>
K6
K2
<nurse>
K3
<administrative>
K4
<patientID><patientID>
Formal analysis – Pattern cont.
  HOSPITAL, K1 , K 4  
 Lets recall:
hosp, OR _ EXP
 hosp
, PHYSICIAN
, OR _ EXP_, PHYSICIAN
EXPK
_ EXPK
HOSPITAL
1
1

OR _ EXP  OR, AND _ EXP, K6 K , NURSE _ EXP

4
   


AND _ EXP  AND, K51 K , , KK52K , ,KKK6 K
NURSE _ EXP 
K
22
3 K3
5
5
 ,  paitentID
 ,  paitentID
   
 nurse,DpaitentID
K3

K3
K4

K6
PHYSICIAN _ EXP  physician, administrative
DK
K2
2
K4

K6
Formal analysis – Pattern cont.
 We describe patterns as follows:
pattern  E     E , recoverable  E  
 For example:
   , K  , K  , K 
pattern  AND _ EXP    AND, K  , K  , K 
AND _ EXP  AND, K51
K2
2
5 K
3
K2
6 K
5
2
5 K
3
3
K5
, K3

Formal analysis – Patternprotection semantics
 We can transform protections into cryptographic
expressions, and use patterns to provide an
equivalent semantics for protections.
 Formally: Let P be a normalized protection. For
any set of keys T  K1 , K 2 ,..., Kl   Keys  E  P   and any
Di  Data , it holds that Di can be accessed iff
occurs in pattern  E  P  , K1 , K 2 ,..., Kl  .
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
Results
Computational analysis - Results
 We can give concrete interpretation for expressions
and patterns as bit-strings.

  , K 
pattern  AND _ EXP   AND, K K , K52
2
K3
K5
, K3

10110100011011010110101
 This interpretations is computational because it
relies on computations on bit-strings.
Computational analysis - Results
 Expressions and patterns induce distributions on bit-
strings.
 These distributions are obtained by replacing data
symbols with bit-strings and implementing encryption
and key sharing with actual encryption and secret
sharing schemes.
Computational analysis - Results
 Patterns faithfully represent the information that
expressions reveal, even when expressions and
patterns are mapped to bit strings.
pattern  AND _ EXP 
10110100011011010110101
 Specifically, distribution ensembles associated with E
and pattern  E  are computationally indistinguishable.
Computational analysis - Results
 If some data is secret according to the abstract
semantics of protections, then that data is in fact
computationally hidden.
<theSmurfs>
?
<gargamel />
dsdmhtkinhf
?
<theSmurfs>
<gargamel />
<papaSmurf
/>
</theSmurfs>
<theSmurfs>
</theSmurfs>
<gargamel />
<smurfette />
</theSmurfs>
 However, attacker can still learn a great deal about the
length and even the structure of encrypted parts of the
document.
Agenda
 Protections.
 Security & data Secrecy.
 Motivation.
 Basic notations
 Formal analysis.
 Computational analysis.
 Summary & conclusions.
Summary & conclusions
 We saw justification for encryption-based techniques
for enforcing access policies for XML documents.
 Specifically, we saw that XML data that is secret
according to an abstract, symbolic semantics is indeed
secret with respect to a strong, computational notion
of security.