Search
Items tagged with: DholeCryptography
In 2017, cryptography researchers from Kudelski Security demonstrated practical fault attacks against EdDSA (specifically Ed25519; RFC 8032).
Their techniques are also applicable to Deterministic ECDSA (RFC 6979), and potentially work against any deterministic signature scheme (n.b. the Fiat-Shamir or Schnorr distinction isn’t meaningful in this context).
Although that might seem alarming, fault attacks aren’t especially useful for software applications running on general-purpose computers. They’re mostly in the threat models for smartcards and embedded devices.
A recent paper discusses a technique called “hedged” signatures, which I’ve mentioned in A Furry’s Guide to Digital Signature Algorithms.
What is a Hedged Signature?
Let’s just consult the formal definition given by Aranha, et al. in the paper I linked above!
Okay, if you’re not a cryptographer, this is probably clear as mud.
Let’s try a different approach (one that most software engineers will find more intuitive). We’ll start with non-hedged signatures, and then tweak them to become hedged.
Libsodium: Non-Hedged Signatures
Libsodium’s crypto_sign_detached() (which implements Ed25519) accepts two arguments:
- The message being signed.
- The secret key held by the signer.
Libsodium’s congruents crypto_sign_verify_detached() accepts three arguments:
- The detached signature.
- The message.
- The public key (corresponds to the secret key from the other function).
Since libsodium uses Ed25519 under-the-hood, the signature algorithm is deterministic: If you sign the same message with the same secret key, it will always produce the same signature.
Don’t believe me? Try it yourself: https://3v4l.org/lKrJb
Dhole Crypto: Hedged Signatures
Last year when I wrote Dhole Cryptography (in PHP and JavaScript), I decided to implement what would later come to be called “hedged signatures” by cryptographers.
Instead of just signing a message, Dhole Crypto first generates a 256-bit per-message nonce and then signs the nonce and the message together. Then, it appends the nonce to the generated signature (and encodes this as one binary-safe string).
That is to say, the major hack is to change a procedure from this:
function sign(string $message, string $secretKey): string { $signature = sodium_crypto_sign_detached( $message, $secretKey ); return base64_encode($signature);}
…into a procedure that looks like this:
function hsign(string $message, string $secretKey): string { $nonce = random_bytes(32); $signature = sodium_crypto_sign_detached( $nonce . $message, $secretKey ); return base64_encode($signature . $nonce);}
If you pay careful attention to the placement of the nonce in this updated procedure, you’ll notice that it’s backwards compatible with the original libsodium API for Ed25519: crypto_sign() and crypto_sign_open().
Of course, these details are totally abstracted away from the user. Instead, the API looks like this (PHP):
<?phpuse Soatok\DholeCrypto\Asymmetric;use Soatok\DholeCrypto\Key\AsymmetricSecretKey;// Key generation$secret = AsymmetricSecretKey::generate();$public = $secret->getPublicKey();// Signing a message$message = "I certify that you have paid your $350 awoo fine";$sig = Asymmetric::sign($message, $secret);// Verifying a message and signatureif (!Asymmetric::verify($message, $public, $sig)) { die('AWOO FINE UNPAID');}
For JavaScript developers, this may be more intuitive to read:
const { Asymmetric, AsymmetricSecretKey} = require('dhole-crypto');(async function () { let wolfSecret = await AsymmetricSecretKey.generate(); let wolfPublic = wolfSecret.getPublicKey(); let message = "Your $350 awoo fine has been paid UwU"; let signature = await Asymmetric.sign(message, wolfSecret); if (!await Asymmetric.verify(message, wolfPublic, signature)) { console.log("Invalid signature. Awoo not authorized."); }})();
Do Hedged Signatures Protect Against Fault Attacks?
Sort of. It really depends on the kind of fault attack the attacker uses.
See Section 5 of the paper for a detailed break-down of the provable security of hedged signatures against XEdDSA (a variant of EdDSA used by the Signal protocol; the EdDSA variants specified in RFC 8032 were not studied in that paper).
However, the exploit explored by Kudelski using simple voltage glitches to break EdDSA in an Arduino device does become significantly more difficult with hedged signatures versus classical EdDSA.
Additionally, if you combine the existing techniques for mitigating fault attacks in embedded software with a protocol that uses hedged signatures, you may push the cost of a successful fault attack to become economically impractical for attackers.
However, it’s demonstrable that Hedged Signatures are at least as secure as Deterministic Signatures:
Even if your hedging suffers from a catastrophic randomness failure and generates the same nonce twice, the actual nonce used within Ed25519 will be derived from the SHA-512 hash of this value, the message, and a secret key.
Consequently, the only way for the internal nonce to repeat is for the message to be the same–which is the same scenario as a Deterministic Signature, which doesn’t let attackers steal your secret key.
What Does This All Mean?
Hedged signatures are at least as safe as Deterministic Signatures, and in some scenarios, offer a greater degree of protection than Deterministic Signatures.
Additionally, it’s very easy to convert a Deterministic Signature scheme into a Hedged Signature Scheme: Just add additional randomness that gets signed as part of the message, then append this randomness to the signature (so the signature can be successfully verified later).
Or, if you’re using a programming language that I publish open source software in, you can just use Dhole Cryptography and not worry about these details.
(Header art by Kyume.)
https://soatok.blog/2020/05/03/hedged-signatures-with-libsodium-using-dhole/
#crypto #cryptography #DholeCryptography #digitalSignatureAlgorithm #Ed25519 #EdDSA #hedgedSignatures #JavaScript #libsodium #openSource #PHP
Let’s talk about digital signature algorithms.Digital signature algorithms are one of the coolest ideas to come out of asymmetric (a.k.a. public-key) cryptography, but they’re so simple and straightforward that most cryptography nerds don’t spend a lot of time thinking about them.
Even though you are more likely to run into a digital signature as a building block (e.g. certificate signatures in TLS) than think about them in isolation (e.g. secure software releases), they’re still really cool and worth learning about.
What’s a Digital Signature?
A digital signature is some string that proves that a specific message was signed by some specific entity in possession of the secret half of an asymmetric key-pair. Digital Signature Algorithms define the process for securely signing and verifying messages with their associated signatures.For example, if I have the following keypair:
- Secret key:
9080a2c7897faeb8526968161695da0f7b3afa2e8e7d8e8369a85547ab48ea05- Public key:
482b8d3430445cdad6b5ce59778e09ab59d099120f32d316e881db1a6330390bI can cryptographically sign the message “Dhole Moments: Never a dull moment!” with the above secret key, and it will generate the signature string:
63629779a31b623486145359c6f1d56602d8d9135e4b17fa2ae3667c8947397decd7ae01bfed08645a429f5dee906e87df4e18eefdfff9acb5b1488c9dec800f.If you only have the message, signature string, and my public key, you can verify that I signed the message. But, very crucially, you cannot sign messages and convince someone else that they came from me. (With symmetric authentication schemes, such as HMAC, you can.)
A digital signature algorithm is considered secure if, in order for anyone else to pass off a different message as being signed by me, they would need my secret key to succeed. When this assumption holds true, we say the scheme is secure against existential forgery attacks.
How Do Digital Signatures Work?
Simple answer: They generally combine a cryptographic hash function (e.g. SHA-256) with some asymmetric operation, and the details beyond that are all magic.More complicated answer: That depends entirely on the algorithm in question!
For example, with RSA signatures, you actually encrypt a hash of the message with your secret key to sign the message, and then you RSA-decrypt it with your public key to verify the signature. This is backwards from RSA encryption (where you do the totally sane thing: encrypt with public key, decrypt with secret key).
In contrast, with ECDSA signatures, you’re doing point arithmetic over an elliptic curve (with a per-signature random value).
Yet another class of digital signature algorithms are hash-based signatures, such as SPHINCS+ from the NIST Post-Quantum Cryptography Standardization effort, wherein your internals consist entirely of hash functions (and trees of hash functions, and stream ciphers built with other hash functions).
In all cases, the fundamental principle stays the same: You sign a message with a secret key, and can verify it with a public key.
In the interest of time, I’m not going to dive deep into how each signature algorithm works. That can be the subject of future blog posts (one for each of the algorithms in question).
Quick aside: Cryptographers who stumble across my blog might notice that I deviate from convention a bit. They typically refer to the sensitive half of an asymmetric key pair as a “private key”, but I instead call it a “secret key”.
The main reason for this is that “secret key” can be abbreviated as “sk” and public key can be abbreviated as “pk”, whereas private/public doesn’t share this convenience. If you ever come across their writings and wonder about this discrepancy, I’m breaking away from the norm and their way is more in line with the orthodoxy.
What Algorithms Should I Use?
What algorithm, indeed! (Art by circuitslime)
If you find yourself asking this question, you’re probably dangerously close to rolling your own crypto. If so, you’ll want to hire a cryptographer to make sure your designs aren’t insecure. (It’s extremely easy to design or implement otherwise-secure cryptography in an insecure way.)
Recommended Digital Signature Algorithms
(Update, 2022-05-19): I’ve published a more in-depth treatment of the Elliptic Curve Digital Signature Algorithms a few years after this post was created. A lot of the topics covered by EdDSA and ECDSA are focused on there.EdDSA: Edwards Curve DSA
EdDSA comes in two variants: Ed25519 (widely supported in a lot of libraries and protocols) and Ed448 (higher security level, but not implemented or supported in as many places).The IETF standardized EdDSA in RFC 8032, in an effort related to the standardization of RFC 7748 (titled: Elliptic Curves for Security).
Formally, EdDSA is derived from Schnorr signatures and defined over Edwards curves. EdDSA’s design was motivated by the real-world security failures of ECDSA:
- Whereas ECDSA requires a per-signature secret number (
) to protect the secret key, EdDSA derives the per-signature nonce deterministically from a hash of the secret key and message.
- ECDSA with biased nonces can also leak your secret key through lattice attacks. To side-step this, EdDSA uses a hash function twice the size as the prime (i.e. SHA-512 for Ed25519), which guarantees that the distribution of the output of the modular reduction is unbiased (assuming uniform random inputs).
- ECDSA implemented over the NIST Curves is difficult to implement in constant-time: Complicated point arithmetic rules, point division, etc. EdDSA only uses operations that are easy to implement in constant-time.
For a real-world example of why EdDSA is better than ECDSA, look no further than the Minerva attacks, and the Ed25519 designer’s notes on why EdDSA stood up to the attacks.
The security benefits of EdDSA over ECDSA are so vast that FIPS 186-5 is going to include Ed25519 and Ed448.
Hooray for EdDSA adoption even in federal hellscapes.
This is kind of a big deal! The FIPS standards are notoriously slow-moving, and they’re deeply committed to a sunk cost fallacy on algorithms they previously deemed acceptable for real-world deployment.
RFC 6979: Deterministic ECDSA
Despite EdDSA being superior to ECDSA in virtually every way (performance, security, misuse-resistance), a lot of systems still require ECDSA support for the foreseeable future.If ECDSA is here to stay, we might as well make it suck less in real-world deployments. And that’s exactly what Thomas Pornin did when he wrote RFC 6979: Deterministic Usage of DSA and ECDSA.
(Like EdDSA, Deterministic ECDSA is on its way to FIPS 186-5. Look for it in FIPS-compliant hardware 5 years from now when people actually bother to update their implementations.)
Acceptable Digital Signature Algorithms
ECDSA Signatures
The Elliptic Curve Digital Signature Algorithm (ECDSA) is the incumbent design for signatures. Unlike EdDSA, ECDSA is a more flexible design that has been applied to many different types of curves.This is more of a curse than a blessing, as Microsoft discovered with CVE-2020-0601: You could take an existing (signature, public key) pair with standard curve, explicitly set the generator point equal to the victim’s public key, and set your secret key to 1, and Windows’s cryptography library would think, “This is fine.”
For this reason, cryptographers were generally wary of proposals to add support for Koblitz curves (including secp256k1–the Bitcoin curve) or Brainpool curves into protocols that are totally fine with NIST P-256 (and maybe NIST P-384 if you need it for compliance reasons).
For that reason, if you can’t use EdDSA or RFC 6979, your fallback option is ECDSA with one of those two curves (secp256r1, secp384r1), and making sure that you have access to a reliable cryptographic random number generator.
RSA Signatures
It’s high time the world stopped using RSA.Not just for the reasons that Trail of Bits is arguing (which I happen to agree with), but more importantly:
Replacing RSA with EdDSA (or Deterministic ECDSA) also gives teams an opportunity to practice migrating from one cryptography algorithm suite to another, which will probably be a much-needed experience when quantum computers come along and we’re all forced to migrate to post-quantum cryptography.
Encryption is a bigger risk of being broken by quantum computers than signature schemes: If you encrypt data today, a quantum computer 20 years down the line can decrypt it immediately. Conversely, messages that are signed today cannot be broken until after a quantum computer exists.
That being said, if you only need signatures and not encryption, RSA is still acceptable. If you also need encryption, don’t use RSA for that purpose.
If you can, use PSS padding rather than PKCS#1 v1.5 padding, with SHA-256 or SHA-384. But for signatures (i.e. not encryption), PKCS#1 v1.5 padding is fine.
Dishonorable Mention
DSA Signatures
There’s really no point in using classical DSA, when ECDSA is widely supported and has more ongoing attention from cryptography experts.If you’re designing a system in 2020 that uses DSA, my only question for you is…
WHYYYYYY?! (Art by Khia)
Upcoming Signature Algorithms
Although it is far too early to consider adopting these yet, cryptographers are working on new designs that protect against wider ranges of real-world threats.Let’s briefly look at some of them and speculate wildly about what the future looks like. For fun. Don’t use these yet, unless you have a very good reason to do so.
Digital Signature Research Topics
Hedged Signatures
Above, we concluded that EdDSA and Deterministic ECDSA were generally the best choice (and what I’d recommend for software developers). There is one important caveat: Fault attacks.A fault attack is when you induce a hardware fault into a computer chip, and thereby interfere with the correct functioning of a cryptography algorithm. This is especially relevant to embedded devices and IoT.
The IETF’s CFRG is investigating the use of additional randomization of messages (rather than randomizing signatures) as a safeguard against leaking secret keys through fault injection.
Of course, the Dhole Cryptography Library (my libsodium wrapper for JavaScript and PHP) already provides a form of Hedged Signatures.
If this technique is proven successful at mitigating fault injection attacks, then libsodium users will be able to follow the technique outlined in Dhole Crypto to safeguard their own protocols against fault attacks. Until then, they’re at least as safe as deterministic EdDSA today.
Threshold ECDSA Signatures
Suppose you have a scenario where you want 3-or-more people to have to sign a message before it’s valid. That’s exactly what Threshold ECDSA with Fast Trustless Setup aspires to provide.Although this is mostly being implemented in cryptocurrency projects today, the cryptography underpinnings are fascinating. At worst, this will be one good side-effect to come from blockchain mania.
Post-Quantum Digital Signatures
Hash-Based Signatures
The best hash-based signature schemes are based on the SPHINCS design for one simple reason: It’s stateless.In earlier hash-based digital signatures, such as XMSS, you have to maintain a state of which keys you’ve already used, to prevent attacks. Google’s Adam Langley previously described this as a “huge foot-cannon” for security (although probably okay in some environments, such as an HSM).
Lattice-Based Signatures
There are a lot of post-quantum signature algorithm designs defined over lattice groups, but my favorite lattice-based design is called FALCON. FALCON stands for FAst-Fourier Lattice-based COmpact Signatures Over NTRU.Sign Here, Please
Who knew there would be so much complexity involved with such a simple cryptographic operation? And we didn’t even dive deep on how any of them work.
That’s the problem with cryptography: It’s a fractal of complexity. The more you know about these topics, the deeper the complexity becomes.
But if you’re implementing a protocol today and need a digital signature algorithm, use (in order of preference):
- Ed25519 or Ed448
- ECDSA over NIST P-256 or P-384, with RFC 6979
- ECDSA over NIST P-256 or P-384, without RFC 6979
- RSA (as a last resort)
But most importantly: make sure you have a cryptographer audit your designs.
(Header art by Kyume.)
https://soatok.blog/2020/04/26/a-furrys-guide-to-digital-signature-algorithms/
#crypto #cryptography #DeterministicSignatures #digitalSignatureAlgorithm #ECDSA #Ed25519 #Ed448 #EdDSA #FIPS #FIPS186 #FIPSCompliance #RFC6979 #SecurityGuidance
