Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

CBMC: Unify native vs. non-native rej_uniform C code #525

Open
hanno-becker opened this issue Dec 13, 2024 · 0 comments
Open

CBMC: Unify native vs. non-native rej_uniform C code #525

hanno-becker opened this issue Dec 13, 2024 · 0 comments
Labels
CBMC enhancement New feature or request
Milestone

Comments

@hanno-becker
Copy link
Contributor

Unlike most other native routines which are a drop-in replacement for their C counterparts, native rej_uniform implementations can reject their input, in which case the caller calls back to the C implementation. This leads to a divergence of the frontend C code depending on the backend, which is not ideal:

#if !defined(MLKEM_USE_NATIVE_REJ_UNIFORM)
unsigned int rej_uniform(int16_t *r, unsigned int target, unsigned int offset,
                         const uint8_t *buf, unsigned int buflen)
{
  return rej_uniform_scalar(r, target, offset, buf, buflen);
}
#else  /* MLKEM_USE_NATIVE_REJ_UNIFORM */

unsigned int rej_uniform(int16_t *r, unsigned int target, unsigned int offset,
                         const uint8_t *buf, unsigned int buflen)
{
  int ret;

  /* Sample from large buffer with full lane as much as possible. */
  ret = rej_uniform_native(r + offset, target - offset, buf, buflen);
  if (ret != -1)
    return offset + (unsigned)ret;

  return rej_uniform_scalar(r, target, offset, buf, buflen);
}
#endif /* MLKEM_USE_NATIVE_REJ_UNIFORM */

In particular, the CBMC proofs do not cover the fallback logic.

Task: Rewrite rej_uniform() so that the fallback logic is always exercised, but implement rej_uniform_native() as a no-op in case no native implementation is provided. In CBMC, specify rej_uniform_native and conduct the proof of rej_uniform against this spec.

@hanno-becker hanno-becker added enhancement New feature or request CBMC labels Dec 13, 2024
@hanno-becker hanno-becker added this to the next milestone Dec 13, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
CBMC enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant