Misplaced Pages

#591408

72-511: So far, hash-based cryptography is used to construct digital signatures schemes such as the Merkle signature scheme , zero knowledge and computationally integrity proofs, such as the zk-STARK proof system and range proofs over issued credentials via the HashWires protocol. Hash-based signature schemes combine a one-time signature scheme, such as a Lamport signature , with a Merkle tree structure. Since

144-438: A preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (set of possible inputs). In the context of attack, there are two types of preimage resistance: These can be compared with a collision resistance , in which it is computationally infeasible to find any two distinct inputs x , x ′ that hash to

216-588: A PKI, or by the technological avant-garde advocating new solutions to old problems, have enacted statutes and/or regulations in many jurisdictions authorizing, endorsing, encouraging, or permitting digital signatures and providing for (or limiting) their legal effect. The first appears to have been in Utah in the United States, followed closely by the states Massachusetts and California . Other countries have also passed statutes or issued regulations in this area as well and

288-406: A branch banker, and not forged—whether a forger fabricated the whole letter, or just modified an existing letter in transit by adding some digits. With a digital signature scheme, the central office can arrange beforehand to have a public key on file whose private key is known only to the branch office. The branch office can later sign a message and the central office can use the public key to verify

360-462: A card reader integrated into a PC, and then entering the PIN using that computer's keyboard. Readers with a numeric keypad are meant to circumvent the eavesdropping threat where the computer might be running a keystroke logger , potentially compromising the PIN code. Specialized card readers are also less vulnerable to tampering with their software or hardware and are often EAL3 certified. Smart card design

432-528: A digit —if the bank's offices simply encrypted the messages they exchange, they could still be vulnerable to forgery. In other applications, such as software updates, the messages are not secret—when a software author publishes a patch for all existing installations of the software to apply, the patch itself is not secret, but computers running the software must verify the authenticity of the patch before applying it, lest they become victims to malware. Replays. A digital signature scheme on its own does not prevent

504-521: A few weeks might be very practical. All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks . In general, a collision attack is easier to mount than a preimage attack, as it is not restricted by any set value (any two values can be used to collide). The time complexity of a brute-force collision attack, in contrast to the preimage attack, is only 2 n 2 {\displaystyle 2^{\frac {n}{2}}} . The computational infeasibility of

576-404: A first preimage attack on an ideal hash function assumes that the set of possible hash inputs is too large for a brute force search. However if a given hash value is known to have been produced from a set of inputs that is relatively small or is ordered by likelihood in some way, then a brute force search may be effective. Practicality depends on the input set size and the speed or cost of computing

648-407: A given hash function becomes insecure, it is sufficient to replace it by a different, secure one to obtain a secure instantiation of the hash-based signature scheme under consideration. Some hash-based signature schemes (such as XMSS with pseudorandom key generation) are forward secure, meaning that previous signatures remain valid if a secret key is compromised. The minimality of security assumptions

720-433: A handwritten signature identifying its sender, but letterheads and handwritten signatures can be copied and pasted onto forged messages. Even legitimate messages may be modified in transit. If a bank's central office receives a letter claiming to be from a branch office with instructions to change the balance of an account, the central bankers need to be sure, before acting on the instructions, that they were actually sent by

792-410: A locally provided one is risk. Many risk averse companies, including governments, financial and medical institutions, and payment processors require more secure standards, like FIPS 140-2 level 3 and FIPS 201 certification, to ensure the signature is validated and secure. Technically speaking, a digital signature applies to a string of bits, whereas humans and applications "believe" that they sign

SECTION 10

#1733085606592

864-451: A minimum of 2 signatures safely. In 2022, NIST announced SPHINCS+ as one of three algorithms to be standardized for digital signatures. NIST standardized stateful hash-based cryptography based on the eXtended Merkle Signature Scheme (XMSS) and Leighton–Micali Signatures (LMS), which are applicable in different circumstances, in 2020, but noted that the requirement to maintain state when using them makes them more difficult to implement in

936-625: A one-time signature scheme key can only sign a single message securely, it is practical to combine many such keys within a single, larger structure. A Merkle tree structure is used to this end. In this hierarchical data structure, a hash function and concatenation are used repeatedly to compute tree nodes. One consideration with hash-based signature schemes is that they can only sign a limited number of messages securely, because of their use of one-time signature schemes. The US National Institute of Standards and Technology (NIST), specified that algorithms in its post-quantum cryptography competition support

1008-406: A practical preimage attack is discovered, it would drastically affect many Internet protocols. In this case, "practical" means that it could be executed by an attacker with a reasonable amount of resources. For example, a preimaging attack that costs trillions of dollars and takes decades to preimage one desired hash value or one message is not practical; one that costs a few thousand dollars and takes

1080-399: A public key. Prior knowledge of a public key can be used to verify authenticity of a signed message , but not the other way around—prior knowledge of a signed message cannot be used to verify authenticity of a public key . In some signature schemes, given a signed message, it is easy to construct a public key under which the signed message will pass verification, even without knowledge of

1152-447: A signatory. The United States Government Printing Office (GPO) publishes electronic versions of the budget, public and private laws, and congressional bills with digital signatures. Universities including Penn State, University of Chicago , and Stanford are publishing electronic student transcripts with digital signatures. Below are some common reasons for applying a digital signature to communications: A message may have letterhead or

1224-572: A standard element of most cryptographic protocol suites, and are commonly used for software distribution, financial transactions, contract management software , and in other cases where it is important to detect forgery or tampering . Digital signatures are often used to implement electronic signatures , which include any electronic data that carries the intent of a signature, but not all electronic signatures use digital signatures. Electronic signatures have legal significance in some countries, including Brazil , Canada , South Africa , Russia ,

1296-453: A trade-off between size and speed. Large values of the Winternitz parameter yield short signatures and keys, at the price of slower signing and verifying. In practice, a typical value for this parameter is 16. In the case of stateless hash-based signatures, few-time signature schemes are used. Such schemes allow security to decrease gradually in case a few-time key is used more than once. HORST

1368-416: A typical digital signature implementation, the hash calculated from the document is sent to the smart card, whose CPU signs the hash using the stored private key of the user, and then returns the signed hash. Typically, a user must activate their smart card by entering a personal identification number or PIN code (thus providing two-factor authentication ). It can be arranged that the private key never leaves

1440-516: A valid signed message from being recorded and then maliciously reused in a replay attack . For example, the branch office may legitimately request that bank transfer be issued once in a signed message. If the bank doesn't use a system of transaction IDs in their messages to detect which transfers have already happened, someone could illegitimately reuse the same signed message many times to drain an account. Uniqueness and malleability of signatures. A signature itself cannot be used to uniquely identify

1512-524: A way that avoids misuse. In 2024 NIST announced the Stateless Hash-Based Digital Signature Standard. Leslie Lamport invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme) and SPHINCS hash-based signature schemes were introduced in 2011 and 2015, respectively. XMSS was developed by a team of researchers under the direction of Johannes Buchmann and is based both on Merkle's seminal scheme and on

SECTION 20

#1733085606592

1584-429: Is Euler's totient function . The signer's public key consists of N and e , and the signer's secret key contains d . Used directly, this type of signature scheme is vulnerable to key-only existential forgery attack. To create a forgery, the attacker picks a random signature σ and uses the verification procedure to determine the message, m , corresponding to that signature. In practice, however, this type of signature

1656-416: Is already known right from the start). By definition, an ideal hash function is such that the fastest way to compute a first or second preimage is through a brute-force attack . For an n -bit hash, this attack has a time complexity 2 , which is considered too high for a typical output size of n = 128 bits. If such complexity is the best that can be achieved by an adversary, then the hash function

1728-424: Is an active field, and there are smart card schemes which are intended to avoid these particular problems, despite having few security proofs so far. One of the main differences between a digital signature and a written signature is that the user does not "see" what they sign. The user application presents a hash code to be signed by the digital signing algorithm using the private key. An attacker who gains control of

1800-419: Is an example of a few-time signature scheme. The central idea of hash-based signature schemes is to combine a larger number of one-time key pairs into a single structure to obtain a practical way of signing more than once (yet a limited number of times). This is done using a Merkle tree structure, with possible variations. One public and one private key are constructed from the numerous public and private keys of

1872-402: Is another characteristic of hash-based signature schemes. Generally, these schemes only require a secure (for instance in the sense of second preimage resistance ) cryptographic hash function to guarantee the overall security of the scheme. This kind of assumption is necessary for any digital signature scheme; however, other signature schemes require additional security assumptions , which is not

1944-546: Is considered preimage-resistant. However, there is a general result that quantum computers perform a structured preimage attack in 2 n = 2 n 2 {\displaystyle {\sqrt {2^{n}}}=2^{\frac {n}{2}}} , which also implies second preimage and thus a collision attack. Faster preimage attacks can be found by cryptanalysing certain hash functions, and are specific to that function. Some significant preimage attacks have already been discovered, but they are not yet practical. If

2016-410: Is critical to signing performance. Increasingly efficient approaches have been introduced, dramatically speeding up signing time. Some hash-based signature schemes use multiple layers of tree, offering faster signing at the price of larger signatures. In such schemes, only the lowest layer of trees is used to sign messages, while all other trees sign root values of lower trees. The Naor–Yung work shows

2088-453: Is existentially unforgeable, even against a chosen-plaintext attack . There are several reasons to sign such a hash (or message digest) instead of the whole document. As organizations move away from paper documents with ink signatures or authenticity stamps, digital signatures can provide added assurances of the evidence to provenance, identity, and status of an electronic document as well as acknowledging informed consent and approval by

2160-486: Is not built on trapdoor functions but rather on a family of function with a much weaker required property of one-way permutation was presented by Moni Naor and Moti Yung . One digital signature scheme (of many) is based on RSA . To create signature keys, generate an RSA key pair containing a modulus, N , that is the product of two random secret distinct large primes, along with integers, e and d , such that e   d   ≡  1 (mod  φ ( N )), where φ

2232-566: Is not used directly, but rather, the message to be signed is first hashed to produce a short digest, that is then padded to larger width comparable to  N , then signed with the reverse trapdoor function . This forgery attack, then, only produces the padded hash function output that corresponds to σ, but not a message that leads to that value, which does not lead to an attack. In the random oracle model, hash-then-sign (an idealized version of that practice where hash and padding combined have close to N possible outputs), this form of signature

Hash-based cryptography - Misplaced Pages Continue

2304-405: Is often thought best to use separate key pairs for encrypting and signing. Using the encryption key pair, a person can engage in an encrypted conversation (e.g., regarding a real estate transaction), but the encryption does not legally sign every message he or she sends. Only when both parties come to an agreement do they sign a contract with their signing keys, and only then are they legally bound by

2376-447: Is relatively easy to change the interpretation of a digital document by implementing changes on the computer system where the document is being processed. From a semantic perspective this creates uncertainty about what exactly has been signed. WYSIWYS (What You See Is What You Sign) means that the semantic interpretation of a signed message cannot be changed. In particular this also means that a message cannot contain hidden information that

2448-512: Is security against existential forgery under an adaptive chosen message attack. All public key / private key cryptosystems depend entirely on keeping the private key secret. A private key can be stored on a user's computer, and protected by a local password, but this has two disadvantages: A more secure alternative is to store the private key on a smart card . Many smart cards are designed to be tamper-resistant (although some designs have been broken, notably by Ross Anderson and his students ). In

2520-553: The National Institute of Standards and Technology , is one of many examples of a signing algorithm. In the following discussion, 1 refers to a unary number . Formally, a digital signature scheme is a triple of probabilistic polynomial time algorithms, ( G , S , V ), satisfying: For correctness, S and V must satisfy A digital signature scheme is secure if for every non-uniform probabilistic polynomial time adversary , A where A denotes that A has access to

2592-677: The RSA algorithm, which could be used to produce primitive digital signatures (although only as a proof-of-concept – "plain" RSA signatures are not secure ). The first widely marketed software package to offer digital signature was Lotus Notes 1.0, released in 1989, which used the RSA algorithm. Other digital signature schemes were soon developed after RSA, the earliest being Lamport signatures , Merkle signatures (also known as "Merkle trees" or simply "Hash trees"), and Rabin signatures . In 1988, Shafi Goldwasser , Silvio Micali , and Ronald Rivest became

2664-534: The United States , Algeria , Turkey , India , Indonesia , Mexico , Saudi Arabia , Uruguay , Switzerland , Chile and the countries of the European Union . Digital signatures employ asymmetric cryptography . In many instances, they provide a layer of validation and security to messages sent through a non-secure channel: Properly implemented, a digital signature gives the receiver reason to believe

2736-594: The oracle , S ( sk , · ), Q denotes the set of the queries on S made by A , which knows the public key, pk , and the security parameter, n , and x ∉ Q denotes that the adversary may not directly query the string, x , on S . In 1976, Whitfield Diffie and Martin Hellman first described the notion of a digital signature scheme, although they only conjectured that such schemes existed based on functions that are trapdoor one-way permutations. Soon afterwards, Ronald Rivest , Adi Shamir , and Len Adleman invented

2808-408: The 2007 Generalized Merkle Signature Scheme (GMSS). A multi-tree variant of XMSS, XMSS, was described in 2013. Hash-based signature schemes use one-time signature schemes as their building block. A given one-time signing key can only be used to sign a single message securely. Indeed, signatures reveal part of the signing key. The security of (hash-based) one-time signature schemes relies exclusively on

2880-481: The SAFE-BioPharma Association for the healthcare industry . In several countries, a digital signature has a status somewhat like that of a traditional pen and paper signature, as in the 1999 EU digital signature directive and 2014 EU follow-on legislation . Generally, these provisions mean that anything digitally signed legally binds the signer of the document to the terms therein. For that reason, it

2952-806: The SPHINCS scheme is stateless. SPHINCS signatures are larger than XMSS and LMS signatures. BPQS has been designed specifically for blockchain systems. Additionally to the WOTS+ one-time signature scheme, SPHINCS also uses a few-time (hash-based) signature scheme called HORST. HORST is an improvement of an older few-time signature scheme, HORS (Hash to Obtain Random Subset). The stateful hash-based schemes XMSS and XMSS are specified in RFC 8391 (XMSS: eXtended Merkle Signature Scheme). Leighton–Micali Hash-Based Signatures are specified in RFC 8554. Practical improvements have been proposed in

Hash-based cryptography - Misplaced Pages Continue

3024-532: The UN has had an active model law project for some time. These enactments (or proposed enactments) vary from place to place, have typically embodied expectations at variance (optimistically or pessimistically) with the state of the underlying cryptographic engineering, and have had the net effect of confusing potential users and specifiers, nearly all of whom are not cryptographically knowledgeable. Adoption of technical standards for digital signatures have lagged behind much of

3096-501: The XMSS RFC exist. The LMS scheme has been implemented in Python and in C following its Internet-Draft. Digital signature A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient. Digital signatures are

3168-564: The XMSS, the Leighton–Micali (LMS), the SPHINCS and the BPQS schemes. Most hash-based signature schemes are stateful , meaning that signing requires updating the secret key, unlike conventional digital signature schemes. For stateful hash-based signature schemes, signing requires keeping state of the used one-time keys and making sure they are never reused. The XMSS, LMS and BPQS schemes are stateful, while

3240-463: The authenticity of a signature generated from a fixed message and fixed private key can be verified by using the corresponding public key. Secondly, it should be computationally infeasible to generate a valid signature for a party without knowing that party's private key. A digital signature is an authentication mechanism that enables the creator of the message to attach a code that acts as a signature. The Digital Signature Algorithm (DSA), developed by

3312-592: The case here. Because of their reliance on an underlying one-time signature scheme, hash-based signature schemes can only sign a fixed number of messages securely. In the case of the Merkle and XMSS schemes, a maximum of 2 h {\displaystyle 2^{h}} messages can be signed securely, with h {\displaystyle h} the total Merkle tree height. Since Merkle's initial scheme, numerous hash-based signature schemes with performance improvements have been introduced. Recent ones include

3384-462: The credit-card issuer to find if a given card has been reported lost or stolen. Of course, with stolen key pairs, the theft is often discovered only after the secret key's use, e.g., to sign a bogus certificate for espionage purpose. In their foundational paper, Goldwasser, Micali, and Rivest lay out a hierarchy of attack models against digital signatures: They also describe a hierarchy of attack results: The strongest notion of security, therefore,

3456-454: The first to rigorously define the security requirements of digital signature schemes. They described a hierarchy of attack models for signature schemes, and also presented the GMR signature scheme , the first that could be proved to prevent even an existential forgery against a chosen message attack, which is the currently accepted security definition for signature schemes. The first such scheme which

3528-458: The following goals regardless of cryptographic theory or legal provision: Only if all of these conditions are met will a digital signature actually be any evidence of who sent the message, and therefore of their assent to its contents. Legal enactment cannot change this reality of the existing engineering possibilities, though some such have not reflected this actuality. Legislatures, being importuned by businesses expecting to profit from operating

3600-408: The hash function. A common example is the use of hashes to store password validation data for authentication. Rather than store the plaintext of user passwords, an access control system stores a hash of the password. When a user requests access, the password they submit is hashed and compared with the stored value. If the stored validation data is stolen, the thief will only have the hash values, not

3672-421: The image manually or digitally, but to have credible signature copies that can resist some scrutiny is a significant manual or technical skill, and to produce ink signature copies that resist professional scrutiny is very difficult. Digital signatures cryptographically bind an electronic identity to an electronic document and the digital signature cannot be copied to another document. Paper contracts sometimes have

SECTION 50

#1733085606592

3744-422: The ink signature block on the last page, and the previous pages may be replaced after a signature is applied. Digital signatures can be applied to an entire document, such that the digital signature on the last page will indicate tampering if any data on any of the pages have been altered, but this can also be achieved by signing with ink and numbering all pages of the contract. Most digital signature schemes share

3816-490: The legislation, delaying a more or less unified engineering position on interoperability , algorithm choice, key lengths , and so on what the engineering is attempting to provide. Some industries have established common interoperability standards for the use of digital signatures between members of the industry and with regulators. These include the Automotive Network Exchange for the automobile industry and

3888-556: The literature that alleviate the concerns introduced by stateful schemes. Hash functions appropriate for these schemes include SHA-2 , SHA-3 and BLAKE . The XMSS, GMSS and SPHINCS schemes are available in the Java Bouncy Castle cryptographic APIs. LMS and XMSS schemes are available in the wolfSSL cryptographic APIs. SPHINCS is implemented in the SUPERCOP benchmarking toolkit. Optimised and unoptimised reference implementations of

3960-405: The loss of the smart card may be detected by the owner and the corresponding certificate can be immediately revoked. Private keys that are protected by software only may be easier to copy, and such compromises are far more difficult to detect. Entering a PIN code to activate the smart card commonly requires a numeric keypad . Some card readers have their own numeric keypad. This is safer than using

4032-436: The message it signs—in some signature schemes, every message has a large number of possible valid signatures from the same signer, and it may be easy, even without knowledge of the private key, to transform one valid signature into another. If signatures are misused as transaction IDs in an attempt by a bank-like system such as a Bitcoin exchange to detect replays, this can be exploited to replay transactions. Authenticating

4104-416: The message was sent by the claimed sender. Digital signatures are equivalent to traditional handwritten signatures in many respects, but properly implemented digital signatures are more difficult to forge than the handwritten type. Digital signature schemes, in the sense used here, are cryptographically based, and must be implemented properly to be effective. They can also provide non-repudiation , meaning that

4176-405: The pattern by which to transfer a limited time signature of the Merkle type family into an unlimited (regular) signature scheme. Hash-based signature schemes rely on security assumptions about the underlying hash function, but any hash function fulfilling these assumptions can be used. As a consequence, each adequate hash function yields a different corresponding hash-based signature scheme. Even if

4248-477: The private key that was used to make the signed message in the first place. Non-repudiation , or more specifically non-repudiation of origin, is an important aspect of digital signatures. By this property, an entity that has signed some information cannot at a later time deny having signed it. Similarly, access to the public key only does not enable a fraudulent party to fake a valid signature. Note that these authentication, non-repudiation etc. properties rely on

4320-429: The same output; i.e., such that h ( x ) = h ( x ′) . Collision resistance implies second-preimage resistance. Second-preimage resistance implies preimage resistance only if the size of the hash function's inputs can be substantially (e.g., factor 2) larger than the size of the hash function's outputs. Conversely, a second-preimage attack implies a collision attack (trivially, since, in addition to x ′ , x

4392-531: The secret key not having been revoked prior to its usage. Public revocation of a key-pair is a required ability, else leaked secret keys would continue to implicate the claimed owner of the key-pair. Checking revocation status requires an "online" check; e.g., checking a certificate revocation list or via the Online Certificate Status Protocol . Very roughly this is analogous to a vendor who receives credit-cards first checking online with

SECTION 60

#1733085606592

4464-536: The security of an underlying hash function. Commonly used one-time signature schemes include the Lamport–Diffie scheme , the Winternitz scheme and its improvements, such as the W-OTS scheme. Unlike the seminal Lamport–Diffie scheme, the Winternitz scheme and variants can sign many bits at once. The number of bits to be signed at once is determined by a value: the Winternitz parameter. The existence of this parameter provides

4536-431: The semantic interpretation of those bits. In order to be semantically interpreted, the bit string must be transformed into a form that is meaningful for humans and applications, and this is done through a combination of hardware and software based processes on a computer system. The problem is that the semantic interpretation of bits can change as a function of the processes used to transform the bits into semantic content. It

4608-434: The signature, and allows a verifier to reconstruct the node path between those two public keys. The global private key is generally handled using a pseudo-random number generator. It is then sufficient to store a seed value. One-time secret keys are derived successively from the seed value using the generator. With this approach, the global private key is also very small, e.g. typically 32 bytes. The problem of tree traversal

4680-468: The signed message was not a forgery before acting on it. A forger who doesn't know the sender's private key can't sign a different message, or even change a single digit in an existing message without making the recipient's signature verification fail. Encryption can hide the content of the message from an eavesdropper, but encryption on its own may not let recipient verify the message's authenticity, or even detect selective modifications like changing

4752-565: The signer cannot successfully claim they did not sign a message, while also claiming their private key remains secret. Further, some non-repudiation schemes offer a timestamp for the digital signature, so that even if the private key is exposed, the signature is valid. Digitally signed messages may be anything representable as a bitstring : examples include electronic mail, contracts, or a message sent via some other cryptographic protocol. A digital signature scheme typically consists of three algorithms: Two main properties are required: First,

4824-537: The signer is unaware of, and that can be revealed after the signature has been applied. WYSIWYS is a requirement for the validity of digital signatures, but this requirement is difficult to guarantee because of the increasing complexity of modern computer systems. The term WYSIWYS was coined by Peter Landrock and Torben Pedersen to describe some of the principles in delivering secure and legally binding digital signatures for Pan-European projects. An ink signature could be replicated from one document to another by copying

4896-461: The smart card, although this is not always implemented. If the smart card is stolen, the thief will still need the PIN code to generate a digital signature. This reduces the security of the scheme to that of the PIN system, although it still requires an attacker to possess the card. A mitigating factor is that private keys, if generated and stored on smart cards, are usually regarded as difficult to copy, and are assumed to exist in exactly one copy. Thus,

4968-460: The terms of a specific document. After signing, the document can be sent over the encrypted link. If a signing key is lost or compromised, it can be revoked to mitigate any future transactions. If an encryption key is lost, a backup or key escrow should be utilized to continue viewing encrypted content. Signing keys should never be backed up or escrowed unless the backup destination is securely encrypted. Preimage attack In cryptography ,

5040-406: The underlying one-time scheme. The global public key is the single node at the very top of the Merkle tree. Its value is an output of the selected hash function, so a typical public key size is 32 bytes. The validity of this global public key is related to the validity of a given one-time public key using a sequence of tree nodes. This sequence is called the authentication path. It is stored as part of

5112-443: The user's PC can possibly replace the user application with a foreign substitute, in effect replacing the user's own communications with those of the attacker. This could allow a malicious application to trick a user into signing any document by displaying the user's original on-screen, but presenting the attacker's own documents to the signing application. To protect against this scenario, an authentication system can be set up between

5184-404: The user's application (word processor, email client, etc.) and the signing application. The general idea is to provide some means for both the user application and signing application to verify each other's integrity. For example, the signing application may require all requests to come from digitally signed binaries. One of the main differences between a cloud based digital signature service and

#591408