University of Virginia, Department of Computer ScienceCS588: Cryptology - Principles and Applications, Fall 2001 |

Matthew Mah discovered a serious problem with the annonymous tallying protocol:Anonymous Tallying Vulnerability Matthew Mah Here is my description of the confidentiality vulnerability in the given solution for Anonymous Tallying. We will use the example given in the solutions to show how Fred can figure out whether Alice has read the paper. He can do this by performing 2n modular exponentiations with appended strings, where n is the number of students in the class. 1. Fred receives EKAF [ EKUF ["send to: Holly" | EKUH ["send to: Cathy" | EKUC ["Here it is:" | 1 | RA]]]] 2. Fred has EKAF and EKUF, and thus he also knows EKUH ["send to: Cathy" | EKUC ["Here it is:" | 1 | RA]]. 3. Fred notes each of the n final responses rj|Rj that are written on the board and the person who wrote that response Wj. Here rj is the bit indicating whether the original sender read the paper and Rj is a random string. 4. Fred tries to generate the message he passes to Holly from the final results on the board. For each final response on the board rj|Rj, Fred generates mj = "EKUH [send to: $(Wj)" | EKUj ["Here it is:" | rj | Rj]]. Fred knows EKUj and EKUH. He knows EKUj because he saw who wrote the final response on the board, and he knows EKUH because he knows whom he passed his message to (Holly). He knows the formatting of the messages sent and so also knows what strings to append. This gives Fred n different texts, one for each student in the class. This step requires 2 modular exponentiations per final response on the board or 2n total modular exponentiations. 5. Fred compares each of these to his own decrypted message from #2. Exactly one will match, and Fred will thus know that Alice sent rj|Rj, and know whether Alice claims to have read the paper. We have shown in generality that the first student (Fred) receiving from the information origin (Alice) can determine whether Alice has read the paper by performing 2n modular exponentiations. This is certainly feasible to calculate since the protocol requires 3n modular exponentiations for encryption and 3n modular exponentiations for decryption. Initially Fred does not need to know where the message he relays to Holly ends up. He can calculate it based upon the final results placed on the board. Discovering whether Alice has read the paper does not require breaking RSA or the symmetric cipher. For onion routes of length L, a similar process for Fred would require O(n ^ (L-2)) modular exponentiations, where the length of the above route is 3. For each additional person in the onion route, Fred needs to encrypt each result from #4 with one additional public key with appropriate appended string designating the receiver. He does not know which keys to use or which final result to use and thus must perform n modular exponentiations for each result from #4. This gives n*2n = 2n^2 for onion routes of length 4. We can fix this problem by making the following simple modification. Alice includes an additional random string RA into her message. This random string can be of fixed length. EKAF [ EKUF ["send to: Holly" | EKUH ["send to: Cathy" | EKUC ["Here it is:" | 1 | RA|RA]]]] When Cathy receives the final message, she writes only 1|RA on the board. Cathy knows how many characters to leave out because the random string is of fixed length. Now Fred cannot reconstruct the message he sends Holly from any of the final responses written on the board.

University of Virginia Department of Computer Science CS 588: Cryptology - Principles and Applications |
David Evansevans@virginia.edu |