On Sat, Oct 12, 2024 at 1:05 PM Brian E Carpenter <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://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
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].
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
[1] https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get
[1] 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
