Python implementation is not constant time

[bwesterb]

The __ctverify does not run in constant time as Python ignores the second argument to and if the first is False.

Easily verified with

def __ctverify(a,b):
    r = True
    for i in range(len(a)):
        r = r and (a[i] == b[i])
    return r

a = [0]*1000000
b = list(a)
b[0] = 1

import time

start = time.time()
__ctverify(a,b)
print (time.time() - start)

start = time.time()
__ctverify(a,a)
print (time.time() - start)

[dstebila]

Hi Bas, yes you're right, that should be fixed.

I think the following code using bitwise operations on integers should mostly do it, assuming that Python does not short-circuit any bitwise operations (I can't tell if that's the case from their documentation). I'm not sure if it's necessary to do something more in the final r == 0 test to ensure constant-time.

def __ctverify2(a,b):
    r = 0
    for i in range(len(a)):
        r = r | (a[i] ^ b[i])
    return r == 0

[bwesterb]

It's a bit complicated. Depending on PYLONG_BITS_IN_DIGIT, Python3 represents its ints radix 15 or 31. See include/longintrepr.h. Timing of the operations thus depends on how many limbs are required for the numbers. We might think that we're safe with radix 31 as Frodo's 16 bit number fit easily, but unfortunately the number zero uses zero limbs. Hence 0 | b is noticeably faster than 1 | b. There are probably more subtle pitfalls.

[dstebila]

Hmmm... the fact that 0 uses 0 limbs would mean code elsewhere in the Frodo python codebase would not be constant-time. (Which I would say is out of scope of this Python implementation, the purpose of which is to provide an easy-to-read implementation that closely matches the FrodoKEM spec pseudocode. Although I guess one could make everything a ctypes.c_uint16?)

If we're staying with Python int's, then one could try to convert them to bytes or strings and then iterate through the bits/characters of that string to manually do the equality test, but I'd worry that there could be some hidden problems in that conversion to bytes or strings...

I wonder whether it is possible to do a convincingly constant time implementation in Python at all...

[bwesterb]

Yeah, I think it's quite hard using pure Python. And Python's behaviour might change as well (in Python2 there is a separate type for small integers, which didn't have this 0 case.)

[bwesterb]

Indeed, I'd say the primary goal of the Python implementation is to be readable. Trying to make it constant-time will hinder that goal. It would be good to add a big fat disclaimer as there are actually use cases for pure Python implementations in production (appengine, pypy.)

[dstebila]

Okay, I've added a warning to the README as well as a warning that is printed out every time the code is run. I also did replace the ctverify with the slightly better (but still not perfect) version above. See PR #20.

[sopmacF]

what about splitting the logical step?
like:

def __ctverify(a,b):
    r = True
    for i in range(len(a)):
        r1 = (a[i] == b[i])
        r = r and r1
    return r

[bwesterb]

Equality does not run in constant time as comparing zero against zero is faster than 1 against 1 as there is one less limb to check.

[dstebila]

Just noticed that the pyca/cryptography module we're using has a constant-time equality check, but only for bytes; we're comparing arrays of int's. We could convert the arrays of int's back to bytes (by running the FrodoKEM pack operation), but that could again be burying a timing leak.

[bwesterb]

It uses Python's own hmac.compare_digest. The big issue is that constant-time arithmetic in Python is hard.