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

Fast constant-time GCD algorithm and modular inversion

gcd.cr.yp.to

Post reply on HN
Print view View original

1–10 of 84 posts

Re: Fast constant-time GCD algorithm and modular inversion

#3

Post by waterhouse »

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out.

To illustrate the kind of thing it's talking about, consider the naive algorithm for computing a^n via exponentiation by squaring:

  total = 1
  while n > 0:
    if n is odd:
      total = total*a
      n = n-1
    a = a*a
    n = n/2
  return total
If n has k bits, and j of them are 1s, then there will be k-1 squarings of a, and j multiplications of total by a. An attacker who can measure the total time may be able to at least figure out the number of 1 bits in n. If they can get fine-grained observations of power draw or something, then they might even be able to tell which bits are 1.

Consider this alternative:

  total = 1
  while n > 0:
    maybe_total = total * a
    if n is odd:
      total = maybe_total
    a = a * a
    n = n >> 1
  return total
This will do the same number of multiplications, if you can convince the compiler to not do any optimizations. Note that it still has a branch, though, which might conceivably be detectable. To plug that hole, something like this might work:

  # if n is odd:
  #   total = maybe_total
  # becomes this:
    low_bit = n & 1 # i.e. 0 or 1 if n is odd or even
    mask = low_bit - 1 # i.e. "all 1s" or 0 respectively
    total = (total & mask) | (maybe_total & ~mask)

Re: Fast constant-time GCD algorithm and modular inversion

#5

Post by bpp »

waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

Thanks for clarifying – really changes the connotation of the headline.

Re: Fast constant-time GCD algorithm and modular inversion

#6

Post by mehrdadn »

waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...

Re: Fast constant-time GCD algorithm and modular inversion

#9

Post by johncolanduoni »

b-3-n wrote: post #7

I was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.

Unfortunately the terms fundamentally overlap (even constant time equality is not constant as a function of input size).

Re: Fast constant-time GCD algorithm and modular inversion

#10

Post by waterhouse »

mehrdadn wrote: post #6
waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...

I have the same feeling... https://en.wikipedia.org/wiki/Side-channel_attack#Countermea... mentions "isochronous" operations.
Post reply on HN