What is Cryptography?
Cryptography is the study of secure communications techniques that allow only the sender and intended recipient of a message to view its contents. The term is derived from the Greek word kryptos, which means hidden. It is closely associated to encryption, which is the act of scrambling ordinary text into what’s known as ciphertext and then back again upon arrival. In addition, cryptography also covers the obfuscation of information in images using techniques such as microdots or merging.
History Of Cryptography:
Ancient Egyptians were known to use these methods in complex hieroglyphics, and Roman Emperor Julius Caesar is credited with using one of the first modern ciphers. Cryptographic techniques mainly encryption & decryptions have been used for centuries to protect military and political issues. Throughout this history of cryptology, confidentiality has taken the primary seat and it was believed that if the secrecy is maintained (using symmetric encryption and secret key) then the authentication will automatically be achieved. The logic was if decryption of an encrypted text results in a meaningful message it must have been constructed by someone who knows the secret key. The trend changers were Diffie and Hellman, who are credited for advent of public key cryptography in mid 70s. Their seminal paper “New Directions in Cryptography”] introduced a number of relevant concepts like Digital Signatures and differentiated Confidentiality from Authentication and to quite an extent initiated the development of cryptographic schemes for the protection of authenticity. These schemes use a very important cryptographic primitive named ‘Cryptographic Hash Functions’. However cryptographic hash functions have received much less attention from the crypto logic community than encryption schemes in the past.
Cryptographic Hash Functions, CHF – one of the most important tools in modern cryptography and security.
- In crypto, CHF instantiates a Random Oracle paradigm
- In security, used in a variety of authentication and integrity applications
- Not the same as “hashing” used in DB or CRCs in communications
- Purpose: produce a fixed-size “fingerprint” or digest of arbitrarily long input data
- Why? To guarantee integrity
Properties of a “good” cryptographic HASH function H():
- Takes on input of any size
- Produces fixed-length output
- Easy to compute (efficient)
- Given any h, computationally infeasible to find any x such that H(x) = h
- For a given x, computationally infeasible to find y such that H(y) = H(x) and y≠x
- Computationally infeasible to find any (x, y) such that H(x) = H(y) and x ≠ y
Same Properties Re-stated:
- Cryptographic properties of a “good” HASH function:
- One-Way-ness (#4)
- Weak Collision-Resistance (#5)
- Strong Collision-Resistance (#6)
- Non-cryptographic properties of a “ good ” HASH function
- Efficiency (#3)
- Fixed Output (#2)
- Arbitrary-Length Input (#1)
Construction
- A hash function is typically based on an internal compression function f() that works on fixed-size input blocks (Mi)
- Sort of like a Chained Block Cipher
- Produces a hash value for each fixed-size block based on (1) its content and (2) hash value for the previous block
- “Avalanche” effect: 1-bit change in input produces “catastrophic” and unpredictable changes in output
Simple Hash Functions
- Bitwise-XOR
- Not secure, e.g., for English text (ASCIl<128) the high-order bit is almost always zero
- Can be improved by rotating the hash code after each block is XOR-ed into it
- If message itself is not encrypted, it is easy to modify the message and append one block that would set the hash code as needed
- Another weak hash example: IP Header CRC
Another Example
- IPv4 header checksum
- One’s complement of the one’s complement sum of the IP header’s 16-bit words
The term hash function has been used in computer science from quite some time and it refers to a function that compresses a string of arbitrary input to a string of fixed length. However if it satisfies some additional requirements (as detailed further), then it can be used for cryptographic applications and then known as Cryptographic Hash functions.
Cryptographic Hash functions are one of the most important tool in the field of cryptography and are used to achieve a number of security goals like authenticity, digital signatures, pseudo number generation, digital steganography, digital time stamping etc.
Cryptographic Hash Functions are broadly of two types i.e. Keyed Hash functions; the one which uses a secret key, and Un-keyed Hash Functions; the other one which does not uses a secret key. The keyed Hash functions are referred to as Message Authentication code.
Unkeyed or simply Hash functions(some time also known as MDC – Manipulation Detection Code)can further classified into OWHF (One Way Hash Functions), CRHF (Collision Resistant Hash Functions) and UOWHF (Universal One way Hash Functions) depending on the additional properties it satisfies.
One Way Hash Functions (OWHF)
OWHF is a hash function H that satisfies the following requirements:
- H can be applied to block of data of any length. (In practice, ‘any length’ may be actually be bounded by some huge constant, larger than any message we ever would want to hash.)
- H produces a fixed-length output.
- Given H and x (any given input), it is easy to computer message digest H(x).
- Given H and H(x), it is computationally infeasible to find x.
- Given H and H(x), it is computationally infeasible to find x and x’ such that H(x) = H(x’)
The first three requirements are must for practical applications of a hash function to message authentication and digital signatures. The fourth requirement also known as pre-image resistance or one way property, states that it is easy to generate a message code given a message but hard (virtually impossible) to generate a message given a code.
Security Services of Cryptographic Hash Functions
Achieving Integrity & Authentication
Verifying the integrity and authenticity of information is a prime necessity in computer systems and networks. In particular, two parties communicating over an insecure channel require a method by which information sent by one party can be validated as authentic (or unmodified) by the other.
Message Integrity & Authentication may be implemented in multiple ways. Symmetric Encryption based mechanisms may be used but they have their own drawbacks. Drawbacks like speed, cost factor, optimization for data sizes etc. have been highlighted. Such methods combine the Confidentiality and Authentication functions. However there are scenarios where encrypting full message (confidentiality) is not required. For such applications keeping message secret is not the concern but authenticating it is important. For example in SNMP (Simple Network Management Protocol), it is usually important for a managed system to authenticate incoming SNMP commands (like changing the parameters at the managed system), but concealing the SNMP traffic is not required.
Implementing Efficient Digital Signatures
Digital signature is a security goal of a cryptosystem which intends to achieve the goal of authenticity and a security service or property of non-repudiation. MAC and Hash Functions alone do not implement the Security goal of Digital Signatures. It was Diffie and Hellman who first realised the need for a message dependent electronic signature (fingerprint) to avoid disputes between sender and receiver. RSA was the first public key crypto systems with digital signature capabilities. However there has been an interesting part of this invention.
Hash functions are used to optimize the digital signature schemes. Without the use of Hash, the signature will be of same size as message. The fundamental concept here is instead of generating the signature for the whole message which is to be authenticated; the sender of the message only signs the digest of the message using a signature generation algorithm. The sender then transmits the message and the signature to the intended receiver. The receiver verifies the signature of the sender by computing the digest of the message using the same hash function as the sender and comparing it with the output of the signature verification algorithm. It is obvious that this approach saves a lot of computational overhead involved in signing and verifying the messages in the absence of hash functions.
Authenticate Users of Computer Systems
Hash functions may be used to authenticate the users at the time of login. The passwords are stored in the form of message digest to avoid access of the same even to Database Administrators (because of Pre-Image resistance of Hash digest). Whenever user tries to login and enter the password, the message digest of the entered password is computed and compared with the digest stored in the database. If it matches, then login is successful, otherwise user is not authenticated.
Digital Time Stamping
Majority of text, audio and video documents are available in digital format and a number of simple techniques and tools are available to change digital documents. So some sort of mechanism is required to certify when such a document was created or last modified. Digital timestamp solve the purpose and provide a temporal authentication. Digital time stamp helps in protecting intellectual property rights, ensuring strong auditing procedures and implementing true non-repudiation services.
Hash functions as PRNG
Hash functions as one way functions can be used to implement PRNG (Pseudo random number generator). A very simple technique can be to start from an initial value (s) known as seed and computer H(s) and then H(s+1), H(s+2) and so on.
Session Key Derivations
Hash functions as one way functions can be used to generate sequence of session keys that are used for the protection of successive communication sessions. Starting from a master key K0, the first session key can be K1 = H(K0) and second session key can be K2 = H(K1) and so on.
The key management scheme based on control vectors which makes use of hash functions and Encryption functions for generating session keys.
Constructions of Block Ciphers Block ciphers can be used to construct a cryptographic hash function however the inverse is also true and there has been block ciphers designed using Hash functions. In Handschuh and Naccache proposed to use the compression function of cryptographic hash function SHA-1 in encryption mode. The name of the cipher was SHACAL. SHACAL-1 (originally named SHACAL) and SHACAL-2 are block ciphers based on SHA-1 and SHA-256 respectively. SHACAL-1 (originally named SHACAL) is 160-bit clock cipher and SHACAL-2 is 256 bit block cipher. Both were selected for the second phase of NESSIE project. In 2003 SHACAL-1 was not recommended for NESSIE portfolio because of concerns about its key schedule, while SHACAL-2 was finally selected as one of the 17 NESSIE finalists. SHACAL-1 used the compression function of SHA-1 and turned it into a block cipher by using the state input as the data block and using the data input as the key input. In other words SHACAL-1contemplated the SHA-1 compression function as an 80-round, 160-bit block cipher with a 512-bit key. Keys shorter than 512 bits are supported by padding them with zero up to 512. SHACAL-1 was not intended to be used with keys shorter than 128-bit.
Other Applications
Hash Functions can also be used to index data in hash tables, for fingerprinting, to detect duplicate data or uniquely identify files, and as checksums to detect accidental data corruption and for generating random numbers also. Looking at this wide range of applications, it is not correct to say that Hash Functions belong to one particular cryptographic sub branch. These cryptographic tools deserve a separate status for themselves. They are used in almost all places in cryptology where efficient information processing is required.
For more updates and information, don’t forgot to get in touch with us, Let us know your views about the content published in our platform, just check out the comment section below. Also, you may click here for more info on our categorized Education Domain.
