Comments (2)
Unfortunately this is still susceptible to cache-timing attacks, like Percival: https://koclab.cs.ucsb.edu/teaching/cren/project/2010/gallegos.pdf
The data in Fp.C.sqrtDlog(dlogLUT)[65534]
would be read often and be hot in cache and so would result in timing differences compared to a "real" key.
Beyond timing differences, this would also result in different power draw or electromagnetic profile depending on the data taken, while on a PC it would be drowned in noise, this can be read on embedded devices like a Raspberry Pi or a Phone.
This technique is often called "double-and-always-add" using a dummy point in elliptic curve scalar multiplication and there is a lot of litterature on attacks it cannot prevent:
- Survey for Performance & Security Problems of Passive Side-channel Attacks Countermeasures in ECC
Rodrigo Abarúa, Claudio Valencia, and Julio López, 2019
https://eprint.iacr.org/2019/010 - State-of-the-art of secure ECC implementations:a survey on known side-channel attacks and countermeasures
Junfeng Fan,XuGuo, Elke De Mulder, Patrick Schaumont, Bart Preneel and Ingrid Verbauwhede, 2010
https://www.esat.kuleuven.be/cosic/publications/article-1461.pdf
In Aburúa, Valencia, López paper, 7 ways to defeat that approach are listed:
In general, to achieve constant-time property, the data access pattern MUST NOT depend on secret data. Hence you need to always access the whole table when dealing with lookup tables:
constantine/constantine/platforms/constant_time/ct_routines.nim
Lines 181 to 189 in 661a481
from constantine.
I came up with a quite simple solution to this issue, but I am not sure if its actually in constant time. While reading the code I came across a certain key value pair in the table (65534: 0). The problem was the time for accessing a value in a table with its key was not the same as returning 0. We can kind of avoid this issue with the following implementation:
func sqrtAlg_NegDlogInSmallDyadicSubgroup(x: Fp): int {.tags:[VarTime], raises: [KeyError].} =
let key = cast[int](x.mres.limbs[0] and SecretWord 0xFFFF)
if Fp.C.sqrtDlog(dlogLUT).hasKey(key):
return Fp.C.sqrtDlog(dlogLUT)[key]
else:
return Fp.C.sqrtDlog(dlogLUT)[65534]
Since in both the cases of the if
we are accessing a table element, it is supposed to be in constant time I think. So this might be a workaround for now.
from constantine.
Related Issues (20)
- EIP-2537: Potential memory leak in G1 and G2 MSM
- Followup: Go API for BLS signatures HOT 2
- MSM - optimized MSM wrong result in IPA verifier.
- Verkle IPA - Incomplete test suite - bugs in prover & verifier HOT 2
- Bug: Cubic extension conjugate
- Build failing on MacOS HOT 4
- Optimize MSM for Bandersnatch/wagon and Verkle Tries
- Optimize MSM for small scalars
- Verkle Trees: Faster subgroup checks for Banderwagon via vartime Legendre symbol
- Parallelize IPA for Verkle Trees
- Custom Vec/Seq with destructors HOT 1
- SIMD Vectorization - Use Integer Fused Multiply-Add (AVX512) HOT 2
- Per-curve towering
- LLVM/Nvidia GPU backend: LLVM 17 broke everything HOT 2
- Optimize batch verification for same message (Pippenger msm)
- Low-level: discrepancy between field arithmetic performance and elliptic curve performance HOT 4
- Windows: Secp256k1 tests assembly test frozen
- Oblivious Maps / side-channel secure hash tables
- Parallel MSM load balancing: minimize work per-thread
- [Fuzzing] Implement a Fp12 serializer to canonical serialization 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 constantine.