Which of the following statements about cryptographic hash is least correct? (Source: Wentz QOTD)
A. A hash function always produces the same hash if given the same message
B. A hash function might produce the same hash if given distinct messages
C. The time of computing hash typically increases exponentially with the message size
D. Implementation of the digital signature can be as simple as encrypting a message digest by the sender’s private key

Kindly be reminded that the suggested answer is for your reference only. It doesn’t matter whether you have the right or wrong answer. What really matters is your reasoning process and justifications.

My suggested answer is C. The time of computing hash typically increases exponentially with the message size.

Algorithms and Big O Notation

Algorithms for encryption, hashing, cryptanalysis, sorting, etc. can be measured in terms of complexity and expressed in the notation of Big O.

For example, an algorithm processing data of 1KB can take 1 second, while 100KB for 1 second/O(1), 10 seconds/O(log n), 100 seconds/O(n), 10,000 seconds/O(n^2), or even longer. The variety of the processing speed depends on the implementation of the algorithm. 

The time of computing hash will increase with the message size. It will typically increase gradually or proportionally, but not “exponentially.”

The uniqueness of Cryptographic Hash

A hash function always produces the same hash if given the same message. In other words, a hash uniquely identifies a file or message. The following are some scenarios of hash applications:

• Dedupe files, pictures, or documents. Before saving files to the storage, check if the hash exists. If so, only metadata is saved, and the file itself can be ignored. Imagine an email server is sending an email with a 10MB photo to 100 recipients, and the email may be forwarded to more people.
• Antivirus or IDS
• Version control, e.g., Git uses linked lists of hashes.
• Blockchain, Cyber coins use linked lists of hashes.

Hash Collision

It is called a collision if a hash function produces the same hash given distinct messages. Only a perfect hash function renders no collision. Hash functions might produce collisions. MD5 is a good example of a vulnerable hash function that produces collision. However, it is practically infeasible or unachievable to generate a collision on purpose.

MD5

One basic requirement of any cryptographic hash function is that it should be computationally infeasible to find two distinct messages that hash to the same value. MD5 fails this requirement catastrophically; such collisions can be found in seconds on an ordinary home computer.

Source: Wikipedia

Digital Signature

The digital signature can be a message digest or hash encrypted by the sender’s private key.

Reference

• Big O Notation (using Ruby)
• Cryptographic hash function
• Security of cryptographic hash functions
• Hashing Functions and Their Uses In Cryptography
• Big O notation
• What is the time complexity for cryptographic hash function?
• 8 time complexities that every programmer should know
• What is Big O Notation Explained: Space and Time Complexity
• Hash table
• E-signature
• Authenticated Document / Data Exchange
• Our choice of digital signature algorithm explained
• The beautiful hash algorithm
• SHA-256 Cryptographic Hash Algorithm
• 6.5. Hashing