Side-channel vulnerability in libgcrypt - the Marvin Attack

[Hubert Kario]

On Friday, 15 March 2024 07:42:24 CET, NIIBE Yutaka wrote:
> Hello, again,
>
> Hubert Kario <hkario at redhat.com> wrote:
>>> 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.
>
> I think that we need to update the document to avoid possible confusion.

Please do.

>>> 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.
>
> Again, thank you for your clarification.
>
>
> I tried hard to consider a possible scenario we could imagine.  I
> managed to come up with something like:
>
> * A crypto developer uses libgcrypt to build a secure enclave
>   implementation which offers RSADP service.
>
> * He is not dumb, so, error return of gcry_pk_decrypt is hidden in the
>   service.
>
> * But he is kind enough to attackers not having protection measures
>   against abuse for the service.
>
> * In the service, side-channel of timing information is available to
>   attackers.  Suppose there is no limitation for number of invocations.
>
> In this scenario, yes, you are right that it's a matter of attacker's
> persistence (or his/product lifespan).  In theory, even with terrible
> S/N ratio, information can be transmitted over a channel.
>
> Thus, it means that RSA private key may be at risk, in this kind of
> hypothetical scenario.
>
> My original question was... about quantitative evaluation and
> possibility in real cases.  In other words, my interest is: if there are
> any existing applications/services/products/etc., and the degree of how
> likely are these problems and how much effort/time is needed to recover
> RSA private key, in such a possible scenario.

The current threat model specifies "Libgcrypt has been developed for use in 
a
wide variety of platforms with different security needs." My reading of 
that
is that it's an appropriate library for general purpose cryptography.

So yes, that means that Marvin requires such hypothetical scenario as you
talk about. But I'd say that using libgcrypt to implement a network API end
point that accepts Json Web Encryption tokens is not outside the realm of
possibility, or even a far fetched idea. And definitely within the
threat model as currently documented.

> Well, I think that there are other protection measures than eliminating
> timing difference in the crypto library.  We can consider the case of a
> USB device.  The communication from a device to host is basically
> time-slotted (or device implementation can wait its response to the next
> Start-Of-Frame, if needed).  Timing information for the computation of
> crypto operation can be hidden by time-slotted response.

Actually no. If the time slots are consistent (say, the USB device returns
the message only on the second, on the dot), then the attacker can tune the
time when it _starts_ the operation so that it end exactly at the second.
Then quicker operations will be returned earlier, while slower will be
returned a second later.

The only way to effectively hide timing side-channel is to have operation
take the same amount of time always, but make it very long, so that 
additional
load can't really push it towards that time. I mean like 30 to 60 seconds
per operation.

That won't mask any other side-channels, but may be enough to protect 
against
simple timing attacks.

-- 
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