Breaking and (Partially) Fixing Provably Secure Onion Routing

[grarpamp]

https://arxiv.org/abs/1910.13772

After several years of research on onion routing, Camenisch and
Lysyanskaya, in an attempt at rigorous analysis, defined an ideal
functionality in the universal composability model, together with
properties that protocols have to meet to achieve provable security. A
whole family of systems based their security proofs on this work.
However, analyzing HORNET and Sphinx, two instances from this family,
we show that this proof strategy is broken. We discover a previously
unknown vulnerability that breaks anonymity completely, and explain a
known one. Both should not exist if privacy is proven correctly. In
this work, we analyze and fix the proof strategy used for this family
of systems. After proving the efficacy of the ideal functionality, we
show how the original properties are flawed and suggest improved,
effective properties in their place. Finally, we discover another
common mistake in the proofs. We demonstrate how to avoid it by
showing our improved properties for one protocol, thus partially
fixing the family of provably secure onion routing protocols.