pq-code-package · hanno-becker · Jan 24, 2025 · Jan 24, 2025 · Jan 24, 2025
@@ -7,11 +7,14 @@ inputs:
   cflags:
     description: CFLAGS to pass to compilation
     default: ""
+  valgrind_flags:
+    description: Extra flags to pass to valgrind
+    default: ""
 
 runs:
   using: composite
   steps:
       - shell: ${{ env.SHELL }}
         run: |
           make clean
-          tests func --exec-wrapper="valgrind --error-exitcode=1 --track-origins=yes" --cflags="-DENABLE_CT_TESTING -DNTESTS=50 ${{ inputs.cflags }}"
+          tests func --exec-wrapper="valgrind --error-exitcode=1 --track-origins=yes ${{ inputs.valgrind_flags }}" --cflags="-DENABLE_CT_TESTING -DNTESTS=50 ${{ inputs.cflags }}"
@@ -40,6 +40,7 @@ jobs:
         with:
           gh_token: ${{ secrets.GITHUB_TOKEN }}
           nix-shell: ${{ matrix.nix-shell }}
+          nix-cache: true
       - name:  Build and run test (-Oz)
         # -Oz got introduced in gcc12
         if: ${{ matrix.nix-shell !=  'ci_gcc48' && matrix.nix-shell !=  'ci_gcc49' && matrix.nix-shell !=  'ci_gcc7' && matrix.nix-shell !=  'ci_gcc11'}}
@@ -76,3 +77,78 @@ jobs:
         uses: ./.github/actions/ct-test
         with:
           cflags: -O0
+  check-ct-varlat:
+    # Using the patched Valgrind from the KyberSlash paper to detect divisions
+    name: CT test (Variable-latency instructions) ${{ matrix.nix-shell }} ${{ matrix.system }}
+    strategy:
+      fail-fast: false
+      max-parallel: 4
+      matrix:
+        system: [ubuntu-latest, ubuntu-24.04-arm]
+        nix-shell:
+          - ci_valgrind-varlat_clang14
+          - ci_valgrind-varlat_clang15
+          - ci_valgrind-varlat_clang16
+          - ci_valgrind-varlat_clang17
+          - ci_valgrind-varlat_clang18
+          - ci_valgrind-varlat_clang19
+          - ci_valgrind-varlat_gcc48
+          - ci_valgrind-varlat_gcc49
+          - ci_valgrind-varlat_gcc7
+          - ci_valgrind-varlat_gcc11
+          - ci_valgrind-varlat_gcc12
+          - ci_valgrind-varlat_gcc13
+          - ci_valgrind-varlat_gcc14
+    runs-on: ${{ matrix.system }}
+    steps:
+      - uses: actions/checkout@11bd71901bbe5b1630ceea73d27597364c9af683 # v4.2.2
+      - name: Setup nix
+        uses: ./.github/actions/setup-shell
+        with:
+          gh_token: ${{ secrets.GITHUB_TOKEN }}
+          nix-shell: ${{ matrix.nix-shell }}
+          nix-cache: true
+      - name:  Build and run test (-Oz)
+        # -Oz got introduced in gcc12
+        if: ${{ matrix.nix-shell !=  'ci_valgrind-varlat_gcc48' && matrix.nix-shell !=  'ci_valgrind-varlat_gcc49' && matrix.nix-shell !=  'ci_valgrind-varlat_gcc7' && matrix.nix-shell !=  'ci_valgrind-varlat_gcc11'}}
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -Oz
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-Os)
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -Os
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-O3)
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -O3
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-Ofast)
+        # -Ofast got deprecated in clang19; -O3 -ffast-math should be used instead
+        if: ${{ matrix.nix-shell !=  'ci_valgrind-varlat_clang19' }}
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -Ofast
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-O3 -ffast-math)
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -O3 -ffast-math
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-O2)
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -O2
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-O1)
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -O1
+          valgrind_flags: --variable-latency-errors=yes
+      - name:  Build and run test (-O0)
+        uses: ./.github/actions/ct-test
+        with:
+          cflags: -O0
+          valgrind_flags: --variable-latency-errors=yes
@@ -58,6 +58,21 @@
           devShells.ci_gcc13 = util.wrapShell (util.mkShellWithCC pkgs.gcc13) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ pkgs.valgrind ]; hardeningDisable = [ "fortify" ]; };
           devShells.ci_gcc14 = util.wrapShell (util.mkShellWithCC pkgs.gcc14) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ pkgs.valgrind ]; hardeningDisable = [ "fortify" ]; };
 
+          # valgrind with a patch for detecting variable-latency instructions
+          devShells.ci_valgrind-varlat_clang14 = util.wrapShell (util.mkShellWithCC pkgs.clang_14) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_clang15 = util.wrapShell (util.mkShellWithCC pkgs.clang_15) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_clang16 = util.wrapShell (util.mkShellWithCC pkgs.clang_16) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_clang17 = util.wrapShell (util.mkShellWithCC pkgs.clang_17) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_clang18 = util.wrapShell (util.mkShellWithCC pkgs.clang_18) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_clang19 = util.wrapShell (util.mkShellWithCC inputs.nixpkgs2411.legacyPackages.${system}.clang_19) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc48 = util.wrapShell (util.mkShellWithCC pkgs.gcc48) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc49 = util.wrapShell (util.mkShellWithCC pkgs.gcc49) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc7 = util.wrapShell (util.mkShellWithCC pkgs.gcc7) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc11 = util.wrapShell (util.mkShellWithCC pkgs.gcc11) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc12 = util.wrapShell (util.mkShellWithCC pkgs.gcc12) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc13 = util.wrapShell (util.mkShellWithCC pkgs.gcc13) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+          devShells.ci_valgrind-varlat_gcc14 = util.wrapShell (util.mkShellWithCC pkgs.gcc14) { packages = [ pkgs.python3 ] ++ pkgs.lib.optionals (!pkgs.stdenv.isDarwin) [ util.valgrind-varlat ]; hardeningDisable = [ "fortify" ]; };
+
         };
       flake = {
         devShell.x86_64-linux =

@@ -110,7 +110,7 @@ static INLINE uint16_t scalar_decompress_d4(uint32_t u)
 __contract__(
   requires(0 <= u && u < 16)
   ensures(return_value <= (MLKEM_Q - 1))
-) { return ((u * MLKEM_Q) + 8) / 16; }
+) { return ((u * MLKEM_Q) + 8) >> 4; }
 
 /************************************************************
  * Name: scalar_compress_d5
@@ -159,7 +159,7 @@ static INLINE uint16_t scalar_decompress_d5(uint32_t u)
 __contract__(
   requires(0 <= u && u < 32)
   ensures(return_value <= MLKEM_Q - 1)
-) { return ((u * MLKEM_Q) + 16) / 32; }
+) { return ((u * MLKEM_Q) + 16) >> 5; }
 
 /************************************************************
  * Name: scalar_compress_d10
@@ -209,7 +209,7 @@ static INLINE uint16_t scalar_decompress_d10(uint32_t u)
 __contract__(
   requires(0 <= u && u < 1024)
   ensures(return_value <= (MLKEM_Q - 1))
-) { return ((u * MLKEM_Q) + 512) / 1024; }
+) { return ((u * MLKEM_Q) + 512) >> 10; }
 
 /************************************************************
  * Name: scalar_compress_d11
@@ -259,7 +259,7 @@ static INLINE uint16_t scalar_decompress_d11(uint32_t u)
 __contract__(
   requires(0 <= u && u < 2048)
   ensures(return_value <= (MLKEM_Q - 1))
-) { return ((u * MLKEM_Q) + 1024) / 2048; }
+) { return ((u * MLKEM_Q) + 1024) >> 11; }
 
 #if defined(MLKEM_NATIVE_MULTILEVEL_BUILD_WITH_SHARED) || \
     (MLKEM_K == 2 || MLKEM_K == 3)

@@ -85,4 +85,5 @@ rec {
     };
 
   cbmc = pkgs.callPackage ./cbmc { inherit bitwuzla; };
+  valgrind-varlat = pkgs.callPackage ./valgrind { };
 }
@@ -0,0 +1,21 @@
+[//]: # (SPDX-License-Identifier: CC-BY-4.0)
+
+This patch to Valgrind allows detecting secret-dependent division
+instructions by flagging variable-latency instruction depending
+on uninitialized data.
+
+It is part of the paper
+KyberSlash: Exploiting secret-dependent division timings in Kyber implementations
+by
+- Daniel J. Bernstein
+- Karthikeyan Bhargavan
+- Shivam Bhasin
+- Anupam Chattopadhyay
+- Tee Kiah Chia
+- Matthias J. Kannwischer
+- Franziskus Kiefer
+- Thales Paiva
+- Prasanna Ravi
+- Goutam Tamvada
+
+See [https://kyberslash.cr.yp.to/papers.html](https://kyberslash.cr.yp.to/papers.html).
@@ -0,0 +1,7 @@
+# SPDX-License-Identifier: Apache-2.0
+{ valgrind, ... }:
+valgrind.overrideAttrs (_: {
+  patches = [
+    ./valgrind-varlat-patch-20240808.txt
+  ];
+})