Schedule

Notes

What does it mean for a problem to be hard?

If you know an algorithm with running time in O(2ⁿ) for problem P, what do you know about the hardness of problem P?

What are the most common reasons for cryptosystems to fail in practice?

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?