cryptomethods.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

% $Id: cryptomethods.tex 1205 2005-07-04 13:58:13Z koy $
% ..............................................................................
%                V E R S C H L U E S S E L U N G S V E R F A H R E N
%
% Schreibregelung: Capitel header with all nouns/verbs-words capitalized,
%                  All other headers in the normal lower/upper case manner
%                  like sentences without dot at the end.
%
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\newpage
\section{Encryption Procedures}
\hypertarget{Kapitel_1}{}
(Bernhard Esslinger, May 1999, Updates Dec. 2001, Feb. 2003, June 2005)


This chapter introduces the topic in a more descriptive way without using too much mathematics.


% --------------------------------------------------------------------------
% \subsection{Encryption}

The purpose of encryption \index{Encryption} is to change data in such a way
that only an authorised recipient is able to reconstruct the plaintext. This
allows us to transmit data without worrying about it getting into unauthorised
hands. Authorised recipients possess a piece of secret information -- called the
key -- which allows them to decrypt the data while it remains hidden from
everyone else.\par \vskip + 3pt

One encryption procedure has been mathematically proved to be secure, the {\em
One Time Pad}\index{One Time Pad}. However, this procedure has several
practical disadvantages (the key used must be randomly selected and must be at
least as long as the message being protected), which means that it is hardly
used except in closed environments such as for the hot wire between Moscow and
Washington.\par \vskip + 3pt

For all other procedures there is a (theoretical) possibility of breaking them.
If the procedures are good, however, the time taken to break them is so long
that it is practically impossible to do so, and these procedures can therefore be
considered (practically) secure.\par \vskip + 3pt

The book of Bruce Schneier \cite{Schneier1996cm} offers a very good overview of
the different algorithms. We basically distinguish between symmetric and
asymmetric encryption procedures.

% --------------------------------------------------------------------------
\subsection[Symmetric encryption]
{Symmetric encryption\footnotemark}
  \footnotetext{%
    With CrypTool\index{CrypTool} you can execute the following modern
    symmetric encryption algorithms 
    (using the menu path {\bf Crypt \textbackslash{} Symmetric (modern)}): \\
    IDEA, RC2, RC4, DES (ECB), DES (CBC), Triple-DES (ECB), Triple-DES (CBC),
    MARS (AES candidate), RC6 (AES candidate), Serpent (AES candidate), 
    Twofish (AES candidate), Rijndael (official AES algorithm).
  }

For {\em symmetric} encryption \index{Encryption!symmetric} sender and
recipient must be in possession of a common (secret) key which they have
exchanged before actually starting to communicate. The sender uses this
key to encrypt the message and the recipient uses it to decrypt it.
\par \vskip + 3pt

All classical methods are of this type. Examples can be found within the 
program CrypTool, in chapter  \ref{Kapitel_PaperandPencil} 
(Paper and Pencil Encryption Methods) of this script or in \cite{Nichols1996}. 
Now we want to consider more modern mechanisms.

The advantages of symmetric algorithms are the high speed with which data can be
encrypted and decrypted. One disadvantage is the need for key management. In
order to communicate with one another confidentially, sender and recipient must
have exchanged a key using a secure channel before actually starting to
communicate. Spontaneous communication between individuals who have never met
therefore seems virtually impossible. If everyone wants to communicate with
everyone else spontaneously at any time in a network of $ n $ subscribers, each
subscriber must have previously exchanged a key with each of the other $n - 1$
subscribers. A total of $n(n - 1)/2$ keys must therefore be exchanged.\par \vskip + 3pt

The most well-known symmetric encryption procedure is the \index{DES} DES-algorithm. The DES-algorithm has been developed by IBM in collaboration with the
National Security Agency \index{NSA} (NSA), and was published as a standard in
1975. Despite the fact that the procedure is relatively old, no effective attack
on it has yet been detected. The most effective way of attacking consists of
testing (almost) all possible keys until the right one is found ({\em brute-force-attack}).
\index{Attack!brute-force} Due to the relatively short key length of
effectively 56 bits (64 bits, which however include 8 parity bits), numerous
messages encrypted using DES have in the past been broken. Therefore, the
procedure can now only be considered to be conditionally secure. Symmetric
alternatives to the DES procedure include the IDEA \index{IDEA} or Triple DES
algorithms.\par \vskip + 3pt

Up-to-the-minute procedure is the symmetric AES standard. The associated
Rijndael algorithm was declared winner of the AES award on October 2nd, 2000
and thus succeedes the DES procedure.

More details about the AES algorithms and the AES candidates of the last round
can be found within the online help of CrypTool\index{CrypTool}%
\footnote{%
      CrypTool online help\index{CrypTool}: the index head-word {\bf AES}
      leads to the 3 help pages: {\bf AES candidates}, 
      {\bf The AES winner Rijndael} and 
      {\bf The Rijndael encryption algorithm}.
  }.


% --------------------------------------------------------------------------
\subsubsection{New results about cryptanalysis of AES}
\index{Cryptanalysis} \label{NeueAES-Analyse}

Below you will find some results, which have recently called into question the security of the AES algorithm -- from our point of view these doubts practically still remain unfounded
% = do not bring disrepute upon AES
. 
The following information is based on the original papers and the articles \cite{Wobst-iX2002} and \cite{Lucks-DuD2002}.

AES with a minimum key length of 128 bit is still in the long run sufficiently secure against brute-force attacks\index{Attack!brute-force} -- as long as the quantum computers aren't powerful enough. When announced as new standard AES was immune against all known crypto attacks, mostly based on statistical considerations and earlier applied to DES: using pairs of clear and cipher texts expressions are constructed, which are not completely at random, so they allow conclusions to the used keys. These attacks required unrealistically large amounts of intercepted data.

Cryptanalysts already label methods as ``academic success'' or as ``cryptanalytic attack'' if they are theoretically faster than the complete testing of all keys (brute force analysis). In the case of AES with the maximal key length (256 bit) exhaustive key search on average needs $2^{255}$ encryption operations. A cryptanalytic attack needs to be better than this. At present between $2^{75}$ and $2^{90}$ encryption operations are estimated to be performable only just for organizations, for example a security agency.

In their 2001-paper Ferguson, Schroeppel and Whiting \cite{Ferguson2001}
presented a new method of symmetric codes cryptanalysis: They described AES with
a closed formula (in the form of a continued fraction) which was possible
because of the "relatively" clear structure of AES. This formula consists of
around 1000 trillion terms of a sum - so it does not help concrete practical
cryptanalysis. Nevertheless curiosity in the academic community was awakened.
It was already known, that the 128-bit AES could be described as an
over-determined system of about 8000 quadratic equations (over an algebraic
number field) with about 1600 variables (some of them are the bits of the wanted
key) -- equation systems of that size are in practice not solvable. This special
equation system is relatively sparse, so only very few of the quadratic terms
(there are about 1,280,000 are possible quadratic terms in total) appear in the
equation system.

The mathematicians Courtois and Pieprzyk \cite{Courtois2002} published a paper
in 2002, which got a great deal of attention amongst the crypto community: The
pair had further developed the XL-method (eXtended Linearization), introduced at
Eurocrypt 2000 by Shamir et al., to create the so called XSL-method (eXtended
Sparse Linearization). The XL-method is a heuristic technique, which in some
cases manages to solve big non-linear equation systems and which was till then
used to analyze an asymmetric algorithm (HFE).  The innovation of Courtois and
Pieprzyk was, to apply the XL-method on symmetric codes: the XSL-method can be
applied to very specific equation systems. A 256-bit AES could be attacked in
roughly $2^{230}$ steps. This is still a purely academic attack, but also a
direction pointer for a complete class of block ciphers. The major problem with
this attack is that until now nobody has worked out, under what conditions it is
successful: the authors specify in their paper necessary conditions, but it is
not known, which conditions are sufficient.  There are two very new aspects of
this attack: firstly this attack is not based on statistics but on algebra. So
attacks seem to be possible, where only very small amounts of cipher text are
available. Secondly the security of a product algorithm\index{Cascade cipher}%
\footnote{%
A cipher text can be used as input for another encryption algorithm. 
A cascade cipher is build up as a composition of different encryption 
transformations. The overall cipher is called product algorithm or cascade cipher (sometimes depending whether the used keys are statistically dependent or not).\\
Cascading does not always improve the security.\\
This process is also used {\em within} modern algorithms:
They usually combine simple and, considered at its own, cryptologically
relatively unsecure single steps in several rounds into an efficient 
overall procedure.  Most block ciphers (e.g. DES, IDEA) are cascade ciphers.\\
Also serial usage of the same cipher with different keys (like with Triple-DES)
is called cascade cipher. 
}
does not exponentially increase with the number of rounds.

Currently there is a large amount of research in this area: for example Murphy and Robshaw presented a paper at Crypto 2002 \cite{Robshaw2002a}, which could dramatically improve cryptanalysis: the burden for a 128-bit key was estimated at about $2^{100}$ steps by describing AES as a special case of an algorithm called BES (Big Encryption System), which has an especially "round" structure. But even $2^{100}$ steps are beyond what is achievable in the foreseeable future. Using a 256 bit key the authors estimate that a XSL-attack will require $2^{200}$ operations.

More details can be found at:
\vspace{-10pt}
\begin{itemize}
  \item[] \href{http://www.cryptosystem.net/aes}
               {\texttt{http://www.cryptosystem.net/aes}}\\
          \href{http://www.minrank.org/aes/}
               {\texttt{http://www.minrank.org/aes/}}
\end{itemize}

So for 256-AES the attack is much more effective than brute-force\index{Attack!brute-force} but still far more away from any computing power which could be accessible in the short-to-long term. 

The discussion is very controversial at the moment: Don Coppersmith (one of the
inventors of DES) for example queries the practicability of the attack because
XLS would provide no solution for AES \cite{Coppersmith2002}. This implies that
then the optimization of Murphy and Robshaw \cite{Robshaw2002b} would not work.


% --------------------------------------------------------------------------
\subsubsection{Current status of brute-force attacks on 
symmetric algorithms (RC5)}
\index{Attack!brute-force}
\index{RC5}
\label{Brute-force-gegen-Symmetr}

The current status of brute-force attacks on symmetric encryption algorithms can be explained with the block cipher RC5.

Brute-force (exhaustive search, trial-and-error) means to completely examine all keys of the key space: so no special analysis methods have to be used. Instead, the cipher text is decrypted with all possible keys and for each resulting text it is checked, whether this is a meaningful clear text. A key length of 64 bit means at most $2^{64}$ = 18,446,744,073,709,551,616 or about 18 trillion (GB) / 18 quintillion (US)  keys to check\index{CrypTool}%
\footnote{%
    With CrypTool\index{CrypTool} you can also try brute-force attacks
    of modern symmetric algorithms (using the menu path
    {\bf Analysis \textbackslash{} Symmetric Encryption (modern)}): here
    the weakest knowledge of an attacker is assumed, he performs a 
    ciphertext-only attack.
    To achieve a result in an appropriate time with a single PC you should 
    mark not more than 20 bit of the key as unknown.
}.

Companies like RSA Security provide so-called cipher challenges in order to quantify the security offered by well-known symmetric ciphers as DES, Triple-DES or RC5\footnote{\href{http://www.rsasecurity.com/rsalabs/challenges/secretkey/index.html}{\tt http://www.rsasecurity.com/rsalabs/challenges/secretkey/index.html}}. They offer prizes for those who manage to decipher cipher texts, encrypted with different algorithms and different key lengths, and to unveil the symmetric key (under controlled conditions). So theoretical estimates can be confirmed.

It is well-known, that the ``old'' standard algorithm DES with a fixed key length of 56 bit is no more secure: this was demonstrated already in January 1999 by the Electronic Frontier Foundation (EFF). With their specialized computer Deep Crack they cracked a DES encrypted message within less than a day\footnote{\href{http://www.rsasecurity.com/rsalabs/challenges/des3/index.html}{\tt http://www.rsasecurity.com/rsalabs/challenges/des3/index.html}}.

The current record for strong symmetric algorithms unveiled a key 64 bit long. The algorithm used was RC5, a block cipher with variable key size. 

The RC5-64 challenge has been solved by the distributed.net team after 5 years\footnote{\href{http://distributed.net/pressroom/news-20020926.html}{\tt http://distributed.net/pressroom/news-20020926.html}}.  In total 331,252 individuals co-operated over the internet to find the key. More than 15 trillion (GB) / 15 quintillion (US)  keys were checked, until they found the right key.

This makes clear, that symmetric algorithms (even if they have no cryptographical weakness) using keys of size 64 bit are no more appropriate to keep sensible data private.

Similar cipher challenges are there for asymmetric algorithms (please see chapter \ref{NoteFactorisation}).




% --------------------------------------------------------------------------
\subsection[Asymmetric encryption]
{Asymmetric encryption\footnotemark}
  \footnotetext{%
    With CrypTool\index{CrypTool} you can execute RSA encryption
    and decryption (using the menu path {\bf Crypt \textbackslash{} Asymmetric}).
    In both cases you must select a RSA key pair. Only in the case of decryption
    the secret RSA key is necessary: so here you are asked to enter the PIN. 
  }

In the case of {\em asymmetric} encryption \index{Encryption!asymmetric} each