Repost in text: IDEA(tm) weakness

[INLINE]
   
                                  Privacy
                                      
                                  [INLINE]
   
   
   How private is your electronic communication ?
   
     [taken from the PGP FAQ]
     
     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.
     
     Encryption in no way should imply illegal activity. It is simply
     intended to keep personal thoughts personal.
     
   Do you trust your mail servers/gateways/virtual redirects ?
   
     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.
     
   Is PGP secure ?
   
     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'>.
     
   Is IDEA secure ?
   
     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 '*'.
     
     The formulas are :
     
     64 bit data => D1, D2, D3 and D4 (all 16 bits)
     
     => K1,K2,K3....rotating extra 25 bits after all 128 bits are used
     
     There are 2 phases in each round and 8 rounds in total + 1 final
     round of just phase 1.
     
     Phase 1:
     
     R1 = D1 * K1
     
     R2 = D2 + K2
     
     R3 = D3 + K3
     
     R4 = D4 * K4
     
     Phase 2:
     
     E1 = R1 xor (((R2 xor R4) + ((R3 xor R1) * K5)) * K6)
     E2 = R3 xor (((R2 xor R4) + ((R3 xor R1) * K5)) * K6)
     E3 = R2 xor ((((R2 xor R4) + ((R3 xor R1) * K5)) * K6) + ((R3 xor
     R1) * K5))
     E4 = R4 xor ((((R2 xor R4) + ((R3 xor R1) * K5)) * K6) + ((R3 xor
     R1) * K5))
     
     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'.
     
     Distribution (where '*' has a bias towards 1 of a)
     
     R1 = a
     
     R2 = even
     
     R3 = even
     
     R4 = a
     
     (a5 & a6 are the bias for K5 and K6)
     
     E1 = (bias a5) * (bias a6)
     
     E2 = (bias a5) * (bias a6)
     
     E3 = (bias a5) - (2 * (bias a5) * (bias a5) * (bias a6)) + ((bias
     a5) * (bias a6))
     
     = (bias a5) * (1 + (bias a6) - (2*(bias a5)*(bias a6)))
     
     E4 = (bias a5) - (2 * (bias a5) * (bias a5) * (bias a6)) + ((bias
     a5) * (bias a6))
     
     = (bias a5) * (1 + (bias a6) - (2*(bias a5)*(bias a6)))
     
     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',...]
     
     eg using a simple 3x3 matrix on second bit, gives (only
     demonstrating the ratio):
     
          if K bit is 1 => bias a ~ (2/8), if K bit is 0 => bias a
     ~(1/8)
     
     ==> We can determine when :
     
     K5=0 and K6=0 as (bias a5) and (bias a6) will be at their highest
     
     ==> E1 & E2 are highest
     
     K5=1 and K6=1 as (bias a5) and (bias a6) are at their lowest
     
     ==> E1 & E2 are Lowest
     
     To determine between K5=0,K6=1 and K5=1,K6=0.
     
     K5 can be determined by check with E3 & E4 as they are both equal
     to :
     
     (bias a5) * (1 + (bias a6) - (2*(bias a5)*(bias a6)))  => directly
     relate to (bias a5) => K5
     
     =>When K5=0, both E3 & E4 will be low.
     
     => When K5=1, both E3 & E4 will be high.
     
     
     The Key rotation start bits are :
     
   Phase K1 K2 K3 K4 K5 K6
   1 0 16 32 48 64 80
   2 96 112 25 41 57 73
   3 89 105 121 9 50 66
   4 82 98 114 2 18 34
   5 75 91 107 123 11 27
   6 43 59 100 116 4 20
   7 36 52 68 84 125 13
   8 29 45 61 77 93 109
   final 22 38 54 70 n/a n/a
   
     
     Working backwards with these distributions you can deduce the key.
     
     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).
     
     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.
     
     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).
     
     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).
     
     It is available under a copyleft license similar to GNU. The Java
     Source code can be found at :
     
       [Application will not be released until beginning of 1999 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: SGOSHA33@mailexcite.com with their request]
     
                                      
   What can we do ?
   
     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.
     
     I have developed an application which does just that. It is
     available under a copyleft license similar to GNU. The Java source
     code can be found here :
     
                                  kiss.zip
     
     To run the application you will need Java installed on your
     machine. Place the files in a directory named KISS. The command
     line is :
     
     java KISS.kiss e <filename>             - encrypt
     
     java KISS.kiss d <filename>             - decrypt (do not add the
     kiss extension to the filename)
     
     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.
     
   
   What is in the pipeline for the future ?
   
     Task 1
     
     The above 'kiss' pre-encryption is not 100% safe from
     non-bruteforce cracking !!
     
     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.
     
     KeyValue xor 1 = CommonValue ==> KeyValue = !CommonValue
     
     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.
     
     Target Release Date : 30/9/98.
     
     Task 2
     
     The integration of both 'kiss' and 'stable'.
     
     Target Release Date : 15/10/98.
     
     Task 3
     
     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].
     
     Target Release Date : 31/10/98.
     
     Task 4
     
     Integration with PGP to provide uses with a much easier encryption
     method.
     
     Target Release Date : 31/11/98.
     
                                                        Author : SGOSHA33
   
                       Return to Albert's Home Page.
   
                                  [INLINE]

I think this is wrong. It claims that the problem
in IDEA comes from the bias of the multiplication
operation... but the multiply in IDEA is over the
integers modulo 65537, with the 0 value
representing 65536, not 0...  this is in fact an
unbiased operation. However I have not attempted
to verify the rest of the logic.

Anonymous writes:
     
>   Is IDEA secure ?
>   
>     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 '*'.
>     
>     The formulas are :
>     
>[...]
>     
>     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'.
     
Greg Rose                                     INTERNET: ggr@qualcomm.com
QUALCOMM Australia        VOICE:  +61-2-9181 4851   FAX: +61-2-9181 5470
Suite 410, Birkenhead Point              http://people.qualcomm.com/ggr/ 
Drummoyne NSW 2047      B5 DF 66 95 89 68 1F C8  EF 29 FA 27 F2 2A 94 8F

> I think this is wrong. It claims that the problem
> in IDEA comes from the bias of the multiplication
> operation... but the multiply in IDEA is over the
> integers modulo 65537, with the 0 value
> representing 65536, not 0...  this is in fact an
> unbiased operation. However I have not attempted
> to verify the rest of the logic.

Correct, multiplication by a non-zero residue modulo 65537 is a
permutation of the non-zero residues.  The central notion behind IDEA is
to use this operation, which can be expressed expeditiously in terms of
the unsigned 16x16->32 multiply, as a builtin wide S-Box.  This is how
IDEA manages to do strong encryption using only a few ordinary arithmetic
and logical instructions with no necessity for table lookup.

I didn't bother to read the rest of the rant. 

-- 
Sponsor the DES Analytic Crack Project
http://www.cyberspace.org/~enoch/crakfaq.html

A quick review reveals that this is clearly another "PGP is broken"
hoax. The author is assuming that IDEA's * operation has a nonuniform
distribution of outputs given a uniform distribution of inputs. Since it
is taken mod 65537 (a prime), this is simply not the case - for constant
x, x * y mod 65537 is a permutation over y. Everything else flows from
this flawed assumption.

The rest of the post is silly as well. "Not tested on real PGP data
because I couldn't find where the IDEA data starts." Very funny, this
info is quite accessible. Also, posting the technique but witholding the
code is ridiculous. If the technique worked, it would get implemented
within hours.

Oh well. It was exciting for a minute or two.

Raph