Error tolerant password from quiztest

Question

I want to use gpg with a symmetric password for encrypting a message. How to do this is explained here in the forum itself, but also in the internet. I'm aware that a symmetric key has the general problem of key exchange. A possible solution is to make a quiz test. The idea is to take 20 questions from an exam test, which can be answered with a, b, c or d. And this will be the password for encrypting the message. The entropy of the password is 4^20, which is high enough for a little fun exam.

The problem is, that the PGP software needs a 100% correct password. But in reality no student will be able to answer all questions correct. What i need is something which is a bit error tolerant. What is the algorithm to generate a password, which is also correct if only 90% of the questions are answered correct? Can this be done with some kind of hash-function or salt?

The idea from educational perspective is, that the students are first attending a quiz, and if they have done all right, they can read the secret message which contains music. Only the student which were successful can hear the song.

Answer 1

One way you could do this is with Shamir's secret sharing. Your song data would be prefixed with a known-good value (e.g. "RIGHTKEY") then encrypted with a symmetric cipher such as AES-CTR-128, and the shared secret S would be the AES key converted into a 128-bit integer.

Using Shamir's you would generate your 20 points on the curve, each in the form [x, f(x)]. Assign each point to a question, adding the answer's correct value (mapping a,b,c,d to 1,2,3,4) to the f(x) part, such that you get points in the form [x, f(x)+q] where q is the correct answer index 1, 2, 3, or 4. If a student were to look at the page source code, they would only see a point [x, y] and would not know what the value of f(x) or q is.

Upon submission of the completed answer sheet, you go through each answer and subtract the given answer's index from the second part of the point. If the answer is correct then their value will have been subtracted back to the original value of f(x). If enough of their answers are correct, they will have enough points [x, f(x)] to decrypt the secret. As some of their answers may be wrong, you can't just use all of the points. Instead, you iterate through each possible combination of k answers and attempt to compute the shared secret, then use the resulting secret to decrypt the first 8 bytes of the encrypted song and see if the data is "RIGHTKEY". If so, you know you got the right key. If not, you move onto the next iteration and try again. For a value of k=16 with 20 questions, you only need to do 4845 attempts at most; for enough correct answers this will be much faster as you are likely to find a correct combination early on in the decryption process.

Against a naive bruteforce approach, the system has a security bound of 4^k for a threshold of k correct answers. The primary weakness is that if a test-taker is absolutely sure of some answers but doesn't know others, they can use the ones they know are correct to reduce the brute-force space significantly. Ultimately, however, this is an inherent problem for any client-side validation approach using thresholds. The only way to avoid this is to have the exam validated on the server-side against a set of known answers.

Answer 2

The easiest solution that comes to mind is to use an error-correcting code as part of your quiz output. A well-known variant is Hamming codes. You'd use Hamming(20,15) for that.

An alternative option that could be more intuitive for manual implementation by the students is a rectangular code. You could arrange the 20 questions in a somewhat improper 5x4 grid for the check, or extend the quiz to 24 questions for a proper 5x5-1 grid.

In both cases, some questions become essentially optional if you were perfect on the "data bits". I can't suggest any simple and scalable way around that (to ensure 1 and only 1 error is correctable), other than using a black box checking program, though that doesn't mean one doesn't exist.