Patent Description:
Nowadays, internet of things (IoT) devices are increasingly applied in private and industrial environments. IoT devices communicate with each other or with controllers in public or private communication networks. Public-key cryptography is used to secure authenticity of communication partners and integrity of the exchanged data. Digital signatures are applied in device certificate to provide counterfeit protection. Therefore, the digital signatures need to provide protection over the whole lifetime of the device, which can extend up to <NUM> to <NUM> years in industrial environment. Respectively public-key cryptography schemes are required, which are still secure in <NUM> or <NUM> years.

Public-key cryptography refers to cryptosystems which employ key-pairs instead of individual secret keys. A key pair consist of a private key, which is only known to its owner, and a public key, which can be distributed publicly to anybody without compromising the security of the cryptosystem. Digital signatures are an example of public-key cryptography, in which a message is signed using the sender's private key and can be verified by anyone having access to the corresponding sender's public key. Two widely employed approaches to public-key cryptography are RSA (Rivest-Shamir-Adleman) and elliptic-curve cryptography. These cryptosystems are based on the RSA problem and the elliptic-curve discrete logarithm problem, respectively. So far, no efficient methods are known to solve such problems using current computing technologies. This means that for sufficiently large numbers the task of solving such problems is believed to be impossible with conventional computers. However, efficient quantum algorithms (e.g. Shor's algorithm) are known to solve such problems with the aid of quantum computers. This means that as soon as powerful enough quantum computers will be built in the future, the security of RSA and elliptic-curve cryptographic systems will become at risk of compromise and should be replaced by algorithms which are also resistant against quantum attacks.

Post-quantum cryptography generally refers to a class of public-key cryptographic algorithms for which no efficient quantum and non-quantum algorithms are known to solve the underlying math problems. One way of realizing post-quantum digital signatures is to employ stateful hash-based signatures algorithms whose security is based on the security of hash functions. One example of a stateful hash-based signature algorithm is extended Merkle Signature Scheme (XMSS) described in RFC <NUM>, which builds upon Winterniz One-Time Signatures+ (WOTS+) and Merkle trees. Another approach to hash-based signatures is the Leighton-Micali Signature (LMS) scheme described in the RFC <NUM>, build upon Leighton-Micali One-Time Signatures (LM-OTS).

WOTS+ private keys are generated using a Pseudo-Random Number Generator (PRNG) using a secret seed and an index as state information. In order to ensure the security of XMSS, it must be guaranteed that the index is never used more than once, e.g., each WOTS+ private key is only generated once using the secret seed and the current index, which gets increased with every signature. This can be achieved using a secure monotone counter, which cannot be decreased or reset. This is typically a very strong requirement which can be circumvented, e.g., by modifying the counter after it has been loaded from memory into the system.

Nowadays, the management of the state is handled by an entity generating the stateful hash-based signature, called a signer, which should take care that the keys are not used twice. For the verifier of a stateful hash-based signature, e.g., an IoT device, there is no way to check if the signer is behaving correctly. However, this might not be an adequate solution in some critical use cases such as digital signatures of software/firmware packages, where maliciously signed updates may lead to major consequences.

<CIT> discloses systems, devices, and computer-implemented methods for detecting double signing in one-time use signature schemes based on a list of public keys and generating an alert message based on determining that the one-time use public/private key pair was used more than once. The alert message is associated with a transfer of cryptocur-rency.

<NPL> a latency-area optimized XMSS sign or verify scheme with <NUM>-bit post-quantum security and an appropriate HW-SW architecture.

<CIT> discloses a combined SHA2 and SHA3 base XMSS HW accelerator.

<NPL> two algorithms that can be used to generate a digital signature, the Leighton-Micali Signature (LMS) system and the eXtended Merkle Signature Scheme (XMSS), both of which are stateful hash-based signature schemes.

Therefore, it is the object of the present application to provide a solution that enables the user, i.e. the verifier, of a stateful hash-based signature to identify a security breach of a hash-based signature, e.g., a key re-usage attack or a malfunction of the signer.

The dependent claims contain further developments of the invention.

A first aspect concerns a signing system for validating stateful hash-based digital signatures, comprising at least one signing device, a logging device and a verifying device, wherein each signing device is configured to.

The invention is based on the main observation that any one-time private key is uniquely tied to its respective one-time public key as they are in a <NUM>:<NUM> relationship. In fact, the one-time public key can be computed from a one-time signature, which is public information included into a stateful hash-based signature, which is public information as well. Therefore, it is sufficient to compare one-time public keys computed from stateful hash-based signatures to check whether the same one-time private key has been used multiple times. The main idea behind the invention is to rely on independent logging device, i.e. external auditors and public logs, to verify the correct functioning of hash-based stateful signing devices in the context of stateful hash-based cryptography. In case the signing device fails to use a one-time private key only once, this can be recognized by external auditors, i.e. the logging device. Compared to the known stateful hash-based signing approaches, which are based on self-checking techniques, there is no single point of failure in the disclosed signing system. There is no need to implement expensive checks on the state, e.g. self-checking techniques, monotone counters, and further in the signing device.

In a further embodiment of the signing system, the logging device comprises a logging unit storing the one-time public key and an auditing unit monitoring the stored one-time public keys in the logging unit.

Separating the logging device into a logging unit and an auditing unit has the advantage, that the logging unit can be kept simple in terms of processing capabilities as it only stores the one-time public keys. The logging unit can be secured with stronger security measures than the auditing unit to prevent manipulation of the stored one-time public keys.

In a further embodiment of the signing system, the auditing unit receives the validation one-time public key from the verifying device and provides the validation feedback signal or the warning feedback signal to the verifying device.

By that, the auditing unit provides a single interface to the verifying device and protecting the logging unit from external access.

In a further embodiment of the signing system, on receiving the generated one-time public key from the signing device in the logging unit, the logging unit or the auditing unit compares the generated one-time public key with all one-time public keys previously stored in the logging unit, and provides the validation feedback signal or the warning feedback signal to the auditing unit.

In this embodiment the logging device is not triggered by the verifying device, but by the one-time public key received from the signing device. This allows a faster validation on receiving the validation one-time public key from the verifying device as the validation is already performed and the resulting feedback signal only needs to be forwarded to the verifying device.

In a further embodiment of the signing system, on receiving the validation one-time public key from the verifying device, the auditing unit compares the validation one-time public key with the stored one-time public keys and provides the validation feedback signal or the warning feedback signal to the auditing unit.

By validating the received validation on its receipt in the auditing unit, the validation is limited to the received validation one-time public keys and optimizes the required processing capacity for validation.

In a further embodiment of the signing system, the auditing unit stores the validation one-time public key received from the verifying device and, if a warning feed-back signal is received for the validation one-time public key at a later time, provides this warning feedback signal automatically to the verifying device which has sent the validation one-time public key.

This enables the auditing unit to keep track of the verifying device requests, such that, in case the one-time public key is used multiples times, the auditing unit can proactively notify the affected verifying device of the unexpected behavior of the signing device.

In a further embodiment of the signing device, the auditing unit notifies all verifying devices, which received a validation feedback signal, if a warning feedback signal is provided for any of the one-time public key stored in the logging device.

This enables all verifying devices which received a hash-based signature from the signing device about the unexpected behaviour of the signing device. All verifying devices can react if any measures are defined for such a situation.

In a further embodiment of the signing system, the auditing unit passes the validation one-time public key received from the verifying device to the logging unit and passes the validation or warning feedback signal received from the logging unit to the verifying device.

In this embodiment the validation, i. e, the comparing and providing functions, are located at the logging unit having direct access to the stored one-time public keys.

In a further embodiment of the signing system, the signing device sends the hash-based digital signature and the data to be signed to the logging device, and the logging device generates the one-time public key based on the hash-based digital signature and the data.

With this embodiment the signing system performs only the signing of the data but merely any additional functionality. In consequence only few adaptions are required compared to a standard procedure performed in the signing device.

In a further embodiment of the signing system, the logging device stores additional meta-information related to the hash-based digital signature received from the signing device and/or the logging device stores additional meta-information related to the verifying device received with the validation one-time public key from the verifying device.

This meta-information can be used to further attest the plausibility of a correct functioning of the signing device, e.g. using machine learning methods. The meta-information on related to the verifying device can be used to further attest the plausibility of a correct functioning of the verifying device, e.g. using machine learning methods. Also, the logging device may generate further meta-information on his own.

In a further embodiment of the signing system, the logging device comprises more than one logging units and/or more than one auditing units.

This has the advantage that logging devices and/or auditing units can be organized in a hierarchical structure and replicate only the information that is relevant in the given context, e.g. geographical region.

A second aspect concerns a logging device comprising at least one logging unit and at least one auditing unit configured to.

The logging device recognizes failure of the signing device additionally to monitoring of internal state handling in the signing device.

A third aspect concerns a signing device comprising at least one processor configured to.

A fourth aspect concerns a method for identifying a security breach of stateful hash-based digital signatures, comprising the steps:.

A fifth aspect concerns a computer program product directly loadable into the internal memory of a digital computer, comprising software code portions for performing the steps as described before, when said product is run on said digital computer.

The invention will be explained in more detail by reference to accompanying figures. Similar objects will be marked by the same reference signs.

It is noted that in the following detailed description of embodiments, the accompanying drawings are only schematic, and the illustrated elements are not necessarily shown to scale. Rather, the drawings are intended to illustrate functions and the co-operation of components. Here, it is to be understood that any connection or coupling of functional blocks, devices, components or other physical or functional elements could also be implemented by an indirect connection or coupling, e.g., via one or more intermediate elements. A connection or a coupling of elements or components or nodes can for example be implemented by a wire-based, a wireless connection and/or a combination of a wire-based and a wireless connection. Functional units can be implemented by dedicated hardware, e.g., processor, by firmware or by software, and/or by a combination of dedicated hardware and firmware and software. It is further noted that each functional unit described for an apparatus can perform a functional step of the related method.

Stateful hash-based signature and hash-based signatures as well as private key and secret key are used as synonyms throughout this document.

<FIG> shows a structure of a stateful hash-based cryptography function, i.e. a stateful hash-based signature scheme. Hash-based signature schemes combine a one-time signature scheme OTSS with a Merkle tree structure MTS. Since a one-time signature scheme key can only sign a single message, i.e., data to be signed, securely, it is practical to combine many such keys within a single, larger structure. A Merkle tree structure MTS is used to this end. In this hierarchical data structure, a hash function and concatenation are used repeatedly to compute tree nodes.

Hash-based signature schemes are stateful, meaning that signing requires updating the private 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. In this way a one-time private key OTsk is uniquely used to generate a one-time signature OTsig, the one-time signature OTsig is uniquely tied to a one-time public key OTpk. A hash-based public key HBpk is determined based on all one-time signature scemes and builds the root of the Merkle tree. The hash-based public key HBpk is published to verify all hash-based digital signatures generated based on one of the one-time private keys OTsk.

As an example, according to the eXtended Merkle Signature Scheme XMSS described in the RFC <NUM>, Winternitz One-Time Signature Plus (WOTS+) private keys are generated using a secret seed value and an index value. The index value is updated for every hash-based signature such that only unique WOTS+ private keys are generated. To guarantee the security of the XMSS cryptosystem, a XMSS signer generating the XMSS signature must guarantee that the index value is never used more than once. This can be achieved using a secure monotone counter, which can be neither decreased nor reset. This is typically a very strong requirement which could be even circumvented in some cases, e.g. by modifying the counter during the signature computation after that the counter has been securely loaded from memory. There is no way for the XMSS verifier to check if the XMSS signer is behaving correctly.

<FIG> shows the hash-based signature HBsig. The hash-based signature HBsig is a data structure consisting of several segments <NUM>, <NUM>, <NUM>, <NUM>. Segment <NUM> comprises an index of the one-time key pair, segment <NUM> comprises a randomized message hashing. In segment <NUM> the one-time signature OTsig is comprised. Segment <NUM> comprises a so-called authentication path AP for the used one-time key pair providing the nodes of the Merkle Tree required to calculate a so called root, which is the hash-based public key HBpk for all hash-based digital signatures <NUM> generated by one of the one-time private keys OTsk of the stateful hash-based signature scheme, see <FIG>.

The signing system and the signing method are based on the observation that one-time private keys OTsk are uniquely tied to their corresponding one-time public keys OTpk, one-time public keys OTpk are uniquely tied to one-time signatures OTsig, and one-time signatures OTsig are included within the hash-based signature HBsig. Since the one-time public keys OTpk can be computed out of one-time signatures OTsig, it is possible to indirectly verify if one-time secret keys OTsk were used multiple times by verifying if one-time public keys OTpk have been seen already.

<FIG> shows a signing system <NUM> comprising a signing device <NUM> having a stateful hash-base cryptographic function which is configured to output hash-based digital signatures HBsig generate by a stateful hash-based cryptographic function. The signing system <NUM> further comprises a logging device <NUM> and a verifying device <NUM>. The logging device <NUM> can serve not only one signing device <NUM> but several independent signing devices. Each of the signing device <NUM>, logging device <NUM> and a verifying device <NUM> comprises at least one processor which is configured to perform the described functions.

The signing device <NUM> is configured to receive data to be signed, see reference sign "dat" at <FIG>. The signing device <NUM> generate a hash-based digital signature HBsig for the data dat based on a current one-time private key. The hash-based signature HBsig comprises a one-time signature as described before with <FIG>. The signing device <NUM> generate a one-time public key OTpk based on the one-time signature and sends the generated one-time public key OTpk to the logging device <NUM>, see second arrow in <FIG>. Further, the signing device <NUM> sends the hash-based digital signature HBsig to the verifying device <NUM>, see third arrow in <FIG>. The signing device <NUM> can perform the sending tasks also in opposite temporal order, i. e first sends the hash-based digital signature HBsig to the verifying device <NUM> and then sends the generated one-time public key OTpk to the logging device <NUM>. In this case the sending tasks should be performed without or only short delay between each other.

The verifying device <NUM> is configured to generate a validation one-time public key valOTpk based on the hash-based digital signature HBsig received from the signing device <NUM> and the data dat. , the verifying device <NUM> determines the validation one-time public key valOTpk during verification of the received hash-based digital signature HBsig. The hash-based digital signature HBsig is verified by first computing a data digest using several parameters from the hash-based public key HBpk, which is known in the verifying device <NUM> and the data dat. Then the used one-time public key, i.e. the validation one-time public key valOTpk is computed from the hash-based signature HBsig. The validation one-time public key valOTpk in turn is used to compute the corresponding leaf L, see <FIG>. The leaf L, together with the authentication path AP, is used to compute an alternative root value for the tree. The verification succeeds if and only if the computed root value matches the one in the hash-base public key HBpk. In any other case it must return fail.

The verifying device <NUM> sends the determined valOTpk to the logging device <NUM> to validate whether the one-time private key OTsk used to generate the hash-based signature HBsig was used only once by the signing device <NUM>, see arrow <NUM> in <FIG>. The logging device <NUM> compares validation one-time public keys valOTpk because for each Merkle tree root there can be between thousands and millions of one-time public keys therefore it would not be possible to detect a misuse by only comparing Merkle trees' roots.

The logging device <NUM> is configured to store the generated one-time public key OTpk received from the signing device <NUM>. It is further configured to receive a validation one-time public key valOTpk from the verifying device <NUM> and to compare the validation one-time public key valOTpk with all one-time public keys stored in the logging device <NUM>. If the validation one-time public key valOTpk coincides with exactly one stored one-time private key, the logging device <NUM> provides a validation feedback signal to the verifying device <NUM>. If the validation one-time public key valOTkey does not coincide with exactly one stored one-time private keys, it provides a warning feedback signal to the verifying device <NUM>.

<FIG> shows a further embodiment of the signing system <NUM>, comprising a signing device <NUM>, a verifying device <NUM> and a logging device <NUM> comprising a separate logging unit <NUM> storing the one-time public key and an auditing unit <NUM> monitoring the stored one-time public keys in the logging unit <NUM>. The logging unit <NUM> and the monitoring unit <NUM> can be implemented as physically separated entities. The monitoring unit <NUM> can even be implemented physically collocated in a verifying device. The configuration and processing of the signing device <NUM> and the verifying device <NUM> remains unchanged with respect to signing system <NUM>.

In the signing system <NUM> the signing device <NUM> generates a stateful hash-based signature HBsig for an input data dat using the current one-time privat key OTsk. The signing device <NUM> generates the one-time public key OTpk corresponding to the one-time private key OTsk and sends it to the public logging unit <NUM>. Further, the signing device <NUM> sends the hash-based signature HBsig to the verifying device <NUM>, e.g., an IoT device. The verifying device <NUM> asks the auditing unit <NUM> if the validation one-time public key valOTpk is present exactly once in the public log. If this is the case, then it proceeds verifying the hash-based signature HBsig, otherwise it rises an alarm. Optionally, the alarm is raised also by the auditing unit <NUM>.

The functional split of the logging device into logging unit <NUM> and auditing unit <NUM> is explained in the following. The logging unit <NUM> is configured to receive the generated one-time public key OTpk from the signing device <NUM>. The auditing unit <NUM> is configured to receive the validation one-time public key valOTpk from the verifying device <NUM> and to send the validation feedback signal or the warning feedback signal to the verifying device <NUM>. The monitoring unit <NUM> monitors the logging unit <NUM> with respect to the stored one-time public keys OTpk. The monitoring can be continuously, e.g. the monitoring unit <NUM> can query the logging unit <NUM> periodically, in predefined time intervals or on request. , on receiving the validation one-time public key valOTpk from the verifying device <NUM>, the auditing unit <NUM> compares the validation one-time public key valOTpk with the stored one-time public keys OTpk in the logging unit <NUM> and provides the validation feed-back signal or the warning feedback signal to the auditing unit <NUM>.

Alternatively or additionally, after receipt of the generated one-time public key OTpk from the signing device <NUM> in the logging unit <NUM>, the logging unit <NUM> compares the generated one-time public key OTpk with all one-time public keys previously stored in the logging unit <NUM>, and provides the resulting validation feedback signal or the warning feedback signal to the auditing unit <NUM>. Alternatively, after receipt of the generated one-time public key OTpk, the logging unit <NUM> sends an indication to the auditing unit <NUM>, that a new one-time public key OTpk is stored, and the auditing unit retrieves the newly stored one-time public key OTpk from the logging unit <NUM>. The logging unit <NUM> can also forwards the newly stored one-time public key OTpk to the auditing unit <NUM>. Subsequently, the auditing unit <NUM> initiates the comparing of the newly stored one-time public key with those stored in the logging unit <NUM> and provides the resulting feedback signal, to answer a request for validation from the verifying unit <NUM>.

The auditing unit <NUM> stores the validation one-time public key received from the verifying device <NUM> and automatically provides the warning feedback signal if a warning feedback signal is received for the validation one-time public key later. The auditing unit <NUM> can notify all verifying devices, which received a validation feedback signal, if a warning feedback signal is provided for any of the one-time public key stored in the logging device. The logging unit <NUM> may be publicly accessible.

In signing system <NUM>, <NUM> the signing device <NUM>, <NUM> can send the hash-based digital signature and the data to be signed to the logging device <NUM>, <NUM>, and the logging device <NUM>, <NUM> generates the one-time public key based on the hash-based digital signature and the data. In a further embodiment the logging device <NUM>, <NUM> stores additional meta-information related to the hash-based digital signature received from the signing device <NUM>, <NUM> and/or the logging device <NUM>, <NUM> stores additional meta-information related to the verifying device received with the validation one-time public key from the verifying device <NUM>, <NUM>. The logging device <NUM>, <NUM> comprises more than one logging units <NUM> and/or more than one auditing units <NUM>.

The signing system <NUM>, <NUM> can comprise a large amount of verifying units <NUM>, <NUM>, especially all verifying units <NUM>, <NUM> which receive hash-based signatures generated by the signing device <NUM>, <NUM> of the signing system <NUM>, <NUM>.

In a variant of the embodiment, one or more auditing units <NUM> validate the hash-based signature HBsig on behalf of the verifying device <NUM>. The advantage is that auditing units <NUM> can be organized in a hierarchical structure and information can be audited using only a subset of data that is relevant in the given context, e.g., geographical region.

In a variant of the embodiment, the logging unit is shared across multiple signing devices <NUM>. The advantage is that a third party, that is independent from all the signing devices <NUM> that generate the log entries, can independently collect and verify the correct functioning of multiple signing devices <NUM>. In a variant of the embodiment, all communications among the parties are further encrypted, and all parties involved are mutually authenticated. In a variant of the embodiment, multiple distributed logging devices <NUM>, <NUM> or logging units (<NUM>) are used for redundancy and load-balancing.

<FIG> shows a logging device <NUM> comprising a data interface <NUM> to communicate with the signing device <NUM>, <NUM> and a storage unit <NUM> configured to store the one-time public keys received from the signing device <NUM>, <NUM>. The data interface and storage unit build up the logging unit <NUM>, described in <FIG>. The logging device <NUM> further comprises a validation unit <NUM> and a verifier interface <NUM> building the auditing unit <NUM>.

<FIG> shows a signing device <NUM> comprising a data interface <NUM> to communicate with the signing device <NUM>, <NUM>, a generating unit <NUM> comprising a hash-based cryptography function generating the hash-based signatures HBsig. The signing device <NUM> further comprises a verifier interface <NUM> to communicate with the verifying device <NUM>, <NUM> as well as a logging interface <NUM> for communication to the logging device <NUM>, <NUM>.

<FIG> illustrates the method for validating stateful hash-based digital signatures as a flow chart. Method identifies a security breach of stateful hash-based digital signatures. The method comprises the steps receiving S1 data to be signed, generating S2 a hash-based digital signature comprising a one-time signature calculated for the data based on a one-time private key, generating S3 a one-time public key based on the one-time signature, sending S4 the generated one-time public key to a logging device <NUM>, <NUM>, and sending S5 the hash-based digital signature to a verifying device <NUM>, <NUM>, in the signing device <NUM>, <NUM>. The method comprises in the verifying device <NUM>, <NUM> the steps generating S6 a validation one-time public key based on the hash-based digital signature and the data and sending S7 the validation one-time public key to the logging device <NUM>, <NUM>.

The method comprises following the steps performed in the logging device <NUM>, <NUM>: storing S8 the generated one-time public key, receiving S9 the validation one-time public key, comparing S10 the validation one-time public key with all one-time public keys stored in the logging device <NUM>, <NUM>, and providing S11 a validation feedback signal to the verifying device <NUM>, <NUM>, if the validation one-time public key coincides with exactly one stored one-time private key, and providing S12 a warning feedback signal, if the validation one-time public key does not coincide with exactly one stored one-time private key to the verifying device <NUM>, <NUM>.

This invention can be applied not only to XSMM but also to other stateful hash-based signatures based on one-time signatures, like Winternitz One-Time Signature (WOTS), Winternitz One-Time Signature Plus (WOTS+), Leighton-Micali One-Time Signatures (LM-OTS), LOTS and Merkle trees. This invention can be applied to XMSS^MT, which is a multi-tree variant of XMSS which is also described in the RFC <NUM> and NIST SP <NUM>-<NUM>.

Claim 1:
Signing system for validating stateful hash-based digital signatures, comprising at least one signing device (<NUM>, <NUM>), a logging device (<NUM>, <NUM>) and a verifying device (<NUM>, <NUM>), wherein each signing device (<NUM>) is configured to
- receive data to be signed,
- generate a hash-based digital signature comprising a one-time signature calculated for the data based on a one-time private key,
- generate a one-time public key based on the one-time signature,
- send the generated one-time public key to the logging device (<NUM>, <NUM>),
- send the hash-based digital signature to the verifying device (<NUM>, <NUM>),
the verifying device (<NUM>, <NUM>) is configured to
- generated a validation one-time public key based on the hash-based digital signature and the data,
- send the validation one-time public key to the logging device, and
the logging device (<NUM>, <NUM>) is configured to
- store the generated one-time public key,
- receive a validation one-time public key,
- compare the validation one-time public key with all one-time public keys stored in the logging device (<NUM>, <NUM>), and
- provide a validation feedback signal to the verifying device (<NUM>, <NUM>), if the validation one-time public key coincides with exactly one stored one-time private key, and
- provide a warning feedback signal, if the validation one-time public key does not coincide with exactly one stored one-time private key to the verifying device (<NUM>, <NUM>).