Crypto.Sign.Ed25519

This module provides bindings to the Ed25519 public-key signature system, including detached signatures. The documentation should be self explanatory with complete examples.

Below the basic documentation you'll find API, performance and security notes, which you may want to read carefully before continuing. (Nonetheless, Ed25519 is one of the easiest-to-use signature systems around, and is simple to get started with for building more complex protocols. But the below details are highly educational and should help adjust your expectations properly.)

For more reading on the underlying implementation and theory (including how to get a copy of the Ed25519 software), visit http://ed25519.cr.yp.to. There are two papers that discuss the design of EdDSA/Ed25519 in detail:

• "High-speed high-security signatures" - The original specification by Bernstein, Duif, Lange, Schwabe, and Yang.
• "EdDSA for more curves" - An extension of the original EdDSA specification allowing it to be used with more curves (such as Ed41417, or Ed488), as well as defining the support for message prehashing. The original EdDSA is easily derived from the extended version through a few parameter defaults. (This package won't consider non-Ed25519 EdDSA systems any further.)

A crash course introduction

The simplest use of this library is one where you probably need to sign short messages, so they can be verified independently. That's easily done by first creating a keypair with createKeypair, and using sign to create a signed message. Then, you can distribute your public key and the signed message, and any recipient can verify that message:

>>> (pk, sk) <- createKeypair
>>> let msg = sign sk "Hello world"
>>> verify pk msg
True

This interface is fine if your messages are small and simple binary blobs you want to verify in an opaque manner, but internally it creates a copy of the input message. Often, you'll want the signature independently of the message, and that can be done with dsign and dverify. Naturally, verification fails if the message is incorrect:

>>> (pk, sk) <- createKeypair
>>> let msg = "Hello world" :: ByteString
>>> let sig = dsign sk msg
>>> dverify pk msg sig
True
>>> dverify pk "Hello world" sig
True
>>> dverify pk "Goodbye world" sig
False

Finally, it's worth keeping in mind this package doesn't expose any kind of incremental interface, and signing/verification can be expensive. So, if you're dealing with large inputs, you can hash the input with a robust, fast cryptographic hash, and then sign that (for example, the hash function below could be SHA-512 or BLAKE2b):

>>> (pk, sk) <- createKeypair
>>> msg <- readBigFile "blob.tar.gz" :: IO ByteString
>>> let sig = dsign sk (hash msg)
>>> dverify pk (hash msg) sig
True

See the notes at the bottom of this module for more on message prehashing (as it acts slightly differently in an EdDSA system).

Keypair creation

Ed25519 signatures start off life by having a keypair created, using createKeypair or createKeypairFromSeed_, which gives you back a SecretKey you can use for signing messages, and a PublicKey your users can use to verify you in fact authored the messages.

Ed25519 is a deterministic signature system, meaning that you may always recompute a PublicKey and a SecretKey from an initial, 32-byte input seed. Despite that, the default interface almost all clients will wish to use is simply createKeypair, which uses an Operating System provided source of secure randomness to seed key creation. (For more information, see the security notes at the bottom of this page.)

newtype PublicKey

A PublicKey created by createKeypair.

Since: 0.0.1.0

Constructors

PublicKey

Fields

unPublicKey :: ByteString

Unwrapper for getting the raw ByteString in a PublicKey. In general you should not make any assumptions about the underlying blob; this is only provided for interoperability.

Instances

Eq PublicKey

Ord PublicKey

Show PublicKey

Generic PublicKey

type Rep PublicKey

newtype SecretKey

A SecretKey created by createKeypair. Be sure to keep this safe!

Since: 0.0.1.0

Constructors

SecretKey

Fields

unSecretKey :: ByteString

Unwrapper for getting the raw ByteString in a SecretKey. In general you should not make any assumptions about the underlying blob; this is only provided for interoperability.

Instances

Eq SecretKey

Ord SecretKey

Show SecretKey

Generic SecretKey

type Rep SecretKey

createKeypair :: IO (PublicKey, SecretKey)

Randomly generate a SecretKey and PublicKey for doing authenticated signing and verification. This essentically calls createKeypairFromSeed_ with a randomly generated 32-byte seed, the source of which is operating-system dependent (see security notes below). However, internally it is implemented more efficiently (with less allocations and copies).

If you wish to use your own seed (for design purposes so you may recreate keys, due to high paranoia, or because you have your own source of randomness), please use createKeypairFromSeed_ instead.

Since: 0.0.1.0

createKeypairFromSeed_

Arguments

:: ByteString

32-byte seed

-> Maybe (PublicKey, SecretKey)

Resulting keypair

Generate a deterministic PublicKey and SecretKey from a given 32-byte seed, allowing you to recreate a keypair at any point in time, providing you have the seed available.

If the input seed is not 32 bytes in length, createKeypairFromSeed_ returns Nothing. Otherwise, it always returns Just (pk, sk) for the given seed.

NOTE: This function will replace createKeypairFromSeed in the future.

Since: 0.0.4.0

createKeypairFromSeed

Arguments

:: ByteString

32-byte seed

-> (PublicKey, SecretKey)

Resulting keypair

Deprecated: This function is unsafe as it can fail with an invalid input. Use createKeypairWithSeed_ instead.

Generate a deterministic PublicKey and SecretKey from a given 32-byte seed, allowing you to recreate a keypair at any point in time, providing you have the seed available.

Note that this will error if the given input is not 32 bytes in length, so you must be careful with this input.

Since: 0.0.3.0

toPublicKey

Arguments

:: SecretKey

Any valid SecretKey

-> PublicKey

Corresponding PublicKey

Derive the PublicKey for a given SecretKey. This is a convenience which allows (for example) using createKeypair and only ever storing the returned SecretKey for any future operations.

Since: 0.0.3.0

Signing and verifying messages

By default, the Ed25519 interface computes a signed message given a SecretKey and an input message. A signed message consists of an Ed25519 signature (of unspecified format), followed by the input message. This means that given an input message of M bytes, you get back a message of M+N bytes where N is a constant (the size of the Ed25519 signature blob).

The default interface in this package reflects that. As a result, any time you use sign or verify you will be given back the full input, and then some.

sign

Arguments

:: SecretKey

Signers SecretKey

-> ByteString

Input message

-> ByteString

Resulting signed message

Sign a message with a particular SecretKey. Note that the resulting signed message contains both the message itself, and the signature attached. If you only want the signature of a given input string, please see dsign.

Since: 0.0.1.0

verify

Arguments

:: PublicKey

Signers PublicKey

-> ByteString

Signed message

-> Bool

Verification result

Verifies a signed message against a PublicKey. Note that the input message must be generated by sign (that is, it is the message itself plus its signature). If you want to verify an arbitrary signature against an arbitrary message, please see dverify.

Since: 0.0.1.0

Detached signatures

This package also provides an alternative interface for detached signatures, which is more in-line with what you might traditionally expect from a signing API. In this mode, the dsign and dverify interfaces simply return a constant-sized blob, representing the Ed25519 signature of the input message.

This allows users to independently download, verify or attach signatures to messages in any way they see fit - for example, by providing a tarball file to download, with a corresponding .sig file containing the Ed25519 signature from the author.

newtype Signature

A Signature which is detached from the message it signed.

Since: 0.0.1.0

Constructors

Signature

Fields

unSignature :: ByteString

Unwrapper for getting the raw ByteString in a Signature. In general you should not make any assumptions about the underlying blob; this is only provided for interoperability.

Instances

Eq Signature

Ord Signature

Show Signature

Generic Signature

type Rep Signature

dsign

Arguments

:: SecretKey

Signers SecretKey

-> ByteString

Input message

-> Signature

Message Signature, without the message

Sign a message with a particular SecretKey, only returning the Signature without the message.

Since: 0.0.4.0

dverify

Arguments

:: PublicKey

Signers PublicKey

-> ByteString

Raw input message

-> Signature

Message Signature

-> Bool

Verification result

Verify a message with a detached Signature against a given PublicKey.

Since: 0.0.4.0

Deprecated interface

The below interface is deprecated but functionally equivalent to the above; it simply has "worse" naming and will eventually be removed.

sign'

Arguments

:: SecretKey

Signers SecretKey

-> ByteString

Input message

-> Signature

Message Signature, without the message

Deprecated: sign' will be removed in a future release; use dsign instead.

Sign a message with a particular SecretKey, only returning the Signature without the message. Simply an alias for dsign.

Since: 0.0.1.0

verify'

Arguments

:: PublicKey

Signers PublicKey

-> ByteString

Raw input message

-> Signature

Message Signature

-> Bool

Verification result

Deprecated: verify' will be removed in a future release; use dverify instead.

Verify a message with a detached Signature against a given PublicKey. Simply an alias for dverify.

Since: 0.0.1.0

Security, design and implementation notes

Included below are some notes on the security aspects of the Ed25519 signature system, its implementation and design, this package, and suggestions for how you might use it properly.

EdDSA background and properties

Ed25519 is a specific instantiation of the EdDSA digital signature scheme - a high performance, secure-by-design variant of Schnorr signatures based on "Twisted Edwards Curves" (hence the name EdDSA). The (extended) EdDSA system is defined by an elliptic curve:

ax^2 + y^2 = 1 + d*x^2*y^2

along with several other parameters, chosen by the implementation in question. These parameters include a, d, and a field GF(p) where p is prime. Ed25519 specifically uses d = -121665/121666, a = -1, and the finite field GF((2^155)-19), where (2^155)-19 is a prime number (which is also the namesake of the algorithm in question, as Ed25519). This yields the equation:

-x^2 + y^2 = 1 - (121665/121666)*x^2*y^2

This curve is 'birationally equivalent' to the well-known Montgomery curve 'Curve25519', which means that EdDSA shares the same the difficult problem as Curve25519: that of the Elliptic Curve Discrete Logarithm Problem (ECDLP). Ed25519 is currently still the recommended EdDSA curve for most deployments.

As Ed25519 is an elliptic curve algorithm, the security level (i.e. number of computations taken to find a solution to the ECDLP with the fastest known attacks) is roughly half the key size in bits, as it stands. As Ed25519 features 32-byte keys, the security level of Ed25519 is thus 2^((32*8)/2) = 2^128, far beyond any attacker capability (modulo major breakthroughs for the ECDLP, which would likely catastrophically be applicable to other systems too).

Ed25519 designed to meet the standard notion of unforgeability for a public-key signature scheme under chosen-message attacks. This means that even should the attacker be able to request someone sign any arbitrary message of their choice (hence chosen-message), they are still not capable of any forgery what-so-ever, even the weakest kind of 'existential forgery'.

Generation of psuedo-random seeds

Seed generation as done by createKeypair uses Operating System provided APIs for generating cryptographically secure psuedo-random data to be used as an Ed25519 key seed. Your own deterministic keys may be generated using createKeypairFromSeed_, provided you have your own cryptographically secure psuedo-random data from somewhere.

On Linux, OS X and other Unix machines, the /dev/urandom device is consulted internally in order to generate random data. In the current implementation, a global file descriptor is used through the lifetime of the program to periodically get psuedo-random data.

On Windows, the CryptGenRandom API is used internally. This does not require file handles of any kind, and should work on all versions of Windows. (Windows may instead use RtlGenRandom in the future for even less overhead.)

In the future, there are plans for this package to internally take advantage of better APIs when they are available; for example, on Linux 3.17 and above, getrandom(2) provides psuedo-random data directly through the internal pool provided by /dev/urandom, without a file descriptor. Similarly, OpenBSD provides the arc4random(3) family of functions, which internally uses a data generator based on ChaCha20. These should offer somewhat better efficiency, and also avoid file-descriptor exhaustion attacks which could lead to denial of service in some scenarios.

Performance and implementation

Ed25519 is exceptionally fast, although the implementation provided by this package is not the fastest possible implementation. Indeed, it is rather slow, even by non-handwritten-assembly standards of speed. That said, it should still be competitive with most other signature schemes: the underlying implementation is ref10 from SUPERCOP, authored by Daniel J. Bernstein, which is within the realm of competition against some assembly implementations (only 2x slower), and much faster than the slow reference implementation (25x slower). When up against RSA signatures (ronald3072) on a modern Intel machine, it is still 15x faster at signing messages at the same 128-bit security level.

On the author's Sandy Bridge i5-2520M 2.50GHz CPU, the benchmarking code included with the library reports the following numbers for the Haskell interface:

benchmarking deterministic key generation
time                 250.0 μs   (249.8 μs .. 250.3 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 250.0 μs   (249.9 μs .. 250.2 μs)
std dev              467.0 ns   (331.7 ns .. 627.9 ns)

benchmarking signing a 256 byte message
time                 273.2 μs   (273.0 μs .. 273.4 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 273.3 μs   (273.1 μs .. 273.5 μs)
std dev              616.2 ns   (374.1 ns .. 998.8 ns)

benchmarking verifying a signature
time                 635.7 μs   (634.6 μs .. 637.3 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 635.4 μs   (635.0 μs .. 636.0 μs)
std dev              1.687 μs   (999.3 ns .. 2.487 μs)

benchmarking roundtrip 256-byte sign/verify
time                 923.6 μs   (910.0 μs .. 950.6 μs)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 913.2 μs   (910.6 μs .. 923.0 μs)
std dev              15.93 μs   (1.820 μs .. 33.72 μs)

In the future, this package will hopefully provide an opt-in (or possibly default) implementation of ed25519-donna, which should dramatically increase speed at no cost for many/all platforms.

Secure SecretKey storage

By default, keys are not encrypted in any meaningful manner with any mechanism, and this package does not provide any means of doing so. As a result, your secret keys are only as secure as the computing environment housing them - a server alone out on the hostile internet, or a USB stick that's susceptable to theft.

If you wish to add some security to your keys, a very simple and effective way is to add a password to your SecretKey with a KDF and a hash. How does this work?

• First, hash the secret key you have generated. Use this as a checksum of the original key. Truncating this hash to save space is acceptable; see below for more details and boring hemming and hawing.
• Given an input password, use a KDF to stretch it to the length of a SecretKey.
• XOR the SecretKey bytewise, directly with the output of your chosen KDF.
• Attach the checksum you generated to the resulting encrypted key, and store it as you like.

In this mode, your key is XOR'd with the psuedo-random result of a KDF, which will stretch simple passwords like "I am the robot" into a suitable amount of psuedo-random data for a given secret key to be encrypted with. Decryption is simply the act of taking the password, generating the psuedo-random stream again, XORing the key bytewise, and validating the checksum. In this sense, you are simply using a KDF as a short stream cipher.

Recommendation: Encrypt keys by stretching a password with scrypt (or yescrypt), using better-than-default parameters. (These being N = 2^14, r = 8, p = 1; the default results in 16mb of memory per invocation, and this is the recommended default for 'interactive systems'; signing keys may be loaded on-startup for some things however, so it may be profitable to increase security as well as memory use in these cases. For example, at N = 2^18, r = 10 and p = 2, you'll get 320mb of memory per use, which may be acceptable for dramatic security increases. See elsewhere for exact memory use.) Checksums may be computed with an exceptionally fast hash such as BLAKE2b.

Bonus points: Print that resulting checksum + key out on a piece of paper (~100 bytes, tops), and put that somewhere safe.

Q: What is the hash needed for? A: A simple file integrity check. Rather than invoke complicated methods of verifying if an ed25519 keypair is valid (as it is simply an opaque binary blob, for all intents and purposes), especially after 'streaming decryption', it's far easier to simply compute and compare against a checksum of the original to determine if decryption with your password worked.

Q: Wait, why is it OK to truncate the hash here? That sounds scary. Won't that open up collisions or something like that if they stole my encrypted key? A: No. The hash in this case is only used as a checksum to see if the password is legitimate after running the KDF and XORing with the result. Think about how the 'challenge' itself is chosen: if you know H(m), do you want to find m itself, or simply find m' where H(m') = H(m)? To forge a signature, you want the original key, m. Suppose given an input of 256-bits, we hashed it and truncated to one bit. Finding collisions would be easy: you would only need to try a few times to find a collision or preimage. But you probably found m' such that H(m') = H(m) - you didn't necessarily find m itself. In this sense, finding collisions or preimages of the hash is not useful to the attacker, because you must find the unique m.

Q: Okay, why use hashes at all? Why not CRC32? A: You could do that, it wouldn't change much. You can really use any kind of error detecting code you want. The thing is, some hashes such as BLAKE2 are very fast in things like software (not every CPU has CRC instructions, not all software uses CRC instructions), and you're likely to already have a fast, modern hash function sitting around anyway if you're signing stuff with Ed25519. Why not use it?

Prehashing and large input messages

Message prehashing (although not an official term in any right) is the idea of first taking an input x, using a cryptographically secure hash function H to calculate y = H(x), and then generating a signature via Sign(secretKey, y). The idea is that signing is often expensive, while hashing is often extremely fast. As a result, signing the hash of a message (which should be indistinguishable from a truly random function) is often faster than simply signing the full message alone, and in larger cases can save a significant amount of CPU cycles. However, internally Ed25519 uses a hash function H already to hash the input message for computing the signature. Thus, there is a question - is it appropriate or desireable to hash the input already if this is the case?

Generally speaking, it's OK to prehash messages before giving them to Ed25519. However, there is a caveat. In the paper "EdDSA for more curves", the authors of the original EdDSA enhance the specification by extending it with a message prehash function, H', along with an internal hash H. Here, the prehash H' is simply applied to the original message first before anything else. The original EdDSA specification (and the implementation in this package) was a trivial case of this enhancement: it was implicit that H' is simply the identity function. We call the case where H' is the identity function PureEdDSA, while the case where H' is a cryptographic hash function is known as HashEdDSA. (Thus, the interfaces sign and dsign implement PureEdDSA - while they can be converted to HashEdDSA by simply hashing the ByteString first with some other function.)

However, the authors note that HashEdDSA suffers from a weakness that PureEdDSA does not - PureEdDSA is resiliant to collision attacks in the underlying hash function H, while HashEdDSA is vulnerable to collisions in H'. This is an important distinction. Assume that the attacker finds a collision such that H'(x) = H'(y), and then gets convinces a signer to HashEdDSA-sign x - the attacker may then forge this signature and use it as the same signature as for the message y. For a hash function of N-bits of output, a collision attack takes roughly 2^(N/2) operations.

Ed25519 internally sets H = SHA-512 anyway, which has no known collision attacks or weaknesses in any meaningful sense. It is however slower compared to other, more modern hash functions, and is used on the input message in its entirety (and there are no plans to switch the internal implementation of this package, or the standard Ed25519 away from H = SHA-512).

But note: all other hash-then-sign constructions suffer from this, in the sense they are all vulnerable to collision attacks in H', should you prehash the message. In fact, PureEdDSA is unique (as far as I am aware) in that it is immune to collision attacks in H - should a collision be found, it would not suffer from these forgeries. By this view, it's arguable that depending on the HashEdDSA construction (for efficiency or size purposes) when using EdDSA is somewhat less robust, even if SHA-512 or whatever is not very fast. Despite that, just about any modern hash you pick is going to be collision resistant to a fine degree (say, 256 bits of output, therefore collisions 'at best' happen in 2^128 operations), so in practice this robustness issue may not be that big of a deal.

However, the more pertinent issue is that due to the current design of the API which requires the entire blob to sign up front, using the HashEdDSA construction is often much more convenient, faster and sometimes necessary too. For example, when signing very large messages (such as creating a very large tar.gz file which you wish to sign after creation), it is often convenient and possible to use 'incremental' hashing APIs to incrementally consume data blocks from the input in a constant amount of memory. At the end of consumption, you can 'finalize' the data blocks and get back a final N-bit hash, and sign this hash all in a constant amount of memory. With the current API, using PureDSA would require you loading the entire file up front to either sign, or verify it. This is especially unoptimal for possibly smaller, low-memory systems (where decompression, hashing or verification are all best done in constant space if possible).

Beware however, that if you do this sort of incremental hashing for large blobs, you are taking untrusted data and hashing it before checking the signature - be exceptionally careful with data from a possibly untrustworthy source until you can verify the signature.

So, some basic guidelines are:

• If you are simply not worried about efficiency very much, just use PureEdDSA (i.e. just use sign and verify directly).
• If you have lots of small messages, use PureEdDSA (i.e. just use sign and verify directly).

• If you have to sign/verify large messages, possibly in an incremental fashion, use HashEdDSA with a fast hash (i.e. just hash a message before using sign or verify on it).

  • A hash like BLAKE2b is recommended. Fast and very secure.
  • Remember: never touch input data in any form until you are done hashing it and verifying the signature.

As a result, you should be safe hashing your input before passing it to sign or dsign in this library if you desire, and it may save you CPU cycles for large inputs. It should be no different than the typical hash-then-sign construction you see elsewhere, with the same downfalls. Should you do this, an extremely fast-yet-secure hash such as BLAKE2b is recommended, which is even faster than MD5 or SHA-1 (and do not ever use MD5 or SHA-1, on that note - they suffer from collision attacks).