Implementing CAESAR candidate Prøst on ARM11


  • Thom Wiggers Radboud University Nijmegen


Prøst was a contestant in the CAESAR competition for Authenticated Encryption. I optimised Prøst for the ARM11 microprocessor architecture. By trying to find a provably minimal program for one of the sub-operations, I found a new approach to implementing MixSlices, one of the sub-operations in Prøst's permute function. This new implementation has 33% fewer arithmetic operations than the original version. Using this result and by implementing Prøst in assembly and applying micro-optimisations, a performance gain of 28% to 48% was achieved.

Author Biography

Thom Wiggers, Radboud University Nijmegen

Institute for Computing and Information Sciences


Andreeva, E., Bilgin, B., Bogdanov, A., Luykx, A., Mennink,

B., Mouha, N., and Yasuda, K. APE: authenticated

permutation-based encryption for lightweight cryptography.

Cryptology ePrint Archive, Report 2013/791.


Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B.,

Tischhauser, E., and Yasuda, K. Parallelizable and

authenticated online ciphers. Cryptology ePrint Archive,

Report 2013/790. 2013. address: http://eprint.iacr.


ARM Limited. Arm1176jzf-s technical reference manual.

Revision: r0p7. address: http://infocenter.arm.



Bellare, M., Rogaway, P., andWagner, D. A conventional

authenticated-encryption mode. 2003. Address:


D. J. Bernstein and T. Lange, eds. Supercop. eBACS:

ECRYPT Benchmarking of Cryptographic Systems.


Boyar, J., Matthews, P., and Peralta, R. Logic minimization

techniques with applications to cryptology.

Journal of Cryptology, 26(2), 2013: 280–312.

CAESAR: competition for authenticated encryption:

security, applicability, and robustness. Address: http:


Dobraunig, C., Eichlseder, M., and Mendel, F. Relatedkey

forgeries for Prøst-OTR. Cryptology ePrint Archive,

Report 2015/091. 2015. address: http://eprint.iacr.


Fuhs, C., and Schneider-Kamp, P. Synthesizing shortest

linear straight-line programs over GF(2) using SAT.

Proc. SAT’10, 71–84.

Kavun, E. B., Lauridsen, M. M., Leander, G., Rechberger,

C., Schwabe, P., and Yalc¸ın, T. Prøst v1.1. 21st June



Krawczyk, H. The order of encryption and authentication

for protecting communications (or: how secure is

ssl?) Advances in Cryptology – CRYPTO 2001. 2001,


Le Berre, D., and Parrain, A. The sat4j library, release

2 system description. Journal on Satisfiability,

Boolean Modeling and Computation, 7, 2010: 59–64.

McGrew, D. A., and Viega, J. The galois/counter mode

of operation (GCM). address:



Minematsu, K. Parallelizable rate-1 authenticated

encryption from pseudorandom functions. Cryptology

ePrint Archive, Report 2013/628. 2013. address: http:


Papadimitriou, C. H., and Yannakakis, M. Optimization,

approximation, and complexity classes. Journal of

Computer and System Sciences, 43(3), 1991: 425–440.

Rijneveld, J. Implementing Prøst on the Cortex A8

using internal parallelisation. 2015-01. Address: https:



Rogaway, P. Authenticated-encryption with associated-

data. Proceedings of the 9th ACM conference on

Computer and communications security. 2002, 98–107.






Economics & Social Sciences