vartime Safety - guardrails & static analysis by design

[pinkforest]

Some algorithms have vartime components on non-secret data requiring associated use of vartime functionality.

e.g. where the vartime use is associated with non-secret dependant data.

This could be treated similarly to Rust borrow checker and unsafe { .. }

Marking data as VarTime safe - e.g. hinting it's public could be done via a macro:

#[vartime(public)]
pub struct PublicData {
  pub(crate) public_field: SomeOtherData,
}

Then in functions guard input to vartime functions via the generated wrapper VarTime<PublicData> type

/// VARTIME SAFETY: PublicData is not secret
#[vartime_guard]
pub fn some_vartime_thing(VarTime<PublicData>, SecretData) { .. }

This would enable borrow check type static analysis - ctgrind but in static - so that secret data does not end up in vartime.

I've also looked into doing static analysis off MIR for CI check but having type-level guardrails could help safety.

Also we can enable check to ensure no use of "vartime safety undocumented" vartime gets undocumented.

Relevant Cryptography

• #590 with RSA Even GCD where Even mod-1 is used

Prior art

• https://github.com/agl/ctgrind - Adam Langley ctgrind (dynamic analysis via valgrind)
• https://www.post-apocalyptic-crypto.org/timecop/ - TIMECOP as part of SUPERCOP adapting ctgrind for all nist entries
• https://github.com/rozbb/dudect-bencher - @rozbb port of dudect to Rust (dynamic statistical analysis)
• https://eprint.iacr.org/2016/1123.pdf - dudect paper
• https://docs.rs/pre/latest/pre/ - when type-level is not enough

Dudect requires carefully crafted datasets (I adapted rozbb's vec eq example to ct/vartime memcmp) to illustrate.

[tarcieri]

One problem is we use *_vartime if any of the parameters lead to variable-time behavior, however often in practice we will call these *_vartime methods on a secret input but where they're variable-time only with respect to an rhs parameter which is fixed/constant, generally noting the overall result is constant-time with a comment.