What are the security related challenges in implementing something like Unix sudo?

There are two primary challenges, though both are somewhat complex.

The first is common to any "setuid" program which is owned by root (or another highly-privileged user, but mostly root); this property of an executable file (it's a bit set on the file permissions) causes the program to be run with the privileges of the owner of the file, rather than the permissions of whoever launched it. This is a standard Unix/Linux feature, and is how sudo works to run programs elevated (it has this bit set, and is owned by root). However, it's a risky design. There are a number of pitfalls with setuid root programs, many of which stem from the fact that you have an elevated process that is inheriting its execution environment - pty, process tree, environment variables, working directory, standard streams, etc. - from an untrusted source (an unprivileged process, typically a shell). To safely execute the authorized operations without accidentally executing unauthorized ones requires considerable care! For example, suppose the process needs to dynamically load a library by calling dlopen; normally this could cause the LD_LIBRARY_PATH environment variable to be searched for the library file, but that's unsafe when an attacker might have set it, so for setuid (or setgid) processes, that variable is ignored. This kind of "clean up" must be performed in a bunch of places, by various parties (the program's developer, the libraries it uses including the standard library as in dlopen, and even the OS itself), and any time a new kind of inherited execution context is added (e.g. cgroups) or an existing one is used in a new way (e.g. a new use for an existing environment variable), we run the risk of this causing a vulnerability for any setuid program. It's not impossible to do this clean up correctly - after all, sudo has been a part of Unix/Linux for decades now - but it's a substantial risk. Such "cleaning" is insecure by default; you need to correctly do everything necessary to be safe, not just avoid doing something to become unsafe.

A safer alternative would avoid inheriting anything, in so far as that can safely and meaningfully be done, and run in an execution environment that is only controllable by other privileged processes (e.g. a clean login shell in the root profile, using a new pty and so forth). This risks making the tool somewhat less useful, but most of the time it should be fine, and additional compatibility or convenience functionality can be carefully added back, narrowly and after thorough security review, rather than needing to be pruned down to only what is safe and necessary.

The second security challenge with sudo is that it's actually a fairly complicated program in its own right, with a file parser and the ability to interact with network servers, plus the need to correctly identify and carry out the authorized actions. None of this is very relevant if you simply invoke it interactively on your personal machine and supply a password on demand to run a program elevated, but it becomes very relevant indeed in an organizational or automated setting, where the contents of the sudoers file and LDAP server and various plugins can drastically increase the attack surface of the tool. Then, it needs to determine exactly what it's supposed to do - making sure that the command it was passed matches the allowed set of parameters for for automatic execution of the specified program as a particular user, for example - and launch that process with in the authorized way.

While such advanced functionality would be very hard for system administrators to give up - after all, it all exists to address a need somebody had (or expected to have) - re-creating it securely would be very difficult. With most programs, if they parse a parameter flag or config file wrongly, the resulting bug is merely frustrating; with sudo, a bug could result in an unprivileged user taking over the system. That's a difficult level of security assurance to meet in a complicated program, and a replacement that loses most of the advanced functionality in exchange for vastly reduced complexity would be preferred for most machines that never need the advanced tricks.