[HN Gopher] Constant-Time Big Numbers: An Introduction
       ___________________________________________________________________
        
       Constant-Time Big Numbers: An Introduction
        
       Author : gbrown_
       Score  : 46 points
       Date   : 2021-05-21 12:05 UTC (1 days ago)
        
 (HTM) web link (cronokirby.com)
 (TXT) w3m dump (cronokirby.com)
        
       | bob1029 wrote:
       | > Because of this, adding in timing noise can only act as a
       | mitigation, and not a particularly effective one at that.
       | 
       | I think the author is thinking in terms of X << t for purposes of
       | adding random delay. If you flip this around, you get the
       | opposite conclusion. For instance,                 Crypto
       | operation actual: 10uS       Random delay: 100-1000ms
       | 
       | In this arrangement, the amount of time the actual cryptographic
       | operation takes to complete falls under the noise floor.
       | 
       | Isn't this essentially a big part of why PBKDF2 and friends are
       | good at hashing passwords?
        
         | cronokirby wrote:
         | Author here.
         | 
         | To illustrate my point further, let's say that your operation
         | takes either 0.1ms or 0.0ms.
         | 
         | If you add in a uniform random delay of 100-1000ms, your
         | expected random delay becomes 450ms.
         | 
         | The expected total runtime is thus either 450.1ms or 450.0ms.
         | If you have a way to calculate this expected value with enough
         | precision, you can completely recover the timing signal.
         | 
         | The amount of noise you inject can only make recovering the
         | signal harder, not impossible. I also believe that the
         | difficulty is only polynomial in the amount of noise, which
         | limits the effectiveness of this strategy.
         | 
         | The reason why password hashes like PBKDF2 try and make the
         | operation take longer is for a different reason, as far as I
         | know. If you try and crack a password's hash by trying many
         | different common passwords, until you can find a match, then it
         | helps your attack if calculating a hash is very fast. Password
         | hashes intentionally try and make calculating hashes more
         | expensive, both in time, but also in memory consumption (in
         | Argon2, for example), to limit the effectiveness of this
         | attack.
        
           | ghusbands wrote:
           | This is a good place to ask without a top-level comment: Do
           | people really tend to do it that way? Whenever I've
           | considered using sleep to mitigate timing attacks, it has
           | been to sleep an amount of time that makes the resultant time
           | constant. That is, to make the operation in this case always
           | take 450ms.
        
             | cronokirby wrote:
             | Sleeping just long enough to fill the remaining time-slot
             | for an operation is actually a valid countermeasure; in
             | theory.
             | 
             | The problem is figuring out how much sleep is necessary
             | based on what variable time work has been done, and
             | actually sleeping the right amount. This can be difficult
             | with the granularity involved.
             | 
             | In practice, attempting to fill the remaining time is
             | either not effective, or requires a level of
             | instrumentation that severely degrades performances.
             | 
             | I'd recommend section 5 of
             | https://eprint.iacr.org/2016/613.pdf for a survey of these
             | ideas.
        
       | moasda wrote:
       | From article:
       | 
       | The key here is to understand that by constant-time, we don't
       | mean that operations can't take a varying amount of time.
       | Instead, we mean that the timing signal generated by our
       | operations doesn't leak any secret information.
        
         | codeflo wrote:
         | It's very unfortunate that the crypto-community uses the term
         | "constant-time" this way. Without further context, I thought of
         | algorithmic complexity, where "constant time" means " _bounded_
         | by a constant" -- which doesn't guarantee resistance to timing
         | attacks at all!
         | 
         | So if you're looking for a crypto algorithm, make sure it's
         | constant-time in the relevant sense.
        
           | dataflow wrote:
           | Yeah I wish people would say uniform-time instead.
        
           | moasda wrote:
           | Exactly, that was my assumption, too. I was wondering how
           | they could handle big numbers in algorithmic time complexity
           | O(1).
        
       | stephenbuilds wrote:
       | Just wanted to congratulate the author on a beautifully
       | structured and penned article. It's not a topic that is directly
       | related to my work, but I still enjoyed it and learned from it.
        
         | aaronAgain wrote:
         | And I wanted to concur with this. A great description of
         | complicated topic. Just enough information in each section to
         | get you ready for the next, nothing extra. Well done.
        
       | nickcw wrote:
       | > This means representing numbers in base 2^{m} where m is your
       | register width). With components this big, we usually call these
       | "limbs": wordplay on "digits", of course.
       | 
       | I never realised limbs was wordplay on digits. Duh!
        
       ___________________________________________________________________
       (page generated 2021-05-22 23:02 UTC)