7 ms·
How to defeat Ed25519 and EdDSA using faults
- loup-vaillant 9y agoCrap, now I have to update my manual¹, and advise the paranoid to verify the signature they just generated. Perhaps even provide a helper function for it? (I still think letting the user control `r` is too dangerous.) [1]: http://loup-vaillant.fr/projects/monocypher/ http://loup-vaillant.fr/projects/monocypher/
- Lery 9y agoYou don't really want to verify the signature you've just generated, if you care about perf, because verification is twice as costly as signing.
- loup-vaillant 9y agoI know, it would slow down the whole thing by a factor of 3. Monocypher can "only" produce 7000 signatures per seconds on a single thread on my laptop (i5 Skylake Intel). With the verification, I would waste a whooping 0.3ms on each signature, reducing the throughput to 2000 signatures per seconds. Unless you're running a signing intensive application on the scale of Let's Encrypt, you won't really care about the slow-down. If you don't fully trust your hardware however, faults might be a real problem.
- rightos 9y agoEven let's encrypt is issuing only a handful of certificates per second. Perhaps it'd matter more if used on a per connection basis.
- tptacek 9y ago1. Nobody is attacking Lets Encrypt with fault attacks. 2. If you can induce faults on Lets Encrypt's signing infrastructure you have better attacks to deploy. 3. Lets Encrypt doesn't use Elliptic Curve in the first place.
- loup-vaillant 9y agoOf course, I was only speculating about the scale required to make several thousands of signature per second. Your second point stands, though. It's probably a waste of CPU to mitigate fault attacks in a Lets Encrypt like use case.
- deleted 9y ago[deleted]
- rightos 9y agoI wasn't suggesting any of those things weren't true, merely a back-of-the-napkin estimate of the sort of load a function like this would be sufficient for.
- wolf550e 9y agoLet's Encrypt use HSMs to sign, and more than 90% of signatures produced are for OCSP, not for issuance. Though I have failed to find the link for this, I saw them publish these numbers.
- marcosdumay 9y agoYet, if you then proceed to send your signed document over a network, for it to be rejected 10 minutes later because of a bad signature and then you have to start from the beginning again, that verification cost is irrelevant.
- loup-vaillant 9y agoHow frequent do you expect failures to be? (That would attack induced failures). There's a threshold below which the "10 minutes later" cost less than wasting 3ms every single time.
- AstralStorm 9y agoIt is much more likely that the fault is due to corruption during data transfer anyway and you get to handle this case.
- db48x 9y agoThe paranoid should be doing that regardless of the algorithm, should they not?
- loup-vaillant 9y agoIt depends on the algorithm. If the algorithm is immune to faults, the worst thing that can happen is that you produce an invalid signature, which will then be rejected. This turns the security concern into a more mundane performance concern.
- dspillett 9y ago> It depends on the algorithm ... If the algorithm is immune to faults The truly paranoid would never believe any algorithm is immune to faults. Even if full mathematical code analysis shows it to be so, can you prove that the proving analysis algorithm itself is immune to faults? It is potentially faulty turtles all the way down!
- loup-vaillant 9y agoThe higher that tower of turtles, the stronger the confidence. The proof checker can be ran several times to account for faults. Then you don't need to run it at all (it's proven). And you can use another proof checker (or that proof checker itself) to prove that the proof checker works. Etc. Now there's the problem of the compiler, which gives a upper bound on the confidence you can have: if there's a bug in it, you're screwed even with a correct algorithm. > Even if full mathematical code analysis shows it to be so Come to think of it, that may not be possible for lots and lots of algorithms —whose mathematical security is only conjectured to begin with. Thanks for pointing that out.
- dspillett 9y agoI expect (though I'm not theoretical mathematician so I'm happy to be told how wrong I am!) any formal proof method will have algorithms that it can't do anything with, and that there will exist those that none can deal with. Presumably there is a code version of Gödel's incompleteness theorems somewhere in Turing's work or similar.
- clawoo 9y agoAnyone have any idea how does this affect Olm[1] (and possible NaCl and libsodium)? I know it uses Ed25519 signatures for both the device fingerprint and the one time pre keys. [1]: https://git.matrix.org/git/olm/about/docs/signing.rst https://git.matrix.org/git/olm/about/docs/signing.rst
- deleted 9y ago[deleted]
- Arathorn 9y agoOn the Matrix side we’re reading through the paper and seeing if/how it applies to Olm.
- tptacek 9y agoWhy would you need to read through the paper to see if it applies? Are you deployed in settings where attackers can physically flip bits or not? That question, the only one that matters, is posed essentially in the abstract of the paper.
- Arathorn 9y agoYup, Olm could conceivably be deployed in settings where attackers could physically flip bits, but we're not aware of anyone doing so yet (all current usage is on non-embedded devices where the hassle of bit flipping would be enormous). Assuming I've correctly skimmed the paper, it looks like it relies on your Ed25519 impl incorrectly reusing the same 'r' value when signing messages - and then deliberately flipping bits whilst it does so, in order to gradually recover the private key. Our usage of Ed25519 doesn't reuse 'r' values, so I think Olm is okay.
- deleted 9y ago[deleted]
- lvh 9y agoThe article acknowledges RFC6979, which is the standard way to produce a deterministic r that doesn't have this problem intrinsically. It also refs RFC8032, which has EdDSA in it (both variants). The fault attack acts after that deterministic generation, so tha fact that Olm doesn't reuse r values explicitly doesn't matter. You're not _erroneously_ reusing r: the attack involves you trying to sign the same message twice, with a fault occurring on the second signing.
- jopsen 9y agoI wonder how long before someone demonstrates fault attacks triggered from a sandbox in the cloud.. I imagine something like rowhammer could be used..
- kerouanton 9y agoThis attack uses physical fault injection, so it shouldn't be trivial for remote attackers to use it, but it definitely is a nice demonstration, and exposes vulnerabilities on chips that generate and store such keys, like maybe pay-tv cards (remember the business of Kudekski/Nagra).
- marcosdumay 9y agoJust a while ago there was a paper here about how to create faults using the CPU's power management features, by software.
- tptacek 9y agoSure, and Rowhammer flips bits from software too. The point here is you need relatively precise control not just in location but in timing of your bit flips to break crypto like this. Rowhammer attackers have the luxury of attacking bits that stay high-value for long periods of time. DFA attackers get very tiny windows.
- zimmerfrei 9y agoNot very long. Flip Feng Shui does exactly that: a malicious program in a VM can affect another one co-hosted in the same cloud server if the hypervisor uses deduplication: https://www.vusec.net/projects/flip-feng-shui/ https://www.vusec.net/projects/flip-feng-shui/
- animal531 9y agoI believe the only way to defeat Ed209 is also through exploiting its faults.
- loup-vaillant 9y agoReferring to its first demo? Really, the engineers were asking for that… "glitch": 1) Failed to test Ed209 on demo conditions (medium sized meeting room). 2) Failed to anticipate the failure of the sound recognition algorithm (gun on on carpet instead of gun on concrete). 3) Failed to implement software failsafes for the demo: a layer on the motor system so it never touches anything (especially moving things such as humans), a weapons system that doesn't actually fire… 4) Failed to implement a proper shut down button, such as a physical plug one could pull from behind. 5) Loaded the damn thing with live ammo.
- meta_AU 9y agoIt has always seemed like a footgun for the algorithm to totally cave if the 'r' value is reused for the same key and different message. This attack uses the deterministic 'r' generation using the key and the message (to ensure that the 'r' is only reused if the message is the same), but then glitches the hash function that is used on the message during signing (so the same'r' is used on a different message). Edit: Removed silly question on why the order has to be 'r' before the second hash. Spolier: Signature is two parts - and at least one needs to be fixed to prevent an forger just modifying both. That needs to be the 'r' part, so it has to be before the S.
- loup-vaillant 9y agoI have another, perhaps less silly question. The way EdDSA works, one needs to hash the message twice, in a way that makes incremental hashing impossible (you need to complete the first pass before you begin the second): r = Hash(secret_key | message) R = Base_point × r H = Hash(R | public_key | message) // use H to compute the signature Because of this, we cannot have a streaming interface. Thus, signing and verifying huge messages is a hassle. I think there are ways to avoid this, if we're willing to mess with EdDSA (I'm not). We could for instance change the second hash to this: H = Hash(public_key | message | R) By appending R to the rest, instead of pre-pending it, we can perform the two hashes in parallel, and use the result of the first hash only for the last bit of the second hash. A more involved tweak would hash the message first: r = Hash(message | secret_key) R = Base_point × r H = Hash(message | R | public_key) That way you can hash the message once, then duplicate the hash context to complete the two hashes. --- Now the question: would those modifications work? Are they still immune to collision attacks? How about length extension attacks? Subsidiary question: if my modifications are secure, how DJB and al didn't think of it? DJB in particular is reputed to be quite performance sensitive.
- cesarb 9y agoShouldn't the "message" being signed by EdDSA (or others like RSA) be a hash of the real data? That way you can do a streaming interface just fine, and the "message" being hashed within EdDSA is small and constant-sized. I think the idea with the ordering of the inputs to the hash functions was to always put the most secret data first, to make things harder for the attacker. It was probably expected that the "message" would always be small, like it must be with for instance RSA.
- pg_is_a_butt 9y agoThe paranoid are only paranoid because they are told how to be paranoid. #fakenews
- tptacek 9y agoThe most important thing to understand about this attack is that it's premised on attackers physically flipping bits, usually in targeted memory locations, during particular phases of computation. Even for attackers with physical access to a device, it's not an easy attack to pull off. It's for the most part not a line of attacks relevant to client/server and cloud software (your cloud provider has less dramatic ways of destroying your security). The textbook example of a setting where fault attacks matter is smart cards: they're computing devices that perform crypto operations and their users are naturally adversarial (the card controls their access to some resource they'd naturally prefer unfettered access to). The crypto in a smart card needs to work even when the custodian of the card is zapping it with lasers. The paper mentions IOT as a setting that will increasingly implicate fault attacks. To some extent, maybe. Most IOT devices aren't adversarial with the people whose custody they're in; in other words, if you can get your hands on an IOT device once deployed, the threat model for that device basically already says you own all the "secrets" in the device. Another pretty important thing to know is that while the paper is interesting, it's not unexpected that DFA attacks would compromise EdDSA; they compromise pretty much everything, don't they? Finally: I think you really don't care what your crypto library has to say about DFA attacks on its EdDSA implementation. All the mainstream implementations will be "vulnerable" to the attack (EdDSA is unworkably slow with the most obvious workaround of checking the signatures you yourself generate). If you need protection against fault attacks in your threat model, you are way past the point where library safeguards will help you. This is probably the point at which you can't responsibly ship products without getting an actual crypto consultancy to sign off on it. These are relatively straightforward attacks, both conceptually (the paper has a pretty useful breakdown of "nine" attacks on EdDSA that are basically the same fundamental attack applied to different phases of the algorithm) and to simulate in software, so if you really want to get your head around it, boot up a Sage shell, get EdDSA working, and just play with fake "bit flips".
- CiPHPerCoder 9y ago> If you need protection against fault attacks in your threat model, you are way past the point where library safeguards will help you. This is probably the point at which you can't responsibly ship products without getting an actual crypto consultancy to sign off on it. I wish there was a way to make comment text bold, because this definitely seems like it needs to be emphasized.
- TurboHaskal 9y agoFor a moment, I thought somebody wrote an article on how to beat edw519's HN karma.