CRYPTOGRAPHY - Signatures
Contents
Signature introduction
At a glance:
- 1976 Idea published by Whit Diffie and Martin Hellman
- 1978 RSA crypto system invented by Rivest, Shamir and Adleman, can be used for encryption and signature
- 1985 ElGamal Signature Scheme invented, later improved by Schnorr
- Today any computationally hard problem can be turned into a signature scheme
- Variants of RSA (RSA-PKCS#1, RSA-PSS) and ElGamal-Schnorr (DSA, ECDSA) dominate applications
By convention, Message Authentication Codes (MACs), generated and verified with the same symmetric key,
are not considered as signatures. They do not provide the property of non-repudiation.
Signature scheme
A signature scheme is usually defined as a triplet of algorithms (K; S; V ), where
- K is the Key generation algorithm,
- S is the Signing algorithm and
- V is the Verification algorithm.
K generates pairs (s; v) of keys for the Signing/Verification algorithm. Only the party knowing
s is able to generate a valid signature on m, sig(m), but using V and the corresponding key v
(assumed to be public information), anybody can efficiently decide if a given (m; sig(m)) pair
is valid.
Note that some schemes, e.g. Identity based schemes, also specify a fourth function,
P, that generates parameters.
Signature suite
To meet security requirements and to allow signing of more or
less arbitrary long messages, a signature scheme requires a hash function, so that the signing/
verification algorithms operate on a fixed-size hash of the message. The combination of
signature algorithm and hash function is called a signature suite.
With or without message recovery
Some signature schemes enable the whole message, or part of it, to be recovered from
the signature. These schemes can be useful in constrained environments because only the
non-recoverable part of the message need be stored or transmitted with the signature.
As for asymmetric encryption, main choices are whether to use factoring or DLOG based
schemes (in the latter case also which group) and what security model/proof (if any) one
finds attractive.
Security
Today the most widely used security notion for signatures is called
resistance against existential forgery under adaptive chosen message attack. It is similar to that for MACs.
Informally, this means that the attacker is allowed to have messages of his own choosing signed by a 'signing
oracle', after which the attacker is to provide a single valid (m; sig(m))-pair that he has not
seen before.
For more info refer to the NESSIE Security report, available at https://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/D20-v2.pdf
Signature transformation types
Factorisation
RSA (1977)
RSA is a set of algorithms that can be used for encryption and for signature.
For signatures it can be used either as a scheme with appendix or as a scheme with message recovery.
- Signature scheme with appendix:
- Message + Alice’s private key = Signature (signature does not contain message, use of hash, more efficient for long messages)
- Message + Signature + Alice’s public key = YES/NO
- Signature scheme with message recovery:
- Message + Alice’s private key = Signature (signature contains message)
- Signature + Alice’s public key = YES/NO+Message
It can be observed that:
- RSA is not suited to some applications since signature generation is a costly operation.
- RSA signatures are large, some applications require smaller signature footprints.
- DSA is an algorithm that tries to address this.
Rabin (1979)
DLP-based (discrete logarithm problem)
In any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a
is an integer k such that bk = a.
Used in DSA and ECDSA
- Taher ElGamal - Wikipedia
- ElGamal signature scheme (1985) - Wikipedia - based on the difficulty of computing discrete logarithm
- DSA - Wikipedia
- a Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem.
- a variant of the Schnorr and ElGamal signature schemes
- DSA is a signature with appendix algorithm and the signature produced consists of two 160-bit integers r and s
- The integer r is a function of a 160-bit random number k called the ephemeral key which changes with every message
- The integer s is a function of the message, the signer’s private key x, the integer r, the ephemeral key k
- Schnorr signature scheme (1989) - Wikipedia
- Schnorr signatures have been suggested to be used for challenge response mechanisms in smart
cards since the response part of the signature (the value of s) is particularly easy to evaluate since
it only requires the computation of a single modular multiplication and a single modular addition.
- Edwards DSA (2011) - Wikipedia
- The Edwards-Curve Digital Signature Algorithm (EdDSA) is a deterministic Schnorr signature variant using twisted
Edwards curves rather than Weier-strass curves, at a significant performance gain.
- Ed25519 is a popular if not the most popular
instance of EdDSA and is based on the Edwards Curve25519 providing 128-bits of security. Due to its superior efficiency
among Elliptic Curve schemes and better security guarantees against side-channel attacks under weak randomness sources,Ed25519
is widely adopted by such protocols as TLS 1.3, SSH, Tor, GnuPGP,Signal and more. It is
also the preferred signature scheme of several blockchain systems, such as Corda, Tezos, Stellar, and Libra.
For an analysis see Konstantinos Chalkias (SSR2020).
- ed25519 paper and public reference implementation
- Pointcheval Stern signature scheme - Wikipedia
- changes the ElGamal scheme slightly to produce an algorithm which has been proven secure in a strong sense against adaptive chosen-message attacks
- Nyberg–Rueppel Signatures
- based on discrete logarithms in some public finite abelian group G
- provides message recoverable (which many other DL-based algorithms do not)
DH-based (Diffie-Hellman)
Based on the DH computational problem. The Diffie–Hellman problem is stated informally as follows:
Given an element g and the values of gx and gy, what is the value of gxy?
- Decisional DH - Wikipedia
- The DDH assumption states that, given ga and gb for uniformly and independently chosen a, b in Zq,
the value gab "looks like" a random element in G.
- The DDH assumption is related to the discrete log assumption.
If it were possible to efficiently compute discrete logs in G, then the DDH assumption would not hold in G.
- Computational DH - Wikipedia
- The CDH assumption states that, given ga and gb for a randomly chosen generator g and random
a, b in { 0 , … , q − 1 } it is computationally intractable to compute the value gxy.
- BLS - Boneh–Lynn–Shacham - Wikipedia
- The signature scheme is provably secure (the scheme is existentially unforgeable under adaptive chosen-message attacks)
assuming both the existence of random oracles and the intractability of the computational Diffie–Hellman problem
in a gap Diffie–Hellman group.
- Boneh and Franklin describe a generic method for converting any Identity-Based Encryption
scheme into a signature scheme in 'Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. SIAM
J. Comput., 32(3):586–615, 2003.'
- Brent Waters in 'Efficient Identity-Based Encryption Without Random Oracles' presented the first efficient Identity-Based Encryption (IBE) scheme that is fully secure
without random oracles. Security is based on the decisional Bilinear Diffie-Hellman (BDH) problem.
This can be used to build a new signature scheme that is secure under the computational
Diffie-Hellman assumption without random oracles.
Hash based (relevant for PQ)
One-time signatures (OTS)
- Lamport one-time signatures - 1979
- Both x and y are integers, private key is (x, y), public key is (h(x) | h(y)).
- To sign a single bit:
- if it’s 0, publish (x)
- if it’s 1, publish (y)
- Simple, but don’t use it to sign twice obviously (since you publish x 'half of the time'). Hence it's referred to as OTS.
- To sign multiple bits, hash what you want to sign (so that it has a predictible output length),
for example with SHA-256. Then use 256 key pairs, each consisting of (xn, yn):
- Concatenate all xn, yn to create the private key,
- Concatenate all h(xn) | h(yn) to create the public key,
- If you want to sign (1001102 ...),
- Then publish (y0, x1, x2, y3, y4, x5, ...)
- Ralph Merkle
- Merkle signature scheme - Wikipedia
- A Merkle signature scheme (MSS) consists of the combination of a one-time signature scheme (OTS) to sign the data and
Merkle’s tree authentication scheme which reduces the authenticity of many one-time verification keys to the authenticity
of a single public key.
- Merkle's paper 'A certified digital signature' - 1979
- This paper describes a digital signature system which is "pre-certified," generates signatures of about 1 to 3 kilobytes
(depending on the exact security requirements), requires a few thousand applications of the underlying encryption function per
signature, and only a few kilobytes of memory. If the underlying encryption function takes 10 microseconds to encrypt a block, generating a signature might take 20 milliseconds. The new signature method is called a "tree signature."
- Contents:
- A discussion of one way functions.
- A description of the Lamport-Diffie one time signature.
- An improvement to the Lamport-Diffie one time signature.
- The Winternitz one time signature.
- The W-OTS scheme was proposed by Ralph Merkle in his 1979 paper as an improved version of the Lamport-Diffie OTS
to reduce the size of signatures. Instead of a 'per-bit-signature', he proposed to sign multiple bits at once.
He was inspired by Robert Winternitz, hence the name.
- Some months after Lamport’s publication, Winternitz of the Stanford Mathematics Department proposed to
publish hw(x) instead of publishing (h(x) | h(y)).
- For example choose w=16 and publish h16(x) as public key, still using x as secret key.
- To sign the binary 10012 (equal to 910), publish h9(x).
- A problem now is that a malicious person could see this signature and hash it to create h10(x)
and thus forge a valid signature for 10102 (equal to 1010). However this can be circumvented by
adding a short checksum after the message (which you would have to sign as well).
- A description of tree signatures.
- Winternitz security
- Huelsing's W-OTS+ signatures
- Huelsing's W-OTS+ signatures explained
- XMSS signature - Buchmann, Dahmen and Huelsing
Other hash based signatures
- Leighton-Micali Hash-Based Signatures ('LMS') - RFC 8554 - describes the Leighton and Micali adaptation
of the original Lamport-Diffie-Winternitz-Merkle one-time signature system
- Sphincs.cr.yp.to
- SPHINCS-256 is a PQ stateless hash-based signature scheme that signs hundreds of messages per second on a modern
4-core 3.5GHz Intel CPU.
- Signatures are 41 KB, public keys are 1 KB, and private keys are 1 KB.
- SPHINCS-256 is designed to provide long-term 2128 security even against attackers equipped with quantum
computers.
- Unlike most hash-based signature schemes, SPHINCS-256 is stateless, allowing it to be a drop-in replacement for
current signature schemes.
Few-time signatures
Few-times signatures schemes (FTS) include:
- 1994, The Bleichenbacher-Maurer OTS
- 2001, The BiBa OTS
- 2002, HORS
- 2014, HORST (HORS with Trees)
Lattice based (relevant for PQ)
Undeniable signatures
In this scheme, a signer possessing a private key can publish a signature of a message.
However, the signature reveals nothing to a recipient/verifier of the message and signature without taking part in either
of two interactive protocols:
- Confirmation protocol, which confirms that a candidate is a valid signature of the message issued by the signer, identified by the public key.
- Disavowal protocol, which confirms that a candidate is not a valid signature of the message issued by the signer.
Refer to Chaum, David; van Antwerpen, Hans (1990) "Undeniable Signatures" and
Chaum, David (1991) "Zero-Knowledge Undeniable Signatures" EUROCRYPT '90.
Other signature types
Blind signatures
Group signatures
Anonymous signatures
Threshold signatures
- RSA PKCS#1 (IETF RFC 8017) - RSA Cryptography Specifications Version 2.2
- cryptographic primitives
- encryption schemes
- signature schemes with appendix
- ASN.1 syntax for representing keys and for identifying the schemes
The Cryptographic Message Syntax (CMS) is the IETF's standard for cryptographically protected messages.
It can be used by cryptographic schemes and protocols to sign, digest, authenticate or encrypt data.
It is based on the syntax of PKCS #7, which in turn is based on the Privacy-Enhanced Mail standard.
CMS is used as the key cryptographic component of a.o. S/MIME, PKCS #12 and the RFC 3161 Digital timestamping protocol.
OpenSSL is open source software that can encrypt, decrypt, sign and verify, compress and uncompress CMS documents.
- CMS - Wikipedia
- RFC 5652 Cryptographic Message Syntax (CMS)
- RFC 6268 New ASN.1 Modules for Cryptographic Message Syntax (CMS) and S/MIME
- RFC 5753 Using Elliptic Curve Cryptography with CMS
- RFC 5084 Using AES-CCM and AES-GCM Authenticated Encryption in the Cryptographic Message Syntax (CMS)
Signature standards
- W3C XMLDSIG - the basis for XAdES
- Wikipedia on XMLDSIG
- XML signatures can be used to sign data–a resource–of any type, typically XML documents,
but anything that is accessible via a URL can be signed.
- An XML signature used to sign a resource outside its containing XML document is called a detached signature;
- if it is used to sign some part of its containing document, it is called an enveloped signature;
- if it contains the signed data within itself it is called an enveloping signature.
- XAdES (short for XML Advanced Electronic Signatures) is a set of extensions to XML-DSig recommendation making it suitable for advanced electronic signatures.
W3C and ETSI maintain and update XAdES together.
- XMLDSIG interop report 2001
- OpenSignature.org - widely supported
- Cloud Signature Consortium (CSC) - remote signatures
For more signature standards refer to