Skip to content

lshift_prevent_overflow(bits = 0) empties/underflows altstack due to missing OP_TOALTSTACK pushes in limb shifters #399

Closed

Description

@trackoor

Summary

The function lshift_prevent_overflow assumes that its helper shifters populate the altstack with $(N_\text{LIMBS}-1)$ intermediate limbs and, unconditionally, pulls exactly $(N_\text{LIMBS}-1)$ items back via a trailing loop of OP_FROMALTSTACK.
This assumption is violated when bits = 0: both limb_lshift_without_carry(0) and limb_lshift_with_carry(0) execute the for i in 1..=bits body zero times and therefore never reach the branch that performs OP_TOALTSTACK.
Consequently, no elements are pushed to the altstack, while lshift_prevent_overflow still executes the following:

for _ in 1..Self::N_LIMBS {
    OP_FROMALTSTACK
}

which attempts to pop $(N_\text{LIMBS}-1)$ items from an empty altstack.
The observable effects are (i) an immediate stack underflow at runtime, or (ii) a silent stack-shape mismatch depending on the embedding, both of which break the function’s stated contract.

Expected Behavior

For any bits ∈ [0, LIMB_SIZE], the function should return the left-shifted BigInt with correct carry propagation, preserve stack discipline, and leave the altstack empty upon return.
In particular, bits = 0 is a semantic no-op: the input BigInt must be returned unchanged, and the altstack must not be touched (or, if touched, must be restored to its prior state).

Acknowledgments: This issue was identified using Pomelo (https://eprint.iacr.org/2024/1768) by the UCSB/Nubit team.

Activity

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

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions