This paper studies the issues of flexibility and scalability in the context of network security. In particular, it concentrates on authentication and key distribution services suited for a variety of communication paradigms, network environments, and end-devices. We present the design criteria, specification, and step-by-step construction of authentication and key distribution services based on experience in the KryptoKnight project. The central goal of the KryptoKnight project was the construction of basic network security functions in a minimal, flexible (thus, versatile) and scalable manner. Protocol minimality (in terms of resource usage) and flexibility are not merely theoretical goals; they have clear advantages in environments where computational resources are limited and connectivity is restricted. KryptoKnight was aimed at such environments: small and anemic wireless devices, simple network and data-link entities, embedded micro-devices and other special-purpose communication equipment and configurations. Furthermore, scalability of protocols makes their deployment possible in the presence of rapid network growth and inter-domain communication.