Lecture 3 Cryptography
Recall …
Cryptographic hash function Merkle tree Digital signature
A blockchain is a linked list with hash pointers.
Copyright By PowCoder代写 加微信 powcoder
prev: H( )
prev: H( )
prev: H( )
Cryptographic hash function
• A hash function is a function that o takesanystringasinput,
o has fixed-size output (we’ll use 256 bits), and
o is efficiently computable.
• A cryptographic hash function has additional security
properties:
o collision-resistant
o puzzle-friendly
• Computationally no one can find x and y such that x != y and H(x)=H(y)
• There are many many collisions. Can we find one?
roperty 1:
infinite input space
finite output space
How to find a collision?
• For every hash with 256-bit fixed-length output, if we try 2130 random inputs, with probability 99.8% at least two of them will collide.
• This takes too long to matter.
• Is there a faster way? For some hash functions, yes; for
others, we don’t know of one.
• No hash function has been proven to be collision-resistant; yet people have designed hash functions that are believed to be practically collision-resistant.
Application: Hash as digest
• If we know H(x) = H(y), it’s safe to assume that x = y. (Why?)
• Useful because the hash is small.
• Example: Dropbox uses content hash. In lieu of comparing bit-by-bit two big files residing at different sites, Dropbox compares their hashes.
Hash property 2: Hiding
• Want something like this: Given H(x), it is infeasible to find x.
• Can’t be true for all x, so we resort to a probabilistic property.
• Let r|x denote the concatenation of r an x.
• Hiding property: If r is uniformly randomly chosen from a
large set, then given H(r|x), it is infeasible to find x.
• More generally, r can be drawn according to a distribution with high min-entropy, which means that the distribution is “very spread out”, so that no particular value is chosen with more than negligible probability.
Application: Commitment
• Want to “seal a value in an envelope” and “open the envelope” later.
• To seal msg in envelope: (com, key) := commit(msg) — then publish com;
• To open envelope: publish key, msg, so that anyone can use verify(com, key, msg) to validate.
• Security properties:
Hiding: Given com, infeasible to find msg. Binding: Infeasible to find msg != msg’ such that
verify(commit(msg), msg’) == true
Hash property 3:
Puzzle-friendly:
For every possible output value y,
if k is chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k|x) = y.
Application:
Given a “puzzle ID” id (from high min-entropy distribution), and a target set Y:
Try to find a “solution” x such that H(id|x) ∈ Y.
Puzzle-friendly property implies that no solving strategy is much better than trying random values of x.
earch puzzle
Checksum is no crypto hash
• Internet checksum has some properties of hash function: oproduces fixed length digest of message
ois many-to-one
• However, it’s too easy to find a collision.
I O U 9 0 0 . 1 9 B O B
different messages but identical checksums!
• A member of SHA-2 (Secure Hash Algorithm 2);
ASCII format
49 4F 55 39 30 30 2E 31 39 42 D2 42
B2 C1 D2 AC
I O U 1 0 0 . 9 9 B O B
ASCII format
49 4F 55 31 30 30 2E 39 39 42 D2 42
B2 C1 D2 AC
• U.S. National Security Agency (NSA) designed SHA-2;
• Adopted by (anonymous) to compute hash pointers (conspiracy theory?);
• Recall the mining puzzle is to find nonce such that H(nonce|previous hash|transactions) < difficulty target;
• Basically the most frequent function computed by Bitcoin miners;
• State-of-the-art ASIC computes at above 10 tera hashes/s, using less than 75 joules per tera hashes (1 joule supplies a 1W light bulb for 1 second).
A brief sketch of SHA
Input: 512 bits or 16 words (Mt). Output: 8 words A-H.
Merkle-Damgard transform.
c maps 512+256 bits to 256 bits. If c is collision-resistant, then SHA-256 is collision-resistant.
Padding (10* | length)
256 hash function
Message (block 1)
Message (block 2)
Message (block n)
Block difficulty
• The hash of any valid block must be below a mining target.
• The mining target/threshold (in hexadecimal):
0000000000000000172EC0000000000000000000000000000000000000000000 (March 2015) 0000000000000000000ed0eb0000000000000000000000000000000000000000 (Sept. 2021)
• On 1/1/2023, only one in about 1023 nonces that you try will be successful.
• Difficulty of a block:
Block_difficulty = 1/mining_target
Why variable difficulty?
Total hash rate increases rapidly with price and technological advances. About 10 orders of magnitude increase in 10 years.
Bitcoin difficulty rule
(a) The mining difficulty changes every 2016 blocks
next_difficulty = (previous_difficulty * 2016 * 10 minutes) / (time to mine last 2016 blocks)
(b) Adopt the heaviest chain instead of the longest chain
chain_difficulty = sum of block_difficulty
(c) Allow the difficulty to be adjusted only mildly every epoch
1⁄4 < next_difficulty/previous_difficulty < 4
Only rule (a) is insufficient
• One can only judge whether a chain is valid based on the chain itself.
• Recall the blockchain growth rate is about 1 block every 10 minutes, regardless of the technology!
• Recall the miner writes the timestamp, so it costs nothing to fake.
• You can mine in private a longest blockchain using a single laptop,
which can be a valid chain by itself.
• Between two chains, however, the one that is more difficult to
produce is more convincing as the result of the majority mining power in the network. Hence we favor the ”heavier” chain – this is rule (b).
• Note: Under the assumption the difficulty target remains constant
forever, the longest chain is also the heaviest chain, so the protocol reduces to “longest chain wins”.
Rule (b) is also insufficient
• If an attacker is lucky to mine a single highly difficult block, which is heavier than k blocks of lower difficulty, it can cause a safety violation under the k-confirmation rule.
• Hence one cannot let the minor choose the difficulty arbitrarily in each block, leading to rule (c).
Alternate rule ((a) + (b))
The adversary creates an epoch filled with timestamps extremely close-together, so that the difficulty adjustment rule from (a) will set the difficulty extremely high for the next epoch.
A difficulty-rising attack:
Bitcoin Rule ((a) + (b) + (c))
is a binary tree with hash pointers; summarize by its root hash. Can verify membership in O(log n) time and space.
H() H() H() H()
(data) (data) (data) (data)
H() H() H() H()
(data) (data) (data) (data)
Simplified payment verification (SPV) nodes use Merkle paths to verify transactions without downloading full blocks.
What we want from signatures
• Only you can sign, but anyone can verify;
• Signature is tied to a particular document, can’t be cut-and-
pasted to another one.
API for digital signatures
• (sk, pk) := generateKeys(keysize) sk: secret signing key
pk: public verification key
• sig := sign(sk, message)
• isValid := verify(pk, message, sig)
can be randomized algorithms
Requirements for signatures
“valid signatures verify”
verify(pk, message, sign(sk, message)) == true “can’t forge signatures”
adversary who: knows pk
gets to see signatures on messages of his choice can’t produce a verifiable signature on another message
challenger
sign(sk, m0)
sign(sk, m1)
... M, sig
verify(pk, M, sig)
if true, attacker wins
M not in { m0, m1, ... }
Practical stuff...
• The algorithms are randomized, so we need good source of randomness;
• Mistake in generateKeys() or sign() could leak the private key.
• There are limits on message size, so we use Hash(message)
rather than message.
• Fun trick: If one signs a hash pointer, the signature “covers”
the whole structure. (Why?)
• Bitcoin uses Elliptic Curve Digital Signature Algorithm (ECDSA).
Public key as identity
If you see sig such that verify(pk, msg, sig)==true, think of it as
pk says, “[msg]”.
To “speak for” pk, you must know matching secret key sk.
Making a new identity
• Create a new, random key-pair (sk, pk) pk is the public “name” you can use
[usually better to use Hash(pk)] sk lets you “speak for” the identity
• You control the identity, because only you know sk;
• If pk “looks random”, nobody needs to know who you are.
Decentralized ID management
• Anybody can make a new identity by themselves at any time;
• Make as many as they want!
• No central point of coordination;
• These identities become “addresses” in Bitcoin.
Addresses not directly connected to real-world identity.
But observer can link together an address’s activity over time and make inferences.
Signatures in Practice
Elliptic Curve Digital Signature Algorithm (ECDSA) Standard part of crypto libraries
Public key: Secret key:
512 bits 256 bits 256 bits
Note: can sign hash of message
Signature: 512 bits
Cryptocurrency: Coin Management
Cryptocurrency: data = transactions involving coins
Createcoins
Creation signed by a user (identified via public key) each coin has a recipient (identified via public key)
Transaction signed by a user consumed coins (list)
coins created (list)
Total wealth consumed = total wealth created
Cryptocurrency: Coin Management
Cryptocurrency: data = transactions involving coins Coin: (coinID, signature of Creator)
Creator creates coins
Transaction: Transfer of coin ownership This: hash pointer to coin
Alice: public key of this to by owner of coin
Decentralized blockchain
Block: Header + Data + Signature Header: Pointer to previous block
= hash of the previous block header and Merkle root of data of previous block
Data: information specific to the block
Signature: one of the users signs the block (header+data)
Public key cryptography and addresses
Cryptography
• Alice and Bob wish to communicate “securely” and/or “privately”. • Trudy (intruder) may intercept, delete, add messages.
secure sender
secure receiver
What can an intruder do?
• eavesdrop: intercept messages
• actively insert messages
• impersonate
• hijacking: “take over” ongoing communication by removing
sender or receiver, inserting oneself in place
• denial of service: prevent service from being used by others (e.g., by overloading resources)
The language of cryptography
Alice’s KA encryption
Bob’s KBdecryption
ciphertext
encryption algorithm
decryption algorithm
• m: plaintext message
• KA(m): ciphertext, encrypted with key KA
• decryption: m = KB(KA(m))
• Usually the algorithms are no secret. The keys are secret.
Breaking an encryption scheme
• Three different levels of attacks
o cipher-text only attack: Trudy has ciphertext she can
o known-plaintext attack: Trudy has plaintext corresponding to ciphertext
o chosen-plaintext attack: Trudy can get ciphertext for a number of chosen plaintext
• Two approaches for cryptanalysis:
o brute force: search through all keys o statistical analysis
Symmetric key cryptography
Bob and Alice share the same (symmetric) key: KS
plaintext message, m
ciphertext KS(m)
m = K’S(KS(m))
encryption algorithm
simple substitution cipher
monoalphabetic cipher: substitute one letter for another
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: mnbvcxzasdfghjklpoiuytrewq
Encryption key: a mapping from the alphabet to itself.
Plaintext: bob. i love you. alice
ciphertext: nkn. s gktc wky. mgsbc
decryption algorithm
DES: Data Encryption Standard
• U.S. symmetric encryption standard
• National Institute of Standards and Technology (NIST), 1993
• 56-bit symmetric key, 64-bit plaintext input
• block cipher with cipher block chaining
• how secure is DES?
o DES Challenge: 56-bit-key-encrypted phrase decrypted (brute force) in less than a day
o no known good analytic attack
• AES: Advanced Encryption Standard, NIS T 2001
• Similar to DES with longer blocks and keys. Harder to break.
DES operation
initial permutation;
16 identical “rounds” of function application, each using different 48 bits of key;
f( ) is complicated; final permutation.
• A Challenge not addressed by symmetric key cryptography: How do Alice and Bob agree on a key value?
• In particular, there may be no secure channel to exchange the symmetric key.
Public key cryptography
§ A radically different approach [Diffie-Hellman ‘76, RSA ‘78]
§ Public encryption key known to all.
§ Private decryption key known only to receiver.
§ Security rests on the computational hardness of reversing
some known mapping, rather than shared secret.
Bob’s public key
KB- Bob’s private key
plaintext m
ciphertext
message -+
encryption algorithm
decryption algorithm
m=K (K (m)) BB
Digital signatures
• Sender (Bob) digitally signs document, establishing he is document owner/creator.
• Verifiable, nonforgeable: recipient (Alice) can prove to someone that Bob, and no one else (including Alice), must have signed document.
Digital signatures
simple digital signature for message m:
• Bob signs m by encrypting with his private key, creating
“signed” message, K-B(m) Bob’s message, m
KB- Bob’sprivate m,K-(m) key B
Dear Alice (blah blah blah)
!s message, m, signed (encrypted) with his private key
Public key encryption algorithm
Digital signatures
§ Alice receives message m along with a signature s.
§ Alice verifies m signed by Bob by applying Bobs public key to
check whether K+B(s) = m.
§ If true, then Alice believes s = K-B(m) and that:
§ Bob signed m
§ no one else signed m
§ Bob signed m and not m’
• non-repudiation: Alice can take m and signature K-B(m) to court to demonstrate that Bob undeniably signed m.
General digital signature
It is expensive to public-key-encrypt long messages. So use hash.
Bob’s private -
Bob’s public +
large message m
H: Hash function
encrypted msg digest
K- (H(m)) B
signature (encrypt)
large message m
digital signature (decrypt)
msg digest
K- (H(m)) B
H: Hash function
Need keys that satisfy
1 K-(K+(m)) = m BB
given a public key, it should be infeasible to compute the matching private key
Elliptic curve cryptography
• The use of elliptic curves in cryptography was suggested independently by and . Miller in 1985.
• Elliptic curve cryptography algorithms entered wide use in 2004 to 2005.
• An elliptic curve is a plane curve over a finite field (rather than the real numbers) which consists of the points in Galois field F(p) satisfying the equation
y2 =(x3 +ax+b)modp.
• A point is represented as Q=(x,y).
• InBitcoin,p=2256 -232 -29 -28 -27 -26 -24 -1.
• All integers of the same residue mod 17 are identical in F(17).
• 52 =8=(13+7)mod17
• 02 =0=(33+7)mod17
• 152 =4=(103+7)mod17
• y and (17-y) satisfy the equation simultaneously.
Toy example y
+7) mod 17
Elliptic curve: addition
• Define addition: If there is a line that pass three points on the curve P, Q, R, then P+Q+R=0, or P+Q=-R.
• -R = 2P = P+P is the intersection of the tangent line through P and the curve.
• 2n+1P = 2(2nP)
NIST secp256k1
• Adopted in the Bitcoin protocol.
• Constructed in a non-random way to be efficient and at the same time to reduce the probability the creator inserted any sort of backdoor into the curve.
• p~=2256 -232
• A fixed generator point G is chosen in the Bitcoin protocol.
• A private key is generated as a random 256-bit sequence.
• Given private key k, the public key K is calculated as the product K = k G. (This admits efficient computation.)
• Given K, there is no known efficient algorithm for computing k such that K = k G. This so-called discrete logarithm problem is hard.
Public key to bitcoin address
• To represent long numbers in a compact way.
• Base64 uses 26 lowercase, 26 uppercase letters, 10 numerals,
and 2 additional characters (+, /).
• Base64 is commonly used to add binary attachments to email.
• Base58 strikes out 6 letters: (0, O, l, I, +, /).
Base58Check
Keys and address
• private key: 256 bits 1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD
• public key: essentially 512 bits
x = F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A y = 07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB
• address: 160 bits, in the Base58Check format for ease of transcribing by human. E.g., 1J7mdg5rbQyUHENYdx39WVWK7fsLpEoXZy
• Using the address in lieu of the public key allows an additional layer of security.
Compressed public key
• Suffices to store the x coordinate (y can be recovered).
• Reduces to 8+256=264 bits. Minimize transaction size.
Review of basic probability
• Probability mass function
• Bernoulli(q)
• binomial(n,q)
• Poisson(𝜆) – it’s the limit of binomial(n, 𝜆/n) as n->infinity.
• Probability density function.
• Exponential(𝜆)
• Poisson point process with rate h.
• Reference: ., A first course in probability, Pearson. (Any edition will do.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com