1
$\begingroup$

In my algorith execution time depends on the size of the key. It is a linear relationship (probably). The larger the key, the longer the algorithm takes to run. I have a code in Python so far.

For example for 3-bit round keys it runs 1 sec and for 128-bit round keys it runs 4 sec (for some number of inputs).

Is this a disqualifying problem?

PS By the way I will precise why it happens. There are simply additions and multiplications. It takes more time to multiply plaintext by bigger number, the same is with adding. What's more there are some equations to solve with euclidean algorithm, where we got for example to solve $2^{128} \cdot c - key^{64} \cdot k = 1$. I don't how $key$ size can affect time of solving that.

$\endgroup$
2
$\begingroup$

Execution time of my algorithm/code depends on the size of the key. Is this a disqualifying problem?

No, because the key size is not considered a secret.

But having execution time depend on the bit size of the integer coded by the key would be something different. It would be a problem, more or less minor depending on the size we are talking about and algorithm/key generation method. For example, in RSA, that's typically not a serious issue for any of the integers defining the private key $p$, $q$, $d$, $d_p$, $d_q$, $q_\text{inv}$, because it's so unlikely that the bit size of these integers is significantly reduced compared to its maximum; and regarding $p$ and $q$, their bit size as an integer is customarily fixed to exactly half the bit size of $n=p\,q$.

What could be a serious side-channel issue would be that execution time depends on some secret data, like the key value, or plaintext in an encryption algorithm. The worse is when execution time depends on a combination of the key value and varying information known or under control of adversaries (e.g. key and ciphertext; or key and hash of signed data). That's ideal ground for a side-channel attack. That could well be the case if multiplication time depends on the value multiplied. That's a common and hard-to-avoid issue, see this.

| improve this answer | |
$\endgroup$
  • $\begingroup$ As far as I know, execution time does not depend on the bit size of plaintext. Also I can't see any relationship between exact key value and execution time. But it seems to be hard to prove that there are no such weak keys. $\endgroup$ – Tom Oct 18 at 22:47
1
$\begingroup$

The difference between the execution time of logical operations (addition, multiplication, ...) and their relationship with the secret key of your cryptographic algorithm makes your program prone to side channel attacks, not whole time that it takes to execute.

For example for 3-bit round keys it runs 1 sec and for 128-bit round keys it runs 4 sec (for some number of inputs).

Indeed, every program is faster when its key is smaller.

Is this a disqualifying problem?

No.

There are two general ways to defeat side channel attacks: reducing side channels and eliminating the relationship between side channels and the secret key. You can reduce the side channels of your program by writing/using constant-time algorithms and you can make the side channels unrelated to your secret key by using masking/binding with adding random operations to your cryptographic algorithm.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.