Skip to content

Ed25519 scalar mul leaks secret through constraint graph #2

@Mahdi171

Description

@Mahdi171

Reported by Justin Thaler (@GUJustin).

Problem

scalar_mul in ed25519.cpp extracts secret scalar bits into native bool via get_u64() and branches on them with regular if statements. This makes the constraint graph depend on the secret scalar. We found same issue in scalar_mul_generator and scalar_mul_montgomery.

Impact

Any circuit using ed25519_point::scalar_mul with a private scalar (like PQChain's pk_verify) produces input-dependent constraints. Ligero verification fails because the verifier re-executes with zeroed private inputs and gets a different constraint structure.

Plan

  • Keep scalar bits as bn254fr_class, add mux()/mux2() to ed25519_point
  • Rewrite all three scalar muls to use oblivious 2-bit windowed selection
  • Replace while loops in sub()/reduce() with fixed-iteration equivalents
  • Remove get_u64() branching in byte reconstruction; use unconditional bit-OR
  • Remove early-return zero checks in inverse(), to_affine(), to_limbs()

Metadata

Metadata

Labels

bugSomething isn't workingenhancementNew feature or request

Type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions