Crypto.Sign.Ed25519

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

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'.

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.

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.

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?

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).