[tor-dev] PQ crypto updates

[b***@openmailbox.org]

If I understand correctly, DJB describes how NTRU-Prime is more robust against certain attack classes that Ring-LWE is more prone to:

https://twitter.com/hashbreaker/status/880086983057526784

***

About two months later DJB releases a streamlined version of NTRU-Prime that is faster, safer and uses less resources than the latest version of New Hope while (wait for it...) completely eliminating decryption failures !:

https://twitter.com/hashbreaker/status/898048057849380864
https://twitter.com/hashbreaker/status/898048506681860096
https://twitter.com/hashbreaker/status/898048760009420801
https://twitter.com/hashbreaker/status/898391210456489984


***

Boom headshot! AEZ is dead in the water post quantum:

Paper name: Quantum Key-Recovery on full AEZ

https://eprint.iacr.org/2017/767.pdf

[Yawning Angel]

On Sat, 19 Aug 2017 04:11:16 -0000

Post by b***@openmailbox.org
Paper name: Quantum Key-Recovery on full AEZ
https://eprint.iacr.org/2017/767.pdf

... 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.

Regards,

[Yawning Angel]

On Sun, 20 Aug 2017 16:32:17 +0000

Post by Yawning Angel
... 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,

[Peter Schwabe]

Yawning Angel <***@schwanenlied.me> wrote:

Hi Yawning, hi all,

Post by Yawning Angel
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"?

Cheers,

Peter

[Yawning Angel]

On Tue, 22 Aug 2017 20:47:06 +0200

Post by Peter Schwabe
Hi Yawning, hi all,

Post by Yawning Angel
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,

[Peter Schwabe]

Yawning Angel <***@schwanenlied.me> wrote:


Hi Yawning, hi all,

Post by Yawning Angel
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.

Cheers,

Peter

[Nick Mathewson]

Post by Peter Schwabe
Hi Yawning, hi all,

Post by Yawning Angel
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.

[Yawning Angel]

On Sun, 17 Sep 2017 21:04:28 -0400

Post by Nick Mathewson
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!)

I'd also argue that instrumenting an high traffic client is important
(if only so that there aren't unpleasant surprises later in the form of
the clients hosting spacebookgopheri.onion or whatever exploding).

There was some discussion about obtaining profiler output for this
particular case, but AFAIK nothing really happened[0].

Post by Nick Mathewson
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.)

I wonder how many of the relays have support for hardware assisted
SHA. (nb: I don't have access to ARMv8, Ryzen or a sufficiently new
Intel system, so I don't know how good the implementations are)

Regards,