ic_ec/
x25519.rs

1//! RFC 7748 X25519 key agreement.
2
3use crate::field::Fe;
4use ic_core::ct::Choice;
5use ic_core::traits::{Algorithm, KeyAgreement, SelfTest};
6use ic_core::{ensure, Result};
7
8/// The RFC 7748 base point, `u = 9`.
9const BASEPOINT: [u8; 32] = {
10    let mut b = [0u8; 32];
11    b[0] = 9;
12    b
13};
14
15/// X25519, the Diffie-Hellman function on Curve25519.
16pub struct X25519;
17
18impl Algorithm for X25519 {
19    const ID: &'static str = "x25519";
20    const NAME: &'static str = "X25519";
21}
22
23/// Apply the RFC 7748 clamping to a scalar.
24///
25/// Clearing the low three bits kills the small-order component; forcing bit 254
26/// fixes the ladder length so timing does not reveal the scalar's magnitude.
27fn clamp(scalar: &[u8], out: &mut [u8; 32]) {
28    out.copy_from_slice(&scalar[..32]);
29    out[0] &= 248;
30    out[31] &= 127;
31    out[31] |= 64;
32}
33
34/// The Montgomery ladder: compute `scalar * u`.
35///
36/// The loop is fixed at 255 iterations with a constant-time conditional swap,
37/// so neither the number of operations nor their operands depend on the scalar.
38fn ladder(scalar: &[u8; 32], u: &[u8; 32]) -> [u8; 32] {
39    let x1 = Fe::from_bytes(u);
40    let mut x2 = Fe::ONE;
41    let mut z2 = Fe::ZERO;
42    let mut x3 = x1;
43    let mut z3 = Fe::ONE;
44    let mut swap = Choice::FALSE;
45
46    for pos in (0..255).rev() {
47        let bit = Choice::from_u8((scalar[pos / 8] >> (pos & 7)) & 1);
48        swap = Choice::from_u8(swap.unwrap_u8() ^ bit.unwrap_u8());
49        Fe::cswap(&mut x2, &mut x3, swap);
50        Fe::cswap(&mut z2, &mut z3, swap);
51        swap = bit;
52
53        let a = x2.add(&z2);
54        let b = x2.sub(&z2);
55        let aa = a.square();
56        let bb = b.square();
57        let e = aa.sub(&bb);
58        let c = x3.add(&z3);
59        let d = x3.sub(&z3);
60        let da = d.mul(&a);
61        let cb = c.mul(&b);
62
63        x3 = da.add(&cb).square();
64        z3 = x1.mul(&da.sub(&cb).square());
65        x2 = aa.mul(&bb);
66        // RFC 7748 writes this as E * (AA + 121665*E). Expanding both forms
67        // gives 121666*AA - 121665*BB, so the 121666 variant below is the same
68        // value with the multiplier the field module already provides.
69        z2 = e.mul(&bb.add(&e.mul121666()));
70    }
71
72    Fe::cswap(&mut x2, &mut x3, swap);
73    Fe::cswap(&mut z2, &mut z3, swap);
74    x2.mul(&z2.invert()).to_bytes()
75}
76
77impl KeyAgreement for X25519 {
78    const PRIVATE_KEY_LEN: usize = 32;
79    const PUBLIC_KEY_LEN: usize = 32;
80    const SHARED_SECRET_LEN: usize = 32;
81
82    fn public_key(private_key: &[u8], out: &mut [u8]) -> Result<()> {
83        ic_core::module::operational()?;
84        ensure!(private_key.len() == 32, InvalidLength, "x25519 private key");
85        ensure!(out.len() == 32, InvalidLength, "x25519 public key buffer");
86        let mut k = [0u8; 32];
87        clamp(private_key, &mut k);
88        out.copy_from_slice(&ladder(&k, &BASEPOINT));
89        Ok(())
90    }
91
92    fn agree(private_key: &[u8], peer_public_key: &[u8], out: &mut [u8]) -> Result<()> {
93        ic_core::module::operational()?;
94        ensure!(private_key.len() == 32, InvalidLength, "x25519 private key");
95        ensure!(
96            peer_public_key.len() == 32,
97            InvalidLength,
98            "x25519 public key"
99        );
100        ensure!(
101            out.len() == 32,
102            InvalidLength,
103            "x25519 shared secret buffer"
104        );
105
106        let mut k = [0u8; 32];
107        clamp(private_key, &mut k);
108        let mut u = [0u8; 32];
109        u.copy_from_slice(peer_public_key);
110
111        let shared = ladder(&k, &u);
112
113        // RFC 7748 §6.1: an all-zero shared secret means the peer supplied a
114        // small-order point. Rejecting it stops a peer from forcing a known
115        // secret, which matters for any protocol that does not hash a
116        // transcript over the public keys.
117        ensure!(
118            !bool::from(ic_core::ct::is_zero(&shared)),
119            InvalidParameter,
120            "x25519 peer public key has small order"
121        );
122        out.copy_from_slice(&shared);
123        Ok(())
124    }
125}
126
127impl SelfTest for X25519 {
128    fn self_test() -> Result<()> {
129        // RFC 7748 §6.1: Alice's key pair.
130        let mut sk = [0u8; 32];
131        ic_core::codec::hex_decode(
132            b"77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a",
133            &mut sk,
134        )?;
135        let mut want = [0u8; 32];
136        ic_core::codec::hex_decode(
137            b"8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a",
138            &mut want,
139        )?;
140        let mut got = [0u8; 32];
141        <Self as KeyAgreement>::public_key(&sk, &mut got)?;
142        ensure!(ic_core::ct::verify(&want, &got), SelfTestFailed, "x25519");
143        Ok(())
144    }
145}
146
147#[cfg(test)]
148mod tests {
149    use super::*;
150    use ic_core::codec::{hex, unhex};
151
152    /// RFC 7748 §5.2, first scalar-multiplication vector.
153    #[test]
154    fn rfc7748_scalar_mult_vector_1() {
155        let k = unhex("a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4").unwrap();
156        let u = unhex("e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c").unwrap();
157        let mut sk = [0u8; 32];
158        clamp(&k, &mut sk);
159        let mut up = [0u8; 32];
160        up.copy_from_slice(&u);
161        assert_eq!(
162            hex(&ladder(&sk, &up)),
163            "c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552"
164        );
165    }
166
167    /// RFC 7748 §5.2, second vector.
168    #[test]
169    fn rfc7748_scalar_mult_vector_2() {
170        let k = unhex("4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d").unwrap();
171        let u = unhex("e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493").unwrap();
172        let mut sk = [0u8; 32];
173        clamp(&k, &mut sk);
174        let mut up = [0u8; 32];
175        up.copy_from_slice(&u);
176        assert_eq!(
177            hex(&ladder(&sk, &up)),
178            "95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957"
179        );
180    }
181
182    /// RFC 7748 §6.1, the full Diffie-Hellman exchange.
183    #[test]
184    fn rfc7748_diffie_hellman() {
185        let a_sk =
186            unhex("77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a").unwrap();
187        let b_sk =
188            unhex("5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb").unwrap();
189
190        let mut a_pk = [0u8; 32];
191        let mut b_pk = [0u8; 32];
192        X25519::public_key(&a_sk, &mut a_pk).unwrap();
193        X25519::public_key(&b_sk, &mut b_pk).unwrap();
194        assert_eq!(
195            hex(&a_pk),
196            "8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a"
197        );
198        assert_eq!(
199            hex(&b_pk),
200            "de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f"
201        );
202
203        let mut s1 = [0u8; 32];
204        let mut s2 = [0u8; 32];
205        X25519::agree(&a_sk, &b_pk, &mut s1).unwrap();
206        X25519::agree(&b_sk, &a_pk, &mut s2).unwrap();
207        assert_eq!(s1, s2);
208        assert_eq!(
209            hex(&s1),
210            "4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742"
211        );
212    }
213
214    #[test]
215    fn rejects_small_order_points() {
216        let sk = [0x11u8; 32];
217        let mut out = [0u8; 32];
218        // The identity and the other RFC 7748 small-order points.
219        for bad in [
220            "0000000000000000000000000000000000000000000000000000000000000000",
221            "0100000000000000000000000000000000000000000000000000000000000000",
222            "e0eb7a7c3b41b8ae1656e3faf19fc46ada098deb9c32b1fd866205165f49b800",
223            "5f9c95bca3508c24b1d0b1559c83ef5b04445cc4581c8e86d8224eddd09f1157",
224            "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
225        ] {
226            let pk = unhex(bad).unwrap();
227            assert!(
228                X25519::agree(&sk, &pk, &mut out).is_err(),
229                "small-order point {bad} must be rejected"
230            );
231        }
232    }
233
234    #[test]
235    fn rejects_wrong_lengths() {
236        let mut out = [0u8; 32];
237        assert!(X25519::public_key(&[0u8; 31], &mut out).is_err());
238        assert!(X25519::public_key(&[0u8; 32], &mut out[..31]).is_err());
239        assert!(X25519::agree(&[1u8; 32], &[0u8; 31], &mut out).is_err());
240    }
241
242    /// Clamping must be applied even when the caller passes an unclamped scalar,
243    /// so two scalars differing only in the cleared bits agree.
244    #[test]
245    fn clamping_is_applied_to_caller_scalars() {
246        let mut a = [0x42u8; 32];
247        let mut b = a;
248        a[0] |= 0x07;
249        b[0] &= !0x07;
250        a[31] |= 0x80;
251        b[31] &= 0x7f;
252
253        let mut pa = [0u8; 32];
254        let mut pb = [0u8; 32];
255        X25519::public_key(&a, &mut pa).unwrap();
256        X25519::public_key(&b, &mut pb).unwrap();
257        assert_eq!(pa, pb);
258    }
259
260    #[test]
261    fn self_test_passes() {
262        X25519::self_test().unwrap();
263    }
264}
ic_ec/x25519.rs

ic_ec/
x25519.rs
