Side-channel vulnerability in libgcrypt - the Marvin Attack

[Hubert Kario]

On Friday, 8 March 2024 03:55:55 CET, NIIBE Yutaka wrote:
> Hello,
>
> Hubert Kario wrote:
>> I've tested libgcrypt against the Marvin Attack[1] and have verified it to
>> be vulnerable.
>
> Thank you for your report.
>
> My understanding is that libgcrypt exposes timing differences against
> chosen cipher texts by your timing analysis.

Correct, it's vulnerable to the chosen ciphertext attacks using timing
as a side-channel.

>> Looking more closely at results, the side-channel from removal of blinding
>> or conversion of the integer returned from the RSADP() operation[3] to a
>> byte string is the most significant source of leakage.
>> That means that all padding modes that use RSA will be vulnerable: raw RSA
>> (RSASVE), PKCS#1v1.5, and RSA-OAEP.
>
> The major possible causes of timing differences in libgcrypt are:
>
>    an old fork of GNU MP Bignum library for multi precision integer
>    arithmetic.
>
>    S-expression handling for multi precision integer representation.

not only for integers, the result of the PKCS#1v1.5 decryption is also
returned as an S-expression and it includes memory allocation that is
exactly the size of the message. Combined with no memory allocation in
case of padding check failure, that gives a very clear signal.

So it's general S-expression handling of data that has secret lengths.

> I'd agree that we need documentation update of libgcrypt to explain
> possible timing differences of libgcrypt RSA implementation; Well,
> libgcrypt users should know that RSA private key may be at risk when
> implementing decryption network service if timing information is
> available to remote side.

+1 to that. Not every implementation needs to be side-channel safe, but
if it isn't, then the covered threat model needs to be documented so
that users can make informed decisions.

My reading of current https://gnupg.org/documentation/security.html
is that remote timing attacks are in scope. Only microarchitectural
attacks, like SPECTRE, are outside the threat model.

> If possible, could you give us some concrete information how large the
> side-channel to compose a possible attack?  It would be good for us to
> know the impact of timing differences.

Not sure if I understand the question...

The size of the side-channel in libgcrypt is about 200 ns.
The smallest side-channel I was able to successfully differentiate
over the network, across 5 router hops (2 physically separate data centres
in the same city), is about 1 ns.

So in practice, to _fix_ a timing side-channel, the leakage needs to be
completely eliminated. Otherwise the attack is just a question of
attacker's persistence, not size of the side-channel.

-- 
Regards,
Hubert Kario
Principal Quality Engineer, RHEL Crypto team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00, Brno, Czech Republic