-
Notifications
You must be signed in to change notification settings - Fork 1
/
original_instructions.html
57 lines (56 loc) · 17.6 KB
/
original_instructions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
<!-- saved from url=(0062)file:///virt/s2/rootspare/home/antony/dev/go/Instructions.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"></head><body>
<p>It was good chatting with you, and thanks for accepting my programming challenge - here are the details. Please ACK when you receive this message.</p>
<p>Especially since you are one of the first victims…I mean volunteers to take this challenge, I’ll try to be available (perhaps intermittently) to answer any clarifying questions. However, I may elect to answer only questions on which I agree that the instructions below were overly unclear or outright broken. Please try not to get “blocked” waiting for answers, but try to figure out a reasonable way to make progress even in the presence of imperfect/incomplete information; that’s in effect part of the challenge. :) But if you feel it is taking an unreasonable amount of your time, feel free also to stop after stage 1 or 2, as I haven't yet fully calibrated its difficulty yet.</p>
<p>The challenge will be in three stages, each successive stage building on the last and getting progressively more challenging. Please E-mail me your solution to each stage individually, as soon as you complete that stage, rather than waiting until you have everything done.</p>
<p>The challenge uses the Go language - you should probably make sure you’re using a recent version (currently 1.4.x). We will use the DeDiS crypto library, available at: https://github.com/DeDiS/crypto You can find more complete godoc-based documentation for the library and its packages at: http://godoc.org/github.com/DeDiS/crypto You will by no means need to learn or understand the whole library; I will provide pointers below to the specific packages and APIs you will need, and other relevant background information.</p>
<p>You will be building a small client/server application that performs a few cryptographic operations using the above crypto library. You could implement the client and server as separate Go programs (each with its own ‘main’ package), or as one program taking a command-line parameter to select between its client and server roles - either is fine with me as long as it’s clearly documented.</p>
<p>The code should have embedded godoc-compatible documentation (see http://blog.golang.org/godoc-documenting-go-code) for any public symbols exported from your main package(s) and any other shared or utility package(s) they might depend on. You can get a live, local godoc server by running 'godoc -http=:6060’ and browsing localhost:6060 to see what the output looks like. No need for the documentation to be extremely long-winded, only clear: I believe in concise clarity as an important art (though all-too-often seemingly unattainable).</p>
<p>Your code should also have basic unit-tests covering the critical functionality you will be implementing (see http://golang.org/pkg/testing/). Your unit tests do not have to try to exhaust every conceivable corner case or error condition, but should automatically test the main code paths. I appreciate concise test code as well as concise documentation: e.g., a small amount of test code cleanly and efficiently covering a large, possibly parameterized space of test cases is better than a large number of tests each covering just one tiny, narrow scenario. I should be able to run all your tests via a ‘go test -v ./…’ at the top level of your package.</p>
<p>For simplicity, please send me your solution at each stage as a tarball of your top-level package. (My group of course uses git for source code control, and you’re welcome to keep your solution code under git as well and send me a tarball of your local git repo after each stage, but that’s up to you.)</p>
<hr>
<p>Stage 1: Client/Server Signing</p>
<p>The first stage is to implement a simple TCP server that simply accepts arbitrary messages exactly 1KB in size from clients, and in response to each submitted message, simply returns a digital signature over that message. You might consider this to be part of the functionality of a basic “digital notary” or “timestamp service”, for example (minus the actual timestamp or other metadata like hash-chains, which we’ll omit here but would be trivial to add). See http://golang.org/pkg/net/ for details on Go’s sockets API; you’ll probably be mainly interested in DialTCP and ListenTCP.</p>
<p>The server should simply listen for incoming TCP connections; when one arrives, it reads 1KB of data on the connection, without interpreting that data in any way, then computes a signature on the received data send the binary-encoded signature in reply on the TCP connection, and finally closes the connection. If the server receives less than 1KB of data on a connection, it should simply close the connection with no (empty) reply. </p>
<p>The corresponding client should simply exercise the server by sending 1KB blobs of data from any source you like (e.g., a random bit-stream), and verify the returned signatures against the server’s public key, which you may assume to be well-known. The public key could be deterministically generated at runtime by both the client and server as part of the test framework, or loaded from a disk file somewhere - the dedis/crypto/config package has some code that might be useful if you want to do this, but don’t spend any significant time worrying about doing proper key management, since that’s not what this exercise is about.</p>
<p>The signatures your server produces should not use RSA or [EC]DSA but rather the Schnorr signature algorithm. See https://en.wikipedia.org/wiki/Schnorr_signature for basic background, and crypto/sig_test.go for some existing example code implementing this algorithm. You’re welcome to use that code itself (cut-and-paste is fine), but make sure you understand the basics of how the code works and uses the crypto library because you’ll need that understanding for the later stages below. This first stage isn’t supposed to be “hard”, but rather just more of an attempt at a gentle introduction to the building-blocks we’ll be using later.</p>
<p>Since Schnorr signatures are just a “trivial case” of a very powerful and general framework for zero-knowledge proofs, if you’re not already familiar with it, I also recommend looking through Sections 1-3 of Camenisch/Stadler’s paper “Proof Systems for General Statements about Discrete Logarithms" (ftp://ftp-dept.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf) to get a high-level understanding of how “Challenge/Response” protocols like Schnorr signatures work. Note that the Camenisch/Stadler paper uses slightly different terminology and notation than the wikipedia page on Schnorr signatures: e.g., Camenisch/Stadler’s “commitment” t is called k on the Wikipedia page; the “challenge” c is called e on Wikipedia; and the “response” r is called s on Wikipedia. You do not need to understand how the Camenisch/Stadler framework handles complex AND/OR predicate expressions or multiplicative combinations of group elements, but having a general gist for how such challenge/response protocols work may be helpful.</p>
<p>One more notational heads-up, if you’re not already intimately familiar with public-key cryptosystems. Much of the classic documentation on discrete-log crypto systems (including the Wikipedia page above and the Camenisch/Stadler document) use “multiplicative-group” notation, where the primitive group operation is assumed to be multiplication, and repeated application of that is represented as exponentiation (e.g., g^x). However, in more recent elliptic-curve literature, “additive-group” notation tends to be increasingly common as it is more natural in the case of elliptic-curve crypto: in this case the primitive group operation is point addition, and repeated application of that is representative as multiplication by a scalar (e.g., xG where x is the scalar and G is the base point or generator). You can treat these as merely two different notations for semantically equivalent sets of operations; it may just be a bit confusing because the classic literature above uses multiplicative-group notation whereas the DeDiS crypto library’s Point interface uses additive-group notation for consistency with recent elliptic-curve crypto practice. Thus, ‘Point.Add’ is the basic group operation, and ‘Point.Mul’ is scalar multiplication (xG), which you can treat as equivalent to the g^x notation you find in other documentation.</p>
<p>You’re welcome to use any of the elliptic curve implementations and ciphersuites the DeDiS crypto library provides, the two most obvious choices being the NIST P256 based suite in the crypto/nist package (which the sig_test.go is already set up to use), or the implementation of the Ed25519 curve in the crypto/edwards/ed25519 package if you’d like a second alternative to test against. No need to learn about or understand all the details of where these curves come from or how they work at this point, only that they all support the appropriate abstract arithmetic operations represented by the generic Point and Secret interfaces in the crypto/abstract package of the crypto library (see http://godoc.org/github.com/DeDiS/crypto/abstract). For now all we care about is using these interfaces as cryptographic building-blocks. You can simply pick one ciphersuite and use it for this and the remaining stages below.</p>
<p>I also don’t particularly care exactly which binary encoding you use for your Schnorr signatures - it needn’t be compatible with any particular existing standard - but a simple default binary encoding is already used in the sig_test.go example, so the easiest thing is probably just to use that.</p>
<p>As a reminder, please E-mail me a tarball of your solution to this stage when you complete it.</p>
<hr>
<p>Stage 2: Simple Schnorr Multisignatures</p>
<p>In this second stage, you will need to split the single server role from the previous stage into two separate servers, each holding separate private keys (x1, x2) and corresponding public keys (X1=g^x1, X2=g^x2). We will combine these two servers’ public keys into a single composite public key X=g^x by multiplying the individual public keys together: X = g^x = (g^x1)(g^x2) = g^(x1+x2). Or equivalently in additive-group notation as the DeDiS crypto library’s interfaces use, the public keys would be X1=x1<em>G and X2=x2</em>G (secret scalars multiplied by the base-point/generator G), and the combined public key would be X=(x1+x2)<em>G, which can also be computed as X=(x1</em>G)+(x2*G). Finally, the client will be able to interact with the two severs to get a 2-part “multi signature” on any message it submits: i.e., a Schnorr signature that anyone can verify against the combined public key X without needing to know or care that two servers were involved in producing that signature.</p>
<p>This is a special case of more sophisticated threshold-cryptography techniques, for which arbitrary t-of-k signing may be implemented via Shamir secret sharing (see https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing for example). However, you will not need to do full Shamir secret sharing here (although some of the code needed for that is available in the crypto/poly package of the crypto library). We will only worry about the special case for which both ’t’ and ‘k’ are 2, hence both of the two servers are needed to produce a signature verifiable against the combined public key.</p>
<p>To implement simple 2-way multi signatures, the (still fairly simple but not completely trivial) client/server protocol you will need to implement is as follows:</p>
<ol>
<li>
<p>The client opens TCP connections to the two servers, and sends each server the same 1KB message M.</p>
</li>
<li>
<p>Each server independently chooses its own random secrets (v1, v2) using Camenisch/Stadler notation, or (k1,k2) in the notation used on the Wikipedia Shnorr signature page. Based on this, each server computes a corresponding public commitment (t1=g^v1, t2=g^v2), and sends the respective t1 or t2 back to the client.</p>
</li>
<li>
<p>The client combines commitments t1 and t2 into an aggregate commitment t=t1*t2 in multiplicative-group notation (meaning Point.Add in the crypto library since it uses additive notation). The client sends this aggregate commitment t back to both servers.</p>
</li>
<li>
<p>The client and both servers can all now compute a single, “collective challenge” c, using a hash function that depends on the message M and the aggregate commitment t. Based on this challenge, each server now computes its “share” of a response, (r1 = v1 - c<em>x1, r2 = v2 - c</em>x2), and sends its response-share (r1 or r2) back to the client.</p>
</li>
<li>
<p>Finally, the client computes a combined response r = r1+r2. The resulting multi signature is (c,r). The client, and anyone else, should now be able to verify this signature on the message M against the composite public key (X = X1*X2) using the same Schnorr signature verification code you used in the first stage. (This works because of the homomorphic properties of discrete-log crypto systems, but no need to get into details for now.)</p>
</li>
</ol>
<p>In principle the above should be all you need to know to implement basic multisignatures for the moment, although there is a deep, rich literature on multisignatures and important security caveats in practice. See https://www.cs.bu.edu/~reyzin/papers/multisig.pdf for example for background, issues, and pointers to other relevant literature in this space - but no need to take time studying it for purposes of this challenge.</p>
<hr>
<p>Stage 3: Partially Blind Signatures</p>
<p>The final part of the challenge is to implement a single client/server “partially blinded signature” protocol, as specified in Abe and Okamoto’s paper “Provably Secure Partially Blind Signatures”: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.6004&rep=rep1&type=pdf You do not by any means need to read or understand the whole paper, especially the security proofs. In fact, most everything you need to know (and perhaps everything you need) is in Figure 1 on page 277. </p>
<p>This is one of many blinded signing schemes in the spirit of Chaum’s original invention designed to support untraceable, anonymous e-cash. See http://people.dsv.su.se/~matei/courses/IK2001_SJE/Chaum90.pdf for quite readable and interesting early background, but you don’t need to soak in or understand all the details of that for purposes of this challenge, though it may be helpful in understanding why blind signatures are interesting. In the blinded client/server signing system you’re building in this stage, you can think of the server as a “bank” in a Chaum-style e-cash system. The client then represents a user who “withdraws” a “coin” from the bank by getting the bank’s blinded signature on a message that the bank never actually sees, so that the bank will not be able to trace (later) how or when the customer later “spends” the coin (at which point the bank verifies the signature when depositing the coin into someone else’s account). Again, no need to understand all the details; this is just for background.</p>
<p>The Abe/Okamoto protocol is interesting and useful for our purposes here because it is at its core just a slightly souped-up and (partially-)blinded version of the Schnorr signature scheme we’ve been using above in the first two stages. You can just go back to the single-client, single-server case used in Stage 1 for now; no need to implement blind multi signatures (although that should certainly be possible too!). Just implement the partially-blind protocol as specified in the paper, between a single client and a single server. </p>
<p>For the “unblinded” portion of the signature, represented by “F(info)” in the protocol, you can use any deterministic function, which will in effect represent the “type of coin” in the Chaum-style e-cash example: e.g., F(info) will be the same for the same “denomination” of coin and different for different denominations. For example, you could hash the text “One Chaumian FoozleCoin”, use that to seed a cryptographic PRNG, and use Point.Pick() to pick the relevant point z in the protocol representing the coin’s denomination. Everything else in the protocol should be, more-or-less, straightforward arithmetic.</p>
<p>Since in this case the server (purposely) is not supposed to know what message is being signed (other than the unblinded part representing the denomination of the coin), the client no longer needs to send a message M to the server. Instead, when a client opens a TCP connection to the server, the server should just immediately respond with the a,b that the Abe/Okomoto protocol specifies, and continue from there, until the client is left with the 4-tuple (ρ,ω,σ,δ) representing the final blinded signature. Then the client should (of course) verify the signature against the corresponding (α,β,z,msg) that it used in the signing process (which the server will not know because of the blinding).</p>
<hr>
<p>That’s it - again, please send me your solution for each stage as you complete it. </p>
<p>If after you’re done it so happens that you find the challenge too easy and are left yearning for more, you might try to (a) generalize the Stage 2 project into (t-of-n) threshold signatures using the Shamir secret sharing code available in the crypto/poly package; and/or (b) figure out how to combine the Stage 2 and Stage 3 techniques into a partially blinded multisignature protocol. But this is by no means either required or expected.</p>
<p>Good luck; I hope you have fun with this and I look forward to seeing your solutions!</p>
</body></html>