monero_ed25519/

unreduced_scalar.rs

use core::cmp::Ordering;
use std_shims::{
  sync::LazyLock,
  io::{self, *},
};

use subtle::{Choice, ConstantTimeEq};
use zeroize::Zeroize;

use monero_io::*;

use crate::Scalar;

/// An unreduced scalar.
///
/// While most of modern Monero enforces scalars be reduced, certain legacy parts of the code did
/// not. These section can generally simply be read as a scalar/reduced into a scalar when the time
/// comes, yet a couple have non-standard reductions performed.
///
/// This struct delays scalar conversions and offers the non-standard reduction.
#[derive(Clone, Copy, Eq, Debug, Zeroize)]
pub struct UnreducedScalar([u8; 32]);

impl ConstantTimeEq for UnreducedScalar {
  fn ct_eq(&self, other: &Self) -> Choice {
    self.0.ct_eq(&other.0)
  }
}
impl PartialEq for UnreducedScalar {
  /// This defers to `ConstantTimeEq::ct_eq`.
  fn eq(&self, other: &Self) -> bool {
    bool::from(self.ct_eq(other))
  }
}

impl UnreducedScalar {
  /// Read an UnreducedScalar.
  pub fn read<R: Read>(r: &mut R) -> io::Result<UnreducedScalar> {
    Ok(UnreducedScalar(read_bytes(r)?))
  }

  /// Write an UnreducedScalar.
  pub fn write<W: Write>(&self, w: &mut W) -> io::Result<()> {
    w.write_all(&self.0)
  }

  fn as_bits(&self) -> [u8; 256] {
    let mut bits = [0; 256];
    for (i, bit) in bits.iter_mut().enumerate() {
      // Using `Choice` here takes advantage of `subtle`'s internal `black_box` function, necessary
      // as our MSRV doesn't allow us to use `core::hint::black_box`
      *bit = Choice::from(1 & (self.0[i / 8] >> (i % 8))).unwrap_u8();
    }

    bits
  }

  // Computes the non-adjacent form of this scalar with width 5.
  //
  // This matches Monero's `slide` function and intentionally gives incorrect outputs under
  // certain conditions in order to match Monero.
  //
  // This function does not execute in constant time and must only be used with public data.
  fn non_adjacent_form(&self) -> [i8; 256] {
    let bits = self.as_bits();
    let mut naf = [0i8; 256];
    for (b, bit) in bits.into_iter().enumerate() {
      naf[b] = i8::try_from(bit).expect("bit didn't fit within an i8");
    }

    for i in 0 .. 256 {
      if naf[i] != 0 {
        // if the bit is a one, work our way up through the window
        // combining the bits with this bit.
        for b in 1 .. 6 {
          if (i + b) >= 256 {
            // if we are at the length of the array then break out
            // the loop.
            break;
          }
          // potential_carry - the value of the bit at i+b compared to the bit at i
          let potential_carry = naf[i + b] << b;

          if potential_carry != 0 {
            if (naf[i] + potential_carry) <= 15 {
              // if our current "bit" plus the potential carry is less than 16
              // add it to our current "bit" and set the potential carry bit to 0.
              naf[i] += potential_carry;
              naf[i + b] = 0;
            } else if (naf[i] - potential_carry) >= -15 {
              // else if our current "bit" minus the potential carry is more than -16
              // take it away from our current "bit".
              // we then work our way up through the bits setting ones to zero, when
              // we hit the first zero we change it to one then stop, this is to factor
              // in the minus.
              naf[i] -= potential_carry;
              #[allow(clippy::needless_range_loop)]
              for k in (i + b) .. 256 {
                if naf[k] == 0 {
                  naf[k] = 1;
                  break;
                }
                naf[k] = 0;
              }
            } else {
              break;
            }
          }
        }
      }
    }

    naf
  }

  /// Recover the scalar that an array of bytes was incorrectly interpreted as by ref10's `slide`
  /// function (as used by the reference Monero implementation in C++).
  ///
  /// For Borromean range proofs, Monero did not check the scalars used were reduced. This led to
  /// some scalars serialized being interpreted as distinct scalars. This function recovers these
  /// distinct scalars, as required to verify Borromean range proofs within the Monero protocol.
  ///
  /// See <https://github.com/monero-project/monero/issues/8438> for more info.
  //
  /// This function does not execute in constant time and must only be used with public data.
  pub fn ref10_slide_scalar_vartime(&self) -> Scalar {
    use curve25519_dalek::Scalar as DScalar;

    /// Precomputed scalars used to recover an incorrectly reduced scalar
    static PRECOMPUTED_SCALARS: LazyLock<[DScalar; 8]> = LazyLock::new(|| {
      let mut precomputed_scalars = [DScalar::ONE; 8];
      for (i, scalar) in precomputed_scalars.iter_mut().enumerate().skip(1) {
        *scalar = DScalar::from(
          u64::try_from((i * 2) + 1).expect("enumerating more than u64::MAX / 2 items"),
        );
      }
      precomputed_scalars
    });

    if self.0[31] & 128 == 0 {
      // Computing the w-NAF of a number can only give an output with 1 more bit than
      // the number, so even if the number isn't reduced, the `slide` function will be
      // correct when the last bit isn't set.
      return Scalar::from(DScalar::from_bytes_mod_order(self.0));
    }

    let mut recovered = DScalar::ZERO;
    for &numb in self.non_adjacent_form().iter().rev() {
      recovered += recovered;
      match numb.cmp(&0) {
        Ordering::Greater => {
          recovered +=
            PRECOMPUTED_SCALARS[usize::try_from(numb).expect("positive i8 -> usize") / 2];
        }
        Ordering::Less => {
          recovered -=
            PRECOMPUTED_SCALARS[usize::try_from(-numb).expect("negated negative i8 -> usize") / 2];
        }
        Ordering::Equal => (),
      }
    }
    Scalar::from(recovered)
  }
}