14-05.html

Applied Cryptography

<!-- LEFT NAV SEARCH END -->

		</td>
		
<!-- PUB PARTNERS END -->
<!-- END LEFT NAV -->

<td rowspan="8" align="right" valign="top"><img src="/images/iswbls.gif" width=1 height=400 alt="" border="0"></td>
<td><img src="/images/white.gif" width="5" height="1" alt="" border="0"></td>
<!-- end of ITK left NAV -->

<!-- begin main content -->
<td width="100%" valign="top" align="left">


<!-- END SUB HEADER -->

<!--Begin Content Column -->

<FONT FACE="Arial,Helvetica" SIZE="-1">
To access the contents, click the chapter and section titles.
</FONT>
<P>
<B>Applied Cryptography, Second Edition: Protocols,  Algorthms, and Source Code in C (cloth)</B>
<FONT SIZE="-1">
<BR>
<I>(Publisher: John Wiley & Sons, Inc.)</I>
<BR>
Author(s): Bruce Schneier
<BR>
ISBN: 0471128457
<BR>
Publication Date: 01/01/96
</FONT>
<P>
<form name="Search" method="GET" action="http://search.earthweb.com/search97/search_redir.cgi">

<INPUT TYPE="hidden" NAME="Action" VALUE="Search">
<INPUT TYPE="hidden" NAME="SearchPage" VALUE="http://search.earthweb.com/search97/samples/forms/srchdemo.htm">
<INPUT TYPE="hidden" NAME="Collection" VALUE="ITK">
<INPUT TYPE="hidden" NAME="ResultTemplate" VALUE="itk-full.hts">
<INPUT TYPE="hidden" NAME="ViewTemplate" VALUE="view.hts">

<font face="arial, helvetica" size=2><b>Search this book:</b></font><br>
<INPUT NAME="queryText" size=50 VALUE="">&nbsp;<input type="submit" name="submitbutton" value="Go!">
<INPUT type=hidden NAME="section_on" VALUE="on">
<INPUT type=hidden NAME="section" VALUE="http://www.itknowledge.com/reference/standard/0471128457/">

</form>


<!-- Empty Reference Subhead -->

<!--ISBN=0471128457//-->
<!--TITLE=APPLIED CRYPTOGRAPHY, SECOND EDITION: Protocols, Algorithms, and Source Code in C//-->
<!--AUTHOR=Bruce Schneier//-->
<!--PUBLISHER=Wiley Computer Publishing//-->
<!--CHAPTER=14//-->
<!--PAGES=340-342//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="14-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="14-06.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>These are operations in the finite field GF(257), and 45 is a primitive element in that field. In practical implementations of SAFER K-64, it is quicker to implement this in a lookup table than to calculate new results all the time.
</P>
<P>Then, sub-blocks are either XORed or added with bytes of subkey <I>K</I><SUB>2r</SUB>. The results of this operation are fed through three layers of linear operations designed to increase the avalanche effect. Each operation is called a Pseudo-Hadamard Transform (PHT). If the inputs to a PHT are <I>a</I><SUB>1</SUB> and <I>a</I><SUB>2</SUB>, then the outputs are:</P>
<DL>
<DD><I>b</I><SUB>1</SUB> = (2<I>a</I><SUB>1</SUB> &#43; <I>a</I><SUB>2</SUB>) mod 256
<DD><I>b</I><SUB>2</SUB> = (<I>a</I><SUB>1</SUB> &#43; <I>a</I><SUB>2</SUB>) mod 256
</DL>
<P>After <I>r</I> rounds, there is a final output transformation. This is the same as the first step of each round. <I>B</I><SUB>1</SUB>, <I>B</I><SUB>4</SUB>, <I>B</I><SUB>5</SUB>, and <I>B</I><SUB>8</SUB> are XORed with the corresponding bytes of the last subkey, and <I>B</I><SUB>2</SUB>, <I>B</I><SUB>3</SUB>, <I>B</I><SUB>6</SUB>, and <I>B</I><SUB>7</SUB> are added to the corresponding bytes of the last subkey. The result is the ciphertext.</P>
<I><P><A NAME="Fig4"></A><A HREF="javascript:displayWindow('images/14-04.jpg',351,319 )"><IMG SRC="images/14-04t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/14-04.jpg',351,319)"><FONT COLOR="#000077"><B>Figure 14.4</B></FONT></A>&nbsp;&nbsp;One round of SAFER.</I>
</P>
<P>Decryption is the reverse process: the output transformation (with subtraction instead of addition), then <I>r</I> reverse rounds. The Inverse PHT (IPHT) is:</P>
<DL>
<DD><I>a</I><SUB>1</SUB> = (<I>b</I><SUB>1</SUB> &#150; <I>b</I><SUB>2</SUB>) mod 256
<DD><I>a</I><SUB>2</SUB> = (&#150;<I>b</I><SUB>1</SUB> &#43; 2<I>b</I><SUB>2</SUB>) mod 256
</DL>
<P>Massey recommends 6 rounds, but you can increase that if you want greater security.
</P>
<P>Generating subkeys is easy. The first subkey, <I>K</I><SUB>1</SUB>, is simply the user key. Subsequent subkeys are generated by the following procedure:</P>
<DL>
<DD><I>K</I><SUB>i&#43;1</SUB> = (<I>K</I><SUB>1</SUB> &lt&lt&lt 3<I>i</I>) &#43; <I>c</I><SUB>i</SUB>
</DL>
<P>The symbol &#147;&lt&lt&lt&#148; is a left circular shift or a left rotation. The rotation is byte by byte, and <I>c</I><SUB>i</SUB> is a round constant. If <I>c</I><SUB>ij</SUB> is the <I>j</I>th byte of the <I>i</I>th round constant, then you can calculate all of the round constants by the formula</P>
<DL>
<DD><I>c</I><SUB>ij</SUB> = 45<SUP>45^((9<I>i &#43; j</I>) mod 256) mod 257</SUP> mod 257
</DL>
<P>Generally, these values are stored in a table.
</P>
<P><FONT SIZE="+1"><B><I>SAFER K-128</I></B></FONT></P>
<P>This alternate key schedule was developed by the Ministry of Home Affairs in Singapore, and then incorporated into SAFER by Massey [1010]. It uses two keys, <I>K</I><SUB>a</SUB> and <I>K</I><SUB>b</SUB>, each 64-bits long. The trick is to generate two subkey sequences in parallel, and then alternate subkeys from each sequence. This means that if you choose <I>K</I><SUB>a</SUB> = <I>K</I><SUB>b</SUB>, then the 128-bit key is compatible with the 64-bit key <I>K</I><SUB>a</SUB>.</P>
<P><FONT SIZE="+1"><B><I>Security of SAFER K-64</I></B></FONT></P>
<P>Massey showed that SAFER K-64 is immune to differential cryptanalysis after 8 rounds and is adequately secure against the attack after 6 rounds. After only 3 rounds linear cryptanalysis is ineffective against this algorithm [1010].
</P>
<P>Knudsen found a weakness in the key schedule: For virtually every key, there exists at least one (and sometimes as many as nine) other key that encrypts some different plaintext to identical ciphertexts [862]. The number of different plaintexts that encrypt to identical ciphertexts after 6 rounds is anywhere from 2<SUP>22</SUP> to 2<SUP>28</SUP>. While this attack may not impact SAFER&#146;s security when used as an encryption algorithm, it greatly reduces its security when used as a one-way hash function. In any case, Knudsen recommends at least 8 rounds.</P>
<P>SAFER was designed for Cylink, and Cylink is tainted by the NSA [80]. I recommend years of intense cryptanalysis before using SAFER in any form.</P>
<H3><A NAME="Heading6"></A><FONT COLOR="#000077">14.5 3-Way</FONT></H3>
<P>3-Way is a block cipher designed by Joan Daemen [402,410]. It has a 96-bit block length and key length, and is designed to be very efficient in hardware.
</P>
<P>3-Way is not a Feistel network, but it is an iterated block cipher. 3-Way can have <I>n</I> rounds; Daemen recommends 11.</P>
<P><FONT SIZE="+1"><B><I>Description of 3-Way</I></B></FONT></P>
<P>The algorithm is simple to describe. To encrypt a plaintext block, <I>x:</I></P>
<DL>
<DD>For <I>i</I> = 0 to <I>n</I> &#150; 1
<DL>
<DD><I>x</I> = <I>x</I> XOR <I>K</I><SUB>i</SUB>
<DD><I>x</I> = theta (<I>x</I>)
<DD><I>x</I> = pi &#150; 1 (<I>x</I>)
<DD><I>x</I> = gamma (<I>x</I>)
<DD><I>x</I> = pi &#150; 2 (x)
</DL>
<DD><I>x</I> = <I>x</I> &#8853; <I>K</I><SUB>n</SUB>
<DD><I>x</I> = theta (<I>x</I>)
</DL>
<P>The functions are:
</P>
<DL>
<DD><B>&#151;</B>&nbsp;&nbsp;theta(<I>x</I>) is a linear substitution function&#151;basically a bunch of circular shifts and XORs.
<DD><B>&#151;</B>&nbsp;&nbsp;pi&#150;1(<I>x</I>) and pi&#150;2(<I>x</I>) are simple permutations.
<DD><B>&#151;</B>&nbsp;&nbsp;gamma(<I>x</I>) is a nonlinear substitution function. This is the step that gives 3-Way its name; it is the parallel execution of the substitution step on 3-bit blocks of the input.
</DL>
<P>Decryption is similar to encryption, except that the bits of the input have to be reversed and the bits of the output have to be reversed. Code to implement 3-Way can be found in the back of this book.
</P>
<P>So far, there has been no successful cryptanalysis of 3-Way. The algorithm is unpatented.</P>
<H3><A NAME="Heading7"></A><FONT COLOR="#000077">14.6 Crab</FONT></H3>
<P>This algorithm was developed by Burt Kaliski and Matt Robshaw of RSA Laboratories [810]. The idea behind Crab is to use techniques from one-way hash functions to make a fast encryption algorithm. Hence, Crab is very similar to MD5, and this section assumes you are familiar with Section 18.5.
</P>
<P>Crab has a very large block: 1024 bytes. Since Crab is presented more as a research contribution than a real algorithm, no definitive key-generation routines are presented. The authors suggest a method that could turn an 80-bit key into three requisite subkeys, although the algorithm could easily accept variable-length keys.</P>
<P>Crab uses two sets of large subkeys:</P>
<DL>
<DD><I>A permutation of the numbers 0 through 255: P<SUB>0</SUB>, P<SUB>1</SUB>, P<SUB>2</SUB>,..., P<SUB>255</SUB>.</I>
<DD><I>A 2048-entry array of 32-bit numbers: S<SUB>0</SUB>, S<SUB>1</SUB>, S<SUB>2</SUB>,..., S<SUB>2047</SUB>.</I>
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="14-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="14-06.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>

[an error occurred while processing this directive]
<!-- all of the reference materials (books) have the footer and subfoot reveresed -->
<!-- reference_subfoot = footer -->
<!-- reference_footer = subfoot -->

<!-- BEGIN SUB FOOTER -->
		<br><br>
		</TD>
    </TR>
	</TABLE>

		
	<table width="640" border=0 cellpadding=0 cellspacing=0>
		<tr>
		<td align="left" width=135><img src="/images/white.gif" width=100 height="1" alt="" border="0"></td>
		
		
<!-- END SUB FOOTER -->

<!-- all of the books have the footer and subfoot reveresed -->
<!-- reference_subfoot = footer -->
<!-- reference_footer = subfoot -->

<!-- FOOTER -->
			
		<td width="515" align="left" bgcolor="#FFFFFF">
<font face="arial, helvetica" size="1"><b><a href="/products.html"><font color="#006666">Products</font></a>&nbsp;|&nbsp; <a href="/contactus.html"><font color="#006666">Contact Us</font></a>&nbsp;|&nbsp; <a href="/aboutus.html"><font color="#006666">About Us</font></a>&nbsp;|&nbsp; <a href="http://www.earthweb.com/corporate/privacy.html" target="_blank"><font color="#006666">Privacy</font></a> &nbsp;|&nbsp; <a href="http://www.itmarketer.com/" target="_blank"><font color="#006666">Ad Info</font></a> &nbsp;|&nbsp; <a href="/"><font color="#006666">Home</font></a></b>
		<br><br>
		
		Use of this site is subject to certain <a href="/agreement.html">Terms &amp; Conditions</a>, <a href="/copyright.html">Copyright &copy; 1996-1999 EarthWeb Inc.</a><br> 
All rights reserved.  Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.</font><p>
</td>
		</tr>
</table>
</BODY>
</HTML>

<!-- END FOOTER -->