Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

matasano.com

Post reply on HN
Print view View original

61–70 of 76 posts

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#61

Post by pmjordan »

paulgb wrote: post #58

Great post, not that I can claim to understand all of it. One question: Just put a “for” loop around SHA-1 and run it 1000 times to generate the key; that’ll at least slow down a brute force attack. SHA-1 is lightning fast. By itself, it’s a crappy way to generate a key. I see the purpose of this, but doesn't it also provide 999 more opportunities for a hash collision to happen? Are you so confident in the collision…

As far as I can tell, you're confusing collisions with cycles. I don't think any of the main cryptographic hashes have problems with short cycles.

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#62

Post by paulgb »

pmjordan wrote: post #61
paulgb wrote: post #58

Great post, not that I can claim to understand all of it. One question: Just put a “for” loop around SHA-1 and run it 1000 times to generate the key; that’ll at least slow down a brute force attack. SHA-1 is lightning fast. By itself, it’s a crappy way to generate a key. I see the purpose of this, but doesn't it also provide 999 more opportunities for a hash collision to happen? Are you so confident in the collision…

As far as I can tell, you're confusing collisions with cycles. I don't think any of the main cryptographic hashes have problems with short cycles.

I could well be confusing the two, because I'm not sure if I even know what cycles are :-). I'm guessing from the name that cycles are when h(h(h(... h(a)))) = a? That's not quite what I'm getting at.

I'll try explaining my concern a little better. Suppose you have a hash function h. Let p be the probability that h(x) == h(y) for any unique x and y.

Now suppose you have some arbitrary inputs a and b.

  h(a) = h(b) with probability p
  h(h(a)) = h(h(b)) with probability 2p
  h(h(h(a))) = h(h(h(b))) with probability 3p
  etc.
The probability at each step increases because a collision is possible at each step, but a collision in a previous step guarantees a collision in the current one.

With a good hash function, p should be astronomically low, so I guess that's why it isn't a problem in this case? Or am I completely off-base in my assumptions?

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#63

Post by pmjordan »

paulgb wrote: post #62
pmjordan wrote: post #61

Earlier quoted context omitted.

As far as I can tell, you're confusing collisions with cycles. I don't think any of the main cryptographic hashes have problems with short cycles.

I could well be confusing the two, because I'm not sure if I even know what cycles are :-). I'm guessing from the name that cycles are when h(h(h(... h(a)))) = a? That's not quite what I'm getting at. I'll try explaining my concern a little better. Suppose you have a hash function h. Let p be the probability that h(x) == h(y) for any unique x and y. Now suppose you have some arbitrary inputs a and b. h(a) = h(b) with…

I see what you mean now. And your intuition on cycles was spot-on.

And to answer your question (I'm not a crypto expert, so take with a pinch of salt):

With SHA-1, that probability is generally accepted to be 2^(-160). 1000 is roughly 2^10, so the final probability is about 2^(-150). I guess that's still improbable enough...

But I think you do make a very valid and interesting point.

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#64

Post by tptacek »

djahng wrote: post #59
tptacek wrote: post #2

Hm. I wrote this for our normal blog readers, who live and breathe security stuff, so I don't know how well it'll carry here.

So, in the context of the SSO cookie, could tampering with the encrypted data be prevented by signing the ciphertext (please excuse the terminology if it's not correct)? What I mean by that is, encrypt the cookie's plaintext (e.g. "user=username, role=admin, etc."), and then sign it, so the value stored in cookie is something like : ?

In the context of SSO, you could probably get away with not even encrypting it. Just take HMAC-SHA256 of the cookie contents and tack it on.

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#65

Post by tptacek »

piramida wrote: post #60
gojomo wrote: post #49

Is there a shorthand name for "the industry standard answer; the cookie both apps honor to let you in, encrypted so users can’t change their account to someone else’s" pattern, especially that pattern 'done right'? What's the best battle-tested library (and call) for implementing exactly that, without making any of the common mistakes?

yeah I think the standard answer is "don't store credentials i the cookie". session key only and central session storage.

That works great when apps can find each other, talk directly to each other, or share storage.

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#66

Post by tptacek »

pmjordan wrote: post #63
paulgb wrote: post #62

Earlier quoted context omitted.

I could well be confusing the two, because I'm not sure if I even know what cycles are :-). I'm guessing from the name that cycles are when h(h(h(... h(a)))) = a? That's not quite what I'm getting at. I'll try explaining my concern a little better. Suppose you have a hash function h. Let p be the probability that h(x) == h(y) for any unique x and y. Now suppose you have some arbitrary inputs a and b. h(a) = h(b) with…

I see what you mean now. And your intuition on cycles was spot-on. And to answer your question (I'm not a crypto expert, so take with a pinch of salt): With SHA-1, that probability is generally accepted to be 2^(-160). 1000 is roughly 2^10, so the final probability is about 2^(-150). I guess that's still improbable enough... But I think you do make a very valid and interesting point.

The loop has nothing to do with the probability of a collision. If your key comes out of /usr/share/dict/words, you have a 2^18 search space, not a 2^160 space. If you have a 2^18 search space, you better hope your constant factors are very high. Hence the loop.

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#67

Post by paulgb »

tptacek wrote: post #66
pmjordan wrote: post #63

Earlier quoted context omitted.

I see what you mean now. And your intuition on cycles was spot-on. And to answer your question (I'm not a crypto expert, so take with a pinch of salt): With SHA-1, that probability is generally accepted to be 2^(-160). 1000 is roughly 2^10, so the final probability is about 2^(-150). I guess that's still improbable enough... But I think you do make a very valid and interesting point.

The loop has nothing to do with the probability of a collision. If your key comes out of /usr/share/dict/words, you have a 2^18 search space, not a 2^160 space. If you have a 2^18 search space, you better hope your constant factors are very high. Hence the loop.

Yeah, I get why the loop is there. But I still think it increases the probability of a collision by nearly 1000x over the probability of a collision without the loop.

Maybe a better way to explain my concern is to consider hashing something once versus twice, rather than 1000 times.

Let h be a hash function and p be the probability P(h(x) = h(y)) for randomly chosen x and y.

Say you have unique inputs a and b.

Obviously, P(h(a) = h(b)) = p.

Now consider P(h(h(a)) = h(h(b))). h(h(a)) = h(h(b)) if:

  h(a) = h(b) [probability p]
     OR
  h(a) != h(b) [probability 1-p], and
  h(h(a)) = h(h(b)) [probability p].
So the total probability when we repeat the hash is p + (1-p) * p

Since p is small, the probability of a collision has nearly doubled just by applying the hash function again.

[note: Higher up in this thread I mistakenly implied that the probability increased linearly. With a low number of iterations and realistic values for p it should be close to linear, but not exact.]

[edit:formatting]

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#68

Post by tptacek »

paulgb wrote: post #67
tptacek wrote: post #66

Earlier quoted context omitted.

The loop has nothing to do with the probability of a collision. If your key comes out of /usr/share/dict/words, you have a 2^18 search space, not a 2^160 space. If you have a 2^18 search space, you better hope your constant factors are very high. Hence the loop.

Yeah, I get why the loop is there. But I still think it increases the probability of a collision by nearly 1000x over the probability of a collision without the loop. Maybe a better way to explain my concern is to consider hashing something once versus twice, rather than 1000 times. Let h be a hash function and p be the probability P(h(x) = h(y)) for randomly chosen x and y. Say you have unique inputs a and b. Obviou…

H(m) -> SHA1(SHA1(m)) is not the same hash function as H(m) -> SHA1(m).

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#69

Post by paulgb »

tptacek wrote: post #68
paulgb wrote: post #67

Earlier quoted context omitted.

Yeah, I get why the loop is there. But I still think it increases the probability of a collision by nearly 1000x over the probability of a collision without the loop. Maybe a better way to explain my concern is to consider hashing something once versus twice, rather than 1000 times. Let h be a hash function and p be the probability P(h(x) = h(y)) for randomly chosen x and y. Say you have unique inputs a and b. Obviou…

H(m) -> SHA1(SHA1(m)) is not the same hash function as H(m) -> SHA1(m).

Right, but if SHA1(m) = SHA1(n), then SHA1(SHA1(m)) = SHA1(SHA1(n)) also.

The converse is not true. There will be cases where SHA1(SHA1(m)) = SHA1(SHA1(n)), but SHA1(m) != SHA1(n). (Or does SHA1 somehow guarantee that this will not happen?)

So it seems to follow that the chances that H(a) = H(b) when H(m) -> SHA1(SHA1(m)) must be higher than when H(m) -> SHA1(m).

Am I missing something?

Re: Typing The Letters A-E-S Into Your Code? You’re Doing It Wrong

#70

Post by tptacek »

paulgb wrote: post #69
tptacek wrote: post #68

Earlier quoted context omitted.

H(m) -> SHA1(SHA1(m)) is not the same hash function as H(m) -> SHA1(m).

Right, but if SHA1(m) = SHA1(n), then SHA1(SHA1(m)) = SHA1(SHA1(n)) also. The converse is not true. There will be cases where SHA1(SHA1(m)) = SHA1(SHA1(n)), but SHA1(m) != SHA1(n). (Or does SHA1 somehow guarantee that this will not happen?) So it seems to follow that the chances that H(a) = H(b) when H(m) -> SHA1(SHA1(m)) must be higher than when H(m) -> SHA1(m). Am I missing something?

I think you're going to need to better explain the logic behind graf 2 before I can answer you.

But on the off chance that we can end this thread gracefully, I'll point out that SHA256(SHA(256(m), m) is SHAd256(m), and considered by Ferguson to address security concerns in straight SHA256.

Post reply on HN