Time-invariant equality in assembly

For crypto code it's important that it's time-invariant, otherwise it is vulnerable to timing attacks. I've had to build this time-invariant equality test from scratch, because I couldn't find something on Google. I hope it's useful to someone else.

;
; Linear time equality
;
; Author: Thom Wiggers
;

; based on this C code:

; int equals (int a, int b) {
;   unsigned long long t = a ^ b;
;   return 1-((-t) >> 63);
; }

; stores result in first argument
.macro linear_equals ; register A, register B
EOR @0, @1
NEG @0
BRVS skiplinearequalsoverflow ; I don't know how else to take care of the overflow.
  ROR @0 ; if this is just one operation, it still is time-invariant.
skiplinearequalsoverflow:
LSR @0
LSR @0
LSR @0
LSR @0
LSR @0
LSR @0
LSR @0
NEG @0
inc @0
.endm


.exit
;; everything here isn't executed
;; This test proves that the above code works.
TEST:
mov r2, r16
mov r3, r17
linear_equals r2, r3
BREQ skipnop
  CP r16, r17 ; check if it's indeed equal
  BREQ skipnop
  nop ; for breakpoints
  inc r15 ; amount of mistakes
skipnop:
inc r16
CPI r16, 0xFF
BRNE skipinc ; j + 1, i = 0
  inc r17
  clr r16
skipinc:
CPI r17, 0xFF
BRNE skipbreak ; done
  break
skipbreak:
rjmp test
Avatar
Thom Wiggers
PhD candidate