qid/dispid recycling vs. Tor circuit isolation

[Rusty Bird]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Hi!

So, the qid/dispid of a removed VM can be recycled immediately. When
that happens inside a 10 minute window*, it could break inter-VM Tor
circuit isolation, which is based on the VMs' IP addresses.

For dispids, a relevant collision happens with ~ n/10000 probability
(where n is the number of recently removed DispVMs). For qids, which
are allocated "lowest first", it seems to me that it should be more
likely to happen in practise (depending on the balance of deleted and
created VMs). Consider something like the following, where two VMs
both connect via sys-whonix:

qvm-kill identity1
qvm-remove identity1
qvm-create identity2
qvm-start identity2

Better not rely on circuit isolation between those two identities...
(As a workaround, the user can create the new VM _before_ removing the
old VM, if they are aware of this issue.)

Proposal:

Let's keep two lists, recording qids/dispids freed since boot, similar
to DISPID_STATE_FILE in R3.2. VMCollection's __delitem__() would be
wrapped in a lock and add the qid/dispid to the lists.

Then get_new_unused_qid/dispid() would acquire the lock and randomly
choose a new id from the applicable number range that is neither in
use, nor on the freed list. If this fails, it would expire some old
entries from the freed list, i.e. the oldest qid or a batch of the
oldest dispids, and retry.

Does this look okay?

Rusty


* Or whatever timeout is configured as tor's MaxCircuitDirtiness
-----BEGIN PGP SIGNATURE-----

iQJ8BAEBCgBmBQJaTW8jXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXQ4NEI1OUJDRkM2MkIxMjlGRTFCMDZEMDQ0
NjlENzhGNDdBQUYyQURGAAoJEEadePR6ryrf9KsQAILsq77RF6ku7SFxwoTcAOJU
4W7kqNV37Bisig8aI0l6V54fS0yA5gbSzTwm5vjGaeTV/wrCsv2k0FJRrI53rWoM
6pQaLjv2l8LO2GrVwvPrAwWAoSnSjIs+rl8LhTcbBy0bL/mx/vJrxZkwdtsdhhqC
5o5hslV5Pw1+m6bbULT+R13muQ1/DAA71ukyX8qCbwDZA+u7Po+EexuwkDar4bAC
izK6L8Rr8W6/ZHPskJJgy9LcxpmBm+70n79foi5CYwjmPNTyJxGEV97qMpgcyzss
SQ6DDkS1RHF4Pp0IwTs46AqeoHEEGFajHu3twmLwwEJFEILbsm3dcxhGmtzUFmYt
VmgpfoiruOMcFs2j+qvr3A+IfsaNi7v32JVnIqCYX8XnaqrAPqjgrvFYQ/EUu8oJ
8+gKdzJlHb/LhYqpMcBON98x8FLWpIgOhUaQFmOtoTxmIyYZXDEGcb3BJsHW6xy7
BHEXLU+MQCNBVkfX/XSeCZsH9f2x+CvQBQ7T/86HQk8EVuCs5LGLHFuecOzKKi4V
BiPhN+sqDXrJcf7ZH8VugoahZN8dBe/rTyUwLavdTfxTGwJqv7VlmbdwlCMTKCq8
f5Z7LRD7neldkdmkOXho5eMQEQ8sfayFfMXMPcTsReccZznDgFZ0jeKfOv/v6WAG
2w2I7udGNbWqPfc1ZnIH
=/1Vt
-----END PGP SIGNATURE-----

[Jean-Philippe Ouellet]

+1

Did this go anywhere?

[Rusty Bird]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Jean-Philippe Ouellet:

No (sad trombone). Part of why is that the case I care most about
(dispid collision) _feels_ unlikely enough (and for Tor Browser is
mitigated by its per-startup circuit isolation nonce) that it never
seemed urgent to pester the core folks for feedback. Especially since
it might take me a while to actually get around to implementation.
This assumes nobody else wants to do it, hint hint...

One possible simplification of the scheme would be to choose the qid
at random instead of lowest-first when creating any new VM; bump up
max_qid from 254 to e.g. 2^16-1 (which has been proposed for a long
time); and use the qid in the dispN name and the IP address, instead
of a separate dispid - so there'd be only one "recently freed"
blacklist to maintain.

Rusty
-----BEGIN PGP SIGNATURE-----

iQJ8BAEBCgBmBQJbg+f+XxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXQ4NEI1OUJDRkM2MkIxMjlGRTFCMDZEMDQ0
NjlENzhGNDdBQUYyQURGAAoJEEadePR6ryrfMWEP/3Ein1qUmXBOe30tTc/bRWiK
XAEzyLiU4dEU9hmk0m4zE0DJDhTxcvI/XS3DVN3dXj25iE7U+JQ2bZAfhfQbbXhi
wPsPH2L9sXxsZgl0P2nJRtXJslygQhHOh1jSglOlf4mVDGcKfz4UpKkddLDVRt4h
3HfbUd8mMtLA2h3TgEQrj29BDxpxvf1x3A1kwj1y/avZDqhZzNJsecpbCEnEnaas
/MGx4QrBC4q7rNZRCQRj+2XcYNK8BDCJxu/4TeBKqjLXZu+/uFxxodGfE49P5FJ6
3pvKZ/omBpiK+qzbP4vHqcqeFzRFsifdt8BnNZB1E3piQBsu3+/n1XyMgsCk28uS
L0/OyV0HKmqB7IX3gNIfiCum+o0EMCHbvYg6+dQucawIuxKoGh8y7bSl3swR872E
fLw7W4tsU7pXJ2yIW/iFudM818dXQnaMSjKhcdkGyH6SXjvPHNDEFKut5Bnz19Dw
YE2ixryqcXDBXNNMFpDEC8WJxMk1P9YT8fJkt5agY74kNqUFtaZ0FEkVP06h2GTC
vDkWm9dllvo7xtl+AhNclBuq0WiquIY8afgpiQfgjzbWm8UtuFhFQ/HIMUwR3F1v
gqpgHEmFEgGSurgnKkQbC7DxVdh2Jh6hR14D4IQzmalrzVaMtqB1YKACSXaxa64j
VDrbm2ty6mkLVuiWPFSX
=aLzW
-----END PGP SIGNATURE-----