Side-channel vulnerability in libgcrypt - the Marvin Attack

[NIIBE Yutaka]

Hello, again,

Hubert Kario <hkario at redhat.com> wrote:
> Correct, it's vulnerable to the chosen ciphertext attacks using timing
> as a side-channel.

Thank you for your confirmation.

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

Thank you for your clarification.

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

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


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.


Let us see how we can change our documentation.
--