New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Secure comparator is broken #85
Comments
Oh that's funny #83. P.S. You should also test after scalar point multiplication for the zero point or "8*input == zero" because I can give you a point of order 8 for g2a or g2b and achieve the same as a zero point. I pretty sure Ed25519 only has points that are of order 1, 2, 4, 8, and 2^252+27742317777372353535851937790883648493. |
Thank you for pointing this out. We are considering it as part of #83 . Maybe it doesn't make sense to verify g2a or g2b at all, but rather to check the final g2. What do you think? |
That is what I was suggesting. Well g2, g3, Rab, and R but I don't think checking g3, Rab, and R{a,b} is necessary. But I'm too drunk to understand what you are even doing... besides a PAKE algorithm. Have you heard of SPAKE2 (or SPAKE2-EE)? There's also the client-server augmentation: PAKE2+ and PAKE2+EE. Both are much faster and have security proofs. |
Actually, we were considering it for other use-cases we are having from the industry. So far these are more like handling personal data than PAKE or authentication. This is just a building block we want to try out and see whether it will fit their needs. So it is not a full-featured protocol but rather a potential piece in a bigger security structure/protocol. |
... So you don't want to use an algorithm that's better and faster because it covers more use cases? 0_o |
Thank you for your feedback and attention to detail. Shortly, my colleague will return after investigation and you will be able to get back to technical detail. I can answer about general choice and reasoning, however don't think github issue is the right place to discuss such things and my discourse is going to be obvious and boring :) If password auth and speed were the only considerations, there would be much better choices than either SC or PAKE. SC's threat model is seen around 'no possible leakage' both in transport and on verifier side - for some use cases we need mutual authentication, which by design has nothing to leak even to dishonest party (this is the main use case for us, password authentication is just something that came along the way and could be developed from current SC state). When we were planning SC a year ago as a part of larger research, we were not aware of ECC-based SPAKE implementation, and I am still not aware of publicly available security proofs (although seeing work of Mike Hamburg makes me think he knows what to do, @secumod might comment better on that). Moreover, at that point, non-EE SPAKE2 is discrete log problem class with obvious future repercussions to that. We're quite lazy, and remember Schneier's law well, so if there was an instrument, which would fit us - we'd implement it in the first place. |
tl;dr We would like to choose an algorithm for our particular use-cases. It doesn’t make much sense to hammer nails with a screwdriver. P.S. We pushed a fix to the problem you pointed out and would greatly appreciate your comments. |
I assume you are referring to a54f2fe. I think it is still exploitable, however it depends on internals of how ed25519 is implemented, and I have not looked much at that yet. The check for The bottom line is that This would not be a problem in itself, if not for another problem: I think it should be possible to make My advice:
I think that the last one would be sufficient to make the implementation secure against these kinds of attacks however there is not much lost by doing all of them. P.S. You should probably make |
Hmmm. There are more attacks, which libotr protects against, but this implementation does not. One attack is to try and make |
Thanks for your valuable feedback. Good catch for |
Well, you are already computing In any case: Consider the case where Bob sends You have no way of detecting this, that would not simply be adding a lot of special-cases everywhere. I would think that there are more similar attacks possible, which would mean you would require many such special-cases. The way OTR solves this is by having every value include a ZK-proof that it is valid. For instance |
Hmm. After more detailed look I see they use Schnorr signatures everywhere as ZK-proofs. Since ed25519 is a EC variant of Schnorr signature maybe we should just reuse their approach. Will take a look in that direction. |
You will need to design a few primitives yourself, as they also use ZK-proofs for e.g. "I know a But yes, I think it should be doable. If you haven't already, I would suggest reading the first 8 pages of https://www.win.tue.nl/~berry/papers/dam.pdf |
I've ported all ZK-proofs from OTR to ed25519. If you have time, would really appreciate your feedback for #89 |
These lines are broken: if (!ge_cmp(&(comp_ctx->Pp), &(comp_ctx->P))) |
More generally: There are only three types of checks in the OTR implementation and in the original paper:
So almost all of the It turns out that they are not. For instance I have not yet verified whether that check is actually necessary, but I think it is. In any case: Either the check should be there and be done correctly, or it should be removed to reduce complexity. |
So far I removed some of the checks which are probably indeed excessive. The idea behind that is the following:
Would appreciate your comments on #92 |
Closed by #92 (hopefully...) |
The attack is send g2a or g2b as the zero point "(0, 2^255-19+1)"
These won't match this zero point:
themis/src/themis/secure_comparator.c
Line 168 in 50fd35d
themis/src/themis/secure_comparator.c
Line 241 in 50fd35d
The text was updated successfully, but these errors were encountered: