3
$\begingroup$

I am interested in Elliptic Curve Cryptography and found algorithms for constant-time multiplication. Within these algorithms arithmetic operations must be performed (like addition and multiplication).

I have two questions about these 'internal' arithmetic operations:

  • these 'internal' operations must be performed in constant-time, too, right? Then I guess the precision of all intermediate variables must be the same. But what precision is necessary here (e.g. if I multiply two 256 bit numbers, I need 512 bits for the result, I guess).

  • What are good algorithms for performing these 'internal' arithmetic operations in constant time?

Improve this question
$\endgroup$
2
$\begingroup$

You can have additions and multiplications take constant time on a hardware level; however, the multiply units generally take 4 cycles due to the array multiplier design for a 32-bit width, at 64-bit on Intel, it's 6 cycles. The division will always be iterative, which is the problem.

Here's an example of a routine that I have for adding two 256 numbers in constant time on my i7 (note, these times will be different for different cores):

add256:
        xorl      %r9d, %r9d         # 1 cycle                             
        movq      (%rsi), %rax       # 1 cycle                          
        addq      %rax, (%rdi)       # 1 cycle                        
        movq      8(%rsi), %rdx      # 1 cycle                         
        adcq      %rdx, 8(%rdi)      # 1 cycle                           
        movq      16(%rsi), %rcx     # 1 cycle                           
        adcq      %rcx, 16(%rdi)     # 1 cycle                         
        movq      24(%rsi), %r8      # 1 cycle                          
        adcq      %r8, 24(%rdi)      # 1 cycle
        setb      %r9b               # 1 cycle                           
        ret                          # 1 cycle

You are not going to get true constant time unless you are in assembly. I believe that the best way to get constant time would be to just figure out the maximum it time it takes to do a calculation, and then pad intermediate cycles with junk because the ADD and MUL will take different times.

The thing that will hurt you the most is the division that is iterative, as that takes an arbitrary amount of cycles.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ can you formally prove it is constant time ? $\endgroup$ – Biv Aug 31 '16 at 15:25
  • $\begingroup$ @Biv just to make sure I understand what you want here: Can I prove relative to cycles that the addition always takes the same amount of cycle time? I'm more of a hardware person, so that is the definition of constant time for us, I'm recently learning all of the lingo and assumptions of the cryptography community. $\endgroup$ – b degnan Aug 31 '16 at 15:55
  • $\begingroup$ Technically it is a bit more that proving the number of cycles what ever the branch but yes you have the idea. Also you might want to remember that most of common people don't read assembly (and me neither...) $\endgroup$ – Biv Aug 31 '16 at 15:57
  • $\begingroup$ @Biv I added the cycle times. That routine was written in such a way that everything took one cycle. This was from what I was initially playing with once I started making my own ECC hardware. I actually have a more complicated implementation where all of the math for the ECC curve in the form of $$y^2 = ax^3 + bx^2+cx mod P$$ works out for some of the common curves. The issues is always division, but in hardware I made a 1/x divider circuit and then you do a multiply so it's 4 cycles for the 1/x and then 4 for the array multiply $\endgroup$ – b degnan Aug 31 '16 at 16:15
  • 1
    $\begingroup$ Actually, I would disagree that you MUST use assembly language to do constant time programming; for example, the C code 'a = b + c;' is likely to compile into code that is constant time. Yes, you're trusting the compiler, but (most) compilers won't go out of their way to thwart you. Doing bignum math efficiently and in constant time in C is difficult; most other operations translate naturally... $\endgroup$ – poncho Aug 31 '16 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.