use bigger random one-time keys, rename to "timing_safe_compare"

[zooko]

Because of this advice from Marsh Ray and Solar Designer: ​https://twitter.com/zooko/status/431105294777597952

[zooko]

​https://github.com/tahoe-lafs/tahoe-lafs/pull/86

[zooko]

Here is Solar Designer's reviewcomment: ​https://twitter.com/solardiz/status/431414358846230528

[daira]

Is the pull request attached to the right branch? It seems to be a branch that includes patches for #1382, which makes it difficult to review.

[zooko]

Replying to daira:

Is the pull request attached to the right branch? It seems to be a branch that includes patches for #1382, which makes it difficult to review.

Whoops, sounds like I accidentally used the wrong branch. If someone else could fix that for me, that would be fine, or else I will do so when I get a minute…

[daira]

I reviewed ​https://github.com/zooko/tahoe-lafs/commit/a79b6927af57dc701af2f9037f11accc324a9cfb and it looks fine, other than being on the wrong branch. I'll commit it to trunk.

[Daira Hopwood <daira@…>]

In 6ca5f5fc39650de55c9d93ceef5f275b80a100d1/trunk:

Use bigger random one-time keys in timing_safe_compare. fixes #2165

Follows this advice from Marsh Ray and Solar Designer: ​https://twitter.com/zooko/status/431105294777597952

Signed-off-by: Daira Hopwood <daira@…>

[daira]

There should also have been a commit notification for d5651a0d0eebdc144db53425ee461e186319e5fd/trunk; not sure why there wasn't.

[daira]

BTW zooko, for future reference, please don't use quotes in branch names. (They confuse git's shell command completion.)

[warner]

BTW, looking back at it, I don't believe the os.urandom is necessary at all. hash(X) == hash(Y) is sufficient, as long as the attacker only gets to submit "X" and not hash(X). To learn the first byte of hash(Y), they must create 256 Xs (where each one has a hash(X) that begins with a different value), at a cost of about 256 trials. Then they can do the usual timing attack with these 256 strings. But, once they've learned the first byte of hash(Y), then to learn the second byte, they must build a new set of 256 Xs (where they care about both the first and second bytes) at a cost of 256^2 trials. This gets exponentially worse as they try to test more bits, because they can't cheaply control the output of hash(Y).

Of course these days I'd use HKDF(X) instead of SHA256(X), or maybe HMAC or SHA256d.

I believe there's a different construct in which the random value is important, but not hash-vs-hash.

[zooko]

Replying to warner:

BTW, looking back at it, I don't believe the os.urandom is necessary at all. hash(X) == hash(Y) is sufficient, as long as the attacker only gets to submit "X" and not hash(X).

That's funny, Brian! Because when you first invented this, I suggested hash(X) == hash(Y) instead, and you objected that you weren't entirely sure that was safe, and I later decided that you were right!

The thing is, the computation of hash(X) (where X is the secret) might leak information about X!

Although I guess you could always just compute that one time at process-start-up and store the value of hash(X) and use that. Okay, I'm convinced that would be safe. ☺

[warner]

That *is* funny. Yeah, I remember thinking that I didn't have time to analyze it properly, and being freaked out that it's easy to get the first few bytes of the target, so a randomized hash would be the most conservative approach.

I like your hash-it-once-and-store-it approach. For our purposes, I guess that'd mean storing H(write-enabler) instead of write-enabler, so the potentially-leaky hash occurs at mutable-share creation time, not subsequent access time.