digitalsignatures.tex

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

% $Id: digitalsignatures.tex 1205 2005-07-04 13:58:13Z koy $
% ...........................................................................
%                  D I G I T A L E  S I G N A T U R E N
% ...........................................................................

\newpage
% --------------------------------------------------------------------------
\section{Hash Functions and Digital Signatures}
\hypertarget{Chapter_Hashes-and-Digital-Signatures}{}
\index{Signature!digital}
(Schneider J. / Esslinger B. / Koy H., June 2002,
Update: Feb. 2003, June 2005)

\vspace{12pt}
The aim of digital signatures is to guarantee the following two points:
\begin{itemize}
 \item User authenticity: \index{Authenticity!user} \\
      It can be checked whether a message really does
come from a particular person.
 \item Message integrity:  \index{Message integrity} \\
      It can be checked whether the message has been
changed (on route).
\end{itemize}


An asymmetric technique is used again (see encryption procedures). Participants
who wish to generate a digital signature for a document must possess a pair of
keys. They use their secret key to generate signatures and the recipient uses
the sender's public key to verify whether the signature is correct. As before,
it must be impossible to use the public key to derive the secret key\footnote{%
With CrypTool\index{CrypTool} you can also generate and check 
digital signatures: \\
using the submenus of the main menu {\bf Digital Signatures / PKI} or \\
using menu {\bf Indiv. Procedures \textbackslash{} RSA Cryptosystem 
\textbackslash{} Signature Demonstration (Signature Generation)}.
}.


In detail, a \index{Signature procedure} {\em Signature procedure} looks like
this: \\ Senders use their message and secret key to calculate the digital
signature for the message. Compared to hand-written signatures, digital
signatures therefore have the advantage that they also depend on the document to
be signed. Signatures from one and the same participant are different unless the
signed documents are completely identical. Even inserting a blank in the text
would lead to a different signature. The recipient of the message would
therefore detect any injury to the message integrity as this would mean that the
signature no longer matches the document and is shown to be incorrect when
verified.

The document is sent to the recipient together with the signature. The recipient
can then use the sender's public key, the document and the signature to
establish whether or not the signature is correct. Because a signature is about
as long as the straight datastream to be signed, the procedure we just described
has in practice, however, a decisive disadvantage. The signature is
approximately as long as the document itself. To prevent an unnecessary increase
in data traffic, and also for reasons of performance\index{Performance}, we apply
a cryptographic hash function\footnote{%
Hash functions\index{Hash function} are implemented within 
CrypTool\index{CrypTool} at several places.\\
Using menus {\bf Individual Procedures \textbackslash{} Hash} and
            {\bf Analysis \textbackslash{} Hash}
you have the possibilities
% hier die items nicht einr點ken!
\begin{list}{\textbullet}{\leftmargin10pt\addtolength{\itemsep}{-1.0\baselineskip}}
%\begin{itemize}\addtolength{\itemsep}{-1.0\baselineskip} % um den Abstand zu verringern bebe
\item to apply one of 6 hash functions to the content of the current window, \\
\item to calculate the hash value of a file, \\
\item to test, how changes to a text change the according hash value,\\
\item to calculate a key from a password according to the PKCS\#5 
      standard\index{PKCS\#5}, \\
\item to calculate HMACs from a text and a secret key, and\\
\item to perform a simulation, how digital signatures could be attacked 
      by a targeted search for hash value collisions\index{Collision}.
\end{list}
} to the document -- before signing. The output of the hash function will 
then be signed.


% --------------------------------------------------------------------------
\vskip + 15pt
\subsection{Hash functions}
\hypertarget{Hash-functions-ht}{}
\index{Hash function}
A {\em hash function}\footnote{%
Hash algorithms compute a condensed representation of electronic data (message).
When a message is input to a hash algorithm, the result is an output called
a message digest. The message digests typically range in length 
from 128 to 512 bits, depending on the algorithm. 
Secure hash algorithms are typically used with
other cryptographic algorithms, such as digital signature algorithms and
keyed-hash message authentication codes, or in the generation of random
numbers (bits).
}
maps a message of any length to a string of characters with a constant size,
the \index{Hash value} hash value. 



% --------------------------------------------------------------------------
\vskip + 15pt
\subsubsection{Requirements for hash functions}

Cryptographically secure hash functions fulfill the following requirements:
\begin{itemize}
 \item Resistance against 1st Pre-Image attacks:
      \index{Pre-Image-Attack!1st}  \\
      It should be practically impossible, for a given number, to find a message
      that has precisely this number as hash value. \\
      Given (fix): hash value H', \\
      Searched: message m, so that: H(m) = H'.
 \item Resistance against 2nd Pre-Image attacks:
      \index{Pre-Image-Attack!2nd}  \\
      It should be practically impossible, for a given message, to find another
      message, which has precisely the same hash value. \\
      Given (fix): message m1 [and so the hash value H1 = H(m1)], \\
      Searched: message m2, so that: H(m2) = H1.
 \item Collision resistance:
      \index{Collision resistance}  \\
      It should be practically impossible to find any two messages with the
      same hash value (it doesn't matter what hash value). \\
      Searched: 2 messages m1 and m2, so that: H(m1) = H(m2).
\end{itemize}



% --------------------------------------------------------------------------
\vskip + 15pt
\subsubsection{Current attacks against hash functions like SHA-1}
\label{collision-attacks-against-sha-1}

So far, no formal proof has been found that perfectly secure cryptographic
hash functions exist. 

During the past several years no new attacks against hash algorithms
came up, and so the candidates that had not yet shown any weaknesses
in their structure in practice 
(e.g. \index{SHA-1} SHA--1\footnote{%
  SHA-1 \index{SHA-1} is a 160 bit hash function specified in FIPS 180-1
  (by NIST), ANSI X9.30 Part 2 and \cite{FIPS186}.\\
  SHA means Secure Hash Algorithm, and is widely used, 
  e.g. with DSA, RSA or ECDSA.\\
  The current standard \cite{FIPS180-2} defines four secure hash algorithms
  -- SHA-1, SHA-256, SHA-384, and SHA-512.
  For these hash algorithms there are also validation tests defined in the
  test suite FIPS 140-2.

  The output length of the SHA algorithms was enhanced because of the
  possibility of birthday attacks\index{Attack!birthday}\index{Collision}:
  these make n-bit AES and a 2n-bit hash roughly equivalent: \\
  - 128-bit AES -- SHA-256 \\
  - 192-bit AES -- SHA-384 \\
  - 256-bit AES -- SHA-512.

  With CrypTool\index{CrypTool} you can comprehend the birthday attack
  \index{Attack!birthday} on digital signatures: \\
  using the menu {\bf Analysis \textbackslash{} Hash \textbackslash{} 
  Attack on the Hash Value of the Digital Signature}.
  }  
or \index{RIPEMD-160} RIPEMD-160\footnote{%
  RIPEMD-160, RIPEMD-128 and the optional extension RIPEMD-256 have object
  identifiers defined by the ISO-identified organization TeleTrusT, both 
  as hash algorithm and in combination with RSA.
  RIPEMD-160 is also part of the ISO/IEC international standard 
  ISO/IEC 10118-3:1998 on dedicated hash functions, together with 
  RIPEMD-128 and SHA-1. 

  Further details: \\
  http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html \\
  http://www.ietf.org/rfc/rfc2857.txt (``The Use of HMAC-RIPEMD-160-96
  within ESP and AH'').
  }%
) were trusted.


At Crypto 2004 (August 2004)\footnote{%
    \href{http://www.iacr.org/conferences/crypto2004/}
 {\texttt{http://www.iacr.org/conferences/crypto2004/}} }
this safety-feeling was disputed: 
Chinese researchers published collision attacks against MD4, SHA-0 and
parts of SHA-1. This globally caused new motivation to engage in
new hash attack methods.

Right now the details of the results of the Chinese cryptographers are
only announced, but not revealed completely: They stated that collision
attacks on SHA-1 can be found with a work load of $2^{69}$.
This would mean that SHA-1 has cryptographic weaknesses, 
because the design of SHA-1 should ensure a work load for collision search
of about $2^{80}$.
The value of $2^{69}$ is currently a prognosis based on theoretic forecasts. 
The security of already created digital signatures is not affected by the
described attacks. 


% be_2005_UPDATEN_if-hash-attacks-make-progress
According to our current knowledge there is no need to run scared.
But in the future digital signatures should use longer hash values and/or
other hash algorithms.

Already before Crypto 2004 NIST announced, to discontinue SHA-1 
in the next few years. So it is recommended not to use SHA-1 for
new products generating digital signatures.

Further information about this topic can be found in the article
``Hash cracked -- The consequences of the successful attacks on SHA-1''
by Reinhard Wobst and J\"urgen Schmidt\footnote{% 
      \href{http://www.heise.de/security/artikel/56634}
   {\texttt{http://www.heise.de/security/artikel/56634}}. \\
  Further references are e.g.: \\
      \href{http://www.bsi.bund.de/esig/basics/techbas/krypto/index.htm}
   {\texttt{http://www.bsi.bund.de/esig/basics/techbas/krypto/index.htm}} \\
      \href{http://csrc.nist.gov/CryptoToolkit/tkhash.html}
   {\texttt{http://csrc.nist.gov/CryptoToolkit/tkhash.html}}.
} 
  by Heise Security.




% --------------------------------------------------------------------------
\vskip + 15pt
\subsubsection{Signing with hash functions}
The hash function procedure is as follows:\\ Rather than signing the actual
document, the sender now first calculates the hash value of the message and
signs this. The recipient also calculates the hash value of the message (the
algorithm used must be known), then verifies whether the signature sent with the
message is a correct signature of the hash value. If this is the case, the
signature is verified to be correct. This means that the message is authentic,
because we have assumed that knowledge of the public key does not enable you to
derive the secret key. However, you would need this secret key to sign messages
in another name.

Some digital signature schemes are based on asymmetric \emph{encryption}
procedures, the most prominent example being the RSA system, which can be
used for signing by performing the private key operation on the hash value
of the document to be signed.

Other digital signature schemes where developed exclusively for this
purpose, as the DSA (Digital Signature Algorithm), and are not directly