Zhuocheng Li
email: zhuocheng.li@gipsa-lab.grenoble-inp.fr

Tuong-Bach Nguyen
email: tuong-bach.nguyen@gipsa-lab.grenoble-inp.fr

Quentin Lampin
email: quentin.lampin@orange.com

Isabelle Sivignon
email: isabelle.sivignon@gipsa-lab.grenoble-inp.fr

Steeve Zozor
email: steeve.zozor@gipsa-lab.grenoble-inp.fr

Ensuring k-coverage in low-power wide area networks for Internet of Things

Keywords: LPWANs, k-coverage, k-order Voronoi diagram

Low-Power Wide Area Networks (LPWANs) promise to enable nationwide low-power connectivity to Internet of Things (IoT) devices. While transmission ranges meet expectations, concerns on the packet delivery ratio are voiced. Receiverside diversity is often thought as a solution to improve on delivery ratio, as well as an enabler to the geolocation of devices. In this context, we study the infrastructure density required to achieve k-coverage of the IoT devices, which preludes k-reception. To that purpose, we make use of k-order Voronoi diagram to compute an estimate of the gateway density in reference deployment setups: dense urban, urban and rural networks. We thus provide insights on the feasibility of k-coverage deployment in those scenarios.

I. INTRODUCTION

Trading higher bit rates for better link budgets, LPWANs provide long range wireless connectivity to IoT devices. Such networks provide a promising alternative to traditional cellular or multi-hop networks and are indeed envisioned to provide nationwide connectivity over industrial, scientific and medical (ISM) bands to battery-powered IoT devices that transmit little amount of data over long periods of time, e.g.,, water & gas meters. As stated in European Telecommunications Standards Institute (ETSI) requirements for smart city applications [START_REF]ETSI[END_REF], typical use cases exhibit stringent Quality of Service (QoS) requirements, e.g.,, high packet delivery ratio, which pose a challenge to LPWANs such as [START_REF]LoRaWAN TM Specification[END_REF][START_REF]Sigfox[END_REF] that mostly rely on random, uncoordinated access schemes. Those requirements, as well as harsh propagation environments, e.g.,, meters deployed in water pits, motivate the use of redundancy mechanisms at the emitter side, i.e.,, retransmissions and the receiver side, i.e.,, multiple-reception or receiver diversity. Unlike retransmission mechanisms that apply a higher pressure on the medium usage, receiver diversity comes at virtually no cost for IoT devices and medium usage. However, receiver diversity requires a higher infrastructure density and thus higher deployment costs.

In this context, we investigate the dimensioning of the gateway density to ensure k-coverage, i.e.,, k gateways in communication range of each IoT device. The number of IoT devices being huge, we consider k-covering the network region of IoT devices. To this purpose, we introduce some notions based on k-order Voronoi diagram to express the inter-gateway distance and gateway density in three regular deployment patterns: triangular, square and hexagonal as a function of the target coverage degree k and communication range r.

Our results provide an estimate of the infrastructure density required in three real-world reference IoT scenarios : a dense urban setup, an urban setup and a rural setup, by considering only the factor of k-coverage. As we will see, the k-coverage is not the primary dimensioning factor in some use cases. Capacity of gateways should also be taken into account.

The paper is organized as follows. In section II, we provide an overview of methodologies and results of related works in the domain of wireless sensor networks (WSNs). In section III, we introduce our problem setting and essential definitions before proposing our methodology in section IV. Section V is finally dedicated to the numerical application of our methodology on three network dimensioning use cases.

II. RELATED WORKS

k-order Voronoi diagram and k-coverage in WSNs are both well-studied subjects in the geometry and the network litteratures respectively. Without pretending to be exhaustive on the matter, we present works whose methodologies are similar to that of this paper. WSNs have been first thought to be a viable solution to monitor physical events, be it for military or civil surveillance applications. From this context arose the concept of sensing coverage, i.e.,, ensuring the detection of events in a monitored area. The requirement of k-coverage comes from the detection precision concern. In [START_REF] Kumar | On k-coverage in a mostly sleeping sensor network[END_REF][START_REF] Xing | Integrated coverage and connectivity configuration for energy conservation in sensor networks[END_REF][START_REF] Hefeeda | Randomized k-coverage algorithms for dense sensor networks[END_REF][START_REF] Ammari | Centralized and clustered k-coverage protocols for wireless sensor networks[END_REF], a dense network of randomly scattered sensors is assumed and the authors propose algorithms, either distributed or centralized, to compute minimal sets of active nodes to ensure a complete k-coverage of the area of interest while maximizing the network lifetime. While the coverage objective is similar to covering an area of sensor nodes with gateways, such algorithms are ill-suited to compute the minimal spatial density of an infrastructure tailored to ensure k-coverage.

Pattern-based deployments have the advantage of guaranteeing regular inter-site distances [START_REF] Grunbaum | Tilings by regular polygons[END_REF]. It's especially adapted for planned infrastructure deployment. In [START_REF] Kim | Regular sensor deployment patterns for p-coverage and q-connectivity in wireless sensor networks[END_REF], by combining the notion of grid coverage and that of k-perimeter coverage, sufficient yet not necessary conditions for k-coverage in regular deployment patterns are given. In this article, we propose a different methodology based on k-order Voronoi diagram that gives the necessary and sufficient condition for kcoverage, thus resulting in minimal spatial densities of regular deployments. Our results confirm those obtained in [START_REF] Kershner | The number of circles covering a set[END_REF][START_REF] Ge | Planar thinnest deployment pattern of congruent discs which achieves 2-coverage[END_REF] in terms of optimal 1 and 2-coverage deployment patterns, and can give some insights for the more general case of k ≥ 3.

k-order Voronoi diagram has been used to study distributed and randomized k-coverage issues in WSNs [START_REF] Zhu | A survey on coverage and connectivity issues in wireless sensor networks[END_REF][START_REF] Li | LAACAD: Load balancing k-area coverage through autonomous deployment in wireless sensor networks[END_REF]. However, pattern-based deployments being more appropriate for infrastructure deployment by requiring probably smaller deployment density, we apply k-order Voronoi diagram to regular patterns and find the optimal k-coverage pattern as well as an overview of the deployment cost for achieving k-coverage.

III. PROBLEM FORMULATION

As in [START_REF] Kim | Regular sensor deployment patterns for p-coverage and q-connectivity in wireless sensor networks[END_REF], in order to model the gateway deployment, we choose three regular patterns coming from the only three possible edge-to-edge tilings of the 2D plane by mutually congruent regular square, triangle and hexagon polygons [START_REF] Grunbaum | Tilings by regular polygons[END_REF]. The vertices of the polyons represent the positions of gateways, as shown in figure 1. As the deployments thus obtained are spatially periodical, single periods are shown. We first introduce several definitions necessary to our problem formulation.

We denote the Euclidean distance between two points p, q ∈ R 2 by d(p, q). The region to provide k-coverage is denoted by Ω ⊆ R 2 , that can be bounded or not. Let G denote the deployment pattern of gateways, G = {g i } i∈I , where I ⊆ N. G is not necessarily limited to Ω, nor finite (assuming that the pattern is regular, when Ω = R 2 the pattern is necessarily infinite). Let | • | denotes the cardinality, and r the communication range which is supposed to be identical for all devices. We denote by G(p, r) the subset of G enclosed by a disc of radius r, centered at p ∈ Ω, i.e.,,

G(p, r) = {g i ∈ G | d(p, g i ) ≤ r}. Finally, the k-distance of p to set G is defined as d k (p, G) = min{r ≥ 0 | |G(p, r)| ≥ k}.
k-coverage means that every device in Ω is able to communicate with k gateways in G with communication range r as stated by the following definition and proposition.

Definition 1 (k-coverage). Ω is said to be k-covered by the deployment G, if for any p ∈ Ω representing a device, |G(p, r)| ≥ k. Proposition 1. The minimal communication range to k-cover Ω is r k = max p∈Ω d k (p, G).
Proof. Note that since G is defined as a regular pattern, this maximum is well defined as long as

k ≤ |G|. If r k is the minimal communication range achieving k-coverage, then we have r k ≥ max p∈Ω d k (p, G): indeed, if r k < max p∈Ω d k (p, G), there exists at least a point p such that |G(p, r)| < k and p is not k- covered by definition. For r = max p∈Ω d k (p, G), we have for any p ∈ Ω, r ≥ d k (p, G), according to the definition of d k (p, G), we have |G(p, r)| ≥ k, thus Ω is k-covered.
In order to find r k , let's introduce the following definitions.

Definition 2 (k-order Voronoi cell). Let us denote by

P k (G) = {G ⊆ G | |G | = k} the collection of the sub- sets of G having the cardinality k, with k ≥ 1. For any G 0 ∈ P k (G), the k-order Voronoi cell of G 0 is defined as C k (G 0 ) = {p ∈ Ω | ∀ G ∈ P k (G), d k (p, G 0 ) ≤ d k (p, G )}. Definition 3 (k-order Voronoi cell of a vertex). The k-order Voronoi cell of a vertex g i ∈ G is defined as V k (g i ) = G gi C k (G ).
C k (G 0 ) is the set of points that have G 0 as the k nearest gateways among G. V k (g i ) is the set of points that have g i as one of its k nearest gateways among G. The classical Voronoi polygon of g i is a special k-order Voronoi cell given by k = 1, i.e.,, 1. With all the necessary definitions given, in section IV we express the minimal k-coverage ensuring density D(k, r) in regular patterns by fixing a communication range r.

C 1 (g i ) = V 1 (g i ). Note that there is no overlap between adjacent C k , but V k overlap in general except for V 1 . An example of C 3 (G ), V 3 (g i ) and C 1 (g i ) = V 1 (g i ) is shown in figure

IV. ENSURING k-COVERAGE

We define the spatial density of a deployment as the number of gateways per unit surface, i.e.,, D = |G| SΩ , where S Ω stands for the surface of Ω. When Ω and G are infinite, D = 1 Svp where S vp is the surface of the Voronoi polygon V 1 (g i ) of the regular pattern. In this section, we first consider the infinite case Ω = R 2 . A realistic finite scenario with Ω chosen as a rectangle region is briefly discussed at the end of the section.

A. Necessary and sufficient condition of k-coverage

Proposition 2. We denote the inter-gateway distance in regular patterns by a, i.e.,, the distance between nearest gateways. By fixing an a, the necessary and sufficient condition for R 2 to be k-covered is that every point g i in G covers V k (g i ). r k equals to the distance between an arbitrary vertex g i and the most distant points from g i in V k (g i ). We have

r k (a) = max p∈R 2 d k (p, G) = max p∈V k (gi) d(p, g i ).
The proof of propostion 2 is inspired from [START_REF] So | On solving coverage problems in a wireless sensor network using voronoi diagrams[END_REF] and included in the document [START_REF] Li | Ensuring k-coverage in low-power wide area networks for internet of things[END_REF]. It is omitted here due to limitation of space. Trivially, the coverage condition is scale-invariant and thus r k (a) is proportional to a, i.e.,, r k (a) = β(k) a where β(k) depends only on k and on the pattern. Proposition 3. Given a communication range r, the minimal densities D(k, r) ensuring k-coverage in regular patterns is given by D(k, r) = 1 Svp(a k (r)) , where a k (r) = r β(k) is the maximal inter-gateway distance that guarantees k-coverage.

Proof. If a = a k (r) = r β(k) , we have r = β(k)a = r k (a)
, according to proposition 2, we guarantee k-coverage.

We illustrate an example of 3-coverage by proposition 3 in figure 1. Obviously, D(k, r) is proportional to 1 a k (r) 2 , and thus to 1 r 2 , i.e.,, D(k, r) = α(k) r 2 . α(k) is the k-coverage coefficient which depends only on k and on the pattern. D(k, r) can be expressed as:

D sqr (k, r) = 1 a k (r) 2 , so that α sqr (k) = β sqr (k) 2 for the square pattern; D tri (k, r) = 2 √ 3 3 a k (r) 2 , so that α tri (k) = 2 √ 3 βtri(k) 2 3
for the triangular pattern;

D hex (k, r) = 4 √ 3 9 a k (r) 2 , so that α hex (k) = 4 √ 3 β hex (k) 2 9
for the hexagonal pattern.

D(k, r) is thus directly linked to β(k) which can be determined exactly by some algorithm of the literature on k-order Voronoi diagrams (see for instance [START_REF] Lee | On k-nearest neighbor voronoi diagrams in the plane[END_REF]).

B. Numerical results

α(k) for three regular patterns are listed in table I. We observe that α tri (1) ≈ 0.385 is the smallest for 3 regular patterns, which confirms the theory of [START_REF] Kershner | The number of circles covering a set[END_REF], i.e.,, the regular triangular pattern is asymptotically optimal in terms of the number of discs necessary to provide 1-coverage on a plane. We define the minimal k-coverage achieving coefficient in mutually congruent patterns as α min . Obviously, we have α min (1) = α tri (1). In [START_REF] Ge | Planar thinnest deployment pattern of congruent discs which achieves 2-coverage[END_REF], the authors find that α min (2) = 4 3 √ 3 , which coincides with 2 α tri (1), meaning a superposition of two 1-coverage regular triangular patterns gives α min [START_REF]LoRaWAN TM Specification[END_REF]. Note that regular hexagonal pattern can be seen as a superposition of two regular triangular patterns, that's why we have α hex (2) = 2 α tri (1) = α min (2). The advantage of regular hexagonal pattern over any two randomly superposed regular triangular patterns is that the inter-gateway distance can not be arbitrarily small. Since α min (1) and α min (2) are found among regular patterns, we conjecture that for k ≥ 3, α min (k) = min {α sqr (k) , α tri (k) , α hex (k)}. In literature, many heuristics for optimal general k-coverage have been proposed by superposing k regular triangular patterns [START_REF] Kim | Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments[END_REF][START_REF] Yuan | A cost-efficiency method on beacon nodes placement for wireless localization[END_REF]. Superposed patterns may be optimal for k = 3, as 3 α tri (1) = min {α sqr (3) , α tri (3) , α hex (3)} = α tri (3). Note that a 3-coverage regular triangular pattern can be decomposed to three 1-coverage regular triangular patterns. For k = 4, 4 α tri (1) ≈ 1.540 > min {α sqr (4) , α tri (4) , α hex (4)} = α sqr (4) ≈ 1.389. For k = 5, 5 α tri (1) ≈ 1.925 < min {α sqr (5) , α tri (5) , α hex (5)} = α tri (5) ≈ 2.021. For k = 6, 6 α tri (1) ≈ 2.309 > min {α sqr (6) , α tri (6) , α hex (6)} = α tri (6) ≈ 2.096. For k = 4, 6, superposition heuristics result in greater densities. For k = 5, they require smaller density but the resulting patterns neither are necessarily mutually congruent nor guarantee a non arbitrarily small inter-site distance. Although it's not our primary objective to deduce optimal k-coverage pattern, our work can give some guidelines for this effort. In Figure 2 we can see that α(k) increases almost linearly with k, revealing the scalability of k-coverage deployment cost.

TABLE I α(k) IN FUNCTION OF k FOR THREE REGULAR PATTERNS k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 αsqr(k)

C. Edge effect consideration

In this section, we consider a realistic finite scenario. We first provide the following proposition. The proof of this proposition is evident and included in [START_REF] Li | Ensuring k-coverage in low-power wide area networks for internet of things[END_REF]. Let's take an example of providing 3-coverage with regular triangular pattern to a rectangle region Ω of dimensions 5km × 2.5km. r is chosen to be a realistic communication range for LPWANs in dense urban scenario, i.e.,, 0.79 km, see table II. a 3 (r) = r = 0.79km for triangular pattern. One way to interpret this proposition is to consider Ω as the region of interest filled with sensor nodes to provide 3-coverage. This proposition provides a way to fully 3-cover Ω by deploying gateways in the dilation of it, i.e.,, Ω ⊕r . "Gateway density" in this scenario can be calculated as

D full = |G∩S Ω ⊕r | SΩ = 48
12.5km 2 = 3.84/km 2 , which is much greater than the density calculated in infinite case, i.e.,,

D tri (3, r) = 2 √ 3 3r 2 ≈ 1.155 r 2
≈ 1.85/km 2 . However, if we consider Ω ⊕r as the area of interest, certainly the border area of it is not 3-covered, but the center area Ω is fully 3-covered, see figure 3. In this scenario we have

D realistic = |G∩S Ω ⊕r | S Ω ⊕r ≈ 48 26.31km 2 ≈ 1.82/km 2 . In the fully 3- covered area Ω, D center = |G∩SΩ| SΩ ≈ 24
12.5km 2 ≈ 1.92/km 2 . In reality, the border area being usually less populated, it's not necessary and realistic to perfectly k-cover it, especially when the cost is too high compared to the realistic case. Moreover, it's difficult to consider edge effect which depends on region shapes etc. It's of little interest when providing general scaling laws. In section V, we neglect the edge effect and stick to the approximation D(k, r) = 1 S V P (a k (r)) in order to evaluate the efficiency of a real LPWANs k-coverage deployment .

V. APPLICATION

In this section, by applying our results in IV, we aim at visualizing the dimensioning of a real LPWANs deployment according to the k-coverage criterion in some real-world scenarios. In order to quantify the efficiency of a deployment we introduce the average number of sensor nodes per gateway when k-coverage is achieved, denoted by N avg = d s /D(k, r), in which d s indicates the sensor node density in an area. Since D(k, r) depends on r, we consider 3 scenarios, i.e.,, dense urban, urban and rural, in which the sensor node density d s and typical communication range r are intrinsically different, due to different population density and radio environment.

We consider a real LPWANs technology LoRaWAN TM , which operates on 868 MHz frequency band in Europe and has a typical link budget of 154 dB [START_REF]LoRaWAN TM Specification[END_REF]. For the path loss model, we choose Hata model for 150 MHz ≤ f ≤ 1000 MHz as recommended by ETSI for GSM 900 MHz [START_REF]ETSI[END_REF]. We add shadowing margin as it's not included in the Hata model and penetration loss as sensor nodes are mostly deployed indoor. Typical values of these two parameters are found in [START_REF] Mishra | Advanced cellular network planning and optimisation[END_REF]. The parameters and calculated typical r are listed in table II. d s can be calculated as the product of the house density and number of sensor nodes per house. For house density, we gather some statistics from INSEE [START_REF]INSEE[END_REF] for different scenarios. For dense urban scenario, we take the city of Paris in 2013 as an example. For urban and rural scenarios, we average statistics from several cities and villages. The estimations of number of sensor nodes per house are also listed in table III. N avg = ds D(k,r) = d s S vp (a k (r)), which is the number of sensor nodes in the Voronoi polygon of a gateway g i . These sensor nodes are nearer to g i than to any other gateways. However, the number of sensor nodes that can actually communicate with g i should be calculated as N real = d s πr 2 . N avg and N real are both represented in figure 4. N avg reflects the number of sensor nodes "allocated" to g i . D(k, r) increases with k, N avg thus decreases with k. A denser deployment can in fact reduce the number of sensor nodes "allocated" to every gateway, thus reducing it's traffic pressure. A gateway can only support packets from a limited number of sensor nodes, i.e.,, the load-capacity of gateway denoted by C load . It depends on the number of frequency channels available, the duration of packets, the interference phenomenon between packets etc. Note that C load of a gateway also increases with k in that packets benefit from an increase in reception diversity. One can imagine an increasing curve representing C load in figure 4, which probably crosses the N real and N avg curves. As sensor nodes in LPWANs send their packets using uncoordinated access schemes, the level of interferences increases with N real and N avg . When N real and N avg are too high compared to C load , we are in the interference-limited regime. Even with k-reception, there can be heavy packet loss. Therefore the position of C load curve is essential to decide when the dimensioning factor is the kcoverage or C load . In dense scenarios, even though we deploy gateways to achieve a certain k-coverage, N real and N avg may be too high compared to C load . One solution is to allocate more frequency resources to gateways, which is not always available. Another solution is to reduce the communication range r by a tilt of the gateway antenna or an artificial reduction of the reception sensibility etc., in order to reduce N real and N avg and thus the interferences, but more gateways need to be deployed in this case. The primary dimensioning factor is thus C load . In sparse cases, by achieving k-coverage, N real and N avg don't exceed C load of gateways, no more gateways need to be deployed. The primary dimensioning factor is thus k-coverage.

In [START_REF] Zozor | Timefrequency aloha-like random access: A scalability study of low-power wide-area networks for iot using stochastic geometry[END_REF], the phenomenon of interferences between packets is studied using a stochastic geometry model for typical LPWANs access schemes, in order to deduce C load without considering k-reception. An extra reference C load curve can be drawn by combining the interference model in [START_REF] Zozor | Timefrequency aloha-like random access: A scalability study of low-power wide-area networks for iot using stochastic geometry[END_REF] and kcoverage model in this article in order to give a more refined study of the dimensioning factors of LPWANs.

VI. CONCLUSION AND FUTURE WORKS

In this article, we study the problem of minimal gateway density ensuring k-coverage in regular deployment patterns in order to give some insights of the dimensioning of the LPWANs. We notice that the gateway density increases almost linearly with coverage degree, revealing that the cost of kcoverage is almost linear and thus scalable. Our method gives the optimal k-coverage patterns among the three regular ones. which confirm the results obtained in [START_REF] Kershner | The number of circles covering a set[END_REF][START_REF] Ge | Planar thinnest deployment pattern of congruent discs which achieves 2-coverage[END_REF]. We thus conjecture that minimal density for general k-coverage among mutually congruent patterns is always achieved among the three regular patterns.

From three real-world scenarios, we show that k-coverage alone is unable to dimension the gateway density, especially in dense populated scenarios, load-capacity of gateway being another essential factor. In future works, we are going to combine the load-capacity model and k-coverage model in order to give a more refined dimensioning of LPWANs.

Fig. 1 .

 1 Fig. 1. Illustration of three regular patterns based deployments. Black points are the positions of gateways. Polygons with blue edges are C 3 (G ). Regions painted in light blue are V 3 (g i ), i.e.,, ∪ G g i C 3 (G ). Polygons with dashed black edges are C 1 (gi ) = V 1 (g i ).Red points are p = argmax p∈V 3 (g i ) d(p, g i ). r denotes a given communication range. a 3 (r) is maximal inter-gateway distance for 3-coverage with the given r.

Fig. 2 .

 2 Fig. 2. α(k) in function of k in three regular patterns

Proposition 4 .

 4 Let Ω ⊂ R 2 be a bounded region and r a given communication range. If gateways are deployed following any regular pattern with inter-gateway distance a k (r) inside Ω ⊕r = {y ∈ R 2 | ∃x ∈ Ω, d(x, y) ≤ r}, defined as the dilation of Ω by r, then Ω is k-covered.

Fig. 3 .

 3 Fig. 3. Illustration of edge effect. Region enclosed by black solid line is Ω, by black dashed line Ω ⊕r . The area between black and blue dashed line is the border area.

Fig. 4 .

 4 Fig. 4. Comparison of Navg and N real in 3 scenarios


Yasmine Labiad
email: labiad.yasmine@gmail.com

Geoffroy Venton
email: geoffroy.venton@aphm.fr

MD Farnault Laure
email: laure.farnault@aphm.fr

Céline Baier
email: celine.baier@yahoo.fr

Julien Colle
email: julien.colle@aphm.fr

Cédric Mercier

MD Ivanov Vadim
email: vadim.ivanov@aphm.fr

Corinne Nicolino-Brunet

Loriod Béatrice
email: beatrice.loriod@inserm.fr

Nicolas Fernandez-Nunez

Labiad Yasmine

MD-PhD Venton Geoffroy

PhD Baier Céline

MD Colle Julien

Mercier Cedric
email: cedric.mercier@aphm.fr

MD Nicolino Corinne
email: corinne.nicolino@aphm.fr

Fernandez-Nunez Nicolas
email: nicolas.fernandeznunez@inserm.fr

Torres Magali
email: magali.torres@univamu.fr

Mattei Jeancamille
email: jeancamille.mattei@gmail.com

Rihet Pascal
email: pascal.rihet@univamu.fr

PhD Nguyen Catherine
email: catherine.nguyen@inserm.fr

Costello Régis
email: regis.costello@free.fr

Prof Régis Costello

MD Mercier Cédric

Mattei Jean-Camille

Pr

A transcriptomic signature predicting septic outcome in patients undergoing autologous stem cell transplantation

Keywords: Systemic Inflammatory Response Syndrome (SIRS), Sepsis, Autologous Hematopoietic Stem Cell Transplantation (AutoHSCT), Transcriptomic Analysis, Treatment related mortality (TRM)

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

Introduction

AutoHSCT is based on the administration of myelosuppressive highdose chemotherapy, followed by infusion of autologous hematopoietic stem cells to obtain hematologic reconstitution. Hematopoietic stem cells (HSCs) infusion reduces chemotherapyinduced myelosuppression period and procedure related mortality rate below 3% [START_REF] Kurnick | Autologous and Isologous Bone Marrow Storage and Infusion in the Treatment of Myelo-Suppression[END_REF][START_REF] Mcfarland W | Autologous bone marrow infusion as an adjunct in therapy of malignant disease[END_REF][START_REF] Clifford | Nitrogenmustard therapy combined with autologous marrow infusion[END_REF]. With few exceptions (solid tumors, autoimmune diseases), autoHSCT is essentially indicated for selected hematological malignancies and considered as a standard treatment in young patients with MM and for relapsed or refractory lymphoma.

Besides direct toxicity of conditioning regimens, deep (<0.5 G/L neutrophils) and prolonged (usually 7-12 days) neutropenia exposes patients to significant risks of infection. The saprophytic gram negative bacilli (such as Escherichia coli) are the most common cause of septic shock [START_REF] Veeraputhiran | BEAM Conditioning Regimen Has Higher Toxicity Compared With HighDose Melphalan for Salvage Autologous Hematopoietic Stem Cell Transplantation in Multiple Myeloma. Clinical lymphoma, myeloma & leukemia[END_REF] and chronic immunosuppression exposes to the risk of fungal infection. An antifungal prophylaxis is usually administered [START_REF] Maertens | European guidelines for antifungal management in leukemia and hematopoietic stem cell transplant recipients: summary of the ECIL 3-2009 update[END_REF] but antimicrobial prophylaxis is less often given because its effectiveness is not clearly established and increases the risk of Clostridium difficile diarrhea [START_REF] Sohn | The role of prophylactic antimicrobials during autologous stem cell transplantation: a singlecenter experience[END_REF]. Unfortunately, it is not possible to foresee which patients will develop a SIRS and/or sepsis. Therefore, it remains impossible to adjust the antibiotic or antifungal prophylaxis to the specific risk profile of each patient.

The main objective of this work was to determine and identify a predictive transcriptomic signature of the SIRS and/or sepsis in patients receiving autoHSCT, leading to the possibility of a preemptive antiinfectious treatment.

Patients, materials and methods

Patients

The prospective study was approved by the institutional review board of the Assistance Publique des Hôpitaux de Marseille (APHM - AORC2012 201208). Written informed consent was obtained from each patient. Patients were admitted in the hematology department of the Conception university hospital for undergoing autoHSCT. All patients were under 65 years and were already followed in the hematology department for MM or highgrade lymphoma. Before autoHSCT, patients were in complete remission (CR) or in partial remission (PR) after conventional chemotherapy. Inclusion criteria were the same as required for being eligible to autoHSCT. Twenty fours patients were included in this study protocol. Twenty one were analyzed. Blood samples were collected for each patient at three moments: before the conditioning regimen (T1), after the conditioning regimen and before the graft infusion (T2) and at the end of the neutropenic phase (T3).

All patients (after written informed consent) hospitalized in the Hematology and Cellular Therapy Department of the university hospital of Marseille between August 2012 and December 2015 have been included. Only the patients (21 in all) in whom the RNA extraction was a success (after quantification and quality control) have been analyzed.

SIRS and sepsis definitions

SIRS and sepsis definition are based on the American College of Chest Physicians society of Critical Care Medicine consensus. SIRS is defined as the systemic inflammatory response to a variety of severe clinical symptoms with at least two of the following criteria: a) Temperature higher than 38 °C or lower than 36 °C b) Heart rate higher than 90 beats/min c) Respiratory rate higher than 20 breaths/min or PaCO2 lower than 32 mmHg d) White blood cell counts higher than 12,000 cells/mm 3 or lower than 4,000 cells/mm 3 , or the presence of more than 10% immature neutrophils. The last criterion cannot be considered in autoHSCT context because of the aplasia phase following HSC infusion [START_REF] Acoc | Definitions for sepsis and organ failure and guidelines for the use of innovative therapies in sepsis[END_REF][START_REF] Robertson | The systemic inflammatory response syndrome[END_REF]. Sepsis is defined as SIRS secondary to documented or suspected infection. Patients with severe sepsis are patients with sepsis and at least one organ dysfunction. Septic choc is defined by severe sepsis associated with refractory hypotension [START_REF] Robertson | The systemic inflammatory response syndrome[END_REF].

Conditioning regimens

Conditioning regimen for therapeutic intensification was high dose melphalan (200 mg/m 2 ) for patients with MM and BEAM for patients with lymphoma (carmustin 300 mg/m2 at day 6, etoposide 150 mg/m2 from day 5 to 2 twice daily, cytarabin 200mg/m2 from day 5 to 2 twice daily and melphalan 140mg/m2 day 1, with autoHSCT on day 0).

Hematopoietic stem cell collection

HSCs mobilization required hematopoietic growth factors (GCSF in most cases). Two procedures have been used to mobilize HSCs. For steadystate collection, GCSF was injected at the dose of 10µg/kgaday. Mobilization chemotherapy consisted in high doses cyclophosphamide (1.5 to 4g/m 2 ) followed by 5µg/kgaday of GCSF. When HSCs collection failed with these usual procedures, plerixafor (SDF1/CXCR4 interaction inhibitor) was used at 240 µg/kg.

PBMCs isolation

Blood samples were centrifuged to separate plasma and other blood components. Concentrate blood was diluted and PBMCs were collected by FicollHystopaque densitygradient centrifugation [START_REF] English | Singlestep separation of red blood cells, granulocytes and mononuclear leukocytes on discontinuous density gradients of FicollHypaque[END_REF].

RNA extraction, quantification quality controls

Depending on cell number, two kits were used for RNA extraction, the RNeasy Mini Kit Qiagen ™ (Qiagen, Valencia, California), which accepts 10 million of cells and the RNeasy Midi Kit Qiagen ™, which accepts up to 100 million cells. RNAs were extracted according to the Qiagen protocol. RNAs were quantified by NanoDrop 1000 (Nano Drop Technologies, San Diego, CA). Optical density was measured at 260 and 280 nm and the ratio 260/280 (> 1.8) indicates its purity. Extracted RNA quality was checked with Agilent 2100 Bioanalyzer ™ (Agilent Technologies, Santa Clara, California). A score on a scale of 0 to 10 was automatically attributed to each sample and corresponded to RNA Integrity Number (RIN). Sample with a RIN under 7 was discarded.

Pangenomic gene expression assay

One hundred nanograms of total RNA was labelled using OneColor MicroarrayBased Gene Expression Analysis: Low Input Quick Amp (LIQA) labelling protocol. 0.6 µg of the purified Cy3 labelled cRNA were hybridized for 17h at 65 °C, at 60 rpm, using the SurePrint G3 human GE 8x60K V2 chips (Agilent Technologies, Santa Clara, California). Microarrays were composed of 62 928 features. Probes synthesized on chips had a size of 60 nucleotides. Microarrays were washed using Gene Expression Wash Buffer Kit (Agilent Technologies) and scanned through the standard Agilent protocol. Data were processed using Feature Extraction software.

Differential gene expression analysis

The library AgiND is implemented in R software in order to analyze and visualize data. AgiND was developed on Bioconductor library model (tagc.univmrs.fr/ComputationalBiology/AgiND/) and is used to diagnose data quality and datamicroarray normalization. Quantile method was used to normalize data; the objective was to homogenize distribution of microarray intensity [START_REF] Bolstad | A comparison of normalization methods for high density oligonucleotide array data based on variance and bias[END_REF]. A filter was applied on row data to delete controls, then a second filter was applied to delete genes which were expressed under the background in at least 80% of samples in each group (SIRS - , SIRS+, Sepsis+).

To test cofactors effects (gender, treatment, infection) on gene expression, GeneANOVA software was used to perform ANalysis Of Variance (ANOVA) on normalized data to determine an estimation of the contribution of each factor (genes, gender, treatment, infection) in gene expression variation.

Global ANOVA model is given in the following formula: Y = µ + β 1 G + β 2 T + β 3 I + ε, where Y is explained variable, µ is global mean, β 1 , β 2 , β 3 , are model coefficients, and G, T, I are the quantitative variables; β 1 G, is the gene effects, β 2 T, is the treatment effects, β 3 I, the infection effects, and ε is the error term [START_REF] Brown | Knowledgebased analysis of microarray gene expression data by using support vector machines[END_REF]. Differential gene expression analysis was performed using linear Models for Microarray Data (Limma). Limma is a multivariate analysis and takes into account cofactorseffect tested by ANOVA analysis (treatment and gender) (Table 2). In order to determine infection impact on gene expression and on the heat map, new gene expression was calculated after subtracting gender and treatment cofactors effects. Unsupervised hierarchical clustering was applied on adjusted gene expression median adjusted data to group genes and samples, according to their

Highthroughput quantitative PCR

RTPCR was performed using SuperScript™ VILO™ MasterMix protocol described by Invitrogen. Sixty nanogram of RNA of each sample was retrotranscribed, using 4µL of SuperScript™ VILO™ MasterMix, and RNase DNase Free water for a final volume of 20µL. Mix was incubated 10 min at 25 °C, 60min at 42 °C and 5min at 85°C. Quantitative PCR was performed with FlexSix array on BioMark™ HD (Fluidigm). A preamplification of each sample was applied according to the protocol provided by Fluidigm. The preamplification step was followed by an Exonuclease I treatment (BioLegend) to remove unincorporated primers. The final product was diluted 5fold using 18µl of TE Buffer (10 mM TrisHCl, 1mM EDTA). In a second part, 12 x 12 (samples x primers) qRTPCR reactions are performed for each primer pair on each sample on the 12 x 12 array (FlexSix). We used the EvaGreen detection assay for following standard Fluidigm protocols. Ct values were calculated from the system software Biomark RealTime PCR Analysis (Fluidigm). The primers used were:

Gene R F SLC18B1 5'GCAGGACAGCTTTTCAGTATCAC3' 5'CCTGGCCTTAAACATCACCG3' CNN3 5'GGCTGGCTCCTTTATTAGTGC3' 5'AAGCTGGCCAAAGTGTAATTG3' MTMR8 5'ACTTAAGTGGGGAGAGGGGT3' 5'GAGGCAGACTACTCCAAGCA3' GPAT2 5'GCCCAGAGAAGCCTACATCA3' 5'CATCAGAAGCTCCTGGGGGA3' PLCG1 5'ACAGGAATCTTGGTGCTTCAGT3' 5'CAGGGAGGTACATGGCCAAT3' ANKRD42 5'CGCCCATGAAAAGCTGCATA3' 5'GGAGCAAATCTGACAGCCCA3' GAPDH 5'CCACCACCCTGTTGCTGTGA3' 5'CCCACTCCTCCACCTTTGAC3' EDAR 5'ACATGAGCTGACACTGGCTG3' 5'TGAGTGTGCCATTCCAGGAT3' TRAV3 5'GCCTCGGTTGGGGTATTGAA3' 5'CTCAGCCGGAAGATCAGGTC3' CHAT 5'CAGCAGAACATCTCCGTCGT3' 5'ATGGCCATTGACAACCACCT3' LOC100289230 5'GTGCTTCCGGAAAACGTAAA3' 5'TCCTGTGCCCGTAATTTCTC3'

Results

Patient's analysis

Twentyfour patients were included in the study, among these patients; 21 validated the molecular criteria for transcriptomic analysis. Among these 21 patients, 6 patients did not develop a fever or SIRS (28.6%), nine patients developed SIRS (42.6%), 5 a sepsis (23.8%) and 1 a severe sepsis (5%).

Patients' clinical data are summarized in the Table 1.

Pangenomic gene expression

The 21 samples were analyzed on Agilent microarrays 'SurePrint G3 GE 8x60K human.' After 17 hours of hybridization, the chips were washed and scanned. Results passed microarrays quality controls.

Raw data were transformed into log2 and normalized with quantile method. 24 046 probes expressing a higher signal than background (in at least one group) have been selected. Two methods were used for statistical analysis: ANOVA analysis to measure the impact of each factor on gene expression variation (infection, gender, treatment) and Limma analysis on three groups (SIRS - , SIRS+, sepsis +) with the following cofactors: gender and treatment, to define differential gene expression (Figure 1). ANOVA analysis was performed on the 24 046 probes to estimate impact of each factor (infection, gender, treatment) in gene expression variation. Pvalue was calculated for each factor. For all factors (genes, infections, gender, and treatment) pvalues were <10 4 (Table 2).

Infection F score was the highest, suggesting that 'infection' had the greatest impact on the gene expression. Genes F score was of 115.45 (pvalue <10

4

) and explains genes fluctuations. Treatment and gender had an impact on the variation of gene expression with a F score of respectively 176.21 and 156.07 (pvalue <10

4

). Unsupervised hierarchical clustering method was used to classify the differently expressed genes identified by Limma analysis. Expression similarity profiles of the genes were grouped on the horizontal axis and samples on the vertical axis. Gene expression profiles are shown in heat map (Figure 2). With a FDR (False Discovery Rate) fixed to 5%, 11 genes differentially expressed were identified between the patients who did not have temperature (SIRS) and the patients who developed SIRS and sepsis (taking account effect of gender and treatment). The eleven differentially expressed genes were: CHAT, CNN3, ANKRD42, LOC100505725, EDAR, GPAT2, ENST00000390425, MTRM8, LOC10289230 and XLOC005643 (Table 3). Gene expression profiling distinguished two groups: patients who did not develop temperature, on the one hand, and patients with SIRS or sepsis, on the other hand. CHAT, CNN3, C6orf192, ANKRD42, LOC100505725, EDAR, GPATZ, ENST00000390425, MTRM8, LOC10289230 were over expressed and XLOC005643 was underexpressed in patient samples with SIRS or Sepsis in contrast to patients who did not develop fever and SIRS.

SVM

SVM and leaveoneout crossvalidation were used to classify patients according to their gene expression. 21 samples were separated into two groups, the first group was composed of 15 SIRS and septic patients and the second of the 6 patients who did not have temperature. SIRS and sepsis patients were considered as positive experiments, and the other as negative. All 15 patients of the positive experiments were classified as positive, staying in positive class (true positives=15) and none was transferred from negative class to positive (False negatives=0). On the 6 patients of the negative experiments, all were classified as negative, all retained in negative class (true negatives=15) and none was recruited into negative class from positives (false positives=0). We performed a Fisher exact test on our results; the pvalue = 1.84 E5.

RTqPCR

In order to confirm the microarray gene expression results, RTqPCR was performed on 9 genes that composed the transcriptomic signature. The LOC 100289230 gene was differently expressed (pvalue = 0.003) in patients who developed SIRS or sepsis compared with patients who did not. TRAV3, EDAR, PLCG1AS1001, GPAT2, MTRM8, CNN3, and SLC18B1 were also differentially expressed with pvalues of 0.004, 0.01, 0.01, 0.005, 0.009, 0.09 and 0.01, respectively (Figure 3).

Discussion and conclusion

This clinical study identified eleven genes significantly and differentially expressed in patients who developed SIRS or sepsis after the conditioning regimen for autoHSCT. Ten of them were up regulated (CHAT, CNN3, ANKRD42, LOC100505725, EDAR, GPATZ, ENST00000390425, MTRM8, C6orf192 and LOC10289230) while only one was downregulated (XLOC005643). All patients with this specific transcriptomic signature developed a SIRS or sepsis within 48 hours (range 48 hours7 days) following conditioning regimen. All patients were classified in the right group according to their gene expression and based on SVMs analysis. After a wide scientific literature review, genes composing our predictive signature are not directly involved in sepsis or infection pathways. In this cohort of 21 patients, 9 developed a SIRS and 5 a sepsis. Only one patient developed a severe sepsis, and no patient had septic shock, thus impeding the possibility to identify a specific transcriptomic signature predictive for these lifethreatening conditions. In addition, since a SIRS/sepsis predictive signature before the conditioning regimen was not identified, the transcriptomic signature was not linked to the patient preauto HSCT status but depended on the conditioning regimen patient's response.

We wondered about the definition of sepsis and SIRS and the clustering of sirs and sepsis; first, white blood cells count criteria is not relevant in patients in deep aplasia. Furthermore, in the same way, patients in deep aplasia present grade IIIII anemia especially after BEAM conditioning regimen. In patients with no cardiovascular and/or pulmonary comorbidity, hemoglobin until 8g/dl is tolerated. However, that often results in an increase of the heart rate higher than 90 beats/min and/or respiratory rate higher than 20 breaths/min, especially in patients with fever.

Fever is neither sensitive or specific in conventional patients. But, in our severely immunocompromised patients fever is more sensitive and specific than in immunocompetent patients. Nevertheless, it is not unusual to start an antibiotic therapy in patients with no fever but with a microbiological documentation and/or a major increase of the C reactive protein only.

At last, we have been very drastic on the definition of our sepsis patients group. Only the patients with fever and a microbiological documentation have been considered in sepsis. Anyway, our immunocompromised patients are paucisymtpomatic and very few infections were clinically probable.

Our transcriptomic signature predicts SIRS/sepsis profiles and is more robust than the main confounding factors, such as conditioning regimen, type or gender. BEAM conditioning regimen was more myelosuppressive than melphalan alone and men have had a more significant risk to develop infectious complications than women [START_REF] Adrie | Influence of gender on the outcome of severe sepsis: a reappraisal[END_REF]. AutoHSCT patients affected by MM are conditioned by high dose of melphalan while patients with lymphoma by high dose BEAM chemotherapy, meaning that treatment and pathology are confounding factors. SAM and ANOVA analyses were performed on the data of patient samples before chemotherapy, and no differentially expressed genes were found between patients affected by lymphoma or MM.

This work proposes a transcriptomic approach of the sepsis issue during autoHSCT neutropenic phase. Vanska et al. have shown that high pentraxin 3 level predicted septic shock and bacteremia at the onset of febrile neutropenia after intensive chemotherapy of hematologic patients [START_REF] Vänskä | High pentraxin 3 level predicts septic shock and bacteremia at the onset of febrile neutropenia after intensive chemotherapy of hematologic patients[END_REF]. Nonetheless, high pentraxin 3 level had only a predictive value for septic shock in patients who already had a febrile neutropenia. In contrast, our predictive transcriptomic signature identifies patients who have a major risk to develop SIRS and/or sepsis at least 48 hours (range 48 hours-7 days) before onset of fever. In order to confirm our results, our transcriptomic signature has been validated on a 10 patient's prospective validation cohort (data not shown). Since total gene expression analysis by microarrays is not possible in clinical routine for time and costeffective reasons, RTqPCR analysis on a blood sample of the eleven deregulated genes will have to be developed in order to assess the possibility of a routine use.

Prophylactic antifungal and/or antimicrobial treatments have not proven a high efficiency regarding the outcome in patients undergoing highly myeloablative chemotherapy. For example, the use of ciprofloxacin induces a 20% reduction of infection rates but lead to 70% increase in the development of cifloxacin resistance [START_REF] Pohlen | Ciprofloxacin versus colistin prophylaxis during neutropenia in acute myeloid leukemia: two parallel patient cohorts treated in a single center[END_REF]. Early identification of patients who will develop SIRS and/or sepsis could perhaps contribute to a better use of antiinfectious agents as preemptive treatment instead of a prophylactic treatment, although this is only an hypothesis by should be tested in a prospective clinical trial. A limitation of our study, directly related to the small number of patients and of infectious events, is the impossibility to identify a specific profile for microbial or fungal or viral infections, in order to precisely orientate the preemptive treatment. Finally, identification of high vs low infectious risk patients after myeloablative chemotherapy, could help to select patients with a safe septic profile and allows an early hospital discharge or even outpatient based blood stem cell transplantation, in order to develop a more rational utilization of hospital resources but still maintaining optimal safety conditions [1619]. A validation of this transcriptomic signature in a prospective and larger cohort of patients is necessary to have a stronger clinical impact. Another strategy (work in progress) is to validate in RTqPCR only the eleven genes of interest in a prospective and larger cohort. Ch : Chromosome, +1 : Forward strand, from 3' to 5', -1 : Reverse strand, from 5' to 3'

  expression using 'TMeV' (Tigr MultiExperiment Viewer) MeV: MultiExperiment Viewer | Part of the TM4 Microarray Software Suite [http://www.tm4.org/mev/]. Pearson correlation was used, and clusters were grouped on the basis of average linkage method. Support Vector Machines (SVMs) SVMs were applied to predict classification of patients according to the predictive signature. SVMs use training set in which genes known to be related to each other by function or samples related to a group are described as positive examples and genes or samples known not to be members of that class are labelled as negative examples. In this study, samples were attributed to two groups: SIRS and sepsis patients in the first group and patients with no temperature in the second. They were combined into a set of training examples used by SVM to distinguish class members from non members on the basis of expression data. After learning the class expression features, the SVM can be used to recognize and classify each sample on the basis of their expression [11, 12]. SVMs tool is implemented in TMeV software MeV: MultiExperiment Viewer | Part of the TM4 Microarray Software Suite. [http://www.tm4.org/mev/].

Figure 1 :

 1 Figure 1: Differential gene expression flow chart

Figure 2 :

 2 Figure 2: Gene expression profile adjusted on the effects of the cofactors

Figure 1 :Figure1Figure 2 :Figure2Figure 3 :

 123 Figure 1: Differential genes expression flow-chart

Figure3

  Figure3

Table legends :Table 1 : Patients, pathologies and autoHSCT characteristicsTable 2 : cofactors effect on gene expression.

 legends12

	ANOVA analysis was performed to test the cofactors impact (infection, treatment and gender) on
	gene expression for samples taken at T2 (after chemotherapy). With pvalues <0, 05 infection,
	treatment and gender have a significant effect on the gene expression. DF: Degrees of Freedom

Table 3 : Differentially expressed gene characteristics

 3

	Ch: Chromosome, +1: Forward strand, from 3' to 5', 1: Reverse strand, from 5' to 3'

Table 3 : Differentially expressed gene characteristics.

 3

	Gene	Complete name	Ensembl ID	Location	Sens
	SLC18B1 / C6ORF192	solute carrier family 18 member B1	ENSG00000146409	Chr 6: 132,769,370-132,798,553	-1
	CNN3	calponin 3	ENSG00000117519	Chr 1: 94,896,949-94,927,278	-1
	MTMR8	myotubularin related protein 8	ENSG00000102043	Chr X: 64,268,081-64,395,431	-1
	LOC100505725 PLCG1-AS1-001 / TOP1-AS1 /	PLCG1 antisense RNA 1	ENSG00000226648	Chr 20: 41,098,329-41,138,003	-1
	CHAT	choline O-acetyltransferase	ENSG00000070748	Chr 10: 49,609,095-49,665,104	1
	EDAR	ectodysplasin A receptor	ENSG00000135960	Chr 2: 108,894,471-108,989,372	-1
	ANKRD42	ankyrin repeat domain 42	ENSG00000137494	Chr 11: 83,193,739-83,260,694	1
	GPAT2	glycerol-3-phosphate acyltransferase 2, mitochondrial	ENSG00000186281	Chr 2: 96,021,946-96,039,451	-1
	ENST00000390425/ TRAV3	T cell receptor alpha variable 3 (gene/pseudogene)	ENSG00000211777	Chr 14: 21,723,713-21,724,321	1
	LOC100289230	NS	NS	Chr 5: 98,929,134-98,931,009	1
	XLOC_005643	lnc-CMAHP-1:1 / linc-FAM65B-1/RP3-425P12.2	ENSG00000230372	Chr 6: 25,061,853-25,063,735	-1

Table2

Acknowledgments

We would like to thank INSERM, AixMarseille Université and Advanced BioDesign (Parc Technologique de Lyon Bâtiment Cèdre 1, 97 Allée Alexandre Borodine, 69 800 SaintPriest - Lyon) for grants.

We are grateful to the patients who gave their informed consent to the use of their samples for research. We are grateful to the IBiSA Transcriptomics and Genomics MarseilleLuminy (TGML) platform was supported by the France Génomique National infrastructure. We thank Laurence Borge for assistance and the use of the cell culture platform facilities (CRCM U1068, Marseille) Plateforme de Culture Cellulaire de MarseilleLuminy, bâtiment TPR2 163 Avenue de Luminy, 13009 Marseille.

We also thank Geneviève Victorero and Noushine MossadeghKeller for technical supports.

Funding

This work was supported by grants from APHM, Assistance Publique - Hôpitaux de Marseille (AORC APHM Junior), and AixMarseille Université, Advanced BioDesign. TGML platform supported by the France Génomique

Conflict of interest

All authors declare no financial conflict of interest Microarray analysis revealed 11 genes differentially expressed. This genes cluster distinguished SIRS or sepsis patients from patients who didn't develop any fever or SIRS. Gram-positive bacteria 75%

Staphylococcus hominis 1

Staphylococcus epidermidis 2

Staphylococcus aureus 1

Streptococcus mitis 1

Clostridium difficile 1

Gram-negative bacteria 25%

Escherichia coli 1

Klebsiella pneumonia 1

Documented fungal infections 0 (0%)


David Adrian

Karthikeyan Bhargavan

Zakir Durumeric

Pierrick Gaudry

Matthew Green

J Alex Halderman

Nadia Heninger

Drew Springall

Emmanuel Thomé

Luke Valenta

Benjamin Vandersloot

Eric Wustrow

Santiago Zanella-Béguelin

Paul Zimmermann

Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice

We investigate the security of Diffie-Hellman key exchange as used in popular Internet protocols and find it to be less secure than widely believed. First, we present Logjam, a novel flaw in TLS that lets a man-in-the-middle downgrade connections to "export-grade" Diffie-Hellman. To carry out this attack, we implement the number field sieve discrete logarithm algorithm. After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logarithms in that group in about a minute. We find that 82% of vulnerable servers use a single 512-bit group, and that 8.4% of Alexa Top Million HTTPS sites are vulnerable to the attack. a In response, major browsers have changed to reject short groups.

We go on to consider Diffie-Hellman with 768-and 1024bit groups. We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources. A small number of fixed or standardized groups are used by millions of servers; performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers. A close reading of published NSA leaks shows that the agency's attacks on VPNs are consistent with having achieved such a break. We conclude that moving to stronger key exchange methods should be a priority for the Internet community.

Active attacks on export ciphers in TLS

We introduce Logjam, a new attack on TLS by which a man-in-the-middle attacker can downgrade a connection to export-grade cryptography. This attack is reminiscent of the FREAK attack 1 but applies to the ephemeral Diffie-Hellman ciphersuites and is a TLS protocol flaw rather than an implementation vulnerability. We present measurements that show that this attack applies to 8.4% of Alexa Top Million HTTPS sites and 3.4% of all HTTPS servers that have browser-trusted certificates.

To exploit this attack, we implemented the number field sieve discrete logarithm algorithm and carried out precomputation for two 512-bit Diffie-Hellman groups used by more than 92% of the vulnerable servers. This allows us to compute individual discrete logarithms in about a minute. Using our discrete logarithm oracle, we can compromise connections to over 7% of Alexa Top Million HTTPS sites. Discrete logarithms over larger groups have been computed before, 2 but, as far as we are aware, this is the first time they have been exploited to expose concrete vulnerabilities in real-world systems.

Risks from common 1024-bit groups

We explore the implications of precomputation attacks for 768-and 1024-bit groups, which are widely used in practice a Except where otherwise noted, the experimental data and network measurements for this article were obtained in early 2015.

INTRODUCTION

Diffie-Hellman (DH) key exchange is a popular cryptographic algorithm that allows Internet protocols to agree on a shared key and negotiate a secure connection. It is fundamental to protocols such as Hypertext Transport Protocol Secure (HTTPS), Secure Shell (SSH), Internet Protocol Security (IPsec), Simple Mail Transfer Protocol Secure (SMTPS), and other protocols that rely on Transport Layer Security (TLS). Many protocols use Diffie-Hellman to achieve perfect forward secrecy, the property that a compromise of the long-term keys used for authentication does not compromise session keys for past connections. We examine how Diffie-Hellman is commonly implemented and deployed with common protocols and find that, in practice, it frequently offers less security than widely believed.

There are two reasons for this. First, a surprising number of servers use weak Diffie-Hellman parameters or maintain

The full version of this paper was published in Proceedings of the 22nd Conference on Computer and Communications Security (CCS), October 2015, ACM. The full paper and additional materials are available at https://weakdh.org/.

support for obsolete 1990s-era "export-grade" cryptography. More critically, the common practice of using standardized, hard-coded, or widely shared Diffie-Hellman parameters has the effect of dramatically reducing the cost of large-scale attacks, bringing some within range of feasibility.

The current best technique for attacking Diffie-Hellman relies on compromising one of the private exponents (a, b) by computing the discrete logarithm of the corresponding public value (g a mod p, g b mod p). With state-of-the-art number field sieve algorithms, computing a single discrete logarithm is more difficult than factoring a Rivest-Shamir-Adleman (RSA) modulus of the same size. However, an adversary who performs a large precomputation for a prime p can then quickly calculate arbitrary discrete logarithms in that group, amortizing the cost over all targets that share this parameter. Although this fact is well known among mathematical cryptographers, it seems to have been lost among practitioners deploying cryptosystems. We exploit it to obtain the following results. logarithm. In fact, as illustrated in Figure 1, a single large precomputation on p can be used to efficiently break all Diffie-Hellman exchanges made with that prime.

Diffie-Hellman is typically implemented with prime fields and large group orders. In this case, the most efficient known algorithm for computing discrete logarithms is the Number Field Sieve (NFS). [START_REF] Gordon | Discrete logarithms in GF(p) using the number field sieve[END_REF][START_REF] Joux | Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method[END_REF][START_REF] Schirokauer | Virtual logarithms[END_REF] The algorithm has four stages with different computational properties. The first three steps are only dependent on the prime p and comprise most of the computation.

First is polynomial selection, in which one finds a polynomial f (z) defining a number field Q[z]/f (z) for the computation. This parallelizes well and is only a small portion of the runtime.

In the second stage, sieving, one factors ranges of integers and number field elements in batches to find many relations of elements, all of whose prime factors are less than some bound B (called B-smooth). Sieving parallelizes well, but is computationally expensive, because we must search through and attempt to factor many elements.

In the third stage, linear algebra, we construct a large, sparse matrix consisting of the coefficient vectors of prime factorizations we have found. This stage can be parallelized in a limited fashion, and produces a database of logarithms which are used as input to the final stage.

The final stage, descent, actually deduces the discrete logarithm of the target y. We re-sieve until we find a set of relations that allow us to write the logarithm of y in terms of the logarithms in the precomputed database. Crucially, descent is the only NFS stage that involves y (or g), so polynomial selection, sieving, and linear algebra can be done once for a prime p and reused to compute the discrete logarithms of many targets.

The numerous parameters of the algorithm allow some flexibility to reduce time on some computational steps at the expense of others. For example, sieving more will result in a smaller matrix, making linear algebra cheaper, and doing more work in the precomputation makes the final descent step easier.

Standard primes

Generating safe primes b can be computationally burdensome, so many implementations use standardized and still considered secure. We estimate the computational resources necessary to compute discrete logarithms in groups of these sizes, concluding that 768-bit groups are within range of academic teams, and 1024-bit groups may plausibly be within range of nation-state adversaries. In both cases, individual logarithms can be quickly computed after the initial precomputation.

We then examine evidence from published Snowden documents that suggests that the National Security Agency (NSA) may already be exploiting 1024-bit Diffie-Hellman to decrypt Virtual Private Network (VPN) traffic. We perform measurements to understand the implications of such an attack for popular protocols, finding that an attacker who could perform precomputations for ten 1024-bit groups could passively decrypt traffic to about 66% of Internet Key Exchange (IKE) VPNs, 26% of SSH servers, and 24% of popular HTTPS sites.

Mitigations and lessons

In response to the Logjam attack, mainstream browsers have implemented a more restrictive policy on the size of Diffie-Hellman groups they accept, and Google Chrome has discontinued support for finite field key exchanges. We further recommend that TLS servers disable export-grade cryptography and carefully vet the Diffie-Hellman groups they use. In the longer term, we advocate that protocols migrate to elliptic curve Diffie-Hellman.

DIFFIE-HELLMAN CRYPTANALYSIS

Diffie-Hellman key exchange was the first published publickey algorithm. [START_REF] Diffie | New directions in cryptography[END_REF] In the simple case of prime groups, Alice and Bob agree on a prime p and a generator g of a multiplicative subgroup modulo p. Then each generates a random private exponent, a and b. Alice sends g a mod p, Bob sends g b mod p, and each computes a shared secret g ab mod p. While there is also a Diffie-Hellman exchange over elliptic curve groups, we address only the "mod p" case.

The security of Diffie-Hellman is not known to be equivalent to the discrete logarithm problem, but computing discrete logarithms remains the best known cryptanalytic attack. An attacker who can find the discrete logarithm x from y = g x mod p can easily find the shared secret.

Textbook descriptions of discrete logarithm algorithms can be misleading about the computational tradeoffs, for example by optimizing for computing a single discrete To ensure agreement on the negotiation messages, and to prevent downgrade attacks, each party computes the TLS master secret from g ab and calculates a Message Authentication Code (MAC) of its view of the handshake transcript. These MACs are exchanged in a pair of Finished messages and verified by the recipients.

To comply with 1990s-era U.S. export restrictions on cryptography, SSL 3.0 and TLS 1.0 supported reduced-strength DHE_EXPORT ciphersuites that were restricted to primes no longer than 512 bits. In all other respects, DHE_EXPORT protocol messages are identical to DHE. The relevant export restrictions are no longer in effect, but many servers maintain support for backward compatibility.

To understand how HTTPS servers in the wild use Diffie-Hellman, we modified the ZMap [START_REF] Durumeric | Fast Internet-wide scanning and its security applications[END_REF] While the TLS protocol allows servers to generate their own Diffie-Hellman parameters, just two 512-bit primes account for 92.3% of Alexa Top Million domains that support DHE_EXPORT (Table 1), and 92.5% of all servers with browser-trusted certificates that support DHE_EXPORT. The most popular 512-bit prime was hard-coded into many versions of Apache; the second most popular is the mod_ssl default for DHE_EXPORT.

Active downgrade to export-grade DHE

Given the widespread use of these primes, an attacker with the ability to compute discrete logarithms in 512-bit groups could efficiently break DHE_EXPORT handshakes for about 8% of Alexa Top Million HTTPS sites, but modern browsers never negotiate export-grade ciphersuites. To circumvent this, we show how an attacker can downgrade a regular DHE connection to use a DHE_EXPORT group, and thereby break both the confidentiality and integrity of application data.

The attack, which we call Logjam, is depicted in Figure 2 and relies on a flaw in the way TLS composes DHE and Diffie-Hellman parameters. A prominent example is the Oakley groups, [START_REF] Orman | The Oakley key determination protocol[END_REF] which give "safe" primes of length 768 (Oakley Group 1), 1024 (Oakley Group 2), and 1536 (Oakley Group 5). These groups were published in 1998 and have been used for many applications since, including IKE, SSH, Tor, and Off-the-Record Messaging (OTR).

When primes are of sufficient strength, there seems to be no disadvantage to reusing them. However, widespread reuse of Diffie-Hellman groups can convert attacks that are at the limits of an adversary's capabilities into devastating breaks, since it allows the attacker to amortize the cost of discrete logarithm precomputation among vast numbers of potential targets.

ATTACKING TLS

TLS supports Diffie-Hellman as one of several possible key exchange methods, and prior to public disclosure of our attack, about two-thirds of popular HTTPS sites supported it, most commonly using 1024-bit primes. However, a smaller number of servers also support legacy "export-grade" Diffie-Hellman using 512-bit primes that are well within reach of NFS-based cryptanalysis. Furthermore, for both normal and export-grade Diffie-Hellman, the vast majority of servers use a handful of common groups.

In this section, we exploit these facts to construct a novel attack against TLS, which we call the Logjam attack. First, we perform NFS precomputations for the two most popular 512bit primes on the web, so that we can quickly compute the discrete logarithm for any key exchange message that uses one of them. Next, we show how a man-in-the-middle, so armed, can attack connections between popular browsers and any server that allows export-grade Diffie-Hellman, by using a TLS protocol flaw to downgrade the connection to export-strength and then recovering the session key. We find that this attack with our precomputations can compromise connections to about 8% of HTTPS servers among Alexa Top Million domains.

TLS and Diffie-Hellman

The TLS handshake begins with a negotiation to determine the cryptographic algorithms used for the session. The client sends a list of supported ciphersuites (and a random nonce cr) within the ClientHello message, where each ciphersuite specifies a key exchange algorithm and other primitives. The server selects a ciphersuite from the client's list and signals its selection in a ServerHello message (containing a random nonce sr).

TLS specifies ciphersuites supporting multiple varieties of Diffie-Hellman. Textbook Diffie-Hellman with unrestricted strength is called "ephemeral" Diffie-Hellman, or DHE, and is identified by ciphersuites that begin with TLS_DHE_*. c In DHE, the server is responsible for selecting the Diffie-Hellman parameters. It chooses a group (p, g), computes g b , and sends a ServerKeyExchange message containing a signature over the tuple (cr, sr, p, g, g b ) using the long-term signing key from its certificate. The client verifies the signature and responds with a ClientKeyExchange message containing g a . c New ciphersuites that use elliptic curve Diffie-Hellman (ECDHE) are gaining in popularity, but we focus exclusively on the traditional prime field variety. DHE_EXPORT. When a server selects DHE_EXPORT for a handshake, it proceeds by issuing a signed ServerKeyExchange message containing a 512-bit p 512 , but the structure of this message is identical to the message sent during standard DHE ciphersuites. Critically, the signed portion of the server's message fails to include any indication of the specific ciphersuite that the server has chosen. Provided that a client offers DHE, an active attacker can rewrite the client's ClientHello to offer a corresponding DHE_EXPORT ciphersuite accepted by the server and remove other ciphersuites that could be chosen instead. The attacker rewrites the ServerHello response to replace the chosen DHE_EXPORT ciphersuite with a matching non-export ciphersuite and forwards the ServerKeyExchange message to the client as is. The client will interpret the export-grade tuple (p 512 , g, g b ) as valid DHE parameters chosen by the server and proceed with the handshake. The client and server have different handshake transcripts at this stage, but an attacker who can compute b in close to real time can then derive the master secret and connection keys to complete the handshake with the client. There are two remaining challenges in implementing this active downgrade attack. The first is to compute individual discrete logarithms in close to real time, and the second is to delay handshake completion until the discrete logarithm computation has had time to finish.

512-bit discrete logarithm computations

We modified CADO-NFS [START_REF] Zimmermann | CADO-NFS, an implementation of the number field sieve algorithm[END_REF] to implement the number field sieve discrete logarithm algorithm and applied it to the top two DHE_EXPORT primes shown in Table 1. Precomputation took seven days for each prime, after which computing individual logarithms requires a median of 70 seconds.

Precomputation. As illustrated in Figure 1, the precomputation phase includes the polynomial selection, sieving, and linear algebra steps. For this precomputation, we deliberately sieved more than strictly necessary. This enabled two optimizations: first, with more relations obtained from sieving, we eventually obtain a larger database of known logarithms, which makes the descent faster. Second, more sieving relations also yield a smaller linear algebra step, which is desirable because sieving is much easier to parallelize than linear algebra.

For the polynomial selection and sieving steps, we used idle time on 2000-3000 microprocessor cores in parallel. Polynomial selection ran for about 3hrs (7,600 core-hours). Sieving ran for 15hrs (21,400 core-hours). This sufficed to collect 40mn relations of which 28mn were unique, involving 15mn primes of at most 27 bits.

From this data set, we obtained a square matrix with 2.2mn rows and columns, with 113 nonzero coefficients per row on average. We solved the corresponding linear system on a 36-node cluster using the block Wiedemann algorithm. [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF][START_REF] Thomé | Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm[END_REF] Using unoptimized code, the computation finished in 120hrs (60,000 core-hours).

The experiment above was done with CADO-NFS in early 2015. As of 2017, release 2.3 of CADO-NFS [START_REF] Zimmermann | CADO-NFS, an implementation of the number field sieve algorithm[END_REF] performs 20% faster for sieving, and drastically faster for linear algebra, since 9,000 core-hours suffice to solve the same linear system on the same hardware. In total, the wall-clock time for each precomputation was slightly over one week in 2015, and is reduced to about two days with current hardware and more recent software.

Descent. Once this precomputation was finished, we were able to run the final descent step to compute individual discrete logarithms in about a minute. We implemented the descent calculation in a mix of Python and C. On average, computing individual logarithms took about 70sec, but the time varied from 34sec to 206sec on a server with two 18-core Intel Xeon E5-2699 CPUs. For purposes of comparison, a single 512-bit RSA factorization using the CADO-NFS implementation takes about four days of wall-clock time on the computer used for the descent. [START_REF] Zimmermann | CADO-NFS, an implementation of the number field sieve algorithm[END_REF]

Active attack implementation

The main challenge in performing this attack is to compute the shared secret g ab before the handshake completes in order to forge a Finished message from the server. With our descent implementation, the computation takes an average of 70sec, but there are several ways an attacker can work around this delay:

Non-browser clients. Different TLS clients impose different time limits, after which they kill the connection. Command-line clients such as curl and git have long or no timeouts, and we can hijack their connections without difficulty.

TLS warning alerts. Web browsers tend to have shorter timeouts, but we can keep their connections alive by sending TLS warning alerts, which are ignored by the browser but reset the handshake timer. For example, this allows us to keep Firefox TLS connections alive indefinitely.

Ephemeral key caching. Many TLS servers do not use a fresh value b for each connection, but instead compute g b once and reuse it for multiple negotiations. For example, F5 BIG-IP load balancers will reuse g b by default. Microsoft Schannel caches g b for two hours -this setting is hardcoded. For these servers, an attacker can compute the discrete logarithm of g b from one connection and use it to attack later handshakes. In these cases, a man-in-the-middle can record the handshake and decrypt the False Start payload at leisure.

NATION-STATE THREATS TO DIFFIE-HELLMAN

The previous sections demonstrate the existence of practical attacks against Diffie-Hellman key exchange as currently used by TLS. However, these attacks rely on the ability to downgrade connections to export-grade cryptography. In this section we address the following question: how secure is Diffie-Hellman in broader practice, as used in other protocols that do not suffer from downgrade, and when applied with stronger groups?

To answer this question we must first examine how the number field sieve for discrete logarithms scales to 768and 1024-bit groups. As we argue below, 768-bit groups in relatively widespread use are now within reach for academic computational resources. Additionally, performing precomputations for a small number of 1024-bit groups is plausibly within the resources of nation-state adversaries. The precomputation would likely require special-purpose hardware, but would not require any major algorithmic improvements. In light of these results, we examine several standard Internet security protocols -IKE, SSH, and TLS -to determine their vulnerability. Although the cost of the precomputation for a 1024-bit group is several times higher than for an RSA key of equal size, a one-time investment could be used to attack millions of hosts, due to widespread reuse of the most common Diffie-Hellman parameters. Finally, we apply this new understanding to a set of recently published documents to evaluate the hypothesis that the National Security Agency has already implemented such a capability.

Scaling NFS to 768-and 1024-bit Diffie-Hellman

Estimating the cost for discrete logarithm cryptanalysis at larger key sizes is far from straightforward due to the complexity of parameter tuning. We attempt estimates up to 1024-bit discrete logarithm based on the existing literature and our own experiments but further work is needed for greater confidence. We summarize all the costs, measured or estimated in Table 2.

DH-768: done in 2016. When the ACM CCS version of this article was prepared, the latest discrete logarithm record was a 596-bit computation. Based on that work, and on prior experience with the 768-bit factorization record in 2009, [START_REF] Kleinjung | Factorization of a 768-bit RSA modulus[END_REF] we made the conservative prediction that it was possible, as explained in Section 2, to put more computational effort into sieving for the discrete logarithm case than for factoring, so that the linear algebra step would run on a slightly smaller matrix. This led to a runtime estimate of around 37,000 coreyears, most of which was spent on linear algebra.

This estimate turned out to be overly conservative, for several reasons. First, there have been significant improvements in our software implementation (Section 3.3). In addition, our estimate did not use the Joux-Lercier alternative polynomial selection method, [START_REF] Joux | Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method[END_REF] which is specific to discrete logarithms. For 768-bit discrete logarithms, this polynomial selection method leads to a significantly smaller computational cost.

In 2016, Kleinjung et al. completed a 768-bit discrete logarithm computation. [START_REF] Kleinjung | Computation of a 768-bit prime field discrete logarithm[END_REF] While this is a massive computation on the academic scale, a computation of this size has likely been within reach of nation-states for more than a decade. This data is mentioned in Table 2.

DH-1024: Plausible with nation-state resources. Experimentally extrapolating sieving parameters to the 1024-bit case is difficult due to the trade-offs between the steps of the algorithm and their relative parallelism. The prior work proposing parameters for factoring a 1024-bit RSA key is thin, and we resort to extrapolating from asymptotic complexity. For the number field sieve, the complexity is exp ((k + o( 1) )(log N) 1/3 (log log N) 2/3 ), where N is the integer to factor or the prime modulus for discrete logarithm and k is an algorithm-specific constant. This formula is inherently imprecise, since the o(1) in the exponent can hide polynomial factors. This complexity formula, with k = 1.923, describes the overall time for both discrete logarithm and factorization, which are both dominated by sieving and linear algebra in the precomputation. Evaluating the formula for 768-and 1024-bit N gives us estimated multiplicative factors by which time and space will increase from the 768-to the 1024-bit case. of 80. [START_REF] Geiselmann | Improved routing-based linear algebra for the number field sieve[END_REF] If we optimistically assume that a similar reduction can be achieved for discrete logarithm, the hardware cost to perform the linear algebra for DH-1024 in one year is plausibly on the order of $5mn. Combining these estimates, special-purpose hardware that can perform the precomputation for one 1024-bit group per year would cost roughly $13mn. This is much less than the "hundreds of millions of dollars" that we conservatively estimated in 2015, making it even more likely that nationstate adversaries have implemented the attack.

To put this dollar figure in context, the FY 2012 budget for the U.S. Consolidated Cryptologic Program (which includes NSA) was $10.5bn. [START_REF]FY 2013[END_REF] The 2013 budget request, which prioritized investment in "groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic" included notable $100mn+ increases in two programs under Cryptanalysis & Exploitation Services: "Cryptanalytic IT Systems" (to $247mn), and the cryptically named "PEO Program C" (to $360mn). [START_REF]FY 2013[END_REF]

Is NSA breaking 1024-bit Diffie-Hellman?

Our calculations suggest that it is plausibly within NSA's resources to have performed number field sieve precomputations for a small number of 1024-bit Diffie-Hellman groups. This would allow them to break any key exchanges made with those groups in close to real time. If true, this would answer one of the major cryptographic questions raised by the Edward Snowden leaks: How is NSA defeating the encryption for widely used VPN protocols?

Virtual private networks are widely used for tunneling business or personal traffic across potentially hostile networks. We focus on the IPsec VPN protocol using the IKE protocol for key establishment and parameter negotiation and the Encapsulating Security Payload (ESP) protocol for protecting packet contents.

IKE. There are two versions, IKEv1 and IKEv2, which differ in message structure but are conceptually similar. For the sake of brevity, we will use IKEv1 terminology. [START_REF] Harkins | The Internet key exchange (IKE)[END_REF] Each IKE session begins with a Phase 1 handshake in which the client and server select a Diffie-Hellman group from a small set of standardized parameters and perform a key exchange to establish a shared secret. The shared secret is combined with other cleartext values transmitted by each side, such as nonces and cookies, to derive a value called SKEYID. In IKEv1, SKEYID also incorporates a Pre-Shared Key (PSK) used for authentication.

The resulting SKEYID is used to encrypt and authenticate a Phase 2 handshake. Phase 2 establishes the parameters and key material, KEYMAT, for protecting the subsequently tunneled traffic. Ultimately, KEYMAT is derived from SKEYID, additional nonces, and the result of an optional Phase 2 Diffie-Hellman exchange.

NSA's VPN exploitation process. Documents published by Der Spiegel describe NSA's ability to decrypt VPN traffic using passive eavesdropping and without message injection or man-in-the-middle attacks on IPsec or IKE. Figure 3 illustrates the flow of information required to decrypt the tunneled traffic.

When the IKE/ESP messages of a VPN of interest are collected, the IKE messages and a small amount of ESP For 1024-bit precomputation, the total time complexity can be expected to increase by a factor of 1220 using the complexity formula, while space complexity increases by its square root, approximately 35. These ratios are relevant for both factorization and discrete logarithm since they have the same asymptotic behavior. For DH-1024, we get a total cost estimate for the precomputation of about 6mn core-years. In practice, it is not uncommon for estimates based merely on the complexity formula to be off by a factor of 10. Estimates of Table 2 must therefore be considered with due caution.

For 1024-bit descent, we experimented with our earlyabort implementation to inform our estimates for descent initialization, which should dominate the individual discrete logarithm computation. For a random target in Oakley Group 2, initialization took 22 core-days, and yielded a few primes of at most 130 bits to be descended further. In twice this time, we reached primes of about 110 bits. At this point, we were certain to have bootstrapped the descent and could continue down to the smoothness bound in a few more coredays if proper sieving software were available. Thus we estimate that a 1024-bit descent would take about 30 core-days, once again easily parallelizable.

Costs in hardware. Although several million core-years is a massive computational effort, it is not necessarily out of reach for a nation-state. At this scale, significant cost savings could be realized by developing application-specific hardware given that sieving is a natural target for hardware implementation. To our knowledge, the best prior description of an Application-Specific Integrated Circuit (ASIC) implementation of 1024-bit sieving is the 2007 work of Geiselmann and Steinwandt. [START_REF] Geiselmann | Non-wafer-scale sieving hardware for the NFS: Another attempt to cope with 1024-bit[END_REF] Updating their estimates for modern techniques and adjusting parameters for discrete logarithm allows us to extrapolate the financial and time costs.

We increase their chip count by a factor of ten to sieve more and save on linear algebra as above, giving an estimate of 3mn chips to complete sieving in one year. Shrinking the dies from the 130 nanometer technology node used in the paper to a more modern size reduces costs as transistors are cheaper at newer technologies. With standard transistor costs and utilization, it would cost about $2 per chip to manufacture after fixed design and tape-out costs of roughly $2mn. [START_REF] Lipacis | Semiconductors: Moore stress = structural industry shift[END_REF] This suggests that an $8mn investment would buy enough ASICs to complete the DH-1024 sieving precomputation in one year. Since a step of descent uses sieving, the same hardware could likely be reused to speed calculations of individual logarithms.

Estimating the financial cost for the linear algebra is more difficult since there has been little work on designing chips that are suitable for the larger fields involved in discrete logarithm. To derive a rough estimate, we can begin with general purpose hardware and the core-year estimate from Table 2. Using the 300,000 CPU core Titan supercomputer it would take four years to complete the 1024-bit linear algebra stage (notwithstanding the fact that estimates from Table 2 are known to be extremely coarse, and could be optimistic by a factor of maybe 10). Titan was constructed in 2012 for $94mn, suggesting a cost of under $400mn in supercomputers to finish this step in a year. In the context of factorization, moving linear algebra from general purpose CPUs to ASICs has been estimated to reduce costs by a factor traffic are sent to the Cryptanalysis and Exploitation Services (CES). [START_REF]Fielded capability: End-to-end VPN SPIN 9 design review. Media leak[END_REF]23,[START_REF]TURMOIL VPN processing[END_REF] Within the CES enclave, a specialized "attack orchestrator" attempts to recover the ESP decryption key with assistance from high-performance computing resources as well as a database of known PSKs ("CORALREEF"). [START_REF]Fielded capability: End-to-end VPN SPIN 9 design review. Media leak[END_REF]23,[START_REF]TURMOIL VPN processing[END_REF] If the recovery was successful, the decryption key is returned from CES and used to decrypt the buffered ESP traffic such that the encapsulated content can be processed. [START_REF]Fielded capability: End-to-end VPN SPIN 9 design review. Media leak[END_REF][START_REF]SPIN 15 VPN story[END_REF] Evidence for a discrete logarithm attack. The ability to decrypt VPN traffic does not necessarily indicate a defeat of Diffie-Hellman. There are, however, several features of the described exploitation process that support this hypothesis.

The IKE protocol has been extensively analyzed 3,[START_REF] Meadows | Analysis of the Internet key exchange protocol using the NRL protocol analyzer[END_REF] and is not believed to be exploitable in standard configurations under passive eavesdropping attacks. Absent a vulnerability in the key derivation function or transport encryption, the attacker must recover the decryption keys. This requires the attacker to calculate SKEYID generated from the Phase 1 Diffie-Hellman shared secret after passively observing an IKE handshake.

While IKE is designed to support a range of Diffie-Hellman groups, our Internet-wide scans (Section 4.3) show that the vast majority of IKE endpoints select one particular 1024-bit Diffie-Hellman group even when offered stronger groups. Conducting an expensive, but feasible, precomputation for this single 1024-bit group (Oakley Group 2) would allow the efficient recovery of a large number of Diffie-Hellman shared secrets used to derive SKEYID and the subsequent KEYMAT.

Given an efficient oracle for solving the discrete logarithm problem, attacks on IKE are possible provided that the attacker can obtain the following: (1) a complete two-sided IKE transcript, and (2) any PSK used for deriving SKEYID in IKEv1. The available documents describe both of these as explicit prerequisites for the VPN exploitation process outlined above and provide the reader with internal resources available to meet these prerequisites. 23 Of course, this explanation is not dispositive and the possibility remains that NSA could defeat VPN encryption using alternative means. A published NSA document refers to the use of a router "implant" to allow decryption of IPsec traffic, indicating the use of targeted malware is possible. However, this implant "allows passive exploitation with just ESP" 23 without the prerequisite of collecting the IKE handshake messages. This indicates it is an alternative mechanism to the attack described above.

The most compelling argument for a pure cryptographic attack is the generality of NSA's VPN exploitation process. This process appears to be applicable across a broad swath of VPNs without regard to endpoint's identity or the ability to compromise individual endpoints.

Effects of a 1024-bit break

In this section, we use Internet-wide scanning to assess the impact of a hypothetical DH-1024 break on IKE, SSH, and HTTPS. Our measurements, performed in early 2015, indicate that these protocols would be subject to widespread compromise by a nation-state attacker who had the resources to invest in precomputation for a small number of 1024-bit groups.

IKE. We measured how IPsec VPNs use Diffie-Hellman in practice by scanning a 1% random sample of the public IPv4 address space for IKEv1 and IKEv2 (the protocols used to initiate an IPsec VPN connection) in May 2015. We used the ZMap UDP probe module to measure support for Oakley Groups 1 and 2 (two popular 768-and 1024-bit, builtin groups) and which group servers prefer. Of the 80K hosts that responded with a valid IKE packet, 44.2% were willing to negotiate a connection using one of the two groups. We found that 31.8% of IKEv1 and 19.7% of IKEv2 servers supported Oakley Group 1 (768-bit) while 86.1% and 91.0% respectively supported Oakley Group 2 (1024-bit). In our sample of IKEv1 servers, 2.6% of profiled servers preferred

Vulnerable servers, if the attacker can precompute for…

All 512-bit groups All 768-bit groups One 1024-bit group Ten 1024-bit groups for its Suite B cryptographic algorithms and would replace them with algorithms resistant to quantum computers. [START_REF]Cryptography today[END_REF] However, since no fully vetted and standardized quantumresistant algorithms exist currently, elliptic curves remain the most secure choice for public key operations.

Increase minimum key strengths

To protect against the Logjam attack, server operators should disable DHE_EXPORT and configure DHE ciphersuites to use primes of 2048 bits or larger. Browsers and clients should raise the minimum accepted size for Diffie-Hellman groups to at least 1024 bits in order to avoid downgrade attacks.

Don't deliberately weaken cryptography

The Logjam attack illustrates the fragility of cryptographic "front doors." Although the key sizes originally used in DHE_EXPORT were intended to be tractable only to NSA, two decades of algorithmic and computational improvements have significantly lowered the bar to attacks on such key sizes. Despite the eventual relaxation of cryptography export restrictions and subsequent attempts to remove support for DHE_EXPORT, the technical debt induced by the additional complexity has left implementations vulnerable for decades. Like FREAK, 1 our results warn of the long-term debilitating effects of deliberately weakening cryptography.

CONCLUSION

We find that Diffie-Hellman key exchange, as used in practice, is often less secure than widely believed. The problems stem from the fact that the number field sieve for discrete logarithms allows an attacker to perform a single precomputation that depends only on the group, after which computing individual logarithms in that group has a far lower cost.

Although this is well known to cryptographers, it apparently has not been widely understood by system builders. Likewise, many cryptographers did not appreciate that a large fraction of Internet communication depends on a few small, widely shared groups.

A key lesson is that cryptographers and creators of practical systems need to work together more effectively. System builders should take responsibility for being aware of applicable cryptanalytic attacks. Cryptographers should involve themselves in how cryptography is actually being applied, such as through engagement with standards efforts and software review. Bridging the perilous gap that separates these communities will be essential for keeping future systems secure.

Figure 1 .

 1 Figure 1. Number field sieve for discrete logarithms. This algorithm consists of a precomputation stage that depends only on the prime p and a descent stage that computes individual logarithms. With sufficient precomputation, an attacker can quickly break any Diffie-Hellman instances that use a particular p.

Figure 2 .

 2 Figure 2. The Logjam attack. A man-in-the-middle can force TLS clients to use export-strength Diffie-Hellman with any server that allows DHE_EXPORT. Then, by finding the 512-bit discrete log, the attacker can learn the session key and arbitrarily read or modify the contents. Data fs refers to False Start application data that some TLS clients send before receiving the server's Finished message. Client C

InternetFigure 3 .

 3 Figure 3. NSA's VPN decryption infrastructure. This classified illustration published by Der Spiegel 25 shows captured IKE handshake messages being passed to a high-performance computing system, which returns the symmetric keys for ESP session traffic. The details of this attack are consistent with an efficient break for 1024-bit Diffie-Hellman.

  toolchain to offer DHE and DHE_EXPORT ciphersuites and scanned TCP/443 on both the full public IPv4 address space and the Alexa Top Million domains. The scans took place in March 2015. Of 539,000 HTTPS sites among Top Million domains, we found that 68.3% supported DHE and 8.4% supported DHE_EXPORT. Of 14.3mn IPv4 HTTPS servers with browser-trusted certificates, 23.9% supported DHE and 4.9% DHE_EXPORT.

Table 1 . Top 512-bit Diffie-Hellman primes for TLS d .

 1

	Source	Popularity Prime
	Apache	82%	9fdb8b8a004544f0045f1737d0ba2e0b
			274cdf1a9f588218fb435316a16e3741
			71fd19d8d8f37c39bf863fd60e3e3006
			80a3030c6e4c3757d08f70e6aa871033
	mod_ssl	10%	d4bcd52406f69b35994b88de5db89682
			c8157f62d8f33633ee5772f11f05ab22
			d6b5145b9f241e5acc31ff090a4bc711
			48976f76795094e71e7903529f5a824b
	(others)	8%	(463 distinct primes)

Table 2 . Estimating costs for factoring and discrete log e .

 2

			Sieving	Linear Algebra	Descent
		Log 2 B	Core-years	Rows	Core-years	Core-time
	RSA-512	29	0.3	4.2mn	0.03		Timings with default CADO-NFS parameters.
	DH-512	27	2.5	2.2mn	1.1	10min	For the computations in this paper; may be suboptimal.
	RSA-768	37	800	250mn	100		Est. based on Kleinjung and Aoki et al. 12 with less sieving.
	DH-768	36	4,000	24mn	920	43hrs	Data from, Kleinjung and Diem et al. 13 , Table 1.
	RSA-1024	42	≈1,000,000	≈8.7bn	≈120,000		Crude estimate based on complexity formula.
	DH-1024	40	≈5,000,000	≈0.8bn	≈1,100,000	30 days	Crude estimate based on formula and our experiments.

e For sieving, we give one important parameter, which is the number of bits of the smoothness bound B. For linear algebra, all costs for DH are for safe primes; for Digital Signature Algorithm (DSA) primes with group order of 160 bits, this should be divided by 6.4 for 1024 bits, 4.8 for 768 bits, and 3.2 for 512 bits.

b An odd prime p is safe when (p -1)/2 is prime.

d 8.4% of Alexa Top Million HTTPS domains allow DHE_EXPORT, of which 92.3% use one of the two most popular primes, shown here.

Acknowledgments

The authors thank Michael Bailey, Daniel Bernstein, Ron Dreslinski, Tanja Lange, Adam Langley, Kenny Paterson, Andrei Popov, Ivan Ristic, Edward Snowden, Brian Smith, Martin Thomson, and Eric Rescorla. This work was supported by the U.S. National Science Foundation, the Office University, Baltimore, MD, USA.

Nadia Heninger and Luke Valenta, University of Pennsylvania, Philadelphia, PA, USA.

Santiago Zanella-Béguelin, Microsoft Research, Cambridge, England, UK.

of Naval Research, the European Research Council, and the French National Research Agency, with additional support from the Mozilla Foundation, Supermicro, Google, Cisco, the Morris Wellman Professorship, and the Alfred P. Sloan Foundation. Some experiments used the Grid'5000 testbed, supported by INRIA, CNRS, RENATER, and others. the 768-bit Oakley Group 1 and 66.1% preferred the 1024-bit Oakley Group 2. For IKEv2, 5.8% of profiled servers chose Oakley Group 1, and 63.9% chose Oakley Group 2.

SSH. All SSH handshakes complete either a finite field or elliptic curve Diffie-Hellman exchange. The protocol explicitly defines support for Oakley Group 2 (1024-bit) and Oakley Group 14 (2048-bit) but also allows a server-defined group to be negotiated. We scanned 1% random samples of the public IPv4 address space in April 2015. We found that 98.9% of SSH servers supported the 1024-bit Oakley Group 2, 77.6% supported the 2048-bit Oakley Group 14, and 68.7% supported a server-defined group.

During the SSH handshake, the server selects the client's highest priority mutually supported key exchange algorithm. To estimate what servers will prefer in practice, we performed a scan in which we mimicked the algorithms offered by OpenSSH 6.6.1p1, the latest version of OpenSSH. In this scan, 21.8% of servers preferred the 1024-bit Oakley Group 2, and 37.4% preferred a server-defined group. 10% of the server-defined groups were 1024-bit, but, of those, nearly all provided Oakley Group 2 rather than a custom group.

Combining these equivalent choices, we find that a nation-state adversary who performed NFS precomputations for the 1024-bit Oakley Group 2 could passively eavesdrop on connections to 3.6mn (25.7%) publicly accessible SSH servers.

HTTPS. Our 2015 scans found that DHE was commonly deployed on web servers. 68.3% of Alexa Top Million sites supported DHE, as did 23.9% of sites with browser-trusted certificates. Of the Top Million sites that supported DHE, 84% used a 1024-bit or smaller group, with 94% of these using one of five groups.

Despite widespread support for DHE, a passive eavesdropper can only decrypt connections that organically agree to use Diffie-Hellman. We estimated the number of sites for which this would occur by offering the same sets of ciphersuites as Chrome, Firefox, and Safari. We found that browser connections to approximately 24% of browser connections with HTTPS-enabled Top Million sites (and 10% of all sites with browser-trusted sites certificates) would negotiate DHE using one of the ten most popular 1024-bit primes. After completing the NFS precomputation for only the most popular 1024-bit prime, an adversary could passive eavesdrop on browser connections to 17.9% of Top Million sites.

RECOMMENDATIONS

In this section, we present concrete recommendations to recover the expected security of Diffie-Hellman.

Transition to elliptic curves

Transitioning to Elliptic Curve Diffie-Hellman (ECDH) key exchange avoids all known feasible cryptanalytic attacks. Current elliptic curve discrete logarithm algorithms do not gain as much of an advantage from precomputation. In addition, ECDH keys are shorter and computations are faster. We recommend transitioning to elliptic curves; this is the most effective solution to the vulnerabilities in this paper. We note that in August 2015, NSA announced that it was planning to transition away from elliptic curve cryptography