Question on constant-time implementation

[Seongkwang Kim]

Dear KpqC committee and all,

We are wondering about how the constant-time implementation should be achieved.

We think there may be two (or more) types of constant-time implementation.

1. strict type: all the algorithms in a cryptosystem run in constant time regardless whether the secret key is involved or not.

2. relaxed type: only algorithms involving the secret key run in constant time. It targets to prevent exfiltration of the secret key by timing attacks.

We look forward to hearing from you, the participants, as well as the committee.

Best regards,

Seongkwang Kim

[Hwajeong Seo]

Hi Dr. Kim,

In my opinion, for the competition purpose, the option 2 (relaxed type) is enough.

(Actually I think we need to see the relative performance rather than secure implementation in the competition.)

For the case of industiral distribution, we need to considerthe option 1 (strict type).

THank you.

2023년 11월 16일 목요일 오전 10시 48분 0초 UTC+9에 Seongkwang Kim님이 작성:

[D. J. Bernstein]

The rules enforced by the TIMECOP option inside SUPERCOP are as follows.
Inputs are marked as secret except for public keys, nonces, and
ciphertexts. RNG output, anything returned from randombytes(), is marked
as secret. Anything computed from a secret is marked as secret. Secret
branches and secret array indices aren't allowed.

Marking RNG output as secret is important. DSA and ECDSA are standard
examples where timings that depend on RNG output lead to fast attacks;
see, e.g., https://tpm.fail.

It's safe to have secret branches in typical rejection-sampling loops,
such as trying many independent random p inside RSA key generation until
p is prime. With TIMECOP, you can call crypto_declassify() to mark the
rejection condition as public before using it.

saferewrite from https://pqsrc.cr.yp.to/downloads.html also checks for
divisions and multiplications involving secret data. CPUs typically take
variable time for divisions, and some CPUs take variable time for
multiplications. There are plans to have TIMECOP support goal-constmul,
on top of the existing goal-constbranch and goal-constindex.

---D. J. Bernstein

[KpqC-bulletin]

Dear Dr. Seongkwang Kim,

 

We appreciate your interest in the KpqC competition.

Concerning the implementation issue mentioned in your posting, we solicited the opinions of the algorithm submitters, and the agreements reached are detailed below.

 

Regarding constant-time implementation, we will request only the part involving secret information to be constant-time for Round 2.

Please note that our stance from the very beginning was to reflect submitters’ opinions as much as possible.

Similarly, we will only request minimum criteria, which is a constant-time implementation of secret-related components, and leave the decision of the implementation beyond that to each team.

 

Thank you once more for your interest in these matters.

Any comments or suggestions are always welcome.

 

Best regards,

KpqC team

2023년 11월 16일 목요일 오전 10시 48분 0초 UTC+9에 seongkwa...@gmail.com님이 작성: