An attack against the Paloma reference software
Alex Pellegrini
We want to share an observation on the reference implementation of Paloma. The
attached script recovers the shared secret from a given Paloma ciphertext by
observing the receiver's reactions to tweaked versions of the ciphertext.
We noticed that the implementation checks for the polynomial computed by the
extended-Patterson algorithm not having roots in the base field, which often
crashes the program if there are small modifications to the ciphertext.
The attack relies on observing which modified ciphertexts produce crashes.
This models the situation that a server accepts connections and decapsulates
ciphertexts using its long-term private key.
A crash is normally observable as a dropped connection, and servers normally
restart after they crash, so the attacker is free to continue sending modified
ciphertexts to the server.
In particular, introducing an error in the error vector and thus increasing its
weight to t+1, would make the decoder fail and produce a random polynomial, not
corresponding to the error-locator. The produced polynomial has low chance to
have roots in the base field, and thus a good chance of crashing the server.
Therefore, the idea is to locate 0-bits of the error vector by flipping bits
of the ciphertext. If a bit flip crashes the server, then the flipped bit was
a 0-bit. In a Niederreiter-like system, the operation corresponding to a bit
flip is that of XOR-ing a column of the public matrix into the syndrome.
A crash tells the attacker that she introduced an extra error or, in other
words, she flipped a 0 bit of the error vector.
In case the polynomial computed by the decoding algorithm has at least one root
in the base field, the program does not crash. This means that one cannot
directly identify the 1-bits, but only restrict their positions by looking at
how the receiver reacts attempting to decrypt a modified ciphertext.
We noticed also that the attacker can recover more 1-bits of the error vector
by flipping combinations of two bits, where she picks one to be a confirmed 0-bit
and one being an unknown bit isolated in the previous step.
In this case, if both bits were originally 0, the polynomial computed by
the decoder corresponds to an error of weight t + 2, so a fresh random
polynomial having a new chance of crashing the server.
The attacker can thus distinguish more 1-bits using this strategy because
flipping a combination of one 1 and one 0 to their opposites does keep the
error at weight t and thus cannot cause a crash.
It turns out that flipping such combinations of two bits is enough to fully
reconstruct the error vector. Recovering the shared secret is then
straightforward.
It should be possible to use fewer ciphertexts by taking combinations of two
bits at the beginning and marking both bits as 0 in case of a crash. It may
also be possible to recover information about the private key from the pattern
of ciphertexts that cause crashes.
NB : This issue is easy to fix by removing the exception for Hamming
weight 0 of the recovered error vector, but care must be taken to avoid
introducing other side channels.
To run the attack:
- make sure the two attached files sit in the same directory;
- execute .sh script, it will download and extract a copy of Paloma, compile
with the attack script and run.
All the best,
Alex, Dan and Tanja.
Minji Kim
Dear Alex, Dan, and Tanja,
Thank you for sharing your observation regarding the reference C code of PALOMA.
We have carefully reviewed the bug you've outlined.
Source Code Changes
In the utility/decap.c file, specifically within the decap() function, we have made modifications to the check_err_vec function call as follows:
Before:
--------------------------------------------------------------------------------------
if (!check_err_vec(e_hat))
{
puts("invalid error vector: error vector does not have t errors.");
exit(1);
}
--------------------------------------------------------------------------------------
After:
--------------------------------------------------------------------------------------
/* Delete the following 5 lines. */
// if (!check_err_vec(e_hat))
// {
// puts("invalid error vector: error vector does not have t error.");
// exit(1);
// }
--------------------------------------------------------------------------------------
It was code intended for debugging during development, and it was mistakenly not deleted.
With this remove, if the Hamming weight of the error vector after decryption is not t, implicit rejection is triggered, and the aforementioned modification enables the software to defend against the scenario.
Additionally, we are actively working on further improvements from a secure implementation perspective. Updates reflecting these changes will soon be available on the PALOMA Website .
Once again, we appreciate your thorough analysis of PALOMA and the insights you've provided.
Best regards,
PALOMA TEAM