[103067] in Cypherpunks
IDEA(tm) weakness?
daemon@ATHENA.MIT.EDU (Anonymous)
Sat Sep 19 18:28:19 1998
Date: Sun, 20 Sep 1998 00:04:54 +0200
From: Anonymous <nobody@replay.com>
To: cypherpunks@toad.com
Reply-To: Anonymous <nobody@replay.com>
-----------Next_Part--6DH3NOE586KE
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
-----------Next_Part--6DH3NOE586KE
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<html>
<head>
<meta name="DESCRIPTION" content="Albert Kan's Privacy Page. Containing PGP, IDEA and possible crack methods">
<meta name="KEYWORDS" content="Albert, Kan, Privacy, PGP, IDEA, Crack, SGOSHA33, KISS, STABLE">
<meta name="AUTHOR" content="Albert Kan">
<meta name="OWNER" content="Albert Kan">
<title>Privacy Page</title>
<meta name="Microsoft Theme" content="artsy 111, default"></head>
<body background="_themes/artsy/arttilea.jpg" bgcolor="#333333" text="#FFFF99" link="#FFCC00" vlink="#999966" alink="#66FF00"><!--mstheme--><font face="garamond, times new roman, times">
<!--msthemeseparator--><p align="center"><img src="_themes/artsy/arthsepa.gif" width="300" height="10"></p>
<h1 align="center"><!--mstheme--><font face="arial" color="#FFCC00">Privacy<!--mstheme--></font></h1>
<!--msthemeseparator--><p align="center"><img src="_themes/artsy/arthsepa.gif" width="300" height="10"></p>
<p align="left"> </p>
<p align="left"><font color="#FFFFFF">How private is your electronic communication ?</font></p>
<blockquote>
<p align="left">[taken from the PGP FAQ]</p>
<p align="left">You should encrypt your e-mail for the same reason that you don't write
all of your correspondence on the back of a post card. E-mail is actually far less secure
than the postal system. With the post office, you at least put your letter inside an
envelope to hide it from casual snooping. Take a look at the header area of any e-mail
message that you receive and you will see that it has passed through a number of nodes on
its way to you. Every one of these nodes presents the opportunity for snooping. </p>
<p align="left">Encryption in no way should imply illegal activity. It is simply intended
to keep personal thoughts personal. </p>
</blockquote>
<p align="left"><font color="#FFFFFF">Do you trust your mail servers/gateways/virtual
redirects ?</font></p>
<blockquote>
<p>With the increasing use of virtual email accounts which allow you to keep the same
email address no matter if you change jobs, ISPs, etc, the opportunity for snooping
increases. </p>
</blockquote>
<p><font color="#FFFFFF">Is PGP secure ?</font></p>
<blockquote>
<p>PGP uses acombination of IDEA, RSA and MD5. RSA is used to allow the transfer of
session keys and MD5 is used to generate a unique message digest from the passphrase for
generating the IDEA key and signatures. IDEA is the core algorithm used to encrypt the
actual message. Thus the security of IDEA is also means the security of PGP <read the
section 'is IDEA secure'>.</p>
</blockquote>
<p><font color="#FFFFFF">Is IDEA secure ?</font></p>
<blockquote>
<p><font color="#FF0000">The IDEA algorithm (patented by ASCOM) is the core algorithmm
used in PGP. It is based on a rotating 128 bit key split into 16 bit segments. The
algorthm converts 64 bits of data at a time using the following operations '+', '^'
(exclusive-or) and '*'.</font></p>
<p><font color="#FF0000">The formulas are :</font></p>
<p><font color="#FF0000">64 bit data => D1, D2, D3 and D4 (all 16 bits)</font></p>
<p><font color="#FF0000">=> K1,K2,K3....rotating extra 25 bits after all 128 bits are
used</font></p>
<p><font color="#FF0000">There are 2 phases in each round and 8 rounds in total + 1 final
round of just phase 1.</font></p>
<p><font color="#FF0000">Phase 1:</font></p>
<blockquote>
<p><font color="#FF0000">R1 = D1 * K1</font></p>
<p><font color="#FF0000">R2 = D2 + K2</font></p>
<p><font color="#FF0000">R3 = D3 + K3</font></p>
<p><font color="#FF0000">R4 = D4 * K4</font></p>
</blockquote>
<p><font color="#FF0000">Phase 2:</font></p>
<blockquote>
<p><font color="#FF0000">E1 = R1 xor (((R2 xor R4) + ((R3 xor R1) * K5)) * K6)<br>
E2 = R3 xor (((R2 xor R4) + ((R3 xor R1) * K5)) * K6)<br>
E3 = R2 xor ((((R2 xor R4) + ((R3 xor R1) * K5)) * K6) + ((R3 xor R1) * K5))<br>
E4 = R4 xor ((((R2 xor R4) + ((R3 xor R1) * K5)) * K6) + ((R3 xor R1) * K5))<br>
</font></p>
</blockquote>
<p><font color="#FF0000">Given a large random data message (ie 1000 samples - 64*1000 =
8Kb file). The distribution of the above operations can be used to break the key. ie both
the '+' and the '^' operations give an even distribution but the '*' operator gives a
biased distribution towards '0'.</font></p>
<blockquote>
<p><font color="#FF0000">Distribution (where '*' has a bias towards 1 of a) </font></p>
<p><font color="#FF0000">R1 = a</font></p>
<p><font color="#FF0000">R2 = even</font></p>
<p><font color="#FF0000">R3 = even</font></p>
<p><font color="#FF0000">R4 = a</font></p>
<p><font color="#FF0000">(a5 & a6 are the bias for K5 and K6)</font></p>
<p><font color="#FF0000">E1 = (bias a5) * (bias a6)</font></p>
<p><font color="#FF0000">E2 = (bias a5) * (bias a6)</font></p>
<p><font color="#FF0000">E3 = (bias a5) - (2 * (bias a5) * (bias a5) * (bias a6)) + ((bias
a5) * (bias a6))</font></p>
<blockquote>
<p><font color="#FF0000">= (bias a5) * (1 + (bias a6) - (2*(bias a5)*(bias a6))) </font></p>
</blockquote>
<p><font color="#FF0000">E4 = (bias a5) - (2 * (bias a5) * (bias a5) * (bias a6)) + ((bias
a5) * (bias a6))</font></p>
<blockquote>
<p><font color="#FF0000">= (bias a5) * (1 + (bias a6) - (2*(bias a5)*(bias a6))) </font></p>
</blockquote>
<p><font color="#FF0000">Also as the '*' operator is biased towards its own bit for the
result '1' - approx (60% to 100% depending on bit position). [Working from the low bit
upwards will provide an even greater approximation as then you would have the relevant Key
bits against a random data. ie for 1st bit, it is 100% dependant on the bit for a '1',...]</font></p>
<p><font color="#FF0000">eg using a simple 3x3 matrix on second bit, gives (only
demonstrating the ratio):</font></p>
<p><font color="#FF0000"> if K bit is 1 => bias a ~ (2/8), if K
bit is 0 => bias a ~(1/8) </font></p>
<p><font color="#FF0000">==> We can determine when :</font></p>
<blockquote>
<p><font color="#FF0000">K5=0 and K6=0 as (bias a5) and (bias a6) will be at their highest</font></p>
<blockquote>
<p><font color="#FF0000">==> E1 & E2 are highest</font></p>
</blockquote>
<p><font color="#FF0000">K5=1 and K6=1 as (bias a5) and (bias a6) are at their lowest</font></p>
<blockquote>
<p><font color="#FF0000">==> E1 & E2 are Lowest </font></p>
</blockquote>
<p><font color="#FF0000">To determine between K5=0,K6=1 and K5=1,K6=0. </font></p>
<blockquote>
<p><font color="#FF0000">K5 can be determined by check with E3 & E4 as they are both
equal to :</font></p>
<p><font color="#FF0000">(bias a5) * (1 + (bias a6) - (2*(bias a5)*(bias a6))) =>
directly relate to (bias a5) => K5</font></p>
</blockquote>
<blockquote>
<p><font color="#FF0000">=>When K5=0, both E3 & E4 will be low.</font></p>
<p><font color="#FF0000">=> When K5=1, both E3 & E4 will be high.</font></p>
</blockquote>
<p> </p>
</blockquote>
</blockquote>
<p><font color="#FF0000">The Key rotation start bits are :</font></p>
<div align="center"><center><!--mstheme--></font><table border="1" width="100%" bordercolordark="#999933" bordercolorlight="#CCCC66">
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">Phase</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">K1</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">K2</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">K3</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">K4</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">K5</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">K6</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">1</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">0</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">16</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">32</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">48</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">64</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">80</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">2</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">96</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">112</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">25</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">41</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">57</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">73</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">3</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">89</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">105</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">121</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">9</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">50</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">66</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">4</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">82</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">98</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">114</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">2</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">18</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">34</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">5</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">75</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">91</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">107</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">123</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">11</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">27</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">6</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">43</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">59</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">100</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">116</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">4</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">20</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">7</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">36</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">52</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">68</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">84</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">125</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">13</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">8</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">29</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">45</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">61</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">77</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">93</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">109</font><!--mstheme--></font></td>
</tr>
<tr>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">final</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">22</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">38</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">54</font><!--mstheme--></font></td>
<td width="14%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">70</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">n/a</font><!--mstheme--></font></td>
<td width="15%"><!--mstheme--><font face="garamond, times new roman, times"><font color="#FF0000">n/a</font><!--mstheme--></font></td>
</tr>
</table><!--mstheme--><font face="garamond, times new roman, times">
</center></div><p> </p>
<p><font color="#FF0000">Working backwards with these distributions you can deduce the
key. </font></p>
<p><font color="#FF0000">ie work out K5 (93..108) and K6 (109..124) from its distribution
pattern [using just the distributions for E2 & E3, as E1 & E4 have had the '*'
operation applied in the final phase], then with K5 and K6 work out K1..K4 (22..85). You
now have the key values for K1 to K6 !!!. Modify the Samples such they are back a phase
and repeat (ie for each sample work backwards using known K1..K6 to find the E1..4
values). </font></p>
<p><font color="#FF0000">MAJOR ASSUMPTION : Assume that a large random sample provides a
close to even distribution at the end of each phase (For E2 & E3) such that the
bias (ie a5 & a6) used to determine E2 and E3 are the only significant factors. </font></p>
<p><font color="#FF0000">Reasoning : If the distribution is not even, then it is very much
easier to break (ie only the key values can cause the change in distribution pattern =>
know the pattern, know the key).</font></p>
<p><font color="#FF0000">I have developed a program which does just this (NOTE: not tested
with real PGP data, as I have not had the time to investigate how the PGP file is
structured, ie where the IDEA code starts and ends).</font></p>
<p><font color="#FF0000">It is available under a copyleft license similar to <a href="http://www.gnu.org/copyleft/gpl.html">GNU</a>. The Java Source code can be found at
:</font></p>
<p align="center"><font color="#FF0000">[Application will </font><font color="#00FF00">not
be released until beginning of 1999</font><font color="#FF0000"> when enough people are
aware of the potential problem, and solutions are widely available - thus the threat to
the general users privacy is kept to a minimal. Software houses which would like a delay
in the release of this application so as to provide a solution should email: <a href="mailto:SGOSHA33@mailexcite.com">SGOSHA33@mailexcite.com</a> with their request]</font></p>
<p align="center"> </p>
</blockquote>
<p><font color="#FFFFFF">What can we do ?</font></p>
<blockquote>
<p><font color="#00FFFF">The above crack works because there is a large sample involved.
If however you pre-encrypted the file such that you got your pre-encrypted file and a key
file, where this key file is small and contains only the key required to open the
pre-encrypt file. You then PGP the two files, this would make it much harder to break as
the key file cannot be broken from the sampling technique descibed above.</font></p>
<p><font color="#00FFFF">I have developed an application which does just that. It is
available under a copyleft license similar to <a href="http://www.gnu.org/copyleft/gpl.html">GNU</a>. The Java source code can be found
here : </font></p>
<p align="center"><font color="#00FFFF"><a href="kiss.zip">kiss.zip</a></font></p>
</blockquote>
<blockquote>
<p><font color="#00FFFF">To run the application you will need Java installed on your
machine. Place the files in a directory named KISS. The command line is :</font></p>
<blockquote>
<p><font color="#00FFFF">java KISS.kiss e <filename>
- encrypt</font></p>
<p><font color="#00FFFF">java KISS.kiss d <filename>
- decrypt (do not add
the kiss extension to the filename)</font></p>
</blockquote>
</blockquote>
<blockquote>
<p><font color="#00FFFF">After encryption you will get 2 files. The '.kiss' file is the
encrypted file and the '.lips' file contains the key used to encrypt the file. You should
then encrypt both files with PGP.</font></p>
</blockquote>
<p> </p>
<p><font color="#FFFFFF">What is in the pipeline for the future ?</font></p>
<blockquote>
<p><u>Task 1</u></p>
<p>The above 'kiss' pre-encryption is not 100% safe from non-bruteforce cracking !! </p>
<p>As the majority of files encrypted are text messages which are based mainly on the
characters 'a' to 'z' thus the Ascii codes of the characters are of the form
011xxxxx. From this you can see that the rotating distribution as used above will tend
toward '1'. Thus with enough samples they can deduce the key with the simple equation.</p>
<blockquote>
<p>KeyValue xor 1 = CommonValue ==> KeyValue = !CommonValue</p>
</blockquote>
<p>To prevent this my next application (codename Stable) will be a stabiliser program
which will ensure that the distribution of the data has an even distribution.</p>
<p>Target Release Date : 30/9/98.</p>
<p><u>Task 2</u></p>
<p>The integration of both 'kiss' and 'stable'.</p>
<p>Target Release Date : 15/10/98.</p>
<p><u>Task 3</u></p>
<p>Port of both kiss and stable to C/C++ (for speed and also for Task 4). [Wrote Kiss and
Stable in Java to test the speed of Java and also how it handled bit manipulation
operations].</p>
<p>Target Release Date : 31/10/98.</p>
<p><u>Task 4</u></p>
<p>Integration with PGP to provide uses with a much easier encryption method.</p>
</blockquote>
<blockquote>
<p>Target Release Date : 31/11/98.</p>
</blockquote>
<p align="right"><font color="#808080">Author : SGOSHA33</font></p>
<p align="center">Return to <a href="index.htm" target="_parent">Albert's Home Page</a>.</p>
<!--msthemeseparator--><p align="center"><img src="_themes/artsy/arthsepa.gif" width="300" height="10"></p>
<!--mstheme--></font></body>
</html>
-----------Next_Part--6DH3NOE586KE--
