Crypto in the classroom: digital signatures for homework

If you don’t know, I’m a graduate student at the University of Utah, which means I make a living my teaching classes. Recently a student charged that I lost a good deal of her homework. We wound up in a “he-said/she-said” situation where ultimately the dean concluded that we need to raise her grade by a letter under the assumption that I really was up to shenanigans (we ultimately gave her 100% credit in the “homework” column in the grade book, raising her grade from F to D). Not a pleasant situation: aside from a track record of strong teaching evaluations, there was nothing to defend my reputation.

Experienced teachers know that claims of “lost” work are frequent. If we want to be objective about this (and we do), the claims need to be taken seriously, since lost things rarely leave a trail. All we have when analyzing such claims is the following:

  • The missing work never seems to turn up. Not after a week, a month, a semester, a year, or ever.
  • If a person rarely finds that they misplace his own belongings, it’s hard to accept that he is misplacing student work (assuming they treat student work with a reasonable amount of care, as we typically do, given how terrible it would be to lose it!)
  • These claims never seem to come from students who are doing well on exams; they tend to come from students who are backed into a corner, grade-wise.

Of course, it is entirely conceivable that these claims are occasionally correct, and it would be terrible to allow such mistakes — our mistakes — to adversely effect our students.

Last Spring was the only time a student has accused me of losing their work. It was a lousy situation that I have no intention of ever repeating. So when I was assigned to teach a half-term class this summer, I decided it was time to try something new. I’ve recently finished teaching that class; here’s what I did.

The idea

A digital signature is a cryptographic technique to verify that a document was authored by a particular person. They are frequently used in situations where someone might later claim to have not authored a document in order to weasel out of a precarious situation. It is usually the recipient of the document who insists that a digital signature be used.

Digital signatures can be used in other situations where authenticity is important. For instance, concert tickets can be printed with a digital signature that validates they were printed by the ticketing agent. The signature on each ticket will need to be different, but this isn’t hard to arrange. If the cryptography is sound, no one will be able to forge the signature, hence no one should be able to print a phony ticket.

This summer I experimented with using digital signatures to provide students with a way to prove that they’ve turned an assignment in. Every time I made an assignment I produced a corresponding batch of digitally-signed receipts. One receipt per student per assignment. I wrote a program to automate this: it takes a list of students and the name of the assignment and produces a PDF file of receipts. I’d then print the PDF, take it to the cutting board, and produce an alphabetized stack of receipts for each assignment (the program was clever enough to sort the receipts on the printed page in such a way that the alphabetizing didn’t require me to sort through the cut up pages).

I then instituted a policy: I won’t take your homework unless you take your receipt. Because the receipts were sorted this didn’t take long to do (though to save class time, I only accept homework before and after class, or during problem sessions).

I’d then periodically create printed grade reports for each individual (again I had a program that automated this, taking data from my spreadsheet and turning it into a PDF with one page per student). This allowed students to check whether or not I was giving them credit for their work. At the end of the term, I gave them one last report that showed the grade I was going to submit for them. No one can claim that I was withholding information.

The wonderful thing about this system is that it gives the students proper recourse: if it looks like I lost an assignment, the receipt proves they are right, and I’ll give them full credit. Because the receipts are digitally-signed, they cannot be forged, so there’s no funny business to be had by any bad apples.

Reception

Naturally I described my plan to the bosses in the math department. My department chair conjectured that no one on earth had tried this before. The associate chair laughed at the lengths I was going through. My peers suspected that the students would find this system confusing, annoying, and unnecessary.

When I implemented this system the results were fantastic. I don’t believe anyone in class understood how the digital signatures worked, but they didn’t need to: all they had to know is that the receipts give them recourse if I lose their work. And they loved it. Why wouldn’t they? It was apparent that I was doing extra work to expose myself for their sake (nevermind that I was originally motivated to try this to avoid getting in hot water myself).

Contrary to initial predictions that I would be mired down in extra paperwork, this process did not take much time on my end. Once I had the programs written to automate the work (which took an afternoon) the time investment was nearly zero. The most time consuming part was passing out the receipts as students turned in their work, but since this was taking place during problem sessions, it didn’t actually increase my working time.

For me the most interesting thing is that I did apparently lose someone’s assignment! I have no clue how, and part of me still hasn’t accepted this, but the evidence suggests that it happened. I gave someone a grade report, it said they were missing an assignment, but sure enough they had a receipt. They called me on it in front of the class, and when I reaffirmed my promise to give them credit, a couple people in the class praised me. The receipt system actually took my mistake and turned it into an asset. Incredible.

Edit: this is what a sample of my receipt-PDF looks like (here shown with just a small number of hypothetical students). Notice how it’s sorted — makes it very easy to just go to the chopping board, stack the pages, make 4 cuts, and concatenate the little stacks.

How I did it

There’s a considerable about of machinery that goes into such a scheme. If you’re interested in implementing something like this, and have a good familiarity with computing, you can follow these steps to get rolling. For all of this I’m using openssl, which is installed by default on my Mac, and also on every Linux distribution I’ve ever used. I’ll show how this is done using a test receipt.

Step 1: Create the key files. Create a directory to do your work in. Within this directory, issue the following two commands:


$ openssl genrsa -out private.pem 1024
$ openssl rsa -in private.pem -out public.pem -outform PEM -pubout

This will create a public and a private file, so-named by openssl. The public file can be put on your website, or included in your syllabus, allowing a 3rd party to arbitrate any disputes that may arise. The private file must be kept private, as it is the key to signing the receipts.

Step 2: Create a test receipt to work with. Later you’ll do this step for each student, for each assignment (consider using a script to do this for you!). Here’s my test receipt:


$ cat Test-receipt.txt
FAKE, STUDENT ASSIGNMENT 0001

Step 3: Sign the receipt, putting the output into base64 (this will allow you to print the signed receipt so you can give it to your student in writing)


$ openssl rsautl -sign -inkey private.pem -in Test-receipt.txt |
openssl enc -base64 -out Test-receipt.sig

You can examine the output:


$ cat Test-receipt.sig
hRqaY5LAns3CrzueaMXirehihYCn6TI6K4Luwo9T6F4JVMXiBb10wSN4fDLnM12m
NICQihiAt5prlqDxjwqpr2J4tPMmQZpXr8dpFKdyQgxn6IesLiEm9HIVjYUELRMW
kzxv86+8oVl6qQny+kMVWo3w7pI/JTTnHP3yLl1NJJw=

When you go to print your student’s receipt, include both the contents of the receipt (in my case, Test-receipt.txt) as well as this gibberish.

Step 4: Make sure you know how to verify a receipt! This isn’t so bad. If someone gives you their receipt, you enter the gibberish into a file (in this case, Test-receipt.sig) and execute the following:


$ cat Test-receipt.sig | openssl enc -base64 -d | openssl rsautl -verify
-pubin -inkey public.pem
FAKE, STUDENT ASSIGNMENT 0001

If the signature is correct (that is, not entered wrongly, nor an invalid forgery) you should see the receipt in plain text, as demonstrated here.

As an example, if I modify even a single letter in Test-receipt.sig, I’ll wind up with something that makes no sense, or more likely, I’ll get an error. For instance, if I replace the first letter (a lower-case h) with an upper case H, I get the following:


$ cat Test-receipt.sig-error | openssl enc -base64 -d | openssl rsautl -verify -pubin -inkey public.pem
RSA operation error
286:error:0407006A:rsa routines:RSA_padding_check_PKCS1_type_1:block type is not 01:/SourceCache/OpenSSL098/OpenSSL098-27/src/crypto/rsa/rsa_pk1.c:100:
286:error:04067072:rsa routines:RSA_EAY_PUBLIC_DECRYPT:padding check failed:/SourceCache/OpenSSL098/OpenSSL098-27/src/crypto/rsa/rsa_eay.c:697:

This will allow you to detect cheap forgeries.

Conclusions

This summer I ran this experiment with a class of 55 students, and in this setting, homework collection took about 15 minutes. It worked fantastically. In the Fall I’m teaching a group of 180. The turn-in time might make this plan infeasible for such a large group unless I can have my TA’s come to class to help collect work. I’ll definitely post my experience with this group in the comments to this post.

Advertisements
Leave a comment

29 Comments

  1. s/Crypo/Crypto/

    Also, very cool idea. I’m sending this to all my friends who teach classes as I know at least one who had a similar problem.

  2. oh no! Fixed the typo. …not a great typo to make :/

  3. Sean

     /  27 June, 2010

    Could you potentially use a barcode or something similar and a cameraphone to expediate checking the receipts? This would seem to me a far better(Although probably more involved) solution than having to type out the entire key into a sig file.

  4. Barcodes would be much faster, but in this system, the only time I need to manually enter any data is when I’m verifying the integrity of a receipt, and that only comes up when there’s a question about whether or not someone turned something in. Certainly if this came up more frequently I would implement a more serious technology (such as barcodes), but it seems rare enough that the need isn’t there.

  5. Chris H.

     /  27 June, 2010

    Couldn’t you just have the students email their homework to you?

  6. Brian

     /  27 June, 2010

    The only problem with a barcode is that there is a lack of integrity. Barcodes can be reverse engineered, I don’t see that with this system since he controls the private key to decrypt.

  7. I’m a very technically capable person, so in most situations I greatly prefer email to hard copies.
    But when it comes to students, I actually try to discourage them from emailing me their work. It’s hard to succinctly articulate why this is, but here goes:
    1. Someone always has some technical problem. I’ve had (teenage!) students claim they couldn’t figure out how to use YouTube. I’ve had people claim their laptop “crashed” (whatever that means). I’ve had people insist they sent it and it “must have gotten lost.” Perhaps for infrequent assignments email would work well, but when there’s lots of students and lots of work, I’ve found it to be a can of worms.

    2. If they want to email it to me, they either need to type it up or scan it. A few students will try and learn LaTeX for typing up their math, but most will fumble around with Word, and when they can’t figure out how to format something, they’ll invent some kind of crazy notation. It’s a real mess.

    And those with scanners sure do like sending 5mb JPEGs.

    These aren’t fundamental problems with email, of course. Reflecting on the question, it’s actually a shame that using email to collect work isn’t easier. I just haven’t had good luck with it on a classroom-scale.

  8. A dropbox is probably a better way to do this.

  9. How does dropbox improve on email? I can’t see how it improves on any of the problems mentioned above.

  10. Nice idea! I’m now considering implementing a modified form of this for my courses next year.

    I’ve seen dropbox-type systems set up before, allowing uploads before a certain time, but inevitably it gives a devious student an out to claim that he did upload it but the system was down/something went wrong/computers are the devil. The personal exchange of receipt and homework is what makes this system shine, to me.

  11. About the dropbox: I have only experience with the one I built, but it’s much better than email.

    1. Everything uploaded is tagged to a course and student. It gets a time stamp. You can insist that the student download it (after uploading) to make sure it’s the right file and it’s not corrupted, AND that they print off a screen shot as a receipt.

    2. It creates an archive of student work for later analysis.

    3. You can easily add features like uploading a response (I posted all graded work this way) or use a form-based rating system.

    4. It helps everyone be more organized. The student can find past work all in one spot, and no looking through email for submissions for anyone. And it’s accessible from the web.

    5. Since everything is electronic, everything is logged and trackable and backed up. If a student says they couldn’t log in, it will be in the httpd access log.

    6. It’s all automatic and virtually free.

    7. I used it to encourage use of digital media, like using Tex (lite) to submit homework.

    I guess the best proof that it’s useful is that it took off like a rocket at the college.

    With your receipt system, what do you do if they say they got a receipt but lost it?

  12. Brian

     /  28 June, 2010

    When I went to college, we used a ‘submit server’ and that was over 8 years ago. Apparently they are still using it and using it well: http://cs.fit.edu/~ryan/submit.html

    From what I remember, it also automated the process of checking for plagiarism as well. I’m sure if you asked them they would loan you a copy of the client and server.

  13. Kristie Walker

     /  28 June, 2010

    I work for an online university. We use a dropbox system (built into the course platform, eCollege). We use it because we have to, but having taught in a physical classroom, I much prefer Tim’s way. I have indeed seen every one of the issues he presented and am told that we have to give students the benefit of the doubt.

    In one case, a student didn’t turn in a rather large assignment from the second week of the course (worth 10% of the points available in the course). The week she turned in her final paper, she “noticed” that I “hadn’t given her credit” for that assignment and wanted to know why. Ultimately it was concluded that the file “must have gotten lost somewhere” and I needed to give her the grade she’d earned. Strangely, this bumped her from failing to passing. At the very end of the course. Even though she’d had a number of weeks to “notice” (all grading is live and online, meaning that as soon as I enter a grade, the student can see it) that I’d “forgotten” to grade her work.

    In any event, given the notation challenges that he mentioned above, I can see additional reasoning there for students not to submit electronically.

  14. Kristie – exactly. The real challenge is not only to make a technologically capable technically verifiable system, but also to as much as possible put the onus on the student to produce proof that the assignment was turned in – e.g. the receipt. In any case of doubt, administrations will favor the student’s story, especially if they make a good fuss. While server logs and digital evidence is 100% convincing to me, it often seems far too ethereal to many administrators, decreasing its utility in these situations.

  15. luysii

     /  28 June, 2010

    Yes, this happens. For an example with more malignant possibilities see http://luysii.wordpress.com/2010/05/26/a-responsibility-you-didnt-know-you-had/

  16. Great system!
    If I were in your shoes, though, I wouldn’t type anything… I’d just scan the receipt and OCR it. Works just as well as barcodes, at least, in this case.

  17. Kristie Walker

     /  28 June, 2010

    @Constantine: Precisely. I don’t see a decrease in utility, though; it’s more of a complete negation, at least in the case of students who know how to work the system.

  18. @Alex Indeed. Although there’s a secret extra option I haven’t mentioned: just re-generate the receipt on my laptop, then compare that most of it looks correct. This process errors in the favor of theoretically allowing a forgery to get through, but such events are incredibly improbable, and it is decidedly the fastest way to “verify.”

    @Constantine, @Kristie. As you’ve both identified, the challenge is to devise a system that the administration can understand and back up. I’m in the lucky situation of working in a math department at a large university, with a dean who himself started his career in mathematics. I’m going to guess that the level of support I received when I briefed the bosses on my plan would be unmatched in more typical circumstances.

  19. solrize

     /  30 June, 2010

    That doesn’t make sense. Why do you want public keys if you’re the only one verifying the signatures? Just use a 5-digit secret-key checksum instead of having to type all that base64 cruft. Or just assign a random number to each receipt and keep a private copy of the receipts. Again, 5 digits is probably enough and 8 digits is more than plenty.

    If you really need public keys, use the DSA algorithm so the signatures are just 320 bits long, a lot less typing.

  20. @solrize I used RSA because it has name recognition, and I felt that this would be important if I needed to rely on the higher ups for conflict resolution.

    Using randomly assigned numbers will not work. If a student attempts to forge a receipt, and guesses wrong, what’s to stop them from claiming I modified my private list of numbers? With the signing, provided that the public key is in the syllabus there is no chance of this problem.

    DSA keys are shorter, which would mean less typing. Definitely something to consider in the future.

  21. solrize

     /  30 June, 2010

    “Using randomly assigned numbers will not work. If a student attempts to forge a receipt, and guesses wrong, what’s to stop them from claiming I modified my private list of numbers?”

    Just give a copy of the private list to the higher ups at the beginning of the semester, so they can check it in the event of a later dispute.

  22. That could certainly work. It’d be enough to just email the listing to the bosses, provided they didn’t mind keeping the emails around in some folder in case they were needed. This sounds reasonable to me.

    Moving forward I’m going to continue using my current system, though. It’s already implemented, so absent a practical weakness in the system, I don’t see any value in modifying it. Though certainly this route may be of use to others who are interested in using receipts but don’t want to bother with a cryptographic approach.

    I do see another problem with the random numbers approach, though. Cryptographic signatures might be able to survive this problem (the jury is out) but random numbers don’t stand a chance (if we want to be practical about it):

    With any receipt system, a student could claim that I gave them a misprinted receipt (they could easily make this claim without alleging malice, since it’s conceivable that the script I wrote had a glitch).

    The only way around this problem is to make a point of allowing students to demand verification of correctness when they take the receipt. I always made the offer, but no one took me up on it, so this doesn’t really hold much weight in practice. Perhaps if students routinely took advantage of this, so that it was an accepted practice in the classroom, such claims would be harder to accept. I’m very interested in a practical, effective defense against this conundrum.

    Theoretically with a cryptographic signature this offer could have been effective. With a random number it could not, unless the boss was there with his copy of the list (I don’t see this as a practical solution).

  23. solrize

     /  1 July, 2010

    “It’d be enough to just email the listing to the bosses, provided they didn’t mind keeping the emails around in some folder in case they were needed.”

    That’s why they have secretaries ;-)

    “Although there’s a secret extra option I haven’t mentioned: just re-generate the receipt on my laptop, then compare that most of it looks correct.”

    That doesn’t work with openssl since the signature will incorporate random numbers, so you’ll get different signatures each time. You could just save private copies of the signatures on the receipts you give out, and compare those. You don’t have to check that most of it looks correct, since the contents will be essentially random. Comparing three or four characters from the middle of the signature is enough.

  24. It’s too bad that there’s no follow-up to this post.

    I’ve decided to implement this for my class. The “mis-printed receipt” problem troubles me, so I modified the approach which, academically and somewhat practically, partially solves the problem.

    I decided to use GnuPG instead of OpenSSL. This is so that, in principle, a student could verify a receipt without my intervention without having to download, install, and learn to use OpenSSL. (Most students use Windows, so this is a significant barrier.) I put the public key, which I sign with my main key, on the course web page.

    Even more, I use qrencode (http://fukuchi.org/works/qrencode/index.en.html) to encode the content of the receipt as a QR code (http://en.wikipedia.org/wiki/QR_code). A typical signature is about 400 characters, and therefore not too much fun to type in, but a decent scanner (like Qrafter on my iPhone 3GS) can scan the code at small size (~1 inch wide) with little trouble. A free iPhone app like OpenGP can check the signature, so I or a student can verify any signature on the spot in seconds.

    Ideally, a student verifies the signature as soon he receives it. The difference is largely academic as you said, since most students will not take you up on the offer nor will they ever check the code. Therefore, I worry about what might happen if a student claims the teacher lost the work and produces a fake receipt. Since the receipt has never been verified, there is no evidence (despite all precautions taken) that the receipt is simply faulty. Requiring a student to verify his receipt in a timely manner is, I am afraid, too great a burden.

    If it came down to an adjudication, what would happen? Here’s a hint: what if you actually produce a bum receipt? After all this work, you shouldn’t accept it. In practice, you probably have to verify every receipt you give out; if you say that you do so, and if it is possible for students to verify their own receipts, I think we have a system.

  25. Actually, I spoke a bit too soon — there is currently no app (to my knowledge) that can decrypt a signed message. (oPenGP can decrypt messages which are encrypted with public keys.) Therefore, for me at least, a laptop is still required somewhere in the equation. I believe that Android Privacy Guard (http://thialfihar.org/projects/apg/) can do this, though.

  26. did you check the claim to see if the signature on the receipt was valid?
    did anyone shoulder surf your workstation and copy receipts?
    did you leave your workstation unlocked?
    did you leave a copy of receipt at the printer too long?
    did you leave receipts visible to other students during study session?

    on the bright side you raised the bar enough not to get pwned by an F student

  27. @Clinton Curry Excellent! I’m glad someone’s picked up and improved on this idea. Please do advise on how it works out.

    I did, in fact, verify every receipt I gave out. I didn’t generate the receipts by hand; I had a script that took a list of students, and the name of the assignment, and produces a LaTeX file containing the receipts (there’s sample output of this in the post). That same script verified every receipt it generated, just as a simple sanity check.

    I agree that it is important for the students to be able to verify the receipts in a timely manner. Absent some technological aid — the use of QR codes is a very good start — there isn’t really a good way to do this. I’m no longer teaching (out in industry now), so it seems unlikely that I’ll work on any advancements. If you work out a good fix, please share!

    @cc When I tried this out, I wasn’t too worried about anyone subverting the system operationally. The purpose of the system was to give students a way to demonstrate that I had lost their work; for that to work, it had to be difficult for students to forge the signatures. Of course, if they can outright steal receipts, that’s just as bad.

    Let’s not lose sight of the real attack, though: if a student wants to cheat to get credit, it’s much, much simpler and safer to just copy someone else’s work.

    But, to answer your questions: yes, no, no, no, no. :)

  28. Came here to to suggest that an easier system may be to just hash the assignment information with a pre-selected salt at the beginning of the term. But after reading your comments I see that your method allows students to verify their own tickets, which is a really important aspect of the system that I think you might want to make clearer in your post. It takes the whole system to a new level :)

    It might be helpful to barcode- or QR-encode the signatures themselves, though, to make it even easier for students to verify their own tickets (who wants to type in all those characters?)
    It might also enhance some of the aesthetics :)

  29. Cryptographic techniques is very good technique used in digital signatures.So that proper validation of signatures will be check and this information will be hidden.And signatures will be check whether it is of the author only or not.Very good and proper safety technique.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: