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.
Upcoming office hours: Thursday 4-5pm (Dave, Rice 507); Friday (Nick, noon-2pm in Hackcville).
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(KRA, H(m))
Given KUA, 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: Mde = M mod n
Sign(m) = md mod n
Alice picks random k in [1, n)
t = mke mod n
Sends t to signer.
Signer returns td.
Signer returns td.
td = (mke mod n)d mod n
= mdked mod n
= mdk mod n
Dividing by k gives Sign(m) = md mod n.
What should a signer know before signing a random-looking string?
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?
I = "firstname.lastname@example.org"
Mi = "Bill #[ri] : Bear’s Turns Bank owes the holder of this message $100."
+ identity strings: I1 = (h(I1L), h(I1R)), ..., In = (h(InL), h(InR))
where h is a one-way hash function and each IiL ⊕ IiR = I (but IiL 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?
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.
Scheduled office hours:
Dave: after class Mondays, Thursdays 4-5pm (both in Rice 507)
Nick: Mondays 5-7pm (in Rice 442), Fridays (noon-2pm in Hackcville, #9 Elliewood Ave)
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.
Private key: d = pick a random integer in [1, n-1]
Public key: point on the curve, Q = dG
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 227 + 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 log2 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.
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"?
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
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?
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 Qe = P.
s0 = initialize with seed randomness
si+1 = ϕ(si × P)
ri = ϕ(si × Q)
oi = the low-order 16 bits of the x-coordinate of ri.
Given oi, how much work is it to find all the possible ri = (x, y) values?
Given e, what is ϕ(e × A) where A is a possible ri 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:
Mondays right after class.
Thursdays, 4-5pm in Rice 507.
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.