Subject: [TLS] FYI, a subverted implementation attack against TLS at ia.cr/2020/1452

From: Dan Brown <[email-masked]>
Date: Wed, 25 Aug 2021 14:26:14 +0000

Dear TLS list,

FYI, ICYMI,

Berndt et al. describe a subverted implementation attack against TLS
https://eprint.iacr.org/2020/1452
I just noticed this report today and don't remember seeing it mentioned on the TLS list already.  It seems to be worth at least considering.

A summary and brief discussion:

The subverted TLS implementation (IIUC) uses server randoms (nonce) to quickly exfiltrate the server's signing key - so it could be characterized as proof of concept instance of a well-known idea, kleptography, (but please correct this summary if necessary, since it is only based on a skimming of the report).

Granted: it is difficult (impossible?) to thwart all subverted implementation attacks. But this attack is easier than others in that category, so might be notable.

This general issue with public random nonces has been discussed on TLS, for example:
https://mailarchive.ietf.org/arch/msg/tls/56N_-KDN0LuWyEvAhmFnm7g8p6A/
This past discussion led to a recommendation to use different RNGs for the public random versus the DH secrets, but I don't see how that would be enough to stop this attack.

In reviewing the TLS archive (from the thread above), I see that the general difficulty of thwarting subverted implementations has also already been raised. Basically, this argues that the best solution is to prevent subversion of implementations in the first place, and that making the protocol robust against subverted implementations is hopeless and wasteful. Maybe that's right.  (Maybe part of this anti-subversion defense would be separating the server keys, e.g. in a separate signing module, from the rest of the implementation?  Maybe some TLS servers already do this.)

>From the abstract of the attack report:
"... We show that these protocols can be easily subverted by carefully placing ASAs. Our analysis shows that careful design of ASAs makes detection unlikely while leaking long-term secrets within a few messages in the case of TLS ..., allowing impersonation attacks. ..."

The attack report also says that forward secrecy makes an implementation inherently more vulnerable to this attack.  I didn't look at the details, but I suspect that this is because ephemeral public keys can also be filtered by hashing, e.g. a Simmons subliminal channel,  - but this is presumably more costly, and more detectable?

The attack report has a section on Countermeasures and Design Lessons, the most general countermeasure is to re-design the protocol not to send freely random nonces, which I agree with, since it is so simple.  They also suggest requiring time-stamps to prevent replay attacks, (in case re-used ephemeral keys).

Best regards,
 
Dan Brown

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 26 Aug 2021 08:01:15 +1000

I don't think that this is a particularly important result.  The formalism is perhaps valuable, but the intuition is not novel: if you control an endpoint and it can send messages, those messages can contain information.  There are far too many places in almost any protocol where information can be placed for exfiltration.

Just looking at random nonces isn't going change anything here.  Those are just the easy choice.  Message size and timing contains information.  Ordering of extensions or options contains information.  GREASE contains information.

That Signal was hard is interesting, but I don't think that the authors were sufficiently creative.  They say "these low-bandwidth attacks cannot be used to leak the short-term, ephemeral keys", but I don't think that is true at all.  I'll leave it as an exercise for the reader, but I believe it to be trivial to have all keying material available to the observer if an endpoint is cooperative.

The idea that you might somehow design your way into a protocol that has no exfiltration capability is a nice academic exercise, but any such protocol would be completely impractical.

On Thu, Aug 26, 2021, at 00:26, Dan Brown wrote:
> I just noticed this report today and don't remember seeing it mentioned 
> on the TLS list already.  It seems to be worth at least considering.
> 
> The subverted TLS implementation (IIUC) uses server randoms (nonce) to 
> quickly exfiltrate the server's signing key - so it could be 
> characterized as proof of concept instance of a well-known idea, 
> kleptography, (but please correct this summary if necessary, since it 
> is only based on a skimming of the report).
> 
> Granted: it is difficult (impossible?) to thwart all subverted 
> implementation attacks. But this attack is easier than others in that 
> category, so might be notable.
> 
> This past discussion led to a recommendation to use different RNGs for 
> the public random versus the DH secrets, but I don't see how that would 
> be enough to stop this attack.
> 
> In reviewing the TLS archive (from the thread above), I see that the 
> general difficulty of thwarting subverted implementations has also 
> already been raised. Basically, this argues that the best solution is 
> to prevent subversion of implementations in the first place, and that 
> making the protocol robust against subverted implementations is 
> hopeless and wasteful. Maybe that's right.  (Maybe part of this 
> anti-subversion defense would be separating the server keys, e.g. in a 
> separate signing module, from the rest of the implementation?  Maybe 
> some TLS servers already do this.)
> 
> "... We show that these protocols can be easily subverted by carefully 
> placing ASAs. Our analysis shows that careful design of ASAs makes 
> detection unlikely while leaking long-term secrets within a few 
> messages in the case of TLS ..., allowing impersonation attacks. ..."
> 
> The attack report also says that forward secrecy makes an 
> implementation inherently more vulnerable to this attack.  I didn't 
> look at the details, but I suspect that this is because ephemeral 
> public keys can also be filtered by hashing, e.g. a Simmons subliminal 
> channel,  - but this is presumably more costly, and more detectable?
> 
> The attack report has a section on Countermeasures and Design Lessons, 
> the most general countermeasure is to re-design the protocol not to 
> send freely random nonces, which I agree with, since it is so simple.  
> They also suggest requiring time-stamps to prevent replay attacks, (in 
> case re-used ephemeral keys).
> 
> Best regards,
> 
> Dan Brown
> 
> This transmission (including any attachments) may contain confidential 
> information, privileged material (including material protected by the 
> solicitor-client or other applicable privileges), or constitute 
> non-public information. Any use of this information by anyone other 
> than the intended recipient is prohibited. If you have received this 
> transmission in error, please immediately reply to the sender and 
> delete this information from your system. Use, dissemination, 
> distribution, or reproduction of this transmission by unintended 
> recipients is not authorized and may be unlawful.
> 
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
> 
> Attachments:
> * smime.p7s

---

From: Bill Frantz <[email-masked]>
Date: Wed, 25 Aug 2021 18:26:47 -0400

On 8/26/21 at 6:01 PM, [email-masked] (Martin Thomson) wrote:

>That Signal was hard is interesting, but I don't think that the 
>authors were sufficiently creative.  They say "these 
>low-bandwidth attacks cannot be used to leak the short-term, 
>ephemeral keys", but I don't think that is true at all.  I'll 
>leave it as an exercise for the reader, but I believe it to be 
>trivial to have all keying material available to the observer 
>if an endpoint is cooperative.

And remember, you don't have to exfiltrate the whole key to make 
the exhaustive search problem much easier.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | The first thing you need when  | Periwinkle
(408)348-7900      | using a perimeter defense is a | 150 
Rivermead Rd #235
www.pwpconsult.com | perimeter.                     | 
Peterborough, NH 03458