I think there's value in publishing this document, but I agree with Watson
that we should improve its security recommendations.
that we should improve its security recommendations.
Back in 2019, Google servers took some damage from a DoS attack that was
inducing collisions in our QUIC connection ID hash table. Our solution was
to use SipHash for that hash table, with a random key generated at process
startup. SipHash is fast enough that we found it usable for a hash table
that is queried on every single QUIC packet received by the Google Front End.
inducing collisions in our QUIC connection ID hash table. Our solution was
to use SipHash for that hash table, with a random key generated at process
startup. SipHash is fast enough that we found it usable for a hash table
that is queried on every single QUIC packet received by the Google Front End.
The draft currently mentions this issue in its security recommendations
subsection about collisions [1], but it currently recommends still using
FNV1a with an unknown offset_basis as the solution. I think this
section should instead recommend using a cryptographic hash for such
use cases.
David
On Mon, Oct 14, 2024 at 11:06 AM Watson Ladd <watsonbladd@xxxxxxxxx> wrote:
On Sat, Oct 12, 2024, 6:26 PM Brian E Carpenter
<brian.e.carpenter@xxxxxxxxx> wrote:
>
> Thanks.
>
> [0] is now at http://www.usenix.org/events/sec03/tech/full_papers/crosby/crosby.pdf
> and is considerably easier to understand than what I found.
>
> I'm sure a warning can be crafted that is not as global as "usage in new applications and
> protocols".
The question is out of all the hash functions why FNV over SipHash, or
Murmer, or an e-universal hash that will be faster. FNV only processes
one byte per mul and xor, which is pretty slow, and can't easily be
parallelized or vectorized the way more principled universal hash
functions can be. A lot of applications mentioned in the draft are
ones where collisions are observable by an attacker and could be
problematic.
We do need some sort of guidance and improvement in the security
section, but that can be more crafted.
Sincerely,
Watson
>
>
> Regards
> Brian Carpenter
>
> On 13-Oct-24 12:22, Eric Rescorla wrote:
> >
> >
> > On Sat, Oct 12, 2024 at 1:05 PM Brian E Carpenter <brian.e.carpenter@xxxxxxxxx <mailto:brian.e.carpenter@xxxxxxxxx>> wrote:
> >
> > On 12-Oct-24 09:10, Watson Ladd wrote:
> > > Dear all,
> > >
> > > I have reviewed this document as part of the security directorate's
> > > ongoing effort to review all IETF documents being processed by the
> > > IESG. These comments were written primarily for the benefit of the
> > > security area directors. Document editors and WG chairs should treat
> > > these comments just like any other last call comments.
> > >
> > > The summary of the review is Not Ready.
> > >
> > > The draft does a good job of describing the FNV-1a hash function.
> > > However, it falls short on recommending when it should be used and
> > > when it should not be. Python had to change away from FNV-1a due to
> > > collision attacks leading to DoS (https://peps.python.org/pep-0456/ <https://peps.python.org/pep-0456/>,
> > > https://www.youtube.com/watch?v=Vdrab3sB7MU <https://www.youtube.com/watch?v=Vdrab3sB7MU>). The offset is
> > > insufficient to solve this problem. FNV-1a is slower than other hash
> > > functions with better guarantees of equidistribution, taking one
> > > multiply per byte and is hard to parallelize. I think this draft needs
> > > to say these things, and advise against usage in new applications and
> > > protocols.
> >
> > Isn't that a bit too wide? It took me a while to track it down, but
> > it seems that the original exposition of this problem is at
> > http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf <http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf>
> >
> > That seems too narrow an attack to justify avoiding it in *all*
> > new applications and protocols. The whole world is not HTTP POST.
> >
> >
> > There certainly are other instances of this class of attack. Here's
> > the earliest publication that I'm aware of from Crosby and Wallach
> > 2003 [0]. In general any time you have a system that deterministically
> > stores attacker provided data under a lookup key controlled by the
> > attacker, you have the potential for this type of algorithmic
> > complexity attack. It's not just Python either, Rust hash tables are
> > constructed using a keyed hash [1].
> >
> > -Ekr
> >
> > [0] https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-algorithmic-complexity-attack <https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-algorithmic-complexity-attack>
> > [1] https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get <https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get>
> >
> >
--
last-call mailing list -- last-call@xxxxxxxx
To unsubscribe send an email to last-call-leave@xxxxxxxx
-- last-call mailing list -- last-call@xxxxxxxx To unsubscribe send an email to last-call-leave@xxxxxxxx
