Lab 08a: Secret Sharing

Spring 2020

The questions below are due on Sunday April 05, 2020; 11:59:00 PM.
 
Partners: You have not yet been assigned a partner for this lab.
You are not logged in.

If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.csail.mit.edu) to authenticate, and then you will be redirected back to this page.
A Python Error Occurred:

Error on line 7 of Python tag (line 8 of source):
    kerberos = cs_user_info['username']

KeyError: 'username'

Tearing up Secrets into Shards

Goals:Today you'll get some exposure to git in advance of the final project and then implement a secret sharing scheme between you and some fake people. This lab will also serve as a review/more practice with writing some server side scripts that are a bit more time-sensitive than ones we've previously been messing with.

This lab can be done on your own, just like in Lab06A. You can either get a live-checkoff with a staff member over video chat at the end (one large checkoff), or submit a writeup report like you did for Lab06A, which will be graded witha bit of delay.

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 setting up a repo on 608dev-2.net) 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. This could be very beneficial for team-based work.

A central repository and version control allows us to relatively safetly collaborate on files/projects without fear of deleting others work

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. They are now owned by Microsoft and probably steal your data. You can use git without Github (and many do!). You cannot use Github without git. For lab we'll create a git repo on the server, then clone it locally on our computer. You'll then add some files locally, commit them, then push them up to the server. Real easy.

First you'll need to get git (lol) on your computer. Links to do that for the three operating systems are below (Many 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. It is basically the same as what we've been doing on the server/interfacing with it so far, so it shouldn't be too foreign to you!

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 directory
  • 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?

We'll be working quite a bit on the server/shell today. Make sure to go back to Exercise 03 if you need a refresher on that stuff.

2) Create a Repo on the Server

NOTE your server login password is

A Python Error Occurred:

Error on line 1 of Python tag (line 59 of source):
    print('%s' % (cs_user_logos[kerberos],))

NameError: name 'kerberos' is not defined

in case you forgot.

OK let's first ssh into our server and make a git repo. In your home directory make a folder (mkdir) called lab08a. Move into that folder and then run the command:

touch README.md

What this will do is create a file inside lab08a that is called README.md with nothing in it. Cool. If you run ls you should now see your empty directory has README.md in it.

Now, next, run the following command while in lab08a:

git init

Some stuff will fly by but it should look like the following (don't worry about the templates not being found):

<div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 77 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>@608dev2:~/lab08a$ git init warning: templates not found /usr/share/git-core/templates Initialized empty Git repository in /home/<div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 79 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>/lab08a/.git/

Cool, you've just created a git repository. The repository is empty on creation by default, however. Let's add that file we made. Run the following command:

git add README.md

This adds the file to the repo. Now let's commit this file into the repo. To do this we'll use the git commit command, but we'll also provide a message while we're doing it which notes what's happening during this commit so that if we need to look at our history in the future, we'll be able to know at a high level what we were doing here. An inline message is done with a -m 'MESSAGE' tacked on to the command. Finally, let's specify that we're commiting the changes that we've implemented with README.md, namely its creation.

All together this means type:

git commit -m 'adding in README.md' README.md

When you run this you'll get something like the following:

<div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 98 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>@608dev2:~/lab08a$ git commit -m 'bringing in README.md' README.md [master (root-commit) 44e729b] bringing in README.md Committer: 6.08 Student <<div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 100 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>@608dev2.608dev-2.net> Your name and email address were configured automatically based on your username and hostname. Please check that they are accurate. You can suppress this message by setting them explicitly. Run the following command and follow the instructions in your editor to edit your configuration file: git config --global --edit After doing this, you may fix the identity used for this commit with: git commit --amend --reset-author 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 README.md

You may also get a message about your email not being auto-detected looking like this:

*** Please tell me who you are.

Run

  git config --global user.email "you@example.com"
  git config --global user.name "Your Name"

to set your account's default identity.
Omit --global to set the identity only in this repository.

fatal: unable to auto-detect email address

If you do, go ahead and follow the instructions that it prompts you with:

  git config --global user.email "you@example.com"

and then:

  git config --global user.name "Your Name"

where you should replace the content in quotes with stuff that is relevant to you.

If you'd like to set your email you can, but the message above isn't going to prevent other stuff from working.

Cool you've now successfully set up a git repository on the server! Before we leave the server, let's check on the size of that README.md file. It should be 0 since there's nothing in it. Run the following command:

ls -s README.md

You should get back:

0 README.md

which confirms the size is 0. Good.

Finally we need to change one more thing on our repo. Inside of your repo if you do ls, you'll see just README.md. This isn't the whole story. If you type:

ls -a

you'll see several other things show up:

.  ..  .git  README.md

This is everything that's in the folder. . means the current directory. .. means the parent directory (these two are always there). We can see README.md, but the other one is .git. Files in *Nix systems that start with a period are "hidden" files. When you turned this folder into a git repository, what git did was set up a hidden folder with all the appropriate settings stored in it. If you move into that folder with cd .git and then run ls you'll get:

COMMIT_EDITMSG  config  HEAD  index  logs  objects  refs

These are all the settings and history and important information about your repo. When you run git commands in it, they will be using/modifying information stored in there.

We need to change one of the files in this folder, the config file. Onto your local machine, download this config file HERE (don't rename it. Save it just as "config").

Do not save the file as "config.txt" or anything with an extension. It should just be "config". If it automatically sets it something with an extension (I'm looking at you, Windows kids), you need to change it

scp it up to your repo, and replace the current config file. For example, if your saved config in you home directory on your local computer you could do:

scp ~/config <div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 186 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>@608dev-2.net:~/lab08a/.git/config

You could also just scp it into your home directory on the server, and then move it (mv) it manually to where it needs to go.

Make sure you do the last step above where you replace config. Failure to do this will lead to confusing results later.

3) Clone the Repo

Now let's open up a new terminal/shell local on your computer. 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_SERVER name_youd_like

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

Specifically, if you put the files where you were instructed to above, you'd do:

git clone <div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 206 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>@608dev-2.net:~/lab08a ~/lab08a_local

It will prompt you for your password, and once that's entered, it will clone! If you don't specify a name for the local copy, git will create a directory with the same name as the remote repository. As typed above, this will create a local copy of the repo called lab08a_local in the home directory.

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

cd lab08a_local

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, !Word). When you are done, save it.

Then in the terminal/shell enter:

git status

You will get back something like:

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)

	modified:   README.md

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

There's some helpful instruction messages, but of particular note is that git is telling us we have modified README.md. Let's solidify these changes by commiting them. To do that type:

git commit -m 'modifying README' README.md

It'll say something like:

[master 375e910] editing README
 1 file changed, 1 insertion(+)

If you now check the status again you'll see:

On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)
nothing to commit, working tree clean

This is essentially saying that we've made some changes and commited them locally which are not yet reflected on our remote server (the origin/master). Let's actually move them up there. To do that we'll run push. Specifically do:

git push origin master

In response you'll see some stuff fly by like:

Counting objects: 3, done.
Writing objects: 100% (3/3), 260 bytes | 0 bytes/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To 608dev-2.net:~/lab08a
   44e729b..375e910  master -> master

which is a success message.

If you now jump back into you ssh session on the server and type ls -s README.md you should see something like (note you may not have an 8...the number there will be based on the size of text you put into the file!)

8 README.md

This is showing us that README.md has now increased in size from before. Awesome.

3.1) Add in a File

We've edited a file that was already there and saw evidence that our remote change was successfully brought into the live repo on the server.

Let's create a new file from scratch remotely, add it, commit it, then push it up to the server. Move back onto your local computer. Inside of lab08a_local create a new python file called lab08a.py. Give it a simple request_handler function like so:

def request_handler(request):
  return "Hello, there!"

Returning to your local shell, we need to add that file to your local repo. To do this run:

git add lab08a.py

Then commit that new file:

git commit -m 'adding in a starter file for lab08a.py' lab08a.py

Then push to your master repo using the appropriate command. Returning to the server, and you should now see that a file called lab08a.py lives there! Not only that, visiting http://608dev-2.net/sandbox/sc/

A Python Error Occurred:

Error on line 1 of Python tag (line 321 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined

/lab08a/lab08a.py shows that the file is working and live!

Every time you make a change, or a series of changes, you can do it locally. And then commit and push them! Where it gets really cool is that all of your changes are saved (if you commit often), so that if you ruin your code later on, you can always move back to a prior commit to get working code again. (we'll add a brief note about this in the future for reference.)

3.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)

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

When done, onto the next part!

4) Secret Sharing

In exercises this week we look 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

With things like the Caesar or Vigenere Cipher (and more advanced schemes), our goal is to allow two parties, here koala and cat, to communicate in a way that is largely safe from outsiders (here robot) listening in on.

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:

In secret sharing, we break the secret up into portions (called shards) such that each user has a part of the secret and only when a sufficient number of shards are combined is the secret able to be determined. As a result no single-user has the capability of knowing the full-secret or causing an action on their own that requires the full secret, but still has a capability of controlling if the secret is used/shared.

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

In some secret sharing we can also design it so that you only need consensus of a certain number of users. For example whereas in the last figure, koala, dog, smoking cow, and cat all needed to provide their keys for the system to work, in this situation only two of the four are needed for the same thing.

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

A simple line (assume it is a true line that goes off to infinity...not a line segment).

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.

Using the y-intercept of our line as our secret value we can split this information among two parties

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:

Using different points on the line will give the same result (so long as you don't provide the value when x=0)

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:

Using the y-intercept of our line as our secret value we can split this information among many parties...and only two need to provide their shard.

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).

Using the y-intercept of our quadratic as our secret value we can split this information among at a minimum three parties

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:

We can now distribute three shards to users and only when all three are recombined, will things work out.

We can use three different shards as well.

In this situation we distributed four shards to four separate entities. Because they are from a quadratic, only three are needed to determine the secret, and thus our system has a bit of redundancy in it, which could be desirable.

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 party, 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 a real-life implementation, they usually use much higher-dimension geometries/polynomials over finite fields, 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?

5) Implementation

So now it is time to implement a version of SSSS. 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 the ESP32 lab kit and two spoofed users via POSTman) submit their shards and usernames within a 30 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.

You're going to need to fit a polynomial for this assignment. May we suggest numpy? Use the internet to look up how to fit a polynomial using numpy.

Again, to reiterate and restate what you must do:

  • If any three valid users submit three valid shards within a 30 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 30 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 30 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 thirty 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. Do not put it in the query arguments. Body. 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).

Details of your implementation are up to you. However, you will 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 thirty 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_writeup>Briefly discuss Shamir's Secret Sharing Scheme and a general idea of how to implement the assignment </checkoff_writeup>

Design a system so that three separate users need to submit POST requests with their correct secret shard within a 30 second window to enable the viewing of a GIF (of your choosing) when performing a GET request.

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 thirty 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_writeup>Demonstrate your working SSSS where three separate users must have logged in within the last thirty seconds in order for a GIF to be available in the browser. </checkoff_writeup>

<checkoff_writeup>Demonstrate in a short video (~30 seconds) your system performing the proper secret sharing scheme. Describe how your code (both the ESP32 and the server code) works and include it in your writeup. Make sure you describe what you did. Don't just dump it into the document. Make sure to specifically address the following things:

  • How your system ensures enough shards have been submitted
  • How your system gets its key from the points
  • How the system handles a bad shar
</checkoff_writeup>

Upload your report below when completed.

Even if you're getting an in-video checkoff submit something below so to code knows to grade it.

Submit your writeup here: No file selected