Embed Size (px)
Citation preview
Cédric FournetMicrosoft Research, Cambridge
Ecole JEUNES Ecole JEUNES CHERCHEURS CHERCHEURS
en PROGRAMMATIONen PROGRAMMATION
6 au 17 juin 20056 au 17 juin 2005
Modèles formels Modèles formels de sécurité logiciellede sécurité logicielle
2eme partie2eme partie
Protocoles cryptographiques & pi Protocoles cryptographiques & pi calculcalcul
14h Modélisation de protocoles en pi calcul 16h Application: Services web et sécurité
Un Stage Chez Microsoft Research?
“Summer Internships” a Cambridgeen interlude pendant la thèse.
Objectif: boucler un projet de rechercheen 12 semaines avec un chercheur du labo
Candidatures avant février pour l’été 2006
http://research.microsoft.com/aboutmsr/jobs/internships/cambridge.aspx
Web Services Security& Protocol Verification
Cédric FournetMicrosoft Research, Cambridge
joint work with
Karthik Bhargavan, Andy Gordon, Greg O’Shea, Riccardo Pucella, Ricardo Corin
MSRC Samoa: Details, papers, tools, pointers at http://Securing.WS
Web Services and Formal Security
Two parallel trends: Rapid invention and deployment of XML-based
crypto protocols for securing web services Flexible message formats for interop Enables home-grown protocols New crypto protocols are often wrong, XML or not
Sustained and successful effort to develop formalisms and tools to verify crypto protocols
(Dolev&Yao, BAN,) FDR, Athena, Isabelle, ProVerif, …
At MSRC: spi, sjoin, Cryptyc, applied pi calculus, …
Timely opportunity to develop tools for validating standards-based XML crypto protocols
What’s a Web Service?
“A web service is a web site intended for use by computer programs instead of human beings.” (Barclay et al)
So XML not HTML
Service messages in SOAP format: Envelope/Header – addressing, security,
and transactional headers Envelope/Body – actual payload
Service metadata in WSDL format: For each SOAP endpoint, list of operations For each operation, request and response types
XMLXMLRequesReques
tt
Client
Server
XMLXMLResponsRespons
ee
(1) On the Public Internet Aim: outsource user-
interface to specialists
Specialist storefronts Ex: Products sold through
Amazon, but associate site gets commission
From Jul’02; 25k developers one year later
Specialist visualizations Ex: TouchGraph re
(2) Within a Private Intranet Aim: XML as common language to integrate
systems obtained from different vendors Ex: single service to calculate quotes uniformly
no matter how customer contacts an insurance company call centre sales force website
Today, biggest growth area for web services, in part because there are few new security concerns
(3) Between Private Intranets
Aim: support inter-institution workflows E-business transactions E-science grid
This is the hardest of the three cases to secure
Needs being addressed by crypto-based security specs Single sign-on: scientist may access 100 sites Federation: eg can company A permit just
certain company B employees to access shared service?
Delegation: eg can I permit online travel agent to consult my calendar service, make bookings?
Standards & Specifications “XML Web Services” refers to SOAP stack of
specifications: SOAP – message format
Syntax of request, response, fault messages WSDL – service description
Interface: function name, parameter and return types UDDI – service discovery
Search for service by attributes (like Yellow Pages) Not yet widely used in practice
BPEL4WS – service composition Programming language for automating business
processes, such as B2B order processing Some sort of merger of IBM WSFL, Microsoft XLANG, and
Sun WSCI … so quite complex …
A Sample SOAP Request
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"> <soap:Body> <GetOrder xmlns="http://microsoft.com/petshop"> <OrderId>20</orderId> </GetOrder> </soap:Body> </soap:Envelope>
Says: “get me status of order 20”
A Sample SOAP Request
<Envelope> <Body> <GetOrder> <OrderId>20</>
Says: “get me status of order 20”
XML not meant to be read by humans, so we’ll omit namespace info, and trailing brackets…
Another SOAP Request
<Envelope> <Header> <Action>http://bookshop/ws/OrderStatus</> <To>http://www.bookshop.com/ws/orderstatus.asmx</> <MessageId>uuid:5ba86b04-3c0f-428b-8dd6-17804286fe40</> <Body> <GetOrder> <OrderId>20</>
Optional headers tell SOAP processorswhat to do with the envelope (automatically)
Web Services: What’s New?
Though their core is roughly XML-encoded RPC – rather old! – what’s new about SOAP web services is the combination of:
Standards, Internet-scale, high-level tools
Signs of fervour, Wide support, easy to deploy OASIS and W3C
yet reasons for caution, Cost of SOAP encoding? Lack of SOAP security?
Web Services Security
The 2002 Security Story The 2002 best practice was to build secure web
services using an SSL transport
SSL gives transport- not application-level security Messages secured point-to-point not end-to-end Messages cannot securely be filtered or routed Messages not encrypted in files or databases
Party line (Web Services Security Roadmap) security within SOAP envelopes is better
Web Services Security SOAP level security aims to provide end-to-
end, compositional application-level security, independently of transport protocol
Fresh standards: Security Roadmap WS-Security, May 2004 (Draft: Apr 2002) WS-Trust, WS-SecureConversation,
WS-SecurityPolicy,…
A grammar for SOAP-based security protocols Automated processing of security headers Informal semantics except for XML syntax Security tokens = wire format for claims and
evidence Keys, certificates, x509 signatures, Kerberos tickets,…
<Envelope> <Header> <Security> <UsernameToken Id=1> <Username>“Alice" <Nonce>"mTbzQM84RkFqza+lIes/xw==" <Created>"2004-09-01T13:31:50Z" <Signature> <SignedInfo> <SignatureMethod Algorithm=hmac-sha1> <Reference URI=#2> <DigestValue>"U9sBHidIkVvKA4vZo0gGKxMhA1g=“ <SignatureValue>"8/ohMBZ5JwzYyu+POU/v879R01s=" <KeyInfo> <SecurityTokenReference> <Reference URI=#1 ValueType=UsernameToken> <Body Id=2> <StockQuoteRequest> <symbols> <Symbol>"FABRIKAM" <Symbol>"CONTOSO"
Securing SOAP MessagesUsernameToken
assumes both parties know Alice’s secret
password p
Each DigestValue is a cryptographic
hash of the URI target
hmacsha1(key, SignedInfo) where
keypsha1(p+nonce+created)
<Security> header defined by OASIS
WS-Security 2004 includes identity tokens,
signatures, encrypted message
parts
Dozens of implementations,
including Microsoft Web
Services Enhancements
(WSE)
Attacks on SOAP security Web services vulnerable to same sorts of attacks
as conventional websites Buffer overruns, denial of service, SQL injection, etc
New concerns: flexible, XML-based protocols Web services developers can design and deploy
their own application-specific security protocols XML message format open to rewriting attacks
Much like classic active attackers (Needham-Schroeder ’78)
Opponent can redirect, replay, modify, impersonate New: message processing is driven by a flexible,
semi-structured message format
Flexibility is usually bad for security We have found a range of problems in sample code,
thus motivating our research on theory and tools
An XML Rewriting Attack
From: AliceFrom: AliceTo: BookshopTo: BookshopAction: “Buy Charlie’s book”Action: “Buy Charlie’s book”(signed by Alice)(signed by Alice)
Alice’s laptop
Alice’s bookshop(Web Service)
Someoneon the net(Charlie?)
Sent: MondaySent: MondayFrom: AliceFrom: AliceTo: BankTo: BankAction: “Pay Charlie $20”Action: “Pay Charlie $20”(signed by Alice)(signed by Alice)
Sent: TuesdaySent: TuesdayFrom: AliceFrom: AliceTo: BankTo: BankAction: “Buy Charlie’s book”Action: “Buy Charlie’s book”(signed by Alice)(signed by Alice)
Sent: WednesdaySent: WednesdayFrom: AliceFrom: AliceTo: BookshopTo: BookshopAction: “Buy Charlie’s book”Action: “Buy Charlie’s book”(signed by Alice)(signed by Alice)
Alter and replay envelopesto confuse participants
Alice’s laptop
Alice’s bookshop(Web Service)
Someoneon the net(Charlie?)
Another XML Rewriting Attack
From: AliceFrom: AliceTo: BookshopTo: Bookshop“Publish this paper” “Publish this paper” (encrypted for bookshop)(encrypted for bookshop)(signed by Alice)(signed by Alice)
From: CharlieFrom: CharlieTo: BookshopTo: Bookshop“Publish this paper”“Publish this paper”(encrypted for bookshop)(encrypted for bookshop)(signed by Charlie)(signed by Charlie)
Take credit for someone else’s
data
A Signed SOAP Message Before...
<Envelope> <Header> <Security> <UsernameToken Id=2> <Username>Alice</> <Nonce>cGxr8w2AnBUzuhLzDYDoVw==</> <Created>2003-02-04T16:49:45Z</> <Signature> <SignedInfo> <Reference URI= #1><DigestValue>Ego0...</> <SignatureValue>vSB9JU/Wr8ykpAlaxCx2KdvjZcc=</> <KeyInfo> <SecurityTokenReference><Reference URI=#2/> <Body Id=1> <TransferFunds> <beneficiary>Bob</> <amount>1000</>
Message to bank’s web service says: “Transfer $1000 to Bob, signed
Alice”
Bank can verify the signature has been computed using key derived from Alice’s
secret password
and After an XML Rewriting Attack
<Envelope> <Header> <Security> <UsernameToken Id=2> <Username>Alice</> <Nonce>cGxr8w2AnBUzuhLzDYDoVw==</> <Created>2003-02-04T16:49:45Z</> <Signature> <SignedInfo> <Reference URI= #1><DigestValue>Ego0...</> <SignatureValue>vSB9JU/Wr8ykpAlaxCx2KdvjZcc=</> <KeyInfo> <SecurityTokenReference><Reference URI=#2/> <BogusHeader> <Body Id=1> <TransferFunds> <beneficiary>Bob</> <amount>1000</> <Body> <TransferFunds> <beneficiary>Charlie</> <amount>5000</>
Although Alice’s password has not been broken, the message now reads “Transfer
$5000 to Charlie, signed Alice”
Charlie has intercepted and rewritten this
message
The indirect signature of the body, now hidden in BogusHeader, may
still appear valid
A Long History of Attacks
A B
C
We assume that an intruder can interpose a computer on all communication paths, and thus can alter or copy parts of messages, replay messages, or emit false material.While this may seem an extreme view, it is the only safe one when designing authentication protocols.
Needham and Schroeder CACM (1978)
1978: N&S propose authentication protocols for “large networks of computers”1981: Denning and Sacco find attack found on N&S symmetric key protocol1983: Dolev and Yao first formalize secrecy properties wrt N&S threat model, using formal algebra1987: Burrows, Abadi, Needham invent authentication logic; neither sound nor complete, but useful1994: Hickman (Netscape) invents SSL; holes in v2, but v3 fixes these, very widely deployed1994: Ylonen invents SSH; holes in first versions, now very widely deployed1995: Abadi, Anderson, Needham, et al propose various informal “robustness principles”1995: Lowe finds insider attack on N&S asymmetric protocol; rejuvenates interest in FMscirca 1999: Several FMs for “D&Y problem”: tradeoff between accuracy and approximationcirca 2004: Many FMs now developed; several deliver both accuracy and automation
The Samoa Project: Tools If misconfigured or mis-implemented, WS-Security
protocols vulnerable to XML rewriting attacks
TulaFale — shows the absence of such attacksgiven a description of the protocol
An analysis tool for XML-based crypto protocols Automatic analysis of hand-written models via
applied pi calculus and Bruno Blanchet’s ProVerif tool
Policy generator/analyzer — produces TulaFalefrom declarative XML policy files that drive WSE 2.0
Hence, can directly analyze WSE 2.0 configurations Source-based formal verification of deployed
implementations of crypto protocols
Policy advisor — runs 35+ queries for securityerrors found in reviews of sample policies
TulaFale
TulaFale: a language for WS-Sec
OK, orNo because…
WSE 1.0 out of the box
What TulaFale does
CLR(IL)
SOAP processin
g
WSE 1.0ProVerif Analyzer
[B. Blanchet]
TulaFaleC# code
TulaFalescript
predicatelibrary
intermediate pi-calculus
We designed TulaFale, a programming
language to model WSE protocols and hand-wrote models for a
series of WSE protocols(POPL’04, FMCO’03)
TulaFale = pi + XML + predicates + assertions
Example: A Secure RPC A typical system model:
A single certification authority (CA) issuing X.509 public-key certificates for services, signed with the CA's private key.
Two servers, each equipped with a public key certified by the CA and exporting an arbitrary number of web services
Multiple clients, acting on behalf of human users
Threat model: an active attacker, in control of network, but knowing none of:
The private key of the CA The private key of any public key certified by the CA The password of any user in the database
Security goals: authentication of each message;and correlation of request and response; but not confidentiality
Client(kr,U) Server(sx,cert,S)
isMsg1(-,U,S,id1,t1,b1)
isMsg2(-,S,id1,id2,t2,b2)
begin C1 (U,S,id1,t1,b1)
end C1 (U,S,id1,t1,b1)
begin C2 (U,S,id1,t1,b1,id2,t2,b2)
end C2 (U,S,id1,t1,b1,id2,t2,b2)
An intended run of the protocol
Msg 1 includes signature of S,id1,t1,b1 under key derived from username
token for U
Msg 2 includes signature of
id1,id2,t2,b2 under public key of S
pi+XML+predicates+assertions
For example, this predicate is used
in two ways, to construct and parse Message 1
TulaFale messages are terms in a many-sorted algebra with
sorts:
TulaFale predicates defined by Horn
clauses with message patterns
pi+XML+predicates+assertions
TulaFale library includes
predefined predicates for XML
signatures and encryption
For example, this predicate uses these predicates to check
structure of Message 1
pi+XML+predicates+assertions
By sending a message on init, the attacker can
pick any payload and destination
Each end-event marksthe intent to accept a message as valid
Each begin-event marksthe intent to send a message
Messages are exchanged on a public SOAP channel
pi+XML+predicates+assertions
The implicit attacker, running in parallel, can: Send and receive on the soap channel Generate arbitrarily many users and services Initiate arbitrarily many sessions
Some Tulafale queries
We also run basic reachability queries (sanity checks)
We verify two correspondence properties from end-events to begin-event with matching contents (including both messages for C2)
TulaFale Demo
Automatic verification of following reachability and safety properties via TulaFale/ProVerif
OpponentClient(kr,U) Server(sx,cert,S)
isMsg1(-,U,S, id1,t1,b1)
Suppose a client does not sign the message identifier id1...
begin C1 (U,S,id1,t1,b1)
end C1 (U,S,id1,t1,b1)
id1:=id2, Replay isMsg1(-,U,S
, id2,t1,b1)
end C1 (U,S,id2,t1,b1)
Copy
Pair (id1,t1) uniquely identifies the message only if id1 and t1 are signed
We found and fixed faults like this in preliminary WSE samples
OpponentClient(kr,U) Server(sx,cert,S)
isMsg2(-,S,id1,
id2,t2,b2)
begin C2 (U,S,id1,t1,b1,id2,t2,b2)
end C2 (U,S,id1,t1’,b1’,id2,t2,b2)
If the client doesn’t generate fresh id1’s, then message correlation (C2) fails; the tool easily finds this bug
isMsg1(-,U,S, id1,t1,b1)
isMsg1(-,U,S, id1,t1’,b1’)
isMsg2(-,S,id1,
id2,t2,b2)
SOAP Fault
Call 1
Call 2, re-using
id1
What else might go wrong?
Opponent aka OClient(kr,u) Server(sx,cert,S)
isMsg2(-,S,id1,
id2,t2,b2)
begin C2 (O,S,id1,t1,b1’,id2,t2,b2)
end C2 (U,S,id1,t1,b1,id2,t2,b2)
If one or more passwords are compromised, there is an insider attack on message correlation; more
extensive changes to the script are needed to model this
isMsg1(-,U,S, id1,t1,b1)
isMsg2(-,S,id1,
id2,t2,b2)
isMsg1(-,O,S, id1,t1,b1’)
What about insider attacks?
Secure Conversations
A TulaFale case study WS-Security provides basic mechanisms to
secure SOAP traffic, one message at a time Signing and encryption keys derived from long-lived
secrets like passwords or private keys
If a SOAP interaction consists of multiple, related messages, WS-Security alone may be inefficient, and does not secure session integrity
Standard idea: establish short-lived session key
Recent specs describe this idea at the SOAP-level
WS-SecureConversation defines security contexts, used to secure sessions between two parties
WS-Trust defines how security contexts are issued and obtained
A Typical System
Client
STS
Service
1. RST
2. RSTR
3. “Session Exchanges”
SCsSCT
…
SC
Trust
SecureConv
STS = Security Token Server
RST = Request Security Token
RSTR = RST Response
SC = Security Context
SCT = SC Token
Open-Ended Conversations
Client Service
begin Cn
end Cn
begin C’n
end C’n
getSC get
SC
for n ¸ 0
We prove authentication forwhole sessions
We rely on some combination of manual and automated proofs
Discussion A formal analysis of WS-Trust and
WS-SecureConversation XML syntax and automation very effective,
against a demanding, realistic attacker model Approx 1000 lines of script – too large for manual
proofs
As is common, these specs: focus on message formats for interoperability are non-committal regarding security,
for example, no clear spec of contents of SCs
By making modes, data, and goals explicit, we found design and implementation bugs
Policy-Based Security
Security Policies Clients, services use XML files to pick security
mechanisms Located in same IIS virtual directory Describe protocols to use for different services Simple declarative description of deployed
protocols No need to look at messy C# code We analyze policy files collected from client and
servers Easy to get them wrong
Many policies are insecure Combination of policies may have unexpected
effects
<Policy Id=“Msg1"> <All> <Confidentiality> <TokenInfo> <SecurityToken> <TokenType>X509v3</> <Claims><SubjectName>S</></> <MessageParts>Body()</> <Integrity> <TokenInfo> <SecurityToken> <TokenType>UsernameToken</> <Claims><SubjectName>U</></> <MessageParts>Body() Header("To") Header("MessageId”)</>
Analyzing Policy Configurations
U’s pwd V’s pwd’
certkey
RegularWeb Service
TSecurity
Layer
U’s pwdcert
Client App
SecurityLayer
User UPremium
Web ServiceS
SecurityLayer
Web Server
V’s pwdcert
Client App
SecurityLayer
User V
Policy3.xmlPolicy4.xml
Policy1.xml Policy2.xml
Automated tools for collecting, parsing policies from IIS Servers, ClientsConfig = [Policy1, Policy2, Policy3, Policy4]
Modelling Security Policies
OK, orNo because…
Static warning
s
WSE 2.0 out of the box
What our tools do
CLR(IL)
SOAP processin
g
ProVerif(pi calculus)
TulaFale
C# code TulaFale script S(C(L),L)
predicatelibrary
Analyzer S(-,-)
In WSE 2.0, WS-SecurityPolicy files drive security; hence, we can
generate TulaFale directly from implementation files
(CCS’04)Generator C(-)
policy configC(L)
spec L of asecure link
WSE 2.0
Translating Policies to Predicates
<Policy Id="Msg1"> <All> <Confidentiality> <TokenInfo> <SecurityToken> <TokenType>X509v3</> <Claims><SubjectName>S</></> <MessageParts>Body()</> <Integrity> <TokenInfo> <SecurityToken> <TokenType>UsernameToken</> <Claims><SubjectName>U</></> <MessageParts>Body() Header("To") Header("MessageId")</>
predicate hasMsg1Policy(msg1:item,U:item,pwd:string, S:item,skS:bytes,id1:string,req:item) :- msg1 = <Envelope> <Header> <To>S</> <MessageId>id1</> <Security> utok sig1</></> <Body>b1</></>, isEncryptedData(b1,req,skS), isUserTokenKey(utok,U,pwd,skU), isSignature(sig1,"hmacsha1",skU, [<Body>b1</> <To>S</> MessageId>id1</>]).
Conjunction
Encryption RequirementSignature
Requirement
Security for All Generated Configs? Theorem: All policy configurations generated from link
specs enforce their security goals For all link specifications L, S(C(L),L) provides request &
response authentication, correlation, and secrecy. Hence, at least generated configs can be safely
deployed
Proof: Non-obvious: there are infinitely-many link specs Use combination of automated proofs and manual
reasoning Hint 1: Reduce to 4 base kinds of link-generated policies Hint 2: Prove that configs with all links enabled is secure
(programmed unfoldings in the pi calculus)
Security for Any Client Policy? Theorem: If a service uses a link-generated policy, then
irrespective of the client policies, the resulting configuration preserves request authentication and response secrecy
Hence, naïve clients cannot break service authentication
Proof: Combination of automated proofs and manual reasoning Hint: Even the weakest send policy preserves
secrecy of passwords and signing keys
Security in the field:a Policy Advisor for WSE
WSE 2.0 SP2 out of the box Our plugin
CLR(IL)
SOAP processin
g
codeC#/VB
staticqueries
securityreport
Advisor guesses intended goals and runs queries that check for:
(1)likely errors in configuration file settings
(2)conformance to conservative policy schema
(3)likely errors in (request,response,fault) mappings
(4)likely errors in particular policies
policy config
WSE 2.0
WSE Policy Advisor
Summary Web services security specs encourage extreme
flexibility Message formats, composable protocols, configurations Specs and implementations are only just emerging Attacks and proofs are subtle: tool support needed
We bridge the gap between theoretical pi threat modeland XML as used in WS security protocols
Put effort into real samples & implementations, found bugs Obtained theorems about wire-level protocols Exploited automation for authentication & secrecy
properties
We develop tools for the automated analysis ofsecurity for deployed systems based on crypto protocols
Proving protocols secure in isolation is not enough Our tools find attacks, verify configs, generate safe configs
Good place to develop formal tools, get positive results Standard message formats, composition, wide applicabilityDetails, papers, tools, pointers at http://Securing.WS
Related Work Going in the opposite direction to our policy analyzer,
several tools compile formal models to code: Strand spaces: Perrig, Song, Phan (2001), Lukell et al
(2003) CAPSL: Muller and Millen (2001) Spi calculus: Lashari (2002), Pozza, Sista, Durante (2004) Apparently, the resulting code cannot yet interoperate with
other implementations – an important future target Other Dolev-Yao modelling of web services
Type-based analysis of pre-WS-Security web services using Cryptyc: Gordon and Pucella (2002)
Model-checking of some example WS-Security specs using FDR, uncovering similar attacks: Kleiner & Roscoe (2004)
Other formalizations of XML and web services specs XPath, XSLT, XQuery: Wadler et al (since 1999) WS-RM: Johnson, Langworthy, Lamport, Vogt (2004)
