Subject: [Cfrg] misuse-resistant AEAD (was: Re: CFRG and thwarting pervasive montoring)

From: David McGrew <[email-masked]>
Date: Thu, 02 Jan 2014 10:03:16 -0500

Hi Paul,

On 12/30/2013 02:06 PM, Paul Lambert wrote:
>
> On 12/29/13, 1:12 PM, "Paul Hoffman" <[email-masked]> wrote:
>
>> On Dec 29, 2013, at 11:12 AM, Stephen Farrell <[email-masked]>
>> wrote:
>>
>>> . . .
>>> I would love to see ongoing detailed work within
>>> CFRG as to how to counter pervasive monitoring.
>> Wearing your perpass hat, how can CFRG help? I ask this because I have
>> seen little on the perpass mailing list that indicated that an even minor
>> problem has been lack of crypto, or the use of crypto that is thought to
>> be breakable. What type of crypto research or assessment would help
>> perpass?
> In the past I¹ve never considered CFRG a viable discussion forum for
> making an impact by creating or approving new algorithms Š but if it is:
>
> 	We need an Œapproved' nonce-insensitive AEAD algorithm.
>
> I¹m designing multicast communications in a mesh topology and CCM and GCM
> suffer from N^2 complexity (since they require unique nonce/key).  Yes Š
> there are ways that some link proposals like 802.1ae mitigate the issue
> using device addresses as part of the key setup.  The best solution is a
> nonce-insensitive AEAD.
I agree.   The best solution would be an authenticated encryption 
algorithm that did not require a nonce as input.   An alternative which 
is not quite as good would be an algorithm that requires a nonce as 
input, but which has security that suffers only a minimal degradation if 
nonces are repeated.

> We already have an RFC for SIV which is deterministic and a decent
> solution, but it is not ŒNIST¹ approved, so I have problems introducing it
> into consumer equipment.  It¹s also a little slow Š but I¹m not sure that
> efficiency should be the primary evaluation criteria.

All valid points.   SIV shows that it is possible to have a 
misuse-resistant algorithm.  It may not have all of the properties that 
one might want in an algorithm (for instance: more amenable to parallel 
processing), but it shows that we can achieve more robust security than 
nonce-based AEAD.

>
> I¹ve asked NIST in the past and they have expressed no interest in the
> problem.  It used to be very important for algorithms to be NIST approved.
>   Do we need to find/create a new review and approval process for
> algorithms that can be referenced by commercial products?

NIST is responsive when the industry and standards organizations adopt 
new mechanisms that have some clear advantage over previous 
mechanisms.   The problem is that NIST and the industry have gotten into 
a deadlock (or deadly embrace) situation: the industry now hesitates to 
adopt algorithms that are not NIST approved, and NIST hesitates to 
approve algorithms that have not seen any adoption by industry or 
standards.    We can not just blame NIST for being overly conservative 
here; there are many more algorithm proposals than they could reasonably 
incorporate into their processes.   To break the deadlock, we (CFRG and 
the industry) need to be willing to adopt a new algorithm, or at least 
we need to be willing to take further steps towards adoption than we 
have shown in the past. Some things that CFRG could do: write a 
requirements document that demonstrates the need for a new algorithm, 
publish a document specifying the new algorithm, document the fact that 
there is a set of adopters or potential adopters that are interested, 
and lastly, reach out to NIST (for instance, with a question like "do 
you have any particular concerns about this algorithm that would prevent 
you from approving it?").

Going further, it might facilitate adoption if all of the information 
needed to validate an implementation of an algorithm were provided.   
That is, a complete set of test cases in a format suitable for automated 
validation (as done in the NIST Crypto Module Validation Program, or 
CMVP) would make it easier to incorporate the algorithm in an 
implementation-validation process.

The CMVP is run jointly by the U.S. and Canada.   It would be good to 
hear from the rest of the world on this topic.  I suspect that many 
vendors outside of Northa America want to sell into the NA market, and 
thus also would favor NIST approval of new algorithms. What is less 
clear is the role of nation-specific block ciphers (or other 
algorithms), which is a topic unto itself.

David

>
> Paul
>
>
>
>
>
>
>
>> Note that deprecating the use of crypto that is widely known to be broken
>> is the purview of IETF WGs, not the CFRG. The relevant WGs (particularly
>> TLS) seem to already be doing that.
>>
>> --Paul Hoffman
>> _______________________________________________
>> Cfrg mailing list
>> [email-masked]
>> http://www.irtf.org/mailman/listinfo/cfrg
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 2 Jan 2014 10:31:20 -0500

On Jan 2, 2014 10:03 AM, "David McGrew" <[email-masked]> wrote:
>>> On Dec 29, 2013, at 11:12 AM, Stephen Farrell <[email-masked]
>
>>> wrote:
>>>
>>>> . . .
algorithm that did not require a nonce as input.   An alternative which is
not quite as good would be an algorithm that requires a nonce as input, but
which has security that suffers only a minimal degradation if nonces are
repeated.

Already exists: it's called CBC mode with HMAC. IVs are random and can
repeat.
> All valid points.   SIV shows that it is possible to have a
misuse-resistant algorithm.  It may not have all of the properties that one
might want in an algorithm (for instance: more amenable to parallel
processing), but it shows that we can achieve more robust security than
nonce-based AEAD.

Deterministic encryption leaks considerable information when used on low
entropy messages. Nonce reuse resistant nonce based MAC and encryption
algorithms exist today, namely CBC initialized with the encryption of a
counter and HMAC.

> NIST is responsive when the industry and standards organizations adopt
new mechanisms that have some clear advantage over previous mechanisms.
The problem is that NIST and the industry have gotten into a deadlock (or
deadly embrace) situation: the industry now hesitates to adopt algorithms
that are not NIST approved, and NIST hesitates to approve algorithms that
have not seen any adoption by industry or standards.    We can not just
blame NIST for being overly conservative here; there are many more
algorithm proposals than they could reasonably incorporate into their
processes.   To break the deadlock, we (CFRG and the industry) need to be
willing to adopt a new algorithm, or at least we need to be willing to take
further steps towards adoption than we have shown in the past. Some things
that CFRG could do: write a requirements document that demonstrates the
need for a new algorithm, publish a document specifying the new algorithm,
document the fact that there is a set of adopters or potential adopters
that are interested, and lastly, reach out to NIST (for instance, with a
question like "do you have any particular concerns about this algorithm
that would prevent you from approving it?").

CAESAR is going on right now with regards to AE. If you have requirements
that haven't been in the call, tell us about them.

> Going further, it might facilitate adoption if all of the information
needed to validate an implementation of an algorithm were provided.   That
is, a complete set of test cases in a format suitable for automated
validation (as done in the NIST Crypto Module Validation Program, or CMVP)
would make it easier to incorporate the algorithm in an
implementation-validation process.
> The CMVP is run jointly by the U.S. and Canada.   It would be good to
hear from the rest of the world on this topic.  I suspect that many vendors
outside of Northa America want to sell into the NA market, and thus also
would favor NIST approval of new algorithms. What is less clear is the role
of nation-specific block ciphers (or other algorithms), which is a topic
unto itself.
> David

Sincerely,
Watson

---

From: David McGrew <[email-masked]>
Date: Thu, 02 Jan 2014 12:07:08 -0500

On 01/02/2014 10:31 AM, Watson Ladd wrote:
>
>
> On Jan 2, 2014 10:03 AM, "David McGrew" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> > Hi Paul,
> >
> >> On 12/29/13, 1:12 PM, "Paul Hoffman" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >>
> >>> On Dec 29, 2013, at 11:12 AM, Stephen Farrell 
> <[email-masked] <mailto:[email-masked]>>
> >>> wrote:
> >>>
> >>>> . . .
> algorithm that did not require a nonce as input.   An alternative 
> which is not quite as good would be an algorithm that requires a nonce 
> as input, but which has security that suffers only a minimal 
> degradation if nonces are repeated.
>

This combination of algorithms doesn't require a distinct nonce, and it 
can be secure if the encoding and IV generation is done correctly, but 
it lacks other desirable properties.   For instance, it uses serialized 
computations, expands the data a lot, is not robust against misuse of 
decrypted data prior to verification.

If you are interested in seeing that combination of algorithms used 
more, you should review draft-mcgrew-aead-aes-cbc-hmac-sha2 and offer 
your support, or suggestions for improvements.   My opinion of that 
draft: it would be better if the IVs were generated pseudorandomly and 
if ciphertext stealing were used (to avoid side channels on the 
decryption side).    There are better algorithms, so it is not clear how 
much effort the industry should spend on doing the combination of CBC 
and HMAC better.

> misuse-resistant algorithm.  It may not have all of the properties 
> that one might want in an algorithm (for instance: more amenable to 
> parallel processing), but it shows that we can achieve more robust 
> security than nonce-based AEAD.
> >
>
> Deterministic encryption leaks considerable information when used on 
> low entropy messages.
>

Right, and I'm not advocating such things.

> Nonce reuse resistant nonce based MAC and encryption algorithms exist 
> today, namely CBC initialized with the encryption of a counter and HMAC.
>
> >>
> > NIST is responsive when the industry and standards organizations 
> adopt new mechanisms that have some clear advantage over previous 
> mechanisms.   The problem is that NIST and the industry have gotten 
> into a deadlock (or deadly embrace) situation: the industry now 
> hesitates to adopt algorithms that are not NIST approved, and NIST 
> hesitates to approve algorithms that have not seen any adoption by 
> industry or standards.    We can not just blame NIST for being overly 
> conservative here; there are many more algorithm proposals than they 
> could reasonably incorporate into their processes.   To break the 
> deadlock, we (CFRG and the industry) need to be willing to adopt a new 
> algorithm, or at least we need to be willing to take further steps 
> towards adoption than we have shown in the past. Some things that CFRG 
> could do: write a requirements document that demonstrates the need for 
> a new algorithm, publish a document specifying the new algorithm, 
> document the fact that there is a set of adopters or potential 
> adopters that are interested, and lastly, reach out to NIST (for 
> instance, with a question like "do you have any particular concerns 
> about this algorithm that would prevent you from approving it?").
> >
>
> CAESAR is going on right now with regards to AE. If you have 
> requirements that haven't been in the call, tell us about them.
>

Yes, I will.   I'm on the CAESAR review committee, and I'm a fan of many 
aspects of the program.   The call for submissions allows a submission 
to use a deterministic nonce, and that might be OK in some situations, 
but there are other situations where it is highly undesirable.   The 
call also allows submissions that don't use a deterministic nonce.   
This inclusiveness is clearly the right thing for CAESAR.   But what the 
world needs more of are algorithms in the latter category, or at least 
algorithms that are more robust against misuse.

David

> > Going further, it might facilitate adoption if all of the 
> information needed to validate an implementation of an algorithm were 
> provided.   That is, a complete set of test cases in a format suitable 
> for automated validation (as done in the NIST Crypto Module Validation 
> Program, or CMVP) would make it easier to incorporate the algorithm in 
> an implementation-validation process.
> >
> > The CMVP is run jointly by the U.S. and Canada.   It would be good 
> to hear from the rest of the world on this topic.  I suspect that many 
> >>> [email-masked] <mailto:[email-masked]>
> >> [email-masked] <mailto:[email-masked]>
> > [email-masked] <mailto:[email-masked]>

---

From: David McGrew <[email-masked]>
Date: Thu, 02 Jan 2014 15:53:58 -0500

Hi Trevor,

On 12/27/2013 10:56 AM, Trevor Perrin wrote:
> On Tue, Dec 24, 2013 at 9:57 AM, David McGrew <[email-masked]> wrote:
> [...]
>>>> As far as Kevin's
>>>> competence goes, your complaint needs to be balanced against his
>>>> contributions.
>>> I've looked over his mailing list contributions.
>>>
>>> Kevin seems unfamiliar with sidechannel attacks, RSA padding, provable
>>> security, key agreement protocols, and consulting academic literature.
>>>    I'm sure he's good at math, but I don't see the breadth of knowledge
>>> I'd expect for his position.
>>>
>>> His messages don't reflect a high standard of diligence.  He's made
>>> significant mistakes with Dragonfly.  His tone reminds me of a bemused
>>> hobbyist who doesn't care whether any of this is secure.
>>>
>>> I believe there are people who could do a better job.
>>
>> I respectfully disagree with your characterization.   I would guess that if
>> you could have been present for the discussion at the RG meeting, you might
>> feel differently.
> Which discussion?  The only substantial discussion of Dragonfly at a
> CFRG meeting appears to be at IETF 83.  Is that what you're referring
> to?
>
> http://www.ietf.org/proceedings/83/minutes/minutes-83-cfrg.txt
>
>
>> Let me make an aside about provable security. In the crypto practice
>> community, it is often regarded as oversold.
> As a member of the "crypto practice community" I disagree.  Key
> agreement protocols are widely understood to be a tricky area where
> formal analysis is crucial.  Dragonfly's lack of such analysis was a
> red flag.  Jonathan Katz, a world-class cryptographer, raised the
> issue repeatedly.  The CFRG chairs ignored him and endorsed Dan
> Harkins' bluster.
>
> http://www.ietf.org/mail-archive/web/cfrg/current/msg03053.html
> http://www.ietf.org/mail-archive/web/cfrg/current/msg03216.html
>
> Seems like CFRG could use more outreach to the cryptography community
> and less to the intelligence community.

I agree, more outreach to the theory community would be valuable. 
Perhaps you would be interested in helping with that effort?

>
>
>>> You seem to be arguing that intelligence agencies are the only people
>>> who would propose someone for CFRG chair.
>>>
>>> I'm not sure that's true.
>>
>> I agree that it is not true; it is an overstatement.  But it is a fact that
>> intelligence agencies have a lot of the talent that will show up at a venue
>> like this, and that those organizations are able to justify the cost of
>> ongoing professional participation.
> I see.  That's terrifying.
>
>
>>> Perhaps CFRG should follow an actual
>>> process for selecting its chairs.  Kevin or anyone else would be
>>> welcome to participate.
>>
>> Do I understand you correctly to say that you would accept Kevin as a
>> co-chair if he was selected through some sort of official process, other
>> than affirmation by the RG?
> If the IETF/IRTF community endorses Kevin through an open process I'd
> give up participating in IETF/IRTF any further.  That's not
> "acceptance", but you wouldn't have to listen to me any more.

I hope that you stay engaged with CFRG over the long term and help it do 
useful work.

>
>
>>>> What about someone in the role
>>>> of a document author or co-author? Would you ask that Sean Shen step down
>>>> as
>>>> co-author of draft-irtf-cfrg-cipher-catalog-01, for instance? I hope not,
>>>> but these are important questions to consider.
>>> No one proposed that.
>>
>> I didn't mean to suggest that you said that, but I did want to ask. If the
>> IRTF decides to establish a policy that is based on an RG member's employer,
>> as you are advocating, it would be best to establish the entire policy up
>> front, rather than debate each case as it comes up.
> I'm not advocating a formal policy.  I believe the selection (or
> removal) of chairs involves weighing many factors, and is best handled
> on a case-by-case basis.

I think we are in agreement here.

>
>
>> If we really did want to exclude people from intelligence agencies while not
>> setting a formal policy to that effect, we could achieve that goal by
>> crafting a policy that demands more transparency than an intelligence agency
>> would be comfortable with.   For instance, the policy could require the
>> publication of all of the contributor's publications, regardless of whether
>> or not they have been classified, or it could require that the contributor
>> sign a statement regarding transparency that their employer would never
>> agree to.   But note that if we did this, it would not solve any problems,
>> because an intelligence agency could always work through contractors or
>> other people who are on their payroll, but do not admit to being on their
>> payroll.
> I think those are bad ideas which would not prevent sabotage and would
> burden innocent contributors.

I think you are right.   I kind of like the idea of having a statement 
of purpose of CFRG that contributors need to agree to, but it would not 
be addressing any of the problems that people care most about.

>
>
>>>    For the CFRG chairs this has
>>> included handling an important security flaw prior to public
>>> disclosure [2].
>>
>> What do you mean by this?   Are you saying that the CFRG chairs mishandled
>> the Lucky-13 disclosure?
> No.  From what I can tell Kenny Paterson handled it well.
>
> But amongst those defending Kevin, a major theme seems to be that
> trustworthiness and expertise is not important for IETF/IRTF chairs
> since they're presiding over an open process.
>
> I disagree since chairs wield a great deal of power in the IETF/IRTF
> process.  The "Lucky 13" disclosure highlights an additional duty
> which has been entrusted to CFRG chairs and which is hard to audit.

I think that you are overestimating the power of a research group 
chair.  But I do think that trustworthyness and expertise are important.

>
>
>>>> [IGOE_2] ends with the statement "Many thanks to Rene Struik and Scott
>>>> Fluhrer for their insightful comments. Would anyone else on the list like
>>>> to
>>>> join in? We can’t learn from our mistakes until we realize we’ve made
>>>> them."
>>>> I have a hard time seeing this message as steering the RG in an
>>>> unfruitful
>>>> direction.
>>> That's [IGOE_3].  See the paragraph preceding your quote.  "steering
>>> the RG in an unfruitful direction" is exactly how I'd describe it.
>>
>> If I understand you, the paragraph is Kevin's summary of Scott's improvement
>> to Dan's protocol.   To me, that paragraph, followed by the request for
>> review, looks like an RG chair that is seeking to stimulate discussion.
> That's a good description.  But so is your phrase "steering the RG in
> an unfruitful direction".  Kevin's paragraph is below:
>
> """
> Scott Fluhrer proposed an elegant change to DragonFly that fixes this.
>   In the EC case, replace
> the while-loop with a for-loop, say “for t = 1,,,,40”.  On each pass
> through this for-loop generate
> a possible x- coorodinate as in DragonFly,  saving off the first x
> value which corresponds to a
> point on the curve.  The only thing that can go wrong here is doing
> all 40-iterations without
> finding a good x-coordinate.  This is quite unlikely to occur (~
> 10^-12), but when it does occur
> it gives 40 bits of information about the password.  In some VERY high
> volume applications it
> might be prudent to choose a value larger than 40.
> """
>
>
>>>>> He also endorsed an ineffective attempt to avoid
>>>>> timing attacks by adding extra iterations to one of the loops [IGOE_3,
>>>>> IGOE_4].
>>>>
>>>> I think that by "ineffective attempt to avoid timing attacks" you are
>>>> referring to your statement that "within each loop are conditional
>>>> branches
>>>> and Legendre symbol / square-root algorithms, which are hard to implement
>>>> efficiently in constant time ([STRUIK], [ICART], [FIPS186-4])" from
>>>> [REVIEW]. Is this right? There is a significant difference between "hard
>>>> to
>>>> implement" and "ineffective". The statement in [REVIEW] makes it sound
>>>> like
>>>> it is inconvenient for the implementer, while the statement in your email
>>>> makes it sound as though it is impossible.
>>> Not sure I understand this quibble.
>>
>> The important point here is that a Research Group chair reading [REVIEW]
>> could get the impression that the proposed mitigation to timing attacks is
>> "hard to implement" rather than "ineffective", in your opinion.
> I'm still not sure what you're asking.  Let's just look at a crude
> analysis of the "40-loops" countermeasure Kevin endorsed, comparing
> CFRG draft-00 vs draft-01/draft-02.
>
> Let's assume that modular square roots are calculated via modular
> exponentiation, and that Legendre symbol calculations take less time.
> Let's also ignore the variable time taken by a Legendre symbol
> calculation and other conditional logic, and just count the number of
> ops.
>
> In draft-00, the hunt-and-peck loop in 3.2.1 performs Legendre symbol
> calculations until it finds a square (probability ~1/2), at which
> point a square root is performed.  So:
>   - 1 modular exponentiation
>   - Variable number of Legendre symbol calculations
>     - geometric distribution with mean ~2, variance ~2
>
> In draft-01 and draft-02, the hunt-and-peck loop continues until it
> completes 40 loops, with a probability ~1/2 of performing a modular
> exponentiation on each iteration.  So:
>   - Variable number of modular exponentiations
>     - binomial distribution with mean ~20, variance ~10
>   - 40 Legendre symbol calculations
>
> The 40-loops algorithm was intended to reduce timing variance but
> instead increases it, and increases computation cost as well.  So I
> think "ineffective" is a fair description.  Do you agree?

I don't have the time right now to go back to the earlier version of the 
draft and check all of this, and I want to get back to you sooner rather 
than later.   So let me comment here as a chair, rather than a technical 
reviewer.  What would have been most useful is for this analysis to have 
been presented to the CFRG mail list during the discussion of timing 
attacks that initially took place on December 2012, or after Kevin put 
out a Last Call for comments on Dragonfly on April 4, 2013.   For 
perspective: Rene Struik's comments on that draft went out on Nov 29, 
and yous went out on Dec 10, over six months after the last call for 
comments.

David

>
>
>>>>> 4)  Kevin's NSA affiliation raises unpleasant but unavoidable
>>>>> questions regarding these actions.  It's entirely possible these are
>>>>> just mistakes by a novice chair who lacks experience in a particular
>>>>> sort of protocol and is being pressured by IETF participants to
>>>>> endorse something.
>>>>
>>>> Yes, I agree: It's entirely possible these are just mistakes by a novice
>>>> chair who lacks experience in a particular sort of protocol and is being
>>>> pressured by IETF participants to endorse something.
>>> I think CFRG deserves a chair who would be informed enough to
>>> understand these areas, and diligent enough not to make the technical
>>> and process mistakes that Kevin did.
>>
>> Of course we need informed and diligent chairs.   But when we are
>> establishing the criteria that we expect from the CFRG chairs, we need to
>> keep in mind that the higher that we set the bar, the fewer the candidates
>> that will be qualified and interested.   It would be wrong to set an
>> expectation that each email that attempts to summarize the on-list
>> discussion must be free from flaws, for instance.
> Sure.  Crypto's hard.  Mistakes happen.  But I'm uncomfortable with
> the volume of mistakes in Kevin's handling of Dragonfly:
>   * Endorsing Dragonfly despite better alternatives in the literature
>   * Twice suggesting a way of deriving the DH generator which makes the
> protocol breakable
>   * Endorsing an ineffective timing-attack countermeasure
>   * Misrepresenting CFRG consensus to TLS WG
>
>
> Trevor
> .
>

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 2 Jan 2014 14:06:31 -0800 (PST)

> Already exists: it's called CBC mode with HMAC. IVs are random and can

  There are still security sensitive requirements on IVs in CBC mode.
Namely, they have to be unpredictable to the attacker. That problem does
not exist with SIV. The nonce is completely arbitrary, it can be a counter,
pseudo-random material, it can be partially derived, it can repeat or not.

  And as a formal AEAD construction SIV avoids the ad hoc nature in which
CBC plus HMAC has been put together in the past. It also has a nice and
fixed API for things like passing AAD as a vector of inputs.

>>> solution, but it is not ŒNIST¹ approved, so I have problems
>>> introducing
> it
> one

  With SIV, authenticity remains and the leakage is limited to knowledge
that the plaintext equals a prior plaintext, and that is further constrained
by the fact that it's the same plaintext plus the same AAD, if the AAD
changes (due to a message header that encapsulates the encrypted blob
being different) then there is no leakage.

  It really is the "swiss army knife" of crypto tools-- it slices, it dices,
it provides misuse-resistant AEAD, it does key wrapping with AAD!
(And it has a security proof behind it too).

  regards,

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 2 Jan 2014 17:26:21 -0500

> fixed API for things like passing AAD as a vector of inputs.

CBC+HMAC is an instance of generic composition. So is GCM and
Chacha/Salsa/XSalsa/Poly1305.
What sort of device can encrypt, but not use a PRNG or count?

> (And it has a security proof behind it too).

It's wonderful, but slow as molasses. 2 AES passes, only 1 of which
can be parallelized.
For the example of mesh networking it certainly has a place, but I
don't know if the security
is really that great for that application.

For example, imagine a simple message format with (sender, dest) as
header and a temperature as
the message. A mesh network passing around temperature measurements
will reveal a lot to a passive attacker:
remember temperatures are continuous, so all you need is the direction
change the same or different as before to
see just about everything.

Add a counter and everything is golden. But you need that counter. And
if you have a counter, nonce-based misuse-resistant
is just fine, and moreover can be done faster than SIV at the cost of
leaking common prefixes.

Authenticity doesn't make sense with repeated nonces. All you get is
the attacker cannot introduce new messages, but
they can still repeat old ones. This can be enough to have some fun.

>   Dan.
Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 2 Jan 2014 23:06:15 -0800 (PST)

On Thu, January 2, 2014 2:26 pm, Watson Ladd wrote:
>>> is

  It's not that the device is incapable of using a PRNG or counting, it's
that the device is using a generic composition that provides security
in a tight boundary that falls apart outside that boundary. That is
coupled with knowledge that such a device will be used and configured
and managed by humans, many of whom do not understand the
boundary, or worse they think they understand it when they don't.

  Dan.

---

From: David McGrew <[email-masked]>
Date: Fri, 03 Jan 2014 09:07:10 -0500

> Chacha/Salsa/XSalsa/Poly1305.

A minor correction: GCM isn't a generic composition in the original 
sense of Bellare and Namprempre.   The same block cipher key is used 
both for encryption and authentication, and the particulars about what 
counter block is used during the encryption of the GHASH value matter, 
and are "coordinated" with the encryption operation.

David

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 3 Jan 2014 17:01:46 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Trevor Perrin
> Sent: Friday, December 27, 2013 10:57 AM
> To: David McGrew (mcgrew)
> Cc: [email-masked]; [email-masked]
> Subject: Re: [Cfrg] Requesting removal of CFRG co-chair
> 
> 

I think we agree that what Dan specified in the draft is broken.  However, I believe that's because Dan got it wrong (and I was busy elsewhere, and did not review the draft).

I believe my suggestion is an improvement (but still needs caution; the checking if x^3+ax+b is a QR must be done in constant time, or in random time via blinding; I believe that in this case blinding is easier).

Now, I believe the issue is 'did Kevin endorse my suggestion, or did he endorse Dan's implementation?'

For the record, a better implementation of my suggestion in dragonfly would be:

       found = 0
       counter = 1
       n = len(p) + 64
       do {
         base = H(max(Alice,Bob) | min(Alice,Bob) | password | counter)
         temp = KDF-n(seed, "Dragonfly Hunting And Pecking")
         seed = (temp mod (p - 1)) + 1
         if (seed < p)
         then
           x = seed
           if ( (x^3 + ax + b) is a quadratic residue mod p)
           then
             found_x = x
             found = 1
           fi
       } while((found == 0) || (counter < k))

       x = found_x
       y = sqrt(x^3 + ax + b)
       if (lsb(y) == lsb(base))
       then
         PE = (x,y)
       else
         PE = (x,p-y)
       fi

(this stops on the last acceptable 'x' value found; you could try to select the 'middle-value'; I picked the last because it was the easiest to specify).

As for determining if a value is a QR, the easiest way to do it without leaking any information in the time taken would be to blind the value randomly, as in:

    temp = (x^3 + ax + b mod p)
    r = 1 + random(p-2)      /* Random value between 1 and p-1) */
    temp = (temp * r * r) mod p
    if random(2)                   /* 0.5 chance */
        temp =  (temp * qr) mod p
        bit = 0
    else
        temp =  (temp *qnr) mod p
        bit = 1
    fi
    /* At this point, temp takes on all values between 1 and p-1 with equal probability */
    output = bit ^ legendre_symbol(temp, p)

where qr, qnr are fixed values which are respectively a quadric residue, and quadratic nonresidue mod p, and are the same size (and so the multiplications take the same amount of time).

---

From: David McGrew <[email-masked]>
Date: Fri, 03 Jan 2014 17:26:47 -0500

Hi Trevor,

> think "ineffective" is a fair description.  Do you agree?

I compared version 00 against version 01 using the IETF diff tool:

http://www.ietf.org/rfcdiff?url1=draft-irtf-cfrg-dragonfly-00&difftype=--html&submit=Go!&url2=draft-irtf-cfrg-dragonfly-01

The only change in the algorithm that you cite (Sections 3.2.1 and 
3.2.2.) is the change in the conditional statement that you mention.

If  the condition "((x^3 + ax + b) is a quadratic residue mod p)" is 
checked using an efficient method such as the legendre/jacobi symbol, 
which takes significantly less time than the execution of the branch "y 
= sqrt(x^3 + ax + b)", then the number of times that the branch executes 
will be detectable to an attacker.   This will give an attacker 
information about the password.   So in this case, I agree, versions 01 
and 02 seem more vulnerable than version 00 to timing attacks.

But an alternative way to implement the algorithm would be to use Shanks 
method for computing square roots mod p, or an algorithm like it, which 
upon termination either outputs the square root or an indication that 
the number that was input is not a quadratic residue.   In this case, 
version 01 could be less vulnerable to timing attacks than version 00.   
(I would guess this is what Dan had in mind.)

Clearly, this algorithm is not specified well enough in the draft to 
ensure that it will be implemented in a way that resists timing 
attacks.   Additionally, the most efficient way to implement the 
algorithm in the draft (using the legendre symbol) would lead to 
vulnerabilities.   These are significant problems.

On the subject of Kevin's influence, here is the timeline:

Dec 13 2012.   Kevin summarizes the Dragonfly status, asks for input, 
and is the first person to describe the need for Dragonfly to resist 
timing attacks.   He proposed a solution.   Scott Fluhrer pointed out a 
problem with the proposal, and suggests instead the "40 loop" fix.

Dec 17.   Kevin again summarizes the Dragonfly status, suggests adopting 
Scott's fix, and calls for feedback.   Dan Harkins responds that 
draft-tls-pwd (a different specification of Dragonfly) already has an 
equivalent fix.

Dec 18 2012.   Scott points out that the Dragonfly spec needs to be more 
clear on its use of the fix, and suggests computing the legendre/jacobi 
symbol instead of computing an actual square root.

However, Scott's suggestions were not picked up in 
draft-irtf-cfrg-dragonfly.   In retrospect, it seems that Dan did not 
understand the points that Scott was trying to make, and there was no 
follow up from anyone in the RG to make sure that the changes had been 
done, quite possibly because people assumed that the fix actually was 
equivalent.    Scott has clarified on the list recently, with the 
essential point being that the square root computation can be moved 
outside of the while loop.  (As a side note: it would simplify this 
computation if p = 3 (mod 4).)

I suspect that Dan is assuming that something like Shank's method will 
be used.   Your analysis assumes that the Legendre/Jacobi symbol will be 
used.    Note, however, that the suggestion to use that computational 
method came after Kevin's suggestion to use the "40 loop" fix.

Having participated in some of the off list conversations about 
Dragonfly, and having recently reviewed the discussions on the mail 
list, it seems to me that Kevin's input was an effort to promote 
positive changes, review, and discussion, and not an attempt to subvert 
the protocol.    I note that Kevin was the first to point out that 
resisting timing attacks was a goal, and he called for review 
repeatedly.   If he had wanted to influence the protocol without 
arousing suspicion, a far more effective way to have done that would 
have been to send private emails to Dan asking for changes to the draft.

If you have more questions about what Kevin did and why, please direct 
them to him.

regards,

David

---

From: Trevor Perrin <[email-masked]>
Date: Fri, 3 Jan 2014 18:43:16 -0800

On Thu, Jan 2, 2014 at 12:53 PM, David McGrew <[email-masked]> wrote:
> I agree, more outreach to the theory community would be valuable. Perhaps
> you would be interested in helping with that effort?

Sure, my advice:  There's a wealth of knowledge in academia that CFRG
is not tapping.  Having a CFRG co-chair who could serve as ambassador
to that community and a translator of its knowledge would be very
valuable.

I'd recommend talking to some of the academic cryptographers who've
engaged with TLS and CFRG (Jonathan Katz, Kenny Paterson, Douglas
Stebila, David Wagner, etc), and see where that leads you.

Also, this would be a good discussion to pursue at Real World Crypto
(NYC, shortly).

> been presented to the CFRG mail list during the discussion of timing attacks
> that initially took place on December 2012, or after Kevin put out a Last
> Call for comments on Dragonfly on April 4, 2013.   For perspective: Rene
> Struik's comments on that draft went out on Nov 29, and yous went out on Dec
> 10, over six months after the last call for comments.

Rene brought up the sidechannel issue again in July 2013, with no response:

http://www.ietf.org/mail-archive/web/cfrg/current/msg03489.html

But there's a bigger picture:  Regardless of timing attacks, Dragonfly
is inferior to alternatives already standardized or found in the
literature.

This opinion was well-expressed on the TLS and CFRG mailing lists when
Dragonfly was proposed.  This opinion was probably shared by many more
people than expressed it (like me), and was never adequately
addressed.  By Dec 2012, I assume most people had tuned-out a
discussion about an non-useful protocol that was proceeding without
regard to group opinion.

Trevor

---

From: Trevor Perrin <[email-masked]>
Date: Fri, 3 Jan 2014 18:50:12 -0800

> I think we agree that what Dan specified in the draft is broken.  However, I believe that's because Dan got it wrong (and I was busy elsewhere, and did not review the draft).

Hi Scott,

In 2012 I can imagine you were thinking of something like your below
pseudocode.  However, Dan seems to have understood your 2012 messages
as saying that simply performing 40 loops of the draft-00 algorithm
was a sufficient timing-attack countermeasure.  I don't think we can
blame Dan entirely for that - your messages weren't as clear and
detailed as your current pseudocode.

In any case, I think everyone now agrees Dan's understanding, embodied
in CFRG drafts 01 and 02, is incorrect.  Work still needs to be done
to ensure individual loop iterations don't leak secret info.

> Now, I believe the issue is 'did Kevin endorse my suggestion, or did he endorse Dan's implementation?'

Kevin seems to have shared Dan's understanding.  Or at least: he
considered the issue resolved in drafts 01 and 02, and made no effort
to look more deeply into the timing question.

Scott's proposals:
http://www.ietf.org/mail-archive/web/cfrg/current/msg03260.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03265.html

Dan and Kevin's reception:
http://www.ietf.org/mail-archive/web/cfrg/current/msg03262.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03263.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03264.html

Kevin's endorsement of draft-01 and draft-02:

"The design looks mature, it addresses a real need, and no one has
raised any issues."
http://www.ietf.org/mail-archive/web/cfrg/current/msg03383.html

"Kevin reports to TLS WG chairs that CFRG did not find any problems
with Dragonfly."
http://www.ietf.org/mail-archive/web/cfrg/current/msg03707.html

Trevor

---

From: "Dan Harkins" <[email-masked]>
Date: Sat, 4 Jan 2014 00:24:15 -0800 (PST)

Trevor,

> think "ineffective" is a fair description.  Do you agree?

  That is a good description of a problem. I now see how poor the
text is that describes the hunting-and-pecking loop. I wish you
would have put it in the form of a constructive comment, or at least
separated this signal from the general noise of your posts. But
nevertheless, I see that that section is poorly worded, I understand
your comment, and will address it in a subsequent version of the
draft.

  A sincere thank you for this comment!

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Sat, 4 Jan 2014 00:26:58 -0800 (PST)

Scott,

  Thank you for this very constructive comment. I appreciate the
suggestion on improving the draft. I will look at it closely. Your
help is most appreciated.

  regards,

  Dan.

On Fri, January 3, 2014 9:01 am, Scott Fluhrer (sfluhrer) wrote:
> I think we agree that what Dan specified in the draft is broken.  However,
> I believe that's because Dan got it wrong (and I was busy elsewhere, and
> did not review the draft).
>
> I believe my suggestion is an improvement (but still needs caution; the
> checking if x^3+ax+b is a QR must be done in constant time, or in random
> time via blinding; I believe that in this case blinding is easier).
>
> (this stops on the last acceptable 'x' value found; you could try to
> select the 'middle-value'; I picked the last because it was the easiest to
> specify).
>
> As for determining if a value is a QR, the easiest way to do it without
> leaking any information in the time taken would be to blind the value
> randomly, as in:
>
> where qr, qnr are fixed values which are respectively a quadric residue,
> and quadratic nonresidue mod p, and are the same size (and so the
> multiplications take the same amount of time).
>

---

From: Trevor Perrin <[email-masked]>
Date: Sat, 4 Jan 2014 08:44:08 -0800

On Fri, Jan 3, 2014 at 2:26 PM, David McGrew <[email-masked]> wrote:
> The only change in the algorithm that you cite (Sections 3.2.1 and 3.2.2.)
> is the change in the conditional statement that you mention.
>
> If  the condition "((x^3 + ax + b) is a quadratic residue mod p)" is checked
> using an efficient method such as the legendre/jacobi symbol, which takes
> significantly less time than the execution of the branch "y = sqrt(x^3 + ax
> + b)", then the number of times that the branch executes will be detectable
> to an attacker.   This will give an attacker information about the password.

You're understating the problem:  a timing-attack risk exists in
draft-01 3.2.1 if the computation performed for quadratic residues
take a different amount of time than the computation for non-residues,
or quadratic residuosity testing takes variable time based on its
input.

Even a small timing difference might be exploitable via statistical
tests (it's not necessary that the timing difference be obvious in a
single run of the protocol).

It's also not necessary for quadratic residuosity testing to take
"significantly less time" than square-root finding.

> So in this case, I agree, versions 01 and 02 seem more vulnerable than
> version 00 to timing attacks.
>
> method for computing square roots mod p, or an algorithm like it, which upon
> termination either outputs the square root or an indication that the number
> that was input is not a quadratic residue.   In this case, version 01 could
> be less vulnerable to timing attacks than version 00.   (I would guess this
> is what Dan had in mind.)

I think the Tonelli/Shanks algorithm takes variable time based on its
input, so while it might reduce the problem I doubt it eliminates it.

Also, while I haven't considered this in detail, I'd be worried the
Tonelli/Shanks algorithm would be inefficient enough for some primes
(such as P-224) that it would eliminate the speed advantage which is
the reason to use elliptic curve crypto.

Dan Bernstein has a paper on square-root algorithms that might be relevant here:

http://cr.yp.to/papers/sqroot.pdf

> Clearly, this algorithm is not specified well enough in the draft to ensure
> that it will be implemented in a way that resists timing attacks.
> Additionally, the most efficient way to implement the algorithm in the draft
> (using the legendre symbol) would lead to vulnerabilities.   These are
> significant problems.
>
> Dec 13 2012.   Kevin summarizes the Dragonfly status, asks for input, and is
> the first person to describe the need for Dragonfly to resist timing
> attacks.   He proposed a solution.   Scott Fluhrer pointed out a problem
> with the proposal, and suggests instead the "40 loop" fix.

Kevin was not the first person to observe that.  It was observed by
the IPsec WG and TLS WG.

IPsec, 2010:
http://www.ietf.org/mail-archive/web/ipsec/current/msg06321.html

TLS, 2011:
http://www.ietf.org/mail-archive/web/tls/current/msg08182.html

> understand the points that Scott was trying to make, and there was no follow
> up from anyone in the RG to make sure that the changes had been done, quite
> possibly because people assumed that the fix actually was equivalent.
> Scott has clarified on the list recently, with the essential point being
> that the square root computation can be moved outside of the while loop.
> (As a side note: it would simplify this computation if p = 3 (mod 4).)

Scott also recently suggested blinding the Legendre symbol
calculation, which is a clever idea that was not proposed earlier.

> I suspect that Dan is assuming that something like Shank's method will be
> used.   Your analysis assumes that the Legendre/Jacobi symbol will be used.
> Note, however, that the suggestion to use that computational method came
> after Kevin's suggestion to use the "40 loop" fix.

Avoiding the Legendre/Jacobi symbol calculation would have a
significant performance impact, and would not, by itself, necessarily
fix the problem.

> Having participated in some of the off list conversations about Dragonfly,
> and having recently reviewed the discussions on the mail list, it seems to
> me that Kevin's input was an effort to promote positive changes, review, and
> discussion, and not an attempt to subvert the protocol.    I note that Kevin
> was the first to point out that resisting timing attacks was a goal, and he
> called for review repeatedly.   If he had wanted to influence the protocol
> without arousing suspicion, a far more effective way to have done that would

I doubt the Dec 2012 discussion was Kevin trying to plant a backdoor
in the protocol.  I do think his analysis there was sloppy and
unserious.

Trevor

---

From: David McGrew <[email-masked]>
Date: Sun, 05 Jan 2014 20:05:02 -0500

Hi Trevor,

> to that community and a translator of its knowledge would be very

It would be great to have an ambassador, and that person need not be a 
chair.

> Also, this would be a good discussion to pursue at Real World Crypto

Agreed.  Unfortunately, I will not be able to attend due to other 
travel.  If there is someone in the RG who can attend, it would be great 
to hear a report from them on topics that they think the list should 
know about.   (An aside: I'd like to hear or read about /Provable 
security of advanced properties of TLS and SSH/, which I would guess is 
similar http://eprint.iacr.org/2013/813.pdf) Also, if there is an 
opportunity to present a plug for CFRG at the event, say during a rump 
session, I offer to help to prepare a short presentation on CFRG to 
anyone willing to give it.

I think it would be good to have an actual CFRG meeting adjunct to an 
IACR venue, such as Crypto in Santa Barbara.   Probably there are not 
many people who regularly attend both the IETF and crypto conferences, 
but I think that such a meeting would help to build a stronger online 
community, if nothing else.

thanks,

David

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sun, 05 Jan 2014 20:23:36 -0500

On 01/05/2014 08:05 PM, David McGrew wrote:
> know about.

I'll be at RWC.  If i can assemble a reasonable summary of the event,
i'll try to post it to this list.

> Also, if there is an

there is, actually!  here's the form so you can see what they're asking for:

  https://crypto.di.uoa.gr/rwc2014srtk/

I'd be willing to present a couple-minute short talk encouraging
participation in the CFRG if folks think that would be useful.  David,
if you want to contact me (on-list or off) to go over what you think
such a presentation would look like, i'd be happy to discuss it.

Regards,

	--dkg

---

From: David McGrew <[email-masked]>
Date: Mon, 06 Jan 2014 09:16:21 -0500

> such a presentation would look like, i'd be happy to discuss it.

Thanks!   I drafted up a short overview of the RG, which ends with a 
"why should you participate?" slide, and sent it to you off-list.

David

---

From: [email-masked]
Date: Mon, 06 Jan 2014 17:17:13 -0500

It is a FEATURE (not a bug) that mutually distrustful people
are in a position to engage in a common arena.

Why, for example, do you want poll watchers from opposing
parties to be in the same room at the same time?  Why, for
example, does everyone quote Sun Tzu "Keep your friends close
but your enemies closer?"  Why do you want Red Teams *and*
Black Teams to both be looking at bonuses for beating the
snot out of the other?  Why does capitalism always win?

God bless worthy opponents.

--dan

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 07 Jan 2014 00:23:09 -0500

> are in a position to engage in a common arena.

Yes, there are competitors here, including some people who distrust each
other.  But the IETF and the IRTF are not gladiatorial sports or
marketplace proving grounds.  They are places where commercial,
industrial, academic, governmental and civil society actors can can come
together to collaboratively develop interoperable standards and
mechanisms, to improve the internet for everyone.

This assumes a baseline of common goals, such as those expressed by our
community after IETF 88:

https://www.ietf.org/media/2013-11-07-internet-privacy-and-security.html

Organizations who do not share these common goals, and especially those
who are actively working to subvert them, do not fit into this
forum-of-competitors model that you're touting.

> parties to be in the same room at the same time?

Members of the political parties may compete with each other, but they
all have an interest in the continued functioning of the electoral system.

How do you feel about a poll watcher from an organization whose stated
goals include actively damaging the electoral system itself?  What about
a member of such an organization who offers to help with the thankless
task of coordinating the poll watching?  What if that volunteer has had
ample opportunity to explicitly disavow and reject their organization's
goal of damaging the electoral system, but has not done so publicly?

What does this situation do to motivate people who want to see the
electoral system function better, and who are considering volunteering
to help watch the polls?

I understand that WG and RG co-chairs are not dictators, and that they
cannot single-handedly mandate results.  But I don't buy the argument
that they have no special influence over the process.  Anyone with a
history of working in groups can tell you that even the most thankless
coordinating/facilitating work holds implicit power.  That's power to
shape agendas, to highlight certain decisions over others, to
magnify certain views and minimize others, and to craft the public
messages that reach beyond the group.  RFC 2014 itself calls this
"wide discretion in the conduct of Research Group business".

The IETF does not (and should not) exclude individuals from
participation based on their organizational affiliation.  And certainly
organizations aligned in opposition to the goals of the IETF may attempt
to covertly damage the IETF process no matter what.

But it does not follow from these facts that the IETF should accept or
endorse leadership from people who have explicit, public affiliations
with groups opposed to the goals of the IETF.

One of the counterclaims here is that the IETF has open process where
concerns can be brought up and dealt with.  Well, they're being brought
up, but it doesn't feel that they've been dealt with.

-----

I plan to call for more participation in the CFRG at the Real World
Crypto conference in New York next week.  Since the Snowden leaks, there
is renewed interest and energy around the topics that the CFRG is
chartered to investigate.   It should be easier to encourage
participation than it would have been previously, because people are
more aware of the scope of the issues now, and it is clear that there is
a strong ethical case to defend users from pervasive monitoring and
surveillance.

Unfortunately, I expect it to be significantly harder to effectively
advocate for additional participation in the research group given that
one of the co-chairs continues to work for a known adversary.

	--dkg