More Stuff to Break

On this page, you’ll find food for thoughts, more exercises about the protocol we studied. It’s optional but I hope it can help you get an even better understanding of this practical session.

About Honesty

I must tell you the truth, the threat model we defined in the first exercise is very fragile. We suppose that Alice and Bob are honest. Imagine that you were actually playing the hypothetical clue hunting game with friends. There’s a big prize to win. Do you really think they would be honest? Do you think you could trust them?

Update your threat model: consider Alice and/or Bob not being honest. What happens? What could they do?

Tip

Want a hint?

If Alice lies, the protocol is completely and utterly broken. Without even playing with equations, she could know every clues from Bob.

If they both lie, though…

Reusing \(r\)

What happens if Alice and Bob reuse keys (as we already tried) and if, in addition, Bob always use the same \(r\)?

Draw a new diagram with new equations and see for yourself.

Y2K: Why Two Keys?

RAM is not cheap nowadays¹. What happens if we spare 16 bytes by using only one key, instead of two? In other words, what happens if \(k1 = k2\)?

Draw a new diagram!

A for-loop Can Leak Information Too

Try to change the protocol’s loop. Let’s say we want to optimize it, that Alice continues to the next clue when she finds a shared clue. Something like:

for alice_room in alice_rooms {
    for bob_room in bob_rooms {
        let same_room = protocol(k1, k2, alice_room, bob_room);
        if same_room {
            // We don't need to check Bob's other rooms, right?
            // They will be different anyway, we can skip to the next one.
            continue;
        }
    }
}

It leaks information to the Server. Why? Draw diagrams with example values.

About Randomness

Until now, we suppose Alice and Bob’s shared secret is generated randomly using a uniform distribution. We also assume that \(r\) is a uniform random variable. This is a critical requirement in cryptography. Indeed, think about it: what would happen if the keys were predictable?

Rewrite it in Rust

Try to implement the protocol in Rust.

You’ll need to use crates (the Rust term for libraries):

$ cargo new crypto-game
$ cd crypto-game
$ cargo add rand sha2

To help you, here’s a starting point (because the sha2 crate has an horrendous API):

use sha2::{Digest, Sha256};

fn main() {
    // To initialize keys:
    let secret = b"Hello, World!";
    let hash = ...;
    let (k1, k2) = ...;

    // To get a uniformly-distributed random value:
    let random: u128 = rand::random();

    // To add/subtract/multiply modulo 128:
    let a: u128 = 1;
    let b: u128 = 0xffffffff_ffffffff_ffffffff_ffffffff;
    let sum = a.wrapping_add(b);
    let difference = a.wrapping_sub(b);
    let product = a.wrapping_mul(b);
}

fn sha256(bytes: &[u8]) -> [u8; 32] {
    Sha256::digest(secret).into()
}

fn u256_to_u128x2(bytes: [u8; 32]) -> (u128, u128) {
    // `unwrap` is safe here because we're sure our slices are 16-bytes long.
    let a = u128::from_le_bytes(bytes[0..16].try_into().unwrap());
    let b = u128::from_le_bytes(bytes[16..32].try_into().unwrap());
    (a, b)
}

Does it work? Nice. Now, try to implement the practical attack on the broken version of the protocol!

Tip

Want a hint to implement the attack?

There is an available JavaScript implementation somewhere, don’t look far…

An Even More Precise Attack

We could improve the practical attack against the key-reusing protocol. Indeed, now we’re only computing deltas from Alice. In reality, we could compute deltas using Bob’s clues as well and cross check them.

You could adapt your Rust implementation too.

1. This was written in 2026, everyone talks about this AI stuff. ↩