[tor-dev] Propsal 263 Quantum-safe Hybrid handshake for Tor, updated feature request v1.2

[Zhenfei Zhang]

Hello list,

We had a very constructive discussion on this proposal last Thursday.
I have updated the feature request based on the feedback from the
discussion.
We also like to thank Roger for grammar fixes on the proposal.

The diff file is available at:
https://github.com/zhenfeizhang/ntru-tor/commit/dc48c2065d1772c5497cd6ad900b54f6fbd24cef


Major tech updates are:
1. Use SHA3 and SHAKE instead of HMAC_SHA3

2. In previous proposal, when server sends back the message, it sends a
ciphertext
C = ENCRYPT( P | B, QSPK), and its one-time ECC public key Y = e^y;
where P is the secret that server chose, B is servers long term public key.

In this new version, we also include servers short term public key in the
plaintext, i.e.,
C = ENCRYPT( P | B | Y, QSPK)
and Y is no longer send to the client separately. The client will need to
decrypt
C first and retrieve Y from the message. Y is not revealed to any one other
than the
client.

This is proposed by Nick. It was also suggested to us by Aniket Kate. We
thank Nick
and Aniket for the suggestion. This modification will save 32 bytes of
traffic as Y is no
longer transmitted. Also since Y is now encrypted it will be a little
harder for the attacker
to attack the 25519 keys.

3. Choosing algorithms and parameters for the protocol.
We have identified NTRUEncrypt and R-LWE as two candidates for this
protocol.
We have agreed to use NTRUEncrypt for now, in the meantime, keep the option
open
for "newesthope" version of R-LWE type key exchange when it becomes
available. Also,
for NTRUEncrypt we will be using parameters sets with SHA3, to align with
Tor specs.
I have modified the feature request to reflect this change.

Also in the discussion we were talking about the possibility of using
non-product form
polynomial version of NTRUEncrypt, as this version will become patent free
by Aug 2017,
while the patent for product form will last for another 4 years. The main
concern is that
Debian will not allow patented software in the package.  However, through
our discussion,
it turns out that we may be able to include this proposal in the next one
of two release of
Tor. From this point of view, both patent (basic NTRU patent, till 2017 and
product form
patent, till 2021) are going to be an issue if Debian does not agree with
SI's patent statement.
So does it make sense to keep the product form polynomials as they enables
roughly 3
times faster operations on both client side and server side?


Thanks for your time, and please let us know if you have any further
comments/suggestions.

Best regards,
Zhenfei
Filename: 263-ntru-for-pq-handshake.txt
Title: Request to change key exchange protocol for handshake v1.2
Author: John SCHANCK, William WHYTE and Zhenfei ZHANG
Created: 29 Aug 2015
Updated: 4 Feb 2016
Status: Open

1. Introduction

  Recognized handshake types are:
0x  TAP --  the original Tor handshake;
0x0001  reserved
0x0002  ntor--  the ntor+curve25519+sha256 handshake;

  Request for a new (set of) handshake type:
0x010X  ntor+qsh--  the hybrid of ntor+curve25519+sha3 handshake
and a quantum-safe key encapsulation mechanism

  where
0X0101  ntor+qsh--  refers to this modular design; no specific Key
Encapsulation Mechanism (KEM) is assigned.

0X0102  ntor+ntru   --  the quantum safe KEM is based on NTRUEncrypt, with
parameter ntrueess443ep2

0X0103  ntor+rlwe   --  the quantum safe KEM is based on ring learning with
error encryption scheme; parameter not specified

DEPENDENCY:
  Proposal 249: Allow CREATE cells with >505 bytes of handshake data

  1.1 Motivation: Quantum-safe forward-secure key agreement

We are trying to add Quantum-safe forward-secrecy to the key agreement in
tor handshake. (Classical) forward-secrecy means that if the long-term key
is compromised, the communication prior to this compromise still stays
secure. Similarly, Quantum-safe forward-secrecy implies if the long-term
key is compromised due to attackers with quantum-computing capabilities, the
prior communication still remains secure.

Current approaches for handling key agreement, for instance the ntor
handshake protocol, do not have this feature. ntor uses ECC, which will be
broken when quantum computers become available. This allows the simple yet
very effective harvest-then-decrypt attack, where an adversary with
significant storage capabilities harvests Tor handshakes now and decrypts
them in the future.

The proposed handshake protocol achieves quantum-safe forward-secrecy and
stops those attacks by introducing a secondary short-term pre-master secret
that is transported via a quantum-safe method. In the case where the 
long-term
key is compromised via quantum algorithm, the attacker still needs to 
recover
the second pre-master secret to be able 

[tor-dev] Roadmap - Hidden service next generation (prop224)

[David Goulet]

Hi everyone!

For a while now, we've had an idea on how to proceed for the engineering part
of proposal 224 (next generation hidden service). So, we've put up this pad
with *5* large milestones that will in theory happen one after the other.

Step 1 is shared randomness for which the code and proposal has been finalized
and under review for upstream merge. Yay progress! :)

You'll notice that they are pretty huge milestone. As we go forward, we'll
break them down in much more details (++tickets). You can already see step 2)
has a pad for that already.

Our hope is to update that pad regurlarly as implementation moves forward and
update tor-dev@ as well with relevant information for the community. You to
can help with this huge effort, please come find us on #tor-dev! Code review,
comment on designs, testing, etc..., we'll need a lot of these.

https://storm.torproject.org/shared/TlPhwNbdgPwLw5h23G3gEDtkWdqxVe9Gqn3KiqVlqfJ

Don't hesitate to comment on the roadmap using this thread or you can also do
it in the pad (which is a "Can Comment" link).

Thanks!
David


signature.asc
Description: Digital signature
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] Propsal 263 Quantum-safe Hybrid handshake for Tor, updated feature request v1.2

[Tim Wilson-Brown - teor]

> On 9 Feb 2016, at 02:56, Zhenfei Zhang  wrote:
> 
> Also in the discussion we were talking about the possibility of using 
> non-product form
> polynomial version of NTRUEncrypt, as this version will become patent free by 
> Aug 2017,
> while the patent for product form will last for another 4 years. The main 
> concern is that
> Debian will not allow patented software in the package.  However, through our 
> discussion,
> it turns out that we may be able to include this proposal in the next one of 
> two release of
> Tor. From this point of view, both patent (basic NTRU patent, till 2017 and 
> product form
> patent, till 2021) are going to be an issue if Debian does not agree with 
> SI's patent statement.
> So does it make sense to keep the product form polynomials as they enables 
> roughly 3
> times faster operations on both client side and server side?

I think our priority must be consistency across platforms, rather than 
performance.
(Personally, I really wish NTRU wasn't patented, regardless of the open-source 
patent grant,
then we wouldn't have to be concerned about this.)

As discussed in the meeting last week:
* we have to standardise on one algorithm,
* many tor relays are on debian,
* if debian-legal declines the patent grant for either form, tor won't be able 
to use that form of NTRU on debian,
* and if that is so, tor will have to choose a different form or algorithm.

So it's really up to debian-legal, who I assume we've asked or will be asking.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B

teor at blah dot im
OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F



signature.asc
Description: Message signed with OpenPGP using GPGMail
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] Roadmap - Hidden service next generation (prop224)

[Tim Wilson-Brown - teor]

> On 9 Feb 2016, at 01:01, David Goulet  wrote:
> 
> ...
> Our hope is to update that pad regurlarly as implementation moves forward and
> update tor-dev@ as well with relevant information for the community. You to
> can help with this huge effort, please come find us on #tor-dev! Code review,
> comment on designs, testing, etc..., we'll need a lot of these.
> 
> https://storm.torproject.org/shared/TlPhwNbdgPwLw5h23G3gEDtkWdqxVe9Gqn3KiqVlqfJ
> 
> Don't hesitate to comment on the roadmap using this thread or you can also do
> it in the pad (which is a "Can Comment" link).

I can't seem to edit the pad.
Does the link just allow annotation, or full-blown editing?

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B

teor at blah dot im
OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F



signature.asc
Description: Message signed with OpenPGP using GPGMail
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] Roadmap - Hidden service next generation (prop224)

[David Goulet]

On 09 Feb (08:43:09), Tim Wilson-Brown - teor wrote:
> 
> > On 9 Feb 2016, at 01:01, David Goulet  wrote:
> > 
> > ...
> > Our hope is to update that pad regurlarly as implementation moves forward 
> > and
> > update tor-dev@ as well with relevant information for the community. You to
> > can help with this huge effort, please come find us on #tor-dev! Code 
> > review,
> > comment on designs, testing, etc..., we'll need a lot of these.
> > 
> > https://storm.torproject.org/shared/TlPhwNbdgPwLw5h23G3gEDtkWdqxVe9Gqn3KiqVlqfJ
> > 
> > Don't hesitate to comment on the roadmap using this thread or you can also 
> > do
> > it in the pad (which is a "Can Comment" link).
> 
> I can't seem to edit the pad.
> Does the link just allow annotation, or full-blown editing?

Annotation. Public pad like that, I prefered to avoid giving a full on editing
link and risk someone having fun erasing stuff...

If you would like an Edit link, let me know.

Cheers!
David

> 
> Tim
> 
> Tim Wilson-Brown (teor)
> 
> teor2345 at gmail dot com
> PGP 968F094B
> 
> teor at blah dot im
> OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
> 



> ___
> tor-dev mailing list
> tor-dev@lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev



signature.asc
Description: Digital signature
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] Entry guards, primary guards, dir guards

[George Kadianakis]

Ola Bini  writes:

> Hi again,
>
> Two questions - first, hopefully I simple one. What are directory
> guards, exactly?
>
> Second, we found a weird behavior in the current code
> base. Specifically, when Tor first downloads the microdescriptors, it
> chooses 3 guards for this with the V2Dir flag. That's a little bit
> less than 1600 nodes right now. However, these three guards gets
> persistes as primary guards, which means that almost all Tor users
> will have primary guards among those 1600, not among the 1900 that
> have the Guard flag. Is this intented behavior?
>

Very relevant questions.

Directory guards were intoduced by proposal 207. They are basically guard nodes
for directory connections, so that Tor clients expose themselves to the minimum
number of directory relays when downloading the various Tor documents
(microdescriptors, etc.).

Currently Tor uses the same guardlist for directory guards and entry
guards. That's a feature because ideally you would have a single guard that
would be both your entry guard and your directory guard. Unfortunately, that's
not always possible because some entry guards are not directories (they don't
have the V2Dir flag) so they can't be picked as directory guards. And that's
basically the weird behavior that you noticed. Because Tor pick its directory
guards first and they are picked from a slightly restricted set compared the
total set of guards nodes. Eventually when #12538 gets to stable Tor, all
relays will be directories, and hence all guards will be potential directory
guards.

---

So everything is explained now except from why Tor picks 3 directory guards and
not one. That's because we have decided to keep the number of directory guards
to 3, instead of using a single guard like we do for normal
circuits. Otherwise, that single directory guard could launch some
hard-to-detect route biasing attacks. For more details see:
  https://lists.torproject.org/pipermail/tor-dev/2014-May/006820.html
  https://lists.torproject.org/pipermail/tor-dev/2014-June/006944.html

So basically when Tor picks a directory guard for a directory connection, it
finds the first three reachable entry guards in its guardlist, and picks one of
them.

It might be smart to be able to support "multiple guards" mode in the
algorithms that we are currently designing. That's because we might keep the "3
directory guards" design for some more time, but even more importantly because
if we ever go with a layered guards design we will need to have multiple guards
in some layers.

For example, consider proposal 247 which specifies a layer guard design to
defend against hidden service guard discovery attacks. The proposal basically
makes hidden services pick guard nodes for their second and third hops. So
instead of looking like this:

 -> middle_1 -> middle_A
 -> middle_2 -> middle_B
 -> middle_3 -> middle_C
 -> middle_4 -> middle_D
   HS -> guard   -> middle_5 -> middle_E -> Rendezvous Point
 -> middle_6 -> middle_F
 -> middle_7 -> middle_G
 -> middle_8 -> middle_H
 ->   ...->  ...
 -> middle_n -> middle_n

it will look like this:


  -> guard_3A_A
 -> guard_2_A -> guard_3A_B
  -> guard_3A_C -> Rendezvous Point
   HS -> guard_1
  -> guard_3B_D
 -> guard_2_B -> guard_3B_E
  -> guard_3B_F -> Rendezvous Point


As you can see in this latter design, we pick amongst "2 guard nodes" for the
second hop, and amongst "6 guard nodes" for the third hop. Feel free to read
the introduction of the proposal for more info.

So yeah... it would be nice to support this multiple guard node design in our
algorithms as well. We discussed this a bit during our proposal meeting some
weeks ago but we kind of let it drop. Do you think it's possible? :)
 
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] Entry guards, primary guards, dir guards

[George Kadianakis]

Ola Bini  writes:

> Hey,
>
> Thanks- this is very helpful.
>
> When it comes to vanguards, I've already read through the
> proposal. I'm not exactly sure I understand how much different 259
> would need to be to support the 247 needs. It seems we should be able
> to just run the algorithm NUM_SECOND_GUARDS * NUM_THIRD_GUARDS times
> to choose the sets of vanguards for each layer, right?
>

Hmm, how would that work exactly?

Let's say I'm a prop247 hidden service. I just received an introduction and
want to setup my rendezvous circuit.

To setup my circuit, I would need to do three guard picks, one for every
layer. Each layer has a different guard list.

First, I use my layer-1 guardlist to pick my layer-1 guard. That's easy, I use
a single guard for layer-1, so I always pick the first reachable non-bad guard
from the layer-1 guardlist.

Then I need to use my layer-2 guardlist to pick my layer-2 guard.  Proposal 247
says that each HS has two layer-2 guards , so I would need to pick a guard out
of the two top guards in my layer-2 guardlist. How does this happen exactly?

A similar thing needs to happen for layer-3.

___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] Detailed algorithm

[George Kadianakis]

> Hey,
> 
> So - thinking through your comments and thoughts, I realized that the
> better way to proceed was to describe the algorithm, and then put it
> into a proposal format. The following is updated with most of your
> comments and should be a bit clearer. I decided to remove #241 again,
> since it's unclear how it actually fits together with #259. The idea
> is that the algo is divided into three pieces. If failure is reported
> from the algorithm, the caller can wait for a while or just restart it
> from scratch immediately:
> 

I feel that this algorithm is a step in the right direction! It's interface
logic is quite similar to how Tor picks its guards, and it's more specific than
the previous proposals. It's a good first step so I'll CC tor-dev so that Nick,
Isis and other people can take a look if they want.

After we pin this down, we also need to collect all its security properties in
one place. For example, we should state clearly what security properties the
thresholds GUARDS_TRY_THRESHOLD_TIME and GUARDS_FAILOVER_THRESHOLD provide.

I inline various questions below. I can take a deeper look tomorrow as well.

> - Start of algorithm
>   - Ensure USED_GUARDS is populated (from state file etc)
>   - Create a list of PRIMARY_GUARDS that contain N_PRIMARY_GUARDS that are 
> not bad by:
> - Taking the next entry from USED_GUARDS
> - If USED_GUARDS is empty:
>   - randomly select an entry from UTOPIC_GUARDS, weighted by bandwidth

Hmm. PRIMARY_GUARDS stays like this for ever?

It probably needs to be updated when a primary guard get removed from the
consensus (become bad), and put the next entry of USED_GUARDS in its place.

Maybe we need another event (and algorithm) for "receive new consensus"?
Or is this considered out of scope?

>   - Set TRIED_GUARDS to be an empty set

Hm. What is the point of TRIED_GUARDS? It's like a list of guards that we found
unreachable at some point in time. It's never cleaned, so it will eventually
accumulate many nodes. IIUC, we only use that list to enforce our thresholds by
looking at timestamps.

Can we do without this list, just by checking the timestamps of unreachable
USED_GUARDS?  Or the logic will be much more complicated?

>   - Set TRIED_DYSTOPIC_GUARDS to be an empty set
>   - Set state = STATE_PRIMARY_GUARDS
> 
> - Each iteration of algorithm
>   - If it was at least 3 minutes since we tried the primary guards and we are 
> not in STATE_PRIMARY_GUARDS:
> - save previous state
> - set state = STATE_PRIMARY_GUARDS
> 
>   - STATE_PRIMARY_GUARDS:
> - return each entry in PRIMARY_GUARDS in turn
>   - mark each entry as "unreachable" if algorithm doesn't terminate

What is the "algorithm" here? Is it the guard selection algorithm, or the
circuit construction algorithm? I guess the latter?

If it's indeed the circuit construction algorithm, then the steps here are not
asynchronous anymore, which diverges from how Tor networking is designed. Maybe
this could be fixed by introducing some new states for when we are waiting for
a circuit to connect and we are now learning whether it was succesful or
not. Basically what entry_guard_register_connect_status() does in Tor right
now.

For example we could have STATE_WAITING_FOR_PRIMARY_GUARD_CIRCUIT for when we
are waiting for a primary guard circuit to connect. If it fails, then we need
to mark the entry as unreachable. Maybe we also need
STATE_WAITING_FOR_UTOPIC_GUARD_CIRCUIT etc.

> - restore previous state (or STATE_TRY_UTOPIC if no previous)
>
> 
>   - STATE_TRY_UTOPIC:
> - for each entry in TRIED_GUARDS that was marked as unreachable more than 
> 20 minutes ago
>   - add to the front of remaining UTOPIC_GUARDS

Isn't it already in UTOPIC_GUARDS? I don't see us ever removing stuff from 
UTOPIC_GUARDS.

BTW, what is this step supposed to do? Setup previously TRIED_GUARDS to be 
retried?

> - return each remaining entry from USED_GUARDS in turn
>   - for each entry, if algorithm doesn't terminate
> - mark entry as "unreachable"
> - add entry to TRIED_GUARDS

Add it there even if it it's already there (TRIED_GUARDS is never cleaned)?
Or maybe update a timestamp if it's already there? How to specify this nicely?

> - if the number of entries in TRIED_GUARDS that were tried within 
> GUARDS_TRY_THRESHOLD_TIME
>   is larger than GUARDS_TRY_THRESHOLD, return failure from the 
> algorithm
> - if the number of entries in TRIED_GUARDS is larger than a 
> GUARDS_FAILOVER_THRESHOLD
>   proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC
> - return each remaining entry from UTOPIC_GUARDS randomly selected, 
> weighted by bandwidth
>   - for each entry, if algorithm doesn't terminate
> - mark entry as "unreachable"
> - add entry to TRIED_GUARDS
> - if the number of entries in TRIED_GUARDS that were tried within 
> GUARDS_TRY_THRESHOLD_TIME
>   is larger than GUARDS_TRY_THRESHOLD, return 

[tor-dev] Onion (Hidden) Service Proposal Discussion

[Tim Wilson-Brown - teor]

Hi,

We just had a meeting to discuss the following tor proposals[0] in the #tor-dev 
IRC channel[1].

Proposal 252: Single Onion Services
Proposal 260: Rendezvous Single Onion Services
Proposal 255: Controller features to allow for load-balancing hidden services
Proposal 246: Merging Hidden Service Directories and Introduction Points

A quick summary of each proposal:

Some onion (hidden) service websites don't need to hide their location.
They can have faster connection setup and bandwidth, and put less load on the 
tor network, by having 3 relays between the client and onion service.

Proposal 252 has the onion service open an ORPort, and then clients extend from 
their third relay to the ORPort.
Proposal 260 has the onion service connect directly to the introduction and 
rendezvous points.

The other proposals improve onion service speed in different ways:

Proposal 255 improves hidden or onion service load balancing by handing off the 
rendezvous to another tor instance.

Proposal 246 improves hidden or onion service setup time by using the HSDirs as 
introduction points, and teaching clients to re-use the HSDir connection for 
the introduction.

And a quick summary of our thoughts:

Proposal 252 and Proposal 260 achieve similar outcomes. 260 is simpler to code, 
preserves NAT-punching (which some website providers need), and has already 
been coded[2]. It's also compatible with 255, which 252 is not. But 252 has a 
faster connection set-up time, because it skips the rendezvous protocol 
entirely. We'd like to see more research into the performance differences 
between 252 and 260.

We want to focus on Proposal 224 (next-generation hidden services), and we were 
concerned that too much other work on onion service proposals would slow that 
down. So we'd like to finish 260 in the short term, and then reconsider 252 
based on resourcing and research outcomes.

We thought that 255 was a good idea, but noted that it increases connection 
set-up time.

We noted that 246 already had concerns raised about it on the mailing list. 
That said, we could use 246 to improve the performance of 260.

Tim

[0]: https://gitweb.torproject.org/torspec.git/tree/proposals 

[1]: http://meetbot.debian.net/tor-dev/2016/tor-dev.2016-02-08-22.00.log.html 

[2]: https://trac.torproject.org/projects/tor/ticket/17178 



Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B

teor at blah dot im
OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F



signature.asc
Description: Message signed with OpenPGP using GPGMail
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev