Talk:Key strengthening

From Wikipedia, the free encyclopedia

WikiProject on Cryptography This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

Contents

[edit] Worth 72 bits?

Another way to think of it is that 65000 rounds in the loop means about 216 operations, which means the stronger key is "worth" about 16 bits more in key strength. If the weak key is a 56-bit "export key" then after key strengthening it is worth 56+16 = 72 bits.

This part seems just wrong, since the strength of a 56-bit key is only worth 56-bit when attacked with a brute force exhaustive search. If you use a dictionary attack then a real password usually isn't as strong as the derived key could potentially be (in this case 56-bit). Therefore it's not the output key that is strengthened but the input, which is much weaker.

In other words: you can't exceed the strength of the output key, only the weak input.

If you'd try to strengthen a totally random 56-bit key by repeatedly hashing it and then cutting it down to 56-bit again the cost of an attack wouldn't change, since you could just perform an exhaustive search on the output key instead of the input.

Thus i'll remove that paragraph.

--89.55.230.143 17:18, 7 March 2007 (UTC)

Well, you missunderstood that paragraph. You are right that "You can't exceed the strength of the output key, only the weak input." However, the output key is a "stronger key" and should be the full result of the key strengthening. That is, 128 bits or more. We should NOT cut the output key down to 56-bits after strengthening it. The export laws (thankfully) do not require that.
I put the paragraph back into the text and changed "it" in the sentence to say "the stronger key" to make the paragraph clearer. So the sentence is now: "If the weak key is a 56-bit "export key" then after key strengthening the stronger key is worth 56+16 = 72 bits."
We can extend the paragraph to explain that the output stronger key should NOT be cut down to 56 bits again but should be kept as 128 bits or more. If you find it necessary to make it understandable?
--David Göthberg 11:44, 4 April 2007 (UTC)

[edit] +1.5 years/bit

So far computer speed has doubled about once per 1.5 years. (See Moore's law.) This means that each 1.5 years one more bit of key strength is possible to crack. This means that the 16 extra bits of strength is worth about 16×1.5 = 24 years later cracking.

That's true only for key that can be cracked in long periods (years, not months).

Example 1:

Let's imagine n-bit key can be cracked in 1 minute. Now, let's add 1 bit to the key: (n+1)-bit key will be cracked in 2 minutes, not 1.5 years + 1 minute.

Example 2:

Let n-bit key can be cracked in t years with computation power growing 2x every 1.5 years (P(t) = 2^{\frac{t}{1.5}}, where t = time in years). First, let's find how many "years" (in terms of current computers) will be "calculated" in t real years:
\int 2^{\frac{x}{1.5}}\,\mathrm{d}x = \frac{1.5}{\ln 2}\cdot2^{\frac{x}{1.5}}
N(t) = \int_{0}^{t} 2^{\frac{x}{1.5}}\,\mathrm{d}x = \frac{1.5}{\ln 2}\cdot\left(2^{\frac{t}{1.5}}-2^{\frac{0}{1.5}}\right) = \frac{1.5}{\ln 2}\cdot\left(2^{\frac{t}{1.5}}-1\right)
For example, if key can be cracked in 15 years with computer speed growing, current computers will crack it in:
\frac{1.5}{\ln 2}\cdot\left(2^{\frac{15}{1.5}}-1\right) = \frac{1.5}{\ln 2}\cdot(1024-1) = 2213.8\,years (impressive, isn't it?)
Now let's add 1 bit to the key. It requires 2x calculations(but not computation power!). Let's calculate how fast it can be cracked:
N\left(t_{2}\right)=2\cdot N(t_{1})
\frac{1.5}{\ln 2}\cdot\left(2^{\frac{t_{2}}{1.5}}-1\right) = 2\cdot\frac{1.5}{\ln 2}\cdot\left(2^{\frac{t_{1}}{1.5}}-1\right)
2^{\frac{t_{2}}{1.5}} = 2\cdot 2^{\frac{t_{1}}{1.5}}-1
\frac{t_{2}}{1.5} = log_{2}(2\cdot 2^{\frac{2t_{1}}{3}}-1)
t_{2}(t_{1}) = 1.5\cdot log_{2}(2\cdot 2^{\frac{2t_{1}}{3}}-1)
Examples:
t_{2}(1\, month) = t_{2}(\frac{1}{12}) = 1.5\cdot log_{2}\left(2^{\frac{38}{36}}-1\right) =\frac{1.96}{12}= almost\, 2\, months.
t_{2}(1) = 1.5\cdot log_{2}\left(2^{\frac{5}{3}}-1\right) =1.681=(1+0.681)\, years.
t_{2}(3) = 1.5\cdot log_{2}\left(2^{3}-1\right) =4.211=(3+1.211)\, years.
t_{2}(6) = 1.5\cdot log_{2}\left(2^{5}-1\right) =7.431=(6+1.431)\, years.
t_{2}(15) = 1.5\cdot log_{2}\left(2\cdot 2^{\frac{2\cdot 15}{3}}-1\right) = 1.5\cdot log_{2}(2^{11}-1) =16.4989=(15+1.4989)\, years.
So, everything is correct, but for longer periods. :)
— lim 18:19, 31 August 2007 (UTC)
No, you have misunderstood what that paragraph means. Say you have a X bit "weak key". And that your attacker with his supercomputer can crack that key in about 2 months. But the attacker only thinks the kind of target you are are worth about 1 month of supercomputer time. So you are to expensive for them to attack so they will use their supercomputer for other targets. (Easier targets or targets more worth to attack for them.) But in about 1.5 years they will have a twice as fast supercomputer. And then it will only take them about 1 month to crack your key. Then they think it is worth it and will crack your key. But if you have applied 216 key strengthening rounds to your key they will not be able to crack that "stronger key" even with their new supercomputer. Since it would take them 216 months to crack with that supercomputer. (That is 5461 years mind you.) So they will instead have to wait 16 * 1.5 years = 24 years until they have bought a fast enough supercomputer to do the cracking in one month of supercomputer time. --David Göthberg 00:08, 1 September 2007 (UTC)
Ok, it was too simple for me to understand. :) Still, what I said is also true. — lim 11:26, 1 September 2007 (UTC)

[edit] Consistency

Hi, unless i'm missing something (and while this is somewhat trivial) the below excerpt (from the article)

 key = hash( password + salt )
 for 1 to 65000 do
   key = hash( salt + key )

should be changed to:

 key = hash( password + salt )
 for 1 to 65000 do
   key = hash( key + salt )

for concatentation consistency... again maybe it's stupid... just my comment...

purpleidea (talk) 06:00, 27 December 2007 (UTC)

First a disclaimer: I have studied computer security and encryption since 1988 but I am not a crypto analyst.
As far as I can see it doesn't matter much in what order we hash together the key and the salt. Both ways prevent dictionary attacks and rainbow table attacks etc. However, we did take those examples from reports written by professional cryptographers (see the references). But this article and that code has been edited many times by many editors since then so I don't remember which order those reports used. But putting the key first like you did looks better together with the other examples so I don't feel the need to change it back.
--David Göthberg (talk) 12:03, 6 March 2008 (UTC)

[edit] Update

The article might need a minor update to reflect increases in computing power - it currently cites "today" as 2006. Socrates2008 (Talk) 11:49, 6 March 2008 (UTC)

[edit] References?

Socrates2008: You keep slabbing {{nofootnotes}} and {{refimprove}} on this article. Why?

This article covers a method that is so simple that any one with a basic understanding of cryptography understands how it works and why it is secure. We have two perfectly good references to papers that covers the content of the article. Papers written by some of the most respected cryptographers there is.

Do you mean that we should reference every paragraph in the article to the corresponding sections in those two papers? I haven't heard before that we should "deep link" references like that.

By the way, this is a wiki, you can edit it. So instead of just complaining, why don't you fix it yourself? And why do you do your complaints in the article instead of here on the talk page?

Or is it that you don't understand the method and why it is secure? If that is the case then I can set you up with some good crypto literature so you can read up on it.

--David Göthberg (talk) 11:49, 22 March 2008 (UTC)

Kindly read verifiability rather than having a go at other editors about the poor referencing in the article. Thank you. Socrates2008 (Talk) 03:21, 23 March 2008 (UTC)
So please specify, exactly what part of the article are you challenging? And is that part lacking from the two main references that we have put in this article? Or is it that you don't find the authors of those references ( Bruce Schneier, David Wagner etc) to be reliable sources when it comes to cryptography? You know, they are among the most trusted crypto analysts there are. (But I guess you don't know, right?)
--David Göthberg (talk) 04:09, 23 March 2008 (UTC)
No footnotes. Therefore not possible to determine which parts of the article are referenced and which parts not. Socrates2008 (Talk) 05:32, 23 March 2008 (UTC)

[edit] Is salting considered key strengthening?

In a recent edit, a new section called 'salting' was added to the article; however, does this actually constitute key strengthening? As far as I can tell, salting is primarily a defense against time-memory tradeoffs (like rainbow tables), not about slowing down individual tests.

This means that it doesn't comply with the definition given in the lead section, "[...] to make a weak key such as a password or passphrase stronger, i.e. more costly to test combinations through brute force or a dictionary attack. They operate by increasing the time it takes to test each possible key". Either the 'salting' section should be removed, or the lead section should be updated. -- intgr [talk] 14:37, 9 April 2008 (UTC)

Right, I wouldn't consider salting to be "key strengthening/stretching", although it does make the key stronger. As you pointed out, salting is to prevent rainbow tables and similar (prevent using stored data), and key strengthening is about causing more CPU work. But both should of course be combined, as we show in the second and third examples. And I agree, the salting section should go. It was fine as it was just before that, with salting in example two and three and a little explanation about salting with a link to the salt article.
By the way, I saw that the user that added the salting section also added a "Main article: hash chain". But those examples are not hash chains. Hash chains are just really bad CSPRNGs. The only thing they have in common with key strengthening is that they use a hash in a loop.
--David Göthberg (talk) 15:32, 9 April 2008 (UTC)
I did a copy edit to clean things up some. I gave salting a brief mention as a related technique. I also took out the stuff on export control. I'm not aware of key strengthening actually being used to defeat export key size limits and I strong suspect the export control agencies would simply refuse to license systems that used key strengthening or further limit key size when it was used.--agr (talk) 16:42, 9 April 2008 (UTC)
Well, I used to work with building crypto software for export. So I have read the crypto export regulations here in the EU (which seems to be a direct copy of the Wassenaar Arrangement) and I have several times been in meetings with the export control authority here in my country (Sweden). You don't need a "license" to export systems that has a shorter key length than what the export control restrictions mandate. So it is not about "licensing", it is about following the rules. Pretty much all ciphers internally use some key setup and key expansion. The rules do not state anything about such internal key expansion and the export authorities both in North America and the EU have always allowed export of ciphers like DES that internally used a larger key size than the export limit prescribed. (The limits were increased some years ago so now even the internal key size in DES is below the limit, but the internal size of for instance AES is still above the limits, but may be used as long as it is fed a shorter key.)
But sure, if key strengthening became too common then the export control authorities probably will create new rules that limits it in some way.
--David Göthberg (talk) 17:54, 9 April 2008 (UTC)