LFX Mentorship - Liboqs

[Ritish134]

Enhancing Constant-Time Analysis Tooling in liboqs

Name: Ritish Chandra Srivastava
GitHub: Ritish134
Email: ritishnew@gmail.com
Mentorship Period: 8 Weeks
Mentor: @bhess

---

Background and Motivation

In my exploration of the liboqs codebase, I focused on analyzing AVX2-optimized functions like rej_uniform_avx2.c. While the code used unfamiliar SIMD instructions and had a complex structure, I was determined to understand and compile it in isolation. This led me to investigate how functions like these are tested for constant-time behavior and whether timing vulnerabilities can be reliably detected.

As I dug deeper, I realized there’s a lack of seamless automation around side-channel detection in such projects. The critical nature of post-quantum cryptography and the real-world impact of issues like Kyberslash make automated tooling a necessity.

This mentorship is a chance to contribute a robust solution: by integrating effective constant-time analysis tools into liboqs, improving their reliability, and streamlining them into CI.

---

Project Overview

The goal is to strengthen the detection of timing side-channel vulnerabilities in the liboqs library by building a maintainable, CI-ready testing framework using reliable constant-time analysis tools. This includes:

• Building wrappers and infrastructure for testing selected cryptographic routines.
• Running automated tests with tools like dudect or ctgrind, where applicable.
• Triaging any findings and integrating reporting into liboqs development workflows.
• Submitting upstream reports or fixes if vulnerable patterns are found.
• Documenting the tools, methodology, and integration approach for long-term use.

---

Deliverables

By the end of the mentorship, I will deliver:

• Tooling to test functions for constant-time behavior with consistent input/output setup.
• Automated detection scripts integrated into CI to run on commits and PRs.
• Summary reports generated automatically on suspected violations.
• Investigated findings, triaged and, where needed, discussed or patched upstream.
• Developer documentation showing how to extend or run the tooling locally.

---

🗓️ 8-Week Timeline for Timing Side-Channel Analysis Integration

Week 1 - Setup and Baseline Testing

• Set up local development environment and CI-equivalent runners.
• Identify and isolate ~5 target functions (e.g., rej_uniform_avx2).
• Build minimal reproducible wrappers for testing.

Week 2 - Initial Tool Integration

• Run initial timing tests using Dudect.
• Evaluate available tools:
  • ctgrind: Valgrind patch for detecting secret-dependent memory access and control flow.
  • ctverif: Formal verification tool for constant-time validation.
  • Flow-tracker: Tracks static instruction traces that may lead to timing variabilities.
• Measure timing variance across controlled inputs.
• Compare reference vs optimized (AVX2) implementations for discrepancies.

Week 3 - Expand Test Coverage

• Generalize the test harness across multiple algorithms and implementations.
• Define a logging format for storing results (e.g., JSON or Markdown).
• Review false positives and clean up noisy tests.

Week 4 - CI Integration Prototype

• Design and implement a GitHub Actions workflow.
• Ensure CI output is easily reviewable (e.g., timing summary, pass/fail status).
• Document the setup to ensure reproducibility.

Week 5 - Triage and Deep Inspection

• Investigate failed tests using:
  • Static analysis
  • Disassembly (objdump)
  • Branch profiling
• Determine whether issues are real vulnerabilities or tool limitations.
• Prepare reports and suggest fixes to the liboqs team.

Week 6 - Refinement and Error Handling

• Add caching of results and retry logic.
• Support configurable timing thresholds.
• Add support for skipping known variable-time functions.
• Refactor test infrastructure for long-term maintenance.

Week 7 - Finalize Documentation and Developer Tools

• Write:
  • Usage instructions
  • Contribution guide
  • Integration strategy
• Ensure test scripts are modular and extensible.

Week 8 - Final Review and Reporting

• Submit a complete report summarizing:
  • Tools used
  • Process followed
  • Results found
• Create a sample dashboard or summary output.
• Wrap up any remaining issues or findings.

---

Tools and Languages

• C: For understanding low-level function behavior.
• Shell / Python: For automation scripts and test harnesses.
• Dudect / Ctgrind: Timing and side-channel analysis.
• GitHub Actions: For CI integration.
• Perf / objdump: For deeper inspection when needed.

---

Prior Work and Initiative

• Explored the liboqs AVX2 backend and attempted to build rej_uniform_avx2.c in isolation.
• Studied constant-time analysis tools and began prototyping wrapper code.
• Documented function behavior to identify where side-channel vulnerabilities may appear.
• Reproduced baseline behavior of functions to prepare for analysis.

---

Example Test: Instruction Count Variability

To understand where timing variability might arise in liboqs, I started with direct observation of runtime characteristics using valgrind's cachegrind tool:

$ valgrind --tool=cachegrind --cachegrind-out-file=cache.out ./example_kem
$ cg_annotate cache.out > cache_report.txt

Also created liboqs_dudect_kyber.c to use dudect on OQS_KEM_encaps for testing purpose

#define DUDECT_IMPLEMENTATION
#include "dudect.h"

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <oqs/oqs.h>

#define KEM_NAME "Kyber512"
#define SECRET_LENGTH 32

OQS_KEM *kem = NULL;
uint8_t *pk = NULL;
uint8_t *sk = NULL;

void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
    for (size_t i = 0; i < c->number_measurements; i++) {
        uint8_t value = (i % 2) ? 0xAA : 0x55;
        memset(input_data + i * c->chunk_size, value, c->chunk_size);
        classes[i] = i % 2;
    }
}

uint8_t do_one_computation(uint8_t *input_data) {
    uint8_t ct[kem->length_ciphertext];
    uint8_t ss[kem->length_shared_secret];

    // Note: sk is not used here for encapsulation.
    OQS_STATUS rc = OQS_KEM_encaps(kem, ct, ss, pk);
    if (rc != OQS_SUCCESS) {
        fprintf(stderr, "OQS_KEM_encaps failed\n");
        exit(1);
    }
    return 0;
}

int main(void) {
    kem = OQS_KEM_new(KEM_NAME);
    if (kem == NULL) {
        printf("Failed to init KEM\n");
        return 1;
    }

    pk = malloc(kem->length_public_key);
    sk = malloc(kem->length_secret_key);

    OQS_KEM_keypair(kem, pk, sk);

    dudect_ctx_t ctx;
    dudect_config_t conf = {
        .chunk_size = SECRET_LENGTH,
        .number_measurements = 20000
    };

    dudect_init(&ctx, &conf);

    int ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
    while (ret == DUDECT_NO_LEAKAGE_EVIDENCE_YET) {
        ret = dudect_main(&ctx);
    }

    dudect_free(&ctx);

    free(pk);
    free(sk);
    OQS_KEM_free(kem);

    return (ret == DUDECT_LEAKAGE_FOUND) ? 1 : 0;
}

Output:

meas:    0.02 M, max t:   +0.45, max tau: 3.15e-03, (5/tau)^2: 2.51e+06. For the moment, maybe constant time.
meas:    0.04 M, max t:   +5.81, max tau: 2.97e-02, (5/tau)^2: 2.83e+04. For the moment, maybe constant time.
meas:    0.06 M, max t:   +6.12, max tau: 2.55e-02, (5/tau)^2: 3.83e+04. For the moment, maybe constant time.
meas:    0.08 M, max t:   +6.21, max tau: 2.24e-02, (5/tau)^2: 4.98e+04. For the moment, maybe constant time.
meas:    0.10 M, max t:   +6.82, max tau: 2.20e-02, (5/tau)^2: 5.19e+04. For the moment, maybe constant time.
meas:    0.12 M, max t:   +7.56, max tau: 2.22e-02, (5/tau)^2: 5.07e+04. For the moment, maybe constant time.
meas:    0.13 M, max t:   +7.17, max tau: 1.96e-02, (5/tau)^2: 6.53e+04. For the moment, maybe constant time.
meas:    0.15 M, max t:   +7.25, max tau: 1.85e-02, (5/tau)^2: 7.29e+04. For the moment, maybe constant time.
meas:    0.17 M, max t:   +7.89, max tau: 1.90e-02, (5/tau)^2: 6.90e+04. For the moment, maybe constant time.
meas:    0.19 M, max t:   +8.62, max tau: 1.98e-02, (5/tau)^2: 6.38e+04. For the moment, maybe constant time.
meas:    0.21 M, max t:   +8.89, max tau: 1.95e-02, (5/tau)^2: 6.60e+04. For the moment, maybe constant time.
meas:    0.23 M, max t:   +9.18, max tau: 1.92e-02, (5/tau)^2: 6.75e+04. For the moment, maybe constant time.
meas:    0.25 M, max t:   +9.75, max tau: 1.96e-02, (5/tau)^2: 6.48e+04. For the moment, maybe constant time.
meas:    0.27 M, max t:   +9.40, max tau: 1.82e-02, (5/tau)^2: 7.51e+04. For the moment, maybe constant time.
meas:    0.28 M, max t:   +9.71, max tau: 1.83e-02, (5/tau)^2: 7.50e+04. For the moment, maybe constant time.
meas:    0.30 M, max t:  +10.17, max tau: 1.85e-02, (5/tau)^2: 7.28e+04. Probably not constant time.

[bhess]

Hi,
Thanks a lot for sharing your proposed work plan and initial experiments.

Just a quick note: to be considered for the mentorship, you'll need to submit an application via the LFX platform:
https://mentorship.lfx.linuxfoundation.org/project/aad7822e-9ae8-402d-aeb0-2663a6bd8039

Looking forward to your application!

[Ritish134]

Done!