Subject: [Cfrg] Stateful deterministic encryption

From: Dan Brown <[email-masked]>
Date: Thu, 12 Jun 2014 19:25:24 +0000

Dear CFRG list,

I recommend reading the excellent report on subverted symmetric encryption.

http://eprint.iacr.org/2014/438

The report raises the potential vulnerability of implementations of various
IETF protocols to subverted symmetric encryption attacks.  The report
recommends various stateful deterministic symmetric modes.  Should CFRG
encourage IETF to adopt these?

Many IETF protocols are already pretty close to using stateful and
deterministic symmetric encryption, but still have potential subversion
vulnerability arising from variable padding length being subvertible to leak
the symmetric key.  

If I recall correctly, the purpose of variable message lengths is to hide
the message length.  If so, then maybe it would be beneficial to derive the
variable length deterministically from the key and state (and perhaps
message, etc.) in a manner that achieves the unique-ciphertexts property
describe in the report, and still continue to somewhat hide the message
length.

Best regards,

Daniel Brown

Research In Motion Limited

---

From: David McGrew <[email-masked]>
Date: Fri, 13 Jun 2014 11:27:11 -0400

Hi Dan,

On Jun 12, 2014, at 3:25 PM, Dan Brown <[email-masked]> wrote:

> The report raises the potential vulnerability of implementations of various IETF protocols to subverted symmetric encryption attacks.  The report recommends various stateful deterministic symmetric modes.  Should CFRG encourage IETF to adopt these?

thanks for forwarding this work to the list.   My initial emotional response is an enthusiastic “yes”, though there are limitations to what can be achieved in this direction, so our recommendation to the IETF should be calibrated so that it does not overstate our ability to solve this type of problem through a choice of encryption algorithm (Disclaimer:  I have not yet fully digested the paper, though I spoke to Kenny about it at the last IETF meeting).    At the very least, we should call out the goal of resisting algorithm substitution attacks as a worthwhile one.  

>  
> Many IETF protocols are already pretty close to using stateful and deterministic symmetric encryption, but still have potential subversion vulnerability arising from variable padding length being subvertible to leak the symmetric key. 
>  
> If I recall correctly, the purpose of variable message lengths is to hide the message length.  If so, then maybe it would be beneficial to derive the variable length deterministically from the key and state (and perhaps message, etc.) in a manner that achieves the unique-ciphertexts property describe in the report, and still continue to somewhat hide the message length.

Interesting, I will need to read through the paper better and think about that.  

Appendix A of the eprint paper discusses IETF protocols.   Thanks Kenny and co-authors for relating the work to current practice.  I have some comments on that section.  

When discussing the use of AEAD in TLS, for instance, it is pointed out that the use of the GenericAEADCipher.nonce field to carry part of the nonce means that an implementation of AES-GCM in TLS 1.2 can be RFC-compliant but still vulnerable to an IV replacement attack.   In other words, GenericAEADCipher.nonce could be used by the sender to leak information about the secret key.   This is a valid point.   However, the TLS RFC recommends a particular deterministic construction for that field, and if the recommendation is followed, that fact will be readily apparent.   I believe that the deterministic construction for that field resists algorithm substitution attacks (would like to hear what Kenny thinks on this :-)  If so, new TLS work such as draft-ietf-uta-tls-bcp-00 can and should mandate the recommended nonce formation.   (I’ve copied Yaron, who is both an author on that draft and a CFRG participant.)   Note that draft-ietf-uta recommends AES-GCM, so clarifications around the right way to do AEAD in TLS would be valuable at this point in time.

Another IETF work worth considering is Secure RTP (RFC 3711; also note new related work http://tools.ietf.org/html/draft-ietf-avtcore-srtp-aes-gcm-12) which I believe is resistant to ASAs.

Kenny, a point that deserves some consideration: the main motivation for having (part of) a nonce carried explicitly in the non-encrypted part of the packet is to make it possible for multiple encryption engines to use the same key.   See RFC 6504 “Using Counter Modes with Encapsulating Security Payload (ESP) and Authentication Header (AH) to Protect Group Traffic” for instance.   I don’t think this fact should change your analysis, but it would be good to acknowledge that there are valid motivations for using an explicit nonce.    Also, as far as protocol design motivation goes, the use of an explicit nonce carried in the packet reflects what network protocol people would consider best practices: be liberal in what you accept (see RFC1122).   This “robustness principle” should not trump considerations about algorithm substitution attacks, but it speaks to the importance of explaining all of the issues and motivations to people who design network protocols.  

There was some discussion a few years back about RFC6979, “Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)”, before it became an RFC.   At the time, several CFRG members were enthusiastic about deterministic signatures, in part because of their resistance to ASAs.   Perhaps we should revisit this work and consider either recommending it or updating it (if there are issues or concerns with it).

As a long term goal, it would also benefit us to understand the limitations of this approach of trying to avoid trusting the implementer by designing crypto algorithms  that can’t leak the secret/private key through the strings that they output.   There are other side channels available to an untrustworthy implementer, such as a timing channel (as pointed out by Kenny and co-authors).   Yet another option available to an attacker in the ASA setting is to modify the plaintext,  before encryption, in a way that would not affect the way that the receiver processes it.   For instance, an untrustworthy implementer of the TLS protocol could change HTTP whitespace in such a way as to ensure that the authentication tag leaked some information about the public key.   This attack, of subtly changing the plaintext, would seem to work against any encryption method regardless of whether or not it resists algorithm substitution attacks (because it is outside the ASA model).   So while resisting ASA attacks is a good thing that we should strive for, we should balance it against other requirements, and continue to push for other ways of providing assurance about the faithfulness of crypto implementations.

David

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 13 Jun 2014 17:31:42 +0000

Hi David,

<Removing my CFRG co-chair hat, and with apologies for the broken
indentation with respect to Daniel's earlier message.>

On 13/06/2014 16:27, "David McGrew" <[email-masked]> wrote:

>The report raises the potential vulnerability of implementations of
>various IETF protocols to subverted symmetric encryption attacks.  The
>report recommends various stateful deterministic symmetric modes.  Should
>CFRG encourage IETF to adopt
> these?
>
>
>
>
>
>
>thanks for forwarding this work to the list.   My initial emotional
>response is an enthusiastic ³yes², though there are limitations to what
>can be achieved in this direction, so our recommendation to the IETF
>should be calibrated so that it does not overstate
> our ability to solve this type of problem through a choice of encryption
>algorithm (Disclaimer:  I have not yet fully digested the paper, though I
>spoke to Kenny about it at the last IETF meeting).    At the very least,
>we should call out the goal of resisting
> algorithm substitution attacks as a worthwhile one.
>

There are indeed many limitations in our approach, but we wanted to
(re)start the ball rolling on this topic in the academic community and get
some people thinking about how far we can go. I do think it's very early
to even start to think about giving advice to IETF based on this very new
paper, and any advice we did give would have to come with many caveats as
David indicates.

>vulnerability arising from variable padding length being subvertible to
>leak the symmetric key.
> 
>the message length.  If so, then maybe it would be beneficial to derive
>the variable length deterministically from the key and state (and perhaps
>message, etc.) in
> a manner that achieves the unique-ciphertexts property describe in the
>report, and still continue to somewhat hide the message length.
>
>
>
>Appendix A of the eprint paper discusses IETF protocols.   Thanks Kenny
>and co-authors for relating the work to current practice.  I have some
>comments on that section.
>
>
>When discussing the use of AEAD in TLS, for instance, it is pointed out
>that the use of the GenericAEADCipher.nonce field to carry part of the
>nonce means that an implementation of AES-GCM in TLS 1.2 can be
>RFC-compliant but still vulnerable to an IV replacement
> attack.   In other words, GenericAEADCipher.nonce could be used by the
>sender to leak information about the secret key.   This is a valid point.
>  However, the TLS RFC recommends a particular deterministic construction
>for that field, and if the recommendation
> is followed, that fact will be readily apparent.   I believe that the
>deterministic construction for that field resists algorithm substitution
>attacks (would like to hear what Kenny thinks on this :-)

I will certainly think about it. With a deterministic nonce, it may be
possible to prove "surveillance security" as we call it.

> If so, new TLS work such as draft-ietf-uta-tls-bcp-00
> can and should mandate the recommended nonce formation.   (I¹ve copied
>Yaron, who is both an author on that draft and a CFRG participant.)
>Note that draft-ietf-uta recommends AES-GCM, so clarifications around the
>right way to do AEAD in TLS would be valuable
> at this point in time.
>
>
>Another IETF work worth considering is Secure RTP (RFC 3711; also note
>new related work
>http://tools.ietf.org/html/draft-ietf-avtcore-srtp-aes-gcm-12) which I
>believe is resistant to ASAs.
>
>
>Kenny, a point that deserves some consideration: the main motivation for
>having (part of) a nonce carried explicitly in the non-encrypted part of
>the packet is to make it possible for multiple encryption engines to use
>the same key.   See RFC 6504 ³Using
> Counter Modes with Encapsulating Security Payload (ESP) and
>Authentication Header (AH) to Protect Group Traffic² for instance.   I
>don¹t think this fact should change your analysis, but it would be good
>to acknowledge that there are valid motivations for using
> an explicit nonce.

OK, we should add that in the next update.

>  Also, as far as protocol design motivation goes, the use of an explicit
>nonce carried in the packet reflects what network protocol people would
>consider best practices: be liberal in what you accept (see RFC1122).
>This ³robustness principle²
> should not trump considerations about algorithm substitution attacks,
>but it speaks to the importance of explaining all of the issues and
>motivations to people who design network protocols.

Right, good point.

>
>There was some discussion a few years back about RFC6979, ³Deterministic
>Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital
>Signature Algorithm (ECDSA)², before it became an RFC.   At the time,
>several CFRG members were enthusiastic
> about deterministic signatures, in part because of their resistance to
>ASAs.   Perhaps we should revisit this work and consider either
>recommending it or updating it (if there are issues or concerns with it).

Yes, this is a good and cheap way of blocking off one avenue of attack
against randomised signature schemes. I'll need to read RFC 6979 now to
see exactly what it does and whether it's theoretically sound. Maybe
someone else on the list knows already?

>As a long term goal, it would also benefit us to understand the
>limitations of this approach of trying to avoid trusting the implementer
>by designing crypto algorithms  that can¹t leak the secret/private key
>through the strings that they output.   There
> are other side channels available to an untrustworthy implementer, such
>as a timing channel (as pointed out by Kenny and co-authors).   Yet
>another option available to an attacker in the ASA setting is to modify
>the plaintext,  before encryption, in a way
> that would not affect the way that the receiver processes it.   For
>instance, an untrustworthy implementer of the TLS protocol could change
>HTTP whitespace in such a way as to ensure that the authentication tag
>leaked some information about the public key.
>   This attack, of subtly changing the plaintext, would seem to work
>against any encryption method regardless of whether or not it resists
>algorithm substitution attacks (because it is outside the ASA model).

Agreed, it's outside our model but a real threat. So it's another attack
that needs to be mentioned in our paper as being not covered by our
limited scope. Thanks for pointing it out.

>So while resisting ASA attacks is a good thing
> that we should strive for, we should balance it against other
>requirements, and continue to push for other ways of providing assurance
>about the faithfulness of crypto implementations.

This is a very important point. Our paper is definitely far from being the
last word - in fact, we hope it's just a starting point for more work on
this previously neglected topic.

Cheers,

Kenny

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 13 Jun 2014 14:34:59 -0400

> RFC-compliant but still vulnerable to an IV replacement attack.   In
> other words, GenericAEADCipher.nonce could be used by the sender to leak
> information about the secret key.   This is a valid point.   However,
> the TLS RFC recommends a particular deterministic construction for that
> field, and if the recommendation is followed, that fact will be readily
> apparent.   I believe that the deterministic construction for that field
> resists algorithm substitution attacks (would like to hear what Kenny
> thinks on this :-)  If so, new TLS work such
> as draft-ietf-uta-tls-bcp-00 can and should mandate the recommended
> nonce formation.   (I’ve copied Yaron, who is both an author on that
> draft and a CFRG participant.)   Note that draft-ietf-uta recommends
> AES-GCM, so clarifications around the right way to do AEAD in TLS would
> be valuable at this point in time.
>
I do not think that this belongs in the BCP draft, for several reasons:

- The BCP is about things that can be implemented today or in the near 
future. A research paper quite obviously doesn't meet that criterion.

- I would be surprised if we can achieve consensus that this threat 
model (subliminal channels introduced by rogue implementations) is of 
interest to the UTA working group.

- While the choice of encryption algorithm/mode is a very interesting 
discussion, it clearly cannot prevent info leakage from the TLS protocol 
as a whole. For example, I could very easily leak my RNG's seed in the 
form of crypto suite offers, right at the start of the handshake.

Of course, I may be misunderstanding the issue. Or the UTA WG consensus 
might be different.

Thanks,
	Yaron

---

From: David McGrew <[email-masked]>
Date: Fri, 13 Jun 2014 14:44:54 -0400

> As a long term goal, it would also benefit us to understand the limitations of this approach of trying to avoid trusting the implementer by designing crypto algorithms  that can’t leak the secret/p…

I got a private query about what I meant, so let me try to better explain the “whitespace attack" that I had in mind.

Consider an untrustworthy implementation of the TLS protocol - “malwareSSL” say.  Its goal is to leak the TLS master key of each session that is negotiated, without being detected.  On the input of a plaintext P, which is to be protected as a TLS record and sent to the other side, it computes a tweak P’ of that packet by modifying the whitespace of the HTML at the very end of the packet, then computes the authentication tag for both P and P’, let’s call them T and T’.  Then the implementation chooses to send P or P’ based on some function that will leak information about the key.   For instance, it could choose the plaintext so that the ith bit of the TLS master secret matches the last bit of the authentication tag, where i is the TLS sequence number.   With probability about 3/4, it will be able to leak a single bit with each message.   To leak more bits per message, more candidate plaintexts could be generated and tested.  

This attack would work even against encryption methods that are robust against algorithm substitution attacks, but it offers an untrustworthy attacker a lower-bandwidth and less reliable channel for leaking secret keys, compared to e.g. the unpredictable IVs used in the CBC mode of operation.   So we should prefer algorithms that resist the substitution attack, but also realize that algorithms secure in that model don’t eliminate all of the channels that could leak the secret key.  

David

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 13 Jun 2014 19:50:27 +0100

Hiya,

> this previously neglected topic.

I think this could be a valuable topic for CFRG and the
academic crypto community that could lead to very worthwhile
advice to the IETF as it matures.

Another aspect to consider is FIP-140 and similar national stds
with which vendors and other implementers may be expected to
conform. (Though the US ones are by far the most commonly cited
of course.)

Where new recommendations do not conform to such, it would be
useful to have that clearly set out and justified so that
protocol developers, implementers and folks writing RFPs etc
can point at something credible to justify doing better.

For that part of the work, one might need to engage more with
implementers, (rather than just academic cryptographers) as they
will know better what deviates from e.g. FIPS-140 etc.

The reason to consider this btw is not (IMO) to try to fight
off change and maintain compliance with older national standards
but rather to make it more feasible to move away from those,
where there are good technical justifications for so doing. And
maybe the national stds can later catch up more easily.

Cheers,
S.

---

From: David McGrew <[email-masked]>
Date: Fri, 13 Jun 2014 14:58:02 -0400

On Jun 13, 2014, at 2:34 PM, Yaron Sheffer <[email-masked]> wrote:

> - The BCP is about things that can be implemented today or in the near future. A research paper quite obviously doesn't meet that criterion.

I’m sorry, I think I wasn’t clear in what I was suggesting.   What I meant was this:

RFC5288 says "The nonce_explicit MAY be the 64-bit sequence number.”   draft-ietf-uta-tls-bcp-00 can say that it SHOULD be the sequence number, or that the format of Section 6.2 SHOULD be used.   That recommendation will eliminate the possibility that an untrustworthy implementation could do the “IV replacement attack”.   Considering that the draft recommends a cipher suite from that RFC, I think this would be worth doing.

> 
> - I would be surprised if we can achieve consensus that this threat model (subliminal channels introduced by rogue implementations) is of interest to the UTA working group.
> 
> - While the choice of encryption algorithm/mode is a very interesting discussion, it clearly cannot prevent info leakage from the TLS protocol as a whole. For example, I could very easily leak my RNG's seed in the form of crypto suite offers, right at the start of the handshake.

True enough, and unfortunate.  As I see it, we should seek to minimize the size of subliminal channels that could be used to leak secret information, which is the only realistic goal, since it is impossible to eliminate them.  

David

> 
> Of course, I may be misunderstanding the issue. Or the UTA WG consensus might be different.
> 
> Thanks,
> 	Yaron

---

From: Dan Brown <[email-masked]>
Date: Fri, 13 Jun 2014 21:07:06 +0000

> -----Original Message-----
> From: David McGrew [mailto:[email-masked]]
> I got a private query about what I meant, so let me try to better explain
the
> "whitespace attack" that I had in mind.
> 

As a result of a short off-list discussion, I'll add that this whitespace
attack, or similar plaintext-modification attacks, is "detectable" under the
formal definition of the Bellare--Paterson--Rogaway report (if I understand
it correctly), because the plaintexts are changed.

This formal detection might be practically implemented by running a copy of
the suspicious software "malwareSSL" against a test harness.  The test
harness feeds the suspect software lots of plaintext, e.g. HTML pages, per
the whitespace attack, then decrypts the ciphertexts using some more trusted
decryption software.  If any output plaintext disagrees with an input
plaintext, then the malwareSSL has been detected.  

This test harness should be applied strictly to the encryption module of the
software: else the test harness might not work in a larger protocol setting.
For example, suppose that the malwareSSL provides a TLS server, and leaks it
keys only when connected to a malicious client. Such a client would have to
authenticate itself to the server somehow,  maybe by embedding a signature,
or MAC, or something, somewhere in its TLS stream, perhaps in the client
random or IV, or perhaps hiding the signature within the natural variability
present in whatever plaintexts a normal client might send (i.e. by
steganography).  Anyway, a generic test harness described above might not
detect the leak, because it would be unlikely to simulate the malicious
client.  In particular, this test-harness does not help to detect deployed
copies of the "malwareSSL" because isolating the encryption module would be
hard.  In that case, one might need to reverse engineer the software to find
the leak.  

Despite that other kinds of leaking attacks are possible, the
unique-ciphertexts property described in the BPR report still seems
worthwhile as a low-cost tool for preventing certain kinds of attacks.

---

From: David McGrew <[email-masked]>
Date: Fri, 13 Jun 2014 17:16:37 -0400

Thanks Dan for a fruitful discussion on this point, more inline:

> hard.  In that case, one might need to reverse engineer the software to find

In any case, I like the idea of a test harness.   The raft of vulnerabilities that have appeared in real-world implementations of complex protocols underscores the need for test coverage beyond the algorithm validation methodology of FIPS-140.  

> worthwhile as a low-cost tool for preventing certain kinds of attacks.

Agreed.

David