Cryptographic Hash Functions

Course Outline

• Teams code is xmwxbzp
• References can be found on the Teams post
• Grading breakdown:
  • Midterm: 15%
  • Quizzes: 10%
  • Assignments: 20%
  • Attendance: 5%
  • Final: 50%

Introduction

• In fiat currencies, central banks control the money supply and add anti-counterfeiting measures
• Cryptocurrencies must enforce security rules technologically without relying on a central authority
• Cryptography allows for securely encoding cryptocurrency rules within the system

Cryptographic Hash Functions

• A hash function is a mathematical function with specific properties:
  • Input can be any size string
  • Produces a fixed-size output (e.g., 256-bit)
  • Efficiently computable
• Cryptographically secure hash function properties:
  • Collision-resistance
  • Hiding
  • Puzzle-friendliness

Collision Resistance

• Collision: When two distinct inputs produce the same output
• Collision-resistance means it is infeasible to find two different inputs, x and y, where x ≠ y, but H(x) = H(y)
• The input space (infinite) is larger than the output space (finite), requiring some input strings to map to the same output string
• There are methods that guarantee collisions can be found
• For a 256-bit output size, picking 2^256 + 1 distinct values ensures two outputs are equal when hashed.
• Choosing 2^130 + 1 inputs results in a 99.8% chance of collision
• Birthday Paradox: Collision likelihood examined roughly the square root of possible outputs; with 10,000 hashes per second, finding a collision to 2^128 hashes would take over 10^27 years
• Some functions have efficient collision detection methods, like H(x) = x mod 2^256 with a collision occurring between 3 and 3 + 2^256
• There are no collision-resistant functions
• Cryptographic hash functions are relied on in practice

Property 2: Hiding

• Hiding: With the hash function output y = H(x), finding the input, x, is infeasible
• x has to be chosen from a set that’s very spread out
• Inputs that are not spread can be hidden by concatenating it with another input that is spread out.
• With secret value r from high min-entropy distribution, then finding x given H(r || x) is infeasible
• Min-entropy in information theory describes outcome predictability

Application: Commitment

• A commitment scheme utilizes two algorithms:
• com := commit(msg, nonce)
• verify(com, msg, nonce) returns TRUE if com == commit(msg, nonce)
• Security properties
• Hiding: Given com, finding msg is infeasible
• Binding: Finding two pairs (msg, nonce) and (msg', nonce') where msg ≠ msg' and commit(msg, nonce) == commit(msg', nonce') is infeasible.
• Defining commit(msg, nonce) := H(nonce||msg), necessary security properties depend on H being collision-resistant and hiding

Property 3: Puzzle Friendliness

• For every n-bit output value y, if k is chosen from a distribution with high min-entropy, then finding x such that H(k||x) = y is infeasible in time less than 2^n.
• Application: search puzzle
• A hash function: H
• A puzzle-ID: id chosen from a high min-entropy distribution
• A target set Y
• A solution to puzzle x, such that H(id || x) ∈ Y
• Size of Y determines puzzle difficulty.
• If set of all n-bit strings, trivial, where if Y only 1 element, the puzzle is maximally hard

SHA-256

• Builds a hash compression function that works on fixed-length inputs
• Takes inputs of length 'm' and produces an output of a smaller length 'n'.
• Converts into a hash function for arbitrary-length inputs using Merkle-Damgard transform, dividing input into blocks of length m-n
• Initialization Vector (IV) is used for the first block
• SHA-256 compression function takes 768-bit inputs and produces 256-bit outputs and the block size is 512 bits.

Hash Pointers

• A hash pointer contains the "pointer" to stored information and a cryptographic hash of that information
• A regular pointer retrieves information
• A hash pointer verifies no change has occurred.
• Pointers, like linked lists or binary search trees, can be implemented with hash pointers

Blockchain

• Blockchain is a linked list build using hash pointers where each block indicates the previous block's value and contains a digest of that value
• The head of the list is a regular hash-pointer pointing to the recent data block
• Use case for a blockchain is a tamper-evident log
• Altering log data that is earlier in the log, will be detected

Blockchain: tamper-evident log

• Tampering with data anywhere in the blockchain requires tampering across the hash pointers back to the beginning
• Storing the hash pointer at the "head of the list" prevents undetected changes; The "genesis block" is the initial block

Merkle Trees

• A binary tree with hash pointers
• Data blocks comprise the leaves of a Merkle Tree.
• Data blocks are grouped in pairs so that a new data structure contains 2 hash pointers, one to each of the data block pairs.
• These data structures are each level up on the tree
• This process repeats until reaching the root, a single block
• Tampering gets detected by remembering the top hash pointer

Proof of Membership

• Only the root is remembered
• A block a member of the Merkle Tree
• Verify the specific block and the blocks on the path from data block to the root.
• Where there are 'n' nodes in a tree, checking can occur with log(n) items and requires log(n) time

Proof of Non-Membership

• Sorted Merkle Tree is a Merkle Tree sorted by some ordering function.
• Allows verification of non-membership in a logarithmic time and space.
• The path to the item just before and just after an item is revealed because the requested item is not included.
• When two items are consecutive, then the item in question is not included.

Digital Signatures

• Only one entity can create their signature and anyone can verify validity.
• Signatures are tied to a particular document
• Serves to indicate that the signature cannot endorse a different document

Digital Signature Algorithm

• ( sk, pk ) := generateKeys(keysize ) sk is the secret key, used privately for signing messages and pk is what you give out to people.
• sig := sign(sk, message)
• isValid := verify(pk, message, sig) isValid will return TRUE if sig is a valid signature for message, under public key pk.
• Properties
• verify(pk, message, sign(sk, message)) == TRUE
• Signatures are existentially unforgeable

Practical Concerns

• Algorithms require source randomness
• Signing should occur as the hash of the message
• The hash of the message is a message digest (the hash function is collision resistant)
• Signing a hash pointer protects the total structure.

Elliptic Curve Digital Signature Algorithm (ECDSA)

• ECDSA is used on the standard elliptic curve "secp256k1"
• ECDSA is estimated at 128 bits of security.
• ECDSA difficulty is equivalent to 2128 symmetric-key function calls.
• ECDSA technically signs 256-bit messages, but always hashes before allowing an efficient signature for any size message.

Public Keys as Identities

• public Key is then a means of verifying that you can think of pk.
• Access implies knowledge of the corresponding secret key (sk).
• New identities can be made by creating a new key pair sk and pk.
• Hashing can occur if public keys are large

Decentralized Identity Management

• Generate identities without centralization
• Generate multiple with ease
• Bitcoin's version is addresses
• Probability of a repeated key is low
• Randomness has weakness
• There is no need to show your real-world entity, as behavior might be identifying.

Simple Cryptocurrency: Goofy Coin

• Simplified cryptocurrency
• The designated entity, Goofy makes coins
• Coin owner transfers a coin to someone else

Create a Coin

• Goofy ID generates unique coin ID uniqueCoinID so the string "CreateCoin [uniqueCoinID]" is constructed and the digital signature occurs for that string

Transferring a Coin

• Goofy transfers to Alice
• Generates “Pay this to Alice” to reference a coin
• Signs a statement
• Follow the pointer chain back; rightful owner statement saying "pay this coin to [new owner]"

Problems with GoofyCoin: Double Spending

• Bob transfers the coin using a signed declaration, but keeps it a secret.
• A signed declaration can then occurs with Bob to a 3rd party, Chuck.
• Bob / Chuck appear as owners.

Scrooge Coin

• Publishes a ledger
• Any written data remains
• Transactions must be written to the ledger, to prevent Double spending

Blockchain (Scrooge Coin)

• Scrooge signs each blockchain digitally
• Hash pointers and contents
• The signature is published

Rules of Scrooge Coin transaction

• Valid coins that were made previously.
• Has to be a non-Double Spending transaction
• The consumed total should equal the total of what comes out
• Signing is required
• Coins are immutable

Centralization Problems

• Can make as many coins
• Does not endorse a transaction
• Can refuse to write unless has gets money
• Can stop at any point

Descroogifying the system

• How all users can agree to a chain.
• Have the ability to assign Ids
• Control and design coin miniting