I have a question regarding pitfalls of using only encryption.

Suppose Bob and Alice want to flip a coin over a network. Alice proposes the following protocol.

  1. Alice randomly selects a value X ∈ {0,1}.
  2. Alice generates a 256-bit random symmetric key K.
  3. Using the AES cipher, Alice computes Y = E(X,R,K), where R consists of 255 randomly selected bits.
  4. Alice sends Y to Bob.
  5. Bob guesses a value Z ∈ {0,1} and tells Alice.
  6. Alice gives the key K to Bob who computes (X,R) = D(Y, K).
  7. If X = Z then Bob wins, otherwise Alice wins.

This protocol is insecure.

  • a. Explain how Alice can cheat.
  • b. Using a cryptographic hash function h, modify this protocol so that Alice can't cheat.

My guess is that Alice can repudiate the fact that she did not receive the value Z sent by Bob and hence does not provide the key. Can anyone suggest other ways in which Alice can cheat ?

  • 1
    $\begingroup$ "Alice can repudiate the fact that she did not receive the value Z" has one too much negation. We could say "Alice can repudiate the fact that she received Z, or that value of Z". But that's not the expected answer. Alice has another way to cheat that could convince you (before you find her technique) that she indeed won, even if she never invokes a transmission error. Recommendation: imagine you are Alice, and want to cheat. Note: "X∥R" (or "X,R" and "(X, R)" as there was before my edit) means bit X concatenated with R. $\endgroup$ – fgrieu Sep 26 '20 at 9:19
  • $\begingroup$ my bad on the part X||R its actually (X,R) since K is used to decrypt the ciphertext $\endgroup$ – BishkekPasha Sep 26 '20 at 15:13
  • $\begingroup$ If the exercise is given as it stands after your new edit then it is uses a non-strandard notation, and is borderline wrong. At step 3 we are left to insert parenthesis as appropriate in "E(X,R,K)"; and, independently, wonder if we should read "127" where there is "255", or choose a mode of operation for AES, which Alice and Bob must agree on. New recommendation: first decide and understand what Alice is supposed to do, then apply the previous recommendation. $\endgroup$ – fgrieu Sep 26 '20 at 17:58
  • $\begingroup$ Hint: (assuming $E$ is AES-GCM); given two keys $K_1, K_2$, it is possible to find a 256 bit message that would successfully decrypt (to two different random messages) with those two keys (assuming a fixed well-known nonce and fixed or no AAD). $\endgroup$ – poncho Sep 26 '20 at 19:07
  • $\begingroup$ @poncho: you are adding an interesting twist with authenticated encryption not being usable as commitment. But the question has using only encryption. And it's hard enough to make sense out of the original copy/paste and find what the question should have been. $\endgroup$ – fgrieu Sep 26 '20 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.