Description
I'm writing to inform you of a bad implementation of the BLS signature algorithm in Hyperledger Indy. Hyperledger Indy uses the BLS signature for their consensus algorithm for the ledger. These signatures are created by each node in the ledger pool and aggregated for verification, state proofs and proofs of possession to prevent rogue key attacks. Because the BLS signature was not implemented in any library, Indy implemented the BLS signature over the BN254 curve in its own library. The library code for this is in Indy-crypto in https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/bls/mod.rs.
This common code is used in Indy node and Indy-SDK.
Here is the bug/security problem. All ECC arithmetic operations are supposed to be modulo the curve modulus. For example, if we add field elements A + B, the result is (A+B) mod p.
Instead Indy is using the curve order which is a smaller prime usually denoted as n or q. This results in a reduction of security. BN254 with all the recent attacks, the security level has been reduced to about 100 symmetric bits or a little less. Using the curve order lowers this even more. By Hasse's theorem, the number of points on an elliptic curve is less than 2 \sqrt(p), where p is the order of the field that the elliptic curve is over. So the security level could be less than 80 which is in the range where brute force attacks become viable. Starting here https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/pair/amcl.rs#L402, you can see further down the code they are using the CURVE_ORDER instead of MODULUS. This is not according to the spec as defined at https://eprint.iacr.org/2018/483 and https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html. They are also not using an approved hash to curve algorithm which means an attacker could use timing attacks to extract private keys during signing operations. Here are the code spots where they are hashing https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/bls/mod.rs#L496 and https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/pair/amcl.rs#L191. They are computing SHA256 of the message then looping while adding 1 to the hash until a valid curve point is found. While not entirely bad, it's not constant time and https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/?include_text=1 is now considered the preferred method.
The fix cryptographically is quite simple, change CURVE_ORDER to MODULUS. Ursa has this fix in its amcl_wrapper crate and implemented at https://github.com/hyperledger/ursa/blob/master/libursa/src/signatures/bls.rs
However, this fix will break compatibility going forward. Old signatures will still rely on being modulo CURVE_ORDER vs MODULUS. Indy consumers will have to decide if they want to replace all existing transactions with the fix or checkout the ledger and move forward with new ones while supporting the old ones. The latter case will probably be acceptable. I have reviewed this with 3 cryptographers (Hart Montgomery, Mike Hamburg, and Thomas Pornin) who all agree this is very bad and are surprised it even works at all.
My recommendation is that Indy move as quickly as possible to adopt Ursa and replace its dependency on Indy-crypto for all new BLS signatures. Existing deployments should checkout their ledger once the fix is in place and only use the old code to verify old transactions if needed.
This also affects revocation registry signatures and revocation credential signatures
Description
I'm writing to inform you of a bad implementation of the BLS signature algorithm in Hyperledger Indy. Hyperledger Indy uses the BLS signature for their consensus algorithm for the ledger. These signatures are created by each node in the ledger pool and aggregated for verification, state proofs and proofs of possession to prevent rogue key attacks. Because the BLS signature was not implemented in any library, Indy implemented the BLS signature over the BN254 curve in its own library. The library code for this is in Indy-crypto in https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/bls/mod.rs.
This common code is used in Indy node and Indy-SDK.
Here is the bug/security problem. All ECC arithmetic operations are supposed to be modulo the curve modulus. For example, if we add field elements A + B, the result is (A+B) mod p.
Instead Indy is using the curve order which is a smaller prime usually denoted as n or q. This results in a reduction of security. BN254 with all the recent attacks, the security level has been reduced to about 100 symmetric bits or a little less. Using the curve order lowers this even more. By Hasse's theorem, the number of points on an elliptic curve is less than 2 \sqrt(p), where p is the order of the field that the elliptic curve is over. So the security level could be less than 80 which is in the range where brute force attacks become viable. Starting here https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/pair/amcl.rs#L402, you can see further down the code they are using the CURVE_ORDER instead of MODULUS. This is not according to the spec as defined at https://eprint.iacr.org/2018/483 and https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html. They are also not using an approved hash to curve algorithm which means an attacker could use timing attacks to extract private keys during signing operations. Here are the code spots where they are hashing https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/bls/mod.rs#L496 and https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/pair/amcl.rs#L191. They are computing SHA256 of the message then looping while adding 1 to the hash until a valid curve point is found. While not entirely bad, it's not constant time and https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/?include_text=1 is now considered the preferred method.
The fix cryptographically is quite simple, change CURVE_ORDER to MODULUS. Ursa has this fix in its amcl_wrapper crate and implemented at https://github.com/hyperledger/ursa/blob/master/libursa/src/signatures/bls.rs
However, this fix will break compatibility going forward. Old signatures will still rely on being modulo CURVE_ORDER vs MODULUS. Indy consumers will have to decide if they want to replace all existing transactions with the fix or checkout the ledger and move forward with new ones while supporting the old ones. The latter case will probably be acceptable. I have reviewed this with 3 cryptographers (Hart Montgomery, Mike Hamburg, and Thomas Pornin) who all agree this is very bad and are surprised it even works at all.
My recommendation is that Indy move as quickly as possible to adopt Ursa and replace its dependency on Indy-crypto for all new BLS signatures. Existing deployments should checkout their ledger once the fix is in place and only use the old code to verify old transactions if needed.
This also affects revocation registry signatures and revocation credential signatures