145 views

Skip to first unread message

Apr 13, 2024, 5:05:13 PMApr 13

to KpqC-bulletin

Dear all,

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.

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.

Apr 23, 2024, 5:10:37 AMApr 23

to KpqC-bulletin

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

2024년 4월 14일 일요일 오전 6시 5분 13초 UTC+9에 Alex Pellegrini님이 작성:

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu