<commit_before>\documentclass[11pt]{llncs2e} % change this around if you don't have lncs style installed
%\documentclass[11pt]{article}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{color}
\usepackage{tabularx}
%\usepackage{wrapfig}
\usepackage{float}
%\usepackage{fullpage}
\usepackage{hyperref}

\usepackage{graphicx}
\usepackage{url}
\usepackage{sidecap}
\usepackage{epstopdf}

\def\bibfont{\scriptsize}
\usepackage{natbib}
\setlength{\bibsep}{0.0pt}

\renewcommand\refname{References}
\renewcommand\bibname{References}

\lstset{basicstyle=\scriptsize\sffamily}
%\lstset{language=Assembler}[avr8avra] % not standard
\lstdefinestyle{customasm}{
  morekeywords={adc,adiw,asr,brtc,brcs,brhs,brne,cbr,clh,clr,clt,cp,cpi,dec,eor,ldi,lpm,lsl,nop,mov,or,rcall,ret,seh,set,subi,swap,rjmp},
  morecomment=[l][\color{blue}]{;}
}
\lstset{style=customasm}

\begin{document}
\title{Speed and Size-Optimized Implementations of the PRESENT Cipher for Tiny AVR Devices}
%\title{\textbf{PRESENT Cipher for tinyAVR Architectures}}

\author{<NAME> and <NAME>}
\institute{Radboud Universiteit Nijmegen}
%\date{}
%\conference{RFIDsec 2013, Graz, Austria}
\maketitle

\begin{abstract}
This paper presents high-speed and low-size assembly implementations of the 80-bit version of the PRESENT cipher for the AVRtiny family of microcontrollers. We report new speed and size records for our implementation, with the speed-optimized version achieving a full encryption in 8721 clock cycles and the size-optimized version compressing the cipher down to 280 bytes; the previous state of the art for AVRtiny achieved 10723 clock cycles for encryption with a size of 936 bytes. Along with the two implementation extrema (speed \& size optimized versions), we offer insight into techniques and representations that show the speed/area tradeoffs and provide intermediate solutions for various configurations.\\
\textbf{Key words}: PRESENT, AVR, ATtiny, AVR Assembly, software implementation
\end{abstract}
\section{Introduction}
Modern society is constantly witnessing an extensive and large scale deployment of tiny computing devices. Information processing and wireless communication are being thoroughly integrated into everyday objects and activities, developing a large distributed mobile infrastructure and ushering in the era of ubiquitous computing. RFID tags attached to products, cardiac pacemakers, fire-detecting sensor nodes and the like need to operate \emph{securely} under particularly \emph{restricted conditions}, namely low battery life, small processing power and bandwidth-demanding ad-hoc network protocols. To achieve sustainable security in this new landscape, researchers have developed new cryptographic primitives and techniques, namely lightweight cryptographic ciphers such as PRESENT~\cite{bogdanov2007present}, Klein~\cite{gong2012klein}, LED~\cite{guo2011led} and others.

The majority of these ciphers was designed with hardware performance in mind, leaving most software implementations relatively inefficient. For instance, the AVR-Crypto-Lib~\cite{avr_crypto_lib} often resorts to C language implementations, resulting in 100.000 clock cycles for a single encryption with PRESENT.
AVR microcontrollers are often encountered regarding the Internet of Things and ubiquitous computing, and moreover serve as a good model of a limited instruction set architecture, thus they are an interesting platform on which to enable and optimize lightweight ciphers.
The University of Leuven has initiated a project to draft efficient assembly implementations of various lightweight ciphers on resource-constrained AVR devices to make fair comparisons about their relative efficiency. The contribution by Eisenbarth~\cite{eisenbarth2012compact} achieves an encryption with PRESENT in roughly 11.000 clock cycles.

\textbf{Our contribution.} This paper describes a speed-optimized and a size-optimized implementation of the PRESENT cipher on the ATtiny45, with the aid of algorithmic improvements and efficient programming techniques. Our speed-optimized version improves the state of the art~\cite{eisenbarth2012compact} by 18\%, while the size-optimized version is 70\% smaller than the smallest known implementation~\cite{eisenbarth2012compact}.\\
Algorithmic improvement:
\begin{itemize}[nolistsep]
  \item A merged SP layer, \emph{i.e.} combining the substitution and permutation layer of the cipher in order to construct lookup tables that remove the time-consuming permutations~\cite{gong_code}. This improvement constitutes the core of the achieved speed improvement.
\end{itemize}
Programming improvements:
\begin{itemize}[nolistsep]
  \item Squared S-Box representations, \emph{i.e.} S-Boxes which are custom-made for fast access in the AVR 8-bit architecture, also used by Eisenbarth~\cite{eisenbarth2012compact}.
  \item Compact S-Box representations, \emph{i.e.} minimal footprint S-Boxes that reduce the implementation size.
  \item Minimal key register rotations, allowing the key update procedure to complete in fewer instructions.
  \item Memory access optimizations, grouping memory transactions to improve speed.
  \item Algorithm serialization, by keeping part of the state in SRAM while we operate on fewer registers.
  \item Indirect register access to let loops drive repeated operations on CPU registers.
  \item Use of the stack to store intermediate values to avoid more dedicated registers.
  \item Code restructuring and efficient procedure callings.
\end{itemize}
We note that some of the improvements are interoperable and can be combined to provide the ``golden ratio" between speed and size, depending on the external requirements.\\
\textbf{Paper organization.} The organization of the paper follows. Section 2 provides an introduction to the AVR architecture, including the capabilities and limitations of AVRtiny microcontrollers. Section 3 focuses on high-speed implementation of the PRESENT cipher, regarding efficient S-Box representations and lookup tables. Section 4 describes various techniques that produce a very compact version of the cipher. Section 5 provides the final benchmarking results and conclusions.

\section{Background}
\subsection{PRESENT Cipher}
 PRESENT~\cite{bogdanov2007present} is an ultra-lightweight, 64-bit symmetric block cipher, using 80-bit or 128-bit keys.
It is based on a substitution/permutation network and it is named as a reference to Serpent~\cite{anderson1998serpent} due to its similar constructs.
As of 2012, PRESENT (among other ciphers) was adopted by ISO as a standard for a lightweight block cipher (ISO/IEC 29192-2:2012~\cite{present_iso}). The full algorithm has so far been resistant to attempts at cryptanalysis, although the most successful attack has shown that up to 15 of its 31 rounds can be broken with $2^{35.6}$ plaintext-ciphertext pairs in $2^{20}$ operations~\cite{abed2012biclique,collard2009statistical,nakahara2009linear}.

PRESENT uses exclusive-or as its round key operation, a 4-bit substitution layer, a 4-bit period bit position permutation network in 31 rounds and a final round key operation.
Key scheduling is a combination of bit rotation, S-Box application and exclusive-or with the round counter.
%We chose PRESENT as a cipher to work on within a project to write and optimize AVR crypto code %because we deemed it extremely well-suited for a simple microcontroller, and felt it was within our %grasp to implement and optimize correctly within the allotted time.
Constructs found in PRESENT are also encountered in SPONGENT~\cite{bogdanov2011spongent}, in hash function constructs based on block ciphers proposed by Hirose \cite{bogdanov2008hash,hirose2005provably,hirose2006some} (H-PRESENT) and in the derivatives Maya \cite{gomathisankaran2009maya} SMALLPRESENT \cite{leander2010small}, so the optimizations presented here can also be of interest with respect to the implementations of these ciphers. In our approach, we have implemented PRESENT for the recommended 80-bit key size in AVR assembly in two versions, optimized for maximal speed and minimal size.<commit_msg>Found another PRESENT-like cipher - but it doesn't reference the PRESENT paper<commit_after>\documentclass[11pt]{llncs2e} % change this around if you don't have lncs style installed
%\documentclass[11pt]{article}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{color}
\usepackage{tabularx}
%\usepackage{wrapfig}
\usepackage{float}
%\usepackage{fullpage}
\usepackage{hyperref}

\usepackage{graphicx}
\usepackage{url}
\usepackage{sidecap}
\usepackage{epstopdf}

\def\bibfont{\scriptsize}
\usepackage{natbib}
\setlength{\bibsep}{0.0pt}

\renewcommand\refname{References}
\renewcommand\bibname{References}

\lstset{basicstyle=\scriptsize\sffamily}
%\lstset{language=Assembler}[avr8avra] % not standard
\lstdefinestyle{customasm}{
  morekeywords={adc,adiw,asr,brtc,brcs,brhs,brne,cbr,clh,clr,clt,cp,cpi,dec,eor,ldi,lpm,lsl,nop,mov,or,rcall,ret,seh,set,subi,swap,rjmp},
  morecomment=[l][\color{blue}]{;}
}
\lstset{style=customasm}

\begin{document}
\title{Speed and Size-Optimized Implementations of the PRESENT Cipher for Tiny AVR Devices}
%\title{\textbf{PRESENT Cipher for tinyAVR Architectures}}

\author{<NAME> and <NAME>}
\institute{Radboud Universiteit Nijmegen}
%\date{}
%\conference{RFIDsec 2013, Graz, Austria}
\maketitle

\begin{abstract}
This paper presents high-speed and low-size assembly implementations of the 80-bit version of the PRESENT cipher for the AVRtiny family of microcontrollers. We report new speed and size records for our implementation, with the speed-optimized version achieving a full encryption in 8721 clock cycles and the size-optimized version compressing the cipher down to 280 bytes; the previous state of the art for AVRtiny achieved 10723 clock cycles for encryption with a size of 936 bytes. Along with the two implementation extrema (speed \& size optimized versions), we offer insight into techniques and representations that show the speed/area tradeoffs and provide intermediate solutions for various configurations.\\
\textbf{Key words}: PRESENT, AVR, ATtiny, AVR Assembly, software implementation
\end{abstract}
\section{Introduction}
Modern society is constantly witnessing an extensive and large scale deployment of tiny computing devices. Information processing and wireless communication are being thoroughly integrated into everyday objects and activities, developing a large distributed mobile infrastructure and ushering in the era of ubiquitous computing. RFID tags attached to products, cardiac pacemakers, fire-detecting sensor nodes and the like need to operate \emph{securely} under particularly \emph{restricted conditions}, namely low battery life, small processing power and bandwidth-demanding ad-hoc network protocols. To achieve sustainable security in this new landscape, researchers have developed new cryptographic primitives and techniques, namely lightweight cryptographic ciphers such as PRESENT~\cite{bogdanov2007present}, Klein~\cite{gong2012klein}, LED~\cite{guo2011led} and others.

The majority of these ciphers was designed with hardware performance in mind, leaving most software implementations relatively inefficient. For instance, the AVR-Crypto-Lib~\cite{avr_crypto_lib} often resorts to C language implementations, resulting in 100.000 clock cycles for a single encryption with PRESENT.
AVR microcontrollers are often encountered regarding the Internet of Things and ubiquitous computing, and moreover serve as a good model of a limited instruction set architecture, thus they are an interesting platform on which to enable and optimize lightweight ciphers.
The University of Leuven has initiated a project to draft efficient assembly implementations of various lightweight ciphers on resource-constrained AVR devices to make fair comparisons about their relative efficiency. The contribution by Eisenbarth~\cite{eisenbarth2012compact} achieves an encryption with PRESENT in roughly 11.000 clock cycles.

\textbf{Our contribution.} This paper describes a speed-optimized and a size-optimized implementation of the PRESENT cipher on the ATtiny45, with the aid of algorithmic improvements and efficient programming techniques. Our speed-optimized version improves the state of the art~\cite{eisenbarth2012compact} by 18\%, while the size-optimized version is 70\% smaller than the smallest known implementation~\cite{eisenbarth2012compact}.\\
Algorithmic improvement:
\begin{itemize}[nolistsep]
  \item A merged SP layer, \emph{i.e.} combining the substitution and permutation layer of the cipher in order to construct lookup tables that remove the time-consuming permutations~\cite{gong_code}. This improvement constitutes the core of the achieved speed improvement.
\end{itemize}
Programming improvements:
\begin{itemize}[nolistsep]
  \item Squared S-Box representations, \emph{i.e.} S-Boxes which are custom-made for fast access in the AVR 8-bit architecture, also used by Eisenbarth~\cite{eisenbarth2012compact}.
  \item Compact S-Box representations, \emph{i.e.} minimal footprint S-Boxes that reduce the implementation size.
  \item Minimal key register rotations, allowing the key update procedure to complete in fewer instructions.
  \item Memory access optimizations, grouping memory transactions to improve speed.
  \item Algorithm serialization, by keeping part of the state in SRAM while we operate on fewer registers.
  \item Indirect register access to let loops drive repeated operations on CPU registers.
  \item Use of the stack to store intermediate values to avoid more dedicated registers.
  \item Code restructuring and efficient procedure callings.
\end{itemize}
We note that some of the improvements are interoperable and can be combined to provide the ``golden ratio" between speed and size, depending on the external requirements.\\
\textbf{Paper organization.} The organization of the paper follows. Section 2 provides an introduction to the AVR architecture, including the capabilities and limitations of AVRtiny microcontrollers. Section 3 focuses on high-speed implementation of the PRESENT cipher, regarding efficient S-Box representations and lookup tables. Section 4 describes various techniques that produce a very compact version of the cipher. Section 5 provides the final benchmarking results and conclusions.

\section{Background}
\subsection{PRESENT Cipher}
 PRESENT~\cite{bogdanov2007present} is an ultra-lightweight, 64-bit symmetric block cipher, using 80-bit or 128-bit keys.
It is based on a substitution/permutation network and it is named as a reference to Serpent~\cite{anderson1998serpent} due to its similar constructs.
As of 2012, PRESENT (among other ciphers) was adopted by ISO as a standard for a lightweight block cipher (ISO/IEC 29192-2:2012~\cite{present_iso}). The full algorithm has so far been resistant to attempts at cryptanalysis, although the most successful attack has shown that up to 15 of its 31 rounds can be broken with $2^{35.6}$ plaintext-ciphertext pairs in $2^{20}$ operations~\cite{abed2012biclique,collard2009statistical,nakahara2009linear}.

PRESENT uses exclusive-or as its round key operation, a 4-bit substitution layer, a 4-bit period bit position permutation network in 31 rounds and a final round key operation.
Key scheduling is a combination of bit rotation, S-Box application and exclusive-or with the round counter.
%We chose PRESENT as a cipher to work on within a project to write and optimize AVR crypto code %because we deemed it extremely well-suited for a simple microcontroller, and felt it was within our %grasp to implement and optimize correctly within the allotted time.
Constructs found in PRESENT are also encountered in SPONGENT~\cite{bogdanov2011spongent}, in hash function constructs based on block ciphers proposed by Hirose \cite{bogdanov2008hash,hirose2005provably,hirose2006some} (H-PRESENT) and in the similar Maya \cite{gomathisankaran2009maya} or derivative SMALLPRESENT \cite{leander2010small}, so the optimizations presented here can also be of interest with respect to the implementations of these ciphers. In our approach, we have implemented PRESENT for the recommended 80-bit key size in AVR assembly in two versions, optimized for maximal speed and minimal size.
{'fraction_non_alphanumeric': 0.060003692534925226, 'fraction_numerical': 0.019816604098713768, 'mean_word_length': 5.810561609388097, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4142298', 'n_tokens_mistral': 4477, 'n_tokens_neox': 3955, 'n_words': 1937}