Talk:Key size

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

[who?] key size question

^[1] 1988 January 22 ^[2]

States in section 15 "no technique other than trying all possible keys using known input and output for the DES will guarantee finding the chosen key. As there are over 70,000,000,000,000,000 (seventy quadrillion) possible keys of 56 bits, the feasibility of deriving a particular key in this way is extremely unlikely in typical threat environments. " Biofuel (talk) 06:40, 14 December 2012 (UTC)[reply]

That may have been true in 1988, it's not true now. --agr (talk) 11:49, 14 December 2012 (UTC)[reply]

Well, the statement in question "... was thought[who?] to be sufficient ..." is about the security of DES when it was released. The reference given by the OP still judges the security of DES as sufficient (for typical applications) even 11 years after release. So, yes it is still true that in 1988 NBS rated the security of DES as sufficient. 178.195.225.28 (talk) 10:02, 15 December 2012 (UTC)[reply]

References

^ Burrows, James H. "Director". Institute for Computer Sciences and Technology. National Bureau of Standards. Retrieved 14 December 2012.
^ http://www.itl.nist.gov/fipspubs/fip46-2.htm

Recent addition

"...As of 2003, the U.S. National Institute for Standards and Technology, NIST, is proposing that 80-bit keys be phased out by 2015. The 2005 Shandong University attack on SHA1 suggests a faster phase out."

Hmm...I'm not so sure it does. The SHA-1 attack is claimed to take 2⁶⁹ operations, less than the expected 2⁸⁰ for brute force, which is why it's being replaced. The feasibility or otherwise of performing a computation on the order of 2⁸⁰ hasn't changed. — Matt Crypto 18:01, 23 Feb 2005 (UTC)

Well, it's arguable. I think the broader point is that a cryptographic algorithm with a nominal key size of N may well have weaknesses that reduce that strength somewhat. On the other hand, I took out the recent addition: "or at least will be out of reach while technology continues along its current course. In respect of long term information security it is as well to hold that factor in mind because there are several potential leaps in computational methodology which, _when_ one of the is made, will render current key lengths laughably insecure. A currently evolving technique is that of distributed procssing, where a task is shared between a (potentially very large) network of machines. This technique already renders low to moderate keylengths brute-force breakable." Distributed processing is not, of itself a threat to 128-bit keys. There are 3.4 x 10³⁸ possible keys. There are 3.2 x 10¹⁵ microseconds in a century. Testing all possible keys at one key per microsecond per processor requires 10²³ processors working for 100 years. Even if you reduce the strength of the algorithm by 20 bits (a work factor of 10⁶) there is a fair margin of safety. --agr 11:28, 26 May 2006 (UTC)[reply]

It doesn't matter too badly why it does, if thats what they recommend, its then a factual comment.

But as background, the concern is not just the availability of processing power to crack it. It's also the speed of development of new attacks that cut down the work needed. So for example, it may be that they feel that computationally we will not have enough computing power for 70 years... but that the algorithm itself will gradually become more vulnerable to attacks with less processing power over time and therefore based on speed of mathematical analysis development they now feel it may not last more than 10 years reliably and should be replaced in 5. That's what's going on, I think. FT2 ^{(Talk | email)} 00:35, 30 May 2007 (UTC)[reply]

Error in article, needs fixing

One of the asymmetric algorithm types, elliptic curve cryptography, or ECC, appears to be secure with shorter keys than those needed by other asymmetric key algorithms. NIST guidelines state that ECC keys should be twice the length of equivalent strength symmetric key algorithms. So, for example, a 224-bit ECC key would have roughly the same strength as a 112-bit symmetric key.

If ECC is "secure with shorter keys" then the NIST recommendation would be half the length, and a 112 bit ECC key would be roughly as secure as 224 symmetric (it's given the other way around).

In other words this section should read as follows, either of these versions:

One of the asymmetric algorithm types, elliptic curve cryptography, or ECC, appears to be secure with longer keys than those needed by other asymmetric key algorithms. NIST guidelines state that ECC keys should be twice the length of equivalent strength symmetric key algorithms. So, for example, a 224-bit ECC key would have roughly the same strength as a 112-bit symmetric key.

One of the asymmetric algorithm types, elliptic curve cryptography, or ECC, appears to be secure with shorter keys than those needed by other asymmetric key algorithms. NIST guidelines state that ECC keys can be half the length of equivalent strength symmetric key algorithms. So, for example, a 112-bit ECC key would have roughly the same strength as a 224-bit symmetric key.

Fix? FT2 ^{(Talk | email)} 00:29, 30 May 2007 (UTC)[reply]

Very late reply, but anyway... you misread the paragraph. It says "ECC appears to be secure with shorter keys than those needed by other asymmetric key algorithms [...] So, for example, a 224-bit ECC key would have roughly the same strength as a 112-bit symmetric key." ECC needs shorter keys than (say) RSA, but longer than (say) AES. -- BenRG (talk) 21:12, 28 January 2008 (UTC)[reply]

Quantum Computing?

I am not sufficiently expert to write a suitable section, but should there be a section explaining that most current encryption algorithms are vulnerable to quantum computing techniques, when and if they are sufficiently mature? I would suggest that this branch of computing is much nearer providing routine cracking of present day encryption techniques than Moore's Law would indicate. Of course, we do not know what is happening inside organizations such as GCHQ and NSA! --APRCooper (talk) 14:26, 28 February 2008 (UTC)[reply]

I added a section. -- BenRG (talk) 13:36, 5 March 2008 (UTC)[reply]

Thanks! --APRCooper (talk) 17:25, 7 March 2008 (UTC)[reply]

What means "No asymmetric-key algorithms with this property are known"?

In the intro phrase, "No asymmetric-key algorithms with this property are known", the only "property" that can be inferred is that of key-length ≈ security (I can't find the "proportional to" symbol!?). That doesn't make sense. What property is being referenced, or what was the sentence supposed to say? Thanks. Saintrain (talk) 19:20, 18 September 2008 (UTC)[reply]

Not sure what doesn't make sense. It almost seems that you are answering your own question. For many symmetric cryptosystems a k-bit key gives k-bit security. E.g. the best known attack against AES with an 128 bit key needs 2¹²⁸ steps. Asymmetric cryptosystems don't have k-bit security with k-bit keys. E.g. the best known attack against ECDSA with a 256 bit key needs 2¹²⁸ steps (and not 2²⁵⁶). RSA with 1024 bit keys has comparable strength as an 80 bit cryptosystem, i.e. very roughly it takes about 2⁸⁰ steps to break it. 85.2.80.189 (talk) 19:56, 18 September 2008 (UTC)[reply]

Thanks 189, I get it now (after several readings). Any problems if I change "property" to "level of security"? Saintrain (talk) 21:23, 18 September 2008 (UTC)[reply]

I'm not sure that's a good idea. Asymmetric ciphers are just as secure as symmetric ciphers, they just have longer keys. -- BenRG (talk) 02:04, 19 September 2008 (UTC)[reply]

Forgot the other "security" in this context. How about "this property" to "equivalent key strength"? (Funny, it's obious to me now but confusing before. Like, "Two faces? Nah. It's just a vase. Oh. Yeah.") Saintrain (talk) 18:47, 19 September 2008 (UTC)[reply]

I don't think those sentences need any change. Have you read the rest of that sentence? ",elliptic curve cryptography comes the closest with an effective security of roughly half its key length." I think that makes it clear that public-key ciphers need longer keys to get the same level of security.

--David Göthberg (talk) 21:43, 19 September 2008 (UTC)[reply]

Diffie-Hellman key strength

It is claimed that:

The Finite Field Diffie-Hellman algorithm has roughly the same key strength as RSA for the same key sizes. The work factor for breaking Diffie-Hellman is based on the discrete logarithm problem, which is related to the integer factorization problem on which RSA's strength is based. Thus, a 3072-bit Diffie-Hellman key has about the same strength as a 3072-bit RSA key.

Really? Discrete logarithm is a harder problem than factoring. — Preceding unsigned comment added by Kuroyama (talk • contribs) 01:40, 21 February 2013 (UTC)[reply]

not in finite fields. --MarioS (talk) 11:55, 3 June 2013 (UTC)[reply]

"if sufficiently large quantum computers capable of running Shor's algorithm become available"

What is meant by "sufficiently large" could a "sufficiently large" conventional computer do the job? 87.112.9.121 (talk) 19:23, 13 March 2014 (UTC)[reply]

Opening sentence: security vs. hardness assumption

I have revised the opening to try to clarify what was meant. It is still a little unclear to me. In particular, I assume an algorithm's security is intended to correspond to the difficult of any Computational hardness assumption(s) on which the algorithm's security is based. I haven't tried to clarify this, because I'm not an expert. It would be great if someone else could clarify.

Mistake? Key storage vs. key size

The opening sentence

key size or key length is the number of bits in a key used by a cryptographic algorithm

seems to be incorrect. For instance, an El Gamal public key is a prime p, a generator g, and g^x, where x is a random value used in the private key. Thus, the public key length in El Gamal is the length of the prime, plus the length of the generator, plus the length of g^x mod p. But, this isn't how we use key length, since we refer to only the length of g^x mod p.

(We could argue that the public key is g^x, and p and g are merely security parameters, but then the theory of cryptography comes tumbling down, because definitions of asymmetric encryption state that the encryption algorithm only inputs the public key, not the public key and some security parameters.)

Mistake? Symmetric vs. Asymmetric

The sentence

Since longer symmetric keys require exponentially more work to brute force search, a sufficiently long symmetric key makes this line of attack impractical.

Shouldn't this be "...longer asymmetric keys..." and "...long asymmetric keys..."? Enotdetcelfer (talk) 04:48, 12 February 2019 (UTC)[reply]

External links modified

Hello fellow Wikipedians,

I have just modified 3 external links on Key size. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Y An editor has reviewed this edit and fixed any errors that were found.

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 03:57, 5 May 2017 (UTC)[reply]

RSA key strength

The article currently says: As of 2003 RSA Security claims that 1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys and 3072-bit RSA keys to 128-bit symmetric keys.[14] RSA claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030.[14] An RSA key length of 3072 bits should be used if security is required beyond 2030.[15] NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys.[16]

The reference is to a 2003 analysis. Since we're now in 2017, it seems that we should know whether 1024-bit keys actually did become crackable. So, two questions: is there a tag for Wikipedia to mark predictions like this, like a DIDTHISCOMETRUE template? And, second: did this actually come true? --ESP (talk) 18:30, 24 November 2017 (UTC)[reply]

They did not become crackable. The best-known public attack in 2023 is still under 829 bits (from 2020). Paulehoffman (talk) 01:52, 11 February 2023 (UTC)[reply]

TripleDES was known to have 112 bits of strength from the start

The text in the introduction indicates that a new attack reduced the strength of TripleDES after it was designed. That is not true: the meet-in-the-middle attack was known before TripleDES was created. The design goal for TripleDES was 112 bits. I would like to change the intro to remove TripleDES but instead insert RSA, where the NFS attacks were indeed a surprise. Paulehoffman (talk) 16:08, 11 February 2023 (UTC)[reply]

[1] Burrows, James H. "Director". Institute for Computer Sciences and Technology. National Bureau of Standards. Retrieved 14 December 2012.

[2] ttp://www.itl.nist.gov/fipspubs/fip46-2.htm

[1]

[2]