diem_crypto/
ed25519.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4// Copyright 2021 Conflux Foundation. All rights reserved.
5// Conflux is free software and distributed under GNU General Public License.
6// See http://www.gnu.org/licenses/
7
8//! This module provides an API for the PureEdDSA signature scheme over the
9//! ed25519 twisted Edwards curve as defined in [RFC8032](https://tools.ietf.org/html/rfc8032).
10//!
11//! Signature verification also checks and rejects non-canonical signatures.
12//!
13//! # Examples
14//!
15//! ```
16//! use diem_crypto::{
17//!     ed25519::*,
18//!     traits::{Signature, SigningKey, Uniform},
19//! };
20//! use diem_crypto_derive::{BCSCryptoHash, CryptoHasher};
21//! use rand::{rngs::StdRng, SeedableRng};
22//! use serde::{Deserialize, Serialize};
23//!
24//! #[derive(Serialize, Deserialize, CryptoHasher, BCSCryptoHash)]
25//! pub struct TestCryptoDocTest(String);
26//! let message = TestCryptoDocTest("Test message".to_string());
27//!
28//! let mut rng: StdRng = SeedableRng::from_seed([0; 32]);
29//! let private_key = Ed25519PrivateKey::generate(&mut rng);
30//! let public_key: Ed25519PublicKey = (&private_key).into();
31//! let signature = private_key.sign(&message);
32//! assert!(signature.verify(&message, &public_key).is_ok());
33//! ```
34//! **Note**: The above example generates a private key using a private function
35//! intended only for testing purposes. Production code should find an alternate
36//! means for secure key generation.
37#![allow(clippy::integer_arithmetic)]
38
39use crate::{
40    hash::{CryptoHash, CryptoHasher},
41    traits::*,
42};
43use anyhow::{anyhow, Result};
44use core::convert::TryFrom;
45use diem_crypto_derive::{
46    DeserializeKey, SerializeKey, SilentDebug, SilentDisplay,
47};
48use mirai_annotations::*;
49use serde::Serialize;
50use std::{cmp::Ordering, fmt};
51
52/// The length of the Ed25519PrivateKey
53pub const ED25519_PRIVATE_KEY_LENGTH: usize = ed25519_dalek::SECRET_KEY_LENGTH;
54/// The length of the Ed25519PublicKey
55pub const ED25519_PUBLIC_KEY_LENGTH: usize = ed25519_dalek::PUBLIC_KEY_LENGTH;
56/// The length of the Ed25519Signature
57pub const ED25519_SIGNATURE_LENGTH: usize = ed25519_dalek::SIGNATURE_LENGTH;
58
59/// The order of ed25519 as defined in [RFC8032](https://tools.ietf.org/html/rfc8032).
60const L: [u8; 32] = [
61    0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2,
62    0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
63    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
64];
65
66/// An Ed25519 private key
67#[derive(DeserializeKey, SerializeKey, SilentDebug, SilentDisplay)]
68pub struct Ed25519PrivateKey(ed25519_dalek::SecretKey);
69
70#[cfg(feature = "assert-private-keys-not-cloneable")]
71static_assertions::assert_not_impl_any!(Ed25519PrivateKey: Clone);
72
73#[cfg(any(test, feature = "cloneable-private-keys"))]
74impl Clone for Ed25519PrivateKey {
75    fn clone(&self) -> Self {
76        let serialized: &[u8] = &(self.to_bytes());
77        Ed25519PrivateKey::try_from(serialized).unwrap()
78    }
79}
80
81/// An Ed25519 public key
82#[derive(DeserializeKey, Clone, SerializeKey)]
83pub struct Ed25519PublicKey(ed25519_dalek::PublicKey);
84
85#[cfg(mirai)]
86use crate::tags::ValidatedPublicKeyTag;
87#[cfg(not(mirai))]
88struct ValidatedPublicKeyTag {}
89
90/// An Ed25519 signature
91#[derive(DeserializeKey, Clone, SerializeKey)]
92pub struct Ed25519Signature(ed25519_dalek::Signature);
93
94impl Ed25519PrivateKey {
95    /// The length of the Ed25519PrivateKey
96    pub const LENGTH: usize = ed25519_dalek::SECRET_KEY_LENGTH;
97
98    /// Serialize an Ed25519PrivateKey.
99    pub fn to_bytes(&self) -> [u8; ED25519_PRIVATE_KEY_LENGTH] {
100        self.0.to_bytes()
101    }
102
103    /// Deserialize an Ed25519PrivateKey without any validation checks apart
104    /// from expected key size.
105    fn from_bytes_unchecked(
106        bytes: &[u8],
107    ) -> std::result::Result<Ed25519PrivateKey, CryptoMaterialError> {
108        match ed25519_dalek::SecretKey::from_bytes(bytes) {
109            Ok(dalek_secret_key) => Ok(Ed25519PrivateKey(dalek_secret_key)),
110            Err(_) => Err(CryptoMaterialError::DeserializationError),
111        }
112    }
113
114    /// Private function aimed at minimizing code duplication between sign
115    /// methods of the SigningKey implementation. This should remain private.
116    fn sign_arbitrary_message(&self, message: &[u8]) -> Ed25519Signature {
117        let secret_key: &ed25519_dalek::SecretKey = &self.0;
118        let public_key: Ed25519PublicKey = self.into();
119        let expanded_secret_key: ed25519_dalek::ExpandedSecretKey =
120            ed25519_dalek::ExpandedSecretKey::from(secret_key);
121        let sig = expanded_secret_key.sign(message.as_ref(), &public_key.0);
122        Ed25519Signature(sig)
123    }
124}
125
126impl Ed25519PublicKey {
127    /// Serialize an Ed25519PublicKey.
128    pub fn to_bytes(&self) -> [u8; ED25519_PUBLIC_KEY_LENGTH] {
129        self.0.to_bytes()
130    }
131
132    /// Deserialize an Ed25519PublicKey without any validation checks apart from
133    /// expected key size.
134    pub(crate) fn from_bytes_unchecked(
135        bytes: &[u8],
136    ) -> std::result::Result<Ed25519PublicKey, CryptoMaterialError> {
137        match ed25519_dalek::PublicKey::from_bytes(bytes) {
138            Ok(dalek_public_key) => Ok(Ed25519PublicKey(dalek_public_key)),
139            Err(_) => Err(CryptoMaterialError::DeserializationError),
140        }
141    }
142
143    /// Deserialize an Ed25519PublicKey from its representation as an x25519
144    /// public key, along with an indication of sign. This is meant to
145    /// compensate for the poor key storage capabilities of key management
146    /// solutions, and NOT to promote double usage of keys under several
147    /// schemes, which would lead to BAD vulnerabilities.
148    ///
149    /// Arguments:
150    /// - `x25519_bytes`: bit representation of a public key in clamped
151    ///   Montgomery form, a.k.a. the x25519 public key format.
152    /// - `negative`: whether to interpret the given point as a negative point,
153    ///   as the Montgomery form erases the sign byte. By XEdDSA convention, if
154    ///   you expect to ever convert this back to an x25519 public key, you
155    ///   should pass `false` for this argument.
156    #[cfg(test)]
157    pub(crate) fn from_x25519_public_bytes(
158        x25519_bytes: &[u8], negative: bool,
159    ) -> Result<Self, CryptoMaterialError> {
160        if x25519_bytes.len() != 32 {
161            return Err(CryptoMaterialError::DeserializationError);
162        }
163        let key_bits = {
164            let mut bits = [0u8; 32];
165            bits.copy_from_slice(x25519_bytes);
166            bits
167        };
168        let mtg_point = curve25519_dalek::montgomery::MontgomeryPoint(key_bits);
169        let sign = if negative { 1u8 } else { 0u8 };
170        let ed_point = mtg_point
171            .to_edwards(sign)
172            .ok_or(CryptoMaterialError::DeserializationError)?;
173        Ed25519PublicKey::try_from(&ed_point.compress().as_bytes()[..])
174    }
175}
176
177impl Ed25519Signature {
178    /// The length of the Ed25519Signature
179    pub const LENGTH: usize = ed25519_dalek::SIGNATURE_LENGTH;
180
181    /// Serialize an Ed25519Signature.
182    pub fn to_bytes(&self) -> [u8; ED25519_SIGNATURE_LENGTH] {
183        self.0.to_bytes()
184    }
185
186    /// Deserialize an Ed25519Signature without any validation checks
187    /// (malleability) apart from expected key size.
188    pub(crate) fn from_bytes_unchecked(
189        bytes: &[u8],
190    ) -> std::result::Result<Ed25519Signature, CryptoMaterialError> {
191        match ed25519_dalek::Signature::try_from(bytes) {
192            Ok(dalek_signature) => Ok(Ed25519Signature(dalek_signature)),
193            Err(_) => Err(CryptoMaterialError::DeserializationError),
194        }
195    }
196
197    /// return an all-zero signature (for test only)
198    #[cfg(any(test, feature = "fuzzing"))]
199    pub fn dummy_signature() -> Self {
200        Self::from_bytes_unchecked(&[0u8; Self::LENGTH]).unwrap()
201    }
202
203    /// Check for correct size and third-party based signature malleability
204    /// issues. This method is required to ensure that given a valid
205    /// signature for some message under some key, an attacker cannot
206    /// produce another valid signature for the same message and key.
207    ///
208    /// According to [RFC8032](https://tools.ietf.org/html/rfc8032), signatures comprise elements
209    /// {R, S} and we should enforce that S is of canonical form (smaller than
210    /// L, where L is the order of edwards25519 curve group) to prevent
211    /// signature malleability. Without this check, one could add a multiple
212    /// of L into S and still pass signature verification, resulting in
213    /// a distinct yet valid signature.
214    ///
215    /// This method does not check the R component of the signature, because R
216    /// is hashed during signing and verification to compute h = H(ENC(R) ||
217    /// ENC(A) || M), which means that a third-party cannot modify R without
218    /// being detected.
219    ///
220    /// Note: It's true that malicious signers can already produce varying
221    /// signatures by choosing a different nonce, so this method protects
222    /// against malleability attacks performed by a non-signer.
223    pub fn check_malleability(
224        bytes: &[u8],
225    ) -> std::result::Result<(), CryptoMaterialError> {
226        if bytes.len() != ED25519_SIGNATURE_LENGTH {
227            return Err(CryptoMaterialError::WrongLengthError);
228        }
229        if !check_s_lt_l(&bytes[32..]) {
230            return Err(CryptoMaterialError::CanonicalRepresentationError);
231        }
232        Ok(())
233    }
234}
235
236///////////////////////
237// PrivateKey Traits //
238///////////////////////
239
240impl PrivateKey for Ed25519PrivateKey {
241    type PublicKeyMaterial = Ed25519PublicKey;
242}
243
244impl SigningKey for Ed25519PrivateKey {
245    type SignatureMaterial = Ed25519Signature;
246    type VerifyingKeyMaterial = Ed25519PublicKey;
247
248    fn sign<T: CryptoHash + Serialize>(&self, message: &T) -> Ed25519Signature {
249        let mut bytes = <T::Hasher as CryptoHasher>::seed().to_vec();
250        bcs::serialize_into(&mut bytes, &message)
251            .map_err(|_| CryptoMaterialError::SerializationError)
252            .expect("Serialization of signable material should not fail.");
253        Ed25519PrivateKey::sign_arbitrary_message(&self, bytes.as_ref())
254    }
255
256    #[cfg(any(test, feature = "fuzzing"))]
257    fn sign_arbitrary_message(&self, message: &[u8]) -> Ed25519Signature {
258        Ed25519PrivateKey::sign_arbitrary_message(self, message)
259    }
260}
261
262impl Uniform for Ed25519PrivateKey {
263    fn generate<R>(rng: &mut R) -> Self
264    where R: ::rand::RngCore + ::rand::CryptoRng {
265        Ed25519PrivateKey(ed25519_dalek::SecretKey::generate(rng))
266    }
267}
268
269impl PartialEq<Self> for Ed25519PrivateKey {
270    fn eq(&self, other: &Self) -> bool { self.to_bytes() == other.to_bytes() }
271}
272
273impl Eq for Ed25519PrivateKey {}
274
275// We could have a distinct kind of validation for the PrivateKey, for
276// ex. checking the derived PublicKey is valid?
277impl TryFrom<&[u8]> for Ed25519PrivateKey {
278    type Error = CryptoMaterialError;
279
280    /// Deserialize an Ed25519PrivateKey. This method will also check for key
281    /// validity.
282    fn try_from(
283        bytes: &[u8],
284    ) -> std::result::Result<Ed25519PrivateKey, CryptoMaterialError> {
285        // Note that the only requirement is that the size of the key is 32
286        // bytes, something that is already checked during
287        // deserialization of ed25519_dalek::SecretKey
288        // Also, the underlying ed25519_dalek implementation ensures that the
289        // derived public key is safe and it will not lie in a
290        // small-order group, thus no extra check for PublicKey
291        // validation is required.
292        Ed25519PrivateKey::from_bytes_unchecked(bytes)
293    }
294}
295
296impl Length for Ed25519PrivateKey {
297    fn length(&self) -> usize { Self::LENGTH }
298}
299
300impl ValidCryptoMaterial for Ed25519PrivateKey {
301    fn to_bytes(&self) -> Vec<u8> { self.to_bytes().to_vec() }
302}
303
304impl Genesis for Ed25519PrivateKey {
305    fn genesis() -> Self {
306        let mut buf = [0u8; ED25519_PRIVATE_KEY_LENGTH];
307        buf[ED25519_PRIVATE_KEY_LENGTH - 1] = 1;
308        Self::try_from(buf.as_ref()).unwrap()
309    }
310}
311
312//////////////////////
313// PublicKey Traits //
314//////////////////////
315
316// Implementing From<&PrivateKey<...>> allows to derive a public key in a more
317// elegant fashion
318impl From<&Ed25519PrivateKey> for Ed25519PublicKey {
319    fn from(private_key: &Ed25519PrivateKey) -> Self {
320        let secret: &ed25519_dalek::SecretKey = &private_key.0;
321        let public: ed25519_dalek::PublicKey = secret.into();
322        Ed25519PublicKey(public)
323    }
324}
325
326// We deduce PublicKey from this
327impl PublicKey for Ed25519PublicKey {
328    type PrivateKeyMaterial = Ed25519PrivateKey;
329}
330
331impl std::hash::Hash for Ed25519PublicKey {
332    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
333        let encoded_pubkey = self.to_bytes();
334        state.write(&encoded_pubkey);
335    }
336}
337
338// Those are required by the implementation of hash above
339impl PartialEq for Ed25519PublicKey {
340    fn eq(&self, other: &Ed25519PublicKey) -> bool {
341        self.to_bytes() == other.to_bytes()
342    }
343}
344
345impl Eq for Ed25519PublicKey {}
346
347// We deduce VerifyingKey from pointing to the signature material
348// we get the ability to do `pubkey.validate(msg, signature)`
349impl VerifyingKey for Ed25519PublicKey {
350    type SignatureMaterial = Ed25519Signature;
351    type SigningKeyMaterial = Ed25519PrivateKey;
352}
353
354impl fmt::Display for Ed25519PublicKey {
355    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
356        write!(f, "{}", hex::encode(&self.0.as_bytes()))
357    }
358}
359
360impl fmt::Debug for Ed25519PublicKey {
361    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
362        write!(f, "Ed25519PublicKey({})", self)
363    }
364}
365
366impl TryFrom<&[u8]> for Ed25519PublicKey {
367    type Error = CryptoMaterialError;
368
369    /// Deserialize an Ed25519PublicKey. This method will also check for key
370    /// validity, for instance  it will only deserialize keys that are safe
371    /// against small subgroup attacks.
372    fn try_from(
373        bytes: &[u8],
374    ) -> std::result::Result<Ed25519PublicKey, CryptoMaterialError> {
375        // We need to access the Edwards point which is not directly accessible
376        // from ed25519_dalek::PublicKey, so we need to do some custom
377        // deserialization.
378        if bytes.len() != ED25519_PUBLIC_KEY_LENGTH {
379            return Err(CryptoMaterialError::WrongLengthError);
380        }
381
382        let mut bits = [0u8; ED25519_PUBLIC_KEY_LENGTH];
383        bits.copy_from_slice(&bytes[..ED25519_PUBLIC_KEY_LENGTH]);
384
385        let compressed = curve25519_dalek::edwards::CompressedEdwardsY(bits);
386        let point = compressed
387            .decompress()
388            .ok_or(CryptoMaterialError::DeserializationError)?;
389
390        // Check if the point lies on a small subgroup. This is required
391        // when using curves with a small cofactor (in ed25519, cofactor = 8).
392        if point.is_small_order() {
393            return Err(CryptoMaterialError::SmallSubgroupError);
394        }
395
396        // Unfortunately, tuple struct `PublicKey` is private so we cannot
397        // Ok(Ed25519PublicKey(ed25519_dalek::PublicKey(compressed, point)))
398        // and we have to again invoke deserialization.
399        let public_key = Ed25519PublicKey::from_bytes_unchecked(bytes)?;
400        add_tag!(&public_key, ValidatedPublicKeyTag); // This key has gone through validity checks.
401        Ok(public_key)
402    }
403}
404
405impl Length for Ed25519PublicKey {
406    fn length(&self) -> usize { ED25519_PUBLIC_KEY_LENGTH }
407}
408
409impl ValidCryptoMaterial for Ed25519PublicKey {
410    fn to_bytes(&self) -> Vec<u8> { self.0.to_bytes().to_vec() }
411}
412
413//////////////////////
414// Signature Traits //
415//////////////////////
416
417impl Signature for Ed25519Signature {
418    type SigningKeyMaterial = Ed25519PrivateKey;
419    type VerifyingKeyMaterial = Ed25519PublicKey;
420
421    /// Verifies that the provided signature is valid for the provided
422    /// message, according to the RFC8032 algorithm. This strict verification
423    /// performs the recommended check of 5.1.7 §3, on top of the required
424    /// RFC8032 verifications.
425    fn verify<T: CryptoHash + Serialize>(
426        &self, message: &T, public_key: &Ed25519PublicKey,
427    ) -> Result<()> {
428        // Public keys should be validated to be safe against small subgroup
429        // attacks, etc.
430        precondition!(has_tag!(public_key, ValidatedPublicKeyTag));
431        let mut bytes = <T::Hasher as CryptoHasher>::seed().to_vec();
432        bcs::serialize_into(&mut bytes, &message)
433            .map_err(|_| CryptoMaterialError::SerializationError)?;
434        Self::verify_arbitrary_msg(self, &bytes, public_key)
435    }
436
437    /// Checks that `self` is valid for an arbitrary &[u8] `message` using
438    /// `public_key`. Outside of this crate, this particular function should
439    /// only be used for native signature verification in move
440    fn verify_arbitrary_msg(
441        &self, message: &[u8], public_key: &Ed25519PublicKey,
442    ) -> Result<()> {
443        // Public keys should be validated to be safe against small subgroup
444        // attacks, etc.
445        precondition!(has_tag!(public_key, ValidatedPublicKeyTag));
446        Ed25519Signature::check_malleability(&self.to_bytes())?;
447
448        public_key
449            .0
450            .verify_strict(message, &self.0)
451            .map_err(|e| anyhow!("{}", e))
452            .and(Ok(()))
453    }
454
455    /// Batch signature verification as described in the original EdDSA article
456    /// by Bernstein et al. "High-speed high-security signatures". Current
457    /// implementation works for signatures on the same message and it
458    /// checks for malleability.
459    #[cfg(feature = "batch")]
460    fn batch_verify<T: CryptoHash + Serialize>(
461        message: &T,
462        keys_and_signatures: Vec<(Self::VerifyingKeyMaterial, Self)>,
463    ) -> Result<()> {
464        for (_, sig) in keys_and_signatures.iter() {
465            Ed25519Signature::check_malleability(&sig.to_bytes())?
466        }
467        let mut message_bytes = <T::Hasher as CryptoHasher>::seed().to_vec();
468        bcs::serialize_into(&mut message_bytes, &message)
469            .map_err(|_| CryptoMaterialError::SerializationError)?;
470
471        let batch_argument = keys_and_signatures
472            .iter()
473            .map(|(key, signature)| (key.0, signature.0));
474        let (dalek_public_keys, dalek_signatures): (Vec<_>, Vec<_>) =
475            batch_argument.unzip();
476        let message_ref = &(&message_bytes)[..];
477        // The original batching algorithm works for different messages and it
478        // expects as many messages as the number of signatures. In our
479        // case, we just populate the same message to meet dalek's api
480        // requirements.
481        let messages = vec![message_ref; dalek_signatures.len()];
482        ed25519_dalek::verify_batch(
483            &messages[..],
484            &dalek_signatures[..],
485            &dalek_public_keys[..],
486        )
487        .map_err(|e| anyhow!("{}", e))?;
488        Ok(())
489    }
490}
491
492impl Length for Ed25519Signature {
493    fn length(&self) -> usize { ED25519_SIGNATURE_LENGTH }
494}
495
496impl ValidCryptoMaterial for Ed25519Signature {
497    fn to_bytes(&self) -> Vec<u8> { self.to_bytes().to_vec() }
498}
499
500impl std::hash::Hash for Ed25519Signature {
501    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
502        let encoded_signature = self.to_bytes();
503        state.write(&encoded_signature);
504    }
505}
506
507impl TryFrom<&[u8]> for Ed25519Signature {
508    type Error = CryptoMaterialError;
509
510    fn try_from(
511        bytes: &[u8],
512    ) -> std::result::Result<Ed25519Signature, CryptoMaterialError> {
513        Ed25519Signature::check_malleability(bytes)?;
514        Ed25519Signature::from_bytes_unchecked(bytes)
515    }
516}
517
518// Those are required by the implementation of hash above
519impl PartialEq for Ed25519Signature {
520    fn eq(&self, other: &Ed25519Signature) -> bool {
521        self.to_bytes()[..] == other.to_bytes()[..]
522    }
523}
524
525impl Eq for Ed25519Signature {}
526
527impl fmt::Display for Ed25519Signature {
528    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
529        write!(f, "{}", hex::encode(&self.0.to_bytes()[..]))
530    }
531}
532
533impl fmt::Debug for Ed25519Signature {
534    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
535        write!(f, "Ed25519Signature({})", self)
536    }
537}
538
539/// Check if S < L to capture invalid signatures.
540fn check_s_lt_l(s: &[u8]) -> bool {
541    for i in (0..32).rev() {
542        match s[i].cmp(&L[i]) {
543            Ordering::Less => return true,
544            Ordering::Greater => return false,
545            _ => {}
546        }
547    }
548    // As this stage S == L which implies a non canonical S.
549    false
550}
551
552#[cfg(any(test, feature = "fuzzing"))]
553use crate::test_utils::{self, KeyPair};
554
555/// Produces a uniformly random ed25519 keypair from a seed
556#[cfg(any(test, feature = "fuzzing"))]
557pub fn keypair_strategy(
558) -> impl Strategy<Value = KeyPair<Ed25519PrivateKey, Ed25519PublicKey>> {
559    test_utils::uniform_keypair_strategy::<Ed25519PrivateKey, Ed25519PublicKey>(
560    )
561}
562
563#[cfg(any(test, feature = "fuzzing"))]
564use proptest::prelude::*;
565
566#[cfg(any(test, feature = "fuzzing"))]
567impl proptest::arbitrary::Arbitrary for Ed25519PublicKey {
568    type Parameters = ();
569    type Strategy = BoxedStrategy<Self>;
570
571    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
572        crate::test_utils::uniform_keypair_strategy::<
573            Ed25519PrivateKey,
574            Ed25519PublicKey,
575        >()
576        .prop_map(|v| v.public_key)
577        .boxed()
578    }
579}
diem_crypto/ed25519.rs

diem_crypto/
ed25519.rs
