On Mon, Oct 14, 2024 at 4:04 PM Brian E Carpenter <brian.e.carpenter@xxxxxxxxx> wrote: > > On 15-Oct-24 07:50, Eliot Lear wrote: > > I said this privately, so I guess I'll ask it publicly: > > > > Is there value in a BCP to discuss what hash should be used in what circumstances? > > TL;DR: Yes. I would agree that such a draft would be useful and if someone starts one I'd be happy to help. Thanks, Donald =============================== Donald E. Eastlake 3rd +1-508-333-2270 (cell) 2386 Panoramic Circle, Apopka, FL 32703 USA d3e3e3@xxxxxxxxx > I was quite surprised to discover that there was no such document when we drafted RFC 6437. And even more surprised recently when seeing this thread. > > Brian > > > > > Eliot > > > > On 14.10.2024 20:42, David Schinazi wrote: > >> I think there's value in publishing this document, but I agree with Watson > >> 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. > >> > >> 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 > >> > >> [1] https://datatracker.ietf.org/doc/html/draft-eastlake-fnv-20#section-7.2 > >> > >> 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
