Comments (10)
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.
from pqcrypto-lweke.
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
from pqcrypto-lweke.
It's a bit complicated. Depending on PYLONG_BITS_IN_DIGIT
, Python3 represents its int
s 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.
from pqcrypto-lweke.
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...
from pqcrypto-lweke.
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.)
from pqcrypto-lweke.
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.)
from pqcrypto-lweke.
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
from pqcrypto-lweke.
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.
from pqcrypto-lweke.
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.
from pqcrypto-lweke.
It uses Python's own hmac.compare_digest
. The big issue is that constant-time arithmetic in Python is hard.
from pqcrypto-lweke.
Related Issues (12)
- Unclear indexing in s HOT 2
- Measure of level of security HOT 3
- Unclear why PARAMS_NBAR has be a multiple of 8 HOT 1
- Undefined behavior in FAST_GENERIC implementation HOT 1
- round() makes a mistake HOT 1
- return value of randombytes() not checked HOT 1
- Use of /dev/random in random.c and quantum computing attacks HOT 1
- This repo is missing important files
- enable PQCrypto-LWEKE on s390x HOT 3
- Need clarification on working of Frodo.encode() HOT 1
- Building on MSYS2 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from pqcrypto-lweke.