What is hashing and why is it important in cybersecurity

The hash functions used for cybersecurity and computer science add collision resistance, which means that it is infeasible to find two inputs that produce the same output. This is important to common applications of hash functions, such as integrity protections and hash tables. In fact, it’s so important that a hash function is considered broken as soon as a hash collision has been successfully generated for it. This is why the MD5 and SHA-1 hash functions are no longer used for security-related applications.

Hash function non-locality is important to collision resistance and means that similar inputs to the hash function produce very different outputs. In general, flipping a single bit of the input to a cryptographically secure hash function should flip half of the output bits. This is important because otherwise, tools such as hill climbing algorithms could be used to find hash collisions.

Hash functions are designed to be one-way functions, meaning that you can’t calculate the input from the output.  Think of a hash function like a paper shredder. Once you put a document through the shredder, it’s easy to see the pile of shredded pieces (the output), but it’s almost impossible to put those pieces back together to recreate the original document (the input).

Additionally, hash functions should be collision-resistant. This means that it’s difficult to find two inputs that produce the same output.

This combination might make it seem like hash functions should involve a source of randomness. If the calculation is random, then it’s much easier to hit these goals. However, this would destroy most of the applications of hash functions, which rely on them being deterministic calculations. This means that hashing the same input will always produce the same output.

Hash functions and encryption algorithms are both cryptographic algorithms, meaning that they use similar techniques and mathematical operations to achieve their goals. However, hashing is not encryption, and the two types of algorithms are designed for different purposes.

Encryption is designed to protect the confidentiality of data using a secret key. If someone encrypts a message, then it is scrambled in a way that makes it unreadable to anyone without the decryption key. Encryption is designed to protect against eavesdroppers and is distinct from hashing due to its use of secret keys and reversibility (e.g., you want the recipient to actually be able to read the message).

In contrast, hash functions are designed to protect data integrity. There are no secret keys involved, and these functions are specifically designed to be irreversible (which is essential to their collision resistance). Also, a hash value is commonly sent alongside the original data, so hash functions don’t protect that original data from being read.

Encryption and hashing are distinct but complementary processes. Encryption prevents eavesdroppers from reading sensitive information, and hashing can help to detect modifications to data. Together, they address potential security risks of storing or transmitting sensitive data on untrusted systems (like the Internet).

A digital signature is a cryptographic operation that ensures both data integrity and authenticity. It accomplishes this by combining hashing and encryption.

The role of a hash function in digital signatures is to improve efficiency and enable easy detection of changes to the data. The first step of the digital signature process is to hash the data to be signed. 

The signature is generated using a public key encryption algorithm in reverse. The signer uses their private key to “encrypt” the hash of the message, generating the signature. When the message is sent, the digital signature and the signer’s public key are transmitted with it. Using the public key, the recipient can “decrypt” the signature to produce the hash of the message. They can then compute the hash of the message they received and compare the two versions to see if anything changed. In a digital signature, hashing makes it easy to detect changes to the data, protecting integrity. Public key cryptography provides authentication since only someone with knowledge of the private key could generate a valid digital signature that could be validated using their public key.

Hash functions are used for various purposes. These include everything from enhancing the efficiency of data lookups to security applications to enabling technologies like blockchain.

Hash tables are an application of hashing in computer science designed to enhance the speed and efficiency of data retrieval. They use hash functions for indexing when storing records.  For example, imagine the scenario where an application needs to store various user records that are accessed based on their name. To find a particular user’s record, they’d need to search through the entire list from the beginning of the alphabet to that user, which could take a variable amount of time depending on the number of users and the name in question.

With a hash table, the records are organized into memory based on the hash of the user’s name. When performing a lookup, the application would hash the name in question and would know where in memory to look for the record.

This use case takes advantage of hash function collision resistance, which means that multiple inputs are highly unlikely to produce the same output. In theory, the hash values of the users’ names should be uniformly distributed over the space of possible outputs. For example, if you had 128 users and a hash function with 256 possible outputs, it’s unlikely that any two users would have the same hash and highly unlikely that three or more would.

This is useful because it dramatically speeds up the process of retrieving a user’s record. For the price of a single hash calculation, the application moves from searching through a list of 128 user records to only checking the set associated with a particular hash function. On average, this changes the complexity from 64 checks to 1-2.

Password-based authentication systems need a way to determine if a provided password is correct. The easiest way of doing so would be to store a list of usernames and the associated passwords. When a user tries to authenticate, the system could then compare a provided password with the stored version. However, this approach is horribly insecure. Anyone with access to the password file could steal the passwords of everyone else on the system.

Password storage best practices involve storing a hashed and salted password rather than the plaintext password. Since hash functions are deterministic, comparing the hash of a provided password to a stored hash is just as good as comparing the two passwords themselves. Collision resistance means that it’s infeasible for an attacker to find another password that would produce the same hash and wrongfully provide access to a user’s account.

Salting is a mechanism used to protect against password-guessing attacks using hashes. Since hash functions are deterministic, two users with the same password, a regrettably common occurrence, would have the same password hash. Additionally, an attacker could precompute the hashes of common passwords, producing something called a rainbow table.  Salting involves adding a randomly generated value to a password before hashing it for the first time. This value is stored alongside the password, enabling it to be used when computing hashes during the authentication process. Its role is to ensure that identical passwords don’t produce identical hashes and to render rainbow tables unusable.

Signature-based analysis is a key component of any antimalware system. These systems will maintain a database of known malware variants and check new files against it. If a file matches a signature in the database, then the file is verified to be malware.

If antimalware used filenames in this database, it would be easy to evade detection, and storing the entirety of each malicious executable would be inefficient and unscalable. Instead, the signatures in the malware database are hash values of the executables. This provides an efficient but secure method of identifying whether a file is a known malicious executable. 

Some best practices for using hash functions include:

• Choose the Right Cryptographic Algorithm: Hash functions and encryption algorithms may seem similar, but they’re designed for different purposes. Hash functions should only be used to ensure data integrity, not confidentiality.

• Select a Secure Hash Function: Hash functions are considered insecure once a hash collision has been detected for them. Although these can be used for some purposes (like hash tables), only secure algorithms should be used for password storage and other security-focused applications.

• Use an Existing Implementation: Cryptographic algorithms like hash functions can be tricky to implement and fragile. Use an existing implementation of a trusted algorithm rather than developing your own. 

• Follow Best Practices: Always follow established best practices when using hash functions for security-related tasks. For example, passwords should always be stored using a secure hash algorithm and a unique, random salt for each password.