Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Hash functions and signature schemes
3.
The Lamport One-Time Signature
3.1.
From one-time to many-time signatures: Merkle’s tree-based signature
4.
Frequently Asked Questions
4.1.
What is the hash algorithm in digital signature?
4.2.
What is hash based signature?
4.3.
What is a sha256 signature?
5.
Conclusion 
Last Updated: Mar 27, 2024

Hash Based Signature Schemes

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Let's ensure we understand the foundational concepts before delving further into the subjects. Here is a brief introduction if you are unfamiliar with the Hash-based signature scheme.

Hash Based Signature Schemes

Leslie Lamport created the first Hash-based signature scheme in the late 1970s, and Ralph Merkle and others further refined it.

A one-time signature scheme (OTS), in which each key pair may only be used to sign one message, is the foundation of a hash-based signature scheme. An attacker can easily fabricate signatures if an OTS key pair is used to sign two distinct messages.

This article explains the details of Hash Based Signature Schemes, in which we will talk about Hash functions and signature schemes, The Lamport One-Time Signature, and Merkle’s tree-based signature.
 

Without further ado, let's get started.

Hash functions and signature schemes

It's essential that you have some acquaintance with cryptographic hash functions to comprehend hash-based signatures. These operations take a string of any length as input, normally, and output a fixed-size "digest" as a result. The digests produced by popular cryptographic hash algorithms like SHA2, SHA3, or Blake2 range in size from 256 to 512 bits.
 

💁 A function H(.) must fulfill certain security requirements to be referred to as a "cryptographic" hash. There are plenty of these, but we'll simply concentrate on the following three here:

☑️ Pre-image resistance: Finding an input X such that H(X) = Y should take some time given some output Y = H(X). (There are many limitations to this, but the best such assault should ideally take as long as a brute-force search of whichever distribution X is selected from.)
 

☑️ Second-preimage resistance:In a subtly way, this differs from pre-image resistance. An attacker should have a difficult time discovering a new input X' such that H(X) = H(X') given some input X.

 

☑️ Collision resistance: Finding any two values of X_1, X_2, such that H(X_1) = H(X_2) should be difficult. This is a stronger assumption than second-preimage resistance, as the attacker can choose any two messages.

 

These characteristics are thought to be offered by the example hash functions we discussed earlier. That is to say, none of them have been broken by any meaningful (or even hypothetical) attack. Of course, that may always change, in which case we'd probably cease using them. (We'll go into more detail later about the unique case of quantum assaults.)

It's also useful to quickly review that fundamental since we aim to employ hash functions to build signature schemes.

A user (or "signer") generates a set of keys called the public key and the private key as part of a digital signature system, which is a public key primitive. The private key is kept by the user, who may then use it to "sign" any message they choose, creating a digital signature. Anyone possessing the public key can confirm a message's accuracy and the signature accompanying it.

From a security standpoint, "existential unforgeability" or unforgeability is the key feature we seek in a signature system. This condition ensures that a third party (an attacker) attempting to counterfeit your signature on a communication you did not sign shouldn't be able to do so.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

The Lamport One-Time Signature

Leslie Lamport, a mathematician, created the first hash-based signature technique in 1979. Lamport noted that a very strong signature system might be created with only a one-way or a basic hash function.

That is, if you just need to sign one message, it is powerful! See more below about this.

For the sake of this explanation, let's assume that we have the following component: a hash function that accepts 256-bit inputs and generates 256-bit outputs. A good example of such a function would be SHA256. We'll also require a method for producing random bits.

Assume that we want to sign 256-bit communications. First, we must create a set of 512 unique, 256-bit long random bitstrings to create our secret key. We'll divide those strings into two different lists for ease of use, and we'll refer to each one by an index as follows:

sksk10, sk20,....sk2560

sk1 = sk11, sk21,...sk2561

 

The lists represent the secret key we'll use for signing (sk0, sk1). We now just hash each random string with our function H(.) to create the public key. This results in the second set of lists:

pk0 = H(sk10), H(sk20),...,H(sk2560)

pk1 = H(sk11),H(sk21),....,H(sk2561)

 

We may now share our public key with everyone in the world (pk0, pk1). We may, for instance, email it to our friends, include it in a certificate, or publish it on Keybase.

Let's imagine we wish to use our secret key to sign a 256-bit message M. We first decompose M into a sequence of 256 bits, which we then represent:

M_1, \dots, M_{256} \in \{0,1\}

The remainder of the signing algorithm is obscenely straightforward. From the first to the last bit of the message, we simply choose a string from one of the two secret key lists. Depending on the value of the message bit we're trying to sign, we'll pick from a certain list.

In more detail, for integers i=1 to 256, if the ith message bit Mi = 0, we extract the ith secret key string (sk0i) from the(sk0 ) list and output that string as a component of our signature. We copy the appropriate string (ski1) from the (sk1) list if the message bit Mi = 1. We concatenate all of the strings we chose after doing this for each of the message bits. This is how we sign off.

Here is a toy example of the procedure where the secret key and message are only eight bits long (for simplicity). The colored boxes below each depict a distinct 256-bit random string:

sample example

A user who already has the public key (pk0, pk1) can quickly verify a signature when she receives a message M and one. For each such string, let si stand in for the ith component of the signature. She just computes hash H(s i) and verifies the associated message bit Mi. The outcome should match the matching element from (pk0) if Mi = 0. The outcome must match the element in (pk1) if M i = 1.

If every component of the signature matches the appropriate part of the public key when hashed, the signature is considered to be legitimate. Here is an illustration of the verification procedure for at least one signature component, albeit it is admittedly rudimentary:

Step image

If your first reaction to Lamport's plan seems kind of nuts, you are somewhat correct and partially incorrect.

Let's begin with the bad. The size of Lamport signatures and keys—on the order of thousands of bits—is first and foremost readily apparent. A fundamental security flaw in this system is that each key can only be used to sign one message, which is far more important. As a result, Lamport's technique illustrates a "one-time signature."

Remember that every Lamport signature reveals exactly one of the two potential secret key values at each place to see why this constraint arises. The signature system functions properly when we sign just one message. The secret key values for both messages will ultimately be disclosed if we ever sign two messages that differ in any position i. This might be a challenge.

Imagine that a hacker discovers two legitimate signatures on various emails. She might be able to sign a third mail we never actually signed using a straightforward "mix and match" forgery attack. In our toy example, this is how that may appear:

Step image

The number of messages you've given the attacker to choose from and how varied they are will determine how much this harms you. But the news is rarely positive.

So, to summarise our findings about the Lamport signature technique. It's easy. It moves quickly. And yet, it kind of stinks for a variety of pragmatic reasons. Perhaps we can perform a bit better.

From one-time to many-time signatures: Merkle’s tree-based signature

The Lamport system is a decent first step, but it has a lot of limitations, including the inability to sign numerous messages with a single key. Nobody was more motivated by this than Ralph Merkle, a pupil of Martin Hellman. He soon thought of a brilliant solution to this issue.

Even if we can't exactly follow Merkle's steps, let's try to recapture some basic concepts.

Let's assume we intend to sign N messages with Lamport's signature. The simplest method for the original Lamport scheme is to create N distinct keypairs and then concatenate all of the public keys into a single mega-key.

The signer can now sign N separate messages by utilising exactly one secret Lamport key per message if she keeps hold of all N secret key components. This fixes the issue without asking her to use a secret key again. Since the verifier has access to every public key, it can validate any message they receive. Never is a Lamport key used twice to sign.

This strategy is a complete failure.

In particular, this naive method requires the signer to disseminate a public key N time larger than a typical Lamport public key to sign N times. She will also have to keep track of a similar number of hidden keys. People will eventually become tired of this, and it is unlikely that N will ever reach very big values. Merkle is here.
 

💁 Merkle suggested a method for maintaining N-way message signing while avoiding the linear-cost blowup of public keys. Merkle's plan operated as follows:

1️⃣ Create N unique Lamport keypairs first. Those are (PK1, SK)dots, sometimes known as (PK N, SKN).
 

2️⃣ The next step is to position each public key at the leaf of a Merkle hash tree (see below) and determine the tree's root. The "master" public key of the new Merkle signature scheme will be this root.
 

3️⃣ The signer keeps all of the Lamport public and secret keys for signing.

Frequently Asked Questions

What is the hash algorithm in digital signature?

The original data, encrypted using the signer's private key, is essentially a one-way hash (or message digest) of the digital signature. The recipient initially decrypts the digital signature using the signer's public key to confirm the authenticity of the material.

What is hash based signature?

A one-time signature scheme (OTS), in which each key pair may only be used to sign one message, is the foundation of a hash-based signature scheme. An attacker can easily fabricate signatures if an OTS key pair is used to sign two distinct messages.

What is a sha256 signature?

A text or data files "signature" can be represented by a cryptographic hash, also called a "digest." SHA-256 produces a unique 256-bit (32-byte) signature for a text.

Conclusion 

Congratulations on finishing the blog! We have discussed the details of Hash Based Signature Schemes, in which we talk about Hash functions and signature schemes, The Lamport One-Time Signature, and Merkle’s tree-based signature.

We hope this blog has helped you enhance your knowledge of Hash Based Signature Schemes. If you'd like to learn more, Check out the following links:

🔥 Signature Schemes

🔥 Cryptography

🔥 Hash Function

 

Recommended Readings:

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please upvote 🏆 our blogs 🎈 if you find them helpful and informative!

Happy coding🤗

Previous article
The Oil and Vinegar Signature Scheme - We are not making food
Next article
Lamport Signature Scheme
Live masterclass