View source for Talk:Key size

{{WikiProject banner shell|class=C|
{{WikiProject Cryptography|importance=High}}
}}
{{todo}}


== [who?] key size question ==

<ref>{{cite web|last=Burrows|first=James H|title=Director|url=http://www.itl.nist.gov/fipspubs/fip46-2.htm|work=Institute for Computer Sciences and Technology|publisher=National Bureau of Standards|accessdate=14 December 2012}}</ref> 1988 January 22
<ref>http://www.itl.nist.gov/fipspubs/fip46-2.htm</ref>

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. "
[[User:Biofuel|Biofuel]] ([[User talk:Biofuel|talk]]) 06:40, 14 December 2012 (UTC)

:That may have been true in 1988, it's not true now. --[[User:ArnoldReinhold|agr]] ([[User talk:ArnoldReinhold|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. [[Special:Contributions/178.195.225.28|178.195.225.28]] ([[User talk:178.195.225.28|talk]]) 10:02, 15 December 2012 (UTC)

{{reflist-talk}}

==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<sup>69</sup> operations, less than the expected 2<sup>80</sup> for brute force, which is why it's being replaced. The feasibility or otherwise of performing a computation on the order of 2<sup>80</sup> hasn't changed. [[User:Matt Crypto|&mdash; Matt <small>Crypto</small>]] 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<sup>38</sup> possible keys. There are 3.2 x 10<sup>15</sup> microseconds in a century. Testing all possible keys at one key per microsecond per processor requires 10<sup>23</sup> processors working for 100 years. Even if you reduce the strength of the algorithm by 20 bits (a work factor of 10<sup>6</sup>) there is a fair margin of safety. --[[User:ArnoldReinhold|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. [[user:FT2|FT2]] <sup><span style="font-style:italic">([[User_talk:FT2|Talk]] | [[Special:Emailuser/FT2|email]])</span></sup> 00:35, 30 May 2007 (UTC)

== 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? [[user:FT2|FT2]] <sup><span style="font-style:italic">([[User_talk:FT2|Talk]] | [[Special:Emailuser/FT2|email]])</span></sup> 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. -- [[User:BenRG|BenRG]] ([[User talk:BenRG|talk]]) 21:12, 28 January 2008 (UTC)

== 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! --[[User:APRCooper|APRCooper]] ([[User talk:APRCooper|talk]]) 14:26, 28 February 2008 (UTC)

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

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

== 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.  [[User:Saintrain|Saintrain]] ([[User talk: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 2<sup>128</sup> 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<sup>128</sup> steps (and not 2<sup>256</sup>). RSA with 1024 bit keys has comparable strength as an 80 bit cryptosystem, i.e. very roughly it takes about 2<sup>80</sup> steps to break it. [[Special:Contributions/85.2.80.189|85.2.80.189]] ([[User talk: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"?  [[User:Saintrain|Saintrain]] ([[User talk: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. -- [[User:BenRG|BenRG]] ([[User talk:BenRG|talk]]) 02:04, 19 September 2008 (UTC)
::::Forgot the other "security" in this context.  How about "this property" to "equivalent key strength"?  <small>(Funny, it's obious to me now but confusing before.  Like, "Two faces? Nah. It's just a vase.  Oh.  Yeah.")</small>  [[User:Saintrain|Saintrain]] ([[User talk: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.
:::::--[[User:Davidgothberg|David Göthberg]] ([[User talk:Davidgothberg|talk]]) 21:43, 19 September 2008 (UTC)

== 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.  <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Kuroyama|Kuroyama]] ([[User talk:Kuroyama|talk]] • [[Special:Contributions/Kuroyama|contribs]]) 01:40, 21 February 2013 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
:not in finite fields. --[[User:MarioS|MarioS]] ([[User talk:MarioS|talk]]) 11:55, 3 June 2013 (UTC)

== "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? [[Special:Contributions/87.112.9.121|87.112.9.121]] ([[User talk:87.112.9.121|talk]]) 19:23, 13 March 2014 (UTC)

== 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 [[Password strength|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 [[ElGamal encryption|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..."? [[User:Enotdetcelfer|Enotdetcelfer]] ([[User talk:Enotdetcelfer|talk]]) 04:48, 12 February 2019 (UTC)

== External links modified ==

Hello fellow Wikipedians,

I have just modified 3 external links on [[Key size]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=778768665 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:
*Added archive https://web.archive.org/web/20120410194831/http://www.pcworld.com/article/16028/governments_relax_encryption_regulations.html to http://www.pcworld.com/article/16028/governments_relax_encryption_regulations.html
*Added archive https://web.archive.org/web/20140606050814/http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf to http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf
*Added archive https://web.archive.org/web/20090207005135/http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml to http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml

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

{{sourcecheck|checked=true|needhelp=}}

Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 03:57, 5 May 2017 (UTC)

== 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? --[[User:EvanProdromou|ESP]] ([[User talk:EvanProdromou|talk]]) 18:30, 24 November 2017 (UTC)

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

== 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. [[User:Paulehoffman|Paulehoffman]] ([[User talk:Paulehoffman|talk]]) 16:08, 11 February 2023 (UTC)