4-bit microcontrollers (MCUs) are among the simplest, cheapest and most abundant computing devices that, thanks to their low power consumption, may be deployed even in passive RFID tags. Besides, 4-bit MCUs are embedded in a wide variety of daily-life objects that, when connected to a network, could become a substantial part of the Internet of Things. Despite the fact that quite a number of applications are security sensitive, no implementation of standardized cryptography has been available yet. In this work we present the first implementation of the Advanced Encryption Standard (AES) on a 4-bit MCU and thus, by closing this gap, enable security functionalities on myriads of legacy devices. Besides, we describe the first software implementation of PRINTcipher, a recently proposed block cipher optimized for printed electronics. We describe and apply various optimization techniques to develop time and code-size efficient implementations on the MARC4. As a result our AES implementation is not only the first on a 4-bit MCU, but also the most efficient among all cryptographic algorithms.