On Sun, 20 Aug 2017 16:32:17 +0000 Taylor R Campbell <campbell+tor-dev@mumble.net> wrote:

...

... I'm not seeing your point. Even prior to that paper, AEZ wasn't thought to be quantum resistant in anyway shape or form, and providing quantum resistance wasn't part of the design goals of the primitive, or really why it was being considered at one point for use in Tor.

I would expect AEZ to have essentially the same post-quantum security as, e.g., AES or any other symmetric crypto -- square root speedup by Grover.

Yes and? My point was that quantum speedups that existed prior to the paper alone, were sufficient to render the primitive insecure in a post quantum setting. Something that's broken being more broken is non-interesting, in particular when the impetus for even considering the something (as is the case for AEZ and Tor), had nothing to do with PQ cryptography in the first place.

However, this paper is not about the conventional notion of post-quantum security -- what is the cost, to an adversary with large a quantum computer, of breaking ordinary users of the cryptosystem? -- but a radically different notion of security for users who inexplicably choose evaluate AEZ in a quantum superposition of inputs and reveal that superposition to an adversary.

Believe it or not, I did read the paper.

It is not surprising that when users abuse their crypto primitives in an astoundingly bizarre way, to reveal quantum superpositions of outputs, the original security claims of the classical crypto primitives go flying out the window!

I'm having trouble parsing that, perhaps my English is failing me. Ultimately none of this matters because Prop. 261 is dead in the water. Assuming people want the new cell crypto to be both fragile and to resist tagging attacks, Farfalle may be a better choice, assuming there's a Keccak-p parameterization such that it gives adequate performance. Regards, -- Yawning Angel

On Tue, 22 Aug 2017 20:47:06 +0200 Peter Schwabe <peter@cryptojedi.org> wrote:

Yawning Angel <yawning@schwanenlied.me> wrote:

Hi Yawning, hi all,

...

Ultimately none of this matters because Prop. 261 is dead in the water. Assuming people want the new cell crypto to be both fragile and to resist tagging attacks, Farfalle may be a better choice, assuming there's a Keccak-p parameterization such that it gives adequate performance.

At what number of cycles/block on what architecture(s) would you call the performance "adequate"?

Note, I'm not hating on Farfalle, I need to look at it more, and the last time I gave serious thought to this question in a Tor context was back around the time Prop 261 was being drafted. The answer to this from my point of view is "not slow to the point where the network falls over", which I'll admit is extremely handwavy, but truth be told, I have no idea what fraction of the relays are on what micro architectures these days. Looking at the Farfalle and Kangaroo 12 papers, Kravette may be ok with AVX2 assuming I'm extrapolating correctly. But, while it's probably reasonable to assume that all the fast existing relays have AES-NI, I do not know what fraction of those predate AVX2. Part of me thinks that focusing on raw primitive performance is a bit silly (even though I'm the one that brought it up), because just about anything will likely deliver adequate performance if the cell crypto used more than one core[0]. Sorry I don't have anything more concrete. :( Regards, -- Yawning Angel [0]: And another part of me kind of wants to say "eat the overhead of a MAC per hop and use AES-GCM-SIV or something".

On Sat, Sep 2, 2017 at 4:16 AM, Peter Schwabe <peter@cryptojedi.org> wrote:

Yawning Angel <yawning@schwanenlied.me> wrote:

Hi Yawning, hi all,

...

Note, I'm not hating on Farfalle, I need to look at it more, and the last time I gave serious thought to this question in a Tor context was back around the time Prop 261 was being drafted.

The answer to this from my point of view is "not slow to the point where the network falls over", which I'll admit is extremely handwavy, but truth be told, I have no idea what fraction of the relays are on what micro architectures these days.

Looking at the Farfalle and Kangaroo 12 papers, Kravette may be ok with AVX2 assuming I'm extrapolating correctly. But, while it's probably reasonable to assume that all the fast existing relays have AES-NI, I do not know what fraction of those predate AVX2.

You should end up with something like 13 cycles per byte for Farfalle with the Keccak permutation on Skylake. Would there be some way to test what effects this has on overall performance without harming any users?

If this is *clearly* too slow, then it might be interesting to try the Farfalle construction with different permutations to see how far you can push performance.

I think the first step here is to instrument relays to figure out what fraction of their cryptography is relay cell cryptography: this could tells us what slowdown we should expect. (It _should_ be about a third of our current cell crypto load, but surprises have certainly been known to happen!) The current performance we have is much faster than 13 cpb -- we're at approximately one AES, plus one third of a SHA1. (The "one third" is because only clients and exits do the SHA1 step.) It would be hard to experiment to see whether some slowdown would be acceptable: the problem is that the major increase in load would be at the relay side -- and it's hard to tell the impact of putting more load on relays on the actual network without actually doing it. Yawning is right that doing multithreaded cell crypto is important here too: there are unused cores at the moment. -- Nick