L2 - Cryptographic Basics Flashcards
When is a function a hash function?
- Compression: h maps an input x of arbitrary finite bit length to an output h(x) of fixed bit length n
h: {0,1}* β> {0,1}^n - Ease of computation: given h and x it is easy to compute h(x)
Cryptographic hash functions properities?
Preimage Resistance + Second Preimage Resistance
Collision Resistance
What is preimage resistance?
It is a property of cryptographic hash functions.
- it is infeasible to find the input to outputs (one-way function; h^-1 does not exist)
What is second preimage resistance?
- it is computationally infeasible to find a xβ which computes the same hash output
The attacker is handed a fixed π1 to which he has to find a different π2 with equal hash. In particular, he canβt choose π1.
Given x it is computationally infeasible to find any second input xβ
with x != xβ such that h(x) = h(xβ).
What is collision resistance?
In the second case (collision resistance), the attacker can freely choose both messages π1 and π2, with the only requirement that they are different (and hash to the same value).
A hash function h is said to be collision resistant if it is infeasible to find two values, x and y, such
that x != y, yet h(x) = h(y).
Difference between second preimage resistance and collision resistance
The difference is in the choice of π1.
(From this, it is also obvious that collision resistance implies second preimage resistance: An attacker can just choose an arbitrary π1 and compute a second preimage π2 to obtain a collision.)
Application of the second pre-image resistance property
Message digest
What is message digest?
A message digest is a cryptographic hash function containing a string of digits created by a one-way hashing formula.
Message digests are designed to protect the integrity of a piece of data or media to detect changes and alterations to any part of a message. They are a type of cryptography utilizing hash values that can warn the copyright owner of any modifications applied to their work.
What is an additional desired property in hash functions?
Hiding
What is hiding in hash functions?
A hash function h is said to be hiding if a secret value r is chosen at randomly, then given h(r||x), it is infeasible to find x.
What is a nonce?
Random number used only once. Used to prevent brute force attacks.
In what application can hiding be used?
A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding.
Example:
Someone commits a hash of a message with a nonce. Then later he reveals the nonce and the message. Now everyone can verify that r and x indeed compute to the hash. But beforehand nobody could find x by brute force (try different x values to get the hash).
What does the search puzzle consist of?
- a hash function h (there are many different ones; I think each puzzle has its own one; it computes the puzzle results)
- a value id (is the puzzle-ID; makes solutions to the puzzle unique)
- target set Y (for a valid solution, the puzzle result must lie within the target set Y)
- Computation (The puzzle-ID is concatenated with a value x and hashed. x changes until the puzzle result lies within Y)
What are broken and what are safe hash algorithms?
- MD4, MD5, SHA-1 are broken
- SHA-2/SHA-3 are safe and SHA-3 is preferred
Hash pointer
- allows to verify that the information has not changed. Does not contain the information to the location of the data.
We should note that the hash stored in the hash pointer is the hash of the whole data of the previous block, which also includes the hash pointer to the block before that one. This makes itβs impossible to tamper a block in the blockchain without letting others know.
Tamper Evident Property of Blockchain
We only need to keep the hash pointer to the last block of the blockchain. Then when somebody shows the whole blockchain later and claim the data in it is not modified, we can tell if any block in the chain is tampered by traversing the blocks backwards and verifying the hashes one by one.
Hash tree / Merkle tree
Merkle tree is a binary tree building with hash pointers. The leaves are data blocks, nodes further up in the tree are the hashes of their respective children.
is a tree in which every βleafβ (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labelled with the cryptographic hash of the labels of its child nodes.
Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes in the tree. Conversely, in a hash list, the number is proportional to the number of leaf nodes itself. A Merkle tree is therefore an efficient example of a cryptographic commitment scheme, in which the root of the tree is seen as a commitment and leaf nodes may be revealed and proven to be part of the original commitment.
The main difference from a hash list is that one branch of the hash tree can be downloaded at a time and the integrity of each branch can be checked immediately, even though the whole tree is not available yet.
Properties of a Merkle tree
Traversal efficiency
To verify a data block, we only need to traverse the path from the top to the leaf where the data is. So the complexity is O(log n), which is much more efficient compared with O(n) of a linked list blockchain.
None-membership proof
If Merkel tree is sorted, we can prove a given data is not in the tree: if the data before and after the given data are both in the tree and theyβre consecutive, so thereβs no space between them, this proves that the given data is not in tree.
Proof of Membership
- proof that a certain block is contained in a Merkle Tree
- verification in log(n) time
Weakness if only using the root of a Merkle tree for verification
The Merkle hash root does not indicate the tree depth, enabling a second-preimage attack in which an attacker creates a document other than the original that has the same Merkle hash root. For the example above, an attacker can create a new document containing two data blocks, where the first is hash 0-0 + hash 0β1, and the second is hash 1-0 + hash 1-1.
When is a system symmetric in cryptography?
If
- encryption and decryption are done using the same secret key
- the encryption and decryption functions are similar
-> key must be exchanged btw. organizations so that it can be used for decryption.
What is asymmetric cryptography?
- pairs of related keys are used (one public and private key).
- to generate these key pairs, one-way functions are utilized.
- receiver publishes a public encryption key that is known to everyone and also has a matching private key for decryption.
- One needs the private key for decryption as the public key can only be used for encryption.
- -> Often used to authenticate data using digital signatures
Two major digital signature schemes (asymmetric)
RSA: factorization of large prime number sis hard but easy with additional information (trapdoor one-way-functions)
ECC: e.g. ECDSA: Based on discrete logarithms (shorter than RSA).
How do we solve the problem that digital signatures can only sign a small amount of data?
Signing the hash of the message is sufficient, as the has function is collision resistant.
Two properties of digital signatures
- only an entity is able to create a signature of its own, but everyone can verify it
- the signature is tied to data that gets signed. A signature cannot be used for different data
(private key for signing and a public key for verification)
