Constant time functions are needed in cryptography software to prevent attacks based on time measuring of the operations.
Constant time functions are needed in cryptography software to prevent attacks based on time measuring of the operations.
Questions tagged [constant-time]
27 questions
25
votes
4 answers
Near constant time rotate that does not violate the standards
I'm having a heck of a time trying to come up with a constant time rotate that does not violate the C/C++ standards.
The problem is the edge/corner cases, where operations are called out in algorithms and those algorithms cannot be changed. For…
jww
- 97,681
- 90
- 411
- 885
21
votes
3 answers
Does memory dependence speculation prevent BN_consttime_swap from being constant-time?
Context
The function BN_consttime_swap in OpenSSL is a thing of beauty. In this snippet, condition has been computed as 0 or (BN_ULONG)-1:
#define BN_CONSTTIME_SWAP(ind) \
do { \
t = (a->d[ind] ^ b->d[ind]) & condition; \
…
Pascal Cuoq
- 79,187
- 7
- 161
- 281
7
votes
1 answer
What is the time complexity of Java's ArrayList.sublist(startIndex, endIndex) method?
The question basically says it all. Suppose I have a (sorted) list that can contain anywhere from 1K to 1M items. I have a starting index and an ending index. If I use the ArrayList.sublist(start, end) method, is the time complexity O(n) or O(1)? I…
Grace F.
- 73
- 1
- 3
7
votes
5 answers
Fast constant time evaluation of "x==7" to 1 (true) or 0 (false) in Java
I want to port a crypto function from C to Java. The function has to run in constant time, so no conditional branchings (and no table lookups based on x) are allowed.
The original C code is:
int x,result;
...
result = (x==7);
...
So that 'result'…
Chris
- 187
- 7
5
votes
2 answers
Is JavaScript switch statement linear or constant time?
I have the following JavaScript on my site so that when certain specific searches are performed, the answer is hardcoded to a specific page:
function redirect() {
var input = document.getElementById('searchBox').value.toLowerCase();
switch…
WilliamKF
- 41,123
- 68
- 193
- 295
5
votes
2 answers
Is masking effective for thwarting side channel attacks?
I'm working with some bigint public-key cryptography code. Is it safe to use bitwise masking to ensure that the calculation timing and memory addresses accessed are independent of the data values?
Is this technique vulnerable to side-channel attacks…
Nayuki
- 17,911
- 6
- 53
- 80
3
votes
1 answer
LFU cache, how is get and set in O(1)?
Preparing for interviews and I came across something that is making me question my understanding of big O constant time algorithms.
A question on LeetCode asks to create a solution to the LFU cache problem.
There are 3 methods to…
Jimbo
- 1,685
- 3
- 12
- 15
2
votes
1 answer
Algorithm to find numerical bucket in dynamic list
Say I have input that looks something like this:
[
{index: 0, probability: 0.20},
{index: 1, probability: 0.10},
{index: 2, probability: 0.40},
{index: 3, probability: 0.25},
{index: 4, probability: 0.05},
]
Given that I generate a random…
Alexander Mills
- 90,741
- 139
- 482
- 817
2
votes
3 answers
Create array structure in JavaScript that omits indexing
Indexing (maintaining indices) in an array makes Array.prototype.shift and Array.prototype.unshift O(N) instead of O(1).
However, if we just want to use pop() / push() / shift() and unshift() and never use indices for lookup, is there a way to…
Alexander Mills
- 90,741
- 139
- 482
- 817
1
vote
0 answers
Compare two integers with bitwise operation
I saw a bunch of codes which can do simple arithmetic operations in constant-time.
But there is a code makes me curious.
Here is a code written in C.
int ct_lt_u32(uint32_t x, uint32_t y){
return (x^((x^y)|((x-y)^y)))>>31;
}
This function…
Serenity
- 23
- 2
1
vote
2 answers
Why do we need to add a "sleep" method to make a constant time attack succeed?
In this website: http://elijahcaine.me/remote-timing-attacks/ the author describes well what is a constant time attack and how to protect against this type of vulnerability.
But in the code that the author have done:
# secret.py
from time import…
Segfault
- 23
- 1
- 6
1
vote
1 answer
Why does the hash() function in python take constant time to operate on strings of variable length?
From the run time of programs including the hash() operation on variable length strings I felt that it might be that the hash() function takes constant time to operate on different length strings. To verify my assumption I made the following…
Anirban Chakraborty
- 539
- 1
- 5
- 15
1
vote
2 answers
Efficient circular buffer with constant-time access
In a machine learning project written in python, I need an efficient circular buffer like collections.deque but with constant-time access to any element like numpy.array. The problem is that deque is apparently a linked list. Is there something…
Yann Bouteiller
- 47
- 7
1
vote
1 answer
Python Error: ModuleNotFoundError: No module named 'cryptography.hazmat.bindings._constant_time'
I'm trying to run a script that I've been able to run in the past. It stops with error:
ModuleNotFoundError: No module named 'cryptography.hazmat.bindings._constant_time'
I recently removed python 3.6 and installed python ActiveState:
ActivePython…
Justin Thompson
- 41
- 1
- 5
1
vote
1 answer
Constant-time string comparison function
To compare two strings, I currently use strcmp or one of its variants. However, because strcmp take longer if more characters match, it is vulnerable to timing attacks. Is there a constant-time string comparison function in the standard library on…
Sjoerd
- 74,049
- 16
- 131
- 175