The Role of Signatures in Digital Assets and Cryptocurrencies.

If you are reading that article there is a good chance that communication between your browser and the endpoint serving the content is confidential and authenticated using core cryptographic primitives. The level of abstraction is so high that even if you probably have never heard what encryption, signatures, message authentication code is; the job is done: you are browsing end to end securely: external parties cannot read the exchanged content or change content without being detected. In this article we will focus on unwrapping the internals of digital signatures and the role they play in digital assets and cryptocurrencies.

Traditional Signatures

A bank cheque is an order for money transfer from a sender to a receiver - being validated from a bank issuing the cheques. The cheque issuer called the drawer specifies on the cheque the payee to whom the money will be transferred and the amount thereof. The entire procedure is being validated with the hand signature of a drawer on the cheque paper. In an ideal world nothing can go wrong. The receiver of the cheque goes to the bank, the bank validates and proceeds with the money transfer. However, the problem that arises with hand-written signatures is that in a real world the signature is not unique per cheque paper, but instead it is always the same. That allows easy forging of a cheque signature. You wouldn't be very happy if someone tweaks your cheque and add one more 0 at the transferable amount when you act as a drawer.

Digital Signatures

Digital signatures solve the aforementioned problem by binding the message that needs to be signed with the signature itself. Every electronic signature issued for a message is a different bytestream. In contrast, in traditional signatures the object itself is the same handwritten signature for all messages for the same sender. In order someone to forge the electronic signature by changing the signed message it has to break a mathematical hard problem which with the current known infrastructure and knowledge is almost impossible.
The sender specifies its public and secret signing key, makes the public key publicly available and keeps secret its secret signing key.

The signer gives as input to the signature algorithm the message to be signed and the secret signing key. The receiver validates the correctness of the signature with the public verification key, which usually comes in the form of a certificate which binds senders public information with its public key. The binding is a signature from a Certificate Authority on the public key of the sender with its publicly identifiable metadata. In a real infrastructure the security of the protocol does not only rely on the security guarantees of the signature, its secure implementation, secure storage of the secret key and trustworthy communication channels but also and on the security of the CA it self as well. Hacking the CA and issuing malformed certificates can have devastating consequences as attackers can perform man in the middle attacks and impersonating involved parties.

CAs have been hacked multiple times. Some notable examples include Diginotar, Comodo and MonPass

Signatures in Digital Assets

With the advent of distributed ledger technologies and the financial application built on top (i.e: cryptocurrencies) the interest in digital signatures skyrocketed. Digital signatures are the core primitive in a digital asset system, which guarantees ownership of digital assets and prevents double spending: spend more that you actually own. In a cryptocurrency system when Steve wants to send a specific amount of digital asset (e.g: bitcoin) to Laura then Steve signs a bytestream containing a spending input on his own account. Then the miners/validators with publicly available information verify the validity of the signature and according to the underlying consensus mechanism finalize the transaction by adding it as a block on the master distributed ledger.

Flaws in a digital signature can have devastating consequences on the fairness and the security of the system. Due to a possible non-secure secret signing key storage, or a potential flaw on the underlying signing algorithm an adversary can initiate unauthorized transactions, which may never revert back. Three signatures are governing the DLT ecosystem: ECDSA, Schnorr and EdDSA. All those signatures schemes rely on Elliptic curve groups and on mathematical hard underlying problems. Different curves provide different efficiency and security guarantees in general. For example Edward curves are considered as more secure as it is easier to implement them in constant time to avoid side channel attacks due to their generic forms without special cases.
In the rest of the article we will treat the underlying elliptic curve operations and groups as a black box and we will highlight only algebraic equations on top of them. For all described bellow signagures there exists an underlying group \(\mathbb{G}\) of prime order \(q\) where the arithmetic operations are performed. All operations are \(\mod q\) and there exists a hash function \(H\{0,1\}^*\rightarrow \mathbb{Z}_q\)

ECDSA Signature

When Bitcoin network went live Mr Nakamoto decided the underlying signature scheme to be ECDSA.

The first step at the Sign algorithm is crucial. For each signature a secure implementation should sample a new fresh random \(k\). If that is not the case then an adversary seeing two different signatures for different messages can extract the secret signing key (PS3 hack). And if repeating randomness sounds an extreme scenario, only repetition of some bits from \(k\), is enough to extract the remaining randomness with good probabilities.

Another negative point of the signature is that it is not easily compatible with blockchain desired signature byproducts, i.e: multi-signatures, aggregate signatures and MPC protocols. The reason is the non-linear equation to compute the \(s\) part of the signature due to the inverse element \(k^{-1}\).

Last but not least ECDSA is malleable by definition: two different signatures can map to the same message. That is possible because \((r,s)\) and \((r,-s\mod q)\) are successfully validated for a message m. That can be mitigated with an implementation restriction on the form of \(s\) (consider always the smaller \(s\)).

  • Setup(): Output an elliptic curve group \(\mathbb{G}\) of order \(q\) and an element G which generates \(\mathbb{G}\).
  • KeyGen(\(1^{\lambda}\)): Choose uniformly at random \(x\gets \mathbb{Z}_q\). The secret key is \(x\) and the public key \(\mathsf{pk} = G \cdot x\)
  • Sign(m,\(x\))-> \(\sigma\):
    • Pick uniform at random \(k\gets \mathbb{Z}_q\)
    • Compute \(R = k \cdot G\)
    • Let \(R=(r_x,r_y)\)
    • Set \(r = r_x\)
    • s = \(k^{-1}(H(m) + x\cdot r)\)
    • Output \(\sigma = (r,s)\), if \(r=0\) or \(s=0\) repeat the above steps.
  • Verify(\(\sigma,\mathsf{pk}\)):
    • Compute \(a=H(m)/s =\) and \(b=r/s\)
    • \(u = G \cdot a + G \cdot b\)
    • Let \(u=(u_x,u_y)\)
    • \(r' = u_x\)
    • if \(r==r'\) accept, otherwise reject

Schnorr Signature

Schnorr signature scheme, which by the time Bitcoin started, it was patented; overcomes some of the downpoints of ECDSA. It has a linear form which makes it easier to implement MPC versions thereof but also aggregation and multisignatures come with less efforts. It is not malleable and has stronger theoretical security proof analysis compared with ECDSA. However the need for new randomness is still present, which renders it vulnerable to implementation bugs.

  • Setup(): Output an elliptic curve group \(\mathbb{G}\) of prime order \(q\) and an element G which generates \(\mathbb{G}\).
  • KeyGen(\(1^{\lambda}\)): Choose uniformly at random \(x\gets \mathbb{Z}_q\). The secret key is \(x\) and the public key \(\mathsf{pk} = G \cdot x\)
  • Sign(m,x)-> \(\sigma\):
    • Pick uniform at random \(k\gets \mathbb{Z}_q\)
    • Compute \(R = k \cdot G\)
    • Let \(R=(r_x,r_y)\)
    • Set \(r = r_x\)
    • s = \(k+H(r||\mathsf{pk}||m) \cdot x\)
    • Output \(\sigma = (r,s)\)
  • Verify(\(\sigma,\mathsf{pk}\)):
    • if \(s\cdot G==R+H(r||\mathsf{pk}||m)\cdot \mathsf{pk}\) accept, otherwise reject

EdDSA Signature

EdDSA removes the need for new randomness for every message. As described below the Sign algorithm–which omits many details–fetches the randomness deterministically from the secret key and the message. Moreover, EdDSA is implemented on Edward curves as Curve25519 and Curve448 which make them easily constant time if implementation is correct and provide more efficient algebra implementation.

  • Setup(): Output an elliptic curve group \(\mathbb{G}\) of prime order \(q\) and an element G which generates \(\mathbb{G}\).
  • KeyGen(\(1^{\lambda}\)): Choose uniformly at random \(x\gets \mathbb{Z}_q\). The secret key is \(x\) and the public key \(\mathsf{pk} = G \cdot x\)
  • Sign(m,\(x\))-> \(\sigma\):
    • Compute \(r = H(H(sk)+m)\)
    • Let \(R=(r_x,r_y)\)
    • Compute \(h = H(R||\mathsf{pk}||m)\)
    • s = \(r+h\cdot\mathsf{sk}\)
    • Output \(\sigma = (r,s)\), if \(r=0\) or \(s=0\) repeat the above steps.
  • Verify(\(\sigma,\mathsf{pk}\)):
    • Compute \(h = H(R||\mathsf{pk}||m)\)
    • \(P_1 = s\cdot G\)
    • \(P_2 = R+h\cdot\mathsf{pk}\)
    • if \(P_1==P_2\) accept, otherwise reject

Conclusion

Cryptography research is growing along with the blockchain ecosystem with prominent primitives being designed, implemented and deployed: Threshold cryptography, zero-knowledge proofs, aggregate signatures, VDF, VRF, distributed random beacons, etc. The amount of work that has been put forth both from research and engineering into digital signatures is exponentially growing the last years. We are witnessing a minimum time gap from protocol description to a POC implementation and production ready cryptographic code.
We will see new signatures substituting the aforementioned; being faster, more secure and easier to implement. Every single step from protocol description to POC to production needs to be reviewed thoroughly as a flaw can cost. Industry will push always to early adoption but cryptographic primitives to become standards will need years. Cryptographic protocols are in the heart of every digital financial system securing digital assets and the best choice will always have trade-offs. A cryptographic protocol does not stand at its own in a production environment. An isolated security analysis thereof is only the first step. Product owners, engineers, QA and devops need to orchestrate with cryptographers to understand the risks of deploying cryptographic code and secure the entire infrastructure from potential malevolent users. At Parfin we take all the required steps to deploy production ready cryptographic protocols for financial institutions.

Select a repo