From: karn@qualcomm.com (Phil Karn)
Date: Wed, 6 Jan 93 21:54:47 PST
To: cypherpunks@toad.com
Subject: Russian analysis of PGP
Message-ID: <9301070552.AA22839@servo>
MIME-Version: 1.0
Content-Type: text/plain


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