5 ms·

The fix, for anyone who is interested: https://github.com/golang/go/commit/42b42f71cf8f5956c09e66230293dfb5db652360 https://github.com/golang/go/commit/42b42f71

The fix, for anyone who is interested: https://github.com/golang/go/commit/42b42f71cf8f5956c09e66230293dfb5db652360 https://github.com/golang/go/commit/42b42f71cf8f5956c09e6623...

selljamhere 8y ago
Is there anyone who can ELI5 what `beta8.Mod(beta8, curve.P)` does?
- guessmyname 8y ago
  I cannot ELI5 this for you, but here’s more context: beta8 := new(big.Int).Lsh(beta, 3) beta8.Mod(beta8, curve.P) https://golang.org/pkg/math/big/#Int.Mod https://golang.org/pkg/math/big/#Int.Mod
- lifthrasiir 8y ago
  It is hard to explain what is `beta8` and `curve.P` specifically, but they are arbitrary-precision integers so you can see what went wrong with an appropriate pseudocode: x3 = alpha * alpha beta8 = beta << 3 // beta8 %= curve.P x3 -= beta8 while x3 < 0 { x3 += curve.P } Essentially we want to compute `(alpha * alpha - beta * 8) % curve.P`, so to say. The modulo is expensive though, so for typical cases we can just repeatedly add `curve.P` to compute the modulo a few times. This is indeed a valid optimization when we are sure of the range of `alpha` and `beta`, but `beta` can be controlled outside. So a very large `beta` from an attacker will cause the while loop run forever---a denial-of-service attack.
  - Thorrez 8y ago
    Here's the new code: beta8.Mod(beta8, curve.P) x3.Sub(x3, beta8) if x3.Sign() == -1 { x3.Add(x3, curve.P) } x3.Mod(x3, curve.P) I don't understand it why it's all necessary. This is shorter and seems to do the exact same thing: beta8.Mod(beta8, curve.P) x3.Sub(x3, beta8) x3.Mod(x3, curve.P) Also, beta8 is never used after this code. So this should do the same thing as well: x3.Sub(x3, beta8) x3.Mod(x3, curve.P)
    - lifthrasiir 8y ago
      I think you are right. Go `big.Mod` should be Euclidean (i.e. `x % y` follows `y`'s sign) so the code is redundant. It doesn't seem to be required to run in constant time (if so we won't have `if` at all), probably the committer wanted a minimal change?

The fix, for anyone who is interested: https://github.com/golang/go/commit/42b42f71cf8f5956c09e66230293dfb5db652360 https://github.com/golang/go/commit/42b42f71cf8f5956c09e6623...

selljamhere 8y ago

Is there anyone who can ELI5 what `beta8.Mod(beta8, curve.P)` does?

guessmyname 8y ago
I cannot ELI5 this for you, but here’s more context: beta8 := new(big.Int).Lsh(beta, 3) beta8.Mod(beta8, curve.P) https://golang.org/pkg/math/big/#Int.Mod https://golang.org/pkg/math/big/#Int.Mod
lifthrasiir 8y ago
It is hard to explain what is `beta8` and `curve.P` specifically, but they are arbitrary-precision integers so you can see what went wrong with an appropriate pseudocode: x3 = alpha * alpha beta8 = beta << 3 // beta8 %= curve.P x3 -= beta8 while x3 < 0 { x3 += curve.P } Essentially we want to compute `(alpha * alpha - beta * 8) % curve.P`, so to say. The modulo is expensive though, so for typical cases we can just repeatedly add `curve.P` to compute the modulo a few times. This is indeed a valid optimization when we are sure of the range of `alpha` and `beta`, but `beta` can be controlled outside. So a very large `beta` from an attacker will cause the while loop run forever---a denial-of-service attack.
- Thorrez 8y ago
  Here's the new code: beta8.Mod(beta8, curve.P) x3.Sub(x3, beta8) if x3.Sign() == -1 { x3.Add(x3, curve.P) } x3.Mod(x3, curve.P) I don't understand it why it's all necessary. This is shorter and seems to do the exact same thing: beta8.Mod(beta8, curve.P) x3.Sub(x3, beta8) x3.Mod(x3, curve.P) Also, beta8 is never used after this code. So this should do the same thing as well: x3.Sub(x3, beta8) x3.Mod(x3, curve.P)
  - lifthrasiir 8y ago
    I think you are right. Go `big.Mod` should be Euclidean (i.e. `x % y` follows `y`'s sign) so the code is redundant. It doesn't seem to be required to run in constant time (if so we won't have `if` at all), probably the committer wanted a minimal change?