Talk:Key size

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science  (Rated C-class, High-importance)
WikiProject icon 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.
C-Class article C  This article has been rated as C-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as High-importance).
 
edit·history·watch·refresh Stock post message.svg To-do list for Key size:

None listed.

[who?] key size question[edit]

[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)

That may have been true in 1988, it's not true now. --agr (talk) 11:49, 14 December 2012 (UTC)
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)

Recent addition[edit]

"...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 269 operations, less than the expected 280 for brute force, which is why it's being replaced. The feasibility or otherwise of performing a computation on the order of 280 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 1038 possible keys. There are 3.2 x 1015 microseconds in a century. Testing all possible keys at one key per microsecond per processor requires 1023 processors working for 100 years. Even if you reduce the strength of the algorithm by 20 bits (a work factor of 106) there is a fair margin of safety. --agr 11:28, 26 May 2006 (UTC)
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)

Error in article, needs fixing[edit]

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)

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)

Quantum Computing?[edit]

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)

I added a section. -- BenRG (talk) 13:36, 5 March 2008 (UTC)
Thanks! --APRCooper (talk) 17:25, 7 March 2008 (UTC)

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

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)

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 2128 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 2128 steps (and not 2256). RSA with 1024 bit keys has comparable strength as an 80 bit cryptosystem, i.e. very roughly it takes about 280 steps to break it. 85.2.80.189 (talk) 19:56, 18 September 2008 (UTC)
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)
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)
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)
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)

Diffie-Hellman key strength[edit]

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 (talkcontribs) 01:40, 21 February 2013 (UTC)

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

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

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)

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