Subject: [Cfrg] Additional consequences of the move to ECC (and they are good)

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 13 Jul 2015 12:39:48 -0400

All,

So far people have been talking about the move to ECC as giving an
improvement in either speed or security. One other consequence that should
be considered seriously is that we are also moving to a DH based algorithm
and this has some important consequences:

1) Key generation is much faster (no need to generate primes).

2) Multiplying the parts of public key pair A by the corresponding parts of
key pair B produces a new key pair A.B.

I have used the second feature to produce a solution to the 'weak keys'
problem I will present in the meeting. But right now I want to point out an
interesting consequence for use of fingerprints to represent keys as is
popular in OpenPGP, Bitcoin and is the approach I am taking in what was
PRISMPROOF and is now the Mesh.

Earlier today, in another place, Christian Huitema described some work they
had done to make palatable identifiers of the form:

MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ
<[email-masked]>

This got me thinking about a hack I saw someone do on Bitcoin where they
made an identifier that had their company name embedded in the string.

So what does it take to make me:

MxHAL-LAMxx-xxxxx-xxxxx-xxxxx ?

Using a brute force approach (the only one that I hope is possible), if
selecting the first two letters causes the process to take a second,
selecting the third will cause it to take almost a minute, the fourth
quarter of an hour, the fifth a third of a day and a sixth more than a
week, the seventh a year and so on.

Going to ECC reduces the cost of each attempt by at least a letter,
probably two. It still takes a century or more to get a ten letter vanity
prefix and an exhaustive attack remains comfortably outside the realms of
practicality.

---

From: CodesInChaos <[email-masked]>
Date: Tue, 14 Jul 2015 11:25:34 +0200

Extrapolating from the cost of a Curve25519 key exchange*, a CPU
should be able to produce new keypair in 1000 cycles or so. Hashing
costs another 1000 cycles or so (depending on the hash). This amounts
to about 4 letters per second. Using GPUs and custom hardware speed it
up further.

To avoid these issues it's a good idea to include some kind of
proof-of-work into computing human comparable fingerprints. I'd use
the first letter for the logarithm of the amount of work, so if the
defender put in a lot of work, the attacker needs to put in a lot of
work as well to match even the first letter.

---

From: Tom Ritter <[email-masked]>
Date: Fri, 17 Jul 2015 22:01:43 -0500

> key pair B produces a new key pair A.B.

I've read a paper that enables generation of a single public ElGamal
key from multiple public ElGamal keys; allowing for distributed key
generation and decryption.  Simple question, complicated answer I'm
sure, but is the same thing documented/possible for ECC?  Any
pointers?

Thanks,
tom

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 18 Jul 2015 00:19:31 -0400

Yes, it works in any group

Which paper is that?

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 17 Jul 2015 21:50:35 -0700

> sure, but is the same thing documented/possible for ECC?  Any

Yes, you can do multi-party key agreement schemes with ECC:

http://www.ejournal.org.cn/Jweb_cje/EN/article/downloadArticleFile.do?attachType=PDF&id=3360

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 18 Jul 2015 01:07:48 -0400

There are lots of folk with schemes to do multiparty. But so far, I haven't
seen anyone propose just reassembling the pieces to make a traditional key.

Multiparty signatures don't interest me at all since I can get the exact
same effect by simply having the validator look for multiple signatures.

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 17 Jul 2015 22:16:09 -0700

On Fri, Jul 17, 2015 at 10:07 PM, Phillip Hallam-Baker <
[email-masked]> wrote:

> There are lots of folk with schemes to do multiparty. But so far, I
> haven't seen anyone propose just reassembling the pieces to make a
> traditional key.
>

That's exactly how multiparty Diffie-Hellman schemes work. The
Diffie-Hellman protocol can be extended to N participants.

What you arrive at is a secret shared among multiple parties, and this
applies to cyclic groups and elliptic curve groups. It's either a shared
secret number or a point on an elliptic curve. Either way it can be fed
into a KDF and turned into symmetric key material.

-- 
Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 17 Jul 2015 22:23:14 -0700

Here's another interesting paper:

http://web.cs.ucla.edu/~vanishri/adaptiveNIKE.pdf

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 18 Jul 2015 01:55:14 -0400

> into a KDF and turned into symmetric key material.

No, they are generating a common symmetric key.

This is Alice and Bob generating a public key for Alice and Alice alone
that is used in exactly the same way as any other public key would be.

What you are describing is Alice has a public key and Bob has a public key
and they do something that has the effect of an Alice-Bob virtual key. That
is a different thing altogether.

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 17 Jul 2015 23:05:49 -0700

> is a different thing altogether.

I'm not sure if I really follow you. It'd be helpful, for me at least, if
you could describe the protocol in terms of the public and private keys of
all of the principals/parties involved in the exchange.

For example, we could concoct a multiparty key exchange scheme like this (I
believe this works):

Carol publishes her public key C, but has private key c.

Carol wants to share a secret only Alice and Bob can decrypt if they work
together.

Carol obtains Alice and Bob's public keys A and B respectively.

Carol does fixed-base scalar multiplication c*P=C to obtain her public key.
Carol does variable-base scalar multiplication c*A*B to obtain a multiparty
shared secret.

Carol encrypts some data under this multiparty shared secret and publishes
C to either Alice/Bob such that if Alice and Bob work together they can
recover c*A*B by calculating a*A*C or b*A*C.

I guess I don't understand what you have in mind. How would you describe
it? Who are the principals/parties involved, what keys do they have, and
how do they interact?

-- 
Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 17 Jul 2015 23:33:55 -0700

Another paper:

https://crypto.stanford.edu/~zhandry/docs/papers/IO-TRAITOR.pdf

-- 
Tony Arcieri

---

From: "[email-masked]" <[email-masked]>
Date: Fri, 17 Jul 2015 23:44:39 -0700

In your construction Tony,

Alice and Bob don't need to cooperate to recover the multiparty shared
secret.

Alice need a and B,C to recover the shared multiparty secret.

Bob needs b and A,C to recover the shared multiparty secret.

Everyone arrives at the same secret using their private key and the others
public keys.

I think you need a point addition in there along with the multiply to get
something close to the scheme Philip was asking for. It's late and the
construction isn't coming to me.

On Fri, Jul 17, 2015 at 11:33 PM, Tony Arcieri <[email-masked]> wrote:

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

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 17 Jul 2015 23:49:19 -0700

> Alice and Bob don't need to cooperate to recover the multiparty shared

Sure, if another peer (e.g. Carol) brokers their public keys there isn't
any requirement that Alice and Bob directly collude.

---

From: Bryan Ford <[email-masked]>
Date: Sat, 25 Jul 2015 12:45:36 +0200

Hi Tom, catching up on this thread a bit late…

> On Jul 18, 2015, at 5:01 AM, Tom Ritter <[email-masked]> wrote:
> 

Standard verifiable [Shamir] secret sharing (VSS) techniques allow this, in either integer (ElGamal) groups or elliptic curves.  Not sure if there’s a definitive reference with “everything together in one place” though; I’d like to see one.  One implementation of most of the required mechanism is available in our advanced crypto library for Go: e.g., see http://godoc.org/github.com/DeDiS/crypto/poly <http://godoc.org/github.com/DeDiS/crypto/poly>

Classic VSS works fine for “small” groups, e.g., a few 10s of members, but won’t scale readily to large groups: to avoid a globally trusted dealer all N members must “deal” N polynomial shares to all other members, then add up everyone else’s shares, yielding O(N^2) complexity.  The work I mentioned in my earlier July 12 E-mail ("scalable collective signing”) addresses the problem of scaling VSS techniques to large groups.  It currently focuses on collective signing, but should be readily extensible to collective ElGamal encryption/decryption.  I’m happy to work with you or anyone with an interest or a burning use-case for something like this.

Cheers
Bryan