No, the cookie could be done using RSA, somewhat like a PGP signature.
You only need to keep the kernel itself and/or lilo readonly.
>From what I've heard, the elf binary format makes it easy to attach
stuff like this to the end of an executable.
This way root just signs all suid executables and the kernel
checks for the signature before running them.