L2 - Cryptographic Basics

Question 1

When is a function a hash function?

Answer 1

1. 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
2. Ease of computation: given h and x it is easy to compute h(x)

Question 2

Cryptographic hash functions properities?

Answer 2

Preimage Resistance + Second Preimage Resistance

Collision Resistance

Question 3

What is preimage resistance?

Answer 3

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)

Question 4

What is second preimage resistance?

Answer 4

• 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’).

Question 5

What is collision resistance?

Answer 5

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).

Question 6

Difference between second preimage resistance and collision resistance

Answer 6

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.)

Question 7

Application of the second pre-image resistance property

Answer 7

Message digest

Question 8

What is message digest?

Answer 8

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.

Question 9

What is an additional desired property in hash functions?

Answer 9

Hiding

Question 10

What is hiding in hash functions?

Answer 10

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.

Question 11

What is a nonce?

Answer 11

Random number used only once. Used to prevent brute force attacks.

Question 12

In what application can hiding be used?

Answer 12

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).

Question 13

What does the search puzzle consist of?

Answer 13

• 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)

Question 14

What are broken and what are safe hash algorithms?

Answer 14

• MD4, MD5, SHA-1 are broken

- SHA-2/SHA-3 are safe and SHA-3 is preferred

Question 15

Hash pointer

Answer 15

• 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.

Question 16

Tamper Evident Property of Blockchain

Answer 16

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.

Question 17

Hash tree / Merkle tree

Answer 17

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.

Question 18

Properties of a Merkle tree

Answer 18

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

Question 19

Weakness if only using the root of a Merkle tree for verification

Answer 19

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.

Question 20

When is a system symmetric in cryptography?

Answer 20

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.

Question 21

What is asymmetric cryptography?

Answer 21

• 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

Question 22

Two major digital signature schemes (asymmetric)

Answer 22

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).

Question 23

How do we solve the problem that digital signatures can only sign a small amount of data?

Answer 23

Signing the hash of the message is sufficient, as the has function is collision resistant.

Question 24

Two properties of digital signatures

Answer 24

• 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)

Question 25

Explain how the digital signature works

Answer 25

You first generate keys so a secret key and a public key. The secret key is used to sign the message. The public key is given to everyone to verify the signature.

The sign method takes the secret key and the message and generates a signature for that specific message.

Then the receiver can verify the signature by putting the public key, the message and the signature into a verify function.

Question 26

What does it mean that a digital signature is unforgeable?

Answer 26

• The attacker knows your public key
• the attacker sees your signature on an arbitrary amount of messages
• -> He can still not create signatures on a message that he has not seen. This is because he does not know the secret key which was used to create the signature.

Question 27

How to create an identity with digital signatures?

Answer 27

• The public key can act as an identity
• the private key is the password
• -> new identities can be generated at will with generateKeys from our digital signature scheme

Question 28

How to protect your identity?

Answer 28

You want to hash your public key because public keys are very large and they are vulnerable to quantum computing attacks.

Question 29

Problems with identity creation

Answer 29

The private keys are not recoverable. Once the file is lost, there is no way to act under this entity.
An appropriate key length should be considered. If it is too short it could be computed in the future.

Question 30

Who is safe against quantum attacks?

Answer 30

• Hash function SHA3 is relatively secure against quantum computers.
• users can securely receive coins as long as their public key is unknown (I assume that quantum computers may otherwise be able to use the generateKeys function and input the public key to get the private key).
• if an address only receives coins and never signs a transaction, then it won’t expose its public key.
• do not reuse addresses.