Alex Kuck has offered to hold some extra office hours this evening to help out on Project 1. You'll find him in the Rice Hall common area (the space next to the bagel shop) today, 5-7pm.

Schedule

Cryptographic Hash Functions

A cryptographic hash function, H(x), must satisfy these two properties:

• one-way (preimage resistance): given h= H(x) it is hard to find preimage x.
• strong collision-resistance: hard to find any pair x and y where H(x) = H(y)

If we use SHA-256 for H, how many 258-bit messages would be expected to hash to a given value x?

Signing Message Digests

Sign: Sign(m) = E(KR_A, H(m))

Given KU_A, m, and S, how does Bob verify that S is a valid signature from Alice for m?

A bitcoin address for public key K is RIPEMD160(SHA256(K)) where both RIPEMD160 and SHA256 are cryptographic hash functions.

Is this more or less secure than just using K?

Suppose someone finds a way to find collisions for RIPEMD160. How serious of a risk would this pose to bitcoin?

Suppose someone finds a way to find preimages for RIPEMD160. How serious of a risk would this pose to bitcoin?

Untraceable Electronic Cash

High Trust Bank must be trusty!

David Chaum, Amos Fiat, and Moni Naor. Untraceable Electronic Cash. CRYPTO 1988.

Simple RSA Signatures
Public Key = (e, n) Private Key = d

Identity: M^de = M mod n

Sign(m) = m^d mod n

Blind Signatures Alice picks random k in [1, n)
t = mk^e mod n
Sends t to signer.

Signer returns t^d.

Signer returns t^d.

t^d = (mk^e mod n)^d mod n
    = m^dk^ed mod n
    = m^dk mod n

Dividing by k gives Sign(m) = m^d mod n.

What should a signer know before signing a random-looking string?

Cut-and-Choose

Suppose Alice sends 256 copies and the Bank checks 255 of them. What is the probability Alice can cheat without getting caught?

What should the maximimum bill size be to prevent cheating?

Identity Strings

I = "alice@alice.org"

M_i = "Bill #[r_i] : Bear’s Turns Bank owes the holder of this message $100."
    + identity strings:       I₁ = (h(I_1L), h(I_1R)), ..., I_n = (h(I_nL), h(I_nR))
    where h is a one-way hash function and each I_iL ⊕ I_iR = I (but I_iL is choosen randomly).

To spend a bill, the reciever chooses either L or R for each pair for spender to open.

What is the probability Alice can spend a bill twice without revealing her identity?

Before Bitcoin: The Rise and Fall of DigiCash

By all accounts Chaum was a charismatic leader with an interesting management style, but he refused to compromise his artistic vision in any area against the best advice of his employees. He was suspicious of everyone and 'paranoid' with a habit of suddenly changing his mind without warning. At one time, Microsoft had offered DigiCash $180 million to allow them to preinstall Ecash software on Windows computers and the deal was on the verge of completion, but Chaum suddenly decided that his product was worth more and the deal collapsed. If the deal had gone through, cryptocurrency would now be as ubiquitous as Internet Explorer.

Schedule

Signing with Elliptic Curves

Elliptic curve discrete logarithm problem: given points P and Q on an elliptic curve, it is hard to find an integer k such that Q = kP.

Parameters: curve, G (a point on curve), (large) n such that nG = 0.

Key pair:
   Private key: d = pick a random integer in [1, n-1]
   Public key: point on the curve, Q = dG

Signing:
   pick random integer k in [1, n-1]
   compute curve point: (x, y) = kG
   signature = (x mod n, k^-1(z + rd) mod n)

What are the reasons for prefering ECC for signatures in bitcoin over RSA-based signature algorithms?

For an interesting history of improvements in factoring, see Carl Pomerance, A Tale of Two Sieves, Notices of the AMS, December 1996:

John Pollard in 1988 circulated a letter to several people outlining an idea of his for factoring certain big numbers via algebraic number fields. His original idea was not for any large composite, but for certain "pretty" composites that had the property that they were close to powers and had certain other nice properties as well. He illustrated the idea with a factorization of the number 2²⁷ + 1, the seventh Fermat number. I must admit that at first I was not too keen on Pollard's method, since it seemed to be applicable to only a few numbers. ... But what of general numbers? In the summer of 1989 I was to give a talk at the meeting of the Canadian Number Theory Association in Vancouver. It was to be a survey talk on factoring, and I figured it would be a good idea to mention Pollard's new method. On the plane on the way to the meeting I did a complexity analysis of the method as to how it would work for general numbers, assuming myriad technical difficulties did not exist and that it was possible to run it for general numbers. I was astounded. The complexity for this algorithm-that-did-not-yet exist was of the shape exp(c(log n)^1/3 (log log n)^2/3).

Erich Wenger and Paul Wolfger, Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster.

It is possible to repeatedly fold a standard letter-sized sheet of paper at the midway point about six to seven times. In 2012, some MIT students were able to fold an 1.2 kilometer long toilet paper 13 times. And every time the paper was folded, the number of layers on top of each other doubled. Therefore, the MIT students ended up with 213 = 8192 layers of paper on top of each other. And poor Eve’s job was to manually count all layers one by one. Similar principles apply in cryptography, although bigger numbers are involved. In Elliptic Curve Cryptography (ECC), where log₂ n-bit private keys are used, Eve does not have to iterate through all possible n keys. Instead, Eve would use the more efficient parallelizable Pollard’s rho algorithm that finishes in approximately sqrt(n) steps. The omnipresent question is how big n has to be such that even the most powerful adversaries are not able to reconstruct a private key. Especially in embedded, cost-sensitive applications, it is important to use keys that are only as large as necessary.

Bitcoin's Curve

Standards for Efficient Cryptography: SEC 2: Recommended Elliptic Curve Domain Parameters (Certicom Research, 27 January 2010)

Verifiably random parameters offer some additional conservative features. These parameters are chosen from a seed using SHA-1 as specified in ANSI X9.62 [X9.62]. This process ensures that the parameters cannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to future special-purpose attacks, and no trapdoors can have been placed in the parameters during their generation. When elliptic curve domain parameters are chosen verifiably at random, the seed S used to generate the parameters may optionally be stored along with the parameters so that users can verify the parameters were chosen verifiably at random.

What does it mean for parameters to be "verifiably random"?

Randomness

Kolmogorov Complexity: K(s) = the length of the shortest description of s.

Kolmogorov's Definition of Random: A sequence s is random, if K(s) = |s| + C

What is the Kolmogorov Complexity of the string 0001000010000011111111100111...?

What is the Kolmogorov Complexity of the string: 1MRigEo5423vycLnUdSnA4C6Ts691fUiYu 18UikW89q9VgGDftQW3Gmuhe4sQDCFP5kD 19ZQwQmfAsgy47ErehfkW3SeSzNGFfH9iN 1AZCH1insc6JrT2Z9SiNvgtTugXg8sF8yd 15qYggRJvmyZfpchxvNqr6h3pNjw6bGBV9 1C943NwPPffUFY7VDzi3kt7KikXwc2vdkN 1JBhLLCgNYhR8f6AZcRS3mjfEAmMzPvwyf 1JvDrBSYm6o4ZTQUhwUE4FhPFxd2wuXWUR 1KcBM1RNhcp1oENycoD4AezA5Se4SrsZnA 16JZWC433XRxjWwR7X65uxRVFdLTmoPr4t 149LB8VYaT1BdMLyQUL92Kj6KrJfNwcp64 16zDGuzbwkHjW8dNYMw9stDjRbTzVSLZU1 1HfMaZn53ZDWKgmhWxk1UPZMjQ6QmpW6m 14gZWnuwKpRLTCUFCAgTZMciRaEdrkmEpr 1BZ2ateDPugmqLzYsXVy9EK5BguvXa2Bnj 1rCdRyMVcZHJaHA2LKUvRqYBcHqvAfQkc 1Ak8VwX6x4FPbA6aXTC3BQGQHnnhfaJuB8 129sBvF6Jternwdn5XcoA37LinQRcmAD5U1H2in 1HxEzSKHssPtog2krjFPiPfrKSiw4... ?

Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, and Christine van Vredendaal. How to Manipulate Curve Standards: A White Paper for the Black Hat, 2014.

How likely is it that the parameters for the secp256k1 curve used by bitcoin have a trapdoor?

How should ECC parameters be generated for an important curve in a standard?

Root Zone DNSSEC KSK Ceremonies Guide. If you have a few hours to spare, you can watch a key signing for the DNSSEC (Domain Name System): DNSSEC KSK Ceremony 20

Dual-EC PRNG

NIST Special Publication 800-90A Recommendation for Random Number Generation Using Deterministic Random Bit Generators

P and Q are points on the curve, specified by the standard (but not explained how Q is choosen). P is a generator, so there exists some e such that Q^e = P.

s₀ = initialize with seed randomness
s_i+1 = ϕ(s_i × P)
r_i = ϕ(s_i × Q)
o_i = the low-order 16 bits of the x-coordinate of r_i.

Given o_i, how much work is it to find all the possible r_i = (x, y) values?

Given e, what is ϕ(e × A) where A is a possible r_i value?

Dan Shumow, Niels Ferguson. On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng. CRYPTO 2007 Rump Session.

Michael Wertheimer (NSA), Encryption and the NSA Role in International Standards, Notices of the American Mathematical Society, February 2015.

Wertheimer's letter is an attempt to respond to Mathematicians Discuss the Snowden Revelations.

The recent revelations about the NSA’s spying programs are both dismaying and encouraging. What is encouraging is that they might lead not just to a reform of the intelligence agencies but also to a more serious look at what the ongoing and inevitable erosion of privacy is doing to our society. What is dismaying is less the intrusive data collection itself and more what it reveals about the decision-making processes inside the government. (Andrew Odlyzko)

How satisfying is the NSA's response? Are you more dismayed or encouraged?

Here's the office hours schedule, starting this week:

David Evans:
Mondays right after class.
Thursdays, 4-5pm in Rice 507.

Nick Skelsey:
Monday nights from 5-7pm in Rice 442 (Dave's lab).
Fridays from 12-2pm at Hackcville (#9 Elliewood Ave).

Note that you can see these, as well as other events in the class in the course calendar (which you should be able to embed in your own calendar). When we need to canel or reschedule office hours, it will be updated on the course calendar.