Subject: [Cfrg] Meeting notes

From: Tony Arcieri <[email-masked]>
Date: Fri, 27 Mar 2015 00:02:19 -0700

Did anyone take any notes from Wednesday's CFRG meeting? I'd be interested
in reading them.

-- 
Tony Arcieri

---

From: Yoav Nir <[email-masked]>
Date: Fri, 27 Mar 2015 07:49:44 -0500

The chairs will post the edited notes when they get the chance to go over them. But I’ve posted the raw notes below.

Yoav

> On Mar 27, 2015, at 2:02 AM, Tony Arcieri <[email-masked]> wrote:
> 
> Did anyone take any notes from Wednesday's CFRG meeting? I'd be interested in reading them.

CFRG notes
==========

All three chairs present. ~80 people in the room.

Session began at 12:59.
Document status
Dragonfly in IRSG review
Spake2 accepted as RG Document
Work item: new curves for TLS.

First item: AGL on status of CFRG curves.
Goldilocks has been included.
Algorithms tweaked to work with different length.
Not re-checked yet.
WG decided to send u-value for DH
Check for zero output - happens if input point has wrong order, checking is cheap, now a MUST.

Parameter generation
used to generate (twisted) Edwards curves and then hop isomorphisms and isogenies. 
Base point - in sage. generates the standard base point for curve25519 and u=5 for curve448.
SAGE is a standard maths library based on python

=== no questions.

Second item: Kenny Paterson on next steps for curves
RG selected Curve25519 and Goldilocks (~224 bits)
Produced by a deterministic procedure
Submitted short proposal for NIST workshop as IETF/IRTF input.
next: define a signature scheme for use with the new curves.
Some options:
 - ECDSA on (twisted) Edwards form versions of the new curves
 - De-randomised ECDSA:
   - avoids common failure mode of ECDSA
   - generate r for ECDSA by hashing message and private key
   - generate r via prf.
 - EdDSA [BDLST'11]
   - variant of schnorr signature scheme
Questions:
	- what other signature
	- does NIST compliance matter? for TLS? Others?
	- How should we structure the discussion to make it reaches a useful conclusion in a timely fashion.
	
Rene Struik: we should also do non-special primes
Yoav Nir + Joe Sallowey: we should not consider NIST compliance, because nothing that is not ECDSA on P-256/P-384 is going to be.
PHB: 
Paul Hoffman: You never know what NIST is going to say, so don't include it in our considerations.
Kenny: we should engage with nist
Mike St. Johns: We should consider if it will be acceptable to banks and other high-value organizations.
Andrei Jivsov: Do the decisions of DH for compressed vs uncompressed apply? Shouldn't we kick it to high-level protos?
Stephen Farrell: no.
DKG: Doesn't make sense to re-use formats because we want to not re-use keys
Bob Moskowitz: keep it small
AGL: strong feeling we should not worry about NIST. Should check on the list. randomized vs no? How Schnorrish should it be?
Andrei: There is benefit in unified point format. You can still not share keys.
AGL: not giving up on unified point yet. 
Renee Struik: Confusion point about whether the Montgomery can be done with all formats.
Rich Salz: should move to the next argument. This one is done.
Stephen Farrell: Perhaps need to not use an incremental approach.
KP: I think it has worked.
AGL: EdDSA hashes twice, so you need to get it all the message in one part. Different from current APIs.

=== Third item: Scrypt KDF
password-based KDF
widely used
current draft has pseudo-code in python, test vectors
Seeking CFRG input
to be published as informational.

Ben Kaduk: 
AGL: it is historical? The password hashing competition should be done by then.
KP: should look at the password hashing competition. They're in their final stages - 6-8 months
Nico: why informational? Standards track won't be able to use it
Chorus: not anymore

=== Fourth item: the Algebraic Eraser (Paul E Gunnels)
Protocol for IoT things.

Renee: what about sigs
Atkins: a little different. fleshing 
Yoav: if it's good for IoT, why not for everything else?
Derek Atkins: that's just our focus.
Nico: Because this needs a trusted 3rd party that can break everything
KP: need some more cryptanalysis to know that key search is the best attack.
PEG: there are other attacks. One to recover the conjugator. Another to recover the matrix part or the private key. Those have been refuted - reduced to exhaustive search.
AGL: have you tried an optimized implementation? Would it be 70x faster on a quality CPU?
Derek: I have seen 50x. AE could benefit from larger tables on commodity CPU.
Stephen Farrell: trusted third party - what does it need to do
Derek: the trusted 3rd party is needed for the curve parameters.
AGL: on a large scale you would need... (OK, I didn't understand the trusted 3rd party issue...) 

=== Fifth item: Hash-based signatures (Huelsing)
AGL: why not generate bit masks using stream ciphers?
Huelsing: you don't get the reductions going
AGL: if this is a stateful scheme. It really needs to work for a long time. Isn't this contradictory to having a stateful scheme?
Huelsing: We have to always increase the index. Easily possible on certain applications like smartcards.
AGL: if you want to be conservative, you need to be stateless.
Huelsing: some people want the stateful scheme. Smaller signatures are an advantage. This is s step towards standardizing the stateless schemes. This is more efficient.
AGL: Are you planning on going forward?
Huelsing: yes
Hannes: you talked about efficiency. Do you have numbers somewhere?
Huelsing: yes, we have a C implementation on my website. We have numbers for a smartcard implementation.
Hannes: will check your webpage.

=== Sixth item: PAKE requirements (Harkins)

=== Seventh: AugPage (Shin)

AGL: you had lots of requirements on the EC groups. What is the advantage of this over Spake2 that works with less requirements.
Shin: it's not augmented.
Yaron: The person in the Jabber room (bitwiseshiftleft = Mike Hamburg) thinks the proof is incorrect 
Renee: Can you tweak the scheme so you can get rid of this inversion that computes the z in slide #10?
Shin: Not big computation cost

=== Eighth: SIP authentication with EC-SRP (Liu)
PHB: I've solved the problem that was impossible to solved - the key generation one.

---

From: "Derek Atkins" <[email-masked]>
Date: Fri, 27 Mar 2015 09:29:32 -0400

Yoav,

On Fri, March 27, 2015 8:49 am, Yoav Nir wrote:
[snip]
> PEG: there are other attacks. One to recover the conjugator. Another to
> recover the matrix part or the private key. Those have been refuted -
> reduced to exhaustive search.

AE has a set of public parameters that you use to generate keypairs that
can communicate (the equivalent of an ECC Curve or DH Prime).  The issue
is that you need random data to generate those public parameters, and that
random data needs to be kept secret.  Once the parameters are generated
you don't need access to the random data ever again, but the issue, as I
understand it, is "how do you know that that random data wasn't
compromised during the parameter generation process?"

Hopefully this better explains the issue?

Thanks,

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Yoav Nir <[email-masked]>
Date: Fri, 27 Mar 2015 09:44:14 -0500

> On Mar 27, 2015, at 8:29 AM, Derek Atkins <[email-masked]> wrote:
> 
> Yoav,
> 

Not quite. For ECC and DH these parameters were generated once, and then those public parameters were published in an RFC or NIST document. So 10 years after their generation, we still use those public parameters and we don’t ever need access to any random data that was used to generate them. They’re hard-coded in every implementation.

Is that the same for AE?  Because if it is, you could just generate those parameters, stick them in the draft and be done with it (up to some NUMS claims that can be solved with a key generation ceremony that need happen only once.

Thanks.

Yoav

---

From: "Derek Atkins" <[email-masked]>
Date: Fri, 27 Mar 2015 16:55:54 -0400

Hi,

> Not quite. For ECC and DH these parameters were generated once, and then
> those public parameters were published in an RFC or NIST document. So 10
> years after their generation, we still use those public parameters and we
> don’t ever need access to any random data that was used to generate them.
> They’re hard-coded in every implementation.
>
> Is that the same for AE?

Yes.

>          Because if it is, you could just generate those
> parameters, stick them in the draft and be done with it (up to some NUMS
> claims that can be solved with a key generation ceremony that need happen
> only once.

Exactly.

-derek

---

From: Watson Ladd <[email-masked]>
Date: Fri, 27 Mar 2015 14:47:54 -0700

> > claims that can be solved with a key generation ceremony that need
happen

NIST published the seeds used. But in an email above it's claimed the
random data used must be secret. This us a large difference from ECC.
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 28 Mar 2015 08:39:29 -0500

On Fri 2015-03-27 09:44:14 -0500, Yoav Nir wrote:
> Is that the same for AE?  Because if it is, you could just generate
> those parameters, stick them in the draft and be done with it (up to
> some NUMS claims that can be solved with a key generation ceremony
> that need happen only once.

I think this key generation ceremony is the part that people were
expressing concern about in the meeting.

It's not clear that we have a clear story about how to do this in a
reliable, future-proof way (that is, so that arbitrary people in the
future can easily refute any speculation that the original generation
procedure was somehow backdoored).

Many of us on this list can probably propose clever "performance art"
events that seem like they'd be likely to satisfy this property today
for most of us.  But if we aim for some set of parameters that will
still be used a generation from now, that seems harder to predict.

          --dkg

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 30 Mar 2015 11:56:17 +0200

Derek Atkins schrieb am 27.03.2015 um 14:29:
> random data needs to be kept secret.

What is the consequence if the random data becomes known, e.g., to an adversary?

Does this enable him to recover private keys?

And what does this imply for the level of trust that you need to have in the trusted third party?

-- 
Johannes

---

From: Yoav Nir <[email-masked]>
Date: Mon, 30 Mar 2015 13:26:38 +0300

> On Mar 28, 2015, at 4:39 PM, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

I’m not a big fan of performance art, but if the claims of 50x performance gain are true, I think a lot of us will be willing to just through a lot of hoops to get it.  And I mean for all the Internet, not just SmartObjects.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 30 Mar 2015 13:45:05 +0300

On Mon, Mar 30, 2015 at 01:26:38PM +0300, Yoav Nir wrote:
> I’m not a big fan of performance art, but if the claims of 50x
>  performance gain are true, I think a lot of us will be willing
> to just through a lot of hoops to get it.  And I mean for all
> the Internet, not just SmartObjects.

I haven't really looked, but on surface the algorithm doesn't look to
be friendly for constant-time implementation. Matrix row or column
swaps are involved?

So constant-time implementation would likely be a lot slower (it could
still be much faster than ECC).

Modern CPUs and OSes are pretty ridiculously vulernable to timing
attacks. Even across VMs.

Another advantage: It uses medium primes, which are much
easier to work with than large primes (one can't use medium primes
with ECC due to weak fields). For CPU work, 2^31-1 looks to be pretty
convinient prime.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Mon, 30 Mar 2015 09:23:34 -0400

Dear colleagues:

 From the emails on Algebraic Eraser I have seen on this list, it seems 
clear that most have not given this algorithm any technical look. What 
about actually doing this, instead of having email completely tangential 
email exchanges about a "black box" one did not care to open?

Speculation on implementation security, sizes of primes involved, key 
generation protocols, etc., seem somewhat premature if one did not first 
look at and tried to understand the algorithm itself...

Ilari: the Algebraic Eraser paper of 2006 [1] includes some example 
instantiations with sparse 14 x 14 matrices over GF(p), with p=13. No 
clue at all where your p=2^31-1 comes from.

Rene

[1] Algebraic Eraser - Technical White Paper (Iris Anshel, Michael 
Anshel, Dorian Goldfeld, Stephane Lemieux, Contemporary Mathematics, 2006)

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "Derek Atkins" <[email-masked]>
Date: Mon, 30 Mar 2015 10:15:24 -0400

Thank you Rene,

In the example we gave in the presentation we are using B16F256 to reach a
security level of 2^128.  That's a 16x16 matrix over the field 256 (2^8).

-derek

---

From: Nico Williams <[email-masked]>
Date: Mon, 30 Mar 2015 11:49:58 -0500

On Mon, Mar 30, 2015 at 09:23:34AM -0400, Rene Struik wrote:
> From the emails on Algebraic Eraser I have seen on this list, it
> seems clear that most have not given this algorithm any technical
> look. What about actually doing this, instead of having email
> completely tangential email exchanges about a "black box" one did
> not care to open?

To me there's no clear order in which we should tackle the two problems
in AE.  The two issues can be looked at in parallel.

If we can't come up with a satisfactory parameter generation
performance, then perhaps there will be too few acceptable uses of AE
and similar cryptosystems.  If we can, then the same approach will
probably be reusable for other cryptosystems with similar
characteristics (TTP backdoored parameter).  Even if this cryptosystem
should fall, a parameter generation performance suitable for it might
prove useful elsewhere.  This is an interesting problem in its own
right.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Mon, 30 Mar 2015 11:51:27 -0500

> What is the consequence if the random data becomes known, e.g., to an

It's a complete break.

---

From: Rene Struik <[email-masked]>
Date: Mon, 30 Mar 2015 14:00:21 -0400

Hi Nico:

Perhaps. However, please start a new topic thread then. {with hopefully 
carefully contemplated thoughts, rather than twitter-like trigger-happy 
traffic}

Rene

---

From: Nico Williams <[email-masked]>
Date: Mon, 30 Mar 2015 13:44:54 -0500

On Mon, Mar 30, 2015 at 02:00:21PM -0400, Rene Struik wrote:
> Perhaps. However, please start a new topic thread then. {with

Subject: Re: [Cfrg] (on Algebraic Eraser) Re:  Meeting notes
                     ^^^^^^^^^^^^^^^^^^^       ^^^^^^^^^^^^^

If parameter generation is not to be discussed in this thread (it
certainly came up during the meeting whose notes we're discussing), what
is?  According to whom?

> hopefully carefully contemplated thoughts, rather than twitter-like
> trigger-happy traffic}

The observation that AE might require careful parameter generation
ceremonies had to come before (or with) any proposals for specific
ceremony procedures, and it seems like a critical aspect of AE
application to many possible use-cases.  It's not "twitter-like" to say
so.

(As if, too, twitterings could never be meaningful, important, pithy,
valuable, ...  That seems like a middle-school insult, which, as you can
see, we're all capable of.  Better just not get started. :)

AE's TTP backdoor makes it difficult to conceive of a believable
ceremony, particularly one that will be believed decades after the fact.

Part of the problem is social/political.  So far all sketches of such a
ceremony that I can come up with are mainly about using hardware so
simple that various participants can verify that there are no covert
channels of any sort via which the seed could be communicated to anyone
during or after the ceremony.  The "after" part is trivial: incinerate
the hardware in place, dynamiting it if need be.  The "during" part is
really difficult, and leads me to suggest using 8-bit hardware from the
early 80s.  But really, it's a hard problem, and not in the crypto
sense.

It'd be more productive to find use-cases where the backdoor-capable TTP
is either desirable or not fatal.  For IoT, per-household user-generated
parameters seems utterly acceptable.  Derek suggested (at the meeting)
that a backdoor-capable TTP might be acceptable for DNS root keys, and I
don't yet disagree[*].

[*] I would prefer to ensure that there is no backdoor, and that use of
    the root key be auditable in any case.  But I also tend to think
    that CT for DNSSEC may work well enough.  It's much too soon to tell
    though, which is why I don't yet take a position.

Nico
--