Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
125 lines (110 sloc) 4.82 KB
---
layout: post
title: 'Crypto white elephant gift exchange puzzle'
permalink: '/crypto_white_elephant/'
tags: ['crypto', 'algorithm']
---
<div class="lead">
<p>Seven cryptographers would like to exchange presents with each other. They
are geographically located in different places, so they can't use a
traditional white elephant scheme (everyone brings a wrapped gift and puts it
on a table, people then draw names and take turn picking a gift).
</p>
<p>Can you figure out a cryptographically equivalent scheme?</p>
</div>
<p>Specifically, design a distributed algorithm where:
<ul>
<li>The algorithm results in every cryptographer knowing who they need
to get a present for (they can tailor their presents) but not knowing who is
getting them a present (there's a surprise factor).</li>
<li>Each cryptographer has a public/private key pair.</li>
<li>Each cryptographer knows the public key of the other six participants,
as well as their address (so they can mail the presents).</li>
</ul>
</p>
<pre> ___.-~"~-._ __....__
.' ` \ ~"~ ``-.
/` _ ) `\ `\
/` a) / | `\
:` / | \
&lt;`-._|` .-. ( / . `;\\
`-. `--'_.'-.;\___/' . . | \\
_ /:--` | / / .' \\
("\ /`/ | ' ' / :`;
`\'\_/`/ .\ /`~`=-.: / ``
`._.' /`\ | `\ /(
/ /\ | `Y / \
jgs / / \ | | /`\ \
/ | | | | | | |
/___| /___| /___| /__|
'""" '""" '""" '"""</pre>
<p>Happy holidays! I will post a solution here in a few weeks...</p>
<p><a href="" onclick="solution.style.display=''; return false">First solution</a></p>
<pre id="solution" style="display: none">
Every cryptographer starts with:
- priv_key (their private key)
- pub_key (their prublic key)
- pub_keys (the set of all the 7 cryptographer's keys)
And follows the following 5 steps:
1. Takes the set of public keys (including their own) and generate a token1:
token1 = sort(pub_keys).join('-');
2. Joins an irc channel named #token1, using tor to hide their identity.
3. Creates a temporary private/public key pair (temp_priv_key, temp_pub_key) and
publishes the public part:
- 1st message:
send(temp_pub_key)
The crytographers then wait for everyone else to publish their temporary
public key and stores the set (including their own) in temp_pub_keys.
4. Computes sorted_temp_pub_keys = sort(temp_pub_keys) and
token2 = sorted_temo_pub_keys.join('-'). Signs and sends token2 with their
public key. (It's a way of saying "I have participated in round 3" without
revealing their identity):
- 2nd message:
send(sign(msg=token2, key=priv_key))
The cryptographers then wait for everyone else to publish their second
message and validates that everyone has signed the same token2.
5. Reveals their identify to the person whose temporary public key comes right
after theirs in token2.
To do this, they publish their identify and a proof that they own the
temporary private key:
m = [sign(msg=token1, key=priv_key), sign(msg=token1, key=temp_priv_key)]
next_key = (sorted_temp_pub_keys.indexOf(temp_pub_key) + 1) % 7;
send(encrypt(msg=m, key=sorted_temp_pub_keys[next_key]))
The cryptographers will be able to decrypt one message each. They must
validate that the two signatures are correct and match the expected
temporary key.
Only the identity of the person they need to send a gift to is revealed.
Note:
Some interesting attacks to think of include: what happens if an evil
participant submits multiple temporary keys at step 3? What happens if a
participant is able to split the network in two halves?
</pre>
<p><a href="" onclick="solution2.style.display=''; return false">Another solution</a></p>
<div id="solution2" style="display: none">
<p><a href="https://www.facebook.com/roman">Roman</a> was kind enough to share his solution. His initial approach was somewhat different,
with a restart process. However, what happens if an evil participant doesn't send
the restart signal?</p>
<pre>
distRandom() {
x = random();
sendToAll(md5(x));
// send to friends x, later on if they want to verify that you did not cheat.
return sum(getRandomsFromOther())+x;
}
iter = 0;
x=distrRandom()%7;
sendToPerson(x, "iter => +1 present for you");
if (receiveMoreThenOne()) {
sendToAll("restart iter+1");
}
if (noRestart()) {
givePresent(x);
}
</pre>
<p>His initial approach left out how to map 'x' to an address, he followed up with:</p>
<pre>
SendToAll(random(), secretPublicKey())
SortListByRandom()
SendToNextAfterMe(nextSecretKey, "I am x, send me gift")
</pre>
</div>