David Nuñez
email: dnunez@lcc.uma.es

Isaac Agudo

Javier Lopez

The Fallout of Key Compromise in a Proxy-Mediated Key Agreement Protocol

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Nguyen, Oualha, and Laurent presented at ESORICS 2016 an authenticated key agreement protocol based on an ad-hoc variant of symmetric proxy re-encryption [START_REF] Nguyen | Authenticated key agreement mediated by a proxy re-encryptor for the internet of things[END_REF], called AKAPR. This protocol is intended for highly-constrained IoT devices, and therefore, deliberately excludes the use of asymmetric primitives such as Diffie-Hellman key exchange due to its reliance on modular exponentiations. The proposed protocol is implemented on top of block ciphers, MACs, and simple modular arithmetic. The authors provide a formal verification of the mutual authentication property using ProVerif.

In this paper we identify some deficiencies in the proposed protocol that were not considered by the formal analysis and describe several attacks that exploit them. In particular, our attacks exploit the fact that encryption and decryption operations do not use secret keys directly, but intermediate secret values (which we call "encryption tokens"). These secrets are relatively exposed throughout the protocol and can be used to compromise the security of their corresponding owners (and in certain cases, other users). We show how compromise of these encryption tokens (or directly, of secret keys) makes it possible to break forward security and lead to key compromise impersonation attacks. An interesting (and devastating) consequence of the nature of these attacks is that these cannot be prevented even if the affected user renews his secret key, given that the compromised secret can be linked to the encryption token of other users. This paper constitutes an example of how providing a formal analysis of a protocol or system is often not enough, since this may be incomplete, incorrectly designed or directly flawed. In the case of the analyzed protocol, the authors did not consider the possibility of key compromise. However, in IoT environments (which is the target application of the protocol), key compromise is a realistic risk due to the broad attack surface of most devices, which includes physical attacks (e.g., use of JTAG and UART interfaces, power analysis, etc.), software vulnerabilities (e.g., buffer over-reads like Heartbleed in OpenSSL), privilege escalation through backdoor accounts, etc.

Related work The protocol we analyze in this paper is an example of authenticated key exchange (AKE), one of the most recurring topics in the literature when it comes to security protocols. It is also the basis for most Internet applications that relay on secure channels, as it is embedded in TLS and IPSEC. We can clearly distinguish two research trends in this area, one based on public-key cryptography, where Diffie-Hellman [START_REF] Diffie | New directions in cryptography[END_REF] is the current "standard", and the other on secret key cryptography. With respect to the latter, most proposals rely on a Key Distribution Center (KDC) that shares a secret key with all users in the system and supports them on agreeing on a session key. Since 1978, when the Needham-Schroeder symmetric protocol [START_REF] Needham | Using encryption for authentication in large networks of computers[END_REF] was proposed, several authors have attempted to propose better symmetric AKE protocols, usually showing how previous ones can be attacked and fixing their weaknesses. For example, one of the weaknesses of the original Needham-Schroeder protocol was the inability to prove the freshness of the session key. Denning and Sacco [START_REF] Denning | Timestamps in key distribution protocols[END_REF] proposed the use of Timestamps as a way fix this problem. Later, the Kerberos protocol [START_REF] Neuman | Kerberos: An authentication service for computer networks[END_REF], also built on the idea of using timestamps, was proposed as the current "standard" AKE solution in the symmetric set-up. In the last years, new assumptions on the capabilities of the attackers have been defined as well as new application scenarios, security requirements and constrains that make this problem still an interesting research topic, particularly in those environment where public-key cryptography is not viable. Some recent works show that Elliptic Curve Cryptography (ECC) can be run in most wireless sensor platforms [START_REF] Liu | On emerging family of elliptic curves to secure internet of things: Ecc comes of age[END_REF], although there are still some highly-constrained devices, such as passive RFID, that are not yet capable of using PKC and would then require the use of symmetric AKE protocols.

The analyzed protocol uses techniques from proxy re-encryption (PRE). This is a research topic with increasing popularity, with new use cases arising in different contexts (e.g, data sharing in the cloud, key management, etc.). Although the vast majority of PRE schemes are based on public-key cryptography [START_REF] Nuñez | Proxy re-encryption: Analysis of constructions and its application to secure access delegation[END_REF], there have been some proposals based on symmetric cryptography. Syalim et al. [START_REF] Syalim | Realizing proxy re-encryption in the symmetric world[END_REF] propose a symmetric PRE scheme based on the All-Or-Nothing Transform, although it assumes that both sender and receiver share a common secret. Cook and Keromytis [START_REF] Cook | Conversion functions for symmetric key ciphers[END_REF] present a solution based on a double-encryption approach, but as in the previous case, a priori shared keys are needed. The key-homomorphic PRF primitive by Boneh et al. [START_REF] Boneh | Key homomorphic prfs and their applications[END_REF] can be used to construct symmetric PRE schemes without the shared key requirement, although as noted by Garrison et al. [START_REF] Garrison | On the practicality of cryptographically enforcing dynamic access control policies in the cloud[END_REF], its computational cost is comparable or greater than traditional publickey cryptography. Sakazaki et al. [START_REF] Sakazaki | Study of re-encryption scheme based on symmetric-key cryptography[END_REF] propose a symmetric PRE scheme that is essentially equivalent to the one of this paper; this is discussed further in Section 2.1.

Organization The rest of this paper is organized as follows: In Section 2, we describe the AKAPR protocol in detail, including actors, protocol flow and the underlying symmetric proxy re-encryption primitive. In Section 3, we present several attacks and weaknesses of the AKAPR protocol. In Section 4, we discuss some possible alternatives to the protocol. Finally, Section 5 concludes the paper.

Description of the Authenticated Key Agreement Protocol

In this section we briefly describe the protocol AKAPR (Authenticated Key Agreement mediated by a Proxy Re-Encryptor). The goal of this protocol is to provide an authenticated key exchange between two entities, using a proxy entity as a mediator. As in the general case of proxy re-encryption, although the proxy entity assists in the process, it should not learn any information.

A critical restriction that guides the design of this protocol is that it assumes that the authenticating entities may not be capable of using common publickey cryptography primitives, such as Diffie-Hellman key exchange and digital signatures, due to the its reliance on modular exponentiations. Instead, AKAPR is designed solely on top of block ciphers, MACs, and simple modular arithmetic.

In the remaining of this section we first briefly explain the underlying symmetric proxy re-encryption primitive. Next, we describe the general setting of the protocol, which includes the description of actors, network architecture and trust assumptions. Finally, we detail the protocol flow.

Symmetric proxy re-encryption primitive

The authors propose a symmetric proxy re-encryption algorithm, which is composed of the following five functions:

-KeyGen(λ): On input the security parameter λ, the key generation algorithm KeyGen outputs the secret key sk and identity id. As an example, for user A, these are sk A and id A . -ReKeyGen(sk A , id A , sk B , id B ): On input the secret keys sk A and sk B , and identities id A and id B , the re-encryption key generation algorithm ReKeyGen computes the re-encryption key between users A and B as rk We note that there is a previous proposal by Sakazaki et al. [START_REF] Sakazaki | Study of re-encryption scheme based on symmetric-key cryptography[END_REF], further discussed in [START_REF] Watanabe | Representative system and security message transmission using re-encryption scheme based on symmetric-key cryptography[END_REF], which is essentially equivalent to this symmetric proxy reencryption scheme. The only difference is that the original proposal by Sakazaki et al. uses the XOR operator instead of the modular multiplication. If instantiated correctly, both of them are equivalent, security-wise; however, Sakazaki et al.'s choice of the XOR operator can be implemented more efficiently than modular multiplication.

A→B = h(sk A id B ) -1 • h(sk B id A ) -1 ,
Additionally, we also remark that this symmetric proxy re-encryption scheme is not consistent with the prevalent idea of proxy re-encryption, where the sender does not need to know a priori the identity of the intended recipient. In this scheme, the sender fixes the recipient identity during encryption, and therefore, the resulting ciphertext can only be re-encrypted to this identity. In contrast, in the traditional idea of proxy re-encryption (regardless if it is public-key or symmetric), ciphertexts can be re-encrypted for any possible recipient, as long the corresponding re-encryption key exists. Although, for simplicity, we will continue to refer to this scheme as symmetric proxy re-encryption, we believe that it is actually some kind of multiparty encryption, where the sender and the proxy jointly create a ciphertext decryptable by an a priori fixed recipient.

Protocol setting

There are three main types of actors in the AKAPR protocol, which are the following:

-The Initiator (I) and the Responder (R), which are two entities located in separate subnetworks and that want to establish an authenticated session between them. It is assumed that these entities may lack the capacity to use asymmetric primitives such as Diffie-Hellman, which requires modular exponentiation, and therefore will only use symmetric techniques. Note, however, that a regular device can also participate in this protocol. -The Delegatee1 (D), which mediates in the key agreement protocol between the Initiator and the Responder, without being able to learn the negotiated session keys.

-The Key Distribution Center (KDC), which initially generates all the secret keys and necessary re-encryption keys, and distributes them (secret keys to entities, and re-encryption keys to the delegatee).

Trust assumptions

The protocol has the following trust assumptions:

-The Delegatee is assumed to be honest-but-curious, which means it behaves correctly with respect to the protocol, but at the same time, it has an interest in reading the underlying information. We will latter show that if this assumption is relaxed (e.g., an attacker gains control of the delegatee, or simply, the delegatee cooperates with him), it makes several attacks possible.

-The Key Distribution Center is fully trusted. It is clear that, given that the KDC knows all the keys involved, it can gain full control of the network. The existence of an omniscient KDC can be seen as a single point of failure, precisely for this reason [START_REF] Menezes | Handbook of applied cryptography[END_REF]Remark 13.3].

AKAPR Protocol Flow

We begin this subsection by defining some of the notation used in the protocol.

Recall that one of the principal requirements is to use only symmetric encryption primitives. In particular, the protocol requires an authenticated encryption user A to B can be seen as the delegation of decryption rights from a "delegator" A to a "delegatee" B. However, for consistency with the analyzed protocol, we will also refer to it as "delegatee".

scheme, denoted by AEnc, and a message authentication code MAC. The protocol assumes that each principal X has a shared key with the delegatee D, namely K XD . This key is used to provide authenticity and integrity of communications between the principal and the delegatee. In addition, it also assumes that both initiator and responder maintain two counters for the communication between them, in order to protect against replay attacks. These counters are labeled CT IR and CT RI , respectively. Additionally, nonces N I and N R are used to ensure freshness of messages; a session identifier SID also contributes towards this goal. Table 1 summarizes the notation used in this paper. The AKAPR protocol is composed of 4 messages. In the the first two messages, the delegatee acts as intermediary between the initiator and responder, while the third and fourth messages are directly between them. Figure 2 shows the flow of messages of the protocol. Next, we describe these messages in detail.

Initiator I M 1 M 2 M 3 M 4 Delegatee D Responder R Fig. 2: Protocol flow Message 1 (I → D).
The first message of the protocol, M 1 , is created by an initiator I and sent to the responder R, via the delegatee D. The initiator performs the following steps:

1. CT IR ← CT IR + 1 2. SID ← H(id I id R w), for a random w 3. N I R ← -Z p , t R ← -Z p 4. AK ← KDF(id I , id R , t) 5. AE 1 ← AEnc AK (SID id I id R N I CT IR ) 6. C 1 ← t • h(sk I id R ) 7. M1 ← SID id I id R AE 1 C 1 8. M 1 ← M1 MAC K ID ( M1 ) Message 2 (D → R).
Once the delegatee D receives a message from an initiatior I, he performs the following procedure in order to verify the validity of the message and to generate the message for responder R, namely M 2 .

1. Verify that SID is not repeated and that MAC in M 1 with key

K ID ; if failed, abort the protocol. 2. C 2 ← rk I→R • C 1 3. M2 ← SID id I id R AE 1 C 2 4. M 2 ← M2 MAC K RD ( M2 )
Note that after the re-encryption performed by the delegatee, the value of

C 2 is t • h(sk R id I ) -1 .
Message 3 (R → I). When the responder R receives the previous message from the delegatee D, he also verifies its validity, proceeds to decrypt it and extract the necessary information, as described below. Finally, he produces a new message M 3 that is sent directly to the initiator I, without intermediaries. Note that at the end of this process, the responder already knows the agreed session key K S .

1. Verify MAC in M 2 with key K RD ; if failed, abort the protocol.

2. t ← h(sk R id I ) • C 2 3. AK ← KDF(id I , id R , t) 4. SID id I id R N I CT IR ← ADec AK (AE 1 ) 5. Check that CT IR ≥ CT RI ; if failed, abort the protocol. 6. CT RI ← CT IR + 1 7. N R R ← -Z p 8. K S ← KDF(CT RI , id I , id R , N I , N R ) 9. M 3 ← AEnc AK (SID id R id I N I t N R CT RI )
Message 4 (I → R). When the initiator I receives the response from the responder R, he follows the procedure below to verify its validity and extract the necessary information. He produces a final message M 4 that is sent directly to the responder R, who verifies its validity using the previously generated session key K S .

1. SID id R id I N I t N R CT RI ← ADec AK (M 3 ) 2.
Check that SID, N I and t correspond to the original ones sent in M 1 , and that CT RI = CT IR + 1; if failed, abort the protocol.

3. K S ← KDF(CT RI , id I , id R , N I , N R ) 4. M 4 ← SID MAC K S (SID id I id R N I N R )
As a final remark, we note that the authors do not describe any procedure for the initial key distribution.

Attacks to the AKAPR Protocol

In this section we describe several attacks and weaknesses of the AKAPR protocol. Most of them stem from the use of encryption tokens as intermediate values for encryption and decryption, as well as the possibility of obtaining an encryption token associated to another user by means of the delegatee or analysis of past protocol traffic. This is particularly problematic in the event of compromise of long-term secret keys, to the point that even key revocation and update does not allow the affected user to recover the guarantees of secrecy and authentication with respect to other users. In the Appendix, we also show how the choice of an insecure keyed-hash construction can lead to length-extension attacks, which combined with our previous attacks, can be used to mount complex attack scenarios.

Breaking Forward Secrecy

A first and simple attack to this protocol is to recover previous session keys from past traffic, once the long-term secret of a user is leaked. The security goal we are breaking in this case is forward secrecy, formally defined as follows:

Definition 1 (Forward secrecy [START_REF] Boyd | Protocols for authentication and key establishment[END_REF]). A protocol provides forward secrecy if compromise of the long-term keys of a set of principals does not compromise the session keys established in previous protocol runs involving those principals.

For this type of attack, we assume that an attacker has collected the messages of the protocol for one or several runs, and that, at a latter stage, he is able to get access to the secret key of the responder. The goal is to recover previous session keys. In the case of the AKAPR, the attacker proceeds as follows:

1. The attacker stores the protocol messages for one or several rounds. For simplicity, let us assume he stores the traffic for only the run he wants to extract its session key. 2. At some point, the attacker compromises the responder R and obtains his long-term secret key sk R . 3. From message M 2 of the stored protocol run, he parses t • h(sk R id I ) -1 and extracts t, since he can compute h(sk R id I ). The value t is used to compute the encryption key AK ← KDF(id I , id R , t)

4. From message M 3 , the attacker can decrypt the values N R , N I and CT IR using the key AK computed in the previous step. 5. The attacker computes the session key K S used during the stores run as described in the protocol:

K S = KDF(CT RI , id I , id R , N I , N R )
Therefore, it can be seen this protocol does not fulfill forward secrecy. We note that if the attacker compromises the initiator I instead, then the attack is the same except for step 3, where he uses sk I to extract t from t • h(sk

I id R ), contained in message M 1 .
Countermeasure The messages M 1 and M 2 are transmitted over an authenticated channel using MACs, with pre-shared MAC keys K ID and K RD , respectively. A possible countermeasure to the previous attack is to assume additional encryption keys for securing the confidentiality of the channel, given that the assumption of pre-shared keys already exists. However, if attackers were able to compromise the secret key of one user, it is reasonable to assume that the corresponding MAC key is potentially leaked too.

Key Compromise Impersonation Attacks

The previous subsection was devoted to attacking forward secrecy, a common concern of protocol designers. There are, however, other kinds of attacks that are not that well known, but can be potentially more hazardous. Key compromise impersonation (KCI) attacks occur when an adversary gains access to the secret key of a principal, and uses it to establish a session with him impersonating a different user. The attacker may use this session to actively gain new knowledge about the victim or causing him harm (e.g., by sending him malware), as the victim believes he is communicating with a legitimate user [START_REF] Chalkias | Two types of key-compromise impersonation attacks against one-pass key establishment protocols[END_REF]. Therefore, KCI attacks can be more dangerous than breaking forward secrecy, which is limited to passive eavesdropping of past and future traffic. The following is a more formal definition of KCI, adapted from [START_REF] Strangio | On the resilience of key agreement protocols to key compromise impersonation[END_REF].

Definition 2 (Key compromise impersonation).

A key agreement protocol is vulnerable to key compromise impersonation (KCI) if compromise of the longterm key of a specific user allows the adversary to establish a session key with that user by masquerading as a different user.

Here we describe three types of KCI attacks, although it may be possible that other variations exist. For the first two KCI attacks, we assume that the attacker compromises the secret key of one user and tries to impersonate an initiator I (which may be any user in the system chosen by the attacker); therefore, the victim acts as the responder R. Since the attacker needs to direct the attack via the delegatee, he needs at least one of the pre-shared MAC keys: either the key K RD between the delegatee D and the responder R, or the key K ID between the delegatee and the impersonated user I. The two first KCI attacks differ on which MAC key is compromised. Finally, we also identify a third KCI attack that occurs in the opposite situation, when the attacker tries to impersonate a responder. Although in this case the attacker has to wait for a key agreement request from the victim (which can be forced by an out-of-band action), this attack is much easier to achieve, since it does not require any MAC key. Fig. 3: Flow of KCI attacks KCI Attack 1 If the attacker knows sk R and K RD then the strategy to impersonate an initiator I is to produce a message M 2 (i.e., the second message of the AKAPR protocol, which is between the delegatee and the responder), since this message does not depend on any secret from user I; the only requirement is to chose a counter value high enough. The responder R will accept this message as coming from user I via the delegatee, as depicted by Figure 3b, since its authenticity can be checked with K RD . The attacker now only has to continue the protocol to establish a session key between him and R, although R thinks the session is between him and I. This attack works even in the attacker does not know sk R , but only h(sk R id I ). The initial assumption of the attacker knowing K RD is reasonable given he has access to sk R .

KCI Attack 2

If the attacker knows sk R and K ID then the attacker needs to know also h(sk I id R ) in order to impersonate an initiator I. There are different ways to achieve this:

-A first option is to use past protocol traffic between R and I in order to extract this value, following a strategy similar to the forward secrecy attack: Knowing sk R enables the attacker to compute the t value from the messages of a protocol run, which in turn, can be used to extracth(sk I id R ) from message M 1 .

-A second option is to trick the delegatee into delivering this value by means of the re-encryption function, basically using it as a re-encryption oracle 2 . In order to do this, the attacker initiates a key agreement protocol between R and I, where C 1 is the component of message M 1 with value t • h(sk R id I ). Next, he captures the response M 2 of the delegatee and parses the re-encrypted component C 2 . Finally, he computes h(sk

I id R ) = t • (C 2 ) -1 .
-A third option is to assume that the attacker colludes with the delegatee (or even that the attacker is the delegatee). In this case, h(sk I id R ) can be computed from the re-encryption keys since rk I→R = h(sk

I id R ) -1 • h(sk R id I ) -1 .
In addition, the assumption of knowing K ID is natural.

Once the attacker knows h(sk I id R ), he initiates a normal key agreement protocol with R via the delegatee, as shown in Figure 3b, using K ID for computing the MAC for the first message. Note that the attacker can participate successfully in this key agreement since he does not need to know the secret sk I , but the encryption token h(sk I id R ). As a final comment on this attack, note that it works even if the attacker initially does not know sk R , but only the encryption token h(sk R id I ).

KCI Attack 3

Previous KCI attacks supposed that the leaked secret was of a user who later acted as the responder. Suppose now that the secret key of an initiator I is leaked. Figure 3c shows the protocol flow of this attack, where the attacker acts as the responder R. An attacker that knows the secret key sk I of the initiator can impersonate any user R if he is able to obtain h(sk R id I ). As in the KCI attack 2, there are several ways to do this:

-Previous traffic between I and R. Knowing sk I enables the attacker to compute the t value from the messages of a protocol run, which in turn, can be used to compute h(sk R id I ) from message M 2 . -Using the delegatee as a re-encryption oracle. This requires knowledge of K ID . -Assuming that the attacker controls the delegatee, colludes with it, or the corresponding re-encryption key is leaked somehow.

Once the attacker knows h(sk R id I ), he can respond to normal key agreement requests from I. As in previous KCI attacks, the attacker succeeds without actually knowing the secret sk R , but the encryption token h(sk R id I ); similarly, this attack works even if the attacker only knows the encryption token h(sk I id R ) at the beginning.

As a final remark, KCI attacks 1 and 2 required the additional knowledge of one of the pre-shared MAC keys, since in both of them the attacker impersonated an initiator, whose messages are required to be validated, and therefore, is performing a proactive impersonation. On the contrary, in this KCI attack the attacker impersonates a responder, which implies that the impersonation is reactive in this case (i.e., it requires that the initiator I starts the key agreement). This can be achieved either by waiting for a key agreement request to occur or by forcing it using some out-of-band mechanism (e.g., hard-resetting the initiator's device, social engineering, etc.).

Limited Scope of Key Revocation and Update

An interesting, yet not immediate, takeaway of the previous attacks is that they exploit the following undesired properties of the protocol: (1) encryption tokens can replace long-term secret keys, and (2) associated encryption tokens (e.g., h(sk I id R ) and h(sk R id I )) can be linked with each other through valid protocol messages. These issues are problematic when long-term secret keys are compromised, as illustrated by the attacks we identified.

A natural action that the affected principal performs once he becomes aware of the compromise of his secret key, is to initiate some kind of key revocation/update procedure. In principle, one can believe that key revocation is an effective countermeasure against a long-term key compromise event. However, we show next that this is not the case: once the long-term key of a user is compromised, and even after key revocation and update is realized, the protocol still remains vulnerable with respect to forward secrecy and key compromise impersonation, for all users whom the affected user communicated before. This is a consequence of the two undesired properties described above.

Breaking forward secrecy As an illustration, suppose that the responder R updates his secret key to sk R after his previous long-term secret sk R is exposed, revokes previous re-encryption keys and asks for their update. In order for the protocol to be correct, the new re-encryption keys should be of the form rk I→R = h(sk I id R ) -1 • h(sk R id I ) -1 , for all possible initiators I. Note that the term h(sk I id R ) does not change with respect to the previous re-encryption key, and therefore, the initiator I still uses this same encryption token when participating in a key agreement with the responder R. The consequence of this is that an attacker that was able to break forward secrecy before can extract h(sk I id R ) from previous rounds of the protocol, since h(sk I id R ) has not changed. Using this encryption token, the attacker can compute the corresponding t value from the first message of the protocol (i.e., M 1 ) of any future round, and break forward secrecy again.

Key Compromise Impersonation Suppose now that it is an initiator I who updates his secret key to sk I . Analogously to the previous case, it is still possible for an attacker to recover h(sk R id I ) from previous traffic between I and any other user R. However, in this case, the attacker does not limit himself to passively eavesdrop protocol messages as above (i.e., breaking forward secrecy), but can actively impersonate the responder R, given that he knows the value h(sk R id I ) necessary to decrypt message M 2 . Notice how updating the secret key of I does not have any effect on the encryption token that protects the second message of the protocol.

Countermeasures The only possible countermeasures against this problem are either to issue a new identity for the affected user or to revoke also the users that established communications with him previously. Both options do not seem adequate nor practical.

Discussion

The previous attacks demonstrated that the main weaknesses of the AKAPR protocol is that the encryption tokens are, in fact, long-term secrets, just as the secret keys, and that the encryption tokens between two users can be linked to each other. These problems make it possible for an attacker to perpetually threaten the security goals of the protocol once he gains control of an encryption token. In this section we informally discuss some possible amendments to this protocol.

First, we note that if we assume that the initiator I is also capable of reading Message 2 (from the delegatee D to the responder R), then this means he can extract the encryption token h(sk R id I ). This is a plausible assumption in several settings compatible with this protocol (e.g., wireless environments), and it is also consistent with the philosophy of the Dolev-Yao model [START_REF] Dolev | On the security of public key protocols[END_REF], by which one can consider the network to be open and all its messages public and subject to scrutiny by other entities. Therefore, it can be seen that this is functionally equivalent to the initiator I knowing this encryption token. Given that this encryption token is implicitly known by the responder (since he can generate it), then it acts as a sort of shared key between them. Therefore, a possible variation of the protocol is to simply distribute this encryption token to the initiator when he wants to commence a key agreement with responder R. This can be realized by transforming the delegatee D into a mere key server that distributes these encryption tokens to initiators. Therefore, instead of the delegatee re-encrypting Message 1 into Message 2, which requires it to know a re-encryption key linking two encryption tokens, he stores the "shared encryption tokens".

Note that this variation is still compatible with achieving the goal of secrecy with respect to the delegatee, simply by encrypting these encryption tokens with the secret key of the corresponding initiator. Therefore, re-encryption keys stored by the delegatee D are replaced by encryptions of encryption tokens. Specifically, each rk I→R is substituted by an encrypted key ek I→R = Enc sk I (h(sk R id I )). Note that this implies that ek I→R = ek R→I , and therefore, this doubles the number of keys managed by the delegatee D; nevertheless, this number is still of quadratic order (since it is necessary to store a key between each pair of users of the system), dominated by the number of users. This new type of keys eliminates the link between encryption tokens, reducing this way the applicability of some of the attacks we propose (although not completely). An interesting insight about this variation is that it is extremely similar to the traditional Needham-Schroeder symmetric key agreement protocol [START_REF] Needham | Using encryption for authentication in large networks of computers[END_REF], with the main difference that in this case the key server (i.e., the delegatee) does not know the session keys because these are encrypted by a separate key server (i.e., the KDC).

However, it is important to note that this variant still suffers from the longterm nature of encryption tokens. An improvement to this respect could be to include a timestamp in the encryption token generation, in a similar way than Kerberos [START_REF] Neuman | Kerberos: An authentication service for computer networks[END_REF] improves over Needham-Schroeder protocol. Thus, encryption tokens would be of the form h(sk A id B T i ), where T i represents a time period. Although this could mitigate the attacks to a certain extent (since compromised encryption tokens would only be useful for a given time period), it also implies that the re-encryption keys should be recomputed by the KDC and distributed to the delegatee on each time period. This can represent a great inconvenience in some settings.

Conclusions

Proxy re-encryption (PRE) is a hot research topic nowadays, with new use cases arising in different contexts. Most PRE schemes are based on public-key cryptography, mostly because public key cryptography has become omnipresent in most environments. PRE schemes using symmetric cryptography would make an excellent contribution for IoT scenarios where devices are highly constrained, but it is true that properly capturing the essence of PRE and providing secure solutions in the same sense as in the public-key world is challenging.

In this paper we show how difficult is to properly define and implement PRE in the symmetric world by exploring the weaknesses of a particular scheme proposed at ESORICS 2016. This protocol tries to adapt previous proposals for symmetric key PRE to the IoT scenario, focusing not only on providing a lighter solution (not involving public-key cryptography) but also trying to avoid redundant messages that are needed in well-know and deeply-studied authentication and key exchange protocols (e.g., Needham-Schroeder).

Unfortunately the paper fails to accomplish its goals, mainly because of the use of two immutable encryption tokens for every pair of communicating parties that depend only on the secret keys of the initiator and the identity of the responder (and vice versa). The way the protocol is designed implies that compromising the secrets of one party allows to obtain the encryption token of the other party, which can be used to mount key compromise impersonation attacks and break forward security. Moreover, revocation of compromised keys turns out to be ineffective, which makes the protocol unusable in it present form.

where id BE = "Bob Esponja"4 . For the sake of illustration, let us ignore the internal padding pad for the moment.

As discussed in Section 3.2, an attacker that knows h(sk A id BE ) can impersonate A in a key agreement with BE without knowing sk A , regardless if he acts as an initiator or a responder. The length-extension attack is particularly worrisome when the attacker has access to previous traffic, or the delegatee is compromised or deceived by the attacker; in this case, the delegatee can be used in combination with the attack strategies presented in previous sections in order to compromise the security of non-involved users. For example, let us suppose that an attacker gains access to the private key of user B. Figure 4 shows combination of some of the attacks described in this paper that eventually compromise the security of key agreements between users A and BE. An attacker that knows sk B can trivially generate encryption tokens h(sk A id B ) associated to any other user A; knowing this, he can compute the opposite encryption tokens using strategies discussed in previous attacks (e.g., using the delegatee as an encryption oracle, compromising the delegatee, analyzing previous traffic between A and B). The resulting encryption tokens can be used as input to length-extension attacks, undermining this way the security of other users. The output of the length-extension attacks are also encryption tokens, which in turn, can be used again to obtain more encryption tokens. Therefore, it can be seen how the initial leakage of B's secret can potentially affect key agreements between other users, since once the attacker obtains h(sk A id BE ) and h(sk BE id A ), he can potentially control all their past and future key agreements. Note that, although BE is some user whose identity has id B as prefix (i.e., the choice of BE is not completely free), A is an arbitrary user, which is a serious threat to the application of this protocol in a real setting.

We next describe some possible attack scenarios that apply this strategy in combination with others of the previously identified attacks. In particular, we illustrate two scenarios: the first is reminiscent of sybil attacks in distributed networks, where a malicious entity gains control of multiple identities in order to increase its control over a system or network; the second is similar to a spear phishing attack, where the attacker targets specific victims aided by relevant, yet fake, contextual information that gains the trust of the victim.

Sybil-like attack scenario

The goal of the attacker in this scenario is to gain as much encryption tokens as possible, each of them associated to a different identity, and to start multiple key agreements with a victim A, who will believe is communicating with different entities. In particular, the idea is to obtain encryption tokens between A and fresh "pseudonyms" (all of them with the same prefix in order to exploit the length-extension vulnerability, as described before).

Length-extension attack

Using the delegatee, analysis of previous traffic, ...

Fig. 4: Abstract flow of a length-extension attack

We initially assume either that the attacker is a legitimate user (e.g., user B), or that he gained access to the secret sk B of some user B; this does not matter from the point of view of the attack. Now, he can set up a sybil attack against any user A of his choosing as follows, also represented in Figure 5. First, knowledge of sk B allows to compute h(sk B id A ) trivially; next, using the techniques described for previous attack strategies, the attack obtains the opposite encryption token h(sk A id B ). Now he proceeds to launch the lengthextension attack against this hash value, by appending random i values to the end of id B , obtaining as a result hashes of the form h(sk A id B pad i). Therefore, fresh pseudonyms will be identities of the form id Bi = id B pad i. Note that in this case the internal padding pad that is necessary for the length-extension attack is not necessarily a problem (e.g., if identities have a numerical format); the only important requirement from the point of view of the sybil attack is that identities id Bi are different from each other.

Finally, using once again the techniques for obtaining the opposite encryption token, the attacker eventually obtains a set of encryption tokens of the form h(sk Bi id A ), for different i values, which enable him to mount a sybil-like attack against entity A. The attacker can now start multiple key agreements with the victim A, making him believe that there are several independent entities B i , which in fact are controlled uniquely by the attacker.

Spear phishing scenario Suppose that an attacker gains access to sk B , where id B is a common but dangerous prefix (e.g., "Bank"). Once again, following the previously discussed strategies, the attacker can obtain the encryption tokens between a victim A and user B, namely h(sk A id B ), and later use this hash value to derive new encryption tokens involving a tailored bait whose name starts with "Bank" (e.g., "Bank of America"). Recall that the attacker does not need to know the secret of "Bank of America", but uses instead our attack strategies to obtain an encryption token that compromises the security with respect to the victim A. This type of attack also works if, instead of compromising user B, we suppose B does not initially exist and the attacker is capable of registering it with the KDC as a new user. There is, however, a small problem with the internal padding pad in this case. Following our example, the length-extension attack would allow the attacker to compute the encryption token h(sk A "Bank" pad "of America"). Therefore, the forged identity is actually "Bank" pad "of America", which can be problematic if the padding allows the victim to detect the attack. We will, however, illustrate with a real example how this problem can be overcome, and experimentally demonstrate the viability of the attack.

Suppose that the protocol uses SHA-256 as hash function and that secret keys are of 256 bits. In our experimental attack, the secret key is the hexadecimal value 3F (which corresponds to the character '?') repeated 32 times; note that the specific value of this key is irrelevant for the attack and that it always remains unknown to the attacker. Table 2 shows the concatenation of the secret key and the identity "Bank", represented both as text and as hexadecimal strings, as well as the output of the hash function for this input. We suppose now that the attacker knows this output value (i.e., the encryption token h(sk A "Bank")); knowing this, the attacker can use the length-extension vulnerability of SHA-256 to compute the encryption token h(sk A "Bank" pad "of America").

The concrete result for the length-extension attack applied to the previous values is also presented in Table 2. Note that the first four bytes of the extended identity correspond to the string "Bank" (42 61 6E 6B). Next, there is the internal padding pad (80 00 ... 00 01 20), followed by the characters that correspond to the extension string "of America" (6F 66 ... 63 61). It should be noted that the intermediate padding may be rendered differently depending on the implementation of the user agent (e.g., browsers, mobile apps, standalone GUI, etc.), and some options may be exploitable. For example, when the extended identity "Bank" pad "of America" is rendered with the ISO 8859-

Figure 1 Fig. 1 :

 11 Figure1depicts the network setting assumed by this protocol, as well as its main actors.

  delegatee, analysis of previous traffic, ...

Fig. 5 :

 5 Fig. 5: Abstract flow of a sybil attack

  where h : {0, 1} * → Z p is a hash function.-Enc(sk A , id B , M ): On input the secret key sk A , the identifier of B, and a message M , the encryption algorithm Enc samples t from Z p , derives a fresh key K from t using a key derivation function (KDF), and outputs ciphertextC A = (SymEnc K (M ), t • h(sk A id B )),where SymEnc is a symmetric encryption algorithm. -ReEnc(rk A→B , C A ): On input a re-encryption key rk A→B and a ciphertext C A = (C A,1 , C A,2 ), the re-encryption algorithm ReEnc outputs ciphertext C B = (C A,1 , C A,2 • rk A→B ). -Dec(sk B , id A , C B ): On input the secret key sk B , the identity of the original recipient A, and a ciphertext C B = (C B,1 , C B,2 ), the decryption algorithm Dec computes t ← h(sk B id A )•C B,2 , derives key K from t using the KDF and decrypts the message M from C B,1 using symmetric decryption algorithm SymDec.

Table 1 :

 1 Notation

	Symbol	Description
	I	Initiator
	R	Responder
	D	Delegatee
	KDC	Key Distribution Center
	CTIR, CTRI	Counters
	SID	Session identifier
	NI , NR	Nonces
	H	Hash function
	KDF	Key derivation function
	AEnc, ADec	Authenticated encryption/decryption primitives
	MAC	Message authentication code
	KID, KRD

Pre-shared keys with the delegatee Zp

Multiplicative group of integers modulo p (i.e., {1, ..., p -1})

Note that, in the proxy re-encryption literature, the term "Delegatee" is usually referred to the recipient of a re-encrypted ciphertext. Hence, a re-encryption from

Note that in the traditional proxy re-encryption literature (i.e., in the public-key setting), the re-encryption oracle is considered as a delicate point. See for example[START_REF] Nuñez | A parametric family of attack models for proxy re-encryption[END_REF], where several generic attacks using the re-encryption oracle are discussed.

Note that when we assume that h is implemented with a traditional hash function, it is also necessary an additional encoding from its output domain to Zp, as required in Section 2.1; usual encodings of this type (e.g, taking modulo p) are easily invertible, so we will omit this for simplicity.

"Bob Esponja" is the Spanish name for "SpongeBob SquarePants"[START_REF] Wikipedia | SpongeBob SquarePants -Wikipedia, the free encyclopedia[END_REF]. Not associated with the sponge-based hash function SHA3[START_REF] Bertoni | The Keccak SHA-3 submission[END_REF], which, interestingly, is not susceptible to length-extension attacks.

Acknowledgments

This work was partly supported by the Junta de Andalucía through the project FISICCO (P11-TIC-07223) and by the Spanish Ministry of Economy and Competitiveness through the PERSIST project (TIN2013-41739-R). The first author is supported by a contract from the Regional Ministry of Economy and Knowledge of Andalucía.

Appendix: Length-extension attacks

We now describe a completely different attack strategy, based on a potentially dangerous design choice in the AKAPR protocol. The symmetric proxy reencryption primitive that underlies the key agreement protocol (see Section 2.1), uses a keyed hash function to derive the encryption tokens. Specifically, these values are of the form h(sk A id B ), where the identity of the recipient is used as the message of a keyed hash, with h : {0, 1} * → Z p as the hash function 3 . The authors state that the hash function is required to behave as a random oracle, which can be a rather strong assumption. However, it is known that real instantiations of hash functions do not necessarily behave as random oracles. In fact, widely used hash functions such as SHA-1 and SHA-256 (as well as others based on the Merkle-Damgård construction) suffer from length-extension vulnerabilities [START_REF] Tsudik | Message authentication with one-way hash functions[END_REF] that make possible to create new encryption tokens without knowing sk A , under the assumption that identifiers can have variable length.

First, let us recall the idea of length-extension attacks. In this type of attacks, knowledge of the hash value h(m 1 ) and the length of m 1 can be used to compute h(m 1 pad m 2 ), for any message m 2 chosen by the attacker and some required internal padding pad. It is known that hash functions based on the Merkle-Damgård construction (e.g, MD5, SHA-1, SHA-256) are vulnerable to this type of attacks. This problem has been shown to permeate to real systems, such as the Flickr's API signature forgery vulnerability [START_REF] Duong | Flickr's api signature forgery vulnerability[END_REF].

In the AKAPR protocol, if we assume that identifiers can have different lengths (i.e., id ∈ {0, 1} * ), then it may be possible that, for some identity id B , there exists an identity id BX where id B is a prefix. For example, let us assume that id B = "Bob" and that the attacker knows h(sk A id B ), but that sk A remains secret. Then, by the length-extension vulnerability he can produce h(sk A id BE ), "Extended" encryption token h(skA "Bank" pad "of America") "Bank" pad "of America" (hex)

42 61 6E 6B 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 20 6F 66 20 41 6D 65 72 69 63 61

"Bank" pad "of America" ('latin1') "Bank of America" 1 encoding (also called 'latin1'), the intermediate padding may be ignored, depending on the implementation, since it is composed of NUL characters (00) and invalid codes (80). This is the case of Python 2.7.10 implementation, which we used for reproducing the length-extension attack, and that displays "Bank of America" as the extended identity when 'latin1' encoding is selected. This can be used to deceive users into believing they are interacting with the real Bank of America, since the only difference between the legitimate identity and the displayed extended identity are non-printable characters (i.e., the user cannot visually distinguish one string from another). This also can be reproduced with UTF-8 encoding if errors are ignored when printing UTF-8 encoded strings (in Python this is achieved by specifying the option 'ignore'). We note that this example, although somewhat artificial, only makes relatively common assumptions, such as the use of SHA256, secret keys of 256 bits, 'latin1' encoding of strings, variable-size identities, etc.

Countermeasures As a simple and effective countermeasure to the length-extension attack, the protocol can require the use of a hash function resistant to lengthextension attacks (e.g., SHA3), or even better, use an HMAC or a key derivation function (e.g., HKDF [START_REF] Krawczyk | HMAC-based Extract-and-Expand Key Derivation Function (HKDF)[END_REF]). HMACs and KDFs are specifically designed to take a secret as input, and to be secure against length-extension attacks.


Negar Mosharraf
email: nmosharraf@forcepoint.com

Anura P Jayasumana
email: anura.jayasumana@colostate.edu

Indrakshi Ray
email: indrakshi.ray@colostate.edu

A Distributed Mechanism to Protect against DDoS Attacks

Distributed Denial of Service (DDoS) attacks remain one of the most serious threats on the Internet. Combating such attacks to protect the victim and network infrastructure requires a distributed realtime defense mechanism. We propose Responsive Point Identification using Hop distance and Attack estimation rate (RPI-HA) that when deployed is able to filter out attack traffic and allow legitimate traffic in the event of an attack. It dynamically activates detection and blocks attack traffic while allowing legitimate traffic, as close to the source nodes as possible so that network resources are not wasted in propagating the attack. RPI-HA identifies the most effective points in the network where the filter can be placed to minimize attack traffic in the network and maximize legitimate traffic for the victim during the attack period. Extensive OPNET c based simulations with a real network topology and CAIDA attack data set shows that the method is able to place all filtering routers within three routers of the attacker nodes and stop 95% of attack traffic while allowing 77% of legitimate traffic to reach victim node.

INTRODUCTION

Denial of Service (DoS) attacks, that make network service unavailable to legitimate users, have been known since early 1980s. Distributed Denial of Service (DDoS) attacks originate and propagate in a distributed manner making them harder to mitigate. DDoS attacks against commercial websites like Yahoo, Ebay and E*Trade have provided evidence of how DDoS attacks block legitimate users and cause financial loss [START_REF] Peng | Proactively detecting distributed denial of service attacks using source IP address monitoring[END_REF]. Moreover, emergency and essential services rely on the network infrastructure, and thus DDoS attacks may have severe consequences, such as loss of life. Consequently, techniques for preventing, detecting, and surviving such attacks [START_REF] Cabrera | Proactive intrusion detection and distributed denial of service attacks-A case study in security management[END_REF] are needed. Despite significant research into countermeasures, DDoS attacks still remain a major threat [START_REF] Chen | Attack Diagnosis: Throttling distributed denial-of-service attacks close to the attack sources[END_REF]. DDoS attack can appear like a flash crowd, i.e., a large number of legitimate users connecting to a server/site simultaneously [START_REF] Peng | Survey of network-based defense mechanisms countering the DoS and DDoS problems[END_REF]. A comprehensive defense mechanism should include preventing, detecting, and responding techniques to counter DDoS attacks since there is no one-size-fit-all solution to the DDoS problems [START_REF] Zargar | A survey of defense mechanisms against distributed denial of service (DDoS) flooding attacks[END_REF]. Prevention mechanisms aim to stop the occurrences of attacks [START_REF] Peng | Proactively detecting distributed denial of service attacks using source IP address monitoring[END_REF][START_REF] Yaar | Pi: A Path identification mechanism to defend against DDoS attacks[END_REF], while detection mechanisms aim to identify attack traffic [START_REF] Gil | MULTOPS: A data-structure for bandwidth attack detection[END_REF][START_REF] Mahajan | Controlling high bandwidth aggregates in the network[END_REF]. The response mechanisms attempt to identify the sources of attack and react to those [START_REF] John | DDoS: Survey of traceback methods[END_REF]. Our work belongs to this last category and tries to identify the attack source and prevent the propagation of attack traffic. Responsive techniques identify the source and mitigate DDoS attacks by filtering or limiting attack packets [START_REF] Aghaei Foroushani | TDFA: traceback-based defense against DDoS flooding attacks[END_REF][START_REF] Chen | Attack Diagnosis: Throttling distributed denial-of-service attacks close to the attack sources[END_REF][START_REF] Francois | a collaborative protection network for the detection of flooding DDoS attacks[END_REF]. Such schemes comprise two parts: attack detection and packet filtering. The characteristics of attack packets, such as source IP address or marked IP header values [START_REF] Riorey | RioRey taxonomy of DDoS attacks[END_REF][START_REF] Yaar | Pi: A Path identification mechanism to defend against DDoS attacks[END_REF], are often used to detect and identify attack traffic and packet filtering. Note that packet filtering can be applied either close to the attack node [START_REF] Gil | MULTOPS: A data-structure for bandwidth attack detection[END_REF][START_REF] Mahajan | Controlling high bandwidth aggregates in the network[END_REF] or close to the victim node [START_REF] Yaar | Pi: A Path identification mechanism to defend against DDoS attacks[END_REF] where all the attack aggregate. However, applying filtering close to at the victim has two drawbacks. First, the victim may crash while dealing with an overwhelming volume of attack traffic. Second, the high volume of attack traffic may still overwhelm upstream Internet resources. At these traffic intensities, the infrastructure upstream from the intended victim becomes severely affected necessitating attack traffic be filtered as close as possible to the attack sources. However, it is difficult to anticipate and identify such nodes as the attack may originate at widely distributed nodes and spread through various routes [START_REF] Zargar | A survey of defense mechanisms against distributed denial of service (DDoS) flooding attacks[END_REF]. Our approach aims to solve this problem. This paper proposes a novel distributed DDoS defense mechanism for achieving Responsive Point Identification algorithm using Hop distance and Attack estimation rate (RPI-HA), which does not consume any router resources in the process of identifying routers for upstream filtering. The approach tries to minimize the modifications required to the routers and the current protocols to combat DDoS attacks and such modifications have a low complexity and are scalable. The mechanism aims to maximize the arrival rate for legitimate traffic and minimize the attack flow during the attack. The approach consists of four parts. The first part develops rules to create a history-based profile of high confidence legitimate IP addresses that serve to differentiate the good traffic from the malicious [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF]. The second part represents the IP address history in the form of a Bloom filter for efficient transfer. The third and fourth parts, the main contribution of this paper, identify how and where this history is used to prevent the attacks. Placing filters in upstream routers incur storage and performance costs since the filter must be applied to multiple routers. Placing the filter closer to the victim causes the link capacity to become saturated and wastes network resources. Our scheme introduces an algorithm that identifies the routers where the filters can be placed. To the best of our knowledge, this is the first work that considers the optimal placement of the filters to mitigate DDoS attacks.Section 2 describes our responsive defense mechanism. Section 3 presents our simulation results. Section 4 concludes the paper.

DISTRIBUTED RESPONSIVE DEFENSE APPROACH

This section presents our scheme to identify upstream routers, and block the DDoS attacks at these routers to minimize the impact both to the victim and to the upstream network during the attack time. The DDoS mitigation mechanism consists of the following components:(1) identification model to discriminate attack traffic from legitimate traffic based on a history-based profile, (2) capture the history-based profile in the form of a Bloom filter for efficient transfer, (3) identify the responsive points (router/switch) which carry the attack traffic, and (4) activate packet filtering at selected points. We use the mechanisms detailed in [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF] for the first two steps. The main contributions of this paper are the last two components, and the resulting overall architecture.

IDENTIFICATION MODEL

History based profiles the specific attack features as well as normal traffic characteristics for history based profiles to discriminate between the attack traffic from legitimate traffic are investigated in [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF]. A key observation is that the DDOS attacks tend to use randomly spoofed IP addresses [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF] and other packet features, such as port number and size of packet are randomly distributed as well. Our experiments [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF] with the CAIDA 2007 dataset [START_REF]The CAIDA DDoS Attack[END_REF] indicated that such as filtering model can protect the victim node from 95% of attack traffic while allowing 70% of legitimate traffic.

BLOOM FILTER MECHANISM

The filtering mechanism must be applied at upstream routers which must process all packets targeted towards the victim node. Since the network bandwidth may already be saturated during an attack, transferring the entire history and looking it up in the upstream routers is rather expensive. A Bloom filter is thus proposed for representing the contents of the IP based history [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF]. Such a filter helps reduce the communication and computation costs and also the storage requirements at upstream routers that check for malicious traffic. There are three fundamental performance metrics for Bloom filters where the size of the Bloom filter is an adjustable parameter based on the accepted false positive rate as well as number of hash functions.

RESPONSIVE POINTS' IDENTIFICATION

The third step constitutes the main contribution of this paper and it is how and where to use this filter to minimize the impact of the attack. Proposed solution addresses this problem by using a recently developed technology, typically implemented as Small Formfactor Probes (SFP) using Field Programmable Gate Arrays (FPGAs). Our proposed approach monitors traffic by using SFPs to efficiently identify router/switch which carry high volume of attack traffic and then applies packet filtering at selected routers as the responsive point of defense mechanism. An example of such hardware is JDSU SFProbes and Packet Portal [16]. SFProbes can plug into any SFP compatible elements such as switches/routers in such a way that it taps into the normal fiber without interfering with the traffic flow. It can be programmed over the network using the same fiber to do tasks such as counting the number of packets with certain values in header fields and forward information about link traffic to a remote base station. Our approach uses these probes at a subset of ports in the network to identify the upstream links, and thus nodes, which carry attack traffic. A main advantage of using SFProbes is that they plug into the routers/switches and do not require modifying the router's operation and software to apply our scheme.This feature is used to send the history based profiles to identify the paths with high intensity of attack traffic. Moreover, the portal base station (PBS) has knowledge about SFProbes attached to the routers throughout the network and can collect data from SFProbes and perform the computation needed for our scheme, obviating the need for routers performing such computations. Upon detection of an attack, the proposed approach starts to protect a victim node as illustrated in Figure 1. At this point, the victim network sends the Bloom filters that it had created to PBS. The PBS sends the Bloom filter to those SF-Probes that are plugged into different routers as shown in Figure 1. SFProbes start monitoring the intensity of traffic directed toward the victim node. 1) is defines the historical estimate of the average number of packets received by a router, where α is a weighted value between 0 and 1.

X (t m , i) = (1 -α) X (t m-1 , i) + αX (t m , i) (1)
Let A j (t m , i) represent a Boolean variable which equals 1 if the packet P j is received at router i at time slot t m and matches the corresponding Bloom filter B (v) for point v, and is 0 otherwise, i.e.,

A j (t m , i) = 1 if P j (t m , i) ∈ B (v) 0 otherwise (2)
Let W (t m , i) be the historical estimate of the average number of packets received by the router at SFProbe i during time slot m that match the Bloom filter. Thus, W (t m , i) Eq. ( 3) shows the average number of packets that is considered as the legitimate traffic by the Bloom filter directed towards the victim where, n is the total number of packets flowing toward the victim node in time slot t m :

W (t m , i) = (1 -α) W (t m-1 , i) + (α) n j=1 A j (t m , i) n (3)
During the attack time, if the number of IP addresses that do not match Bloom filter is higher than a specific threshold β, then the router is likely to be carrying significant attack traffic. Such routers are candidates for filter placement. We define Eq. ( 4) Attack Estimation Rate (ASR) R (t m , i) to determine the average number of packets that do not match Bloom filter.

R (t m , i) = X(tm,i)-W (tm,i) X (t m , i) (4)
Upon detection of an attack, the SFProbes start monitoring traffic going towards the victim nodes and send R (t m , i) estimate to PBS. Next we decide the points at which the filters are to be placed. Save network resources, the best routers to apply the filtering mechanism must be as far away as possible from the victim node. The volume of potential attack traffic passing through a router has to be considered as well. Thus, we use two factors to determine the best routers to place the SFProbes -the Attack Estimation Rate of Eq. ( 4) and the hop distance H i (v) that shows how far the SFProbe i is from the victim node v. For each SFProbe i computer the weighted attack estimation rate H i (v) is given by:

S (t m , i) = X(tm,i)-W (tm,i) X (t m , i) * H i (v) (5)
The routers with higher value of S (t m , i) are selected routers to apply filtering mechanism. We call this approach as the Responsive Point's Identification algorithm using Hop distance and Attack estimation rate (RPI-HA). In addition to the hop distance and the volume of attack traffic, other issues must also be considered while placing the filters. One such additional factor is the number of routers on which filters are placed based on the distribution of the attack traffic. We present a new formula that adjusts the number of routers according to the attack traffic distribution that we refer to as the Responsive Point's Identification algorithm using Hop distance, Transmission rate and Attack estimation rate (RPI-HTA). In this scheme, the transmission rate of traffic directed towards the victim node as well as hop distance is considered to determine the best filtering points. SFProbes collect the information of attack estimation rate R (t m , i) and traffic transmission rate T (t m , i) during m time slots and send this information to the PBS. To select the filtering points the attack estimation rate D (t m , i) is computed as follows:

D (t m , i) = X(tm,i)-W (tm,i) X (t m , i) * T (tm,i) C (v) * H i (v) (6)
D (t m , i) = (1 -α) D (t m , i) + (α) n i=1 D (t m , i) n (7)
In Eq. ( 6) we consider the distribution of traffic towards the victim node as an important factor that helps to determine how the attack has followed, where traffic transmission rate T (t m , i) and capacity of the victim node C (v) are considered. D (t m , i) determines if the attack is distributed or centralized. If the attack is highly distributed, we need to consider more filtering points to stop the attack whereas if the attack is more centralized we apply filters on few of the routers. The historical average attack estimation rate is given by D (t m , i) in Eq. ( 7) where n indicates total number of participating SFProbes that collects the data. We select only those routers D (t m , i) higher than average attack estimation rate as filtering points. Thus, the number of filters in the RPI-HTA depends on traffic transmission rate, hop distance, as well as attack estimation rate and it will be vary according to D (t m , i) and D (t m , i).

PACKET FILTERING

The last step of the proposed approach is activating packet filtering at selected points. According to the previous section, PBS selects those routers which carry the attack traffic for applying Bloom filtering. So PBS sends created Bloom filters to these selected routers and the routers start to filter incoming traffic directed towards the victim node. This process continues during the attack.

EVALUATION

Performance of our approach is evaluated next using a real network topology from Oregon route-views between March 31 and May 26 2001 [18] and set it up on OPNET c . We test the effectiveness of the responsive defense mechanism using the DARPA 1998 intrusion detection dataset [17] which contains 7 weeks of training datasets that we use to establish an IP address history and 2 weeks of testing dataset to evaluate our techniques. The first step is creating the IP address history from the DARPA training dataset and then create corresponding Bloom filter, the details of which was presented in [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF]. The next step, evaluates the responsive defense approach based on the created IP address history in OPNET c . We also have validated our model by real network traffic collected at University of Auckland [START_REF] Group | [END_REF] and CAIDA attack dataset [START_REF]The CAIDA DDoS Attack[END_REF] in Section 3.5.

METRICS

Responsive defense mechanism is evaluated, (i) Attack Traffic Detection Rate (ii) Normal Traffic Detection Rate , and (iii) Link Utilization Rate. Attack Detection Rate is the percentage of attack dataset that is correctly detected as the attack and cannot pass through the Bloom filter to reach the victim node. Normal Traffic Detection Rate is defined as the percentage of normal traffic that can correctly pass through the Bloom filter during the attack period. False Negative Rate is defined as the percentage of attack traffic that is incorrectly marked as normal traffic and therefore can pass through the Bloom filter. Link Utilization Rate is defined as the percentage of the network's bandwidth that is currently being consumed by the network traffic.

PERCENTAGE of COLLABORATIVE SFPROBES

The effectiveness of the responsive defense mechanism relies on the collaboration of SFProbes through the network. Increasing the number of SFProbes attached to the routers enables more close monitoring and more effective filtering. We look at four different scenarios to validate this. We assume a different percentage of routers (80% to 25%) have SFProbes attached to them to monitor network traffic to address the case where only a fraction of routers implement the mitigation technique. The number of filtering routers is either fixed according to the RPI-HA or variable based on RPI-HTA algorithm. In the RPI-HA algorithm, the number of filtering routers considered 8, 5 and 3 as 20%, 12.5% and 7.5% of the total routers through the network. We also looked at a fifth scenario where the filters are placed in random locations throughout the network without applying any algorithm to stop the attack traffic. Figure 2 shows the average attack detection rate over 5 runs. We use a time slot of 60 seconds. The results demonstrate the effectiveness of using the RPI-HTA algorithm, which considers all the three features (hop distance, transformation rate and attack estimation rate) together. The RPI-HTA algorithm produces an attack traffic detection rate of 91% when 80% of routers use SFProbes. Note that, by applying the random selection to determine placement of filters the attack traffic detection rate reduces by more than 14% and up to 23%. These results show how the location of filters plays an important role in protecting the victim node. Recall that the number of filtering points for RPI-HTA algorithm is variable and depends on attack distribution, transmission rate, and hop distance. 7 filters for networks having 80% and 60% probes and 6 filters for those having 40% and 25% probes are selected according to the RPI-HTA algorithm. As shown in Figure 3 the attack traffic detection rate for RPI-HTA algorithm for 80% and 60% probes is equal or higher than when RPI-HA algorithm is applied by 8 filtering routers through the network. This means that the RPI-HTA algorithm can provide comparable or better filtering mechanism by using lower number of filtering routers by placing the filters in the appropriate locations. The other important parameter to evaluate is how many normal packets can reach the victim node. As shown in Figure 3, normal or legitimate traffic detection rate is around 72% for RPI-HTA algorithm with

EFFICIENCY of DISTRIBUTED APPROACH

Figure 4 depicts the fraction of attack traffic dropped at different hop distances from the victim, and thus the source. It shows that 60% of the attacks in total are detected and blocked in the first two routers from attacker, with 23% in the first and 37% in the second. Thus, it shows that RPI-HTA algorithm can effectively select routers further from the victim node and close to attacker. Furthermore, it shows that having more probes is more effective and we can select farther routers as well. For instance, with 80% probes all the filtering points are selected at least 3 hop distances away from victim node, while with 25% probes the filtering points must be within 1 and 2 hop distances from victim node. In this experiment, the 25th, 50th (median), 75th percentiles, minimum and maximum value of attack traffic detection rate for all 3 scenarios are computed as well. As shown in Figure 5(a), the first layer of router from attacker (fifth hop distance from victim) has relatively good attack traffic detection rate close to 20% for 50% of simulations in the RPI-HTA algorithm, whereas, this detection rate reduces to less than 10% for random selection scenario. This proves that RPI-HTA algorithm can accurately select desirable filtering points during the attack period. Thus, it can Fig. 4: Attack detection rate and location of selected routes be observed that the core of detection and prevention mechanism is located at the router with hop distance 4, 3, and 5 from victim node in that order. The other part of our evaluation is specifying utilization of the victim node and other end-users before and after applying filtering mechanism. In Fig. 6(a), the last link utilization of victim node without applying filtering approach shows that it is fully utilized during the attack time. However, the link utilization reduces to around 60% after deploying Bloom filter through the network based on RPI-HTA algorithm.The result shows that 80% probes through the network give 50% link utilization rate for the victim node -this is the least link utilization rate that we get in our experiments. In this experiment, the effectiveness of responsive defense approach is tested using real network trace from University of Auckland in New Zealand. The packet trace contains 6.5 weeks IP header trace taken with 155 Mbps Internet links [START_REF] Group | [END_REF]. We use The CAIDA attack dataset 2007 [START_REF]The CAIDA DDoS Attack[END_REF] in the experiments as attack traffic. The dataset is run with same topology that was used in previous part by distributing the dataset traffic over the network. History-based profile of normal traffic going to the victim node is created using the trace collected from the University of Auckland. The corresponding Bloom filter will be created based on the scheme [START_REF] Mosharraf | A Responsive defense mechanism against DDoS attacks[END_REF] in the second step and then rpresented approach is applied during the attack time. Figure 7 shows the attack traffic detection rate against the CAIDA attack traffic. Attack traffic detection rate is around 95% with 80% probes in the RPI-HTA algorithm where it was around 91% for DARPA dataset.

Overall the attack traffic detection rate increases slightly compared with DARPA dataset, where the Bloom filter accuracy played a role in this situation. In Fig. 8, distance from victim has a better attack traffic detection rate close to 25% for 50% of simulations in the RPI-HTA algorithm, whereas this detection rate was 20% for DARPA dataset. Moreover, it shows that router with hop distance 5, 4 and 3 in that order were the core of attack detection. This proves that RPI-HTA algorithm accurately selected desirable filtering points during the attack period for CAIDA attack traffic as well.

CONCLUSION

A responsive defense approach to defend against DDoS attacks was presented.

A key contribution is the distributed mechanism that identifies in real-time the best response points where filters are to be activated so as to minimize attack traffic and maximize legitimate traffic during the attack. The technique has been validated with two real-world data sets. Results for CAIDA attack set, e.g., indicate that the responsive mechanism protects the victim nodes from 95% of attack traffic close to the source of attack, while allowing 77% of legitimate traffic. The method is light in terms of computational and communication overheads. Results also demonstrate the effectiveness of the mechanism in preserving valuable network resources and link utilizations for other end-users during the attack time, thus preserving the service availability and minimizing the attack impact. Our future work includes validating the scheme with very recent realworld network dataset. A part of our future work also includes extending our identification scheme for IPv6 addresses.

Fig. 1 :

 1 Fig. 1: Responsive defense mechanism

Fig. 2 :Fig. 3 :

 23 Fig. 2: Attack traffic detection rate

Fig. 5 :

 5 Fig. 5: Result of attack detection rate

Figure 6 (

 6 b) shows the last link's utilization for other end-users increases with applying the filtering routers. It means the other end-users can receive normal traffic during the attack time. This is good as it provides service availability in the presence of DDoS attacks and minimizes the attack impact during an attack time.

Fig. 6 :

 6 Fig. 6: Victim node's utilization. (b) Average of last link utilization of end-users

Fig. 7 :Fig. 8 :

 78 Fig. 7: Attack traffic detection rate

ACKNOWLEDGMENT

The authors gratefully thank Forcepoint LLC for their funding support.

This work was partially supported by NSF I/UCRC Award Number 1650573 and funding from CableLabs. The views and conclusions contained in this document are those of the authors and should not be automatically interpreted as representing the official policies, either expressed or implied of NSF and CableLabs.