GiacomoPope / kyber-py

A pure python implementation of ML-KEM (FIPS 203) and CRYSTALS-Kyber
MIT License
201 stars 47 forks source link

add a "constant time" select for decaps #48

Closed GiacomoPope closed 3 months ago

GiacomoPope commented 3 months ago

Although the code is not meant to run in constant time, this conditional selection is key to the security of kyber and so is included for completeness

tomato42 commented 3 months ago

I'm pretty sure it's not constant time...

GiacomoPope commented 3 months ago

No, I don't think anything in python is constant time. But the old code had the branching:

if X:
    return Y
return Z

and I don't want someone to see this and think this is how you implement the decaps.

The change I made last night is a step towards the right version, which should use some condition (in C I would use uint32_t set to 0 or -1) to conditionally select all the bytes in the array (or do a conditional swap)

The idea is that we check whether decaps was successful to set this mask and then select between the two byte arrays.

tomato42 commented 3 months ago

I'm familiar with constant time programming :) I wrote https://github.com/tomato42/ctmpi while I worked on fixing https://people.redhat.com/~hkario/marvin/

GiacomoPope commented 3 months ago

Okay, then I'm not sure what your comment about was for? What about the function are you concerned about?

tomato42 commented 3 months ago

that this is not sufficient, and actually I think constant-time programming in python is impossible

if the purpose of this code is to show how it should look like if programmed in C, then actually it won't be sufficient either, as you need either assembly barriers or use of volatile for the mask variable (see ctmpi code)

so, I'd say it should have rather big disclaimer that this is attempting, but not really able to achieve a constant time operation

GiacomoPope commented 3 months ago

actually I think constant-time programming in python is impossible

I agree

rather big disclaimer that this is attempting, but not really able to achieve a constant time operation

The whole repo is wrapped under this disclaimer and the function purposefully doesn't say it's constant time.

as you need either assembly barriers or use of volatile for the mask variable

I'm not sure this is strictly true, as I would argue a better use-case is the lack of any bool types at all in C code and (at least at the time of writing) compilers seem to not cause issues when masks are made from (uint32_t)0 and (uint32_t)-1 from the more serious cryptographic projects im part of

Either way it seems the issue here is the PR name, which I did without thinking much and is probably better labelled as "add a 'constant time' select for decaps"

tomato42 commented 3 months ago

I'm not sure this is strictly true, as I would argue a better use-case is the lack of any bool types at all in C code and (at least at the time of writing) compilers seem to not cause issues when masks are made from (uint32_t)0 and (uint32_t)-1 from the more serious cryptographic projects im part of

that's not the results of my testing, we've just recently discovered that the libgcrypt code is vulnerable because it's not using volatile for the mask