美國加州大學計算機網絡畢業dissertation定制SPINS: Security Protocols for Sensor Networks
Adrian Perrig, Robert Szewczyk, Victor Wen, David Culler, J. D. Tygar
Department of Electrical Engineering and Computer Sciences
University of California, Berkeley
fperrig, szewczyk, vwen, culler,

ABSTRACT
As sensor networks edge closer towards wide-spread deployment,security issues become a central concern. So far, much researchhas focused on making sensor networks feasible and useful, andhas not concentrated on security.
We present a suite of security building blocks optimized for resourceconstrainedenvironments and wireless communication. SPINS hastwo secure building blocks: SNEP and TESLA. SNEP providesthe following important baseline security primitives: Data confidentiality,two-party data authentication, and data freshness. Aparticularly hard problem is to provide efficient broadcast authentication,which is an 留學生dissertation網important mechanism for sensor networks.
TESLA is a new protocol which provides authenticated broadcastfor severely resource-constrained environments. We implementedthe above protocols, and show that they are practical even on minimalhardware: the performance of the protocol suite easily matchesthe data rate of our network. Additionally, we demonstrate that thesuite can be used for building higher level protocols.
1. INTRODUCTION
We envision a future where thousands to millions of small sensorsform self-organizing wireless networks. How can we provide securityfor these sensor networks? Security is not easy; comparedwith conventional desktop computers, severe challenges exist —these sensors will have limited processing power, storage, bandwidth,and energy.
Despite the challenges, security is important for these devices.As we describe below, we are deploying prototype wireless net-We gratefully acknowledge funding support for this research. This research wassponsored in part the United States Postal Service (contract USPS 102592-01-Z-0236), by the United States Defense Advanced Research Projects Agency (contractsDABT63-98-C-0038, “Ninja”, N66001-99-2-8913, “Endeavour”, and DABT63-96-C-0056, “IRAM”), by the United States National Science Foundation (grants FD99-
79852 and RI EIA-9802069) and from gifts and grants from the California MICROprogram, Intel Corporation, IBM, Sun Microsystems, and Philips Electronics. DARPAContract N66001-99-2-8913 is under the supervision of the Space and Naval WarfareSystems Center, San Diego. This paper represents the opinions of the authors and do
not necessarily represent the opinions or policies, either expressed or implied, of theUnited States government, of DARPA, NSF, USPS, or any other of its agencies, or anyof the other funding sponsors.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributedfor profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specific#p#分頁標題#e#
permission and/or a fee.Mobile Computing and Networking 2001 Rome, Italy
Copyright 2001 ACM X-XXXXX-XX-X/XX/XX ...$5.00.
work sensors at UC Berkeley. These sensors measure environmentalparameters and we are experimenting with having them controlair conditioning and lighting systems. Serious privacy questionsarise if third parties can read or tamper with sensor data. In thefuture, we envision wireless sensor networks being used for emergencyand life-critical systems – and here the questions of securityare foremost.
This paper presents a set of Security Protocols for Sensor Networks,SPINS. The chief contributions of this paper are:
 Exploring the challenges for security in sensor networks.
 Designing and developing TESLA (the “micro” version ofthe Timed, Efficient, Streaming, Loss-tolerant AuthenticationProtocol), providing authenticated streaming broadcast.
 Designing and developing SNEP (Secure Network EncryptionProtocol) providing data confidentiality, two-party dataauthentication, and data freshness, with low overhead.
 Designing and developing an authenticated routing protocolusing SPINS building blocks.Sensor Hardware
At UC Berkeley, we are building prototype networks of small sensordevices under the SmartDust program [32]. We have deployedthese in one of our EECS buildings, Cory Hall (see Figure 1).By design, these sensors are inexpensive, low-powerdevices. Asa result, they have limited computational and communication resources.
The sensors form a self-organizing wireless network (seeFigure 1) and form a multihop routing topology. Typical applicationsmay periodically transmit sensor readings for processing.
Our current prototype consists of nodes, small battery powereddevices, that communicate with a more powerful base station, whichin turn is connected to an outside network. Table 1 summarizesthe performance characteristics of these devices. At 4MHz, theyare slow and underpowered (the CPU has good support for bit andbyte level I/O operations, but lacks support for many arithmetic andsome logic operations). They are only 8-bit processors (note thataccording to [40], 80% of all microprocessors shipped in 2000 were
4 bit or 8 bit devices). Communication is slow at 10 Kbps.
The operating system is particularly interesting for these devices.
We use TinyOS [16]. This small, event-driven operating systemconsumes almost half of 8KB of instruction flash memory, leavingjust 4500 bytes for security and the application.
It is hard to imagine how significantly more powerful devicescould be used without consuming large amounts of power. The energysource on our devices is a small battery, so we are stuck with
relatively limited computational devices. Similarly, since communicationover radio will be the most energy-consuming function
CPU 8-bit, 4MHz
Storage 8KB instruction flash
512 bytes RAM
512 bytes EEPROM
Communication 916 MHz radio
Bandwidth 10Kilobits per second#p#分頁標題#e#
Operating System TinyOS
OS code space 3500 bytes
Available code space 4500 bytes
Table 1: Characteristics of prototype SmartDust nodesperformed by these devices, we need to minimize communicationsoverhead. The limited energy supplies create tensions for security:on the one hand, security needs to limit its consumption of processorpower; on the other hand, limited power supply limits the
lifetime of keys (battery replacement is designed to reinitialize deviceand zero out keys.) 1
Is Security on Sensors Possible?
These constraints make it impractical to use the majority of the current
secure algorithms, which were designed for powerful workstations.
For example, the working memory of a sensor node is insufficientto even hold the variables (of sufficient length to ensuresecurity) that are required in asymmetric cryptographic algorithms(e.g. RSA [35], Diffie-Hellman [8]), let alone perform operationswith them.
A particular challenge is broadcasting authenticated data to theentire sensor network. Current proposals for authenticated broadcastare impractical for sensor networks. Most proposals rely onasymmetric digital signatures for the authentication, which are impracticalfor multiple reasons (e.g. long signatures with high communicationoverhead of 50-1000 bytes per packet, very high overheadto create and verify the signature). Furthermore, previouslyproposed purely symmetric solutions for broadcast authenticationare impractical: Gennaro and Rohatgi’s initial work required over
1 Kbyte of authentication information per packet [11], and Rohatgi’simproved k-time signature scheme requires over 300 bytesper packet [36]. Some of the authors of this paper have also proposedthe authenticated streaming broadcast TESLA protocol [31].TESLA is efficient for the Internet with regular desktop workstations,
but does not scale down to our resource-starved sensor nodes.In this paper, we extend and adapt TESLA such that it becomespractical for broadcast authentication for sensor networks. We callour new protocol TESLA.
We have implemented all of these primitives. Our measurementsshow that adding security to a highly resource-constrained sensornetwork is feasible. The paper studies an authenticated routing protocoland a two-party key agreement protocol, and demonstratesthat our security building blocks greatly facilitate the implementationof a complete security solution for a sensor network.Given the severe hardware and energy constraints, we must becareful in the choice of cryptographic primitives and the securityprotocols in the sensor networks.
2. SYSTEM ASSUMPTIONS
Before we outline the security requirements and present our security
infrastructure, we need to define the system architecture and1Note that base stations differ from nodes in having longer-livedenergy supplies and having additional communications connectionsto outside networks.
Figure 1: Communication organization within a sensor network
at UC Berkeley’s Cory Hall. All messages are either destinedfor the base station or originate at the base station. Theroutes are discovered so that the number of hops is minimizedand the reliability of each connection is maximized.the trust requirements. The goal of this work is to propose a generalsecurity infrastructure that is applicable to a variety of sensornetworks.#p#分頁標題#e#
Communication Architecture
Generally, the sensor nodes communicate using RF, so broadcast isthe fundamental communication primitive. The baseline protocolsaccount for this property: on one hand it affects the trust assumptions,and on the other it is exploited to minimize the energy usage.
Figure 1 shows the organization of a typical SmartDust sensornetwork. The network forms around one or more base stations,which interface the sensor network to the outside network. Thesensor nodes establish a routing forest, with a base station at theroot of every tree. Periodic transmission of beacons allows nodes
to create a routing topology. Each node can forward a messagetowards a base station, recognize packets addressed to it, and handlemessage broadcasts. The base station accesses individual nodes
sing source routing. We assume that the base station has capabilitiessimilar to the network nodes, except that it has enough battery
power to surpass the lifetime of all sensor nodes, sufficient memoryto store cryptographic keys, and means for communicating withoutside networks.
In the sensor applications developed so far, there has been limited
local exchange and data processing. The communication patternswithin our network fall into three categories:
 Node to base station communication, e.g. sensor readings.
 Base station to node communication, e.g. specific requests.
 Base station to all nodes, e.g. routing beacons, queries or
reprogramming of the entire network.Our security goal is to address primarily these communication
patterns, though we do show how to adapt our baseline protocols toother communication patterns, i.e. node to node or node broadcast.
Trust Requirements
Generally, the sensor networks may be deployed in untrusted locations.While it may be possible to guarantee the integrity of theeach node through dedicated secure microcontrollers (e.g. [1] or
[7]), we feel that such an architecture is too restrictive and doesnot generalize to the majority of sensor networks. Instead, we assumethat individual sensors are untrusted. Our goal is to designthe SPINS key setup so a compromise of a node does not spread toother nodes.
Basic wireless communication is not secure. Because it is broadcast,any adversary can eavesdrop on the traffic, and inject newmessages or replay and change old messages. Hence, SPINS doesnot place any trust assumptions on the communication infrastructure,except that messages are delivered to the destination with nonzeroprobability.
Since the base station is the gateway for the nodes to communicatewith the outside world, compromising the base station canrender the entire sensor network useless. Thus the base stations area necessary part of our trusted computing base. Ourtrust setup reflectsthis and so all sensor nodes intimately trust the base station:at creation time, each node is given a master key which is sharedwith the base station. All other keys are derived from this key.Finally, each node trusts itself. This assumption seems necessaryto make any forward progress. In particular, we trust the local clockto be accurate, i.e. to have a small drift. This is necessary for theauthenticated broadcast protocol we describe in Section 5.#p#分頁標題#e#
Design Guidelines
With the limited computation resources available on our platform,we cannot afford to use asymmetric cryptography and so we usesymmetric cryptographic primitives to construct the SPINS protocols.
Due to the limited program store, we construct all cryptographicprimitives (i.e. encryption, message authentication code
(MAC), hash, random number generator) out of a single block cipherfor code reuse. To reduce communication overhead we exploitcommon state between the communicating parties.
3. REQUIREMENTS FOR SENSOR
NETWORK SECURITY
In this section, we formalize the security properties required bysensor networks, and show how they are directly applicable in atypical sensor network.Data Confidentiality
A sensor network should not leak sensor readings to neighboringnetworks. In many applications (e.g. key distribution) nodes communicatehighly sensitive data. The standard approach for keepingsensitive data secret is to encrypt the data with a secret key that onlyintended receivers possess, hence achieving confidentiality. Giventhe observed communication patterns, we set up secure channelsbetween nodes and base stations and later bootstrap other secure
channels as necessary.
Data Authentication
Message authentication is important for many applications in sensornetworks. Within the building sensor network, authentication isnecessary for many administrative tasks (e.g. network reprogramming
or controlling sensor node duty cycle). At the same time, an
adversary can easily inject messages, so the receiver needs to makesure that the data used in any decision-making process originatesfrom the correct source. Informally, data authentication allows a
receiver to verify that the data really was sent by the claimed sender.In the two-party communication case, data authentication can beachieved through a purely symmetric mechanism: The sender and
the receiver share a secret key to compute a message authenticationcode (MAC) of all communicated data. When a message with acorrect MAC arrives, the receiver knows that it must have beensent by the sender.
This style of authentication cannot be applied to a broadcast setting,without placing much stronger trust assumptions on the networknodes. If one sender wants to send authentic data to mutuallyuntrusted receivers, using a symmetric MAC is insecure: Any oneof the receivers knows the MAC key, and hence could impersonatethe sender and forge messages to other receivers. Hence, we needan asymmetric mechanism to achieve authenticated broadcast. Oneof our contributions is to construct authenticated broadcast fromsymmetric primitives only, and introduce asymmetry with delayedkey disclosure and one-way function key chains.
Data Integrity
In communication, data integrity ensures the receiver that the receiveddata is not altered in transit by an adversary. In SPINS,we achieve data integrity through data authentication, which is astronger property.
Data Freshness#p#分頁標題#e#
Given that all sensor networks stream some forms of time varyingmeasurements, it is not enough to guarantee confidentiality and
authentication; we also must ensure each message is fresh. Informally,data freshness implies that the data is recent, and it ensuresthat no adversary replayed old messages. We identify two types offreshness: weak freshness, which provides partial message ordering,but carries no delay information, and strong freshness, whichprovides a total order on a request-response pair, and allows fordelay estimation. Weak freshness is required by sensor measurements,while strong freshness is useful for time synchronizationwithin the network.
4. NOTATION
We use the following notation to describe security protocols andcryptographic operations in this paper.
A;B are principals, such as communicating nodes
NA is a nonce generated by A (a nonce is an unpredictablebit string, usually used to achieve freshness).
M1 jM2 denotes the concatenation of messagesM1 andM2
KAB denotes the secret (symmetric) key which is shared between
A and B
fMgKAB is the encryption of messageM with the symmetric
key shared by A and B.
fMghKAB;IV i denotes the encryption of message M, with
key KAB, and the initialization vector IV which is used in
encryption modes such as cipher-block chaining (CBC), output
feedback mode (OFB), or counter mode (CTR) [9, 21,
22].
By a secure channel, we mean a channel that offers confidentiality,data authentication, integrity, and freshness.
5. SPINS SECURITY BUILDING BLOCKS
To achieve the security requirements we established in Section 3we have designed and implemented two security building blocks:
SNEP and TESLA. SNEP provides data confidentiality, two-partydata authentication, integrity, and freshness. TESLA provides authenticationfor data broadcast. We bootstrap the security for bothmechanisms with a shared secret key between each node and thebase station (see Section 2). We demonstrate in Section 8 how wecan extend the trust to node-to-node interactions from the node-tobase-station trust.
SNEP: Data Confidentiality, Authentication, Integrity,and Freshness
SNEP provides a number of unique advantages. First, it has lowcommunication overhead since it only adds 8 bytes per message.Second, like many cryptographic protocols it uses a counter, but
we avoid transmitting the counter value by keeping state at bothend points. Third, SNEP achieves even semantic security, a strongsecurity property which prevents eavesdroppers from inferring themessage content from the encrypted message. Finally, the samesimple and efficient protocol also gives us data authentication, replayprotection, and weak message freshness.
Data confidentiality is one of the most basic security primitivesand it is used in almost every security protocol. A simple formof confidentiality can be achieved through encryption, but pure encryptionis not sufficient. Another important security property issemantic security, which ensures that an eavesdropper has no informationabout the plaintext, even if it sees multiple encryptionsof the same plaintext [12]. For example, even if an attacker hasan encryption of a 0 bit and an encryption of a 1 bit, it will nothelp it distinguish whether a new encryption is an encryption of 0or 1. The basic technique to achieve this is randomization: Beforeencrypting the message with a chaining encryption function(i.e. DES-CBC), the sender precedes the message with a randombit string. This prevents the attacker from inferring the plaintext ofencrypted messages if it knows plaintext-ciphertext pairs encryptedwith the same key.#p#分頁標題#e#
However, sending the randomized data over the RF channel requiresmore energy. So we construct another cryptographic mechanismthat achieves semantic security with no additional transmissionoverhead. Instead, we rely on a shared counter between thesender and the receiver for the block cipher in counter mode (CTR)(as we discuss in Section 6). Since the communicating parties sharethe counter and increment it after each block, the counter does notneed to be sent with the message. To achieve two-party authenticationand data integrity, we use a message authentication code(MAC).The combination of these mechanisms form our Sensor NetworkEncryption Protocol SNEP. The encrypted data has the followingformat: E = fDghKencr;Ci, where D is the data, the encryptionkey is Kencr, and the counter is C. The MAC is M =MAC(Kmac; CjE). We derive the keys Kencr and Kmac from themaster secret key K as we show in Section 6. The complete messagethat A sends to B is:
A ! B : fDghKencr;Ci; MAC(Kmac; CjfDghKencr;Ci)SNEP offers the following nice properties: Semantic security: Since the counter value is incremented aftereach message, the same message is encrypted differentlyeach time. The counter value is long enough that it neverrepeats within the lifetime of the node. Data authentication: If theMAC verifies correctly, a receivercan be assured that the message originated from the claimedsender. Replay protection: The counter value in the MAC preventsreplaying old messages. Note that if the counter were notpresent in the MAC, an adversary could easily replay messages. Weak freshness: If the message verified correctly, a receiverknows that the message must have been sent after the previous
message it received correctly (that had a lower countervalue). This enforces a message ordering and yields weakfreshness.
 Low communication overhead: The counter state is kept ateach end point and does not need to be sent in each message.2
Plain SNEP provides weak data freshness only, because it onlyenforces a sending order on the messages within node B, but noabsolute assurance to node A that a message was created by B inresponse to an event in node A.
Node A achieves strong data freshness for a response from node
B through a nonce NA (which is a random number sufficiently longsuch that it is unpredictable). Node A generates NA randomly andsends it along with a request message RA to node B. The simplestway to achieve strong freshness is for B to return the noncewith the response message RB in an authenticated protocol. However,instead of returning the nonce to the sender, we can optimizethe process by using the nonce implicitly in the MAC computation.
The entire SNEP protocol providing strong freshness for B’sresponse is:
A ! B : NA;RA
B ! A : fRBghKencr;Ci; MAC(Kmac;NAjCjfRBghKencr;Ci)If the MAC verifies correctly, node A knows that node B generatedthe response after it sent the request. The first message canalso use plain SNEP if confidentiality and data authentication areneeded.#p#分頁標題#e#
TESLA: Authenticated Broadcast
Current proposals for authenticated broadcast are impractical forsensor networks. First, most proposals rely on asymmetric digitalsignatures for the authentication, which are impractical for multiple
reasons. They require long signatures with high communicationoverhead of 50-1000 bytes per packet, very high overhead to createand verify the signature. Even previously proposed one-time signatureschemes that are based on symmetric cryptography (one-wayfunctions without trapdoors) have a high overhead: Gennaro andRohatgi’s broadcast signature based on Lamport’s one-time signature
[20] requires over 1 Kbyte of authentication information perpacket [11], and Rohatgi’s improved k-time signature scheme requiresover 300 bytes per packet [36].
The recently proposed TESLA protocol provides efficient authenticatedbroadcast [31, 30]. However, TESLA is not designedfor such limited computing environments as we encounter in sensornetworks forthree reasons.
First, TESLA authenticates the initial packet with a digital signature.Clearly, digital signatures are too expensive to compute onour sensor nodes, since even fitting the code into the memory is amajor challenge. For the same reason as we mention above, onetimesignatures are a challenge to use on our nodes.
Standard TESLA has an overhead of approximately 24 bytes perpacket. For networks connecting workstations this is usually notsignificant. Sensor nodes, however, send very small messages thatare around 30 bytes long. It is simply impractical to disclose theTESLA key for the previous intervals with every packet: with 642In case the MAC does not match, the receiver can try out a fixed,
small number of counter increments to recover from message loss.
In case the optimistic re-synchronization fails, the two parties engagein a counter exchange protocol, which uses the strong freshness
protocol described below.bit keys and MACs, the TESLA-related part of the packet would beconstitute over 50% of the packet.
Finally, the one-way key chain does not fit into the memory ofour sensor node. So pure TESLA is not practical for a node tobroadcast authenticated data.
We design TESLA to solve the following inadequacies of TESLAin sensor networks:
 TESLA authenticates the initial packet with a digital signature,which is too expensive for our sensor nodes. TESLAuses only symmetric mechanisms.
 Disclosing a key in each packet requires too much energy forsending and receiving. TESLA discloses the key once perepoch.
 It is expensive to store a one-way key chain in a sensor node.
TESLA restricts the number of authenticated senders.
TESLA Overview
We give a brief overview of TESLA, followed by a detailed description.As we discussed in Section 3, authenticated broadcast requires
an asymmetric mechanism, otherwise any compromised receivercould forge messages from the sender. Unfortunately, asymmetriccryptographic mechanisms have high computation, communication,and storage overhead, which makes their usage on resourceconstraineddevices impractical. TESLA overcomes this problemby introducing asymmetry through a delayed disclosure of symmetrickeys, which results in an efficient broadcast authenticationscheme.#p#分頁標題#e#
For simplicity, we explain TESLA for the case where the basestation broadcasts authenticated information to the nodes, and wediscuss the case where the nodes are the sender at the end of thissection.
TESLA requires that the base station and nodes are looselytime synchronized, and each node knows an upper bound on themaximum synchronization error. To send an authenticated packet,the base station simply computes a MAC on the packet with a keythat is secret at that point in time. When a node gets a packet, it canverify that the corresponding MAC key was not yet disclosed bythe base station(based on its loosely synchronized clock, its maximumsynchronization error, and the time schedule at which keysare disclosed). Since a receiving node is assured that the MAC keyis known only by the base station, the receiving node is assuredthat no adversary could have altered the packet in transit. The nodestores the packet in a buffer. At the time of key disclosure, the basestation broadcasts the verification key to all receivers. When a nodereceives the disclosed key, it can easily verify the correctness of thekey (which we explain below). If the key is correct, the node cannow use it to authenticate the packet stored in its buffer.
Each MAC key is a key of a key chain, generated by a publicone-way function F. To generate the one-way key chain, the senderchooses the last key Kn of the chain randomly, and repeatedly applies
F to compute all other keys: Ki = F(Ki+1). Each node caneasily perform time synchronization and retrieve an authenticatedkey of the key chain for the commitment in a secure and authenticatedmanner, using the SNEP building block. (We explain moredetails in the next subsection).Example
Figure 2 shows an example of TESLA. Each key of the key chaincorresponds to a time interval and all packets sent within one timeinterval are authenticated with the same key. The time until keys ofa particular interval are disclosed is 2 time intervals in this example.K0 K1 K2 K3 K4
F F F F
P1 P2 P3 P4 P5 P6 P7
time
Figure 2: Using a time-released key chain for source authentication.
We assume that the receiver node is loosely time synchronized and
knowsK0 (a commitment to the key chain) in an authenticated way.
Packets P1 and P2 sent in interval 1 contain a MAC with key K1.
Packet P3 has a MAC using key K2. So far, the receiver cannot
authenticate any packets yet. Let us assume that packets P4, P5,
and P6 are all lost, as well as the packet that discloses key K1, so
the receiver can still not authenticate P1, P2, or P3. In interval 4
the base station broadcasts keyK2, which the node authenticates by
verifying K0 = F(F(K2)), and hence knows also K1 = F(K2),
so it can authenticate packets P1, P2 with K1, and P3 with K2.
Instead of adding a disclosed key to each data packet, the key
disclosure is independent from the packets broadcast, and is tied to
time intervals. Within the context of TESLA, the sender broadcasts#p#分頁標題#e#
the current key periodically in a special packet.
TESLA Detailed Description
TESLA has multiple phases: Sender setup, sending authenticated
packets, bootstrapping new receivers, and authenticating packets.
For simplicity, we explain TESLA for the case where the base
station broadcasts authenticated information, and we discuss the
case where nodes send authenticated broadcasts at the end of this
section.
Sender setup The sender first generates a sequence of secret
keys (or key chain). To generate the one-way key chain of length
n, the sender chooses the last key Kn randomly, and generates
the remaining values by successively applying a one-way function
F (e.g. a cryptographic hash function such as MD5 [34]):
Kj = F(Kj+1). Because F is a one-way function, anybody
can compute forward, e.g. compute K0; : : : ;Kj given Kj+1, but
nobody can compute backward, e.g. compute Kj+1 given only
K0; : : : ;Kj , due to the one-way generator function. This is similar
to the S/Key one-time password system [14].
Broadcasting authenticated packets Time is divided into time
intervals and the sender associates each key of the one-way key
chain with one time interval. In time interval t, the sender uses the
key of the current interval, Kt, to compute the message authentication
code (MAC) of packets in that interval. The sender will then
reveal the key Kt after a delay of Æ intervals after the end of the
time interval t. The key disclosure time delay Æ is on the order of a
few time intervals, as long as it is greater than any reasonable round
trip time between the sender and the receivers.
Bootstrapping a new receiver The important property of the
one-way key chain is that once the receiver has an authenticated key
of the chain, subsequent keys of the chain are self-authenticating,
which means that the receiver can easily and efficiently authenticate
subsequent keys of the one-way key chain using the one authenticated
key. For example, if a receiver has an authenticated value
Ki of the key chain, it can easily authenticate Ki+1, by verifying
Ki = F(Ki+1). Therefore to bootstrap TESLA, each receiver
needs to have one authentic key of the one-way key chain as a commitment
to the entire chain. Another requirement of TESLA is
that the sender and receiver are loosely time synchronized, and that
the receiver knows the key disclosure schedule of the keys of the
one-way key chain. Both the loose time synchronization as well
as the authenticated key chain commitment can be established with
a mechanism that provides strong freshness and point-to-point authentication.
A receiver sends a nonce in the request message to the
sender. The sender replies with a message containing its current
time TS (for time synchronization), a key Ki of the one-way key#p#分頁標題#e#
chain used in a past interval i (the commitment to the key chain),
and the starting time Ti of interval i, the duration Tint of a time interval,
and the disclosure delay Æ (the last three values describe the
key disclosure schedule).
M ! S : NM
S ! M : TS j Ki j Ti j Tint j Æ
MAC(KMS; NM j TS j Ki j Ti j Tint j Æ)
Since we do not need confidentiality, the sender does not need to
encrypt the data. The MAC uses the secret key shared by the node
and base station to authenticate the data, the nonce NM allows the
node to verify freshness. Instead of using a digital signature scheme
as in TESLA, we use the node-to-base-station authenticated channel
to bootstrap the authenticated broadcast.
Authenticating broadcast packets When a receiver receives the
packets with the MAC, it needs to ensure that the packet could not
have been spoofed by an adversary. The threat is that the adversary
already knows the disclosed key of a time interval and so it could
forge the packet since it knows the key used to compute the MAC.
Hence the receiver needs to be sure that the sender did not disclose
the key yet which corresponds to an incoming packet, which
implies that no adversary could have forged the contents. This is
called the security condition, which receivers check for all incoming
packets. Therefore the sender and receivers need to be loosely
time synchronized and the receivers need to know the key disclosure
schedule. If the incoming packet satisfies the security condition,
the receiver stores the packet (it can verify it only once the
corresponding key is disclosed). If the security condition is violated
(the packet had an unusually long delay), the receiver needs
to drop the packet, since an adversary might have altered it.
As soon as the node receives a keyKj of a previous time interval,
it authenticates the key by checking that it matches the last authentic
key it knows Ki, using a small number of applications of the
one-way function F: Ki = F
j