Cryptography

Introduction
• Cryptography is the science of making information secure in
the presence of adversaries. It does so under the assumption
that limitless resources are available to adversaries.
• Ciphers are algorithms used to encrypt or decrypt data, so that
if intercepted by an adversary, the data is meaningless to them
without decryption, which requires a secret key.
• Cryptography is primarily used to provide a confidentiality
service. On its own, it cannot be considered a complete
solution, rather it serves as a crucial building block within a
more extensive security system to address a security problem.
• For example, securing a blockchain ecosystem requires many
different cryptographic primitives, such as hash functions,
symmetric key cryptography, digital signatures, and public key
cryptography.
• In addition to a confidentiality service,
cryptography also provides other security
services such as integrity, authentication
(entity authentication and data origin
authentication), and non-repudiation.
• Additionally, accountability is also provided,
which is a requirement in many security
systems
 Message authentication mode
• In message authentication mode, a Message Authentication Code
(MAC) results from an encryption function.
• The MAC is a cryptographic checksum that provides an integrity
service.
• The most common method to generate a MAC using block ciphers is
CBC-MAC, where a part of the last block of the chain is used as a
MAC.
• For example, a MAC can be used to ensure that if a message is
modified by an unauthorized entity. This can be achieved by
encrypting the message with a key using the MAC function.
• The resultant message and MAC of the message once received by
the receiver can be checked by encrypting the message received
again by the key and comparing it with the MAC received from the
sender.
• If they both match, then the message has not modified by
unauthorized user thus integrity service is provided.
• If they both don't match, then it means that message is modified by
unauthorized entity during the transmission.
 Cryptographic hash mode
• Hash functions are primarily used to compress
a message to a fixed-length digest.
• In cryptographic hash mode, block ciphers are
used as a compression function to produce a
hash of plaintext.
 Hash functions
• Hash functions are used to create fixed-length digests of
arbitrarily-long input strings.
• Hash functions are keyless, and they provide the data
integrity service.
• They are usually built using iterated and dedicated hash
function construction techniques
• Various families of hash functions are available, such as
MD, SHA-1, SHA-2, SHA-3, RIPEMD, and Whirlpool.
• Hash functions are commonly used for digital signatures
and Message Authentication Codes (MACs), such as
HMACs.
• They have three security properties, namely preimage
resistance, second preimage resistance, and collision
resistance.
Some applications use hash functions as a means
for generating Pseudo-random Numbers
Generator (PRNGs).
 Preimage resistance
• This property can be explained by using the
simple equation shown as follows:
h(x) = y
• Here, h is the hash function, x is the input, and y
is the hash.
• The first security property requires that y cannot
be reverse-computed to x. x is considered a
preimage of y, hence the name preimage
resistance. This is also called a one-way property.
 Second preimage resistance
• The second preimage resistance property
requires that given x and h(x), it is almost
impossible to find any other message m, where
m != x and hash of m = hash of x or h(m) =
h(x).
• This property is also known as weak collision
resistance.
 Collision resistance
• The collision resistance property requires that
two different input messages should not hash
to the same output. In other words, h(x) !=
h(z). This property is also known as strong
collision resistance.
 Categories of Hash function
• Message Digest
• Secure Hash Algorithms
• Message Authentication Codes
• MACs using block ciphers
• Hash-based MACs
 Message Digest
• Message Digest (MD) functions were
prevalent in the early 1990s. MD4 and MD5
fall into this category.
• Both MD functions were found to be insecure
and are not recommended for use anymore.
• MD5 is a 128-bit hash function that was
commonly used for file integrity checks.
 Secure Hash Algorithms
• SHA-0: This is a 160-bit function introduced by NIST
in 1993.
• SHA-1: SHA-1 was introduced in 1995 by NIST as a
replacement for SHA-0.
– This is also a 160-bit hash function. SHA-1 is used
commonly in SSL and TLS implementations.
– It should be noted that SHA-1 is now considered insecure,
and it is being deprecated by certificate authorities. Its
usage is discouraged in any new implementations.
• SHA-2: This category includes four functions defined
by the number of bits of the hash: SHA-224, SHA 256,
SHA-384, and SHA-512.
• SHA-3: This is the latest family of SHA functions.
 Secure Hash Algorithms
• SHA-3-224, SHA-3-256, SHA-3-384, and SHA-3-512 are
members of this family.
– SHA-3 is a NIST-standardized version of Keccak. Keccak
uses a new approach called sponge construction instead of
the commonly used Merkle-Damgard transformation.
• RIPEMD: RIPEMD is the acronym for RACE Integrity
Primitives Evaluation Message Digest. It is based on the
design ideas used to build MD4. There are multiple versions of
RIPEMD, including 128-bit, 160-bit, 256-bit, and 320-bit.
• Whirlpool: This is based on a modified version of the Rijndael
cipher known as W.
– It uses the Miyaguchi Preneel compression function, which is a type of
one-way function used for the compression of two fixed length inputs
into a single fixed-length output.
– It is a single block length compression function.
 Design of Secure Hash Algorithms
• SHA-256 has the input message size < 264-
bits.
• Block size is 512-bits, and it has a word size of
32-bits.
• The output is a 256-bit digest
 The algorithm works as follows, in
eight steps:
• 1. Preprocessing:
– 1. Padding of the message is used to adjust the length of a
block to 512-bits if it is smaller than the required block size
of 512-bits.
– 2. Parsing the message into message blocks, which ensures
that the message and its padding is divided into equal
blocks of 512-bits.
– 3. Setting up the initial hash value, which consists of the
eight 32-bit words obtained by taking the first 32-bits of the
fractional parts of the square roots of the first eight prime
numbers.
– These initial values are randomly chosen to initialize the
process, and they provide a level of confidence that no
backdoor exists in the algorithm.
 2. Hash computation:
• 4. Each message block is then processed in a
sequence, and it requires 64 rounds to compute
the full hash output. Each round uses slightly
different constants to ensure that no two rounds
are the same.
• 5. The message schedule is prepared.
• 6. Eight working variables are initialized.
• 7. The intermediate hash value is calculated.
• 8. Finally, the message is processed, and the
output hash is produced:
 Design of SHA-3 (Keccak)
• The key idea behind SHA-3 is based on unkeyed permutations, as
opposed to other typical hash function constructions that used keyed
permutations. Keccak also does not make use of the Merkle-
Damgard transformation that is commonly used to handle arbitrary-
length input messages in hash functions.
• A newer approach called sponge and squeeze construction is used in
Keccak.
• It is a random permutation model.
• Different variants of SHA-3 have been standardized, such as SHA-
3-224, SHA-3-256, SHA-3-384, SHA-3-512, SHAKE-128, and
SHAKE-256. SHAKE-128 and SHAKE-256 are Extendable Output
Functions (XOFs), which are also standardized by NIST.
• XOFs allow the output to be extended to any desired length.
• The diagram shows the sponge and squeeze
model, which is the basis of SHA-3 or Keccak.
Analogous to a sponge, the data is first absorbed
into the sponge after applying padding.
• There it is then changed into a subset of
permutation state using XOR, and then the output
is squeezed out of the sponge function that
represents the transformed state.
• The rate is the input block size of a sponge
function, while capacity determines the general
security level
 Message Authentication Codes
• MACs are sometimes called keyed hash functions,
and they can be used to provide message
integrity and authentication.
• More specifically, they are used to provide data
origin authentication.
• These are symmetric cryptographic primitives
that use a shared key between the sender and
the receiver.
• MACs can be constructed using block ciphers or
hash functions
 MACs using block ciphers
• Block ciphers are used in the Cipher Block
Chaining (CBC) mode in order to generate a
MAC.
• Any block cipher, for example AES in the CBC
mode, can be used.
• The MAC of the message is, in fact, the output of
the last round of the CBC operation.
• The length of the MAC output is the same as the
block length of the block cipher used to generate
the MAC
• MACs are verified simply by computing the
MAC of the message and comparing it to the
received MAC.
• If they are the same, then the message integrity is
confirmed; otherwise, the message is considered
altered.
• It should also be noted that MACs work like
digital signatures, however they cannot provide
non-repudiation service due to their symmetric
nature.
 Hash-based MACs
• Hash-based MACs (HMACs) produce a fixed-length output
and take an arbitrarily long message as the input.
• In this scheme, the sender signs a message using the MAC
and the receiver verifies it using the shared key.
• The key is hashed with the message using either of the two
methods known as secret prefix or the secret suffix.
• With the secret prefix method, the key is concatenated with
the message; that is, the key comes first and the message
comes afterwards, whereas with the secret suffix method,
the key comes after the message, as shown in the following
equations:
• Secret prefix:M = MACk(x) = h(k||x)
• Secret suffix: M=MACk(x) = h(x||k)
• There are HMAC constructions schemes that
use various techniques, such as ipad and opad
(inner padding and outer padding) that have
been proposed by cryptographic researchers.
 Applications of Hash Functions
• Merkle trees,
• Patricia trees, and
• Distributed Hash Table (DHT)
 Merkle trees
• The concept of Merkle tree was introduced by
Ralph Merkle. Merkle trees enable secure and
efficient verification of large datasets.
• A Merkle tree is a binary tree in which the inputs
are first placed at the leaves (node with no
children), and then the values of pairs of child
nodes are hashed together to produce a value for
the parent node (internal node) until a single hash
value known as Merkle root is achieved.
• A diagram of Merkle tree is shown here.
 Patricia trees
• To understand Patricia trees, you will first be
introduced to the concept of a trie. A trie, or a digital
tree, is an ordered tree data structure used to store a
dataset.
• Practical Algorithm to Retrieve Information Coded in
Alphanumeric (Patricia), also known as Radix tree, is a
compact representation of a trie in which a node that is
the only child of a parent is merged with its parent.
• A Merkle-Patricia tree, based on the definitions of
Patricia and Merkle, is a tree that has a root node
which contains the hash value of the entire data
structure.
 Distributed Hash Tables
• A hash table is a data structure that is used to
map keys to values.
• Internally, a hash function is used to calculate
an index into an array of buckets from which
the required value can be found.
• Buckets have records stored in them using a
hash key and are organized into a particular
order.
• The following diagram shows how a DHT works.
Data is passed through a hash function, which
then generates a compact key.
• This key is then linked with the data (values) on
the peer-to-peer network.
• When users on the network request the data (via
the filename), the filename can be hashed again to
produce the same key, and any node on the
network can then be requested to find the
corresponding data.
• DHT provides decentralization, fault tolerance,
and scalability