On the fog of RSA key lengths: Verifying public key cryptography strength recommendations

On the Fog of RSA Key Lengths Verifying Public Key Cryptography Strength Recommendations

Mikko Kiviharju Information Technology Division Finnish Defence Research Agency

Riihimaki, Finland [email protected]

Abstract—Finite-field cryptography plays a major role in

current cyberspace infrastructure. Most notable examples include the RSA public key cryptosystem based on the assumed difficulty of finding factorization of large integers in general; and Diffie-Hellman (DH) key exchange, based on the hardness of finding discrete logarithms in finite fields. In order to use strong enough parameters for cryptography intended to protect classified information, the hardness of these problems needs to be measured and associated with a security level (e.g. RESTRICTED and SECRET). This is, however, a multi-step, nation-dependent and usually classified process, with no unified understanding on how certain parameters should be measured. In this paper we investigate the public key length recommendations for RSA and DH, their background and reasoning. Based on this research, we suggest an updated method for the measurement of sufficient RSA and DH key sizes, and benchmark it against the public Finnish security level recommendation.

Keywords— RSA, Diffie-Hellman, Security levels

I. INTRODUCTION Finite-field cryptography plays a major role in current

cyberspace infrastructure. Most notable examples include the RSA public key cryptosystem based on the assumed difficulty of finding factorization of large integers in general, and Diffie- Hellman (DH) key exchange, based on the hardness of finding discrete logarithms in finite fields.

RSA and DH are both considered to be vulnerable against computational power of possible hypothetical quantum computers. Research for quantum-resistant (classical) cryptographic schemes, so-called post-quantum cryptography (PQC), gained momentum in 2016, after US NSA had announced basically a new Suite B due to the “quantum threat” (CNSS Memorandum 2-15 [12]). NIST quickly announced a competition for a new PQC standard [30], and many governmental organizations started to follow suite and update their key management guidelines (e.g. BSI and ECRYPT, [8], [18]). It then appears to be the time to review the (classical and quantum) strength of RSA and DH for governmental use in general as well.

Estimating the (classical) security of these schemes is equivalent to analyzing the complexity of solving the underlying mathematical problem, which is not always a straightforward task. In addition, these estimations need often

to be commensurate with other cryptographic primitives to form sets of recommendations to be used when handling classified documents. Each official security level (e.g. RESTRICTED, SECRET) is usually appointed a set of approved algorithms with approved key-lengths.

The approved key-lengths are, in turn, derived from public recommendations and other considerations via a multi-step process. In the case of RSA and DH, this process is not very well documented and seldom updated. Furthermore, the estimations are based on heuristic, asymptotic complexity estimates, for which there are only few data points with varying levels of documentation. In the wake of a larger recommendations-update research, we set out to verify the existing RSA/DH-key length recommendations more carefully, based on available data from existing factorization challenges.

Our contributions include: a comprehensive survey of existing RSA key length recommendations and the reasoning behind their conclusions; a normalization and verification of reported semi-prime factoring challenge work factors; and finally experimenting with different curve-fitting approaches to extrapolate more realistic key length recommendations based on the normalized data points and benchmarking this against the Finnish security-level recommendation by NCSA-FI [21].

II. PRELIMINARIES AND RELATED WORK

A. RSA and Diffie-Hellman RSA (from Rivest-Shamir-Adleman [36]) is a public-key

cryptosystem based on exponentiation in finite fields over integers modulo N (ℤ ) where N is a composite integer of two large factors (i.e. a semi-prime). For brevity, we give only a brief reminder of the (textbook) RSA-scheme encryption Encrypt: Given a message ∈ ℤ , encrypt it as =mod

Decryption in RSA is based on the property of ℤ , where it is feasible to find two exponents (e for encryption and d for decryption) cancelling each other out if the factorization of N is known1.

The application-level security (when RSA is used in actual systems) is very much dependent on the additional techniques used in conjunction with RSA, usually embedded, for

1 The corresponding mathematical problem is called IF, Integer Factorization

978-1-5386-3858-3/17/$31.00 ©2017 IEEE

example, in a digital certificate structure and parameters. We stress that, system-wise, there are other far simpler attacks against RSA than solving IF2. However, the complexity of IF works as the worst-case-measure for multiple schemes using RSA.

Diffie-Hellman (DH [16]) is a public-key key-agreement system based on exponentiation in finite fields. A large class of Diffie-Hellman instantiations are performed over integers modulo p (ℤ ) where p is a prime. Another important class of instantiations is built on elliptic curve groups (ECG), called elliptic-curve Diffie-Hellman (ECDH).

The security of DH is dependent on the fact that solving the discrete logarithm problem (DLP) in abstract finite fields in general is proven to be hard and that DLP in ℤ and in ECGs is believed to be hard. However, the research progress for DLP, in ℤ is significantly more advanced than for DLP in ECGs, and ECDH in general forms an entirely different class of schemes. We thus do not consider ECDH further.

Both RSA and DH are mainly used in hybrid encryption, i.e. for encrypting or agreeing upon a symmetric key. Thus it is important that their security parameter is on a par with the length of the key they are supposed to protect.

IF and DLP are different problems, but not completely independent: surprisingly the same algorithm can be applied to both of them, namely the various sieving methods. For reasons of brevity, we do not then elaborate more on the actual DH algorithm.

B. Factorization with Sieves The modern sieves for factorization all aim to find

congruent squares (leading to factorization via the Fermat factorization method) modulo the number to be factored. The first modern sieve is the Quadratic Sieve (QS [33]), which tries to find suitable congruent square candidates via a factor base. The method uses multiple primes to block intermediate-level candidates from the final set of candidates, thus „sieving“ them.

The subsequent sieves to QS (such as specialized and generalized number field sieves) all have the same aim: to find congruent squares to perform factoring.

Number Field Sieves (NFS) generalize QS such that the search for smooth integers is lifted to a more general algebraic structure (called a number field, an extension field of ℚ), giving birth to a larger „factor“ base and thus also a larger set of candidate numbers to choose from. This extension field is characterized by two polynomials, whose selection is an important part of NFS.

NFS can be optimized to be efficient with certain types of composite integers only. These are called Special NFS, or SNFS. If the distinction needs to be made, the NFS able to factor arbitrary types of integers is called the Generalized NFS (GNFS [27]). For the RSA system semi-primes, GNFS is required.

GNFS can be divided into the following steps:

2 Such as padding-oracle attacks, downgrading attacks and hash collisions attacks

• Polynomial selection • Sieving (or relation finding). Of the sieving algorithms, lattice sieving

is asymptotically the most efficient. Sometimes another technique called line sieving is also used (see [40] p.864).

• Filtering (not all sources consider this an independent step). • Linear algebra, with algorithm choices such as Block Lanczos and

Block Wiedemann ([40], p.865).

• Square root, with algorithm choices such as the Montgomery algorithm, and Chinese Remainder Theorem (CRT)-based algorithm

The currently most efficient NFS is called the General Number Field Sieve (GNFS, [27])

Various NFS perform usually according to the so-called L- notation ([33], [28]). L-notation, is formally defined as , = o Here , ∈ ℝ, 0 ≤ ≤ 1 and o(1) is defined as in the „little- Oh“-notation: = o , if ∀ > 0 : ∃ > 0 , such that when > , | | ≤ | |. The L-notation is asymptotic, and is assumed to be valid only for the limiting case lim → ∞. Notation conventions are taken from [40] (p.709).

The GNFS worst-case performance is 1 3 , 8 3 , a result due to Lenstra, Pomerance and Buhler [9], and we refer to it henceforth as the Buhler’s formula. The GNFS performance is better than earlier sieves‘ (QS performs as 1 2 , 1 ), but yet worse than some special-case discrete logarithm functions for elliptic-curve cryptography. The Buhler’s formula is mostly based on heuristics and not rigorous analysis. A recent claim by Microsoft research from 6/2016 [41] seems to imply that this heuristics is indeed also a rigorous worst case running time of GNFS.

The GNFS complexity result follows standard complexity analysis conventions of operations, i.e. assuming that one „step“ is a single line of pseudocode, consisting of a set of simple primitives, such as addition or fixed-length comparison, implementable with a single assembly instruction. Thus the output of applying the GNFS complexity estimate formula is directly the number of (assembly language, low-level) instructions used.

According to RFC 3766, ch.2 [32], solving DL is about 21,5... 26 times more difficult problem than RSA. The ANSSI key length recommendations [1] express a difference measure of 100-200 bits, but this is in terms of actual key lengths, not security parameter, and is calculated based on the achievement date rather than measured work load. Based on the work factors reported for the 596-bit RSA-180 factorization [15] and the DLP record for same size GF(p) [23], DLP is about 6,5 times or 2,7 bits harder than factoring, supporting more the RFC 3766 estimates. With this small bit-length differences, the identical recommendations for DH and RSA seem to be well founded, and thus we do not consider DH separately in this paper further.

C. Related Work Lenstra was the first to try to match the recently invented

NFS to actual factoring and to estimate future trends

([25],[26]). During the time, however, Lenstra did not have many GNFS-data points available, and used instead general algebraic advancement hypotheses, which tended to be too pessimistic.

After Lenstra, Various standardization organizations (such as NIST and IETF), governmental INFOSEC bodies (ANSSI, BSI) and international joint cryptologic efforts (ECRYPT) that produce key length recommendations have become the main sources for trying to inter- or extrapolate existing factorization records for the purpose of attaching a suitable security parameter to them ([6],[5],[19],[18],[20],[32],[35],[1],[8]). However, to the best of our knowledge, their extrapolation methods are rather trivial (adding a constant in or out of the exponent).

Most extrapolations of factoring difficulty aim to predict the date and/or cost of factoring a 1024 modulus. One of the most cited paper in this vein is by Shamir and Tromer [37], but like the others, it is difficult to translate to a formula including a security parameter. R. D. Silverman predicted in 2000 [38] that 1024 RSA modulus would not be factored until 2037, which is a cost-based estimate. Brent [7] gave in 2000 an accurate prediction on the year RSA-768 was factored.

III. KEY LENGTH RECOMMENDATIONS

A. General Official RSA key length recommendations in the western

world are not commonly highly advertised. We made use of a survey compiled by ENISA [22], and a keylength-comparison website (keylength.com).

We selected for comparison those recommendations, which actually presented equivalences between symmetric and asymmetric key lengths. Recommendations or directives, which were aimed more to define actual security levels, were handled separately. The recommendations in the next chapter are by no means binding, nor are all of them even officially endorsed.

The first RSA key strength estimates against GNFS were made by Lenstra. These are very rigorous, but they were, however, too optimistic when it comes to cryptanalytic prog- ress in factoring, resulting in more than three times the keylength compared to current recommendations. We note Lenstra’s work, but do not consider it further.

B. Recommendations for Key Length We will compare here different recommendations

according to both the actual RSA key length – security parameter posture and according to their reasoning. In particular, we will note:

• The work factor unit: 1 computer instruction or a symmetric encryption operation

• Estimation purpose: to find an equivalent security parameter or calendar year

• The reasoning behind the recommendation • The exact extrapolation formula, if any

The comparison between different recommendations is presented in Tables I and II.

Table I represents the recommended modulus size from different sources, and the year the recommendation was given. We considered different versions of some recommendations, since the reasoning between versions may change (e.g. in ECRYPT 2012 and 2016).

To be able to compare different recommendations, data points need to be comparable. This is somewhat challenging, as different recommendations use different sets of security parameters. We chose our parameters to represent typical security level minimum parameters and typical extrapolation base points (80, 100, 112, 128, 192 and 256 bits of security). If sufficient reasoning information was available, we also interpolated the desired data points ourselves (the ANSSI estimates) or by using keylength.com-website3 as a tool.

TABLE I. RECOMMENDED RSA MODULUS LENGTHS

Recom. Year 80 100 112 128 192 256 Lenstra 2001 1464 3137 4509 6790 22089 49979 Lenstra 2004 1300 2300 3154 4440 12548 26268 NIST 2007 1024 - 2048 3072 7680 15360 NIST 2016 1024 - 2048 3072 7680 15360 NESSIE 2003 1536 - 4096 6000 - - ECRYPT 2012 1248 - 2432 3248 7936 15424 ENISA 2013 1024 - - 3072 - 15360 ECRYPT 2016 1024 - - 3072 - 15360 RFC 3766 2004 1228 1926 2448 3253 7976 15489 ANSSI 2014 1004 1702 2179 2930 7406 14614 BSI 2016 - 1900 - 3200 7900 15500 Legend Italics Interpolated values

Bold Italics Extrapolated values

It can be observed from Table I, that the older the recommendations are, the more likely they are to use customized reasoning. In the latest recommendations, there are mainly two lines: NIST and ECRYPT (although ECRYPT has adopted the NIST guidelines since 2013).

Compared to the Lenstra’s recommendations, nearly all the others are practically the same. Even with the Lenstra’s sources removed, the figures are very close to each other (see Fig. 1). The NFS theoretical estimate is, however, always the most optimistic, and all of the recommendations are conservative compared to the bare Buhler’s formula.

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

70 120 170 220 270

NIST

NESSIE

ECRYPT1

NFS

ANSSI

Fig. 1. RSA modulus length, Lenstra’s recommendations removed

3 Keylength.com is a promotional website administered by a Belgian security

consulting company Bluekrypt.

The first Lenstra’s keylength recommendation [25] uses only one data point for RSA (RSA-512) and assumes „standard cryptological progress“ (equivalently measured for all types of ciphers). Lenstra‘s second recommendation [26] adds a more refined estimate of breaking RSA-1024, and the extrapolation parameters become more modest. However, using calendar year together with Moore’s law and a similar speed for the algorithmic evolution paint an unnecessarily gloomy picture

ECRYPT produced yearly reports on algorithms and key sizes, which were influential inside EU [39] up to 2012, after which producing the report was taken up by ENISA. Recently, ECRYPT has again returned to this task.

The ECRYPT‘s most recent paper (2016) is following NIST’s guidelines for the security levels. The older paper from 2012 uses the Buhler’s formula [9] to interpolate the complexity of factoring. However, they subtract an additional constant C=14 (according to our curve-fitting to ECRYPT data C=13,8) from the exponent to match with their data point of RSA-512 and its assumed complexity of 250.

NESSIE was an EU FP5 funded cryptographic primitive meta-level research program. It arrived into its own conclusions of suitable key lengths for RSA ([35]). NESSIE does not explain its extrapolation methods from the RSA-512 factorization data point, but ECRYPT-2012 states that NESSIE was using inaccurate extrapolation formulae.

The NIST‘s (USA‘s National Institute of Standards and Technology) recommended RSA modulus information ([6],[5]) is probably the most cited and used throughout western governments. NIST modulus sizes date back to the ANSI X9.30 standard about DSA in 1993 , but the current document does not explain the reasoning behind the actual values. In the current NIST specification the overarching principle is to define X bits of security in terms of units of time T, where T is said to be „...the amount of time that is required to perform one encryption...“ ([5], p.51). The NIST recommendations are close to the values generated by the Buhler’s formula, but offer 6-12 bits more security. This extra security is not constant, so it would not be explained by ECRYPT-like additive constant nor that the data unit used would actually be encryption. Tweaking either t or γ in the L-notation can come reasonably closer to the actual values, though.

ANSSI (Agence nationale de la sécurité de systèmes d‘information) is the French INFOSEC-regulatory body. The ANSSI recommendation [1] is year-based, so it is more difficult to interpret into computational units. However, based on the rule RegleFact-1 and Table 7, the binding version of the recommendations follows Buhler’s formula, padded with some 5 years or so (equivalent of padding the Buhler’s formula with 8 bits of security parameter). However, in the discussion part, the French standard recognizes unforeseen factorization developments either in the γ- or t-parameter of the L-notation of factoring algorithms, but does not attempt to fit these curves to the existing data points. The existing (factorization) data points are fitted to the Buhler’s formula curve by a constant shift by 12,5 years of modulus length validity time (less than the binding parts‘ 5 years padding). This translates into subtracting a constant of about 300 bits from the Buhler’s formula.

BSI (Bundesamt für Sicherheit in der Informationstechnik) is the German INFOSEC regulatory body. BSI’s recommendation ([8], Table 3.1.1.2) claims to account for the block cipher encryption operation (evidently requiring also the key schedule). The BSI’s view follows the ECRYPT II recommendation from 2011.

RFC 3766 [32] states that the unit of time is one instruction in a computer. The RFC tries to extrapolate the work-factor of the existing RSA-challenges by placing a factor k in front of the Buhler’s formula, and the best fit for this is k=0,02.

The reasoning and parameters of the different recommendations are summarized in Table II. Some of the information in Table II is not explicitly stated by respective documents, but rather inferred from the text and data within there (e.g. by curve-fitting).

TABLE II. KEY LENGTH RECOMMENDATION REASONING AND PARAMETERS

Recom. Fact. recs.

Data points

Data Unit

Est. unit

Estimation method

Lenstra2001 Emp. 1 I Y,S Buhler’s + general progr. Lenstra2004 Emp. 1 I Y,S As v.2001 + RSA-1024 est. NIST2007 - - I Y,S Not explained NIST2016 - - I Y,S Not explained NESSIE Emp. 6(1) E S Not explained ECRYPT2012 Note 1 I Y,S Buhler’s – constant C=13,8 ENISA - - I (Y) S Copies NIST ECRYPT2016 - - I (Y) S Copies NIST RFC 3766 Emp. 4 I S Buhler’s * constant k=0,02 ANSSI Note 10 I Y (S) Buhler’s advanced by 5 yrs BSI - - E Y (S) Copies ECRYPT2012

The information in Table II is as follows:

• Column 2 states, whether the recommendation has noted or even employed existing factoring records

• Column 3 gives the used data points (factoring records). Data points in parenthesis are the number of points used for extrapolation.

• Column 4 expresses the data unit used in giving key size equivalences between asymmetric and symmetric systems. I means that the output of the RSA extrapolation is effectively expressed in number of single computer instructions; E means that the extrapolation is expressed in number of symmetric cipher encryptions.

• Column 5 states, whether the recommendation uses calendar year (Y) or security parameter (S) as the basis of extrapolation. If the estimation unit is in parenthesis, it is used only in a cursory way.

• In column 6 the main extrapolation method (if given) is clarified.

From our perspective, the ideal extrapolation in recommendations would employ as many factoring record data points as possible, remain on the security parameter level, equate the security parameter to a known block cipher key schedule, and try to fit an L-notation-type formula to the data points as best as possible, ignoring any „general cryptanalytic progress“.

From Table II we can see that those recommendations that do not copy others and shed even some light to their reasoning, use two types of extrapolation:

• Buhler’s formula factored by a constant (NESSIEs additive constant is in the exponent)

• Buhler’s formula appended with general cryptanalytic progress.

Only one of the cases uses more than one data point for the extrapolation.

We can also see that in key-equivalence tables (contrary to our expectations) the symmetric block key-schedule is equated to one computer instruction. Thus it seems questionable, whether they are actually key-equivalences.

C. Recommendations for Security Levels Security levels refer here to official security classification

levels used to group governmental or military information according to their sensitivity. The levels are traditionally marked with capital letters, and range from UNCLASSIFIED to TOP SECRET. Actual level names and their existence may differ, but most EU countries follow a simple chain of levels from TOP SECRET to unmarked (or public). To distinguish between different national and/or organizational classifications a qualifier may be prepended to the level name, e.g. US SECRET or EU-RESTRICTED. Levels are also sometimes given number, representing their position in the chain, number 1 usually being the highest level.

The detailed requirements for equipment approved to protect classified information are typically classified as well, even though not all of the requirements would actually mandate that. Typically, if the key length recommendations are separated to an independent document, they may be published.

Examples of official recommendations for security levels include:

• EU cryptographic recommendations for protecting EU-classified information are all classified up to EU-RESTRICTED (RESTREINT- UE)

• Norwegian recommendations are public concerning protection needs up to level NOR RESTRICTED (BEGRENSET), and classified for higher levels (NSM [29]).

• US recommendations for non-military governmental use are public up till US TOP SECRET (NSA [31],[13]).

• The Finnish recommendation (NCSA-FI [21]) is public up to FI SECRET.

There are also some security level recommendations that are on a more general level than merely governmental classified information, but they still include indication of cryptographic security parameters. These general level examples include, e.g. the Austrian (A-SIT [44]) and Spanish (CCN [11]) general government minimum safety recommen- dations. The available key lengths are summarized in Table III. Table III lists first some guidelines, where key lengths are explicitly bound to governmental security levels and in second part guidelines that make this binding in a more informal manner or on a more general level. From USA we list the non- military Suite B before and after the CNSS 2015 memorandum (USA-1, [13] and USA-2, [31]).

We list both the symmetric key length / security parameter (first row of table cell) and recommended RSA key length (second row), where available. The abbreviations of the column headers imply security levels as U=UNCLASSIFIED, R=RESTRICTED, C=CONFIDENTIAL, S=SECRET, TS= TOP SECRET. In countries that do not use UNCLASSIFIED,

a corresponding level is assumed (usually in terms of „basic“ level of protection). The number represents the minimum requirement for the level. The Spanish levels are safety levels, which are not the same as the above confidentiality levels.

From Table III it can be seen that most authorities abide to the NIST key-equivalences, but distribute them to different levels. USA is currently in a transition phase due to the quantum threat and has not published fine-grained level information. An interesting side note explained by E. Barker in 2006 is that neither NIST nor NSA ever intended the 256-bit AES to be at the topmost level (rather 192). However, the industry had already adopted it widely, rather than the 192-bit version, so the 256-bit version was used instead in the FIPS Suite B.

TABLE III. KEY LENGTHS IN NATIONAL SECURITY LEVEL GUIDELINES

Country (U) (R) (C) (S) (TS) Finland - 128

3072 192 7680

256 15360

Class- ified

Norway 112 1) 2048

112-128 2) 2048 Classified

USA-1 112 2048

128 - 3)

192 -

USA-2 256 / 3072 Austria 100

2048 -

Spain Basic 4) Medium High

- 112 2048

128 2048

1) Security strength for integrity, RSA for KE valid up till 2020 2) As 1). 128 bits for confidentiality. RSA validity up to 2018 3) Suite B used ECC instead of RSA before 2015 4) For safety levels only

IV. NORMALIZING FACTORIZATION RESULTS Our main goal was to verify RSA- and DH-key strength

recommendations based on actual factorization records and their trendline. However, to be able to plot a trendline, all the data points need to be commensurate. This implies a couple a simple requirements:

• The data points need to be using the same unit • The data points need to reflect the same factoring algorithm • Each data point needs to have exactly one measure reflecting

the total work.

Fortunately, the factoring records from about 130 digits onward are all performed using GNFS with the same algorithm choices (lattice sieving and block Lanczos). However, the measurement type has changed from MIPS years to CPU-years (with the CPU clock rate given in GHz) to core-years. We chose to remain on the MIPS years partly due to the unavailability of clock-rate information in the older records, and partly to its better correspondence to NFS theoretical bound (Buhler’s formula).

Many of the original record announcements are not very refined in the way they represent their work-factors. It is common to indicate the runtimes per GNFS step, but not necessarily as a complete effort. In a few cases the timing is very inaccurate or completely absent.

We chose the RSA-challenge numbers [42] for our data- points, since they are guaranteed to be of the same type of semi-primes that are used in actual cryptosystems. Additionally, they seem to be more popular targets for factoring than arbitrary composite numbers. We furthermore chose only those factorization records, which were performed with GNFS and for which there exists adequate run-time information. This includes RSA-numbers from RSA-130 to RSA-7684, except for RSA-170, RSA-576 and RSA-210, for which either there is not sufficient information of the run-time platform or the public original references are no longer available.

We selected two additional data points: c158 and c176, (numbers referring to their digit-size) which are both semi- prime factors of larger numbers (2953+1 and 11281+1, respectively). This gives us together a set of 14 data points, which is larger set for GNFS record data points than any that we are aware of.

In some factorization results, the total time is given ambiguously or implicitly (and various meta-level research papers use these ambiguous results differently, arriving at different extrapolation results):

• RSA-130 and RSA-140 factoring work estimates are given both in terms of measured results and “what- could’ve-been”, where the optimistic estimates were twice as fast as what was actually performed.

• Cofactor c176 factorization [14] uses two contradicting measures for the sieving phase, the latter being only 50% of the former

TABLE IV. NORMALIZED GNFS FACTORIZATION RECORDS

Year Digits Bits MIPS years 1996 [14] 130 430 1 000 1999 [14] 140 463 2 000 2004 [2] 150 496 6 700 1999 [10] 155 512 8 000 2002 [14] 158 527 15 500 2003 [14] 160 530 12 400 2005 [14] 176 588 174 800 2010 [15] 180 596 160 000 2010 [34] 190 629 400 000 2005 [14] 193 640 260 000 2005 [14] 200 663 660 000 2012 [4] 212 704 5 000 000 2016 [3] 220 729 3 000 000 2009 [24] 232 768 17 600 000 Legend Normal Verified from external sources

Italics Recomputed from original sources Bold It. Original source ambiguous

The normalized factoring records are depicted in Table IV. The change from MIPS-years to CPU-/core-years presents difficulties for the normalization of the records. According to [17] and [43] modern processors are able to execute 2-8 instructions per cycle (the more modern the processor, the more instructions). We thus used a factor f=4 between the

4 There are varying conventions, whether a particular number is expressed in terms of its digit- or bit-size. RSA-130 refers to digits and RSA-768 to bits.

clock-rate and the flops-count, translating e.g. 1 GHz-year to 4000 MIPS-years.

Meta-research in factorization often may interpret the distinction between 1000 MIPS-years and one GHz-year as nonexistent (such as RFC 3766 for RSA-160 factoring record). This is yet another reason to check our trend lines against the original factoring record announcements.

V. ESTIMATING FACTORIZATION RESULTS To arrive at a compatible extrapolation, we need to modify

some of the Buhler’s formula parameters.

Our default assumptions for the optimal curve include

• Curve needs to be expressed in L-notation, with modified constants (thus we are allowed to tweak t, γ and the o(1)-term) as well as add constants in the exponent (as in RFC 3766 or ECRYPT-2012)

• The result of the modified Buhler’s formula is measured in log2-scale. Thus a result of 80 means 280 computer instructions worth of effort.

• We do not consider „general cryptanalytic progress“ separetely.

We define „optimal“ curve-fit in terms of least squares: the expression resulting in smallest sum of squared differences between the data points and curve points is considered to be optimal.

For the extrapolation we desire a measure that is comparable to actual block-cipher encryption round rather than a single computer instruction. A common estimate for one AES key-schedule is about 1000 instructions, or 10 additional bits of security. This may not sound much, but the additional bits of security need to be added to the equivalent symmetric key length, which on the higher security parameter values may translate to thousands of bits of asymmetric key. We call this additional estimate the „AES-correction“.

Our first idea was to keep the Buhler’s formula intact, but tweak the o(1) expression to be non-zero. However, the o(1) expression is supposed to decrease in absolute value asymptotically, and those value-sets we tested needed all to be increasing in order to interpolate the data points optimally. Especially in extrapolation this seemed to imply e.g. that factoring difficulty would start to decrease at some point. We thus set o(1) identically to zero.

Fig. 2. Buhler’s formula and normalized factoring records on a log2-scale

54

56

58

60

62

64

66

68

70

72

400 500 600 700 800

MIPS-log

Buhler

We then experimented with the additive constant in the Buhler’s formula exponent. If we plot the data points and the Buhler’s formula curve in the same log-scale graph (Fig. 2), we notice that the plot by Buhler’s formula is too steep compared to the actual data points‘ apparent trendline. Thus a mere constant addition seems to be inadequate as well.

Next we note that Buhler’s formula is only a worst-case estimate. It could well be that the average case increases more slowly. We then plotted t and γ both as variables and measured the sum of squared data point differences. The resulting graph is depicted in Fig. 3.

Note that even though there is a diagonal „valley“, the optimum is, in fact, also a curve with a least value. The least value occurs with , = 0.283, 2,1542 .

Fig. 3. Squared difference of the best-fit curve and the data points, in terms of t (horizontal axis) and γ („depth“ axis) and the result of the fit (in log- scale).

Our extrapolated formula is then 2.1542,0.283 . This plot can also be seen in Fig.3.

Using the above expression as an extrapolation formula, we arrive at the following key-equivalence table between a security parameter and extrapolated RSA-key length (Table V):

TABLE V. EXTRAPOLATED RSA MODULUS LENGTHS FOR A GIVEN SECURITY PARAMETER

Sec.param Extrapolation (without AES correction)

Extrapolation (with AES correction)

80 1140 1544 100 2032 2610 112 2738 3435 128 3905 4779 196 11755 13525 256 26180 29157

Table V shows remarkably similar values to the Lenstra’s second keylength estimate, which uses general algorithmic process to arrive at its conclusions. It might well be, that this algorithmic process has appeared in the fine-tuning of GNFS implementations, instead of completely new factoring algorithms.

We also note that according to our extrapolation the RSA- 1024 offers only 76 bits of security, or equivalently DH-1024 would offer approximately 79 bits of security, well within reach of large intelligence organizations.

Comparing the results of Table V to the security levels in Table III, we see that in the Norwegian recommendation the RSA modulus length should not reflect RESTRICTED level data, rather UNCLASSIFIED, if at all. The Austria’s minimum

level security seems to in line, while the USA minimum requirement of a 3k RSA modulus for TOP SECRET would appear to be at least one class off.

In the Finnish requirement, steps between levels are so large that in RESTRICTED or CONFIDENTIAL no immediate changes are needed. However, the minimum level for SECRET is rather close to the actual border for CONFIDENTIAL, and should be rethought.

VI. CONCLUSIONS We surveyed the current status in different asymmetric key

strength and security level recommendations, and found that given the newest data points of actual factoring records available, their promise is somewhat optimistic.

According to our research, there are multiple types of inconsistencies and guesswork at play at many levels of the process.

Problems at the theoretical level, the Buhler’s formula and its interpretation include:

• The Buhler’s formula is a formula for worst-case asymptotic behavior.

• There are differing opinions about the unit of work given by Buhler’s formula. One computer instruction (the original intent of the estimate) is three orders of magnitude smaller measurement unit than e.g. one key schedule in a block cipher

Problems at the data point collection level include: • Creating data points is an intensive and a time-consuming

process. Multiple data points for a given modulus size are not likely to be produced publicly.

• Documentation for the measured computational complexity may be missing, ambiguous, non-unified or fragmented.

Problems at the recommendations process level • Minimum modulus sizes are given based on interoperability

more than security • Large influence of the NIST standards (even to ECRYPT)

We remark that there is a growing gap between the Buhler’s formula given as such and the existing factorization speed data, where the L-notation formula gives increasingly optimistic estimations of the complexity of factorization.

It would be prudent to incorporate the more conservative values to the next RSA modulus update process. However, due to the threat posed by quantum computation it is questionable, whether nations will continue supporting finite-field cryptography in the current extent at all in the long-term.

REFERENCES [1] ANSSI: Mécanismes cryptographiques - règles et recommandations concernant le

choix et le dimensionnement des mécanismes cryptographiques. Référentiel Général De Sécurité, Version 2.0: Annexe B1. Agence nationale de la sécurité des systèmes d’information, http://www.ssi.gouv.fr/uploads/2015/01/RGS_v-2- 0_B1.pdf. (2016)

[2] Aoki, K., Kida, Y., Shimoyama, T., Ueda, H.: GNFS Factoring Statistics of RSA- 100, 110, ... , 150. IACR eprint reports 2004/095, 9p., https://eprint.iacr.org/2004/095.pdf, Accessed: 2017/Feb/5, (2004)

[3] Bai, S., Gaudry, P., Kruppa, A., Thomé, E., Zimmermann, P.: Factorisation of RSA-220 with CADO-NFS. Paul Zimmermann publications, https://members.loria.fr/PZimmermann/papers/rsa220.pdf, Accessed: 2017/Feb/5, (2016)

54

56

58

60

62

64

66

68

70

72

400 500 600 700 800

MIPS-log

L-log

[4] Bai, S., Thomé, E., Zimmermann, P.: Factorisation of RSA-704 with CADO-NFS. IACR eprint reports 2012/369, http://eprint.iacr.org/2012/369.pdf, Accessed: 2017/Feb/5, (2012)

[5] Barker, E.: Recommendation for key management - part 1 (general), revision 4, NIST SP 800-57. National Institute of Standards and Technology (NIST) Special Publication. NIST, http://dx.doi.org/10.6028/NIST.SP.800-57pt1r4. (2016)

[6] Barker, E., Barker, W., Burr, W., Polk, W., Smid, M.: Recommendation for key management - part 1 (general), NIST SP 800-57. National Institute of Standards and Technology (NIST) Special Publication (Archived). NIST, http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1- revised2_Mar08-2007.pdf. (2007)

[7] Brent, R. P.: Recent Progress and Prospects for Integer Factorisation Algorithms (Invited Talk). In: Du, D., Eades, P., Estivill-Castro, V., et al (eds.) 6th Annual on Computing and Combinatorics - COCOON 2000, Sydney, Australia, July 26-28, 2000. Proceedings, vol. 1858, pp. 3-22. Springer Berlin Heidelberg, Berlin, Germany. (2000)

[8] BSI: Kryptographische verfahren: Empfehlungen und schlüssellängen. BSI - Technische Richtlinie. Bundesamt für Sicherheit in der Informationtechnik, https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Technis cheRichtlinien/TR02102/BSI-TR-02102.pdf?__blob=publicationFile. (2016)

[9] Buhler, J. P., Lenstra, H. W. J., Pomerance, C.: Factoring Integers With the Number Field Sieve. In: Lenstra, A.K. and Lenstra, H.W. (eds.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, vol. 1554, pp. 50-94. Springer-Verlag, New York. (1993)

[10] Cavallar, S., et. al.: Factorization of a 512-bit RSA Modulus. In: Preneel, B. (ed.) 14th International Conference on the Theory and Application of Cryptographic Techniques - EUROCRYPT 2000, Bruges, Belgium, May 14–18, 2000. Proceedings, pp. 1-18. Springer Berlin Heidelberg, Berlin, Heidelberg. (2000)

[11] Centro Criptológico Nacional (CCN): Criptologia De Empleo En El Esquema Nacional De Seguridad. Guia/Norma de Seguridad de las TIC (CCN-STIC-807), https://www.ccn-cert.cni.es/publico/seriesCCN-STIC/series/800- Esquema_Nacional_de_Seguridad/807/807-Criptologia_de_empleo_ENS- mar11.pdf, Accessed: 2017/Feb/2, (2011)

[12] CNSS: Use of Public Standards for the Secure Sharing of Information among National Security Systems. Committee on National Security Systems Information Assurance Advisory Memorandum 2-15, https://cryptome.org/2015/08/CNSS_Advisory_Memo_02-15.pdf, Accessed: 2017/Feb/2, (2015)

[13] Committee on National Security Systems (CNSS): National Policy on the use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information (Retired). CNSS Policy No. 15, Fact Sheet No. 1, https://web.archive.org/web/20060710012444/http://www.cnss.gov/Assets/pdf/cn ssp_15_fs.pdf, Accessed: 2017/Feb/3, (2015)

[14] Contini, S.: General Purpose Factoring Records. Crypto-World Factor world records, http://www.crypto-world.com/FactorRecords.html, Accessed: 2017/Feb/5, (2009)

[15] Danilov, S. A., Popovyan, I. A.: Factorization of RSA-180. Cryptology ePrint Archive, Report 2010/270, https://eprint.iacr.org/2010/270.pdf, Accessed: 2017/Feb/2, (2010)

[16] Diffie, W., Hellman, M.: New Directions in Cryptography. IEEE Trans. Inf. Theory, 22(6): 644-654, (1976)

[17] Dukhan, M.: FLOPS Per Cycle for Sandy-Bridge and Haswell SSE2/AVX/AVX2. Stack Exchange Stackoverflow questions, http://stackoverflow.com/questions/15655835/flops-per-cycle-for-sandy-bridge- and-haswell-sse2-avx-avx2, Accessed: 2017/Feb/5, (2016)

[18] ECRYPT, Smart, N. (. ).: ECRYPT CSA Algorithms, Keysize and Protocols Report. ECRYPT Coordination and Support Action deliverable D.5.2, 146p., http://www.ecrypt.eu.org/csa/documents/D5.2-AlgKeySizeProt-1.0.pdf, Accessed: 2017/Jan/25, (2016)

[19] ECRYPT, Smart, N. (. ).: ECRYPT II Yearly Report on Algorithms and Keysizes (2011-2012). European Network of Excellence in Cryptology II deliverable D.SPA.20, http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf, Accessed: 2017/Jan/25, (2012)

[20] ENISA, Smart, N. (. ).: ENISA Algorithms, Key Size and Parameters Report - 2014. EU Agency for Network and Information Security reports, 113p., http://www.ecrypt.eu.org/csa/documents/D5.2-AlgKeySizeProt-1.0.pdf, Accessed: 2017/Feb/2, (2014)

[21] Finnish Communications Regulatory Authority / NCSA-FI: Kryptografiset Vahvuusvaatimukset Luottamuksellisuuden Suojaamiseen - Kansalliset Suojaustasot (in Finnish) / Cryptographic Strength Requirements for Protecting Confidentiality - National Security Levels. NCSA-FI documents, https://www.viestintavirasto.fi/attachments/tietoturva/Kryptografiset_vahvuusvaa timukset_-_kansalliset_suojaustasot.pdf, Accessed: 2017/Feb/2, (2016)

[22] Hamilton, E., Kriens, M., Tirtea, R.: Study on the use of Cryptographic Techniques in Europe. ENISA Report, Deliverable 2011-12-19, 54p., https://www.enisa.europa.eu/publications/the-use-of-cryptographic-techniques- in-europe, Accessed: 2017/Jan/31, (2012)

[23] Jeljeli, H., Bouvier, C., Gaudry, P., Imbert, L., Thomé, E.: Discrete Logarithms in GF(P) - 180 Digits. Listserv Number Theory Archives, https://listserv.nodak.edu/cgi-

bin/wa.exe?A2=ind1406&L=NMBRTHRY&F=&S=&P=3161, Accessed: 2017/Feb/2, (2014)

[24] Kleinjung, T., et al.: Factorization of a 768-Bit RSA Modulus. In: Rabin, T. (ed.) Advances in Cryptology - CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, pp. 333-350 (2010)

[25] Lenstra, A. K., Verheul, E. R.: Selecting Cryptographic Key Sizes. J. Cryptol., 14(4): 255-293, Springer-Verlag New York, Inc. (2001)

[26] Lenstra, A. K.: Key Lengths. In: Bigdoli, H. (ed.) Handbook of Information Security - Information Warfare; Social and Legal Issues; and Security Foundations, vol. 2, pp. 617-635. John Wiley & Sons, Hoboken, NJ, USA. (2006)

[27] Lenstra, A. K., Lenstra, H. W. J., Manasse, M. S., Pollard, J. M.: The Number Field Sieve. In: Lenstra, A.K. and Lenstra, H.W. (eds.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, vol. 1554, pp. 11-42. Springer-Verlag, New York. (1993)

[28] Lenstra, A. K., Lenstra, H. W. J.: Algorithms in Number Theory. In: van Leeuwen, J. (ed.) Handbook of theoretical computer science (vol. A): algorithms and complexity , vol. A, pp. 673-715. MIT Press, Cambridge, MA, USA. (1991)

[29] Nasjonal Sikkerhetsmyndighet (NSM): NSM Cryptographic Requirements. NSM Veiledninger for systemteknisk sikkerhet, https://nsm.stat.no/globalassets/dokumenter/veiledninger/systemteknisk- sikkerhet/ncr3.1.pdf, Accessed: 2017/Feb/2, (2016)

[30] NIST: Proposed Submission Requirements and Evaluation Criteria for the Post- Quantum Cryptography Standardization Process (Draft). NIST Post-Quantum Crypto Project Documents, http://csrc.nist.gov/groups/ST/post-quantum- crypto/documents/call-for-proposals-draft-aug-2016.pdf, Accessed: 2017/Feb/2, (2016)

[31] NSA IAD: Commercial National Security Algorithm (CNSA) Suite. National Security Agency Information Assurance Directorate publications (MFS U/OO/814670-15), https://www.iad.gov/iad/library/ia-guidance/ia-solutions-for- classified/algorithm-guidance/commercial-national-security-algorithm-suite- factsheet.cfm, Accessed: 2017/Feb/4, (2015)

[32] Orman, H., Hoffman, P.: RFC 3766: Determining Strengths for Public Keys used for Exchanging Symmetric Keys. IETF Request for Comments, 23p., https://tools.ietf.org/html/rfc3766, Accessed: 2017/Feb/2, (2004)

[33] Pomerance, C.: Analysis and Comparison of Some Integer Factoring Algorithms. In: Lenstra, H.W.J. and Tijdeman, R. (eds.) Computational Methods in Number Theory, Part I, pp. 89-139. Math. Centre Tract 154, Amsterdam. (1982)

[34] Popovyan, I. A., Timofeev, A.: RSA-190 Factored . Mersenne-Forum posts, 8.11.2010, http://mersenneforum.org/showpost.php?p=236114&postcount=1, Accessed: 2017/Feb/5, (2010)

[35] Preneel, B., Preneel, B., Oswald, E., Biryukov, A., Oswald, E., Rompay, B. V., Murphy, S. et al.: NESSIE D20 - NESSIE Security Report. NESSIE project deliverable D20, 342p., https://www.cosic.esat.kuleuven.be/nessie/deliverables/D20-v2.pdf, Accessed: 2017/Jan/28, (2003)

[36] Rivest, R. L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2): 120-126, ACM. (1978)

[37] Shamir, A., Tromer, E.: On the Cost of Factoring RSA-1024. RSA CryptoBytes, 6: 10-19, (2003)

[38] Silverman, R. D.: A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths. RSA Laboratories' Bulletin, (13 - April 2000): 1-22, RSA Laboratories. (2000)

[39] Smart, N.: Algorithms and Key Sizes. ECRYPT CSA blog, http://ecrypt- eu.blogspot.fi/2015/10/algorithms-and-key-sizes.html, Accessed: 2017/Feb/5, (2015)

[40] Tilborg, H. C. A., Jajodia, S.: Encyclopedia of cryptography and security. 2nd edn. Springer Publishing Company, Incorporated (2011)

[41] Venkatesan, R.: Rigorous Analysis of a Randomized Number Field Sieve for Factoring (Lecture Video). Conference on Geometry, Algebra, Number Theory and their Information Tecnology Applications (GANITA), 15.6.2016, Toronto, Canada, http://www.fields.utoronto.ca/video-archive//event/2023/2016, Accessed: 2017/Feb/1, (2016)

[42] Wikipedia: RSA Factoring Challenge. Doom9 Forum, https://en.wikipedia.org/wiki/RSA_Factoring_Challenge, Accessed: 2017/Feb/5, (2017)

[43] Zbiciak, J.: How do You Convert GHz to FLOPS? Quora.com questions, https://www.quora.com/How-do-you-convert-GHz-to-FLOPS, Accessed: 2017/Feb/5, (2012)

[44] Zentrum für sichere Informationstechnologie – Austria (A-SIT): Sicherheitsempfehlungen Für Behörden, Teil 1: Kryptographische Methoden. Version 1.2 - 15.2.2016. http://demo.a-sit.at/wp- content/uploads/2014/11/Sicherheitsempfehlungen-Teil-1.pdf, Accessed: 2017/Feb/4, (2016)