Presents xmx (xor-multiply-xor), a new symmetric block cipher optimized for public-key libraries and microcontrollers with arithmetic coprocessors. xmx has no S-boxes and uses only modular multiplications and XORs. The complete scheme can be described by a couple of compact formulae that offer several interesting time-space trade-offs (number of rounds/key-size for constant security). In practice, xmx appears to be tiny and fast: 136 code bytes and a 121 kbit/s throughput on a Siemens SLE44CR80s smart-card (5 MHz oscillator)