16-08.html

Applied Cryptography

			<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=16//-->
<!--PAGES=390-392//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="16-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="16-09.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<H3><A NAME="Heading9"></A><FONT COLOR="#000077">16.8 Rambutan</FONT></H3>
<P>Rambutan is a British algorithm, designed by the Communications Electronics Security Group (one of the aliases used by GCHQ). It is only sold as a hardware module and is approved for the protection of classified material up to &#147;Confidential.&#148; The algorithm itself is secret, and the chip is not generally commercially available.
</P>
<P>Rambutan has a 112-bit key (plus parity bits) and can operate in three modes: ECB, CBC, and 8-bit CFB. This strongly indicates that it is a block algorithm, but rumors point elsewhere. Supposedly, it is a LFSR stream cipher. It has five shift registers, each one of a different length around 80 bits. The feedback polynomials are fairly sparse, with only about 10 taps each. Each shift register provides four inputs to a very large and complex nonlinear function which eventually spits out a single bit.</P>
<P>Why call it Rambutan? Perhaps, like the fruit, it&#146;s spiny and forbidding on the outside but soft and yielding inside. On the other hand, maybe that&#146;s not the reason.</P>
<H3><A NAME="Heading10"></A><FONT COLOR="#000077">16.9 Additive Generators</FONT></H3>
<P><B>Additive generators</B> (sometimes called lagged Fibonacci generators) are extremely efficient because they produce random words instead of random bits [863]. They are not secure on their own, but can be used as building blocks for secure generators.</P>
<P>The initial state of the generator is an array of <I>n-</I>bit words: 8-bit words, 16-bit words, 32-bit words, whatever: <I>X</I><SUB>1</SUB>, <I>X</I><SUB>2</SUB>, <I>X</I><SUB>3</SUB>,..., <I>X</I><SUB>m</SUB>. This initial state is the key. The <I>i</I>th word of the generator is</P>
<DL>
<DD><I>X</I><SUB>i</SUB> = (<I>X</I><SUB>i-a</SUB> &#43; <I>X</I><SUB>i-b</SUB> &#43; <I>X</I><SUB>i-c</SUB> &#43;...&#43; <I>X</I><SUB>i-m</SUB>) mod 2<SUP>n</SUP>
</DL>
<P>If the coefficients <I>a, b, c,..., m</I> are chosen right, the period of this generator is at least 2<SUP>n</SUP> - 1. One of the requirements on the coefficients is that the least significant bit forms a maximal-length LFSR.</P>
<P>For example, (55,24,0) is a primitive polynomial mod 2 from Table 16.2. This means that the following additive generator is maximal length.</P>
<DL>
<DD><I>X</I><SUB>i</SUB> = (<I>X</I><SUB>i-55</SUB> &#43; <I>X</I><SUB>i-24</SUB>) mod 2<SUP>n</SUP>
</DL>
<P>This works because the primitive polynomial has three coefficients. If it has more than three, you need some additional requirements to make it maximal length. See [249] for details.
</P>
<P><FONT SIZE="+1"><B><I>Fish</I></B></FONT></P>
<P>Fish is an additive generator based on techniques used in the shrinking generator [190]. It produces a stream of 32-bit words which can be XORed with a plaintext stream to produce ciphertext, or XORed with a ciphertext stream to produce plaintext. The algorithm is named as it is because it is a Fibonacci shrinking generator.
</P>
<P>First, use these two additive generators. The key is the initial values of these generators.</P>
<DL>
<DD><I>A</I><SUB>i</SUB> = (<I>A</I><SUB>i-55</SUB> &#43; <I>A</I><SUB>i-24</SUB>) mod 2<SUP>32</SUP>
<DD><I>B</I><SUB>i</SUB> = (<I>B</I><SUB>i-52</SUB> &#43; <I>B</I><SUB>i-19</SUB>) mod 2<SUP>32</SUP>
</DL>
<P>These sequences are shrunk, as a pair, depending on the least significant bit of <I>B</I><SUB>i</SUB>: if it is 1, use the pair; if it is 0, ignore the pair. <I>C</I><SUB>j</SUB> is the sequence of used words from <I>A</I><SUB>i,</SUB> and <I>D</I><SUB>j</SUB> is the sequence of used words from <I>B</I><SUB>i</SUB>. These words are used in pairs&#151;<I>C</I><SUB>2j</SUB>, <I>C</I><SUB>2j&#43;1</SUB>, <I>D</I><SUB>2j,</SUB> and <I>D</I><SUB>2j&#43;1</SUB>&#151;to generate two 32-bit output words: <I>K2j</I> and <I>K2j</I>&#43;1.</P>
<DL>
<DD><I>E</I><SUB>2j</SUB> = <I>C</I><SUB>2j</SUB> &#8853; (<I>D</I><SUB>2j</SUB> ^ <I>D</I><SUB>2j&#43;1</SUB>)
<DD><I>F</I><SUB>2j</SUB> = <I>D</I><SUB>2j&#43;1</SUB> ^ (<I>E</I><SUB>2j</SUB> ^ <I>C</I><SUB>2j&#43;1</SUB>)
<DD><I>K</I><SUB>2j</SUB> = <I>E</I><SUB>2j</SUB> &#8853; <I>F</I><SUB>2j</SUB>
<DD><I>K</I><SUB>2i&#43;1</SUB> = <I>C</I><SUB>2i&#43;1</SUB> &#8853; <I>F</I><SUB>2j</SUB>
</DL>
<P>This algorithm is fast. On a 33 megahertz 486, a C implementation of Fish encrypts data at 15 megabits per second. Unfortunately, it is also insecure; an attack has a work factor of about 2<SUP>40</SUP> [45].</P>
<P><FONT SIZE="+1"><B><I>Pike</I></B></FONT></P>
<P>Pike is a leaner, meaner version of Fish, brought to you by Ross Anderson, the man who broke Fish [45]. It uses three additive generators. For example:
</P>
<DL>
<DD><I>A</I><SUB>i</SUB> = (<I>A</I><SUB>i-55</SUB> &#43; <I>A</I><SUB>i-24</SUB>) mod 2<SUP>32</SUP>
<DD><I>B</I><SUB>i</SUB> = (<I>B</I><SUB>i-57</SUB> &#43; <I>B</I><SUB>i-7</SUB>) mod 2<SUP>32</SUP>
<DD><I>C</I><SUB>i</SUB> = (<I>C</I><SUB>i-58</SUB> &#43; <I>C</I><SUB>i-19</SUB>) mod 2<SUP>32</SUP>
</DL>
<P>To generate the keystream word, look at the addition carry bits. If all three agree (all are 0 or all are 1), then clock all three generators. If they do not, just clock the two generators that agree. Save the carry bits for next time. The final output is the XOR of the three generators.
</P>
<P>Pike is faster than Fish, since on the average 2.75 steps will be required per output rather than 3. It is far too new to trust, but looks good so far.</P>
<P><FONT SIZE="+1"><B><I>Mush</I></B></FONT></P>
<P>Mush is a mutual shrinking generator. It&#146;s easy to explain [1590]. Take two additive generators: <I>A</I> and <I>B</I>. If the carry bit of <I>A</I> is set, clock <I>B</I>. If the carry bit of <I>B</I> is set, clock <I>A</I>. Clock <I>A</I>, and set the carry bit if there is a carry. Clock <I>B</I>, and set the carry bit if there is a carry. The final output is the XOR of the output of <I>A</I> and <I>B</I>.</P>
<P>The easiest generators to use are the ones from Fish:</P>
<DL>
<DD><I>A</I><SUB>i</SUB> = (<I>A</I><SUB>i-55</SUB> &#43; <I>A</I><SUB>i-24</SUB>) mod 2<SUP>32</SUP>
<DD><I>B</I><SUB>i</SUB> = (<I>B</I><SUB>i-52</SUB> &#43; <I>B</I><SUB>i-19</SUB>) mod 2<SUP>32</SUP>
</DL>
<P>On the average, three generator iterations are required to produce one output word. And if the coefficients of the additive generators are chosen correctly and are relatively prime, the output sequence will be maximal length. I know of no successful attacks, but remember that this algorithm is very new.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="16-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="16-09.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 -->