Subject: [Cfrg] Task for the CFRG

From: "Igoe, Kevin M." <[email-masked]>
Date: Thu, 8 Aug 2013 19:45:40 +0000

The TLS WG has asked the CFRG for their opinion for a stream cipher, eSTREAM-SALSA20,
and two MAC algorithms, UMAC and POLY1305, that have been suggested for use in TLS
(draft-josefsson-salsa20-tls-02).  This was presented to the TLS WG at IETF-87, slides can
be found at http://www.ietf.org/proceedings/87/slides/slides-87-tls-2.pdf.
The SALSA family works on blocks of 512 bits, and forms a key stream in 512-bit blocks by
applying a fixed map V^{512}->V^{512} to an input consisting of the key (either 16 octets or
32 octets), an 8-octet block counter, an 8-octet IV,  and 16 constant octets.

SALSA20 was one of the five finalists for a software stream cipher in the eSTREAM
contest run by ECRYPTII (see http://www.ecrypt.eu.org/stream/).

UMAC has been around since 1999 and is described in RFC 4418.

POLY1305 first showed up as POLY1305-AES, but all it needs from AES is a 16 byte block
of output. Adapting this to SALSA is straightforward.  The 1305 in the name reflects the
fact that it uses arithmetic modulo 2^{130} - 5.  See http://cr.yp.to/mac/poly1305-20050329.pdf
for a description of poly1305-AES.

Off the top of my head, the only objection I can see is that SALSA may be difficult to
implement efficiently in hardware.  Hardware TLS acceleration can be useful at heavily
utilized servers.

The most current attempt to attack SALSA that I could find is a 2012 paper on the IACR
e-print server.

----------------+--------------------------------------------------
Kevin M. Igoe   | "We can't solve problems by using the same kind
[email-masked]  | of thinking we used when we created them."
                |              - Albert Einstein -
----------------+--------------------------------------------------

---

From: Ted Krovetz <[email-masked]>
Date: Thu, 8 Aug 2013 13:24:10 -0700

> and two MAC algorithms, UMAC and POLY1305, that have been suggested for use in TLS

I am well familiar with all three. I edited the UMAC RFC, have been working with a Salsa variant called Chacha, and have used several polynomial hashes similar to Poly1305.

I have no security concerns for any of the three. I do have a few comments.

UMAC: Uses a large internal key (about 1KB), and complex code. UMAC has very high speed if key can be kept in cache. I suggested to the TLS mailing list VMAC as an alternative that uses less internal key and is of similar speed.

Salsa20/12: The estream variant under consideration is the 12-round one. All the fastest Salsa implementations are SIMD, and Salsa's prolog and epilog are complicated under SIMD. Dan Bernstein recognized this and made a SIMD-friendly variant called Chacha. Chacha also made a couple rotation tweaks that improve speed and (Dan speculates) improves security. I wish everyone would forget about Salsa and replace it with Chacha.

Poly1305: This is a standard polynomial evaluation hash with good security. As with UMAC and VMAC, it depends heavily on multiplication (in this case 128x128->256 bits followed by divisionless mod), making it expensive in hardware (same for UMAC and VMAC).

If all the TLS group wants is our security assessment of Salsa, UMAC and Poly1305, we should give them a positive one. If we wish to give some advice as well, I'd recommend consideration of VMAC over UMAC and, especially, Chacha over Salsa.

-Ted

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 8 Aug 2013 16:51:37 -0400

I concur, and second the recommendation to use Chacha instead of Salsa.

TNX!
-- 
Regards, 
Uri Blumenthal                           Voice: (781) 981-1638

On 8/8/13 16:24 , "Ted Krovetz" <[email-masked]> wrote:

>I am well familiar with all three. I edited the UMAC RFC, have been
>working with a Salsa variant called Chacha, and have used several
>polynomial hashes similar to Poly1305.
>
>UMAC: Uses a large internal key (about 1KB), and complex code. UMAC has
>very high speed if key can be kept in cache. I suggested to the TLS
>mailing list VMAC as an alternative that uses less internal key and is of
>similar speed.
>
>Salsa20/12: The estream variant under consideration is the 12-round one.
>All the fastest Salsa implementations are SIMD, and Salsa's prolog and
>epilog are complicated under SIMD. Dan Bernstein recognized this and made
>a SIMD-friendly variant called Chacha. Chacha also made a couple rotation
>tweaks that improve speed and (Dan speculates) improves security. I wish
>everyone would forget about Salsa and replace it with Chacha.
>
>Poly1305: This is a standard polynomial evaluation hash with good
>security. As with UMAC and VMAC, it depends heavily on multiplication (in
>this case 128x128->256 bits followed by divisionless mod), making it
>expensive in hardware (same for UMAC and VMAC).
>
>If all the TLS group wants is our security assessment of Salsa, UMAC and
>Poly1305, we should give them a positive one. If we wish to give some
>advice as well, I'd recommend consideration of VMAC over UMAC and,
>especially, Chacha over Salsa.
>
>-Ted
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Brown <[email-masked]>
Date: Fri, 9 Aug 2013 17:21:04 +0000

I cannot offer an expert opinion on these symmetric algorithms, only a
generic concern and a naïve question, both theoretical and tangential (to
the original thread).

Generic Concern

The proposal is in the form of: change from algorithm A to algorithm A or B.

(+) This improves security in the sense that if we know A or B is broken, we
can shut if off, and then use the other.

(-) If we do not know that A or B is broken, or if we cannot easily shut off
one, then the adversary can perhaps just attack the weakest choice of A or
B.

Arguably (+) already outweighs (-)., but furthermore, many crypto protocols,
including TLS, take two parties, perhaps one of whom can shut off A or B and
be presumed to be more knowledgeable.  In other words, one side can do (+)
to mitigate the (-) above on the other side, if the enforcement to use the
secure choice can be securely conveyed.

Naïve (and theoretical) Questions

How does TLS enable one side to enforce the choice of A or B? Does it use a
mechanism other than A or B?   For a concrete example, suppose a server
implements (+), choosing MAC algorithm A, shutting off B. In TLS, the server
does not sign the algorithm choice of A, right?  Consequently, if MAC
algorithm B is sufficiently broken, can an adversary fool the client into
using the broken MAC alg B, leveraging the fact that B is broken to
mis-authenticate the approval to use B?  A similar question might be asked
about the encryption algorithm.  So, I am concerned that, while the server
will not use the broken algorithms, then client is still at risk, because
the adversary can impersonate the server, or the else, the client leak
plaintexts to the adversary.  

I guess what I am suggesting that for (+) to successfully mitigate (-) as
outlined above, some method other than a broken algorithm should be used to
enforce the other side to use the unbroken algorithm.  In the case of TLS,
this may occur at the public key level, or pre-shared key.  Maybe TLS
already does this: I’ve misunderstood TLS several times already, so maybe my
concerns are unfounded.

Also, all this is not suggest that specific alg might be weak, as in the
hypothesis above, but rather to establish how much is gained by the change
to A or B. .Put another way, maybe AàB substitution I outlined is possible
only if B is disasterously weak, and we can be very confident that B is not
so weak, in which case there may be no downside to allowing A or B at all.
So, this is a theoretical question, not a practical question.  

Authentication of algorithm has already been discussed a few times on this
list and others, but I forget the conclusions.   

Best regards,

Dan

 

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Igoe, Kevin M.
Sent: Thursday, August 08, 2013 3:46 PM
To: [email-masked]
Subject: [Cfrg] Task for the CFRG

The TLS WG has asked the CFRG for their opinion for a stream cipher,
eSTREAM-SALSA20, 

and two MAC algorithms, UMAC and POLY1305, that have been suggested for use
in TLS

(draft-josefsson-salsa20-tls-02).  This was presented to the TLS WG at
IETF-87, slides can

The SALSA family works on blocks of 512 bits, and forms a key stream in
512-bit blocks by

applying a fixed map V^{512}->V^{512} to an input consisting of the key
(either 16 octets or

SALSA20 was one of the five finalists for a software stream cipher in the
eSTREAM

POLY1305 first showed up as POLY1305-AES, but all it needs from AES is a 16
byte block

of output. Adapting this to SALSA is straightforward. The 1305 in the name
reflects the

fact that it uses arithmetic modulo 2^{130} – 5.  See
http://cr.yp.to/mac/poly1305-20050329.pdf

Off the top of my head, the only objection I can see is that SALSA may be
difficult to

implement efficiently in hardware.  Hardware TLS acceleration can be useful
at heavily 

utilized servers.

The most current attempt to attack SALSA that I could find is a 2012 paper
on the IACR

e-print server.

                |              - Albert Einstein -

---

From: David McGrew <[email-masked]>
Date: Mon, 12 Aug 2013 09:23:27 -0400

Thanks Kevin for laying out the questions and background here; I have a
short comment inline:

On Thu, 2013-08-08 at 19:45 +0000, Igoe, Kevin M. wrote:
> be found at
> http://www.ietf.org/proceedings/87/slides/slides-87-tls-2.pdf.

The UMAC details evolved over the years, as people who have been in this
RG since 2005 will recall (as the RFC was reviewed on this list).

David

---

From: zooko <[email-masked]>
Date: Mon, 12 Aug 2013 23:34:59 +0400

Another point in favor of Salsa20 and especially ChaCha is that the latter
formed the core of the BLAKE candidate for SHA3. BLAKE was one of the three
most thoroughly-studied candidates in the SHA3 process (according to NIST's
final report ¹, the most "depthof analysis" was applied to BLAKE, Skein, and
Grøst).

¹ http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf

Of course, the requirements of a secure hash function aren't the same as those
for a cipher, but I still think that having all those cryptographers studying
that core function so closely, and not finding any major weakness in it when
used as a secure hash function, gives confidence that there isn't any major
weakness in it when used as a cipher.

Disclosure: I'm an author of a successor hash function based on BLAKE, named
"BLAKE2", but not an author of the original BLAKE. Here are my slides about
that, from ACNS'13, which includes a few quotes from the NIST report:

https://tahoe-lafs.org/~zooko/acns/slides.html

Regards,

Zooko

---

From: David McGrew <[email-masked]>
Date: Wed, 14 Aug 2013 16:32:36 -0400

This draft lists two motivations: RC4 security is inadequate, and the
performance of the symmetric cryptography in other ciphersuites is
inadequate.  I agree with the first premise, and the authors deserve
kudos for raising and starting to address the issue.   However, the
second premise is questionable.  The draft cites [AEAD-PERFORMANCE], and
that reference shows that the performance of AES-GCM and AES-CCM are
suboptimal in some scenarios, not that they are inadequate.  The draft
ought to cite some other work such as [1] to provide a broader viewpoint
on ciphersuite performance and deployment considerations of new
ciphersuites.   If it is the case that SALSA20 and UMAC (or POLY1305)
compellingly outperform existing ciphersuites on some particular client
environments and server environments, the draft should document the
particulars.  

The security question that we should be considering is: are the
authenticated encryption schemes defined in this draft sound?   The
strategy used in this draft is to rely on the "generic composition"
framework provided by TLS: a new GenericStreamCipher is defined and is
used at the same time as a TLS MAC algorithm, which is either the
conventional TLS HMAC or the new TLS UMAC algorithm defined in this
draft.   Thus, there is a merely a loose binding between authentication
and encryption, and a potential opportunity for a side channel attack
like the ones described in [CBC-ATTACK].  The draft recognizes the value
of resisting side channel attacks, but the loose binding approach works
against that goal.  Instead of defining a GenericStreamCipher, the draft
should define an AEAD algorithm, which would close the door on that sort
of vulnerability.  

One of the motivations for not using the TLS GenericAEADCipher mechanism
is that it appears only in TLSv1.2.  However, the draft proposes
extensions to both the GenericStreamCipher and MAC algorithms used by
TLSv1.0 and TLSv1.1, and it would be no more intrusive to those
protocols to define the use of GenericAEADCipher in them.  Using the
same AEAD mechanism for versions 1.0, 1.1, and 1.2 would result in
smaller and less complex implementation.   

There is ongoing work on authenticated encryption which this draft is
not taking advantage of, e.g. [2].  This could be a missed opportunity;
if the IETF is publishing new authenticated encryption schemes for TLS,
they should improve on the existing schemes.  For instance, the
ciphersuites in the draft do not provide any misuse resistance; they
have the same properties with respect to IV/nonce misuse as does
AES-GCM.   Granted that many GCM implementations successfully avoid
misuse, but several observers have identified misuse resistance as a
desirable property for future AEAD methods.  (See for instance [3] and
RFC 5297.)   A draft using an AEAD method based on SALSA20 that provides
misuse resistance of some kind would be more useful, and would be less
likely to become obsolete in the near future.  

Some more minor points below:

The draft has no mechanism to allow multiple encrypters to work in
parallel, such as is provided in Section 6.2 of RFC5288.

Previous AEAD work has chosen to not use the sequence number provided by
TLS (and other protocols) because of a lack of assurance that those
values will be unique.  This draft does use those sequence numbers,
which enables its ciphersuites to have less data overhead, but
introducing a potential vulnerability through mismanagement of sequence
numbers by TLS implementations.  

Slide 16 shown at IETF87 presents the shorter MAC size as having less
data overhead as compared with existing ciphersuites.   This is true,
but if compactness is a goal, AEAD schemes with less overhead could be
used instead.   (Some are defined already at [3].) 

I don't have anything against SALSA20, nor am I the best person to
assess its quality as a pseudorandom function.   

David, speaking as a research group member and not a research group
co-chair

[1] Gueron, S.  AES-GCM for Efficient Authenticated Encryption - Ending
the Reign of HMAC-SHA-1?  Workshop on Real-World Cryptography, 2013.  

[2] http://2013.diac.cr.yp.to/

[3] http://hyperelliptic.org/DIAC/slides/DIAC-mcgrew.pdf

[4] IANA AEAD Registry,
http://www.iana.org/assignments/aead-parameters/aead-parameters.xhtml

On Thu, 2013-08-08 at 19:45 +0000, Igoe, Kevin M. wrote:
> eSTREAM-SALSA20, and two MAC algorithms, UMAC and POLY1305, that have
> been suggested for use in TLS (draft-josefsson-salsa20-tls-02).  This
> was presented to the TLS WG at IETF-87, slides can be found at
> The SALSA family works on blocks of 512 bits, and forms a key stream
> in 512-bit blocks by applying a fixed map V^{512}->V^{512} to an input
> consisting of the key (either 16 octets or 32 octets), an 8-octet
> block counter, an 8-octet IV, and 16 constant octets.
>  
> SALSA20 was one of the five finalists for a software stream cipher in
> the eSTREAM contest run by ECRYPTII (see
> http://www.ecrypt.eu.org/stream/).
>  
> POLY1305 first showed up as POLY1305-AES, but all it needs from AES is
> a 16 byte block of output. Adapting this to SALSA is straightforward.
> The 1305 in the name reflects the fact that it uses arithmetic modulo
> 2^{130} – 5.  See http://cr.yp.to/mac/poly1305-20050329.pdf
> Off the top of my head, the only objection I can see is that SALSA may
> be difficult to implement efficiently in hardware.  Hardware TLS
> acceleration can be useful at heavily utilized servers.
>

---

From: Ben Laurie <[email-masked]>
Date: Mon, 19 Aug 2013 07:27:38 -0400

> implement efficiently in hardware.  Hardware TLS acceleration can be

This is a myth that should stop being repeated.

The only use of hardware acceleration is for attackers.

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 19 Aug 2013 08:45:33 -0700

> The only use of hardware acceleration is for attackers.

And this is an overgeneralization that should stop being repeated.

Hardware acceleration is used in firewalls because SSL decryption is often the biggest performance hit.  (You might consider these to be an attack, but none of the companies that purchase them do.)

--Paul Hoffman

---

From: Joachim Strömbergson <[email-masked]>
Date: Tue, 20 Aug 2013 08:23:20 +0200

Aloha!

Igoe, Kevin M. wrote:
> Off the top of my head, the only objection I can see is that SALSA
> may be difficult to implement efficiently in hardware.  Hardware TLS

And Salsa isn't that hard to implement in HW. ChaCha is better. But
compared to other eSTREAM profiles such as HC-128 (which is a pain to
implement efficiently in FPGAs) and Rabbit, Salsa is actually pretty ok.

- -- 
Med vänlig hälsning, Yours

Joachim Strömbergson - Alltid i harmonisk svängning.
========================================================================

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 22 Aug 2013 22:57:07 +0300

On Wed, Aug 14, 2013 at 11:32 PM, David McGrew <[email-masked]> wrote:

Hello,
 I believe your comments relate more to the ietf-tls rather than this list.
In any case some comments are in-line.

> environments and server environments, the draft should document the

I thought that it was generally accepted that salsa20 (or any other estream
candidate) outperform AES. There are benchmarks in the estream framework we
can link to [0] if it is deemed necessary.

[0]. http://www.ecrypt.eu.org/stream/perf/

> like the ones described in [CBC-ATTACK].

I don't understand why you think that. There is no padding involved in the
salsa20 ciphersuites, so the padding based  [CBC-ATTACK] (or any other
similar attack) do not apply. To my knowledge there is no known issue for
the mode used in salsa20/hmac or salsa20/umac in the draft.

The draft recognizes the value
> should define an AEAD algorithm, which would close the door on that sort

I don't quite understand that. Could you elaborate on the particulars? Why
do you think that the TLS GenericStreamCipher is vulnerable to side-channel
attacks (and the GenericAEADCipher is not?). I believe your comment is
towards the general constructions (and more precisely you mean the
GenericBlockCipher) rather than this particular ciphersuite.

> smaller and less complex implementation.

Only if you can work in clean slate. Unfortunately that doesn't happen in
practice. In practice one would add the ciphersuite in an existing
implementation that may not support TLS 1.2.

> parallel, such as is provided in Section 6.2 of RFC5288.

Actually RFC5288 needs this section because it uses a random nonce. Since
the salsa draft doesn't use a random nonce it doesn't require such a
special provision for parallel encryptors. Parallel encryptors come for
free in the salsa20 draft.

> numbers by TLS implementations.

TLS ensures that sequence numbers are unique. All of the TLS 1.x documents
mention specifically:
 "Sequence numbers are of type uint64 and may not exceed 2^64-1. Sequence
numbers do not wrap".

regards,
Nikos

---

From: zooko <[email-masked]>
Date: Fri, 23 Aug 2013 02:59:44 +0400

Very thorough and recent benchmarks including Salsa20, ChaCha, Salsa20/8, and
AES, are available here:

http://bench.cr.yp.to/results-stream.html

Regards,

Zooko

---

From: David McGrew <[email-masked]>
Date: Mon, 26 Aug 2013 11:49:42 -0400

Hi Nikos,

On Thu, 2013-08-22 at 22:57 +0300, Nikos Mavrogiannopoulos wrote:
>  I believe your comments relate more to the ietf-tls rather than this
> list. In any case some comments are in-line.
>  
> I thought that it was generally accepted that salsa20 (or any other
> estream candidate) outperform AES.  

If there is a compelling benefit to using these ciphersuites, it
deserves to be quantified.  

> There are benchmarks in the estream framework we can link to [0] if it
> is deemed necessary.
> 

It definitely would be good to reference the ESTREAM performance
comparisons, but the draft should also explain what platform(s) are the
performance targets.   Is the goal of the draft to minimize CPU
utilization, and thus power usage, on mobile clients, without regard to
servers?   Or perhaps there is another goal; I'm speculating here.

An example of why better documentation of the benefits is needed: in the
ESTREAM performance tables that you cite above, AES CTR uses fewer CPU
cycles than Salsa20 on some platforms, while Salsa20 uses fewer cycles
on some other platforms. 

> I don't understand why you think that. There is no padding involved in
> the salsa20 ciphersuites, so the padding based  [CBC-ATTACK] (or any
> other similar attack) do not apply. To my knowledge there is no known
> issue for the mode used in salsa20/hmac or salsa20/umac in the draft.
> 
> 
> I don't quite understand that. Could you elaborate on the particulars?
> Why do you think that the TLS GenericStreamCipher is vulnerable to
> side-channel attacks (and the GenericAEADCipher is not?). I believe
> your comment is towards the general constructions (and more precisely
> you mean the GenericBlockCipher) rather than this particular
> ciphersuite.
> 

One of the important properties of a sound authenticated encryption
scheme is that the decryption operation does not release any
(potentially invalid) plaintext data until the authentication check is
complete.  The GenericStreamCipher does not require an implementation to
have this property.  Experience with AEAD has shown that implementers
are sometimes reluctant to comply with the requirement to not release
post-decryption, pre-verification plaintext, even when the specification
is quite clear on that point.  

> Only if you can work in clean slate. Unfortunately that doesn't happen
> in practice. In practice one would add the ciphersuite in an existing

The point that I wanted to make is: instead of re-defining the
GenericStreamCipher and MAC algorithms for TLS v 1.0 and 1.1,
GenericAEADCipher can be added to those versions of the protocol.   That
would enable a TLS implementation that supports the current version of
the protocol to use its GenericAEADCipher for all three versions, and
relieve that implementation of the need to support an updated definition
for GenericStreamCipher and MAC.

> Actually RFC5288 needs this section because it uses a random nonce.

No, RFC5288 uses a deterministic nonce.

>  Since the salsa draft doesn't use a random nonce it doesn't require
> such a special provision for parallel encryptors. Parallel encryptors
> come for free in the salsa20 draft.
> 

No, each Salsa20 nonce MUST be distinct, and the draft makes no
provision to ensure that they can be distinct when multiple encrypters
are in use.  Rather than being "for free", the draft provides no way to
allow for an implementation to use parallel encryptors and to maintain
security.  

regards,

David

> TLS ensures that sequence numbers are unique. All of the TLS 1.x
> documents mention specifically:
> 
>  "Sequence numbers are of type uint64 and may not exceed 2^64-1.
> Sequence numbers do not wrap".
> 
> 
> 
> regards,
> Nikos
> 
>

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 28 Aug 2013 17:45:15 +0300

> servers?   Or perhaps there is another goal; I'm speculating here.

Hello David,
 I don't think that this is the purpose of this draft. This draft merely
defines how to use salsa20 in TLS. There is a lot of controversy on whether
a cipher is fast/slow or whatever on a particular platform (depending on
the implementation, power usage), and personal taste :) If we'd try to
quantify those things in this draft it would take more effort and heat than
needed. If as you imply salsa20 is not as fast in some platforms, then
things are simple, it will not be used in those platforms. The intention is
to define salsa20 to be used in the platforms that is faster than AES.

> have this property.

I believe that you have misunderstood how the GenericStreamCipher operates
in TLS. No TLS implementation releases plaintext data that have not been
authenticated in GenericStreamCipher or any other mode. This was one of the
initial goals in TLS, and that is the reason that (unlike IPSec) there
aren't any ciphersuites that do not provide authentication.

> for GenericStreamCipher and MAC.

That is a nice idea, and we can consider this option when this is done.
However, as you previously argued it would be good to have a
GenericAEADCipher that uses the TLS sequence numbers instead of another
explicit nonce to save bytes.

> No, RFC5288 uses a deterministic nonce.

As far as I understand RFC5288 doesn't use a deterministic nonce. It allows
the implementer to use any nonce he likes. It merely suggests (with a MAY)
to copy the TLS sequence number as nonce.

> allow for an implementation to use parallel encryptors and to maintain

I don't quite understand your objection. Since each TLS record has a
distinct and unique sequence number (and thus nonce), it is pretty
straightforward to map each record on a different CPUs for encryption.
There is nothing non-obvious needed to clarify there (unless I don't
understand your point).

regards,
Nikos