This is the only chall I solo solved in DEFCON qualifiers 2026, but at least it’s DEFCON quals. Also it’s the only pure crypto chall. Unsurprisingly, the crypto specialist excels in crypto.
I began with reading the rust file to figure out how it works. On a high level, the user enters a “chat room” with 50 bots. 10 of the chat room members, including the user, are committee members. A secret is shared between the 10 committee members through Shamir’s secret sharing algorithm. When a committee member disconnects, a “recommittee” proceeds where a new member is selected through a commitment scheme that seeks to randomise the new selection. When the user exits the chat room, they are prompted to give the secret, and if they provide the correct secret, the flag is provided.
Before I begin with exploitation, I first had to understand the mathematical win condition for this challenge. Thankfully, the maths behind Shamir’s secret sharing is relatively simple. Firstly, a polynomial is constructed of degree k-1, for which the secret is the constant term of the polynomial. A pretentious nerd might write it like this:
f(x)=a₀+a₁x+a₂x²+a₃x³+...+aₙ₋₁xⁿ⁻¹+aₙx
Where a₀ is the secret. Then, n points (called “shares”) are selected on the polynomial, with each point given to a unique custodian. Since k points are necessary to determine a unique polynomial of degree k-1, k shares are necessary to reconstruct the initial polynomial, for which the constant term is the secret. The relevant code in the source files are given as below:
const PARAMS: ProtocolParameters = ProtocolParameters {
committee_size: 10,
threshold: 5,
panic_threshold: 35,
};
fn generate_shares_and_commits(
secret: BigUint,
rng: &mut StdRng,
q: &BigUint,
g: &BigUint,
) -> (Vec<BigUint>, Vec<BigUint>) {
let q_by_two = q.clone() / 2u32;
let polynomial: Vec<BigUint> = std::iter::once(secret.clone())
.chain((1..PARAMS.threshold).map(|_| rng.gen_biguint_range(&q_by_two, q)))
.collect();
let shares: Vec<BigUint> = (1..=PARAMS.committee_size)
.map(|x| {
polynomial
.iter()
.enumerate()
.map(|(i, a)| BigUint::from(x).modpow(&i.into(), q) * a)
.sum::<BigUint>()
% q
})
.collect();
let commitments: Vec<BigUint> = polynomial
.iter()
.map(|a| g.modpow(a, &(q * 2u8 + 1u8)))
.collect();
(shares, commitments)
}
From this, we can tell that the polynomial we want to reconstruct is a randomly generated 4th degree polynomial. Hence, my win condition is to gain 5 shares to reconstruct the secret, which I’d use Lagrange Interpolation for, like this:
def recover(q, shares):
out = 0
items = list(shares.items())
for i, yi in items:
t = yi % q
for j, _ in items:
if i != j:
t = (t * j * pow((j - i) % q, -1, q)) % q
out = (out + t) % q
return out
From there on out, I had to figure out a way to somehow get 5 shares from the committee. I’d either have to intercept communication during share distribution, or get myself 5 seats on the committee. I am not given any means to interact with the network layer itself, nor am I by any means good enough to hack PPP’s infra, so I had to go with the second option. Unfortunately for me, the bots didn’t seem to want to leave the chat room on their own, so I had to figure out a way to get rid of them. Fortunately, the infrastructure allows me to send direct messages to whichever bot I want, so maybe I could “convince” the committee members to leave?
ClientCommand::SendMessage(channel, message) => {
let ns = network_state.read().await;
let no_target_error = if channel.starts_with('@') {
(!ns.users
.iter()
.any(|u| u.as_ref().is_some_and(|u| u.name == channel[1..])))
.then_some("No such user")
} else {
(!ns.channels
.get(&channel)
.is_some_and(|ch| ch.users.contains(&user_id)))
.then_some("Not in channel")
};
After looking through all the commands I could send to the bots (which was veeeeery long, so I’m not pasting the full thing here), I came to the conclusion that the only way I could bully the bots into leaving was by crashing them. Luckily, there is a function that could raise a rust panic:
fn recover_from_shares(q: &BigUint, values: &[Option<BigUint>]) -> BigUint {
let q = BigInt::from(q.clone());
let mut r = BigInt::from(0);
for (i, yi) in values.iter().enumerate().skip(1) {
let Some(yi) = yi else { continue; };
let mut t = BigInt::from(yi.clone());
for (j, yj) in values.iter().enumerate().skip(1) {
if j != i && yj.is_some() {
t *= (BigInt::from(j)) * (BigInt::from(j) - BigInt::from(i)).modpow(&(&q - 2), &q);
t %= q.clone();
t += q.clone();
t %= q.clone();
// ...
Here, two arguments are taken: q and values. You may notice that t %= q.clone() makes no sense when q=0, since that involves dividing by zero, which causes a panic in rust. Hence, by setting q to 0, I can crash a bot. And yes, to you rust nerds out there I am aware that modpow(&(&q - 2), &q) also raises a modulo 0 crash, but my example is more obvious and straightforward. And what’s even better is that there exists a command where I can decide the modulus that the bot itself processes!
"RELEASED" => {
// ...
Ok(Self::ReleasedShare {
ident,
key,
value,
q,
g,
})
}
ProtocolMessage::ReleasedShare {
ident,
key,
value,
q,
g,
} => {
expect_from!("@");
let info = db.entry(ident.clone()).or_insert_with(|| ShareInfo {
users: Default::default(),
initiator: myself.to_string(),
q_g: (q.clone(), g.clone()),
commitments: vec![],
share: Default::default(),
released_share: Default::default(),
recommitteeing: None,
});
if info.q_g.0 != q || info.q_g.1 != g {
error!("Mismatched q/g for released share!");
continue;
}
if key == 0 || key > PARAMS.committee_size {
error!("Invalid key!");
continue;
}
info.released_share.insert(key, value);
if info.released_share.len() >= PARAMS.threshold {
let mut values = vec![None; PARAMS.committee_size + 1];
for (k, v) in &info.released_share {
values[*k] = Some(v.clone());
}
let secret = recover_from_shares(&q, &values).to_bytes_le();
let secret_str = String::from_utf8_lossy(&secret);
info!(ident, ?secret, %secret_str, "Recovered secret");
}
}
From info.released_share.insert(key, value), you can tell that recover_from_shares is triggered with an arbitrary q as long as 5 acceptable unique messages are passed. Hence, if I send 5 “shares” for the bot to verify, it will naively try to recover the secret without checking whether the modulus is even safe! Which means I get to KILL the bot, with just 5 messages that contain a bad q! But what about the other fields?
Firstly, take a look at the conditions for ident.
let info = db.entry(ident.clone()).or_insert_with(|| ShareInfo {
users: Default::default(),
initiator: myself.to_string(),
q_g: (q.clone(), g.clone()),
commitments: vec![],
share: Default::default(),
released_share: Default::default(),
recommitteeing: None,
});
All this does is define a database that initialises q and g if the ident input is new, and if the ident input already exists in the database, it moves onto checking q and g. Hence, for my exploit, all I need is to ensure the ident field remains the same. Now for the checking:
q_g: (q.clone(), g.clone())
if info.q_g.0 != q || info.q_g.1 != g {
error!("Mismatched q/g for released share!");
continue;
}
From this code, it becomes apparent that the value of g is not important (because we only want to get to the stage where the bot evaluates %q for q=0) as long as it passes the check, so all I need is a value for g that remains constant. Now onto key and info
if key == 0 || key > PARAMS.committee_size {
error!("Invalid key!");
continue;
}
info.released_share.insert(key, value);
if info.released_share.len() >= PARAMS.threshold {
let mut values = vec![None; PARAMS.committee_size + 1];
for (k, v) in &info.released_share {
values[*k] = Some(v.clone());
}
let secret = recover_from_shares(&q, &values).to_bytes_le();
let secret_str = String::from_utf8_lossy(&secret);
info!(ident, ?secret, %secret_str, "Recovered secret");
}
This restricts the value of key between 1 and 10, but the code following shows that if the value of a given key already exists in the database, “value” is overridden instead of appended (making the entire message pointless). Hence, my 5 messages need to cycle through 5 unique keys. And from looking at value… it literally does not matter what I put in the value field, except I need 5 of them that are all unique. Very nice! So now I know exactly how to kill the bot!!
def kill_user(self, user, tag):
for key in range(1, THRESHOLD + 1):
self.send(f"MSG @{user} RELEASED {tag} {key} 1 0 2")
time.sleep(0.25)
Now that I can kill anyone I want at will, I need to figure out how to gain more seats in the committee. Luckily, the recommittee code does not check for whether a chosen candidate already exists in the committee to give them a seat (or in my case, an additional seat).
recomm.new_users = share_info.users.clone();
recomm.new_users.add(user);
recomm.new_users.prune(&active_users);
fn add(&mut self, user: String) {
self.users.push(user);
}
So now I need to rig the commitment scheme. The code is, again, unbelievably long, so I’ll only use snippets to describe the whole thing. Firstly, the committee members generate a random value that g is exponentiated by, mod q.
let proposed_share: u64 = rng.gen();
let commit = share_info
.q_g
.1
.modpow(&proposed_share.into(), &share_info.q_g.0);
This is then broadcast to the public channel as commitments, which isn’t very interesting. Then, bots reveal their original random numbers which are compared to the commitments for verification
let rs = recomm
.revealed_shares
.iter()
.cloned()
.filter(|&s| {
let commit = share_info.q_g.1.modpow(&s.into(), &share_info.q_g.0);
recomm.commits.contains(&Some(commit))
})
.collect::<Vec<_>>();
Which isn’t very interesting either, except for the fact that it does not force every commitment to be verified. What is interesting is what happens after commitments have been verified:
if rs.len() < PARAMS.threshold {
abort_recomm!();
}
let r: usize = rs.into_iter().fold(0, |a, x| a ^ x).try_into().unwrap();
let user = active_users[r % active_users.len()].clone();
What happens here is that every random value is XORed against each other modulo the number of members in the room. Whoever happens to have the index of the number within the room members list becomes a committee member. And notably, the only criterion for abortion is if the number of verified commitments is below PARAMS.threshold, which is only 5…
The most straightforward idea is to, well, kill all the bots right? Except that if I kill too many people, the room panics (ba dum tss)
let active_users = connection.active_users(channel).await?;
if active_users.len() < PARAMS.panic_threshold {
error!("We are dropping like flies");
db.remove(&ident);
abort_recomm!()
};
The more realistic idea is to maximise my chances of landing on a selection during the commitment scheme. Since only 5 verified commitments are necessary, the logic does not check to ensure every commitment is verified, and the bots will always commit and verify, I never have to verify my commitments. However, if I do verify my commitments, the selection outcome changes. So for each unique combination of verified commitments, I get a 1/(number of room members) chance to gain a committee seat. And since the bots reveal their original random numbers before I reveal mine, I can actually precompute whether or not revealing my random number would give me the seat.
To make things even better, I can always abort the recommittee by broadcasting a JACCUSE message!
"JACCUSE" => {
let blame = s.next().ok_or(())?.to_owned();
Ok(Self::Abort { blame })
}
if let RecommitteeMessage::Abort { blame } = recomm_msg {
let Some(share_info) = db.get_mut(&ident) else {
debug!(blame, "Trying to abort a non-existent share");
return Ok(());
};
let Some(recomm) = &share_info.recommitteeing else {
debug!(blame, "Trying to abort a non-recommitteeing share");
return Ok(());
};
if recomm.nonce != nonce {
debug!(blame, "Trying to abort the wrong recommitteeing");
return Ok(());
}
share_info.recommitteeing = None;
debug!(from = msg.from, msg = msg.message, "Received Recomm Abort");
return Ok(());
}
Hence, I can write this neat “recommittee rigger”, that calculates the outcome of each combination of reveals, picks one that gives me the seat if it exists and JACCUSEs the committee to trigger a re-recommittee if none exists:
active_users = self.peek()
bot_xor = 0
for x in reveals:
bot_xor ^= x
best = None
for mask in range(1 << len(props)):
x = bot_xor
subset = []
for i, value in enumerate(props):
if mask & (1 << i):
x ^= value
subset.append(value)
selected = active_users[x % len(active_users)]
if selected == self.me:
best = (selected, subset)
break
if best is None:
self.send(f"MSG {self.channel} RECOMM {self.ident} {nonce} JACCUSE {self.me}")
raise RetryRound()
selected, subset = best
for value in subset:
self.send(f"MSG {self.channel} RECOMM {self.ident} {nonce} NUR {value}")
time.sleep(0.15)
self.send(
f"MSG {self.channel} RECOMM {self.ident} {nonce} BEGIN "
f"{selected} {self.initiator} {b36(self.q)} {b36(self.g)} {','.join(old_users)}"
)
By a simple loop of repeatedly killing off a committee member then rigging the recommittee, I can gain the 5 shares necessary to reconstruct the polynomial with the Lagrange Interpolation method I showed at the very start, which I then extract the secret from. And once I have the secret (and a working remote solve script that took me forever to get the timing right), well, this happens:
Flag: bbb{cavalcade_of_beggars_and_thieves:NoWayImTypingAllatByHand}
Postscript: This was by far the longest and most complex writeup I’ve ever written (at least at the time of writing), so uhh… Go follow my socials or something, or not I honestly don’t care
Update: The author responded to this writeup! I was really amazed to see the extent of effort taken within the making of this challenge, and I do feel honoured to receive such praise <3
