search

decentralized-identity / bbs-signature

The BBS Signature Scheme
https://identity.foundation/bbs-signature/draft-irtf-cfrg-bbs-signatures.html
Apache License 2.0
78 stars 26 forks source link

Preferred method of generating random points #218

Closed mikelodder7 closed 1 year ago

mikelodder7 commented 1 year ago

After inspection of the code, I found some examples where a random scalar is chosen then multiplied by a point. While not inherently insecure, there is the potential side channel attack which allows an attacker to learn the discrete log of the random point.

Going forward I propose our new preferred method for creating random points is to draw random bytes and then use hash to curve. The reasoning is even if an attacker learns the random bytes they still do not learn the discrete log of the point and secondly, if the random data is manipulated or has a specific structure, the hashing effectively destroys this.

tplooker commented 1 year ago

It appears that most of this commentary is related to the example implementation in the tooling section of this repository which isn't meant to be a reference implementation?

BasileiosKal commented 1 year ago

If I understand this proposal correctly, the only place this could be applicable is when multiplying s with Q_1. In any other case, the logarithmic format of the operation matters (e.g., we could not replace A * r1 with hash_to_curve(r1)). Since we also plan to remove s entirely eitherway not sure how useful this approach would be.

Also i don't 100% following the reasoning. The random data is what we try to protect. If an attacker learns them it will not matter that they will not learn the dl of the point. As for the hashing operation destroying structure in the random data, one could just hash the random bytes before multiplying (+ the moding operation should destroy some of the structure eitherway)??

Given that neither hash_to_curve is constant time, IMO expanding a bit the Side channel attacks security consideration to recommend implementation of arithmetic operations (mainly point, scalar multiplication) in constant time should be enough.

BasileiosKal commented 1 year ago

Discussed on WG call on 20th of Mar. Will re-visit and consider closing after 1-2 wg calls

BasileiosKal commented 1 year ago

https://github.com/decentralized-identity/bbs-signature/issues/218#issuecomment-1430634237 @mikelodder7

tplooker commented 1 year ago

@mikelodder7 we believe this issue is addressed, we intend to close on the next WG meeting if we hear no objections.

mikelodder7 commented 1 year ago

Cool let me know if I should look at anything in particular

tplooker commented 1 year ago

The WG considers this issue resolved please review the most recent editorial draft and re-open an issue if you encounter one.