# Lab 08a: Secret Sharing

Spring 2019

The questions below are due on Thursday April 04, 2019; 10:00:00 PM.

Partners: You have not yet been assigned a partner for this lab.
You are not logged in.

Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.

Tearing up Secrets

Goals:Today and on Thursday we're going to get some exposure to git in advance of the final project and then implement a secret sharing scheme. This lab will also serve as a review/more practice with writing some server side scripts that are a bit more time-sensitive.

## 1) Git

When working on files either alone or with collaborators, there's often the desire to prevent overwriting/forgetting/messing up certain versions of files. Let's say you got some functionality working with your code, and then you decided to go further and add more functionality, but all of the sudden nothing works. You try to undo and still nothing works. We've all been there (if Piazza posts are any accurate indication). Similarly, if you're working on a shared file in Word with a friend and you both edit the same paragraph at the same time and don't keep in constant communication, when you try to put your work together, it can be a mess.

Version control software is one solution to this and we'll be using git in this lab. Version control allows you to keep track of previous versions of files as well as collaborate with others in a way that ensures changes made by any user aren't necessarily lost right away, but instead will exist in various revisions and branches. The basic idea of how we'll be using it (highly simplified) is that a central repository (repo) of files exists on a centralized server (we'll be using MIT's Github service, which you should all already have accounts on) and then individual users clone this repo onto their local computer using the git clone command so they have their own copy of everything on their computer which they are free to work with and change and modify as needed via the git add and git commit commands.

Users can, when they want, contribute their changes from their local copy to the master copy using the git push command. If other users are contributing, then a user can also harvest/collect the changes pushed to the master repo using the git pull command. While all of this is happening, git is making sure that no conflicts between different versions of files happen and nothing gets lost. Git makes an attempt at resolving any conflicts that have a generally accepted solution (you edited the top of a document, and your friend edited the bottom of a document...in this case it combines these). You can try this with a git merge. More difficult-to-judge conflicts (edits in the same block of code), must be merged manually.

git != github. git is a free software created initially created by Linus Torvalds (also creator of Linux). Github is a company that provides a service based on git and its own web-based stuff. You can use git without Github (and many do!). You cannot use Github without git.

Let's get started by creating our own repo with MIT's github. For starters, go to https://github.mit.edu/ and sign in. Nowadays it should be the same as just signing into most MIT sites, most likely with two-factor authentication.

On the homepage, create a new repository that will be yours and give it the following settings (updating kerberos for you) as shown in the image below. Make sure to initialize your repo with a README. Normally a README is used to give an overview of the repository, including instructions like how to use things within it and work with it. We'll be using it mostly as an example file to mess with in working a bit with git.

You'll next need to get git on your computer. Links to do that for the three OS's are here (Most of you will already have it in place though if you installed the ESP32 core so proceed into these links with caution to make sure you don't redo stuff you've already done).

Once installed, we will be using the git shell/terminal. In Mac and Unix/Linux systems this will just be the terminal/shell. On Windows this will be the git bash shell. This is a Linux shell so you need to be familiar with how to work in it a bit.

If you aren't comfortable moving around in a terminal, here are a few basic commands as a refresher. You should be at least somewhat used to these from working on/with the 608dev.net server. Ask a staff member for help!

• cd: Move your current view to "home directory"
• cd DIRECTORY: move into a directorya
• cd ..: Move up one directory level
• cd -: Move to the previous location you were at
• cd ~: Move to home directory
• ls: List contents (files, etc.) of specified directory
• pwd: Print the path of the current working directory

Check Yourself:

Can you move up and down in the file structure on your computer using these commands?

Once git is working, on your Github repo, get the path to your remote repository from the Clone/Download button on the page. You can either clone/work over HTTPS or SSH. HTTPS is probably the easier one to do today, and that's what we'll show below, but SSH is the less-annoying one to do long-term, though does require a bit more setup. If you'd like to set up your system for SSH, you can doing the steps discussed at this link.

Then, in terminal or git bash shell, move to your home directory (or another directory if you prefer, but try to avoid something in Dropbox or OneDrive, GDrive, or iCloud to avoid syncing issues) and type the following:

git clone PATH_FROM_GITHUB name_youd_like


This says, "make a local clone of the repo located at PATH_FROM_GITHUB and call it name_youd_like.

On my computer, with my path I did the following, for example:

git clone https://github.mit.edu/jodalyst/lab08a.git lab08a


...yours should be similar, but for your kerberos and whatever you called your repo. If you don't specify a name for the local copy, git will create a directory with the same name as the remote repository.

Move into the repo using a command like the following (replacing lab08a with whatever you called your local copy)

cd lab08a


Once inside show the files by doing:

ls


You should see the following show up:

README.md


Now open that README.md (either through a GUI file manager/editor or a command line editor if you are comfortable with that) and add in a line of text about something random. Use whatever text editor you like (Sublime, notepad, NOT Word). When you are done, save it.

Then in the terminal/shell enter:

git commit -m 'modifying README' README.md


git push origin master


Press Enter, and some text should fly by indicating a good push. Let's deconstruct what you just did:

First, you entered the command git commit -m 'modifying README' README.md. This creates a new commit, which is a list of changes to the repository. The -m 'modifying README' part is where we specify a message to go along with the commit - so that other people who look at this commit (including future you!) know what happened in it. The README.md at the end is the file (or files) containing changes we want to include in this commit - in this case, we only changed README.md. If you omit a filename from the end of the statement, git will commit all added files (see the command git add later on this page for more information on how this works).

Second, you entered the command git push origin master. git push tells git to push any new commits we've made to a remote (not on your computer) repository. origin tells git which remote repository to push to - in this case, the one nicknamed origin, which is the one we specified when we originally cloned the repository (the one you made on github.mit.edu). master tells git which branch in the remote repository we want to push to - in this case, master is the only branch, both here and in the remote repository.

Let's go back into the README.md file again and add in another line of text (your choice). Save it and then go to your terminal/shell but do not commit...instead check the status using the git status command. It should return something similar to the following:

On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)

no changes added to commit (use "git add" and/or "git commit -a")


It is telling you that currently you have a modification in the README.md file which has not been committed to a head yet. Go ahead and then type: git commit -m 'another README update' README.md and then check the status again. You should see:

On branch master
(use "git push" to publish your local commits)
nothing to commit, working tree clean


Ok, this is saying your change has been committed and that your current working copy is one commit/set of changes ahead of the master copy in the remote repository.

Now push using git push origin master and do git status one more time. You should see:

On branch master
Your branch is up-to-date with 'origin/master'.
nothing to commit, working tree clean


Next, copy the entire code directory for this lab into your local repo (here it is for your convenience). Don't copy the zip file, copy the uncompressed directory within the zip. When this is done and you are in the root of your repo, typing ls should show:

README.md lab08a_esp


You can move into lab08a_esp using the cd command (cd lab08a) and can look inside that if you'd like to. When you're done, return to the root of this repo and do the following to add that folder you just copied into your local repo's tracking:

git add lab08a_esp


Then commit that new file:

git commit -m 'adding in lab08a ESP32 code file'


Then push to your master repo using the appropriate command. Returning to the Github online interface, you should see the files there now!

### 1.1) Adding a New Collaborator

Now in the Github interface when under the appropriate repository, go up to Settings (the one with the Gear symbol midway on the page), and select Collaborators and New Collaborator. Once in there, add your partner's kerberos. Your partner should receive a notification about this, probably via their MIT email. If you or your partner don't get this, let us know.

At this point in the lab you should also receive a similar notification from your partner's repo. Go back to your terminal/shell and return to your root...(type cd). Then from there you are to clone your partner's repository. Call it something like partner_lab08a or voldman_lab08a (if your partner's kerberos is voldman).

For example when I did this with Joel (kerberos: voldman), I typed:

git clone https://github.mit.edu/voldman/lab08a.git voldman_lab08a


And I'm guessing he did something like this with me since my kerberos is jodalyst:

git clone https://github.mit.edu/jodalyst/lab08a.git awesome_lab08a


If you move into your clone of your partner's repository (cd command), you should see their file structure, which should look identical to yours. View their copy of the README.md and see if it is different from what you did before.

### 1.2) Quick Set of Commands

A short list of commands we just used (and one or two new ones is below):

• git clone: Used to make local copy of remote repo
• git status: Returns the current status of your directory (are you up to date with the master repo?, do you have uncommitted changes?)
• git commit -m 'message' files: Adds changes to a repository's history
• git add file1: Adds file1 into current branch, to be included in your next commit
• git rm file1: Removes file1 from being tracked by git (does not actually remove file) (need to commit after that)

### 1.3) Working Collaboratively

Ok now, you and your partner should decide on one repo to work on together collectively. It can either be your partner's or yours, but you need to pick. This is what you'll be using for the rest of this lab section. Note that this will be the first repo cloned for one person and the second one cloned for the other person in the order of events above.

What you're going to do now is collaboratively edit this README.md document. Both partners should add some of their own text to the bottom of the file. They should both commit (with a meaningful message) and then push. What will happen is that someone will win and in the process of pushing someone will get an error that looks like the following:

To https://github.mit.edu/jodalyst/lab08a.git
! [rejected]        master -> master (fetch first)
error: failed to push some refs to 'https://github.mit.edu/jodalyst/lab08a.git'
hint: Updates were rejected because the remote contains work that you do
hint: not have locally. This is usually caused by another repository pushing
hint: to the same ref. You may want to first integrate the remote changes
hint: (e.g., 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.


What's happened here is that the repo has been edited in two different ways by the two users. The first user to successfully commit and push their local changes to the master repo wins here and the user who comes in second now must resolve the changes! The great thing is that the second user doesn't automatically overwrite what the first user did. Instead, the system indicates a merge conflict that needs to be resolved by the second user before making additional changes. First, the second user should follow the instructions in the previous message and do a git pull. Git will try to automatically merge the changes between the two edits in the repository. If you changed File A and your partner changed File B, for example, chances are the automatic merge will be successful and things will be ok. If the automatic merge fails because your edits overlap (for example here, you're editing the same location in the document), in the process you'll get the following error:

remote: Counting objects: 3, done.
remote: Compressing objects: 100% (2/2), done.
remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (3/3), done.
From https://github.mit.edu/jodalyst/lab08a
0c53650..44f65fa  master     -> origin/master
CONFLICT (content): Merge conflict in README.md
Automatic merge failed; fix conflicts and then commit the result.


If you then run git status you'll get the following, which tells you how to fix the problem.

On branch master
Your branch and 'origin/master' have diverged,
and have 1 and 1 different commits each, respectively.
(use "git pull" to merge the remote branch into yours)
You have unmerged paths.
(fix conflicts and run "git commit")
(use "git merge --abort" to abort the merge)

Unmerged paths:
(use "git add <file>..." to mark resolution)

no changes added to commit (use "git add" and/or "git commit -a")


So let's open up our README.md file on the slower partner's computer and see what's there. You'll see something like the following:

# lab08a
Repo for lab08a in 6.08

Extra good stuff

=======
>>>>>>> 3fbf664326d81dcf0923ab36f6b24d4044de3118


You'll see the text from both user's work, but extra weird stuff like <<<HEAD and === and >>> 3fbf6. These are indicating where the merge conflict occurs in your document. The content outside of this area is agreed upon by both users' versions of the code. The content between <<< HEAD and === is user 2's version of the conflicting region. The HEAD to === region refers to what is on your local copy. The content between === and >>> 3fbf6 is user 1's version of the conflicting region, which in this case is the other commit you're trying to merge with. The long string of number/letters is an identifier for the particular commit that brought in that contribution.

In the case of this test problem, you'll want to keep both partner's contributions probably, so you can remove the three pieces and then save the file so that it looks like this:

# lab08a
Repo for lab08a in 6.08

Extra good stuff



You then need to add it back in

git add README.md


Then commit it with a meaningful message like something about resolving a merge

git commit -m 'resolving merge conflict'


Then push:

git push origin master


Then view on the master repo and you should see both contributions are present.

Checkoff_1:
Show your partner(s) and you correctly working on the README.md file together. Be prepared to demonstrate how you resolve a merge in that file.

For more juicy details on git the 6.031 git overview is a good one to read through.

When done, onto the next part!

## 2) Secret Sharing

In exercises last week (and this week too) we looked at some really simple means of encryption and decryption of messages. In other words, as shown in the figure below, we were developing a way (albeit an easily cracked one) to enable two parties to securely communicate while preventing outside parties from understanding what was being transmitted

Today we're going to investigate another form of data security. We want to develop a secret-sharing infrastructure. This solves a fundamentally different problem than the encryption up above. Instead of ensuring two parties can talk securely together, we want to ensure that two or more parties can securely "consent" on a topic while making sure no party can act on its own. In effect we are going to have a secret be required for some action to take place, but are going to subdivide that secret among multiple parties so that no single user has enough information to get/use the secret. A prototypical situation is where you want to make sure a system acts only if there is agreement among parties. How can we design something electronic to work like that? The problem is illustrated below:

Further can we design the system where we only require a subset of approved parties to consent?

We can find an answer to this predicament in a simple line on a 2-dimensional plane:

As we've probably learned in multiple math classes from growing up, in order to fully define a line, you need to only provide two points. This is sufficient to uniquely determine a line. Along with a line comes a y-intercept, of which there will only be one per line, provided we don't have a perfectly vertical line located at the origin. Another way of thinking about this is, that given two points (x,y), they will uniquely specify a y intercept, but if you have only one point or the other point, you can't figure that out. More importantly, if you give each point to a separate entity, and tell them to keep it secret, only when they provide their two points to some central entity will their actions be able to result in the secret y-intercept being determined. We'll call these points "shards", as in shards of glass, or shards of the secret.

If we treat this y-intercept as the secret we want to keep safe, then what we've done is spread a part of that secret across several distinct entities. Neither entity has enough information to know the secret, thus ensuring that only a critical mass of provided shards will allow determination of the secret.

What's interesting about this setup is that you don't need to provide only those two specific secret shards. Since a line has infinitely many points, one could choose another pair of points to generate shards and they'd be equally as effective:

Furthermore, if you simultaneously deploy more than two shards like in the figure below, you can have a system where any two shards can be combined to generate the key:

If we'd like to be more restrictive in the number of required parties, we only need to increase the order of our polynomial. For example if we want a consensus of at least three entities, we can use a second-order polynomial (a quadratic).

A quadratic can be uniquely specified by any of its three points, so the same sort of approach can be undertaken, just with more shards:

This entire approach is known as Shamir's Secret Sharing Scheme (SSSS), developed by Adi Shamir. What's the first letter in Adi's last name? S, you say? Is it coincidence that there's also an S in RSA? Nope. He is that S. He was one of the guys (along with Ron Rivest for the R, Leonard Adleman for the A) who developed RSA and has done some other fantastic work cryptography and security!

So this SSSS has a lots of uses. Let's say you run a big company with four chief officers (CEO, CTO, etc...) and you only want to be able to pay out money to vendors if all four chief officers agree. You choose a secret code needed to release funds that you give to a trusted third part, perhaps some automated secure Python script. You make that secret code the constant term of a third order polynomial and then randomly choose the other three coefficients to generate a hidden 3rd-order polynomial. You then produce four coordinate points (x,y values) and provide each of your four officers with one of them (the shard...a point coordinate pair). You then make sure your secure script will only release the money if:

1. four shards are provided
2. the four shards provided describe a 3rd order polynomial with an identical constant (the y-intercept) to what the secret code is.

The result is that all four points will need to be provided by your chief officers!

Another use for SSSS, which is perhaps a bit more relevant of the times, is for backing up the seed value needed to recover your wallet for the highly-stable and functional crypto-currency Bitcoin in multiple geographic locations. Let's say you have five servers spread throughout the world and you want to use them to securely store backups of some critical number for your bitcoin wallet (if you lose that number you lose your bitcoin). Keeping the entire secret value on one computer (or keeping it completely on five separate computers) is potentially insecure (someone could steal it). Breaking the secret value up across the five servers is also problematic since if one goes down and/or gets stolen, you won't have the full secret anymore. One solution is to use SSSS to break it up so that any three of the five servers is sufficient to recover the seed by giving each server a part of the key. If someone steals one of your servers, whatever...the thief doesn't have enough information to steal your cryptocoinz and you still have enough information in your remaining servers to get at your cryptocoinz.

Now in real-life implemenation, they usually use much higher-dimension geometries/polynomials, but the general idea holds true! It is beyond the scope of this short lab to go into a more modern and viable implementation of SSSS, but maybe that could be a final project element?

## 3) Implementation

So now it is time to implement a version of SSSS in your group. We're not going to implement a super-secure version...just one that basically uses the thought-experiments above with polynomials in a plane. We'd like you to create a system where a critical number of users (three) must (via a POST from their ESP32 lab kit, or two ESP32 labkits and one spoofed one via POSTman) submit their shards and usernames within a 20 second sliding window in order to enable a GIF of your choosing to be available upon visiting your site in a web-browser via a GET request. The system must not only prevent viewing of the GIF if less than three shards have been provided in the allotted time, but should also prevent viewing if the three shards specify a polynomial with a y-intercept (the constant term) that is different from the secret value.

Again, to reiterate and restate what you must do:

• If any three valid users submit three valid shards within a 20 second window...
• Visiting the python script via a GET in your web browser should reveal a super-secret valuable GIF of your choice that should be available until the 20 second window has passed.
• At all other times, visiting your python script via a GET in the web browser will provide a sad face text emoticon.

Additionally, if a user submits the same valid shard several times within a 20 second window, and two other users submit their unique shards as well within that same window, the GIF should also be released

Additionally, if a user submits a bad shard and a good shard within a twenty second window, the system should default to not accepting anything until only a good shard exists.

Additionally, you must be sending your shards up in the body of your POST. Failure to do this will cause you to fail the class.

In terms of what you put on your labkit, you don't need to do much. The ESP32 code (provided here) should only need minor modification to be working, including ensuring your wiring is matched with the button it assumes, and that your POST body content is correct with how you are setting up your server-side script (remember you must be POSTing). What you change will vary from group to group.

There are ongoing issues with the 6.08 routers on the 2.4 GHz band (the one used by the ESP32s) that suddently appeared over Spring Break we're trying to resolve. The 5GHz band is mostly clear, which is why your laptops are working fine, but the 2.4 interference may cause problems. As always do as much development of your system on Postman or similar, and then when ready shift to the ESP32.

Details of your implementation are up to your team. However, your group should collectively develop TWO Python scripts:

• The first script will generate a second-order polynomial and three user-provided keys as well as the secret value. This can just be a simple local script you run which prints this stuff out. In real-life we'd take care to not publically share its output (since both you and your partner are seeing all the points, and therefore have enough information to separately each specify the secret), but for our toy example today this is fine.
• The second script will be for use on the server and handle the incoming POST requests and GET requests. Remember that your server-side implementation will need to be able to remember who has POSTed their secret shard within the last twenty seconds. Any sort of "remembering" like this will need a database, so make sure you generate a structure for that. Your system must use the POST request body to transfer information, not the POST request query arguments.
• You will need to solve for a polynomial given several points. There are several ways to do that, but we've already actually done one of these previously. Not doing this (and just waiting for three shards to be submitted without checking) voids the whole point of doing this exercise!

Checkoff 2:
Discuss Shamir's Secret Sharing Scheme and a general idea of how to implement the assignment.

Get your system working. Choose a GIF to display in the browser (via a simple GET) when all required users have submitted their shards (via a POST using the body of the POST) within the last twenty seconds. In order to return a GIF, you need to just return some HTML in your Python!


return """ <iframe src="https://giphy.com/embed/sbG9nMttKvPYA" width="480" height="266" frameBorder="0" class="giphy-embed" allowFullScreen></iframe><p><a href="https://giphy.com/gifs/hacf-gordon-clark-good-boy-gordo-sbG9nMttKvPYA">via GIPHY</a></p>"""

will return the GIF below when visited in a browser (from the best television show of the last forty years, Halt and Catch Fire). You should pick a different GIF (that is appropriate).

via GIPHY

Checkoff 3:
Demonstrate your working SSSS where three separate users must have logged in within the last twenty seconds in order for a GIF to be available in the browser.

Now team up with another team and demonstrate any m-1 of m SSSS where m is the number of students in your overall group. This should be set up where if you have four total users, any three are needed to securely release the GIF for viewing (again for only that twenty-second window when the shards had all been submitted.)

Checkoff 4:
Demonstrate your m-1 of m system. What are some major issues with your implementation from a security standpoint that you can think of?

This page was last updated on Tuesday April 02, 2019 at 10:31:22 AM (revision 439c298).