Newsgroups: sci.crypt,alt.security.pgp
Subject: Re: Zimmermann's responses to Sidelnikov's PGP critique
From: pgut1@cs.aukuni.ac.nz (Peter Gutmann)
Date: Sat, 9 Jan 1993 00:19:28 GMT
Organization: Computer Science Dept. University of Auckland

The following was my initial reaction to the posting - I forwarded it to
the other PGPeople a day or two ago, may as well post it here too -

Some thoughts on the recently posted comments on PGP (I've squashed the text up
a bit to save space).  This isn't a language flame, but some of the English is
a bit hard to make out, so maybe I got a few things I commented on wrong...
 
>About using the electronic signature for protection of commercial information:
>
>The analysis of PGP ver.2.0 program.
>
>---------------------------------------------------------------------
>     THE MOSCOW STATE UNIVERSITY named after m.V. Lomonosov
>   ______________________________________________________________
>
>
>       THE MATHEMATICAL CRYPTOGRAPHY PROBLEMS LABORATORY
>
>The MSU mathematical cryptography problems laboratory employeers with some
>addition specialists were executed the preliminary analysis of PGP ver.2.0
>program.
>
>The preliminary study of working and program source code analysis result in
>following PGP features and problems:
>
>1. The common character problems
>
> - the sequence of random numbers has strong prevalences on bytes (up to 0.05
> ...  0.1 on material of 10000 byte) and strong correlation dependence between
> contiguous bytes;
>
> - the program doesn't check it's own integrity, so it can be infected by
> "virus" which intercept confidential keys and passwords used for their
> protection and save them onto magnetic carriers;
 
The problem is that the virus check itself can be subverted.  There are
solutions in the PGP documentation to this problem...
 
> - the program has not optimal exponentiation algorithm in GF(P) field, when P
> - prime number, which result in low performance;
>
>2. The RSA algorithm realization problems
>
> - the prime numbers reception using in this program (R and q in RSA
> algorithm) permits not less than on two order to reduce the labour-
> intensiveness of factorization; with 256 bit blocks of data lenght it is
> possible to execute the cryptanalysis in real time;
 
Presumably meaning that you can factor 256-bit (~77 digit) keys?  (Hmm, if it's
in real time I'd love to get my paws on the code :-).  I can belive that
keys of this length are easily factored, but what about keys of the size PGP
uses?
 
> - before using RSA the program executes compression and block encryption that
> positively affects on the common stability encryption.
>
>3. The electronic signature problems
>
> - for signature calculation the program originally executes hashing of file
> into number of given length (256, 512 or 1024 bit), but hashing function does
> not corresponds the ISO recommendations;
 
PGP uses a hash function with a 128-bit block size, not 256, 512, 1024.  By
"ISO recommendations" I presume this refers to something like ISO 8731 or ISO
9797, one of the DES-as-a-MAC standards?  This has been shown to be
compromisable...
 
> - when considering the hashing function as the automatic device without
> output, it is enough simply possible to construct the image of reverse
> automatic device and with using the blanks in text files (or free fields in
> some standard formats as in DBF), to compensate the hashing function at
> changed file to former significance.
>
> Thus, it is possible to forge the electronic signature without analysis of
> RSA algorithm.
 
Basically this means breaking MD5, which noone has done yet (the closest was
Tom Berson who broke a severely reduced version at Eurocrypt '92).
 
>4. The block encryption algorithm problems
>
> - when executing analysis on plaintext and ciphertext the linear correlation
> dependences with encryption key were founded (0.01 and more degree);
>
> - also the effective method of decreasing security which reduces the order of
> time necessery to key definition in two times in comparison with exhaustive
> search of all keys (i.e.  algorithm has the labour-intensiveness which is
> equal the root square from labour-intensiveness of the exhaustive search
> algorithm) have been found.
 
Most interesting - I'm sure Xuejia Lai and James Massey would be interested in
this - what is the method used?
[Footnote: The two people metioned above are the inventors of the IDEA cipher] 

>The conclusions:
>
> It is recommended to use encryption with 1024 bit key length.
 
Basically the standard recommendation for RSA.
 
> The using of electronic signature is not recommended and requires the
> additional study.
 
ie "How strong is MD5"?
 
> The block encryption algorithm has temporary stability.
>
> The hashing function should be reduce in conformity with ISO recommendations.
 
Which ISO recommendations?  ISO 8730?
 
Is there any way of contacting the people who did the analysis?  They've raised
all sorts of interesting points which I'd like to look at in more detail...
 
                           -------------------------------
 
Peter.
--
 pgut1@cs.aukuni.ac.nz||p_gutmann@cs.aukuni.ac.nz||gutmann_p@kosmos.wcc.govt.nz
peterg@kcbbs.gen.nz||peter@nacjack.gen.nz||peter@phlarnschlorpht.nacjack.gen.nz
              (In order of preference - one of 'ems bound to work)
           -- Whoever dies with the most email addresses ... wins --

Newsgroups: sci.crypt