Russian analysis of PGP

Anybody familiar with the internals of PGP care to comment on this item
that just showed up on sci.crypt?

It's amazing to think that the famous "kremvax" joke was only a decade
ago. Now the Russians are openly reviewing our cryptosystems for us.
May you live in interesting times.

Phil

From qualcom.qualcomm.com!walter!uunet!noc.near.net!lynx!mkagalen Wed Jan  6 21:48:32 PST 1993
Article: 12285 of sci.crypt
Xref: qualcom.qualcomm.com sci.crypt:12285 alt.security.pgp:1003
Newsgroups: sci.crypt,alt.security.pgp
Path: qualcom.qualcomm.com!walter!uunet!noc.near.net!lynx!mkagalen
From: mkagalen@lynx.dac.northeastern.edu (michael kagalenko)
Subject: discussion desired
Message-ID: <1993Jan7.002820.3579@lynx.dac.northeastern.edu>
Organization: Northeastern University, Boston, MA. 02115, USA
Date: Thu, 7 Jan 1993 00:28:20 GMT
Lines: 127

I'd appreciate greately your enlightened opinions on the following article.
(disclaimer : I have no qualification in the Great Science of
Cryptology(tm) ; I'm just posting someone's e-mail)




  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 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;

    - 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;

    - 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.


    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.


    The conclusions:


    It is recommended to use encryption with 1024 bit key length.

    The using of electronic  signature  is  not  recommended  and
    requires the additional study.

    The block encryption algorithm has temporary stability.

    The hashing function  should  be  reduce  in conformity with ISO
    recommendations.

    The using of PGP program in actual version is undesired.




                       The MSU mathematical cryptography
                       problems Laboratory Manager
                       Academician

                          Dr. Sidelnikov V.M.

==END

->    The conclusions:
->    It is recommended to use encryption with 1024 bit key length.
->    The using of electronic  signature  is  not  recommended  and
->    requires the additional study.
->    The block encryption algorithm has temporary stability.
->    The hashing function  should  be  reduce  in conformity with ISO
->    recommendations.
->    The using of PGP program in actual version is undesired.
->                       The MSU mathematical cryptography
->                       problems Laboratory Manager
->                       Academician
->                          Dr. Sidelnikov V.M.

these are serious claims.  What do the authors of the software have
to say about them?  Others?

--

Edward A. Bertsch (eab@msc.edu)   Minnesota Supercomputer Center, Inc.
Operations/User Services          1200 Washington Avenue South
(612) 626-1888 work               Minneapolis, Minnesota  55415
(612) 645-0168 voice mail

From: eab@msc.edu (Edward Bertsch)
   Date: Sat, 9 Jan 93 7:48:46 CST

   these are serious claims.  What do the authors of the software have
   to say about them?  Others?

"Dr. Sidelnikov" has presented some very serious claims, indeed, but has not
produced one shred of evidence to back them up.  Some of his claims, to
wit his assertion that PGP's hashing function is breakable, he could
have very simply demonstrated, without using a lot of clumsy english.
(All he would have needed to do is to produce, two strings, X and Y,
where X != Y and MD5(X) == MD5(Y) --- or better yet, given message
digest Z which someone else picks, such as the test values in RFC-1321,
produce a string X such that MD5(Z) == X.

Some of his other claims, such as his complaint that PGP doesn't contain
any self-checking code to protect against "killer viruses", on the
surface seem to indicate a very shallow analysis of the problem.

Something else to consider is that the source of his posting is somewhat
suspect.  The person who posted it got it from a friend, who got it from
some other net where supposedly Dr. Sidelnikov posted it.  At the
moment, its source sounds like an awful lot of urban legend stories
which many of us have heard before.  An equivalent statement to his
posting might be: 

	"I heard from a friend who heard from an Eminent MIT Professor:
	Don't use XXX, since it uses DES which could be broken."   

While I might have a lot of respect for MIT and its professors, I would
want to see a demonstration of this fact before I would take that kind
of report very seriously.  The same standards should be held to Dr.
Sidelnikov.

							- Ted

P.S.  Note that I am not completely ruling out Dr. Sidelnikov's claims;
but we should keep in mind that up to this point, we have not one shred
of evidence that he is (a) who he claims to be, or (b) his statements
are true.  I would expect that most academics, when publishing something
of this magnitude, would include some sort of evidence to back their
claims up.

P.P.S.  Also note that if his claim about MD5 is true, then we are in a
lot more trouble than just PGP being insecure.  There are an awful lot
of other protocols that use MD5, including Privacy Enhanced Email (PEM).