On Sat, 10 Jul 2004, Dave Crocker wrote:
By the way, the IESG is going to ask about the computational
complexity and load of this mechanism, and of the exposure to DOS
attacks. I've just had them challenge a rather more modest spec on
these grounds.
I reviewed the SPF spec from this point of view a couple of months ago,
and I concluded that it was only just short of being Turing-complete
(ignoring the implementation limits that restrict the size of the
computation). A slight enhancement to the macro language would give it
full computational ability.
http://archives.listbox.com/spf-discuss(_at_)v2(_dot_)listbox(_dot_)com/200405/0075.html
http://archives.listbox.com/spf-discuss(_at_)v2(_dot_)listbox(_dot_)com/200405/0080.html
However from the point of view of protocol design Turing completeness
isn't such an important property. Based on some quick hand-waving, I
believe it is possible to create SPF records that require an execution
time that's exponential in the size of the record, with storage
requirements that are linear in the record size. I can't think of a
construction that would require enormous storage.
Implementation limits are ABSOLUTELY REQUIRED to avoid problems.
I have not reviewed the current specification with this in mind.
Tony.
--
f.a.n.finch <dot(_at_)dotat(_dot_)at> http://dotat.at/
FAEROES SOUTHEAST ICELAND: VARIABLE 3 OR 4. OCCASIONAL RAIN OR DRIZZLE.
MODERATE OR GOOD &NBSP;.