14-07.html

Applied Cryptography

			<option value="/reference/dir.intranetandextranetdevelopment1.html">Intranet Dev
			<option value="/reference/dir.middleware.html">Middleware
			<option value="/reference/dir.multimediaandgraphicdesign1.html">Multimedia
			<option value="/reference/dir.networkservices1.html">Networks 
			<option value="/reference/dir.operatingsystems.html">OS
			<option value="/reference/dir.productivityapplications1.html">Prod Apps
			<option value="/reference/dir.programminglanguages.html">Programming
			<option value="/reference/dir.security1.html">Security	
			<!-- <option value="/reference/dir.ewtraining1.html">Training Guides -->
			<option value="/reference/dir.userinterfaces.html">UI
			<option value="/reference/dir.webservices.html">Web Services
			<option value="/reference/dir.webmasterskills1.html">Webmaster
			<option value="/reference/dir.y2k1.html">Y2K
			<option value="">-----------
			<option value="/reference/whatsnew.html">New Titles
			<option value="">-----------
			<option value="/reference/dir.archive1.html">Free Archive		
			</SELECT>
			</font></td>
	</tr>
	</table>
	</form>
<!-- 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=345-347//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="14-06.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="14-08.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>RC5 is actually a family of algorithms. We just defined RC5 with a 32-bit word size and 64-bit block; there&#146;s no reason why the same algorithm can&#146;t have a 64-bit word size and 128-bit block size. For <I>w</I> = 64, P and Q are 0xb7e151628aed2a6b and 0x9e3779b97f4a7c15, respectively. Rivest designates particular implementations of RC5 as RC5-<I>w/r/b</I>, where <I>w</I> is the word size, <I>r</I> is the number of rounds, and <I>b</I> is the length of the key in bytes.</P>
<P>RC5 is new, but RSA Laboratories has spent considerable time analyzing it with a 64-bit block. After 5 rounds, the statistics look very good. After 8 rounds, every plaintext bit affects at least one rotation. There is a differential attack that requires 2<SUP>24</SUP> chosen plaintexts for 5 rounds, 2<SUP>45</SUP> for 10 rounds, 2<SUP>53</SUP> for 12 rounds, and 2<SUP>68</SUP> for 15 rounds. Of course, there are only 2<SUP>64</SUP> possible chosen plaintexts, so this attack won&#146;t work for 15 or more rounds. Linear cryptanalysis estimates indicate that it is secure after 6 rounds. Rivest recommends at least 12 rounds, and possibly 16 [1325]. This number may change.</P>
<P>RSADSI is in the process of patenting RC5, and the name is trademarked. The company claims that license fees will be very small, but you&#146;d better check with them.</P>
<H3><A NAME="Heading10"></A><FONT COLOR="#000077">14.9 Other Block Algorithms</FONT></H3>
<P>There is an algorithm called CRYPTO-MECCANO in the literature [301]; it is insecure. Four Japanese cryptographers presented an algorithm based on chaotic maps at Eurocrypt &#146;91 [687, 688]; Biham cryptanalyzed the algorithm at the same conference [157]. Another algorithm relies on subsets of a particular set of random codes [693]. There are several algorithms based on the theory of error-correcting codes: a variant of the McEliece algorithm (see Section 19.7) [786,1290], the Rao-Nam algorithm [1292,733,1504,1291,1056,1057,1058,1293], variants of the Rao-Nam algorithm [464,749,1503], and the Li-Wang algorithm [964,1561]&#151;they are all insecure. CALC is insecure [1109]. An algorithm called TEA, for Tiny Encryption Algorithm, is too new to comment on [1592]. Vino is another algorithm [503]. MacGuffin, a block algorithm by Matt Blaze and me, is also insecure [189]; it was broken at the same conference it was proposed. BaseKing, similar in design philosophy as 3-way but with a 192-bit block [402], is too new to comment on.
</P>
<P>There are many more block algorithms outside the cryptology community. Some are used by various government and military organizations. I have no information about any of those. There are also dozens of proprietary commercial algorithms. Some might be good; most are probably not. If companies do not feel that their interests are served by making their algorithms public, it is best to assume they&#146;re right and avoid the algorithm.</P>
<H3><A NAME="Heading11"></A><FONT COLOR="#000077">14.10 Theory of Block Cipher Design</FONT></H3>
<P>In Section 11.1, I described Shannon&#146;s principles of confusion and diffusion. Fifty years after these principles were first written, they remain the cornerstone of good block cipher design.
</P>
<P>Confusion serves to hide any relationship between the plaintext, the ciphertext, and the key. Remember how linear and differential cryptanalysis can exploit even a slight relationship between these three things? Good confusion makes the relationship statistics so complicated that even these powerful cryptanalytic tools won&#146;t work.</P>
<P>Diffusion spreads the influence of individual plaintext or key bits over as much of the ciphertext as possible. This also hides statistical relationships and makes cryptanalysis more difficult.</P>
<P>Confusion alone is enough for security. An algorithm consisting of a single key-dependent lookup table of 64 bits of plaintext to 64 bits of ciphertext would be plenty strong. The problem is that large lookup tables require lots of memory to implement: 10<SUP>20</SUP> bytes of memory for the table just mentioned. The whole point of block cipher design is to create something that looks like a large lookup table, but with much smaller memory requirements.</P>
<P>The trick is to repeatedly mix confusion (with much smaller tables) and diffusion in a single cipher in different combinations. This is called a <B>product cipher</B>. Sometimes a block cipher that incorporates layers of substitution and permutation is called a <B>substitution-permutation network</B>, or even an <B>SP network</B>.</P>
<P>Look back at function f of DES. The expansion permutation and P-box perform diffusion; the S-boxes perform confusion. The expansion permutation and P-box are linear; the S-boxes are nonlinear. Each operation is pretty simple on its own; together they work pretty well.</P>
<P>DES also illustrates a few more principles of block cipher design. The first is the idea of an <B>iterated block cipher</B>. This simply means taking a simple round function and iterating it multiple times. Two-round DES isn&#146;t very strong; it takes 5 rounds before all of the output bits are dependent on all of the input bits and all of the key bits [1078,1080]. Sixteen-round DES is strong; 32-round DES is even stronger.</P>
<P><FONT SIZE="+1"><B><I>Feistel Networks</I></B></FONT></P>
<P>Most block algorithms are <B>Feistel networks</B>. This idea dates from the early 1970s [552,553]. Take a block of length <I>n</I> and divide it into two halves of length <I>n</I>/2: <I>L</I> and <I>R</I>. Of course, <I>n</I> must be even. You can define an iterated block cipher where the output of the <I>i</I>th round is determined from the output of the previous round:</P>
<DL>
<DD><I>L</I><SUB>i</SUB> = <I>R</I><SUB>i - 1</SUB>
<DD><I>R</I><SUB>i</SUB> = <I>L</I><SUB>i - 1</SUB> &#8853; <I>f</I>(<I>R</I><SUB>i - 1</SUB>,<I>K</I><SUB>i</SUB>)
</DL>
<P><I>K</I><SUB>i</SUB> is the subkey used in the <I>i</I>th round and <I>f</I> is an arbitrary round function.</P>
<P>You&#146;ve seen this concept in DES, Lucifer, FEAL, Khufu, Khafre, LOKI, GOST, CAST, Blowfish, and others. Why is it such a big deal? The function is guaranteed to be reversible. Because XOR is used to combine the left half with the output of the round function, it is necessarily true that</P>
<DL>
<DD><I>L</I><SUB>i - 1</SUB> &#8853; <I>f</I>(<I>R</I><SUB>i - 1</SUB>,<I>K</I><SUB>i</SUB>) &#8853; <I>f</I>(<I>R</I><SUB>i - 1</SUB>,<I>K</I><SUB>i</SUB>) = <I>L</I><SUB>i - 1</SUB>
</DL>
<P>A cipher that uses this construction is guaranteed to be invertible as long as the inputs to <I>f</I> in each round can be reconstructed. It doesn&#146;t matter what <I>f</I> is; <I>f</I> need not be invertible. We can design <I>f</I> to be as complicated as we please, and we don&#146;t have to implement two different algorithms&#151;one for encryption and another for decryption. The structure of a Feistel network takes care of all this automatically.</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="14-06.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="14-08.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 -->