Fast constant-time GCD algorithm and modular inversion

https://gcd.cr.yp.to/papers.html

by MrXOR • 7 years ago

124 81 7 years ago

gcd.cr.yp.to

londons_explore• 7 years ago

Isn't constant time GCD a problem for factoring big primes?

xxs• 7 years ago

By the 1st look: the algorithm is just free from side channel attacks.

nullc• 7 years ago

I have an O(N) algorithm for factoring any prime: Read each digit of the prime from the input tape and write it to the output tape. :P

(Perhaps you meant factoring large semi-primes? :) )

hoseja2• 7 years ago

I have an O(1) then!

ColinWright2• 7 years ago

Assuming you mean factoring large number, specifically semi-primes with broadly similar sized factors and no assumed structure, the answer is still no. Taking N as the number being factored and C a candidate that might contain a factor, taking GCD(N,C) is not a significant part of the process. The large part of the process is usually finding C.

And the article isn't claiming that the GCD code here takes the same time regardless of the input, it's saying that for two inputs of the same size the time take is the same. Time as a function of the input size is still proportional to the number of bits in the input, it's just that the routine takes the same time regardless of how many of those bits are 0, regardless of the structure of the input numbers.

========

To others commenting here, the guidelines[0] say:

Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith.

[0] https://news.ycombinator.com/newsguidelines.html

waterhouse3• 7 years ago

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)

bpp• 7 years ago

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

mehrdadn3• 7 years ago

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

waterhouse3• 7 years ago

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

moron4hire2• 7 years ago

Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.

hannob• 7 years ago

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 seems very obvious to me. "Constant" independent of the input size seems literally impossible for any nontrivial algorithm. At the very least you need to somehow read in all the input, and that's already input-size dependent.

arghwhat7• 7 years ago

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1).

A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator:

The most normal, and fastest, approach is to go through data in the largest chunks the CPU can handle, returning 1 immediately a mismatch is found, and 0 at the end under the assumption that no termination = no mismatch. However, this reveals information about the values compared, as the time it takes to compare reveals where the mismatch is located.

For constant time, your goal is to ensure that all data is processed equally regardless of outcome. You do this by effectively making the comparison a-b=c, or a^b=c, where a zero-result means equality. In reality, this would be implemented by XOR'ing the largest chunk the CPU can handle together, and then OR'ing the result with a global value starting at 0, overwriting it. This continues without termination to the very end, where you then simply return the running OR'd counter, which is either 0 for equality, or an arbitrary value for the opposite.

Both of course leak the length of the values compared, but the lengths in these cases are commonly known by the adversary, making its protection less relevant.

caf3• 7 years ago

This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1).

It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).

twic• 7 years ago

This is standard terminology within programming and cryptography

Within cryptography, yes, but in programming in general, absolutely not.

The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.

contravariant• 7 years ago

It might be standard notation, but not only is O(1) misleading as it misrepresents the dependency on the problem size, it is also the wrong symbol as it hides the exact thing it's trying to convey.

throwawaymath14• 7 years ago

A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator:

This is incorrect. The paper explicitly uses "constant time" in the sense of O(1). You can see this listed throughout the paper, in various complexity analyses, beginning from Section 2.

davemp• 7 years ago

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1).

How about 'consistent time' or 'uniform time' for non-O(1) uses?

tomglynch• 7 years ago

This is more of an issue with our definition of 'constant time' rather than a problem with the description. Though I can't think of a better term to rename constant time. Any proposals?

throwawaymath14• 7 years ago

This is incorrect. Refer to Section 2, "Organization of the paper":

We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).

What the authors are doing is (in the simplest sense) adding a worst case O(1) component to the GCD algorithm in the exponent. This is fundamentally a complexity theory paper, and Bernstern and Yang are using "constant time" in the complexity theoretic sense.

Moreover this is not about clever implementation; the algorithm they present will explicitly not take the same amount of time regardless of the input. In line with the presented complexity analysis throughout the paper, the worst case running time is asymptotically bounded independently of inputs n and c.

gjm114• 7 years ago

The authors are not using "constant time" in the complexity-theoretic sense. That would mean an algorithm whose running time doesn't depend on n,c.

The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies.

The nice properties they claim for their algorithm are:

1. The asymptotic running time is good. This is a complexity-theoretic claim. The asymptotic performance is of the same order as e.g. Schoenhage's earlier algorithm, so this isn't in itself any sort of breakthrough.

2. For fixed input size, the running time is constant. This is a cryptographic claim: it gives immunity to timing attacks. There have been earlier constant-time GCD and modular inverse algorithms, so again this on its own isn't any sort of breakthrough.

It isn't clear to me whether 1+2 is claimed to be new. I think it isn't: that is, there are other constant-time GCD algorithms with the same asymptotic growth of runtime.

3. The constant factors are good. This is a matter of the practicality of the algorithm. Here the authors are claiming to have done better than anyone before them.

b-3-n• 7 years ago

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

johncolanduoni• 7 years ago

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

minitech2• 7 years ago

It’s not click bait. It’s standard terminology.

OskarS• 7 years ago

To clarify: it's not "constant time" in the sense of having O(1) time complexity with regards to the size of the inputs, which is what most people mean by "constant time" (which is obviously not possible in this case: there's never going to be a GCD algorithm that can work as fast on 100-bit integers as on 1,000,000,000-bit integers).

It's "constant time" in the cryptographic sense, that the time to run it can't be used as a side-channel to figure out what the inputs are. A great result to be sure, but the terminology is undoubtedly confusing.

xurukefi• 7 years ago

I disagree. "Constant time" means O(1), which this isn't.

kmill2• 7 years ago

One might argue that calling O(1) just "constant time" in asymptotic complexity theory is click bait itself! Calling O(1) bounded time would have been better terminology, in my mathematical opinion.

Sometimes people actually count individual operations to form a function T(n) depending on the input n (see, for example, Knuth's books). If T(n) is the constant function, then the algorithm takes constant time in a much more literal sense.

(The "constant time" terminology bugged me when I first learned about computational complexity.)

Edit: It seems "constant time" in this paper might actually mean "the running time is uncorrelated with the precise secret value, only its size."

ComputerGuru• 7 years ago

I presume you came across this researching the zero-day DoS in Windows 10 (and others?) caused by an infinite loop in Microsoft's modular inversion code? Thanks for sharing!

AnaniasAnanas• 7 years ago

OP probably saw DJBs tweet https://twitter.com/hashbreaker/status/1139008213570007040

throwawaymath14• 7 years ago

It's pretty frustrating to see the discussion on this submission dominated by people litigating the "constant time" terminology. The authors, Bernstein and Yang, are using constant time in the conventional, complexity theoretic sense of the word. Here is a quote from Section 2, "Organization of this paper":

We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).

In particular note that last sentence. The asymptotic runtime of the presented algorithm does not depend on the inputs, n and c. This algorithm analysis is confirmed throughout the remainder of the paper, which walks through each stage of the algorithm. Now let's look at a few canonical definitions of "constant time", i.e. O(1).

From Skiena, we have:

Constant functions - f(n) = 1 - Such functions might measure the cost of adding two numbers, printing out the "Star Spangled Banner", or the growth realized by functions such as f(n) = min(n, 100). In the big picture, there is no dependence on the parameter n.

Likewise from Sedgewick & Wayne:

Constant. A program whose running time's order of growth is constant executes a fixed number of operations to finish its job; consequently its running time does not depend on N. Most Java operations take constant time.

I'll update if I find a choice example from Knuth in TAOCP, but I think this suffices. The discussion about whether or not the cryptographic use of the term satisfies the complexity theoretic sense of the term is a red herring; it's a distinction without a difference. Algorithm analysis focuses on asymptotic behavior, which is definitionally given by tail behavior, or rate of growth of a function. Among other things, this paper is not about an implementation methodology that ensures the GCD algorithm will take exactly the same amount of time regardless of the input.

______________________

1. The Algorithm Design Manual, 2nd Edition, § 2.3.1 Dominance Relations, Page 39

2. Algorithms, 4th Edition, § 1.4 Analysis of Algorithms, Page 187

ziedaniel1• 7 years ago

I think you misread slightly.

All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).

This means that once you have chosen a particular n and c, the time no longer varies. However, if n and c vary, the running time is definitely allowed to vary also (as the formulas n(c + n) and (c + n)(log cn)^2+o(1) clearly do).

throwawaymath14• 7 years ago

No, I didn't misread. You and I are in (apparently violent) agreement. Constant time does not mean that running time cannot vary, in either complexity theory or cryptography. There are misconceptions on both sides here, with regard to what the terminology means in both complexity theory and cryptography.

For precision, I'll start with a good definition[1] for what "constant time" means in cryptography:

Constant-time implementations are pieces of code that do not leak secret information through timing analysis. This is one of the two main ways to defeat timing attacks: since such attacks exploit differences in execution time that depend on secret elements, make it so that execution time does not depend on secret elements. Or, more precisely, that variations in execution time are not correlated with secret elements: execution time may still vary, but not in a way that can be traced back to any kind of value that you wish to keep secret, in particular (but not only) cryptographic keys.

Secure, constant time cryptographic algorithms need not have unvarying execution time. Now going back to complexity theory, it is also an extraordinarily common misconception that "constant time" means "the algorithm has the same execution time regardless of the size of the input." This is not the case. Big O notation doesn't even care about what always happens, it cares about what happens in the worst case. When we use "constant time" in the O(1) sense of the word, we are not precluding the possibility of an algorithm having variable execution time. Again, for precision, we are simply saying that the execution time (number of operations, etc) has an asymptotic upper bound which is independent of the input. The execution time may vary with the input, and generally speaking it will.

_________________________

1. Thomas Pornin, Why constant time crypto? https://bearssl.org/constanttime.html

amelius• 7 years ago

The confusion is that the word-size of the operands plays a role.

For example, some people would say that an operation like a⨯b takes constant time or that its time complexity is O(1). However, other people (for example those implementing a bignum library) would say that the operation takes time depending on the word size of the operands. In the case of the multiplication operation, see for example [1] for a complexity analysis, to get an idea of what I mean.

[1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...

svat2• 7 years ago

The definition of “constant time” in computational complexity theory is O(1) time as a function of the input size n, i.e., the time taken for an input of size n is bounded by some constant regardless of n. This is clear even from the two quotes you picked, from Skiena and from Sedgewick: both say that the running time does not depend on the input size n.

What we have here in the cryptography sense is different: the running time n(c+n) clearly does depend on n; it just does not depend on the actual input. That is, it is only constant across inputs of the same size.

I am not sure how you're claiming that n(c+n) is O(1) when it's clearly Θ(n^2) (i.e. O(n^2) and Ω(n^2)).

throwawaymath14• 7 years ago

What we have here in the cryptography sense is different: the running time n(c+n) clearly does depend on n; it just does not depend on the actual input.

Can you explain to me what the input is, if not c and n?

kmill2• 7 years ago

Among other things, this paper is not about an implementation methodology that ensures the GCD algorithm will take exactly the same amount of time regardless of the input.

The introduction to the paper talks about the importance of developing constant-time implementations of Euler's algorithm to avoid timing attacks, pointing out how algorithms with conditional jumps are susceptible to, for example, cache timing attacks.

As far as I understand it, a constant time algorithm, in the cryptographic sense, is one whose running time is uncorrelated with the precise secret information. If it were correlated, then timing attacks would let you infer the secret information. Presumably, if there is no random model, then the definition is that the algorithm must run in the exact same amount of time no matter the input, assuming a fixed size for the inputs. (At least one of the cited papers agrees with this definition.)

The contribution of the paper is a constant time divstep algorithm. The quote "All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c)" seems to have ambiguous quantifiers and should be rewritten. It should be something like "given a fixed number of iterations n and a fixed number of input power series coefficients c, our divstep takes a constant n(c + n) simple operations, and the algorithm is constant time, i.e., the running time is not correlated with the precise inputs." Section 1.1 gives exact cycle counts for various CPUs.

Section 7 discusses how to use bit masking to actually implement it in a constant time way (in the cryptographic sense).

Anyway, divstepsx is certainly not O(1) time unless n and t are fixed constants.

pierrebai• 7 years ago

I would suggest that you take the time to reflect on the fact that if almost everyone disagree with you, it might point to something that you misunderstand. Either about the meaning of what they say or your understanding of the subject.

Their paper shows that the algorithm takes a constant time to compute the Cth coef. of the Nth step, for a given C and N. Not that the algorithm time is independent of C and N. C and N are not the input of the GCD. The algorithm running time is constant for the input of the GCD. It is dependent on C and N.

esjeon2• 7 years ago

If I understood correctly, this paper is NOT about a new blazing fast security-breaking CS-history-changing algorithm. This paper suggests an algorithm that takes the same amount of time to compute GCD(6, 9) and GCD(123456789, 987654321), to prevent leaking hints on its inputs through side-channels. That is, this thing is basically less efficient, but still runs the same number of instructions no matter the input.

(EDIT: ... as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm.)

The paper do mention this:

However, in cryptography, these algorithms are dangerous. The central problem is that these algorithms have conditional branches that depend on the inputs. Often these inputs are secret, and the branches leak information to the attacker through cache timing, branch timing, etc.

So, yeah, this is security-centered cryptography paper. The term "constant-time" is used in a different context here.

throwawaymath14• 7 years ago

The term "constant-time" is used in the complexity theoretic sense. Can you explain to me, concretely, how what you've said here

as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm

indicates the algorithm is constant-time in one sense but not the other?

esjeon2• 7 years ago

The main difference here is the goal. "O(1)" algorithm often means efficient algorithm out there in the field, but this paper has absolutely no intention of making anything efficient.

People are wrong with that (1) O(1)=fast/efficient (2) I'm arguing over the definition of "constant-time".

waterhouse3• 7 years ago

The problem is: "Constant—with respect to what?" "Remains constant under what conditions?" The function f(x,y) = x^2 is constant under varying y, and is not constant under varying x. The adjective "constant", by itself, is incomplete—unless it's truly a mathematical constant, like 2 or e, that depends on nothing else—which is what leads people to the "O(1)" interpretation of the phrase "constant time".

So if it's not used to mean "constant (no matter what you vary)", then it means "constant (if you vary certain parameters and I'm not specifying which ones)". When you use a phrase with something left out and implied, then the audience has to fill it in somehow. If the audience shares your background, perhaps has been reading similar papers recently in which "constant with respect to xyz" had the xyz spelled out explicitly, this may go well; if not, it may not. In this case, people's interpretations of "the xyz we're varying" appear to range over "the entire space of integer-tuple inputs", "the size of the integers", "the bits of the integers after the leading 1", "the parts of the inputs that are considered 'secret'", and more.

So, if you say something with an implicit part left unspecified, and people fill it in with something different than what you intended... the first time this happens, I might consider it an unfortunate accident. If it happens repeatedly, it may be worth being more explicit or choosing another term. (Suggested terms: "secret-hiding", "secret-blind". "[something]-oblivious" might be another good word-formation—precedent exists in "cache-oblivious" algorithms.)

This is not the worst terminological mess we have in CS[1].

[1] My (least) favorite example is the term "dynamic programming", whose name appears to have been chosen because it sounded good and was vague enough to cover what the author wanted: "Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." https://en.wikipedia.org/wiki/Dynamic_programming#History

Fast constant-time GCD algorithm and modular inversion

Related Stories