Hi!
On 4/23/26 19:23, Vittorio wrote:
on the O(n·m) complexity, streaming optimises the memory access pattern
but does not change the computational complexity of full chain
verification.
You're right if all intermediate steps are needed (even if only to
check their hashes).
If you just need the first version, then I still venture it's O(n)
only:
The input message has n lines (or octets).
So the _cumulated_ rulesets are bounded by O(n).
You can first merge the rulesets, which I think is O(m) with
m being the total size of the rulesets both in terms of time
and in terms of memory (output size).
Then you can execute the rules, which is O(m) instructions,
and the total result is bounded in O(n).
That result is usable to verify i=1.
The monotonicity constraint on "c" recipes enables
sequential processing for that specific recipe type when using header-
based transport - but as you noted in your own review of 16 April 2026,
non-monotone recipes make streaming with bounded memory impossible, and
this applies if MIME epilogue transport is adopted. DKIM2-core
verification remains O(1) per hop regardless: one hash, one signature,
one bh= comparison, independent of chain length and message size.
You mean O(n) because you need to hash the whole message at least once.
On the 32KB header buffer question: the concern is not that large
headers cannot exist today. The concern is what happens when an
antivirus gateway operating under DKIM2-extended logic encodes a removed
attachment into a Message-Instance header.
They won't. That's the use-case of null recipes, and will be done
close to the receiver or on behalf of the sender.
[...]
Hannah.
--
Hannah Stern
Software Developer
Mail Transfer Development
1&1 Mail & Media Development & Technology GmbH | | |
Phone: +49 721 91374-4519
E-Mail: [email protected] | Web: www.mail-and-media.com www.gmx.net
www.web.de www.mail.com www.united-internet-media.de
Hauptsitz Montabaur, Amtsgericht Montabaur, HRB 5452
Geschäftsführer: Alexander Charles, Dr. Michael Hagenau, Thomas Ludwig,
Dr. Verena Patzelt
Member of United Internet
Diese E-Mail kann vertrauliche und/oder gesetzlich geschützte
Informationen enthalten. Wenn Sie nicht der bestimmungsgemäße Adressat
sind oder diese E-Mail irrtümlich erhalten haben, unterrichten Sie bitte
den Absender und vernichten Sie diese E-Mail. Anderen als dem
bestimmungsgemäßen Adressaten ist untersagt, diese E-Mail zu speichern,
weiterzuleiten oder ihren Inhalt auf welche Weise auch immer zu verwenden.
This e-mail may contain confidential and/or privileged information. If
you are not the intended recipient of this e-mail, you are hereby
notified that saving, distribution or use of the content of this e-mail
in any way is prohibited. If you have received this e-mail in error,
please notify the sender and delete the e-mail.
_______________________________________________
Ietf-dkim mailing list -- [email protected]
To unsubscribe send an email to [email protected]
