monero_primitives/
unreduced_scalar.rs

1use core::cmp::Ordering;
2use std_shims::{
3  sync::LazyLock,
4  io::{self, *},
5};
6
7use zeroize::Zeroize;
8
9use curve25519_dalek::scalar::Scalar;
10
11use monero_io::*;
12
13// Precomputed scalars used to recover an incorrectly reduced scalar.
14static PRECOMPUTED_SCALARS: LazyLock<[Scalar; 8]> = LazyLock::new(|| {
15  let mut precomputed_scalars = [Scalar::ONE; 8];
16  for (i, scalar) in precomputed_scalars.iter_mut().enumerate().skip(1) {
17    *scalar =
18      Scalar::from(u64::try_from((i * 2) + 1).expect("enumerating more than u64::MAX / 2 items"));
19  }
20  precomputed_scalars
21});
22
23/// An unreduced scalar.
24///
25/// While most of modern Monero enforces scalars be reduced, certain legacy parts of the code did
26/// not. These section can generally simply be read as a scalar/reduced into a scalar when the time
27/// comes, yet a couple have non-standard reductions performed.
28///
29/// This struct delays scalar conversions and offers the non-standard reduction.
30#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
31pub struct UnreducedScalar(pub [u8; 32]);
32
33impl UnreducedScalar {
34  /// Write an UnreducedScalar.
35  pub fn write<W: Write>(&self, w: &mut W) -> io::Result<()> {
36    w.write_all(&self.0)
37  }
38
39  /// Read an UnreducedScalar.
40  pub fn read<R: Read>(r: &mut R) -> io::Result<UnreducedScalar> {
41    Ok(UnreducedScalar(read_bytes(r)?))
42  }
43
44  fn as_bits(&self) -> [u8; 256] {
45    let mut bits = [0; 256];
46    for (i, bit) in bits.iter_mut().enumerate() {
47      *bit = core::hint::black_box(1 & (self.0[i / 8] >> (i % 8)))
48    }
49
50    bits
51  }
52
53  // Computes the non-adjacent form of this scalar with width 5.
54  //
55  // This matches Monero's `slide` function and intentionally gives incorrect outputs under
56  // certain conditions in order to match Monero.
57  //
58  // This function does not execute in constant time and must only be used with public data.
59  fn non_adjacent_form(&self) -> [i8; 256] {
60    let bits = self.as_bits();
61    let mut naf = [0i8; 256];
62    for (b, bit) in bits.into_iter().enumerate() {
63      naf[b] = i8::try_from(bit).expect("bit didn't fit within an i8");
64    }
65
66    for i in 0 .. 256 {
67      if naf[i] != 0 {
68        // if the bit is a one, work our way up through the window
69        // combining the bits with this bit.
70        for b in 1 .. 6 {
71          if (i + b) >= 256 {
72            // if we are at the length of the array then break out
73            // the loop.
74            break;
75          }
76          // potential_carry - the value of the bit at i+b compared to the bit at i
77          let potential_carry = naf[i + b] << b;
78
79          if potential_carry != 0 {
80            if (naf[i] + potential_carry) <= 15 {
81              // if our current "bit" plus the potential carry is less than 16
82              // add it to our current "bit" and set the potential carry bit to 0.
83              naf[i] += potential_carry;
84              naf[i + b] = 0;
85            } else if (naf[i] - potential_carry) >= -15 {
86              // else if our current "bit" minus the potential carry is more than -16
87              // take it away from our current "bit".
88              // we then work our way up through the bits setting ones to zero, when
89              // we hit the first zero we change it to one then stop, this is to factor
90              // in the minus.
91              naf[i] -= potential_carry;
92              #[allow(clippy::needless_range_loop)]
93              for k in (i + b) .. 256 {
94                if naf[k] == 0 {
95                  naf[k] = 1;
96                  break;
97                }
98                naf[k] = 0;
99              }
100            } else {
101              break;
102            }
103          }
104        }
105      }
106    }
107
108    naf
109  }
110
111  /// Recover the scalar that an array of bytes was incorrectly interpreted as by ref10's `slide`
112  /// function (as used by the reference Monero implementation in C++).
113  ///
114  /// For Borromean range proofs, Monero did not check the scalars used were reduced. This led to
115  /// some scalars serialized being interpreted as distinct scalars. This function recovers these
116  /// distinct scalars, as required to verify Borromean range proofs within the Monero protocol.
117  ///
118  /// See <https://github.com/monero-project/monero/issues/8438> for more info.
119  //
120  /// This function does not execute in constant time and must only be used with public data.
121  pub fn ref10_slide_scalar_vartime(&self) -> Scalar {
122    if self.0[31] & 128 == 0 {
123      // Computing the w-NAF of a number can only give an output with 1 more bit than
124      // the number, so even if the number isn't reduced, the `slide` function will be
125      // correct when the last bit isn't set.
126      return Scalar::from_bytes_mod_order(self.0);
127    }
128
129    let mut recovered = Scalar::ZERO;
130    for &numb in self.non_adjacent_form().iter().rev() {
131      recovered += recovered;
132      match numb.cmp(&0) {
133        Ordering::Greater => {
134          recovered += PRECOMPUTED_SCALARS[usize::try_from(numb).expect("positive i8 -> usize") / 2]
135        }
136        Ordering::Less => {
137          recovered -=
138            PRECOMPUTED_SCALARS[usize::try_from(-numb).expect("negated negative i8 -> usize") / 2]
139        }
140        Ordering::Equal => (),
141      }
142    }
143    recovered
144  }
145}
monero_primitives/unreduced_scalar.rs

monero_primitives/
unreduced_scalar.rs
