How Hashing is Useful in Recent Technologies ?
Hashing is a valuable data structure designed to solve the problem of efficiently finding and storing data in an array.
For example, if you have a list of 90000 integers and you've given one number to search , you'll scan each one until you discover a match.
It will take a large amount of time for you to search through the full list for that specific number. This manual scanning method is not only time-consuming, but also inefficient. You may narrow down the search and find the number in seconds using hashing in the data structure.
This blog will provide a deeper understanding of the hashing
What is the concept of hashing in relation to Data Structures?
The use of a hashing function is to map a large piece
of data into small tables is known as hashing in the data structure. The
message digest function is also another name for it. It's a strategy for
identifying a single object from a group of similar items.
The data is stored in an array format using hash tables. A
unique index number is assigned to each value in the array. For each value
stored in an array format, hash tables use a technique to generate these unique
index numbers. This technique is called as Hash Technique .
Rather than finding the data, you simply need to locate the
index of the required item. You can instantly scan the full list and retrieve
the item you want with indexing. When you need to insert data at a certain
location, indexing really helps a lot. You can update and retrieve data in
seconds, no matter how big or small the table is.
Why is Hashing Required ?
We must execute numerous procedures on vast amounts of data
after they have been stored. For datasets, lookups are unavoidable.
Lookups/searches using linear and binary search have time complexity of O(n)
and O(log n), respectively. These complexities increase significantly as the
quantity of the dataset grows, which is unacceptable.
We require a technique that is independent of data size.
Hashing allows lookups to take place in constant time, i.e. O(1).
In a data structure, hashing is a two-step procedure.
The hash function produces a small integer or hash value for
the item. This integer is used as an index to store original data.
It keeps the information in a hash table. A hash key can be
used to quickly locate data.
Examples of Hashing in Data Structure
The following are some real-world data structure hashing
examples:
In schools, each student is assigned a unique roll number by
the teacher. Later, the teacher will use that roll number to look up
information of that particular kid.
There are no limits to the amount of books that can be found
in a library. Each book is given a unique number by the librarian. This
one-of-a-kind number helps in locating the books in the library.
What are Hash Functions ?
Hashing algorithms are functions that process a given input
and produce a fixed-length result (the hash, or hash value). The hash value is
a summary of the original information.
A data structure's hash function maps data of any size
to data of a specific size. It returns a tiny integer number (sometimes known
as a hash value), as well as hash codes and hash sums.
The following conditions must be satisfied by the hash function:
Hash Table
In a data structure, hash tables are used to store key-value
pairs. The hash function is then used to generate an index for the hash table.
Insert, update, and search activities are all performed with the help of this
unique index.
How does Hashing in Data Structure Works?
Hashing is a function that maps strings or numbers into a small integer value. Hash tables use a hashing function to retrieve an item from a list. The goal of the hashing technique is to uniformly distribute data over an array. Hashing assigns a unique key to each element. This key is used by the hash table to access the data in the list.
The data is stored in a key-value pair in a hash table. The
hashing function takes the key as an input. For each value recorded, the hash
function generates a unique index number. The value that corresponds to that
key is stored in the index number. As an output, the hash function returns a
small integer number. The hash value is the output of the hashing
function.
Collision Resolution Techniques
When two keys in a hash table are assigned the same index
number, a collision occurs. Because each index in a hash table is designed to
store just one value, the collision causes a problem. To manage the performance
of a hash table, hashing in data structures uses many collision resolution
approaches.
Linear Probing
In a data structure, hashing produces an array index that is
already being used to store a value. Hashing executes a search operation and
probes linearly for the next empty cell in this situation.
Double Hashing
Two hash functions are used in the double hashing technique.
When the first hash function creates a collision, the second hash function is
used. It stores the value using an offset index.
The following is the formula for the double hashing
technique:
(firstHash(key) + i * secondHash(key)) % sizeOfTable
What Does a Hash Function Do ?
In cryptography, one of the purposes of a hash function is
to take a plaintext input and generate a hashed value output of a particular
size that cannot be reversed. Strong hash functions, in a nutshell:
• Ensure data integrity
• Protect against unwanted modifications
• Protect stored passwords and Operate at various speeds to
suit various needs
Ensure Data Integrity
In public key cryptography, hash functions are used to
assure data integrity. Hash functions, act as a checksum, or a mechanism for
someone to determine whether data has been tampered after it has been signed.
It also acts as a technique of confirming one's identity.
As an example, suppose you've used public Wi-Fi to send me
an email. (By the way, don't do it, It's quite risky.) So you compose your
message, sign it with your digital certificate, and send it across the
internet.
An example of a digitally signed email that has been
tampered with in transit using a MitM attack is shown above. When any of the
email content is modified after being digitally signed, the hash digest changes
completely, indicating that it cannot be trusted.
So, now that I've received the message, I'm curious whether
if it's genuine. What I can do now is re-produce the hash value using the hash
value your digital signature offers (along with the algorithm it says you used)
to see if the hash value I generate matches the one you sent. If it matches,
that's fantastic; it means no one has tampered with it. If it doesn't, I
know I shouldn't trust it.
Even minor changes in a message, such as capitalising a
letter instead of using lowercase, or substituting an exclamation mark for a
period, will result in the production of a completely new hash value. But
that's the point: no matter how big or tiny a modification is, the difference
in hash values will tell you it's not genuine.
Secure Against Unauthorized Modifications
One of the most useful features of a cryptographic hash
function is that it promotes data integrity. Is it true, however, that if you
apply a hash to data, the message cannot be changed? No. It does. However,
notify the message recipient that the message has been modified. Because even
the tiniest changes to a message result in the development of a whole new hash
value, this is the case.
Consider hashing in the same way you would a smoke alarm.
While a smoke alarm will not prevent a fire from igniting, it will alert you to
the danger before it is too late.
Protect against unwanted modifications
Many websites nowadays allow you to save your passwords so
you don't have to remember them each time you log in. However, keeping
plaintext passwords in a public-facing server is risky , since it exposes
sensitive information to thieves. As a result, most websites uses hash
passwords to generate hash values, which they store instead.
However, password hashes alone are insufficient to protect
you from certain types of assaults, such as brute force attacks. This is why
you must first add a pinch of salt. Before plaintext passwords are hashed, they
are given a salt, which is a unique, random number. This adds another layer of
protection and protects passwords from password cracking techniques such as
rainbow table assaults.
Operate at Different Speeds, Suiting Different Purposes
It's also worth noting that hash functions aren't a
one-size-fits-all solution tools. As previously stated, depending on their
architecture and hash speeds, different hash functions serve different
purposes. They operate at various rates, with some being faster and others
being much slower. Depending on how you use a hashing algorithm, these speeds
can help or hurt its security. As a result, some algorithms are classified as
secure hashing algorithms while others are not.
When creating secure connections to websites, for example,
you'd want to employ a quick hashing technique. This is an example of when
having a faster speed is beneficial because it improves the user experience. If
you wanted to enable your websites to save passwords for your clients, though,
you'd want to employ a slow hashing technique. At scale, a password-cracking
attack (such as brute force) would be required, which would take more time and
computing resources for hackers.
Characteristics of a Strong Hash Algorithm
So, what makes a hashing algorithm strong? All good ones
share a few crucial characteristics:
Determinism
A hash method should be deterministic, which
means it should always produce an identical result regardless of the size of
the input. This means that the output from hashing a single sentence should be
the same size as the output from hashing an entire book.
Pre-Image Resistance
A powerful hash algorithm is one that
is preimage resistant, which means that reversing a hash value to obtain the
original plaintext message is impossible. As a result, hashes are considered
irreversible, one-way functions.
Collision Resistance
When two things collide, it is called
a collision. This idea is carried over to hash values in cryptography. A
collision occurs when two distinct samples of input data produce identical
outcomes. This is bad news because it suggests the hashing algorithm you're
using is broken and so unsecure. The fear is that someone could produce a
malicious file with a fake hash value that matches a genuine (safe) file and
pass it off as the genuine article since the signatures match. As a result, a
good and reliable hashing method is one that avoids collisions.
Avalanche Effect
The avalanche effect states that any
change in an input, no matter how minor, will cause a tremendous change in the
output. The term "avalanche effect" refers to how a little
modification (such as adding a comma) snowballs into something considerably
greater.
Hash Algorithm Speed
Hash algorithms should be fast enough
to be useful. Hashing algorithms should compute hash values fast in many cases;
this is regarded as an ideal attribute of a cryptographic hash function. This
feature, on the other hand, is a little more subjective. You see, faster isn't
necessarily better because the hashing algorithm's speed should be determined
by how it will be used. You may desire a faster hashing algorithm at times, but
you may also want to employ a slower one that takes longer to run. The former
is better for connecting to websites, while the latter is better for hashing
passwords.
Where You’ll Find Hashes in Use
However, where do you find these hash functions?
Take a look at the technology that surrounds you.
Hashing can be used for a variety of tasks, including signing new software and verifying digital signatures, as well as securing website connections on your PC and mobile web browsers. It also works well for indexing and retrieving content from web databases. Hashing, for instance, is used to verify:
Data blocks of cryptocurrencies and a variety of blockchain
technologies
Data integrity emails, documents, and applications software
To store the password strong hashes rather than password
themselves in online databases.
Hash functions are used extensively in public-key
cryptography. Hash functions, for example, are made easier through the use of:
SSL/TLS certificates (i.e., website security certificates)
Code signing certificates
Document signing certificates
Email signing certificates
Hash vs Encryption
Are hashing and encryption are the same things? Although the
answer is no, Yes, they're both cryptography functions that rely on algorithms
to function. But that's about the extent of the resemblances.
A hash function is a one-way function, as you now know. Its
purpose is to transform readable plaintext data to an unreadable hexadecimal
string of digits, but not the other way around. On the other hand, encryption
is referred to as a two-way function. Because the whole idea of being able to
encrypt something is to prevent unauthorized or unintended people from
obtaining the information. Such you encrypt data so that only the person who
has the key may decrypt it.
Popular Hashing Algorithms
Let's be clear - MD5 is a broken algorithm
If you've ever learned a programming language, even if it
was a long time ago, you're probably familiar with this algorithm. It's perhaps
one of the most well-known. This hash method was widely utilized in the past
and remains one of the most well-known hashing algorithms now. Despite the fact
that it was created to be used as a cryptographic algorithm function, it is no
longer regarded as safe to use for that purpose because it has been
compromised. On basic computers, for example, it is feasible to swiftly
manufacture collisions.
When MD5 is used to directly hash passwords, there is an
even easier way to crack them with the help of Google. There's a strong
possibility you'll get the hash's before-state within milliseconds if you type
it into the search box!
Now let’s look at this example:
You may believe your passwords are secure since they are
saved as MD5 hashes, but if someone gains access to your database, they can
just type the hash into Google to obtain its true value!
MD5 is considered "cryptographically flawed and unfit
for further usage," according to the CMU Software Engineering Institute.
It was widely accepted for a long time, but it's currently primarily used to
protect data from unintended corruption.
SHA-family
The Secure Hash Algorithm ( SHA ) is a cryptographic hash
function developed by the National Security Agency of the United States. Many
years ago, the SHA-0 algorithm (first released in 1993) was corrupted. A
160-bit (20-byte) hash value is generated by SHA-1 (1995). It's usually written
as a 40-digit hexadecimal number. It was weakened in 2005 when theoretical
collisions were identified, but its true "death" came in 2010 when
various groups began to advocate that it be replaced.
After repeated successful attacks, the big three – Microsoft, Google, and Mozilla – stopped supporting SHA-1 SSL certificates in their browsers in 2017. The MD4 and MD5 were designed using methods similar to those used in the development of SHA-1.