Skip to content

Padding implementation is not constant-time #626

Open
Open
Padding implementation is not constant-time#626
Labels
security

Description

@tarcieri
tarcieri
opened on Jan 7, 2026

This is a followup to #19, which was originally about the modular exponentiation implementation not being constant-time, and also became our general tracking issue for the subsequent Marvin Attack.

We've gone to great lengths in crypto-bigint to produce the closest thing we can to a constant-time implementation of modular exponentiation, and while we still need to e.g. verify that's truly the case via static analysis tooling, based on the latest analysis from the Marvin Toolkit it seems like the remaining sidechannels in our implementation are probably no longer coming from crypto-bigint, but are instead in this crate's implementation of RSA padding modes.

PKCS#1 v1.5 in particular notably has a long history of sidechannels going back to Bleichenbacher's original 1998 attack, and attacks like Marvin can be seen as an evolution of that attack.

This I-D contains guidance for implementing RSA in constant-time, including things like handling depadding errors using strategies like implicit rejection:

https://datatracker.ietf.org/doc/draft-irtf-cfrg-rsa-guidance/

Activity

  1. tarcieri
    added
    security
    on Jan 7, 2026
  2. tarcieri
    marked CVE #630 as a duplicate of this issue on Jan 18, 2026

  3. Ryujiyasu commented on Mar 24, 2026

    @Ryujiyasu
    Ryujiyasu
    on Mar 24, 2026

    Formal Verification of the Timing Vulnerability using Kani

    I've built ne, a formal verification tool that uses Kani (bounded model checking) to mathematically prove properties of cryptographic code.

    I applied ne to the vulnerable pkcs1v15_encrypt_unpad pattern from this crate and can confirm:

    Vulnerability Detection

    Kani formally proves the timing leak exists — the function has a secret-dependent branch (if valid == 0 { return Err(...) }) that causes different control flow paths depending on padding validity:

    Harness: detect_vulnerable_timing_leak
Result:  VERIFICATION:- FAILED
Reason:  "Timing leak: function returns None for invalid padding"

    This is not a test failure — it's an exhaustive mathematical proof over all possible inputs that the function violates constant-time properties.

    Fix Verification (Implicit Rejection)

    I implemented a constant-time fix using implicit rejection (same approach as Go's crypto/rsa and the IRTF guidance) and Kani verifies:

    Harness Result What it proves
    verify_fixed_constant_output_length VERIFIED Output is always k - 11 bytes regardless of input validity
    verify_fixed_correct_for_valid_input VERIFIED Valid PKCS#1 v1.5 padded messages are correctly decrypted
    verify_ct_eq_u8 VERIFIED Constant-time byte equality (all 256×256 pairs)
    verify_ct_select_u8 VERIFIED Constant-time conditional select
    verify_ct_select_u32 VERIFIED Constant-time conditional select (u32)
    verify_ct_gte_u32 VERIFIED Constant-time greater-than-or-equal

    All proofs verified by CBMC SMT solver — not sampling, but exhaustive verification of all possible inputs.

    Reproduction

    The full audit code is available at: https://gitlab.com/Ryujiyasu/ne/-/tree/main/crates/ne-rsa-audit

    # Install Kani
cargo install --locked kani-verifier && cargo kani setup

# Clone and verify
git clone https://gitlab.com/Ryujiyasu/ne.git && cd ne

# Detect the vulnerability (should FAIL)
cargo kani -p ne-rsa-audit --harness detect_vulnerable_timing_leak

# Verify the fix (should PASS)
cargo kani -p ne-rsa-audit --harness verify_fixed_constant_output_length
cargo kani -p ne-rsa-audit --harness verify_fixed_correct_for_valid_input

    Happy to help verify PR #627's fix with Kani as well — formal verification can provide stronger guarantees than testing alone for constant-time properties.

  4. tarcieri commented on Mar 25, 2026

    @tarcieri
    tarcieri
    on Mar 25, 2026
    MemberAuthor

    @Ryujiyasu per the OP, we are already aware the use of explicit rejection causes a timing side-channel and that implicit rejection is the proper solution.

    You say you implemented a fix based on the Go implementation of implicit rejection. Where is that?

  5. Ryujiyasu commented on Mar 26, 2026

    @Ryujiyasu
    Ryujiyasu
    on Mar 26, 2026

    The implementation is in the audit repo linked in my previous comment: https://gitlab.com/Ryujiyasu/ne/-/blob/main/crates/ne-rsa-audit/src/lib.rs

    To be clear, this is a standalone proof-of-concept with Kani formal verification, not a direct PR to this crate. Happy to help verify PR #627's approach with Kani if that would be useful.

  6. gnapoli23 commented on Apr 1, 2026

    @gnapoli23
    gnapoli23
    on Apr 1, 2026

    The implementation is in the audit repo linked in my previous comment: https://gitlab.com/Ryujiyasu/ne/-/blob/main/crates/ne-rsa-audit/src/lib.rs

    To be clear, this is a standalone proof-of-concept with Kani formal verification, not a direct PR to this crate. Happy to help verify PR #627's approach with Kani if that would be useful.

    This looks promising. @tarcieri did you have the chance to look into it?

  7. tarcieri commented on Apr 7, 2026

    @tarcieri
    tarcieri
    on Apr 7, 2026
    MemberAuthor

    Perhaps I should clarify what we're actually looking for here since we've gotten a few PRs to add this but not really ones I'm happy with yet:

    A PR that adds implicit rejection shouldn't be adding new APIs or features. To the extent the existing APIs are fallible, that fallibility can be removed in the case all a function is doing is padding verification, but we already have fallible APIs that handle other errors, and those shouldn't change.

    Instead, the existing PKCS#1 v1.5 implementation should change to use implicit rejection internally, removing the existing fallible handling of padding. We should also copiously document this change.

    Regarding @Ryujiyasu's implementation, while that could serve as a reference the implementation is really going to need to be specific to the rsa crate and ctutils, with the constant-time portions handled using ctutils.

    The implementation in #680 is looking closer, but I'll reiterate some of my comments there.

  8. rpopplewell commented on May 3, 2026

    @rpopplewell
    rpopplewell
    on May 3, 2026

    @tomato42, I'm taking you up on your offer to help interpret results. This is with 10 million samples on an implementation following the guidance. The rest of the plots are here. I'm wondering if you think it'd be worth it to do another run with more samples or there's an issue here still.

    Image 
    tlsfuzzer analyse.py version 9 analysis
Sign test mean p-value: 0.52, median p-value: 0.5839, min p-value: 0.00545
Friedman test (chisquare approximation) for all samples
p-value: 0.3816383545767115
Worst pair: 1(no_header_with_payload_48), 9(valid_repeated_byte_payload_246_1)
Mean of differences: -1.55932e-08s, 95% CI: -3.24720e-08s, 3.231822e-09s (±1.785e-08s)
Median of differences: -9.00000e-09s, 95% CI: -1.00000e-08s, 0.000000e+00s (±5.000e-09s)
Trimmed mean (5%) of differences: -6.76119e-09s, 95% CI: -1.22300e-08s, -1.665907e-09s (±5.282e-09s)
Trimmed mean (25%) of differences: -4.60229e-09s, 95% CI: -8.97022e-09s, -5.707400e-10s (±4.200e-09s)
Trimmed mean (45%) of differences: -4.81050e-09s, 95% CI: -8.17901e-09s, -1.065756e-09s (±3.557e-09s)
Trimean of differences: -7.00000e-09s, 95% CI: -1.00000e-08s, 0.000000e+00s (±5.000e-09s)
Layperson explanation: Large confidence intervals detected, collecting more data necessary. 
Side channel leakage smaller than 3.557e-09s is possible
For detailed report see rsa2048_repeat/report.csv
  9. oferchen
    added 6 commits that reference this issue on May 3, 2026

    fix(deps): allowlist RUSTSEC-2023-0071 (Marvin Attack via russh-keys/…

    c65fe6e

    fix(workspace): expose embedded-ssh facade feature on root crate (#3569)

    0f759b5

    fix(deny): re-add RUSTSEC-2023-0071 allowlist for rsa 0.10 RC

    d058de7

    chore(deps): bump russh 0.45 -> 0.60.1, drop GHSA-f5v4-2wr6-hqmg allo…

    863d5f4

    fix(workspace): expose embedded-ssh facade feature on root crate (#3569)

    98cdf04

    chore(deps): bump russh 0.45 -> 0.60.1, drop GHSA-f5v4-2wr6-hqmg allo…

    60d5723

  10. tomato42 commented on May 14, 2026

    @tomato42
    tomato42
    on May 14, 2026

    @tomato42, I'm taking you up on your offer to help interpret results. This is with 10 million samples on an implementation following the guidance. The rest of the plots are here. I'm wondering if you think it'd be worth it to do another run with more samples or there's an issue here still.
    Image

    tlsfuzzer analyse.py version 9 analysis
Sign test mean p-value: 0.52, median p-value: 0.5839, min p-value: 0.00545
Friedman test (chisquare approximation) for all samples
p-value: 0.3816383545767115
Worst pair: 1(no_header_with_payload_48), 9(valid_repeated_byte_payload_246_1)
Mean of differences: -1.55932e-08s, 95% CI: -3.24720e-08s, 3.231822e-09s (±1.785e-08s)
Median of differences: -9.00000e-09s, 95% CI: -1.00000e-08s, 0.000000e+00s (±5.000e-09s)
Trimmed mean (5%) of differences: -6.76119e-09s, 95% CI: -1.22300e-08s, -1.665907e-09s (±5.282e-09s)
Trimmed mean (25%) of differences: -4.60229e-09s, 95% CI: -8.97022e-09s, -5.707400e-10s (±4.200e-09s)
Trimmed mean (45%) of differences: -4.81050e-09s, 95% CI: -8.17901e-09s, -1.065756e-09s (±3.557e-09s)
Trimean of differences: -7.00000e-09s, 95% CI: -1.00000e-08s, 0.000000e+00s (±5.000e-09s)
Layperson explanation: Large confidence intervals detected, collecting more data necessary. 
Side channel leakage smaller than 3.557e-09s is possible
For detailed report see rsa2048_repeat/report.csv

    sorry for the delay

    yes, that indeed is a significant improvement, unfortunately, I would say that this size of a sample is insufficient to say that it is definitely not vulnerable, only that a side channel bigger than 3.5 ns is unlikely.
    Generally I try to collect enough data to exclude a possibility of a side channel larger than a nanosecond, as that's only 4-5 CPU clock cycles. That would require about 15 times more data.

  11. 7 remaining items

  12. Ujang360
    added 2 commits that reference this issue on Jun 7, 2026

    chore(snap): supply-chain + lint config for the snap crates

    5eee5f2

    feat(snap): integrate pt-immer/lib-snap as kamu-snap-* crates (#11)

    46debac
  13. send
    added a commit that references this issue on Jun 8, 2026

    fix(crypto): PR-5a Codex R1 — 4 findings + RUSTSEC-2023-0071 deny gate

    05add07
  14. bigunmd
    added a commit that references this issue on Jun 23, 2026

    fix(deps): bump russh to 0.61 to clear RUSTSEC-2026-0153/0154

    b5eaa7a
  15. nunesgh
    marked this as blocking on Jul 19, 2026
  16. tronje
    added a commit that references this issue on Jul 24, 2026

    Update several crates

    1291d6b
  17. vdavid
    added a commit that references this issue on Aug 23, 2026

    docs(security): the RSA/Marvin ignore now says exactly which path is …

    944c03f
  18. debugmode0
    added a commit that references this issue on Aug 23, 2026

    Round 44 F5: ignore RUSTSEC-2023-0071 (Marvin Attack on rsa) — path u…

    0da4f66
  19. supermarsx
    added a commit that references this issue on Sep 2, 2026

    security(osv): waive RUSTSEC-2023-0071 with a short, conditional expiry

    50d180c
  20. salamaashoush
    added a commit that references this issue on Sep 7, 2026

    ci: accept the one advisory that has nowhere to go

    d47bf12
  21. kaen25
    added 2 commits that reference this issue on Sep 8, 2026

    docs(sign): name the residual risk rather than call it closed

    3980321

    docs(deny): the rsa exception is a residual risk, not a resolved finding

    257be07
  22. LeoAlecksey
    added a commit that references this issue on Oct 9, 2026

    Аудит: принятый риск RUSTSEC-2023-0071 (rsa через pgp, Passbolt)

    acd1510
  23. jasondwhyte
    added a commit that references this issue on Oct 15, 2026

    CI: run cargo audit from the engine with a documented ignore for RUST…

    af9ae8d
  24. landoyjx
    added a commit that references this issue on Oct 16, 2026

    ✨ feat(gateway): a JWKS-backed JWT verifier, for the bearer-token cha…

    96ff9aa
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    security

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions