16 ms·
Fast constant-time GCD algorithm and modular inversion
- londons_explore 7y agoIsn't constant time GCD a problem for factoring big primes?
- xxs 7y agoBy the 1st look: the algorithm is just free from side channel attacks.
- nullc 7y agoI 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? :) )
- hoseja 7y agoI have an O(1) then!
- ColinWright 7y agoGiven that you have to read and then write each digit of the input I find it hard to believe that you have an O(1) algorithm - can you tell us what it is?
- ColinWright 7y agoAssuming 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 https://news.ycombinator.com/newsguidelines.html
- waterhouse 7y agoIt 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 7y agoThanks for clarifying – really changes the connotation of the headline.
- mehrdadn 7y agoI'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...
- waterhouse 7y agoI have the same feeling... https://en.wikipedia.org/wiki/Side-channel_attack#Countermeasures https://en.wikipedia.org/wiki/Side-channel_attack#Countermea... mentions "isochronous" operations.
- b-3-n 7y agoI was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.
- johncolanduoni 7y agoUnfortunately the terms fundamentally overlap (even constant time equality is not constant as a function of input size).
- deleted 7y ago[deleted]
- minitech 7y agoIt’s not click bait. It’s standard terminology.
- OskarS 7y agoTo 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.
- nmadden 7y agoWith any algorithm complexity analysis you have to define what the inputs are considered to be. For cryptography, algorithms are designed to be constant-time with respect to the non-secret inputs. The secret inputs (which you are trying to protect) usually do not vary from one call to the next (eg, long-term private keys etc) - so can be assumed to be constant. So while the terminology seems confusing, it’s not actually different. It’s just a different choice of “input” compared to typical algorithm analysis.
- 7y ago
- ComputerGuru 7y agoI 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 7y agoOP probably saw DJBs tweet https://twitter.com/hashbreaker/status/1139008213570007040 https://twitter.com/hashbreaker/status/1139008213570007040
- throwawaymath 7y agoIt'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 7y agoI 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).
- esjeon 7y agoIf 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.
- throwawaymath 7y agoThe 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?
- esjeon 7y agoThe 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".
- waterhouse 7y agoThe 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 https://en.wikipedia.org/wiki/Dynamic_programming#History