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

monero_primitives/
unreduced_scalar.rs
