Thesis - Cryptographic Review
- 1 Overview
- 2 Design Review
- 3 Code Review
- 4 Conclusions
- Appendix 1 - References
- Appendix 2 - Disclosure
This document is the result of a design and code review of the cryptographic constructions and algorithms used in the keep network. This cryptographic review was performed as part of the TBTC and keep Audit.
The design review is based on the documents in the keep-core repository [KC20] and the Keep Random Beacon Yellow Paper [KN20]. The review evaluates the soundness of the protocol and the appropriate use of cryptographic elements. It is not a detailed cryptanalysis of the cryptographic algorithms used.
The code review is based on the source code in the keep-core repository. The goal of the code review is to ensure that cryptographic primitives are being used appropriately, and with proper cryptographic hygiene. It does not constitute a formal proof of correctness or an assurance that the code is free of defects. Note that the ECDSA implementation used [KD20] is excluded from this review, and is assumed to be correct.
2 Design Review
2.1 Design Overview
The primary reference for the design review is the Keep Network Yellow Paper [KN20], which describes both the architecture of the random beacon scheme and the ticketing protocol based on the output of the random beacon. The document delineates a number of possible attacks and demonstrates the effectiveness of the protocol at preventing these attacks.
2.2 Design Elements
The Keep Random Beacon is implemented using the GJKR distributed key generation protocol [GJKR99]. While earlier protocols for distributed key generation exist, GJKR was the first to insure that malicious participants cannot influence the final value of the generated private key. GJKR has been widely studied and implemented for over twenty years, with no significant flaws found.
The variant of the GJKR protocol used in the Keep Network modifies the original specification to work over a single shared channel, rather than separate channels between participants. It also adds the ability to explicitly identify participants who violate the protocol. Neither of these changes affect the overall security properties of the protocol which should be comparable in security to the original GJKR scheme.
The signature algorithm used as the basis for the GJKR protocol used here is the Elliptic Curve Digital Signature Algorithm [NIST13]. ECDSA is the established standard for digital signatures on elliptic curves and has been studied and used for many years.
During the design review, it was suggested that the request for a signature should include the actual data being signed instead of just the digest value. Our conclusion is that if an attacker could create false digest and signature pairs from a valid pair that either the underlying signature scheme, or the hash function used, must be broken. Since the security of the protocol assumes the soundness of both the hash algorithm and signature schemes, there is no need to include the preimage.
AltBN_128 Elliptic Curve [YCKS19] is used widely in existing Ethereum applications.
This is an efficient choice of curve and has the appropriate field size to correspond with the other cryptographic algorithms used in the protocol.
No specific cryptographic attacks against the
AltBN_128 curve have been published, but recent mathematical advances [KB16] have raised concerns about its security level. An improved version of the Number Field Sieve specific to the moduli used in pairing-friendly curves has led to the conclusion that
AltBN_128 and similar curves offer approximately 96 bits of security, rather than the expected 128.
This is not a catastrophic attack, and it has yet to be implemented in practice, but it does suggest changes for the future. The broader ethereum community is looking at other pairing-friendly curves with a larger underlying field size, such as the BLS12-381 curve [YCKS19].
There is no need to immediately abandon the
AltBN_128 curve, but cryptographic prudence suggests making the curve implementation as modular as possible. This allows a new curve to be substituted in the future, without difficult modifications to the design and code base.
The signature algorithm relies on the use of a secure hash function, which is assumed to be resistant to both preimage and collision attacks. In this design, the hash function used is the 256-bit variant of the SHA-2 algorithm, part of NIST’s Secure Hash Standard [NIST15].
The use of a 256-bit hash function is appropriate when paired with the
AltBN_128 Elliptic Curve. While collision attacks have been discovered against earlier algorithms in the SHA series [WYY05], SHA2-256 has, to date, provided the expected level of resistance to both preimage and collision attacks.
2.3 Design Recommendations
The use of the
AltBN_128curve should be modularized, as much as possible, to allow an alternate curve to be used in future implementations. This may be required if the use of the
AltBN_128curve is deprecated in Ethereum at some point in the future.
In the Yellow Paper section labeled “Interactive protocol”, the second option for a non-interactive version of the protocol is said to violate requirement 5 for the protocol, but the document only lists 4 requirements. I believe it should specify requirement 4.
3 Code Review
The keep-core repository contains code, in both go and solidity, that implements the system described in the Keep Network Yellow Paper [KN20]. No critical issues were discovered in the course of this review.
The source code modules which use or implement cryptographic operations are listed below, along with some observations on each module.
3.1 Code Modules
This module is an implementation, in go, of the GJKR distributed key generation protocol as specified in the Yellow Paper.
GenerateEphemeralKeyPair()function corresponds properly with Phase 1 of the protocol as defined in the Yellow Paper.
GenerateSymmetricKeys()function corresponds properly with Phase 2 of the protocol as defined in the Yellow Paper.
CalculateMembersSharesAndCommitments()function corresponds properly with Phase 3 of the protocol as defined in the Yellow Paper.
VerifyReceivedSharesAndCommitmentsMessages()function corresponds properly with Phase 4 of the protocol as defined in the Yellow Paper.
ResolveSecretSharesAccusationsMessages()function corresponds properly with Phase 5 of the protocol as defined in the Yellow Paper.
CombineMemberShares()function corresponds properly with Phase 6 of the protocol as defined in the Yellow Paper.
CalculatePublicKeySharePoints()function corresponds properly with Phase 7 of the protocol as defined in the Yellow Paper.
VerifyPublicKeySharePoints()function corresponds properly with Phase 8 of the protocol as defined in the Yellow Paper.
ResolvePublicKeySharePointsAccusationsMessages()function corresponds properly with Phase 9 of the protocol as defined in the Yellow Paper.
RevealMisbehavedMembersKeys()function corresponds properly with Phase 10 of the protocol as defined in the Yellow Paper.
ReconstructMisbehavedIndividualKeys()function corresponds properly with Phase 11 of the protocol as defined in the Yellow Paper.
findPublicKey()function corresponds properly with Phase 12 of the protocol as defined in the Yellow Paper.
This module computes the shared signature.
SignDKGResult()function does proper error checking on both the hash and signature computations
This module implements all the elliptic curve operations, on the
- The Cloudflare library is used for big number arithmetic.
AltBN_128Curve parameters are properly defined.
- The curve operations appear to be correctly implemented.
This module implements the BLS distributed signature algorithm.
Verify()functions invoke the corresponding operations in
RecoverSignature()function does proper validation on the individual shares and threshold testing on the number of shares.
This module generates and manages ECDSA keys.
GenerateKeyPair()function generates the ECDSA key pair for the participants in the protocol.
This module does local signatures using the ECDSA algorithm.
- Local signing and verification of ECDSA signatures is done by the
- Inputs are properly validated, and proper error checking is done in both functions.
This module implements all the elliptic curve operations, in solidity, on the
- An internal library (
/contracts/solidity/contracts/utils/ModUtils.sol) is used for big number arithmetic.
AltBN_128Curve parameters are properly defined.
- The curve operations appear to be correctly implemented.
This module implements the BLS distributed signature algorithm in solidity.
verify()functions invoke the corresponding operations in
3.2 Code Recommendations
No significant issues were identified in this review that would mandate modifications to the code. The design review recommends modularizing the elliptic curve operations, so that new curves might be used in the future. This could be done by creating a “wrapper class” for curve operations, with a curve ID as a class member. This would allow the use of new curves without major modification to all the code using the curves.
No significant issues were found in the cryptographic review of the design and code. The design is clearly and completely specified in the Yellow Paper, and it is a sound application of the widely-studied GJKR signature scheme. The cryptographic primitives used are appropriate and conform to industry best practices. The code is clearly written and the invocations of cryptographic algorithms follow proper cryptographic hygiene in both parameter checking and cleanup.
Appendix 1 - References
[GJKR99] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Advances in Cryptology — EUROCRYPT ’99: International Conference on the Theory and Application of Cryptographic Techniques Prague, Czech Republic, May 2–6, 1999 Proceedings, chapter Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, pages 295–310. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999 ; http://groups.csail.mit.edu/cis/pubs/stasio/vss.ps.gz
[KN20] “The Keep Random Beacon: An Implementation of a Threshold Relay”, https://docs.keep.network/random-beacon/
[NIST13] National Institute of Standards and Technology, “Digital Signature Standard”, FIPS PUB 186-4, https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf, July 2013
[NIST15] National Institute of Standards and Technology, “Secure Hash Standard”, FIPS PUB 180-4, https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf, August 2015
[YCKS19] Yonezawa, Chikara, Kobyashi, and Saito, “Pairing-Friendly Curves”, Internet Draft, https://tools.ietf.org/id/draft-yonezawa-pairing-friendly-curves-00.html, January 2019
[WYY05] Wang, Yin, and Yu, “Finding Collisions in the Full SHA-1”, https://www.iacr.org/archive/crypto2005/36210017/36210017.pdf, August 2005
Appendix 2 - Disclosure
ConsenSys Diligence (“CD”) typically receives compensation from one or more clients (the “Clients”) for performing the analysis contained in these reports (the “Reports”). The Reports may be distributed through other means, including via ConsenSys publications and other distributions.
The Reports are not an endorsement or indictment of any particular project or team, and the Reports do not guarantee the security of any particular project. This Report does not consider, and should not be interpreted as considering or having any bearing on, the potential economics of a token, token sale or any other product, service or other asset. Cryptographic tokens are emergent technologies and carry with them high levels of technical risk and uncertainty. No Report provides any warranty or representation to any Third-Party in any respect, including regarding the bugfree nature of code, the business model or proprietors of any such business model, and the legal compliance of any such business. No third party should rely on the Reports in any way, including for the purpose of making any decisions to buy or sell any token, product, service or other asset. Specifically, for the avoidance of doubt, this Report does not constitute investment advice, is not intended to be relied upon as investment advice, is not an endorsement of this project or team, and it is not a guarantee as to the absolute security of the project. CD owes no duty to any Third-Party by virtue of publishing these Reports.
PURPOSE OF REPORTS The Reports and the analysis described therein are created solely for Clients and published with their consent. The scope of our review is limited to a review of Solidity code and only the Solidity code we note as being within the scope of our review within this report. The Solidity language itself remains under development and is subject to unknown risks and flaws. The review does not extend to the compiler layer, or any other areas beyond Solidity that could present security risks. Cryptographic tokens are emergent technologies and carry with them high levels of technical risk and uncertainty.
CD makes the Reports available to parties other than the Clients (i.e., “third parties”) – on its website. CD hopes that by making these analyses publicly available, it can help the blockchain ecosystem develop technical best practices in this rapidly evolving area of innovation.
LINKS TO OTHER WEB SITES FROM THIS WEB SITE You may, through hypertext or other computer links, gain access to web sites operated by persons other than ConsenSys and CD. Such hyperlinks are provided for your reference and convenience only, and are the exclusive responsibility of such web sites’ owners. You agree that ConsenSys and CD are not responsible for the content or operation of such Web sites, and that ConsenSys and CD shall have no liability to you or any other person or entity for the use of third party Web sites. Except as described below, a hyperlink from this web Site to another web site does not imply or mean that ConsenSys and CD endorses the content on that Web site or the operator or operations of that site. You are solely responsible for determining the extent to which you may use any content at any other web sites to which you link from the Reports. ConsenSys and CD assumes no responsibility for the use of third party software on the Web Site and shall have no liability whatsoever to any person or entity for the accuracy or completeness of any outcome generated by such software.
TIMELINESS OF CONTENT The content contained in the Reports is current as of the date appearing on the Report and is subject to change without notice. Unless indicated otherwise, by ConsenSys and CD.